An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts

DOI10.1007/s10107-007-0178-5zbMath1279.90139OpenAlexW2082153300MaRDI QIDQ948965

Aristide Mingozzi, Roberto Baldacci, Nicos Christofides

Publication date: 16 October 2008

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

Full work available at URL: https://doi.org/10.1007/s10107-007-0178-5

zbMATH Keywords

vehicle routingvalid inequalitiesdual ascentset partitioning

Mathematics Subject Classification ID

Numerical methods involving duality (49M29) Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items (72)

All-integer column generation for set partitioning: basic principles and extensions ⋮ Min-Max vs. Min-Sum vehicle routing: a worst-case analysis ⋮ Stronger multi-commodity flow formulations of the capacitated vehicle routing problem ⋮ Analytic centre stabilization of column generation algorithm for the capacitated vehicle routing problem ⋮ A hybrid approach for the vehicle routing problem with three-dimensional loading constraints ⋮ Minimum cost VRP with time-dependent speed data and congestion charge ⋮ Managing platelet supply through improved routing of blood collection vehicles ⋮ Enhanced branch-cut-and-price algorithm for heterogeneous fleet vehicle routing problems ⋮ A unified exact method for solving different classes of vehicle routing problems ⋮ Cooperative receding horizon strategies for the multivehicle routing problem ⋮ Improved branch-cut-and-price for capacitated vehicle routing ⋮ The arc-item-load and related formulations for the cumulative vehicle routing problem ⋮ Improving Column Generation for Vehicle Routing Problems via Random Coloring and Parallelization ⋮ A POPMUSIC matheuristic for the capacitated vehicle routing problem ⋮ An \(\varepsilon \)-constraint column generation-and-enumeration algorithm for bi-objective vehicle routing problems ⋮ The close-open mixed vehicle routing problem ⋮ A hybrid algorithm for the heterogeneous fleet vehicle routing problem ⋮ Routing problems with loading constraints ⋮ The vehicle routing problem with service level constraints ⋮ Optimally solving the joint order batching and picker routing problem ⋮ An integer optimality condition for column generation on zero-one linear programs ⋮ Column elimination for capacitated vehicle routing problems ⋮ On the exact solution of vehicle routing problems with backhauls ⋮ An integrated bi-objective optimization model and improved genetic algorithm for vehicle routing problems with temporal and spatial constraints ⋮ Estimating the marginal cost to deliver to individual customers ⋮ Heuristic and exact algorithms for a min-max selective vehicle routing problem ⋮ Integer programming column generation: accelerating branch-and-price using a novel pricing scheme for finding high-quality solutions in set covering, packing, and partitioning problems ⋮ The two-echelon stochastic multi-period capacitated location-routing problem ⋮ Exploiting variable associations to configure efficient local search algorithms in large-scale binary integer programs ⋮ A generic exact solver for vehicle routing and related problems ⋮ Improved lower bounds and exact algorithm for the capacitated arc routing problem ⋮ Clique Inequalities Applied to the Vehicle Routing Problem with Time Windows ⋮ A branch-cut-and-price algorithm for the cumulative capacitated vehicle routing problem ⋮ A branch‐and‐price‐based heuristic for the vehicle routing problem with two‐dimensional loading constraints and time windows ⋮ Exact solution of network flow models with strong relaxations ⋮ Unnamed Item ⋮ Lower and upper bounds for the \(m\)-peripatetic vehicle routing problem ⋮ An Exact Algorithm Based on Cut-and-Column Generation for the Capacitated Location-Routing Problem ⋮ Solving the electricity production planning problem by a column generation based heuristic ⋮ Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints ⋮ Recent advances in vehicle routing exact algorithms ⋮ A Stochastic Integer Programming Approach to Air Traffic Scheduling and Operations ⋮ Robust Branch-Cut-and-Price Algorithms for Vehicle Routing Problems ⋮ The capacitated vehicle routing problem: stronger bounds in pseudo-polynomial time ⋮ New benchmark instances for the capacitated vehicle routing problem ⋮ The demand weighted vehicle routing problem ⋮ Modelling transfer line design problem via a set partitioning problem ⋮ Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints ⋮ A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints ⋮ Exact algorithms for routing problems under vehicle capacity constraints ⋮ A dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints ⋮ A lower bound for the adaptive two-echelon capacitated vehicle routing problem ⋮ Avoiding redundant columns by adding classical Benders cuts to column generation subproblems ⋮ Vehicle routing with endogenous learning: application to offshore plug and abandonment campaign planning ⋮ An exact solution framework for a broad class of vehicle routing problems ⋮ Solving bin packing problems using VRPSolver models ⋮ A computational comparison of flow formulations for the capacitated location-routing problem ⋮ Exact methods for mono-objective and bi-objective multi-vehicle covering tour problems ⋮ Tolerance-Based vs. Cost-Based Branching for the Asymmetric Capacitated Vehicle Routing Problem ⋮ Solving the time-discrete winter runway scheduling problem: a column generation and constraint programming approach ⋮ Two-echelon vehicle routing problems: a literature review ⋮ Robust drone selective routing in humanitarian transportation network assessment ⋮ A set covering based matheuristic for a real‐world city logistics problem ⋮ Branch-Cut-and-Price for the Robust Capacitated Vehicle Routing Problem with Knapsack Uncertainty ⋮ 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 branch-and-cut algorithm for the capacitated profitable tour problem ⋮ A compact transformation of arc routing problems into node routing problems ⋮ Robust vehicle routing under uncertainty via branch-price-and-cut ⋮ A unified exact approach for clustered and generalized vehicle routing problems ⋮ Heuristics for multi-attribute vehicle routing problems: a survey and synthesis ⋮ A heuristic for cumulative vehicle routing using column generation

Uses Software

• CPLEX
• Cliquer
• VRP
• CVRPSEP
• CVRPSP

Cites Work

• 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
• The vehicle routing problem: An overview of exact and approximate algorithms
• Stabilized column generation
• Multistars, partial multistars and the capacitated vehicle routing problem
• A fast algorithm for the maximum clique problem
• A new branch-and-cut algorithm for the capacitated vehicle routing problem
• A new exact algorithm for the vehicle routing problem based on \(q\)-paths and \(k\)-shortest paths relaxations
• A descent method with linear programming subproblems for nondifferentiable convex optimization
• Interior point stabilization for column generation
• The multiple disposal facilities and multiple inventory locations rollon-rolloff vehicle routing problem
• Robust branch-and-cut-and-price for the capacitated vehicle routing problem
• The Vehicle Routing Problem
• An Exact Method for the Vehicle Routing Problem with Backhauls
• Optimal Routing under Capacity and Distance Restrictions
• An Additive Bounding Procedure for Combinatorial Optimization Problems
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• Set Partitioning: A survey
• The B<scp>oxstep</scp> Method for Large-Scale Optimization
• Solving Airline Crew Scheduling Problems by Branch-and-Cut
• A Set Partitioning Approach to the Crew Scheduling Problem
• An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation
• Selected Topics in Column Generation
• A new method for solving capacitated location problems based on a set partitioning approach

This page was built for publication: An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts