Sequential order vs random order in operators of variable neighborhood descent method

Darmawan Satyananda, Sapti Wahyuningsih

Abstract


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 show 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 takes 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.

Keywords


CVRP; local search; neighborhood selection methods; VND; VNS;

Full Text:

PDF


DOI: http://dx.doi.org/10.12928/telkomnika.v17i2.11789

Article Metrics

Abstract view : 56 times
PDF - 30 times

Refbacks

  • There are currently no refbacks.


Copyright (c) 2018 Universitas Ahmad Dahlan

TELKOMNIKA Telecommunication, Computing, Electronics and Control
ISSN: 1693-6930, e-ISSN: 2302-9293
Universitas Ahmad Dahlan, 4th Campus, 9th Floor, LPPI Room
Jl. Ringroad Selatan, Kragilan, Tamanan, Banguntapan, Bantul, Yogyakarta, Indonesia 55191
Phone: +62 (274) 563515, 511830, 379418, 371120 ext. 4902, Fax: +62 274 564604

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

View TELKOMNIKA Stats