Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW

DOI10.1287/opre.42.5.977zbMath0815.90064MaRDI QIDQ4319776

Moshe Dror

Publication date: 12 January 1995

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.42.5.977

zbMATH Keywords

set partition; vehicle routing with time windows; relaxation approach

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C60: Abstract computational complexity for mathematical programming problems

90B06: Transportation, logistics and supply chain management

90C39: Dynamic programming

Related Items

A Pricing Algorithm for the Vehicle Routing Problem with Soft Time Windows, The shortest path problem with forbidden paths, A column generation algorithm for the vehicle routing problem with soft time windows, A tutorial on column generation and branch-and-price for vehicle routing problems, Arcs-states models for the vehicle routing problem with time windows and related problems, A column generation approach to the heterogeneous fleet vehicle routing problem, Improved modeling and solution methods for the multi-resource routing problem, The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach, Real-time vehicle rerouting problems with time windows, The undirected capacitated arc routing problem with profits, Single-vehicle scheduling with time window constraints, A new branching strategy for time constrained routing problems with application to backhauling, Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context, A new mixed integer linear model for a rich vehicle routing problem with docking constraints, Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints, Formulations and exact algorithms for the vehicle routing problem with time windows, Vehicle routing problem with elementary shortest path based column generation, Lagrangian duality applied to the vehicle routing problem with time windows, Accelerated label setting algorithms for the elementary resource constrained shortest path problem, A branch-and-price-based large neighborhood search algorithm for the vehicle routing problem with time windows, Optimal routing with failure-independent path protection, Dynamic programming algorithms for the elementary shortest path problem with resource constraints, Chvátal-Gomory Rank-1 Cuts Used in a Dantzig-Wolfe Decomposition of the Vehicle Routing Problem with Time Windows