Program > By author > Sze Jeeu Fong

An adaptive variable neighbourhood search (AVNS) algorithm that incorporates large neighbourhood search (LNS) as a diversification strategy is proposed and applied to the capacitated vehicle routing problem. The AVNS algorithm consists of two stages: a learning phase and a multi-level VNS with guided local search. Here, the adaptive aspect is integrated in the local search instead of the shaking step. With this, a set of highly successful local searches is selected each time, leading to a more effective search. In addition, a simple but effective data structure and a neighbourhood reduction scheme are embedded in the algorithm. Both of these aim to reduce the computational time with the former limits the search to a small solution space that has been modified whereas the latter restricts the search to a set of potential customers that could be worth examining. Moreover, the hybridisation of LNS with the AVNS enables the solution to escape from the local minimum. Finally, we adapt a new local search move and an effective ruin strategy for the LNS. The algorithm was tested on three sets of instances from the literature and produced very promising results. In a set of instances, the algorithm matches most of the best known results with less than 0.1% average deviation, whereas in the other two sets are very close to the best known. The computational time of the AVNS algorithm is also relatively lower compared to most of the existing methods in the literature.