Solving the Single Vehicle Routing Problem with Variable Capacity

François V. Louveaux () and Juan-José Salazar-González ()
Additional contact information
François V. Louveaux: Department of Business Administration, University of Namur, B-5000 Namur, Belgium
Juan-José Salazar-González: DEIOC, University of La Laguna, 38271 Tenerife, Spain

Transportation Science, 2016, vol. 50, issue 2, 708-719

Abstract: This paper considers the classical vehicle routing problem (VRP) where the vehicle capacity is not fixed. Indeed, at the moment of acquiring (or renting) the vehicle that will serve all customers, there is some freedom of choice. A larger vehicle capacity implies a lower total distance travelled but larger operating costs. The reverse is true for a smaller vehicle. This paper gives an approach to select the best capacity and the best route to minimize a function of the acquisition cost and travelled distance.We first consider an enumerative approach, which consists of solving a sequence of VRPs, starting from the one having the largest capacity. The number of VRPs to solve using this approach is unknown. Based on computational experiments, this number is mostly large in our benchmark instances. We then proceed to a direct approach based on the two-index formulation of the VRP. We introduce several valid inequalities that allow us to have an integer linear programming formulation of the VRP with fixed vehicle capacity. We describe separation procedures for these inequalities. We conclude with computational results that confirm the utility of these inequalities when solving benchmark VRP instances.

Keywords: vehicle routing problem; unknown vehicle capacity; branch-and-cut algorithm (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2014.0556 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:50:y:2016:i:2:p:708-719

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().