View article

This paper introduces a variant of the vehicle routing problem with time windows where a limited number of vehicles is given (m-VRPTW). Under this scenario, a feasible solution is one that may contain either unserved customers and/or relaxed time windows. We provide a computable upper bound to the problem. To solve the problem, we propose a tabu search approach characterized by a holding list and a mechanism to force dense packing within a route. We also allow time windows to be relaxed by introducing the notion of penalty for lateness. In our approach, customer jobs are inserted based on a hierarchical objective function that captures multiple objectives. Computational results on benchmark problems show that our approach yields solutions that are competitive to best-published results on VRPTW. On m-VRPTW instances, experiments show that our approach produces solutions that are very close to …