Train dispatchers faces lots of challenges due to conflicts which causes delays of trains as a result of solving possible dispatching problems the network faces. The major challenge is for the train dispatchers to make the right decision and have reliable, cost effective and much more faster approaches needed to solve dispatching problems. This thesis work provides detail information on the implementation of different heuristic algorithms for train dispatchers in solving train dispatching problems. The library data files used are in xml file format and deals with both single and double tracks between main stations. The main objective of this work is to build different heuristic algorithms to solve unexpected delays faced by train dispatchers and to help in making right decisions on steps to take to have reliable and cost effective solution to the problems. These heuristics algorithms proposed were able to help dispatchers in making right decisions when solving train dispatching problems.

The purpose with this report is to develop a network based insertion algorithm and evaluate it on a real-case timetable. The aim of the algorithm is to minimize the effect that that train implementation cause on the other, already scheduled traffic. We meet this purpose by choosing an objective function that maximizes the minimum distance to a conflicting train path. This ensures that the inserted train receives the best possible bottleneck robustness. We construct a graph problem, which solve with a modified version of Dijkstra’s algorithm. The complexity of the algorithm is Ο(s^2 t log⁡(s^2 t). We applied the algorithm on a Swedish timetable, containing 76 stations. The algorithm performs well and manage to obtain the optimal solution for a range of scenarios, which we have evaluated in various experiments. Increased congestion seemed to reduce the problem size. The case also show that a solution’s robustness decreases with increasing total number of departures. One disadvantage with the algorithm is that it cannot detect the best solution among those using the same bottleneck. We propose a solution to this that we hope can be implemented in further studies.

[pt] Esta pesquisa tem por objetivo conceber um sistema de apoio à decisão ao centro de controle operacional no gerenciamento do tráfego ferroviário. O sistema consiste na resolução de conflitos entre trens. Esta pesquisa justifica- se devido à deficiência encontrada pelos controladores de tráfego na tomada de decisões. Atualmente, as prioridades dos trens são pré-estabelecidas e, a partir da análise de um gráfico feito à medida que os eventos ocorrem, o planejamento do despacho de trens é realizado. As prioridades podem ser modificadas ao longo do dia, a partir de alguma ordem superior. Assim, existe a necessidade do desenvolvimento de um novo sistema que auxilie os controladores de tráfego na determinação da melhor solução para os conflitos entre trens. Inicialmente, foram realizados os levantamentos bibliográficos e de dados. Na revisão bibliográfica, foram analisados o sequenciamento de trens, condições de ultrapassagem e de cruzamentos e modelos de programação de trens. Em seguida, foi aplicada uma heurística proposta por Leal (2003) desenvolvida a partir da formulação de Szpigel (1972) e implementada em um programa de computador, na linguagem delphi. Esta heurística apresenta uma solução para os conflitos entre trens. A aplicação foi baseada nos dados fornecidos pela empresa MRS logística, situada em Juiz de Fora (MG). A partir da solução gerada por Leal (2003), foi desenvolvido um gráfico no Excel, utilizando a linguagem visual basic, onde são analisadas as programações dos trens com a solução dos conflitos. O objetivo final desta pesquisa é sugerir uma ferramenta de auxílio para o gerenciamento do tráfego ferroviário, contribuindo para a evolução e eficiência das ferrovias no Brasil. / [en] The objective of this research is to conceive a decision support system for the operational control center in the railroad traffic management. The system consists of the resolution of conflict between trains. The justification of this research is due to the deficiency founded by controllers of traffic in the decisions making. Currently, the trains priorities are previously established and, through the analysis of a done graph to the measure that the events go happening, these priorities can be modified. Thus, there is the necessity of the development of a new system which helps the controllers in the determination of the best alternative. Initially, the bibliographical surveys and the data-collectings had been made. In the bibliographic revision, the sequenciament of trains, ultraticket and crossing conditions, and trains programming models had been analyzed. The next step was the application of an heuristic developed by Leal (2003), based in the formularization of Szpigel (1972), and implemented in a computer program, in the Delphi language, showing the solution of conflicts between trains. The application was based in the data of MRS logistic company, situated in Juiz De Fora (MG). From the solution generated for Leal (2003), a graph in the excel was developed, using visual basic language, and shows the programmings of the trains with conflits solution. The final objective is to suggest a tool for helping the railroad traffic management, contributing for the evolution and efficiency of the railroads in Brazil.

Since the population growth of Stockholm Region is rapid, leading to larger demand on Public Transport and especially metro, four Municipalities of the Region have agreed on the expansion of the metro network. Blue metro line will be extended to Nacka and Hagsatra in the south and Barkarby in the north of the Swedish capital. The new railway line connections have been already planned, while the operation of the expanded line is analyzed in the current thesis. Taking the expected increase of passenger volumes and the operation of the current Blue line into account and following the safety restrictions, two alternative regular timetables of the expanded Blue line, limited to the morning rush service on a working weekday, have been constructed. The operation at stations of low expected passenger volume on the train is evaluated concerning the satisfaction of the operator. The rst alternative metro operation with trac every 4 minutes during the rush hour is concluded to be less ecient than the second alternative with 5 minutes headway, as 21 % larger amount of rolling stock is needed and more seats are not occupied. Finally, in order to achieve higher operational eciency at the low-demanded stations, a third Blue line operation, that is based on the second alternative and it includes short services, operating on a part of the line and not on the full-length of it, has been proposed. Although the number of trains needed for the morning peak hour operation remains constant between the second and third alternative operations, the proportion of empty seats at the analyzed stations is expected to be lower during the last alternative operation, resulting in a metro line scheduling that satises the operator most.

The goal of this thesis is to create an optimization model to optimize the routing of trains within railway stations. This problem is known as the train platforming problem, and the model we present is an integer programming model. By this model we aim to optimize factors such as walking distance, switch usage or platform usage. We validate the model by implementing the model for Linköping station, which is a typical mid size station in the Swedish railway network. This implementation is done for different time horizons, ranging from 2 hours to one day, which corresponds to train sets ranging from 27 to 265 trains. In the conclusion we see that the model is efficient for optimizing the train platforming problem for the implemented station and timetables, and that the model has a possibility to optimize the four objectives tested. Furthermore we see that optimizing certain objectives gives solutions that are also good with regards to other objective functions. / Målet med den här uppsatsen är att skapa en optimeringsmodell för att optimera valet av vägar för tåg genom tågstationer. Modellen vi presenterar är en heltalsmodell, där syftet är att minimera bland annat gångavstånd, användningen av tågväxlar eller användningen av perronger. För att testa modellen presenterar vi en implementation av modellen för stationen i Linköping, vilken är en typisk mellanstor station i det svenska tågnätet. Impplementeringen är gjord för olika tidslängder, från 2 timmar till ett dygn vilket motsvarar dataset från 27 till 265 tåg. Vi drar slutsatsen att modellen på ett effektivt sätt kan lösa valet av tågvägar genom stationen, för de fyra tidtabeller och den station vi har implementerat. Vidare ser vi att modellen har potential att optimera de fyra målfunktioner vi testat och att optimering av några av målfunktionerna ger lösningar som är bra även med hänsyn till de andra målfunktionerna.

Submitted by Rosivalda Pereira (mrs.pereira@ufma.br) on 2017-10-31T20:55:43Z No. of bitstreams: 1 eggo_pinheiro.pdf: 1913399 bytes, checksum: d95298cbe73fd1e96bc181f116178ffa (MD5) / Made available in DSpace on 2017-10-31T20:55:43Z (GMT). No. of bitstreams: 1 eggo_pinheiro.pdf: 1913399 bytes, checksum: d95298cbe73fd1e96bc181f116178ffa (MD5) Previous issue date: 2017-07-19 / Freight railways are the major means of transportation of bulk material, such as iron ore from the origin to the destination. Usually for heavy haul railways, the destination is a port. For the last few years there has been a fast growing demand. However, railway infrastructure capacity increasing is very expensive and require a lot of investiment budget. Therefore, an improvement of train scheduling process is needed to ensure the best and efficient use of the current railway. Nevertheless, in some situations it is overwhelmingly complex to solve, an NP-hard problem. Since all the previous work provided on the Train Timetable Problem is usually only applied locally to a single railway, this work provides a public base benchmark of test railways built by heuristcs. Moreover, this work deals with the train timetabling problem applied to mixed traffic railways with both cargo trains and passenger trains sharing the same resources with different priorities. It is proposed a new mathematical model extended from literature previous work intended to avoid infeasible solutions instead reparing or discarding on these cases. This model contains additional support for parallel multi-track for several railway’s signaling system approaches context as well as overtaking on it without deadlocks possibility. This model considers trains in current position and future departure planned. To achieve an improved train scheduling is applied the Evolutionary Clustering Search (ECS) with multi heuristics approaches and a modified mutation operator of Genetic Algorithm as component of ECS. The experiments shows ECS outperforms almost all tests scenario and the modified mutation operator strongly improve the results / Ferrovias de trens de carga são os principais meios de transporte de materiais, tais como minério de ferro, da sua origem até o seu destino. Geralmente para ferrovias de transporte pesado, o destino é o porto. Nos últimos anos, a demanda de produção tem aumentado assim como o uso da ferrovia para transportá-la, no entanto, a expansão da sua infraestrutura requer um grande investimento. Assim, um planejamento de circulação de trens mais efetivo que maximize a capacidade de tráfego se faz necessária. No entanto, em algumas situações a sua otimização é bastante complexa para ser executada, um problema NP-Difícil. Embora todo trabalho elaborado nesse tema é geralmente aplicado localmente em uma única ferrovia, este trabalho provê uma base genérica de ferrovias gerado por heurísticas. Além disso, esta dissertação lida com o problema de circulação de trens aplicado a ferrovias mistas envolvendo trens de carga assim como trens de passageiros compartilhando o mesmo recurso e com diferentes prioridades. É proposto um novo modelo matemático estendido de um trabalho existente na literatura que procura evitar conflitos ao invés de permitir soluções inviáveis, sendo necessário reparação delas ou descarte. Este modelo lida com uma quantidade variável de linhas em locais de parada compatível com várias abordagens de sistema de sinalização disponíveis, assim como considera ultrapassagens de forma a evitar deadlocks, da mesma forma que trata contextos de trens em circulação como planejados para realizar a otimização. Para encontrar boas soluções, ao planejamento de circulação de trens é aplicado uma abordagem do Evolutionary Clustering Search (ECS) com múltiplas heurísticas, e um operador de mutação modificado do Algoritmo Genético como componente do ECS. Os experimentos computacionais mostraram que o ECS superou quase todos os cenários de teste e o operador de mutação modificado melhorou significativamente os resultados finais.

Orientador: Fernando Antonio Campos Gomide / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-05T20:02:48Z (GMT). No. of bitstreams: 1 MotaFilho_FranciscoOsvaldoMendes_M.pdf: 2700152 bytes, checksum: 3ab58e91f1a3839dae9d39e47d33ff50 (MD5) Previous issue date: 2005 / Resumo: Para obter uma solução satisfatória, algoritmos genéticos avaliam, em geral, um número grande de indivíduos durante o processo evolutivo. É comum, em aplicações práticas, encontrar funções de avaliação computacionalmente complexas e caras. Porém, nesses casos, o tempo é um fator determinante no desempenho de algoritmos genéticos. Dessa forma, os algoritmos genéticos devem encontrar soluções adequadas em curto intervalo de tempo. Uma alternativa promissora para contornar os custos computacionais referentes à função de avaliação considera o fato de que pode ser mais atrativo avaliar diretamente somente indivíduos selecionados e estimar os fitness dos restantes do que avaliar diretamente toda a população. Este trabalho propõe o uso de modelos de estimação de fitness em algoritmos genéticos. Especificamente, são sugeridos modelos de estimação baseados em agrupamento nebuloso supervisionado (Fuzzy C-Means) e não supervisionado (Aprendizagem Participativa). O objetivo é aproximar as funções de avaliação por meio de modelos de estimação de fitness, sem afetar significativamente a qualidade das soluções. Inicialmente, os modelos de estimação propostos são comparados e analisados experimentalmente com alternativas sugeri das por outros autores, utilizando, para isso, problemas de otimização considerados na literatura de algoritmos genéticos. A seguir, os modelos de estimação de fitness são aplicados em um problema real de engenharia, o planejamento de circulação de trens em ferrovias. Este é um caso típico onde o desempenho de cada planejamento exige um tempo significativo. A eficiência dos modelos propostos é verificada e comprovada experimentalmente comparando com os resultados, em instâncias mais simples, fornecidos por modelos de programação matemática e, em instâncias complexas, fornecidos pelo algoritmo genético clássico / Abstract: Genetic algorithms usually need a large number of fitness evaluations before a satisfying result can be obtained. In many real-world applications, fitness evaluation may be computationally complex and costly. In these cases, time is an essential subject in performance analysis of genetic algorithms. Therefore, genetic algorithms should provide good solutions in a short period of time. A promising approach to alleviate the computational cost of evaluations considers the fact that sometimes it is better to evaluate only selected individuals and estimate the fitness of the remaining individuals instead of evaluate a whole population. This work suggests the application of fitness estimation models in genetic algorithms. More specifically, it deals with estimation models based on supervised fuzzy clustering (Fuzzy C-Means) and unsupervised fuzzy clustering (Participatory Learning). The goal is to approximate the evaluation functions through the use of fitness estimation models, without significantly affect the quality of solutions. Initially, the fitness estimation models are compared and analyzed experimentally with other models already proposed in the literature. Their performance are evaluated using benchmark optimization problems found in the genetic algorithms literature. Next, the fitness estimation models are used to solve a real-world engineering problem, namely the train scheduling in a freight rail line. This is a typical case where the performance measure of each schedule demands a considerable amount of time. Once again, the performance of the fitness estimation models are evaluated experimentally, comparing their results with the results provided, for simple instances, by linear programming models and, for complex instances, by the classic genetic algorithm / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

This thesis introduces a new model formulation to solve routing and scheduling problems, with the main applications in answering routing and scheduling problems faced by a sea-cargo shipping company and a railroad company. For the work in sea-cargo routing and scheduling, we focus on the tramp shipping operation. Tramp shipping is a demand-driven type of shipping operation which does not have fixed schedules. The schedules are based on the pickup and download locations of profitable service requests. Given set of products distributed among a set of ports, with each product having pickup and download time windows and a destination port, the problem is to find the schedule for a fleet of ships that maximizes profit over a specified time horizon. The problem is modeled as a Mixed Integer Non-Linear Program and reformulated as an equivalent Mixed Integer Linear Program. Three heuristic methods, along with computational results, are presented. We also exploit the special structure enjoyed by our model and introduce an upper-bounding problem to the model. With a little modification, the model is readily extendable to reflect soft time windows and inter-ship cargo-transfers. The other part of our work deals with train routing and scheduling. A typical train shipment consists of a set of cars having a common origin and destination. To reduce the handling of individual shipments as they travel, shipments are grouped into blocks. The problem is that given sets of blocks to be carried from origins to destinations, construct the most cost effective train routes and schedules and determine block-to-train assignments, such that the number of block transfers (block swaps) between trains, the number of trains used, and some other cost measures are minimized. Incorporating additional precedence requirements, the modeling techniques from the shipping research are employed to formulate a mixed integer nonlinear program for this train routing and scheduling problem. Computational results are presented.