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.012zbMath1169.90438OpenAlexW1995015521MaRDI QIDQ2371346

Wilbert E. Wilhelm, Xiaoyan Zhu

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

discrete optimizationresource-constrained shortest-path problemcolumn-generation(T) graph theory(T) integer programmingmultiple-choice Knapsack problemmultiple-resourceshortest-path problem with resource windows

Mathematics Subject Classification ID

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

Related Items (4)

The constrained shortest path problem with stochastic correlated link travel times ⋮ On an exact method for the constrained shortest path problem ⋮ A universal concept for robust solving of shortest path problems in dynamically reconfigurable graphs ⋮ A survey of resource constrained shortest path problems: Exact solution approaches

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact methods for the knapsack problem and its generalizations
• A reoptimization algorithm for the shortest path problem with time windows
• The 0-1 knapsack problem with multiple choice constraints
• A minimal algorithm for the multiple-choice knapsack problem
• A penalty function heuristic for the resource constrained shortest path problem
• A model to optimize placement operations on dual-head placement machines
• The shortest route problem with constraints
• Accelerated label setting algorithms for the elementary resource constrained shortest path problem
• 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
• Routing with time windows by column generation
• Shortest path methods: A unifying approach
• Vehicle Routing with Time Windows
• A Column Generation Approach to the Urban Transit Crew Scheduling Problem
• An algorithm for the resource constrained shortest path problem
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• An efficient algorithm for K shortest simple paths
• A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows
• Approximation Schemes for the Restricted Shortest Path Problem
• The Multiple-Choice Knapsack Problem
• Finding the k Shortest Paths
• 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 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
• Simple Heuristics for the Vehicle Routeing Problem with Soft Time Windows
• Finding the K Shortest Loopless Paths in a Network
• Hybrid Heuristics for the Vehicle Routing Problem with Time Windows
• Probabilistic Analyses and Practical Algorithms for the Vehicle Routing Problem with Time Windows
• A simple efficient approximation scheme for the restricted shortest path problem

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