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

DOI10.1007/S10107-012-0610-3MaRDI QIDQ2436645zbMATH OpenOpenAlexFDO

Authors Frank Fischer, Christoph Helmberg

Publication date 25 February 2014

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10107-012-0610-3

zbMATH Keywords

large scale optimizationshortest pathcorridordynamic graph generationtime expanded networks

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10)

Recommendations

• 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

Cites work

• A Case Study of Joint Online Truck Scheduling and Inventory Management for Multiple Warehouses
• A Lagrangian heuristic algorithm for a real-world train timetabling problem
• A column generation approach to train timetabling on a corridor
• 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

Cited in

(11)

• 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
• Algorithms for a special class of state-dependent shortest path problems with an application to the train routing problem
• Branch-and-refine for solving time-expanded MILP formulations
• Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies
• Arc flow formulations based on dynamic programming: theoretical foundations and applications
• A minmax regret version of the time-dependent shortest path problem
• Layered graph approaches for combinatorial optimization problems
• A preconditioned iterative interior point approach to the conic bundle subproblem
• An integrated rolling horizon and adaptive-refinement approach for disjoint trajectories optimization

Describes a project that uses

Uses Software

• ConicBundle

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)