An improved branch-and-cut algorithm for the capacitated vehicle routing problem

An improved branch-and-cut algorithm for the capacitated vehicle routing problem

0.00 Avg rating0 Votes
Article ID: iaor2005207
Country: United States
Volume: 37
Issue: 2
Start Page Number: 153
End Page Number: 169
Publication Date: May 2003
Journal: Transportation Science
Authors: , ,
Keywords: distribution, programming: integer, programming: network
Abstract:

The capacitated vehicle routing problem (CVRP) deals with the distribution of a single commodity from a centralized depot to a number of specified customer locations with known demands. The CVRP considered in this paper assumes common vehicle capacity, fixed or variable number of vehicles, and an objective to minimize the total distance traveled by all the vehicles. The paper develops several new cutting planes for this problem, and uses them in an exact branch-and-cut algorithm. Two of the new cutting planes are based on a specified structure of an optimal solution and its existence. Computational results are reported for 1,650 simulated Euclidean problems as well as 24 standard literature test problems; solved problems range in size from 15 to 100 customers. A comparative analysis demonstrates the significant computational benefit of the proposed method.

Reviews

Required fields are marked *. Your email address will not be published.