Comparision of the walk techniques for fitness state space analysis in vehicle routing problem

Anita Agárdi; László Kovács; Tamás Bányai

doi:10.14311/AP.2021.61.0672

Authors

Anita Agárdi University of Miskolc, Faculty of Mechanical Engineering and Informatics, Institute of Informatics, Miskolc-Egyetemváros 3515, Miskolc, Hungary https://orcid.org/0000-0001-9148-1214
László Kovács University of Miskolc, Faculty of Mechanical Engineering and Informatics, Institute of Informatics, Miskolc-Egyetemváros 3515, Miskolc, Hungary https://orcid.org/0000-0003-2703-7228
Tamás Bányai University of Miskolc, Faculty of Mechanical Engineering and Informatics, Institute of Logistics, Miskolc-Egyetemváros 3515, Miskolc, Hungary https://orcid.org/0000-0002-0229-4781

DOI:

https://doi.org/10.14311/AP.2021.61.0672

Keywords:

fitness state space, Vehicle Routing Problem, optimization

Abstract

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.

Downloads

Download data is not yet available.

References

G. B. Dantzig, J. H. Ramser. The truck dispatching problem. Management science 6(1):80–91, 1959. https://doi.org/10.1287/mnsc.6.1.80.

Y. Shi, Y. Zhou, T. Boudouh, O. Grunder. A lexicographic-based two-stage algorithm for vehicle routing problem with simultaneous pickup – delivery and time window. Engineering Applications of Artificial Intelligence 95:103901, 2020. https://doi.org/10.1016/j.engappai.2020.103901.

M. Hoogeboom, W. Dullaert, D. Lai, D. Vigo. Efficient neighborhood evaluations for the vehicle routing problem with multiple time windows. Transportation Science 54(2):400–416, 2020. https://doi.org/10.1287/trsc.2019.0912.

G. Li, J. Li. An improved tabu search algorithm for the stochastic vehicle routing problem with soft time windows. IEEE Access 8:158115–158124, 2020. https://doi.org/10.1109/access.2020.3020093.

G. Nagy, S. Salhi. Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. European journal of operational research 162(1):126–141, 2005. https://doi.org/10.1016/j.ejor.2002.11.003.

P. Stodola. Hybrid ant colony optimization algorithm applied to the multi-depot vehicle routing problem. Natural Computing 19:463–475, 2020. https://doi.org/10.1007/s11047-020-09783-6.

J. Brandão. A memory-based iterated local search algorithm for the multi-depot open vehicle routing problem. European Journal of Operational Research 284(2):559–571, 2020. https://doi.org/10.1016/j.ejor.2020.01.008.

T. R. P. Ramos, M. I. Gomes, A. P. Barbosa-Povoa. A new matheuristic approach for the multi-depot vehicle routing problem with inter-depot routes. OR Spectrum 42(1):75–110, 2020. https://doi.org/10.1007/s00291-019-00568-7.

P. Kitjacharoenchai, B.-C. Min, S. Lee. Two echelon vehicle routing problem with drones in last mile delivery. International Journal of Production Economics 225:107598, 2020. https://doi.org/10.1016/j.ijpe.2019.107598.

R. F. Fachini, V. A. Armentano. Logic-based Benders decomposition for the heterogeneous fixed fleet vehicle routing problem with time windows. Computers & Industrial Engineering 148:106641, 2020. https://doi.org/10.1016/j.cie.2020.106641.

L. do C. Martins, P. Hirsch, A. A. Juan. Agile optimization of a two-echelon vehicle routing problem with pickup and delivery. International Transactions in Operational Research 2020. https://doi.org/10.1111/itor.12796.

S. M. Nugroho, L. Nafisah, M. S. A. Khannan, et al. Vehicle routing problem with heterogeneous fleet, split delivery, multiple product, multiple trip, and time windows: A case study in fuel distribution. In IOP Conference Series: Materials Science and Engineering, vol. 847, p. 012066. IOP Publishing, 2020. https://doi.org/10.1088/1757-899x/847/1/012066.

Y. Wang, L. Wang, G. Chen, et al. An improved ant colony optimization algorithm to the periodic vehicle routing problem with time window and service choice. Swarm and Evolutionary Computation 55:100675, 2020. https://doi.org/10.1016/j.swevo.2020.100675.

S. Wright. The roles of mutation, inbreeding, crossbreeding, and selection in evolution, vol. 1. 1932.

J. Tavares, F. B. Pereira, E. Costa. Multidimensional knapsack problem: A fitness landscape analysis. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 38(3):604–616, 2008. https://doi.org/10.1109/tsmcb.2008.915539.

G. Ochoa, R. Qu, E. K. Burke. Analyzing the landscape of a graph based hyper-heuristic for timetabling problems. In Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pp. 341–348. 2009. https://doi.org/10.1145/1569901.1569949.

