Tabu search techniques for the heterogeneous vehicle routing problem with time windows and carrier‐dependent costs

In this work we formalize a new complex variant of the classical vehicle routing problem arising from a real‐world application. Our formulation includes a heterogeneous fleet, a multi‐day planning horizon, a complex carrier‐dependent cost for vehicles, and the possibility of leaving orders unscheduled. For tackling this problem we propose a metaheuristic approach based on Tabu Search and on a combination of neighborhood relations. We perform an experimental analysis to tune and compare different combinations, highlighting the most important features of the algorithm. The outcome is that a significant improvement is obtained by a complex combination of neighborhood relations. In addition, we compare our solver with previous work on public benchmarks of a similar version of the problem, namely the Vehicle Routing Problem with Private fleet and Common carrier. The conclusion is that our results are competitive with the best ones in literature.