Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context

DOI10.1016/J.EJOR.2006.10.012MaRDI QIDQ2371346zbMATH OpenOpenAlexFDO

Authors Xiaoyan Zhu, Wilbert E. Wilhelm

Publication date 4 July 2007

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

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

zbMATH Keywords

(T) graph theory(T) integer programmingcolumn-generationdiscrete optimizationmultiple-choice Knapsack problemmultiple-resourceresource-constrained shortest-path problemshortest-path problem with resource windows

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• A three-stage approach for the resource-constrained shortest path as a sub-problem in column generation
• Implementation of a three-stage approach for the dynamic resource-constrained shortest-path sub-problem in branch-and-price
• Solving resource constrained shortest path problems with LP-based methods
• New dynamic programming algorithms for the resource constrained elementary shortest path problem
• Nodal aggregation of resource constraints in a shortest path problem

Cites work

• A Column Generation Approach to the Urban Transit Crew Scheduling Problem
• A minimal algorithm for the multiple-choice knapsack problem
• A model to optimize placement operations on dual-head placement machines
• A multicommodity network-flow problem with side constraints on paths solved by column generation
• A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows
• A penalty function heuristic for the resource constrained shortest path problem
• A reoptimization algorithm for the shortest path problem with time windows
• A Set Partitioning Approach to the Crew Scheduling Problem
• A simple efficient approximation scheme for the restricted shortest path problem
• Accelerated label setting algorithms for the elementary resource constrained shortest path problem
• Algorithms for finding paths with multiple constraints
• Algorithms for the weight constrained shortest path problem
• An algorithm for the resource constrained shortest path problem
• An efficient algorithm for K shortest simple paths
• An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
• Approximation Schemes for the Restricted Shortest Path Problem
• Exact methods for the knapsack problem and its generalizations
• Finding the K Shortest Loopless Paths in a Network
• Finding the k Shortest Paths
• scientific article; zbMATH DE number 1670670 (Why is no real title available?)
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Hybrid Heuristics for the Vehicle Routing Problem with Time Windows
• Improved preprocessing, labeling and scaling algorithms for the Weight-Constrained Shortest Path Problem
• Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW
• Probabilistic Analyses and Practical Algorithms for the Vehicle Routing Problem with Time Windows
• Routing with time windows by column generation
• Shortest chain subject to side constraints
• Shortest path methods: A unifying approach
• Simple Heuristics for the Vehicle Routeing Problem with Soft Time Windows
• The 0-1 knapsack problem with multiple choice constraints
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• The Multiple-Choice Knapsack Problem
• The shortest route problem with constraints
• Vehicle Routing with Time Windows

Cited in

(10)

• A universal concept for robust solving of shortest path problems in dynamically reconfigurable graphs
• A three-stage approach for the resource-constrained shortest path as a sub-problem in column generation
• A survey of resource constrained shortest path problems: exact solution approaches
• Dynamic programming-based column generation on time-expanded networks: application to the dial-a-flight problem
• The constrained shortest path problem with stochastic correlated link travel times
• On an exact method for the constrained shortest path problem
• Implementation of a three-stage approach for the dynamic resource-constrained shortest-path sub-problem in branch-and-price
• Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW
• A column generation method for inverse shortest path problems
• A multiphase dynamic programming algorithm for the shortest path problem with resource constraints

Describes a project that uses

Uses Software

• Knapsack

This page was built for publication: Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context

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