A multiphase dynamic programming algorithm for the shortest path problem with resource constraints

DOI10.1016/J.EJOR.2023.11.047MaRDI QIDQ6554642zbMATH OpenFDO

Authors Ilyas Himmich, Issmail Elhallaoui, François Soumis

Publication date 13 June 2024

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.EJOR.2023.11.047

zbMATH Keywords

column generationdynamic programmingshortest path problem with resource constraintstransportation

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Cites work

• A dual algorithm for the constrained shortest path problem
• A Generalized Permanent Labelling Algorithm For The Shortest Path Problem With Time Windows
• A reoptimization algorithm for the shortest path problem with time windows
• A survey of resource constrained shortest path problems: exact solution approaches
• Acceleration strategies for the weight constrained shortest path problem with replenishment
• An algorithm for the resource constrained shortest path problem
• An exact bidirectional pulse algorithm for the constrained shortest path
• An exact method for the biobjective shortest path problem for large-scale road networks
• Crew pairing at Air France
• scientific article; zbMATH DE number 956787 (Why is no real title available?)
• Improved preprocessing, labeling and scaling algorithms for the Weight-Constrained Shortest Path Problem
• Lagrangian relaxation and enumeration for solving constrained shortest-path problems
• New Refinements for the Solution of Vehicle Routing Problems with Branch and Price
• New route relaxation and pricing strategies for the vehicle routing problem
• New state-space relaxations for solving the traveling salesman problem with time windows
• Nodal aggregation of resource constraints in a shortest path problem
• On an exact method for the constrained shortest path problem
• Shortest Path Problems with Resource Constraints
• Shortest path with time constraints on movement and parking
• Simultaneous solution of Lagrangean dual problems interleaved with preprocessing for the weight constrained shortest path problem
• Simultaneous Vehicle and Crew Scheduling in Urban Mass Transit Systems
• Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints
• The shortest path problem with time windows and linear waiting costs
• Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context

Cited in

(1)

• Generic machine-learning-augmented beam search for resource-constrained shortest path reformulations of combinatorial optimization problems

This page was built for publication: A multiphase dynamic programming algorithm for the shortest path problem with resource constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6554642)