Planejamento e roteamento de trens utilizando a meta heurística VNS e técnicas em grafos

Abstract

Railway transportation is one of the most efficient means for overland transportation of high volumes of bulk cargo and a range of commodities. To be highly efficient it is necessary for trains to make few stops and run at optimal speeds defined for each section of railway. A good route, and train traffic planning, can ensure this. Both objectives can be attained by minimizing the two problems: the number of conflicted schedules along routes and the stopping time accrued by trains in service. A route is defined by a set of sequential nodes that connect a source node with a destination node in a network. Conflicts occur when two or more trains try to use the same railway resource at the same time. To optimize performance a method was put forward to find a solution, a method composed of three stages: (a) create viable routes, (b) minimize conflicting schedules of all rail routes and (c) reduce travel times. In the first stage, routes were obtained using graph techniques. In the second stage, conflicts and travel times were minimized by the use of a metaheuristic. Finally, in the third stage, stop times were minimized by eliminating unnecessary delays. To perform the optimization task of the second stage, we decided to implement a multi-objective version of the Variable Neighborhood Search (VNS) algorithm. In fact, the multi-objective version was based on the Skewed VNS scheme. This algorithm, regarding the current objective, is much more suitable for finding solutions in very distant Neighborhoods. Solution proposed by heuristic method, due to the nature of the problem, was NP-Hard regarding computational complexity theory. The developed algorithm was tested in 5 random planar graphs with n vertices and m edges, where n/m is given by: 49/57, 94/112, 184/222, 274/332 and 364/442. The number of running trains in each graph was adjusted to 20% of the number of vertices to each one of them. It was planned as having 73 trains running in the most complex case. Scenarios were created using 1 or 3 routes for each train, for which we used weighted graphs or graphs with unitary weights on their vertices. Furthermore, we used the betweenness centrality measure. It is relevant to emphasize that many conflicts among train routes were purposefully generated, aiming to test the algorithm in extreme conditions. To verify the optimization process quality a Pareto Front was built and its quality was checked using three measures suggested by some papers and a fourth one proposed by this research. The results were very good when compared to proposed objectives and to the complexity of tested topologies