Implicit time windows and multi-commodity mixed-fleet vehicle routing

We report about a metaheuristic solving approach for a vehicle routing problem with a heterogeneous vehicle fleet. Customer locations require the visit of two different types of vehicles. Operation starting times at the customers are coupled by a specific time window constraint called implicit time window. An implicit time window limits the difference among the starting times of two different operations. At first glance, an implicit time window seems to be less restricting than an explicit time window. However, we exhibit that typical search mechanism originally developed for handling explicit time windows in metaheuristic search fail to meet the requirements of implicit time windows. We therefore propose additional solution manipulation techniques to achieve solution feasibility with respect to the implicit time windows. Within comprehensive computational experiments, we demonstrate the superiority of a memetic algorithm specifically equipped with these new search components over a memetic algorithm that deploys only constraint handling techniques for explicit time windows.