A three-stage approach for the resource-constrained shortest path as a sub-problem in column generation
From MaRDI portal
Publication:1761961
DOI10.1016/j.cor.2011.03.008zbMath1251.90286MaRDI 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
integer programming; column generation; resource-constrained shortest-path problem; \texttt{CPLEX}; pseudo-polynomial time; three-stage solution approach
90C35: Programming involving graphs or networks
90C10: Integer programming
05C38: Paths and cycles
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
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, The constrained shortest path problem with stochastic correlated link travel times, On an exact method for the constrained shortest path problem, A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs, An enhanced K-SP algorithm with pruning strategies to solve the constrained shortest path problem, Lagrangian relaxation for the multiple constrained robust shortest path problem, A survey of resource constrained shortest path problems: Exact solution approaches
Uses Software
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