A perturbation metaheuristic for the vehicle routing problem with private fleet and common carriers

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.

Keywords:

• heterogeneous vehicle routing problem
• common carrier
• private fleet
• metaheuristic
• perturbation

Acknowledgements

This work was partially supported by the Canadian Natural Sciences and Engineering Research Council (NSERC) under grants OGP0036509, OGP0039682 and OGP0172633. This support is gratefully acknowledged. The authors also thank Ching-Wu Chu for providing the computer code of his heuristic and the referees for their valuable comments.