A three-stage approach for the resource-constrained shortest path as a sub-problem in column generation

DOI10.1016/j.cor.2011.03.008zbMath1251.90286OpenAlexW1981162332MaRDI QIDQ1761961

Xiaoyan Zhu, Wilbert E. Wilhelm

Publication date: 15 November 2012

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2011.03.008

zbMATH Keywords

integer programmingcolumn generationresource-constrained shortest-path problem\texttt{CPLEX}pseudo-polynomial timethree-stage solution approach

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

The constrained shortest path problem with stochastic correlated link travel times ⋮ A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs ⋮ On an exact method for the constrained shortest path problem ⋮ An enhanced K-SP algorithm with pruning strategies to solve the constrained shortest path problem ⋮ An exact bidirectional pulse algorithm for the constrained shortest path ⋮ The resource constrained clustered shortest path tree problem: Mathematical formulation and Branch&Price solution algorithm ⋮ A survey of resource constrained shortest path problems: Exact solution approaches ⋮ Lagrangian relaxation for the multiple constrained robust shortest path problem

Uses Software

• CPLEX

Cites Work

• Unnamed Item
• A note on two problems in connexion with graphs
• Enabling flexibility on a dual head placement machine by optimizing platform-tray-feeder picking operations
• A reoptimization algorithm for the shortest path problem with time windows
• Crew pairing at Air France
• A technical review of column generation in integer programming
• Cost-based filtering for shorter path constraints
• A model to optimize placement operations on dual-head placement machines
• A special case of transfer lines balancing by graph approach
• Algorithms for the Weight Constrained Shortest Path Problem
• A Multicommodity Network-Flow Problem with Side Constraints on Paths Solved by Column Generation
• Algorithms for finding paths with multiple constraints
• Shortest chain subject to side constraints
• An algorithm for the resource constrained shortest path problem
• A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows
• Approximation Schemes for the Restricted Shortest Path Problem
• Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW
• Improved preprocessing, labeling and scaling algorithms for the Weight-Constrained Shortest Path Problem
• A dynamic programming algorithm for the shortest path problem with time windows and linear node costs
• A Set Partitioning Approach to the Crew Scheduling Problem
• An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
• Shorter Path Constraints for the Resource Constrained Shortest Path Problem
• Principles and Practice of Constraint Programming – CP 2003
• A simple efficient approximation scheme for the restricted shortest path problem
• Constraint programming based column generation for crew assignment

This page was built for publication: A three-stage approach for the resource-constrained shortest path as a sub-problem in column generation