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

DOI10.1287/opre.42.5.977zbMath0815.90064OpenAlexW2156117830MaRDI 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 partitionvehicle routing with time windowsrelaxation approach

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Transportation, logistics and supply chain management (90B06) Dynamic programming (90C39)

Related Items

Task assignment with start time-dependent processing times for personnel at check-in counters ⋮ Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context ⋮ The shortest-path problem with resource constraints with \((k, 2)\)-loop elimination and its application to the capacitated arc-routing problem ⋮ Efficient elementary and restricted non-elementary route pricing ⋮ Optimal relay node placement in delay constrained wireless sensor network design ⋮ A column generation approach for a multi-attribute vehicle routing problem ⋮ Tramp ship routing and scheduling with voyage separation requirements ⋮ A comparison of column-generation approaches to the synchronized pickup and delivery problem ⋮ Analytic centre stabilization of column generation algorithm for the capacitated vehicle routing problem ⋮ Robust Team Orienteering Problem with Decreasing Profits ⋮ Arcs-states models for the vehicle routing problem with time windows and related problems ⋮ Using the primal-dual interior point algorithm within the branch-price-and-cut method ⋮ A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands ⋮ Pricing routines for vehicle routing with time windows on road networks ⋮ A column generation approach for the location-routing problem with time windows ⋮ A branch-and-price algorithm for the minimum latency problem ⋮ A branch-price-and-cut algorithm for the workover rig routing problem ⋮ A branch-price-and-cut algorithm for the commodity constrained split delivery vehicle routing problem ⋮ Solving resource constrained shortest path problems with LP-based methods ⋮ A new branching strategy for time constrained routing problems with application to backhauling ⋮ A branch-and-price algorithm for location-routing problems with pick-up stations in the last-mile distribution system ⋮ A column generation approach to the heterogeneous fleet vehicle routing problem ⋮ Efficient techniques for the multi-period vehicle routing problem with time windows within a branch and price framework ⋮ Improved modeling and solution methods for the multi-resource routing problem ⋮ The arc-item-load and related formulations for the cumulative vehicle routing problem ⋮ Improving Column Generation for Vehicle Routing Problems via Random Coloring and Parallelization ⋮ An exact algorithm for Agile Earth Observation Satellite scheduling with time-dependent profits ⋮ Medical waste collection considering transportation and storage risk ⋮ Exact approaches to the robust vehicle routing problem with time windows and multiple deliverymen ⋮ The home care crew scheduling problem: preference-based visit clustering and temporal dependencies ⋮ The vehicle routing problem with service level constraints ⋮ A branch-and-price algorithm for the multi-depot heterogeneous-fleet pickup and delivery problem with soft time windows ⋮ A set-covering based heuristic algorithm for the periodic vehicle routing problem ⋮ Estimating the marginal cost to deliver to individual customers ⋮ Using fixed paths to improve branch-and-cut algorithms for precedence-constrained routing problems ⋮ Selective arc‐ng pricing for vehicle routing ⋮ Asymmetric probabilistic minimum-cost Hamiltonian cycle problem considering arc and vertex failures ⋮ A branch‐and‐price‐and‐cut algorithm for the truck‐drone routing problem with simultaneously delivery and pickup ⋮ New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows ⋮ Clique Inequalities Applied to the Vehicle Routing Problem with Time Windows ⋮ Solving a real-world multi-depot multi-period petrol replenishment problem with complex loading constraints ⋮ Two extended formulations for the virtual network function placement and routing problem ⋮ A branch‐and‐price‐based heuristic for the vehicle routing problem with two‐dimensional loading constraints and time windows ⋮ A computational study of solution approaches for the resource constrained elementary shortest path problem ⋮ A new mixed integer linear model for a rich vehicle routing problem with docking constraints ⋮ A tutorial on column generation and branch-and-price for vehicle routing problems ⋮ Analysis of three mathematical models of the staff rostering problem ⋮ A Joint Vehicle Routing and Speed Optimization Problem ⋮ A column generation approach for the split delivery vehicle routing problem ⋮ 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 ⋮ Finding the nucleolus of the vehicle routing game with time windows ⋮ Chvátal-Gomory Rank-1 Cuts Used in a Dantzig-Wolfe Decomposition of the Vehicle Routing Problem with Time Windows ⋮ Exact methods for solving the elementary shortest and longest path problems ⋮ A branch-and-price algorithm for a vehicle routing with demand allocation problem ⋮ Route relaxations on GPU for vehicle routing problems ⋮ Branch-and-price approaches for the multiperiod technician routing and scheduling 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 distance constrained multiple vehicle traveling purchaser problem ⋮ A three-stage approach for the resource-constrained shortest path as a sub-problem in column generation ⋮ A column generation algorithm for the vehicle routing problem with soft time windows ⋮ Vehicle routing problem with elementary shortest path based column generation ⋮ The undirected capacitated arc routing problem with profits ⋮ Solving a vehicle routing problem with resource conflicts and makespan objective with an application in car body manufacturing ⋮ Lagrangian duality applied to the vehicle routing problem with time windows ⋮ Exact solution of the soft-clustered vehicle-routing 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 ⋮ A rollout algorithm for the resource constrained elementary shortest path problem ⋮ The shortest path problem with forbidden paths ⋮ Exact methods for mono-objective and bi-objective multi-vehicle covering tour problems ⋮ A survey of resource constrained shortest path problems: Exact solution approaches ⋮ A branch-price-and-cut algorithm for the min-maxk-vehicle windy rural postman problem ⋮ A branch-and-cut-and-price algorithm for the multi-trip separate pickup and delivery problem with time windows at customers and facilities ⋮ Chebyshev center based column generation ⋮ The vehicle routing problem with time windows and temporal dependencies ⋮ Shortest path with acceleration constraints: complexity and approximation algorithms ⋮ Using column generation to compute lower bound sets for bi-objective combinatorial optimization problems ⋮ Single-vehicle scheduling with time window constraints ⋮ A Pricing Algorithm for the Vehicle Routing Problem with Soft Time Windows ⋮ On Accuracy of Approximation for the Resource Constrained Shortest Path Problem ⋮ A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints ⋮ A compact transformation of arc routing problems into node routing problems ⋮ Robust vehicle routing under uncertainty via branch-price-and-cut ⋮ Accelerated label setting algorithms for the elementary resource constrained shortest path problem ⋮ Dynamic programming algorithms for the elementary shortest path problem with resource constraints ⋮ New exact and heuristic algorithms to solve the prize-collecting job sequencing problem with one common and multiple secondary resources ⋮ Branch-and-refine for solving time-expanded MILP formulations ⋮ A heuristic for cumulative vehicle routing using column generation