M.-H. Tayarani-N., A. Prügel-Bennett. An analysis of the fitness landscape of travelling salesman problem. Evolutionary computation 24(2):347–384, 2016. https://doi.org/10.1162/evco_a_00154.

K. Mathias, D. Whitley. Genetic operators, the fitness landscape and the traveling salesman problem. In PPSN, pp. 221–230. 1992.

M.-E. Marmion, C. Dhaenens, L. Jourdan, et al. On the neutrality of flowshop scheduling fitness landscapes. In International Conference on Learning and Intelligent Optimization, pp. 238–252. Springer, 2011. https://doi.org/10.1007/978-3-642-25566-3_18.

F. Chicano, F. Daolio, G. Ochoa, et al. Local optima networks, landscape autocorrelation and heuristic search performance. In International Conference on Parallel Problem Solving from Nature, pp. 337–347. Springer, 2012. https://doi.org/10.1007/978-3-642-32964-7_34.

M. Belaidouni, J.-K. Hao. An analysis of the configuration space of the maximal constraint satisfaction problem. In International Conference on Parallel Problem Solving from Nature, pp. 49–58. Springer, 2000. https://doi.org/10.1007/3-540-45356-3_5.

M. Ventresca, B. Ombuki-Berman, A. Runka. Predicting genetic algorithm performance on the vehicle routing problem using information theoretic landscape measures. In European Conference on Evolutionary Computation in Combinatorial Optimization, pp. 214–225. Springer, 2013. https://doi.org/10.1007/978-3-642-37198-1_19.

S. Wang, Q. Zhu, L. Kang. Landscape properties and hybrid evolutionary algorithm for optimum multiuser detection problem. In International Conference on Computational Science, pp. 340–347. Springer, 2006. https://doi.org/10.1007/11758501_48.

C. Fonlupt, D. Robilliard, P. Preux. Fitness landscape and the behavior of heuristics. In Evolution Artificielle, vol. 97, p. 56. Citeseer, 1997.

E. Pitzer, M. Affenzeller. A comprehensive survey on fitness landscape analysis. In Recent advances in intelligent engineering systems, pp. 161–191. Springer, 2012. https://doi.org/10.1007/978-3-642-23229-9_8.

L. Kovács, A. Agárdi, T. Bányai. Fitness landscape analysis and edge weighting-based optimization of vehicle routing problems. Processes 8(11):1363, 2020. https://doi.org/10.3390/pr8111363.

A. Agárdi, L. Kovács, T. Bányai. An attraction map framework of a complex multi-echelon vehicle routing problem with random walk analysis. Applied Sciences 11(5), 2021. https://doi.org/10.3390/app11052100.

E. Pitzer, M. Affenzeller, A. Beham, S. Wagner. Comprehensive and automatic fitness landscape analysis using heuristiclab. In International Conference on Computer Aided Systems Theory, pp. 424–431. Springer, 2011. https://doi.org/10.1007/978-3-642-27549-4_54.

E. Pitzer, A. Beham, M. Affenzeller. Generic hardness estimation using fitness and parameter landscapes applied to robust taboo search and the quadratic assignment problem. In Proceedings of the 14th annual conference companion on Genetic and evolutionary computation, pp. 393–400. 2012. https://doi.org/10.1145/2330784.2330845.

P. R. d. O. da Costa, J. Rhuggenaath, Y. Zhang, A. Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning, 2020. arXiv:2004.01608.

A. Srivastav, S. Agrawal. Multi-objective optimization of mixture inventory system experiencing order crossover. Annals of Operations Research 290(1):943–960, 2020. https://doi.org/10.1007/s10479-017-2744-4.

T. Visutarrom, T.-C. Chiang. An evolutionary algorithm with heuristic longest cycle crossover for solving the capacitated vehicle routing problem. In 2019 IEEE Congress on Evolutionary Computation (CEC), pp. 673–680. IEEE, 2019. https://doi.org/10.1109/cec.2019.8789946.

M. A. Al-Omeer, Z. H. Ahmed. Comparative study of crossover operators for the MTSP. In 2019 International Conference on Computer and Information Sciences (ICCIS), pp. 1–6. IEEE, 2019. https://doi.org/10.1109/iccisci.2019.8716483.

K. Li, Z. Liang, S. Yang, et al. Performance analyses of differential evolution algorithm based on dynamic fitness landscape. International Journal of Cognitive Informatics and Natural Intelligence (IJCINI) 13(1):36–61, 2019. https://doi.org/10.4018/ijcini.2019010104.

A. Shamir, I. Safran, E. Ronen, O. Dunkelman. A simple explanation for the existence of adversarial examples with small hamming distance, 2019. arXiv:1901.10861.

I. Khan, M. K. Maiti. A swap sequence based artificial bee colony algorithm for traveling salesman problem. Swarm and evolutionary computation 44:428–438, 2019. https://doi.org/10.1016/j.swevo.2018.05.006.