Dynamic graph generation for the shortest path problem in time expanded networks
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.
- Engineering Time-Expanded Graphs for Faster Timetable Information
- Engineering time-expanded graphs for faster timetable information
- Time depending shortest-path problems with applications to railway networks
- Efficient models for timetable information in public transportation systems
- A directed hypergraph model for random time dependent shortest paths
- A Case Study of Joint Online Truck Scheduling and Inventory Management for Multiple Warehouses
- A column generation approach to train timetabling on a corridor
- A Lagrangian heuristic algorithm for a real-world train timetabling problem
- A survey of dynamic network flows
- An efficient algorithm for the evacuation problem in a certain class of networks with uniform path-lengths
- An introduction to network flows over time
- Dynamic graph generation and dynamic rolling horizon techniques in large scale train timetabling
- Dynamic shortest paths minimizing travel times and costs
- Modeling and Solving the Train Timetabling Problem
- Models for railway track allocation
- Nominal and robust train timetabling problems
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Railway track allocation: Models and methods
- Reach for A^*: shortest path algorithms with preprocessing
- The shortest path problem on large-scale real-road networks
- Time-dependent scheduling
- Towards solving very large scale train timetabling problems by Lagrangian relaxation
- Algorithms for a special class of state-dependent shortest path problems with an application to the train routing problem
- Layered graph approaches for combinatorial optimization problems
- Branch-and-refine for solving time-expanded MILP formulations
- Arc flow formulations based on dynamic programming: theoretical foundations and applications
- Dynamic graph generation and dynamic rolling horizon techniques in large scale train timetabling
- DMVP: Foremost Waypoint Coverage of Time-Varying Graphs
- A repeated route-then-schedule approach to coordinated vehicle platooning: algorithms, valid inequalities and computation
- A preconditioned iterative interior point approach to the conic bundle subproblem
- An integrated rolling horizon and adaptive-refinement approach for disjoint trajectories optimization
- Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies
- A minmax regret version of the time-dependent shortest path problem
This page was built for publication: Dynamic graph generation for the shortest path problem in time expanded networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2436645)
