A Very Large Scale Neighborhood Approach to Pickup and Delivery Problems with Time Windows

When solving optimisation problem in the presence of strong constraints, local search algorithms often fall into local minima. One approach that helps escaping local minima is using Very Large Scale Neighborhoods (VLSN). We applied VLSN to the pick-up and delivery problem with time windows (PDPTW). Unfortunately, VLSN can be rather slow: it requires to build a large graph of moves (the VLSN graph) and explore the graph to identify cycles in it. Most of the execution time is spent building the graph. Once a cycle is found, large parts of the graph are invalidated, hence the time spent building these portions of the graph is wasted. We introduce a generic speed improvement of the VLSN algorithm. The idea is to build the VLSN graph gradually and to perform the cycle search regularly throughout the construction of the graph, so that if the searched cycles are discovered, large portions of the graph under construction are not explored at all. Roughly speaking, on a specific standard PDPTW instance (LC1_2_1), only 43% of the graph needs to be built, and the sped up VLSN procedure only takes 53% of time taken by the original one.