Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations

DOI10.1007/BF01589353zbMath0461.90067MaRDI QIDQ3911683

Paolo Toth, Aristide Mingozzi, Nicos Christofides

Publication date: 1981

Published in: Mathematical Programming (Search for Journal in Brave)

zbMATH Keywords

vehicle routing; Lagrangean relaxation; spanning tree; computational results; exact algorithms; central facility; tree search algorithms; known demands; minimization of total distance travelled; multiple travelling salesman; shortest path relaxations

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C05: Trees

05C35: Extremal problems in graph theory

65K05: Numerical mathematical programming methods

90C39: Dynamic programming

Related Items

A generalized exchange heuristic for the capacitated vehicle routing problem, A branch and bound algorithm for the capacitated vehicle routing problem, A Lagrangean relaxation heuristic for vehicle routing, Implementing an insertion heuristic for vehicle routing on parallel hardware, Models, relaxations and exact approaches for the capacitated vehicle routing problem, A tabu search algorithm for the open vehicle routing problem, A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows, Incorporating inventory and routing costs in strategic location models, An approximation algorithm for the pickup and delivery vehicle routing problem on trees, A column generation approach to the heterogeneous fleet vehicle routing problem, Recent advances in vehicle routing exact algorithms, An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts, A dual ascent procedure for the set partitioning problem, Vehicle routing via column generation, Microcomputer-based algorithms for large scale shortest path problems, Implementation techniques for the vehicle routing problem, Heuristics for unequal weight delivery problems with a fixed error guarantee, The vehicle routing problem with backhauls, A result on projection for the vehicle routing problem, Solving symmetric vehicle routing problems asymmetrically, The pickup and delivery problem with time windows, Topological design of telecommunication networks --- local access design methods, The vehicle routing problem: An overview of exact and approximate algorithms, A heuristic algorithm for the asymmetric capacitated vehicle routing problem, A genetic algorithm for service level based vehicle scheduling, A new subtour elimination constraint for the vehicle routing problem, MIP modelling of changeovers in production planning and scheduling problems, Topological design of ring networks, A heuristic solution to the warehouse location-routing problem, A branch-and-cut algorithm for vehicle routing problems, A TSSP+1 decomposition strategy for the vehicle routing problem, An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts, Improvement heuristics for the vehicle routing problem based on simulated annealing, A dynamic programming based algorithm for the crew scheduling problem., D-Ants: Savings Based Ants divide and conquer the vehicle routing problem., Vehicle routing-scheduling for waste collection in Hanoi, Stronger \(K\)-tree relaxations for the vehicle routing problem, A new exact algorithm for the vehicle routing problem based on \(q\)-paths and \(k\)-shortest paths relaxations, Routing problems: A bibliography, A parallel implementation of the TSSP+1 decomposition for the capacity-constrained vehicle routing problem, A new heuristic for the fleet size and mix vehicle routing problem, Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, A parallel route building algorithm for the vehicle routing and scheduling problem with time windows, Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation, A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands, Formulations and exact algorithms for the vehicle routing problem with time windows, Nodal aggregation of resource constraints in a shortest path problem, Robust branch-and-cut-and-price for the capacitated vehicle routing problem, A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows, Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem, Arc routing in a node routing environment, Savings based ant colony optimization for the capacitated minimum spanning tree problem, Solving capacitated arc routing problems using a transformation to the CVRP, Accelerated label setting algorithms for the elementary resource constrained shortest path problem, Split delivery routing, Two exact algorithms for the distance-constrained vehicle routing problem, A reactive MILP approach to the multidepot heterogeneous fleet vehicle routing problem with time windows, A Heuristic Algorithm for Multi-Period Delivery Planning Problems, Column Generation Algorithms for the Capacitated m-Ring-Star Problem, VEHICLE ROUTE OPTIMIZATION FOR RFID INTEGRATED WASTE COLLECTION SYSTEM, The Minimum Spanning Tree Problem with Time Window Constraints, State-space relaxation procedures for the computation of bounds to routing problems

Uses Software

• VRP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The travelling salesman problem as a constrained shortest path problem: Theory and computational experience
• On a routing problem
• Integer Programming Formulation of Traveling Salesman Problems
• A Heuristic Algorithm for the Vehicle-Dispatch Problem
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem