A Monte Carlo Large Neighbourhood Search for Vehicle Routing Problems

Resource type
Katharina Glock, Anne Meyer, Guido Tack
Book title
CP'16 - The 22nd International Conference on Principles and Practice of Constraint Programming, Doctoral Program Proceedings
Optimization tools addressing large scale combinatorial optimization problems in a real-world setting need to be easily adaptable to application specific requirements. Solution procedures need to be fast and robust towards these adaptations. To this end, we propose a hybrid approach combining Monte Carlo Tree Search (MCTS) and Large Neighbourhood Search (LNS) in a CP framework. The integration of local search and a self-adjusting tree-based search strategy offers a flexible and efficient solution approach that can adapt itself to the problem at hand. First results for the vehicle routing problem (VRP) indicate that the proposed Monte Carlo Large Neighbourhood Search (MCLNS) yields better results than related CP-based approaches.
Research focus
Logistics and Supply Chain Optimisation
Download .bib
Download .bib
Published by
Katharina Glock