Vehicle routing problem with elementary shortest path based column generation

DOI10.1016/j.cor.2005.02.029zbMath1086.90048OpenAlexW1999161039MaRDI QIDQ2489135

Alain Chabrier

Publication date: 16 May 2006

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2005.02.029

zbMATH Keywords

Vehicle routingBranch-and-PriceElementary shortest path

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items (40)

Single vehicle routing with predefined client sequence and multiple warehouse returns: the case of two warehouses ⋮ A branch-price-and-cut algorithm for the vehicle routing problem with time windows and multiple deliverymen ⋮ Branch-and-price and constraint programming for solving a real-life technician dispatching problem ⋮ Efficient elementary and restricted non-elementary route pricing ⋮ Integrated optimization of planetary rover layout and exploration routes ⋮ Lifted and local reachability cuts for the vehicle routing problem with time windows ⋮ Using the primal-dual interior point algorithm within the branch-price-and-cut method ⋮ Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles ⋮ Pricing routines for vehicle routing with time windows on road networks ⋮ A shortest-path-based approach for the stochastic knapsack problem with non-decreasing expected overfilling costs ⋮ Models and hybrid methods for the onshore wells maintenance problem ⋮ Classification of Dantzig-Wolfe reformulations for binary mixed integer programming problems ⋮ A general heuristic for vehicle routing problems ⋮ Efficient techniques for the multi-period vehicle routing problem with time windows within a branch and price framework ⋮ The home care crew scheduling problem: preference-based visit clustering and temporal dependencies ⋮ Branch-and-Price Approaches for Real-Time Vehicle Routing with Picking, Loading, and Soft Time Windows ⋮ Clique Inequalities Applied to the Vehicle Routing Problem with Time Windows ⋮ New Refinements for the Solution of Vehicle Routing Problems with Branch and Price ⋮ Air cargo scheduling: integrated models and solution procedures ⋮ A tutorial on column generation and branch-and-price for vehicle routing problems ⋮ Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints ⋮ A robust optimization approach with probe-able uncertainty ⋮ Formulations and exact algorithms for the vehicle routing problem with time windows ⋮ Chvátal-Gomory Rank-1 Cuts Used in a Dantzig-Wolfe Decomposition of the Vehicle Routing Problem with Time Windows ⋮ The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach ⋮ Vehicle routing under time-dependent travel times: the impact of congestion avoidance ⋮ Lagrangian duality applied to the vehicle routing problem with time windows ⋮ Joint vehicle assembly‐routing problems: An integrated modeling and optimization approach ⋮ A branch-and-price-based large neighborhood search algorithm for the vehicle routing problem with time windows ⋮ Vehicle routing with soft time windows and stochastic travel times: a column generation and branch-and-price solution approach ⋮ A survey of resource constrained shortest path problems: Exact solution approaches ⋮ Chebyshev center based column generation ⋮ A column generation and a post optimization VNS heuristic for the vehicle routing problem with multiple time Windows ⋮ Decomposition, reformulation, and diving in university course timetabling ⋮ A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows ⋮ The vehicle routing problem with time windows and temporal dependencies ⋮ A branch-and-cut algorithm for the capacitated profitable tour problem ⋮ Branch-and-price for staff rostering: an efficient implementation using generic programming and nested column generation ⋮ The nuclear medicine production and delivery problem ⋮ A heuristic for cumulative vehicle routing using column generation

Uses Software

• MACS-VRPTW

Cites Work

• A comparison of traditional and constraint-based heuristic methods on vehicle routing problems with side constraints
• Probabilistic diversification and intensification in local search for vehicle routing
• A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows
• Branch-and-Price: Column Generation for Solving Huge Integer Programs
• Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
• Decomposition Principle for Linear Programs
• A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows
• Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW
• An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
• A unified tabu search heuristic for vehicle routing problems with time windows
• Two Evolutionary Metaheuristics For The Vehicle Routing Problem With Time Windows
• Solving vehicle routing problems using constraint programming and metaheuristics

This page was built for publication: Vehicle routing problem with elementary shortest path based column generation