Open AccessComparision of the walk techniques for fitness state space analysis in vehicle routing problem
Author(s) -
Anita Agárdi,
László Kovács,
Tamás Bányai
Publication year - 2021
Publication title -
acta polytechnica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.207
H-Index - 15
eISSN - 1805-2363
pISSN - 1210-2709
DOI - 10.14311/ap.2021.61.0672
Subject(s) - crossover , vehicle routing problem , heuristic , mathematical optimization , task (project management) , routing (electronic design automation) , computer science , state space , state (computer science) , space (punctuation) , mathematics , algorithm , engineering , artificial intelligence , computer network , statistics , systems engineering , operating system
The Vehicle Routing Problem (VRP) is a highly researched discrete optimization task. The first article dealing with this problem was published by Dantzig and Ramster in 1959 under the name Truck Dispatching Problem. Since then, several versions of VRP have been developed. The task is NP difficult, it can be solved only in the foreseeable future, relying on different heuristic algorithms. The geometrical property of the state space influences the efficiency of the optimization method. In this paper, we present an analysis of the following state space methods: adaptive, reverse adaptive and uphill-downhill walk. In our paper, the efficiency of four operators are analysed on a complex Vehicle Routing Problem. These operators are the 2-opt, Partially Matched Crossover, Cycle Crossover and Order Crossover. Based on the test results, the 2-opt and Partially Matched Crossover are superior to the other two methods.