A new exact algorithm for the vehicle routing problem based on \(q\)-paths and \(k\)-shortest paths relaxations

DOI10.1007/BF02098280zbMath0839.90031OpenAlexW2076862344MaRDI QIDQ1908292

Eleni Hadjiconstantinou, Nicos Christofides, Aristide Mingozzi

Publication date: 18 March 1996

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

Full work available at URL: https://doi.org/10.1007/bf02098280

zbMATH Keywords

Lagrangian relaxationvehicle routingshortest path relaxation

Mathematics Subject Classification ID

Integer programming (90C10) Transportation, logistics and supply chain management (90B06) Dynamic programming (90C39)

Related Items (18)

Analytic centre stabilization of column generation algorithm for the capacitated vehicle routing problem ⋮ A min-max vehicle routing problem with split delivery and heterogeneous demand ⋮ A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem ⋮ Distance-constrained capacitated vehicle routing problems with flexible assignment of start and end depots ⋮ A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands ⋮ An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts ⋮ An Integer Linear Programming Local Search for Capacitated Vehicle Routing Problems ⋮ A dual ascent procedure for the set partitioning problem ⋮ Models, relaxations and exact approaches for the capacitated vehicle routing problem ⋮ The multiple disposal facilities and multiple inventory locations rollon-rolloff vehicle routing problem ⋮ A metaheuristic for stochastic service network design ⋮ Robust branch-and-cut-and-price for the capacitated vehicle routing problem ⋮ Lower bounds from state space relaxations for concave cost network flow problems ⋮ A new method for solving capacitated location problems based on a set partitioning approach ⋮ Implicit depot assignments and rotations in vehicle routing heuristics ⋮ An algorithm for the capacitated vehicle routing problem with route balancing ⋮ Stronger \(K\)-tree relaxations for the vehicle routing problem ⋮ A sweep-based algorithm for the fleet size and mix vehicle routing problem

Uses Software

• VRP

Cites Work

• Unnamed Item
• Optimal Routing under Capacity and Distance Restrictions
• State-space relaxation procedures for the computation of bounds to routing problems
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• An efficient algorithm for K shortest simple paths
• Parallel iterative search methods for vehicle routing problems
• Optimal Solution of Vehicle Routing Problems Using Minimum K-Trees
• Validation of subgradient optimization
• A Tabu Search Heuristic for the Vehicle Routing Problem
• A Heuristic Algorithm for the Vehicle-Dispatch Problem
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem

This page was built for publication: A new exact algorithm for the vehicle routing problem based on \(q\)-paths and \(k\)-shortest paths relaxations