Tabu search with ejection chains for the vehicle routing problem with private fleet and common carrier

Abstract

The problem reported in this paper is a variant of the classical vehicle routing problem, where customer requests for a transportation company can be served either by its private fleet of vehicles or assigned to an external common carrier. The latter case occurs if the demand exceeds the total capacity of the private fleet or if it is more economical to do so. Accordingly, the objective is to minimize the variable and fixed costs of the private fleet plus the costs charged by the common carrier. A tabu search heuristic with a neighbourhood structure based on ejection chains is proposed to solve this problem. It is empirically demonstrated that this algorithm outperforms the best approaches reported in the literature on a set of benchmark instances with both homogeneous and heterogeneous fleets.

Keywords:

• vehicle routing
• private fleet
• common carrier
• tabu search
• ejection chains

Acknowledgements

Financial support for this work was provided by the Canadian Natural Sciences and Engineering Research Council. This support is gratefully acknowledged.