An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts
- 1 August 2007
- journal article
- Published by Springer Science and Business Media LLC in Mathematical Programming
- Vol. 115 (2), 351-385
- https://doi.org/10.1007/s10107-007-0178-5
Abstract
This paper presents a new exact algorithm for the Capacitated Vehicle Routing Problem (CVRP) based on the set partitioning formulation with additional cuts that correspond to capacity and clique inequalities. The exact algorithm uses a bounding procedure that finds a near optimal dual solution of the LP-relaxation of the resulting mathematical formulation by combining three dual ascent heuristics. The first dual heuristic is based on the q-route relaxation of the set partitioning formulation of the CVRP. The second one combines Lagrangean relaxation, pricing and cut generation. The third attempts to close the duality gap left by the first two procedures using a classical pricing and cut generation technique. The final dual solution is used to generate a reduced problem containing only the routes whose reduced costs are smaller than the gap between an upper bound and the lower bound achieved. The resulting problem is solved by an integer programming solver. Computational results over the main instances from the literature show the effectiveness of the proposed algorithm.This publication has 31 references indexed in Scilit:
- The multiple disposal facilities and multiple inventory locations rollon–rolloff vehicle routing problemComputers & Operations Research, 2006
- Street Routing and Scheduling ProblemsPublished by Springer Science and Business Media LLC ,2006
- An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow FormulationOperations Research, 2004
- A new method for solving capacitated location problems based on a set partitioning approachComputers & Operations Research, 2002
- 4. Set-Covering-Based Algorithms for the Capacitated VRPPublished by Society for Industrial & Applied Mathematics (SIAM) ,2002
- A set partitioning approach to the multiple depot vehicle scheduling problemOptimization Methods and Software, 1994
- Optimal Routing under Capacity and Distance RestrictionsOperations Research, 1985
- Set Partitioning: A surveySiam Review, 1976
- An Algorithm for the Vehicle-dispatching ProblemJournal of the Operational Research Society, 1969
- On an Integer Program for a Delivery ProblemOperations Research, 1964