Customer Clustering in the VRPTWMS
The vehicle routing problem with time windows and multiple service workers (VRPTWMS) is a novel approach allowing to efficiently deliver goods to customers in congested cities with limited parking space. Two steps have to be performed in order to solve this problem. First, each customer has to be assigned to a cluster. Thereafter, delivery routes from a central depot to these clusters are constructed. Hence, in this context, a cluster is denoted by a common parking location and a group of customers that is compiled sensibly in terms of location and time windows.
This paper introduces and systematically compares new heuristics for clustering customers in the VRPTWMS. To test the presented algorithms, a set of representative benchmark instances for this problem is proposed.
Results
See the current list of best known VRPTWMS clustering solution values.
If you were able to obtain better results than the ones above, please contact us at vrptwms-clustering@senarclens.eu. Please include a detailed description of your new solution (the sequences of customers making up the final routes) so that we can verify the validity of these results before updating the above list.
Build on our Work
You are encouraged to use our work in order to perform your own experiments. The source code is released using an open source license which essentially enables you to implement new ideas, operators and algorithms on top of the existing framework as long as you release your changes using the same license. This prevents you from having to write your experiments from scratch.
Vehicle Routing Problems with Time Windows and Multiple Service Workers
The vehicle routing problem (VRP) consists of determining a set of (near) optimal routes to a given set of customers from a single depot. The VRP has a series of extensions allowing to model additional constraints occurring in real world problems. One of these is the vehicle routing problem with time windows (VRPTW). It considers customers that are only able to take deliveries during limited frames of time.
A recent development of the VRP focuses on problems where the ratio of driving time to service time is low. In this case, efficient distribution may require more than one service worker per vehicle. These additional laborers shorten the service time allowing to construct routes that would otherwise violate restrictions of working hours or the customers' service time windows. Permitting additional workers is of particular importance in the presence of service time windows as reduced service times may enable the combination of nearby locations with overlapping time windows.
Building on prior work of Pureza et al. (2011) we created a computational framework for the VRPTW with multiple service workers (VRPTWMS). This framework allows investigation of different combinations of route construction heuristics, local search operators and metaheuristics. The framework offers a growing list of choices including the ACO and GRASP metaheuristics, move (relocate) and swap local search operators and Solomon's I1 route construction heuristic. The implementation of these is the result of a thorough investigation concerning the overall solution quality.
Applying the framework to benchmark instances, we were able to obtain new globally best solutions for each of the problems tested. However, given the few prior results available this is not conclusive. As a consequence, we added parameters for testing our framework against classic VRPTW instances. Compared to their best prior results, our framework still performs reasonably well in terms of computation time and solution quality. Our results are summarized in Senarclens and Reimann (2014).
Results
See the current list of best known VRPTWMS solution values.
If you were able to obtain better results than the ones above, please contact us at vrptwms@senarclens.eu. Please include a detailed description of your new solution (the sequences of customers making up the final routes) so that we can verify the validity of these results before updating the above list.
Build on our Work
You are encouraged to use our computational framework in order to perform your own experiments. The source code is released using an open source license which essentially enables you to implement new ideas, operators and algorithms on top of the existing framework as long as you release your changes using the same license. This prevents you from having to write your experiments from scratch.