An Adaptive Metaheuristic for Vehicle Routing Problems with Time Windows and Multiple Service Workers

Gerald Senarclens de Grancy (University of Graz, Austria)

Abstract: Distribution planning in urban areas faces a lack of available parking space at customer sites. One approach to mitigate the issue is to cluster nearby customers around known parking locations. Deliveries from each parking location to its assigned customers occur by a second mode of transport (for example by foot). These lead to long service times at each of the clusters. However, long service times in conjunction with time windows can lead to inefficient routes as nearby customer clusters with overlapping service times may not be connected. As a consequence, assigning additional service workers to each vehicle is a strategy to reduce service times. The additional workers can do the last mile deliveries in parallel to reduce the service time of a cluster and hence permit more efficient routing. The trade-off between paying additional workers to reduce costs for vehicles and driving creates a new decision problem called the vehicle routing problem with time windows and multiple service workers (VRPTWMS).

Keywords: ant colony optimization, clustering customers, metaheuristic, time windows, vehicle routing

Categories: I.2.6, I.2.8, J.7