The neighbourhood generation is a fundamental part in heuristic search design in general and in the VRPs in particular. Six
neighbourhood schemes (N1,…, N6) are used in this study. These are briefly described as follows. 1-insertion intra-route (N1) relocates a customer at a non-adjacent arc within the same route; 1-insertion inter-route (N2) relocates a customer from one route to