Models, relaxations and exact approaches for the capacitated vehicle routing problem

DOI10.1016/S0166-218X(01)00351-1zbMath1060.90065MaRDI QIDQ697581

Daniele Vigo, Paolo Toth

Publication date: 17 September 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

vehicle routingbranch-and-boundexact algorithmsrelaxationsvehicle capacities

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Transportation, logistics and supply chain management (90B06) Combinatorial optimization (90C27) Traffic problems in operations research (90B20)

Related Items (54)

A new novel local search integer-programming-based heuristic for PCB assembly on collect-and-place machines ⋮ Linear temporal logic vehicle routing with applications to multi-UAV mission planning ⋮ A heuristic approach for a real-world electric vehicle routing problem ⋮ Location-routing: issues, models and methods ⋮ Genetic algorithms for supply-chain scheduling: a case study in the distribution of ready-mixed concrete ⋮ The vehicle rescheduling problem ⋮ Managing platelet supply through improved routing of blood collection vehicles ⋮ A hybrid evolutionary algorithm for heterogeneous fleet vehicle routing problems with time windows ⋮ \textsc{Conjure}: automatic generation of constraint models from problem specifications ⋮ An application of special ordered sets to a periodic milk collection problem ⋮ A note on the lifted Miller-Tucker-Zemlin subtour elimination constraints for the capacitated vehicle routing problem ⋮ Efficient techniques for the multi-period vehicle routing problem with time windows within a branch and price framework ⋮ A robust optimization approach to dispatching technicians under stochastic service times ⋮ Medical waste collection considering transportation and storage risk ⋮ A simple model of optimal clearance of improvised explosive devices ⋮ Optimal fleet deployment for electric vehicle sharing systems with the consideration of demand uncertainty ⋮ The close-open mixed vehicle routing problem ⋮ Routing problems with loading constraints ⋮ Comments on: Routing Problems with loading constraints ⋮ A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem ⋮ Competitiveness based on logistic management: a real case study ⋮ A matheuristic for the asymmetric capacitated vehicle routing problem ⋮ A variable neighborhood search algorithm for the capacitated vehicle routing problem ⋮ A PTAS for Capacitated Vehicle Routing on Trees ⋮ Transportation Problem Allowing Sending and Bringing Back ⋮ A conditional-logic interpretation for Miller-Tucker-Zemlin inequalities and extensions ⋮ A computational study of solution approaches for the resource constrained elementary shortest path problem ⋮ MIRHA: multi-start biased randomization of heuristics with adaptive local search for solving non-smooth routing problems ⋮ A decision support system for a real vehicle routing problem. ⋮ D-Ants: Savings Based Ants divide and conquer the vehicle routing problem. ⋮ Heuristic and exact algorithms for the multi-pile vehicle routing problem ⋮ Heuristics for the lexicographic Max-ordering vehicle routing problem ⋮ A hybrid adaptive iterated local search with diversification control to the capacitated vehicle routing problem ⋮ An inverse optimization approach for a capacitated vehicle routing problem ⋮ Applying an Intensification Strategy on Vehicle Routing Problem ⋮ On the kidney exchange problem: cardinality constrained cycle and chain problems on directed graphs: a survey of integer programming approaches ⋮ Honey bees mating optimization algorithm for large scale vehicle routing problems ⋮ Exact algorithms for routing problems under vehicle capacity constraints ⋮ Formulations and valid inequalities for the heterogeneous vehicle routing problem ⋮ Minimizing the total cost in an integrated vendor-managed inventory system ⋮ Robust branch-and-cut-and-price for the capacitated vehicle routing problem ⋮ Hybrid particle swarm optimization with genetic algorithm for solving capacitated vehicle routing problem with fuzzy demand - a case study on garbage collection system ⋮ Strong Coalitional Structure in an Open Vehicle Routing Game ⋮ Application of a fuzzy ant colony system to solve the dynamic vehicle routing problem with uncertain service time ⋮ Probabilistic time-dependent vehicle routing problem ⋮ Consolidation in Urban Freight Transportation — Cost Allocation Models ⋮ Systematic review of the latest scientific publications on the vehicle routing problem ⋮ A new VRPPD model and a hybrid heuristic solution approach for e-tailing ⋮ Unnamed Item ⋮ Routing Optimization Under Uncertainty ⋮ A solution approach from an analytic model to heuristic algorithm for special case of vehicle routing problem with stochastic demands ⋮ Local improvement in planar facility location using vehicle routing ⋮ An approximate dynamic programming approach for the vehicle routing problem with stochastic demands ⋮ Two-phase heuristic algorithms for full truckloads multi-depot capacitated vehicle routing problem in carrier collaboration

Uses Software

• VRP
• VRPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polyhedral study of the capacitated vehicle routing problem
• An additive bounding procedure for the asymmetric travelling salesman problem
• The vehicle routing problem: An overview of exact and approximate algorithms
• A heuristic algorithm for the asymmetric capacitated vehicle routing problem
• A new exact algorithm for the vehicle routing problem based on \(q\)-paths and \(k\)-shortest paths relaxations
• An exact algorithm for the capacitated shortest spanning arborescence
• Routing problems: A bibliography
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• The Granular Tabu Search and Its Application to the Vehicle-Routing Problem
• Integer Programming Formulation of Traveling Salesman Problems
• Efficient algorithms for a family of matroid intersection problems
• Optimal Routing under Capacity and Distance Restrictions
• An exact algorithm for the asymmetrical capacitated vehicle routing problem
• An Additive Bounding Procedure for Combinatorial Optimization Problems
• Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• Some Simple Applications of the Travelling Salesman Problem
• An Exact Algorithm for the Vehicle Routing Problem with Backhauls
• A Staged Primal-Dual Algorithm for Finding a Minimum Cost Perfect Two-Matching in an Undirected Graph
• Optimal Solution of Vehicle Routing Problems Using Minimum K-Trees
• A Branch-and-Bound Algorithm for the Capacitated Vehicle Routing Problem on Directed Graphs
• On the Effectiveness of Set Covering Formulations for the Vehicle Routing Problem with Time Windows
• A set‐partitioning‐based exact algorithm for the vehicle routing problem
• A Matching Based Exact Algorithm for Capacitated Vehicle Routing Problems
• A Staged Primal-Dual Algorithm for Perfect b-Matching with Edge Capacities
• Pathology of Traveling-Salesman Subtour-Elimination Algorithms
• The traveling-salesman problem and minimum spanning trees: Part II
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem

This page was built for publication: Models, relaxations and exact approaches for the capacitated vehicle routing problem