1. ¹Interuniversity Research Center on Enterprise Networks, Logistics and Transportation (CIRRELT)
2. ²Université Laval, Québec, Canada
3. ³Canada Research Chair in Distribution Management, HEC Montréal, Montréal, Canada

Correspondence: J Renaud, Faculté des sciences de l'administration, Université Laval, Québec, Canada G1K 7P4. E-mail: jacques.renaud@fsa.ulaval.ca

Received March 2006; Accepted December 2006; Published online 14 March 2007.

Abstract

The purpose of this article is to propose a perturbation metaheuristic for the vehicle routing problem with private fleet and common carrier (VRPPC). This problem consists of serving all customers in such a way that (1) each customer is served exactly once either by a private fleet vehicle or by a common carrier vehicle, (2) all routes associated with the private fleet start and end at the depot, (3) each private fleet vehicle performs only one route, (4) the total demand of any route does not exceed the capacity of the vehicle assigned to it, and (5) the total cost is minimized. This article describes a new metaheuristic for the VRPPC, which uses a perturbation procedure in the construction and improvement phases and also performs exchanges between the sets of customers served by the private fleet and the common carrier. Extensive computational results show the superiority of the proposed metaheuristic over previous methods.