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

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.