Article ID: | iaor20108712 |
Volume: | 62 |
Issue: | 2 |
Start Page Number: | 326 |
End Page Number: | 336 |
Publication Date: | Feb 2011 |
Journal: | Journal of the Operational Research Society |
Authors: | Potvin J-Y, Naud M-A |
Keywords: | heuristics: tabu search |
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.