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

From MaRDI portal

Publication:3911683

Jump to:navigation, search

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

Programming involving graphs or networks (90C35) Trees (05C05) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05) Dynamic programming (90C39)

Related Items

Min-Max vs. Min-Sum vehicle routing: a worst-case analysis ⋮ Exact Algorithms for the Chance-Constrained Vehicle Routing Problem ⋮ Synchronized Traveling Salesman Problem ⋮ Improving Column Generation for Vehicle Routing Problems via Random Coloring and Parallelization ⋮ A Heuristic Algorithm for Multi-Period Delivery Planning Problems ⋮ Column elimination for capacitated vehicle routing problems ⋮ Two-phase algorithm for solving vehicle routing problem with time windows ⋮ The Minimum Spanning Tree Problem with Time Window Constraints ⋮ Metaheuristics with variable diversity control and neighborhood search for the heterogeneous site-dependent multi-depot multi-trip periodic vehicle routing problem ⋮ Column Generation Algorithms for the Capacitated m-Ring-Star Problem ⋮ Integrating driver behavior into last-mile delivery routing: combining machine learning and optimization in a hybrid decision support framework ⋮ A branch-cut-and-price algorithm for the cumulative capacitated vehicle routing problem ⋮ An Exact Algorithm Based on Cut-and-Column Generation for the Capacitated Location-Routing Problem ⋮ Routing a Heterogeneous Fleet of Vehicles ⋮ Robust Branch-Cut-and-Price Algorithms for Vehicle Routing Problems ⋮ Two exact algorithms for the distance-constrained vehicle routing problem ⋮ Split delivery routing ⋮ Nodal aggregation of resource constraints in a shortest path problem ⋮ Robust branch-and-cut-and-price for the capacitated vehicle routing problem ⋮ VEHICLE ROUTE OPTIMIZATION FOR RFID INTEGRATED WASTE COLLECTION SYSTEM ⋮ A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem ⋮ Valid inequalities for the fleet size and mix vehicle routing problem with fixed costs ⋮ A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows ⋮ A rollout algorithm for the resource constrained elementary shortest path problem ⋮ Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem ⋮ A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem ⋮ A generalized exchange heuristic for the capacitated vehicle routing problem ⋮ Chain partitioning as a key element for building vehicle routing problem heuristics ⋮ A survey of resource constrained shortest path problems: Exact solution approaches ⋮ New State-Space Relaxations for Solving the Traveling Salesman Problem with Time Windows ⋮ Unnamed Item ⋮ State-space relaxation procedures for the computation of bounds to routing problems ⋮ A set covering based matheuristic for a real‐world city logistics problem ⋮ A reactive MILP approach to the multidepot heterogeneous fleet vehicle routing problem with time windows ⋮ 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 ⋮ A heuristic solution to the warehouse location-routing problem ⋮ On the Bellman's principle of optimality ⋮ 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 ⋮ Implementation techniques for the vehicle routing problem ⋮ A branch-and-cut algorithm for vehicle routing problems ⋮ Efficient elementary and restricted non-elementary route pricing ⋮ ILP formulation of the degree-constrained minimum spanning hierarchy problem ⋮ A TSSP+1 decomposition strategy for the vehicle routing problem ⋮ The electric two-echelon vehicle routing problem ⋮ Heuristics for unequal weight delivery problems with a fixed error guarantee ⋮ An effective iterated two-stage heuristic algorithm for the multiple traveling salesmen problem ⋮ A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows ⋮ Multiple asymmetric traveling salesmen problem with and without precedence constraints: performance comparison of alternative formulations ⋮ A hybrid heuristic procedure for the windy rural postman problem with zigzag time windows ⋮ Enhanced branch-cut-and-price algorithm for heterogeneous fleet vehicle routing problems ⋮ Vehicle routing with probabilistic capacity constraints ⋮ The pickup and delivery problem with time windows and handling operations ⋮ Incorporating inventory and routing costs in strategic location models ⋮ An open source spreadsheet solver for vehicle routing problems ⋮ A branch-and-price algorithm for the minimum latency problem ⋮ An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times ⋮ A unified exact method for solving different classes of vehicle routing problems ⋮ Exact algorithms for the double vehicle routing problem with multiple stacks ⋮ A branch-price-and-cut algorithm for the commodity constrained split delivery vehicle routing problem ⋮ An approximation algorithm for the pickup and delivery vehicle routing problem on trees ⋮ A new exact algorithm for the vehicle routing problem based on \(q\)-paths and \(k\)-shortest paths relaxations ⋮ Routing problems: A bibliography ⋮ Improved branch-cut-and-price for capacitated vehicle routing ⋮ A column generation approach to the heterogeneous fleet vehicle routing problem ⋮ A Lagrangean relaxation heuristic for vehicle routing ⋮ The vehicle routing problem with backhauls ⋮ The arc-item-load and related formulations for the cumulative vehicle routing problem ⋮ A parallel implementation of the TSSP+1 decomposition for the capacity-constrained vehicle routing problem ⋮ Branch-and-price algorithms for the two-echelon capacitated vehicle routing problem ⋮ Branch-cut-and-price for the vehicle routing problem with simultaneous pickup and delivery ⋮ A min-max vehicle routing problem with split delivery and heterogeneous demand ⋮ A result on projection for the vehicle routing problem ⋮ The vehicle routing problem with service level constraints ⋮ An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts ⋮ Improvement heuristics for the vehicle routing problem based on simulated annealing ⋮ Pricing strategies for capacitated ring-star problems based on dynamic programming algorithms ⋮ Approximation algorithms for constructing spanning \(K\)-trees using stock pieces of bounded length ⋮ Heuristic and exact algorithms for a min-max selective vehicle routing problem ⋮ Improved lower bounds and exact algorithm for the capacitated arc routing problem ⋮ A dynamic programming based algorithm for the crew scheduling problem. ⋮ A computational study of solution approaches for the resource constrained elementary shortest path problem ⋮ Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints ⋮ A branch-price-and-cut algorithm for the capacitated multiple vehicle traveling purchaser problem with unitary demand ⋮ Adaptive large neighborhood search on the graphics processing unit ⋮ D-Ants: Savings Based Ants divide and conquer the vehicle routing problem. ⋮ Solving symmetric vehicle routing problems asymmetrically ⋮ Recent advances in vehicle routing exact algorithms ⋮ Branch-and-price for a multi-attribute technician routing and scheduling problem ⋮ A branch-and-cut-and-price algorithm for the electric vehicle routing problem with multiple technologies ⋮ The pickup and delivery problem with time windows ⋮ Topological design of telecommunication networks --- local access design methods ⋮ 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 ⋮ An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts ⋮ A branch\&price\&cut algorithm for the vehicle routing problem with intermediate replenishment facilities ⋮ A branch-and-price algorithm for a vehicle routing with demand allocation problem ⋮ A dual ascent procedure for the set partitioning problem ⋮ Route relaxations on GPU for vehicle routing problems ⋮ The traveling purchaser problem and its variants ⋮ The vehicle routing problem: An overview of exact and approximate algorithms ⋮ Solving the team orienteering arc routing problem with a column generation approach ⋮ The demand weighted vehicle routing problem ⋮ Implementing an insertion heuristic for vehicle routing on parallel hardware ⋮ The distance constrained multiple vehicle traveling purchaser problem ⋮ Models, relaxations and exact approaches for the capacitated vehicle routing problem ⋮ Exact algorithms for routing problems under vehicle capacity constraints ⋮ A tabu search algorithm for the open vehicle routing problem ⋮ A metaheuristic for stochastic service network design ⋮ A new heuristic for the fleet size and mix vehicle routing problem ⋮ A branch and bound algorithm for the capacitated vehicle routing problem ⋮ Improved lower bounds for the split delivery vehicle routing problem ⋮ An exact solution framework for a broad class of vehicle routing problems ⋮ Exact algorithms for the chance-constrained vehicle routing problem ⋮ A new efficient approach for solving the capacitated vehicle routing problem using the gravitational emulation local search algorithm ⋮ Industrial and tramp ship routing problems: closing the gap for real-scale instances ⋮ Empirical study of exact algorithms for the multi-objective spanning tree ⋮ A heuristic algorithm for the asymmetric capacitated vehicle routing problem ⋮ A genetic algorithm for service level based vehicle scheduling ⋮ Dynamic vehicle routing with time windows in theory and practice ⋮ A new subtour elimination constraint for the vehicle routing problem ⋮ MIP modelling of changeovers in production planning and scheduling problems ⋮ Stronger \(K\)-tree relaxations for the vehicle routing problem ⋮ Vehicle routing-scheduling for waste collection in Hanoi ⋮ Bilayer local search enhanced particle swarm optimization for the capacitated vehicle routing problem ⋮ Heuristic optimization for multi-depot vehicle routing problem in ATM network model ⋮ A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints ⋮ A branch-and-cut algorithm for the capacitated profitable tour problem ⋮ A compact transformation of arc routing problems into node routing problems ⋮ Vehicle routing via column generation ⋮ Topological design of ring networks ⋮ Microcomputer-based algorithms for large scale shortest path problems ⋮ A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms ⋮ An exact algorithm for the precedence-constrained single-machine scheduling problem

Uses Software

VRP

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:3911683&oldid=17570804"