Sequential order vs random order in operators of variable neighborhood descent method
Darmawan Satyananda, Sapti Wahyuningsih
Many optimization problems require heuristic methods to solve the problem. Variable Neighborhood Search (VNS) is a metaheuristic form that systematically changes its “neighborhood” in search of solutions. One method in VNS is Variable Neighborhood Descent (VND), which performs a deterministic neighborhood change. The change of the neighborhood in VND can be done in a random and sequential order. This paper compares sequential and random neighborhood selection methods in solving Capacitated Vehicle Routing Problem (CVRP) problems. There are 6 intra-route neighborhood structures and 4 inter-route structures used. CVRP problems are taken from several dataset providers. The initial solution is formed by Sequential Insertion method. The experimental results shows that the random selection of neighborhood operators can provide a more optimal route length (in 10 of 13 datasets used) than that of sequential selection (only better in 3 dataset). However, the random selection take more iterations to reach convergent state than the sequential one. For sequential selection, determination of the neighborhood structure’s order affects the speed to the convergent state. Hence, a random selection in VND method is more preferable than sequential selection.
CVRP; local search; neighborhood selection methods; VND; VNS