Generating problem-specific knowledge (for the Vehicle Routing Problem)

The Vehicle Routing Problem (VRP) is probably the most-studied problem in Operations Research. However, in the race for faster algorithms and better solutions, few research has been performed to shed light on the problem itself. Even though problem specific knowledge is an important ingredient in the design of heuristics, such knowledge is rare for the VRP. As an example, it is proven that in the Traveling Salesman Problem does no optimal solution contain intersecting edges. Even though such a statement is not true for the VRP, it should be possible to deduct general guidelines such as: "In general, solutions can be improved by removing intersections". In this presentations, we take a first step in this direction and use data mining techniques to identify properties that distinguish optimal from non-optimal solutions. Those properties describe the geometrical nature and relations of routes. We combine them with instance characteristics to derive findings that are independent of the specific problem instance. With the help of a classification learner we are able to predict with a relatively high percentage from the defined properties whether a certain solution for any instance is optimal or not. Moreover, we extract rules that explain why a solution is not optimal. Finally, we demonstrate how these rules can be used in the design of heuristics. We implement a local search technique that uses a rule-database to determine the most-promising moves in each step.

Registration with Remy Spliet, spliet@ese.eur.nl, is required for availability of lunch.