A multi arm bandit neighbourhood search for routing and scheduling problems
Abstract Local search based meta heuristics such as variable neighbourhood search have achieved remarkable success in solving complex combinatorial problems. Local search techniques are becoming increasingly popular and are used in a wide variety of meta heuristics, such as genetic algorithms. Typically, local search iteratively improves a solution by making a series of small moves. Traditionally these methods do not employ any learning mechanism. We treat the selection of a local search neighbourhood as a dynamic multi armed bandit (D MAB) problem where learning techniques for solving the D MAB can be used to guide the local search process. We present a D MAB neighbourhood search (D MABNS) which can be embedded within any meta heuristic or hyperheuristic framework. Given a set of neighbourhoods, the aim of D MABNS is to adapt the search sequence, testing promising solutions rst. We demonstrate the eectiveness of D MABNS on two vehicle routing and scheduling problems, the real world geographically distributed mainte nance problem (GDMP) and the periodic vehicle routing problem (PVRP) We present comparisons to benchmark instances and give a detailed analysis of parameters, performance and behaviour. Keywords Meta heuristic Local search Vehicle routing