A computational study comparing different multiple neighbourhood strategies for solving rich vehicle routing problems

In this paper we report the results of an extensive computational study on a variety of rich vehicle routing problems in which two fundamentally different paradigms or strategies of applying (the same set of) different neighbourhoods are assessed with respect to effectivity (solution quality) and efficiency (speed). We especially compare the structured approach known from variable neighbourhood search where neighbourhoods are applied in some fixed sequential order with an approach where neighbourhoods are applied concurrently. Since all approaches are implemented using the same basic modules, differences can be attributed to this strategic difference. We can show that, first, the application of large neighbourhoods is essential for quality, and, second, that the concurrent strategy outperforms the sequential strategy.