Dynamic graph generation for the shortest path problem in time expanded networks (Q2436645)

Moving objects through a transportation network along the shortest path is one of the frequently solved optimization problems on a finite structure. The computational intricacies arise, when the graph of the network is too large. This case emerges, when timetabling problems are solved and waiting of the objects at network nodes is permitted. One of the ways how to tackle these problems consists in adding the time dimension to the network graph. Then, each original node converts in a potential infinite set of new nodes, where each element is characterized by a pair of the original node and a time instant. The resulting structure is called the time expanded network. The paper deals with a shortest path searching process in the time expanded graph, which satisfies a special condition regarding the cost function. Two ways to master the shortest path problem size are suggested. Both approaches consist in a subsequent enlarging an initial subgraph so that the resulting finite graph called corridor is as small as possible and contains the shortest path concerning the whole extended graph. In the first case, the construction of the corridor is based on forming such a collection of the fastest path, which must be intersected by any path that exceeds the considered time horizon. In the second case, the corridor construction is improved making use of some collection of hyperpaths in the graph of the generalized nodes and arcs, and then shifting the interception sets is employed to accelerate the computational process. The suggested approaches are tested and compared using real train timetabling problems originated in German Railways. Not only simple shortest path problems were solved there, but the complex timetabling problem with time horizon of six hours with discretization of one minute. Furthermore, capacity constraints are involved into the solved problems and the Lagrangean relaxation is used to transform the complex problem to a series of the shortest path problems. Both approaches lead to a considerable reduction of the resulting graph, on which the shortest path problems are solved.