Program > By author > Glock Katharina

In order to provide flexible services for solving vehicle routing problems (VRP), logistics professionals should be enabled to easily adapt the planning tool even without having a background in optimization. Constraint Programming (CP) combines an expressive modelling language and problem-independent search methods, thus making it a promising candidate for a planning engine for such a flexible service. Users can add or remove constraints without having to modify either the core model formulation or the solution methods.

Large Neighbourhood Search (LNS) proposed by Shaw (1998) is the most frequently used heuristic for solving VRP in a CP framework. We introduce the basic solution architecture with particular consideration of CP specific features. We furthermore present current research combining LNS and Monte-Carlo tree search (MCTS), an algorithm originally proposed for decision making in non-deterministic games that aims at balancing the exploration of a search tree and the exploitation of sub-trees that are likely to contain good solutions. We apply MCTS for constructing the initial solution as well as for solving the sub-problems created by the LNS. Integrated into the CP framework, MCTS provides a robust search algorithm that adjusts itself to the properties of the problem at hand, thus ensuring the flexibility of the search framework. Results are promising with respect to quality and runtime for several problem classes such as the VRP with time windows, the VRP with pickup and delivery, and the periodic VRP with time windows.