Neighborhood search approaches for a multi-trip vehicle routing problem with time windows

We consider a multi-trip vehicle routing problem with time windows where each vehicle can perform several routes to serve the customers. Besides imposing a time window at the depot, we also assume that the working time of each vehicle may not exceed a maximum duration. The pursued objective is the minimization of the total working time. In this context, starting early to ensure the satisfaction of time window constraints has a negative impact on the objective function and on the maximum allowed working time constraint. Thus, vehicle start times are explicit decision variables. We compare two large neighborhood search approaches. The first one combines vehicle routing heuristics with bin packing techniques aimed at assigning routes to vehicles. The second one makes use of specific multi-trip operators designed to tackle simultaneously the routing and the assignment aspects of the problem. We show that the proposed multi-trip operators are more suitable for constrained instances with tight time windows. An automatic configuration tool is used to find high quality results. Moreover, it allows us to gain knowledge about the behavior of algorithmic components. We also question the impact of commonly employed heuristic components