Nodal aggregation of resource constraints in a shortest path problem

DOI10.1016/J.EJOR.2004.09.052MaRDI QIDQ2490165zbMATH OpenOpenAlexFDO

Authors A. Nagih, François Soumis

Publication date 28 April 2006

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

Full work available at URL https://doi.org/10.1016/j.ejor.2004.09.052

zbMATH Keywords

Lagrangian relaxationColumn generationDynamic programmingShortest pathResource constraintsSurrogate relaxationResource aggregation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Dynamic programming (90C39)

Recommendations

• Shorter Path Constraints for the Resource Constrained Shortest Path Problem
• Shortest Path Problems with Resource Constraints
• A polyhedral study of the elementary shortest path problem with resource constraints
• scientific article; zbMATH DE number 1670670
• scientific article; zbMATH DE number 1445588
• A survey of resource constrained shortest path problems: exact solution approaches
• Multi-criteria approximation schemes for the resource constrained shortest path problem
• Solving resource constrained shortest path problems with LP-based methods
• An algorithm for the resource constrained shortest path problem

Cites work

• scientific article; zbMATH DE number 3557512 (Why is no real title available?)
• scientific article; zbMATH DE number 1452999 (Why is no real title available?)
• scientific article; zbMATH DE number 956787 (Why is no real title available?)
• A Generalized Permanent Labelling Algorithm For The Shortest Path Problem With Time Windows
• A lower bound for the shortest Hamiltonean path in directed graphs
• A reoptimization algorithm for the shortest path problem with time windows
• Algorithms for finding paths with multiple constraints
• Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• Decomposition and Nondifferentiable Optimization with the Projective Algorithm
• Dynamic Programming State-Space Relaxation for Single-Machine Scheduling
• Dynamic Programming Strategies for the Traveling Salesman Problem with Time Window and Precedence Constraints
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• Multiple cuts in the analytic center cutting plane method
• Plus court chemin avec contraintes d'horaires
• Shortest chain subject to side constraints
• The shortest path problem with time windows and linear waiting costs
• The shortest path problem with two objective functions
• Vehicle Routing with Time Windows

Cited in

(4)

• A multiphase dynamic programming algorithm for the shortest path problem with resource constraints
• Hybrid column generation for large-size covering integer programs: application to transportation planning
• Performances improvement of the column generation algorithm: application to vehicle routing problems
• Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context

Describes a project that uses

Uses Software

• VRP

This page was built for publication: Nodal aggregation of resource constraints in a shortest path problem

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