Program > By author > Beek Onne

This paper takes a critical look at Candidate Limitation Strategies for the Vehicle Routing Problem. These are techniques that aim to reduce the complexity of the problem by pre-emptively removing edges from consideration. Several different methods of forming CLS are known in the literature; each of these selection criteria has its strengths and weaknesses. We use two complementary analysis methodologies to evaluate and compare six different CLS. Our first methodology looks at benchmark instances for which the optimal solution is known and uses this information to gauge the accuracy of each CLS, i.e. its ability to correctly distinguish good and bad edges. We further use correlations in instance data and CLS performance to help calibrate the parameter for each CLS. Our second methodology uses a simple optimization heuristic to perform computational experiments on large-scale benchmark instances, providing practical insight into the trade-off in solution quality and optimization speed. Using the insights from our first experiments, we see if our calibration insights gained from relatively small instances can be generalized to very large-scale instance. Lastly, we perform a limited comparison between the potential of CLS and that of alternative performance-enhancing techniques, such as Static Move Descriptors and Decomposition methods.