A new branch-and-cut algorithm for the capacitated vehicle routing problem

DOI10.1007/S10107-003-0481-8zbMath1073.90068DBLPjournals/mp/LysgaardLE04OpenAlexW2017070898WikidataQ57702321 ScholiaQ57702321MaRDI QIDQ1881569

Richard W. Eglese, Jens Lysgaard, Adam N. Letchford

Publication date: 5 October 2004

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-003-0481-8

zbMATH Keywords

vehicle routingseparationbranch-and- cut

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic network models in operations research (90B10)

Related Items (only showing first 100 items - show all)

New Families of Valid Inequalities for the Two-Echelon Vehicle Routing Problem ⋮ Balanced vehicle routing: polyhedral analysis and branch-and-cut algorithm ⋮ Efficient elementary and restricted non-elementary route pricing ⋮ A branch-and-cut algorithm for the vehicle routing problem with two-dimensional loading constraints ⋮ The discrete time window assignment vehicle routing problem ⋮ Stronger multi-commodity flow formulations of the capacitated vehicle routing problem ⋮ Branch-and-cut-and-price for the electric vehicle routing problem with time windows, piecewise-linear recharging and capacitated recharging stations ⋮ A branch-and-cut framework for the consistent traveling salesman problem ⋮ Bin packing and cutting stock problems: mathematical models and exact algorithms ⋮ A branch-and-cut algorithm for the preemptive swapping problem ⋮ A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands ⋮ The production routing problem: a review of formulations and solution algorithms ⋮ Battery swap station location-routing problem with capacitated electric vehicles ⋮ Managing platelet supply through improved routing of blood collection vehicles ⋮ An exact algorithm for a vehicle-and-driver scheduling problem ⋮ A variable MIP neighborhood descent algorithm for managing inventory and distribution of cash in automated Teller machines ⋮ A branch-and-cut algorithm for the time window assignment vehicle routing problem ⋮ A unified exact method for solving different classes of vehicle routing problems ⋮ Improved branch-cut-and-price for capacitated vehicle routing ⋮ A general heuristic for vehicle routing problems ⋮ A symmetry-free polynomial formulation of the capacitated vehicle routing problem ⋮ Modeling and solving profitable location and distribution problems ⋮ Branch-cut-and-price for the vehicle routing problem with simultaneous pickup and delivery ⋮ The two-echelon inventory-routing problem with fleet management ⋮ DVRP: a hard dynamic combinatorial optimisation problem tackled by an evolutionary hyper-heuristic ⋮ Exact algorithms for the multi-pickup and delivery problem with time windows ⋮ The joint network vehicle routing game with optional customers ⋮ The close-open mixed vehicle routing problem ⋮ Routing problems with loading constraints ⋮ An improved formulation for the inventory routing problem with time-varying demands ⋮ The coastal seaspace patrol sector design and allocation problem ⋮ Partial-route inequalities for the multi-vehicle routing problem with stochastic demands ⋮ A Branch-and-Cut method for the Capacitated Location-Routing Problem ⋮ Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery ⋮ Lifted polynomial size formulations for the homogeneous and heterogeneous vehicle routing problems ⋮ \(K\)-adaptability in two-stage mixed-integer robust optimization ⋮ A generic exact solver for vehicle routing and related problems ⋮ Improved lower bounds and exact algorithm for the capacitated arc routing problem ⋮ A new mixed integer linear model for a rich vehicle routing problem with docking constraints ⋮ An Exact Algorithm Based on Cut-and-Column Generation for the Capacitated Location-Routing Problem ⋮ Formulations and Branch-and-Cut Algorithms for Multivehicle Production and Inventory Routing Problems ⋮ Reachability cuts for the vehicle routing problem with time windows ⋮ Alternative formulations and improved bounds for the multi-depot fleet size and mix vehicle routing problem ⋮ Single vehicle routing problems with a predefined customer sequence, compartmentalized load and stochastic demands ⋮ Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints ⋮ A branch-and-cut algorithm for the soft-clustered vehicle-routing problem ⋮ Route stability in vehicle routing decisions: a bi-objective approach using metaheuristics ⋮ Recent advances in vehicle routing exact algorithms ⋮ Solving the capacitated location-routing problem. Abstract of Thesis ⋮ Heuristic and exact algorithms for the multi-pile vehicle routing problem ⋮ The inventory routing problem with demand moves ⋮ A branch-and-cut-and-price algorithm for the electric vehicle routing problem with multiple technologies ⋮ A genetic algorithm for a green vehicle routing problem ⋮ Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation ⋮ An optimization algorithm for the inventory routing problem with continuous moves ⋮ An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts ⋮ BPPLIB: a library for bin packing and cutting stock problems ⋮ Combined route capacity and route length models for unit demand vehicle routing problems ⋮ The capacitated vehicle routing problem: stronger bounds in pseudo-polynomial time ⋮ EVE-OPT: a hybrid algorithm for the capacitated vehicle routing problem ⋮ An exact algorithm to solve the vehicle routing problem with stochastic demands under an optimal restocking policy ⋮ The separation problem of rounded capacity inequalities: some polynomial cases ⋮ On the complexity of the separation problem for rounded capacity inequalities ⋮ Route relaxations on GPU for vehicle routing problems ⋮ The value of integrating loading and routing ⋮ New benchmark instances for the capacitated vehicle routing problem ⋮ A branch-and-cut algorithm for the two-echelon capacitated vehicle routing problem with grouping constraints ⋮ A branch-and-cut-and-price approach for the capacitated \(m\)-ring-star problem ⋮ Exact algorithms for routing problems under vehicle capacity constraints ⋮ Minimum makespan vehicle routing problem with compatibility constraints ⋮ Decomposition and dynamic cut generation in integer linear programming ⋮ Formulations and valid inequalities for the heterogeneous vehicle routing problem ⋮ Robust branch-and-cut-and-price for the capacitated vehicle routing problem ⋮ The pyramidal capacitated vehicle routing problem ⋮ New symmetry-less ILP formulation for the classical one dimensional bin-packing problem ⋮ The two-echelon production-routing problem ⋮ A personalized walking bus service requiring optimized route decisions: a real case ⋮ Improved branch-and-cut for the inventory routing problem based on a two-commodity flow formulation ⋮ An exact solution framework for a broad class of vehicle routing problems ⋮ A branch-and-cut algorithm for an assembly routing problem ⋮ Formulations, branch-and-cut and a hybrid heuristic algorithm for an inventory routing problem with perishable products ⋮ Exact and Heuristic Algorithms for Capacitated Vehicle Routing Problems with Quadratic Costs Structure ⋮ A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem ⋮ A branch-and-cut-and-price approach for the pickup and delivery problem with shuttle routes ⋮ Facets and valid inequalities for the time-dependent travelling salesman problem ⋮ A computational comparison of flow formulations for the capacitated location-routing problem ⋮ A new model for the asymmetric vehicle routing problem with simultaneous pickup and deliveries ⋮ Exploiting sparsity in pricing routines for the capacitated arc routing problem ⋮ Tolerance-Based vs. Cost-Based Branching for the Asymmetric Capacitated Vehicle Routing Problem ⋮ CVRPSP ⋮ Two-echelon vehicle routing problems: a literature review ⋮ Heuristic optimization for multi-depot vehicle routing problem in ATM network model ⋮ An improved branch-cut-and-price algorithm for the two-echelon capacitated vehicle routing problem ⋮ A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints ⋮ A compact transformation of arc routing problems into node routing problems ⋮ Solving capacitated arc routing problems using a transformation to the CVRP ⋮ Projection results for vehicle routing ⋮ A new ILP-based refinement heuristic for vehicle routing problems ⋮ Opportunities for reinforcement learning in stochastic dynamic vehicle routing ⋮ Two-stage vehicle routing problem with arc time windows: a mixed integer programming formulation and a heuristic approach

Uses Software

• Unnamed Item

This page was built for publication: A new branch-and-cut algorithm for the capacitated vehicle routing problem