A Branch-and-Bound Algorithm for the Capacitated Vehicle Routing Problem on Directed Graphs

DOI10.1287/OPRE.42.5.846zbMath0815.90065OpenAlexW2054515401MaRDI QIDQ4319767

Paolo Toth, Matteo Fischetti, Daniele Vigo

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.846

zbMATH Keywords

branch-and-boundlower boundsasymmetric capacitated vehicle routing problemvehicle capacity constraintsreal-world and random test problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Transportation, logistics and supply chain management (90B06) Deterministic network models in operations research (90B10)

Related Items (32)

A hybrid algorithm for a class of vehicle routing problems ⋮ An exact algorithm for the capacitated shortest spanning arborescence ⋮ Routing problems: A bibliography ⋮ The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems ⋮ Fitness landscape analysis and metaheuristics efficiency ⋮ Exact and heuristic dynamic programming algorithms for the traveling salesman problem with flexible time windows ⋮ A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls ⋮ A matheuristic for the asymmetric capacitated vehicle routing problem ⋮ Heuristic and exact algorithms for a min-max selective vehicle routing problem ⋮ Lifted polynomial size formulations for the homogeneous and heterogeneous vehicle routing problems ⋮ Distance-constrained capacitated vehicle routing problems with flexible assignment of start and end depots ⋮ The capacitated general windy routing problem with turn penalties ⋮ The Vehicle Routing Problem with Release and Due Dates ⋮ Recent advances in vehicle routing exact algorithms ⋮ Robust Branch-Cut-and-Price Algorithms for Vehicle Routing Problems ⋮ Models, relaxations and exact approaches for the capacitated vehicle routing problem ⋮ Exact algorithms for routing problems under vehicle capacity constraints ⋮ A heuristic approach for a scheduling problem with periodic maintenance and sequence-dependent setup times ⋮ Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs ⋮ A mixed constrained (identical) vehicle routing problem for time minimisation ⋮ The family capacitated vehicle routing problem ⋮ A unified pre-training and adaptation framework for combinatorial optimization on graphs ⋮ Vehicle routing with soft time windows and stochastic travel times: a column generation and branch-and-price solution approach ⋮ A unified solution framework for multi-attribute vehicle routing problems ⋮ General VNS for asymmetric vehicle routing problem with time and capacity constraints ⋮ A branch and bound algorithm for dynamic resource allocation in population disease management ⋮ A heuristic algorithm for the asymmetric capacitated vehicle routing problem ⋮ Tolerance-Based vs. Cost-Based Branching for the Asymmetric Capacitated Vehicle Routing Problem ⋮ Asymmetric Multidepot Vehicle Routing Problems: Valid Inequalities and a Branch-and-Cut Algorithm ⋮ Optimization of printed circuit board manufacturing: Integrated modeling and algorithms ⋮ A new ILP-based refinement heuristic for vehicle routing problems ⋮ Heuristics for multi-attribute vehicle routing problems: a survey and synthesis

Uses Software

• VRP

This page was built for publication: A Branch-and-Bound Algorithm for the Capacitated Vehicle Routing Problem on Directed Graphs