Large neighborhood search approaches for multi-trip vehicle routing with time windows and driver shifts

We consider a multi-trip vehicle routing problem with time windows (MTVRPTW) and we assume that the working time of each vehicle may not exceed a maximum duration smaller than the planning horizon. We seek to minimize the total working time, implying that vehicle start times are explicit decision variables. We develop two adaptive large neighborhood search approaches based on different solution representations. The first method treats each vehicle journey as a giant tour that includes trip delimiters. The second one works on separate trips before assigning them to the available vehicles and scheduling them. We configure both methods using an automatic algorithm configuration package and show that the first one is more efficient in the presence of time windows, especially when these are tight. We obtain high quality results on MTVRPTW benchmark instances. We propose a generator to produce instances which characteristics naturally favor the creation of multi-trips. We also show that minimizing the total working time of the vehicles instead of the total distance is suitable in the presence of time windows since accepting a small deterioration in terms of traveled distance has a large positive impact on the working time. This effect increases as the size of time windows decreases.