Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 18

Proceedings of the 2019 Federated Conference on Computer Science and Information Systems

Non-dominated Sorting Tournament Genetic Algorithm for Multi-Objective Travelling Salesman Problem

, ,

DOI: http://dx.doi.org/10.15439/2019F192

Citation: Proceedings of the 2019 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 18, pages 67–76 ()

Full text

Abstract. A Travelling Salesman Problem (TSP) is an NP-hard combinatorial problem that is very important for many real-world applications. In this paper, it is shown, that proposed approach solves multi-objective TSP (mTSP) more effectively than other investigated methods, i.e. Non-dominated Sorting Genetic Algorithm II (NSGA-II). The proposed methods use rank and crowding distance (well-known from NSGA-II), combining those mechanisms in a novel, unique way: competing and co-evolving in the evolution process. The proposed modifications are investigated and verified by the benchmark mTSP instances, and results are compared to other methods.

References

  1. Abdoun, Otman, Jaafar Abouchabaka, and Chakir Tajani. "Analyzing the performance of mutation operators to solve the travelling salesman problem." arXiv preprint https://arxiv.org/abs/1203.3099 (2012).
  2. Hoffman, Karla L., Manfred Padberg, and Giovanni Rinaldi. "Traveling salesman problem." Encyclopedia of operations research and management science (2013): 1573-1578.
  3. Cai, Xinye, et al. "An adaptive memetic framework for multi-objective combinatorial optimization problems: studies on software next release and travelling salesman problems." Soft Comp. 21.9 (2017): 2215-2236.
  4. Deb, Kalyanmoy, et al. "A fast and elitist multiobjective genetic algorithm: NSGA-II." IEEE transactions on evolutionary computation 6.2 (2002): 182-197.
  5. Laszczyk, Maciej, and Paweł B. Myszkowski. "Improved selection in evolutionary multi-objective optimization of Multi-Skill Resource-Constrained project scheduling problem." Information Sciences 481 (2019): 412-431.
  6. Laszczyk, Maciej, and Paweł B. Myszkowski. "Survey of quality measures for multi-objective optimization. Construction of complementary set of multi-objective quality measures." Swarm and Evolutionary Computation 48 (2019): 109-133.
  7. Miller, Donald L., and Joseph F. Pekny. "Exact solution of large asymmetric traveling salesman problems." Science 251.4995 (1991): 754-761.
  8. Bolanos, R., M. Echeverry, and J. Escobar. "A multiobjective non-dominated sorting genetic algorithm (NSGA-II) for the Multiple Traveling Salesman Problem." Decision Science Letters 4.4 (2015): 559-568.
  9. Elgesem, Aurora Smith, et al. "A traveling salesman problem with pickups and deliveries and stochastic travel times: An application from chemical shipping." European Journal of Operational Research 269.3 (2018): 844-859.
  10. Braekers, Kris, Katrien Ramaekers, and Inneke Van Nieuwenhuyse. "The vehicle routing problem: State of the art classification and review." Computers & Industrial Engineering 99 (2016): 300-313.
  11. Maity, Samir, Arindam Roy, and Manoranjan Maiti. "An imprecise multi-objective genetic algorithm for uncertain constrained multi-objective solid travelling salesman problem." Expert Systems With Applications 46 (2016): 196-223.
  12. Moraes, Deyvid Heric, et al. "A novel multi-objective evolutionary algorithm based on subpopulations for the bi-objective traveling salesman problem." Soft Computing (2018): 1-12.
  13. Seada, Haitham, Mohamed Abouhawwash, and Kalyanmoy Deb. "Multiphase Balance of Diversity and Convergence in Multiobjective Optimization." IEEE Transactions on Evolutionary Computation 23.3 (2018): 503-513.
  14. Ariyasingha, I. D. I. D., and T. G. I. Fernando. "Performance analysis of the multi-objective ant colony optimization algorithms for the traveling salesman problem." Swarm and Evolutionary Comp. 23 (2015): 11-26.
  15. Ke, Liangjun, Qingfu Zhang, and Roberto Battiti. "MOEA/D-ACO: A multiobjective evolutionary algorithm using decomposition and ant-colony." IEEE transactions on cybernetics 43.6 (2013): 1845-1859.
  16. Ke, Liangjun, Qingfu Zhang, and Roberto Battiti. "Hybridization of decomposition and local search for multiobjective optimization." IEEE transactions on cybernetics 44.10 (2014): 1808-1820.
  17. Chen, Xinye, et al. "Ant colony optimization based memetic algorithm to solve bi-objective multiple traveling salesmen problem for multi-robot systems." IEEE Access 6 (2018): 21745-21757.
  18. Cornu, Marek, Tristan Cazenave, and Daniel Vanderpooten. "Perturbed decomposition algorithm applied to the multi-objective traveling salesman problem." Computers & Operations Research 79 (2017): 314-330.
  19. Lust, Thibaut, and Jacques Teghem. "The multiobjective traveling salesman problem: a survey and a new approach." Advances in Multi-Objective Nature Inspired Computing. Springer, Berlin, Heidelberg, 2010. 119-141.
  20. Qamar, Nosheen, Nadeem Akhtar, and Irfan Younas. "Comparative Analysis of Evolutionary Algorithms for Multi-Objective Travelling Salesman Problem." International Journal of Advanced Computer Science and Applications 9.2 (2018): 371-379.
  21. Moraes, Deyvid Heric, et al. "A novel multi-objective evolutionary algorithm based on subpopulations for the bi-objective traveling salesman problem." Soft Computing (2018): 1-12.
  22. Hassin, Refael, and Shlomi Rubinstein. "Better approximations for max TSP." Information Processing Letters 75.4 (2000): 181-186.
  23. Abdoun, Otman, and Jaafar Abouchabaka. "A comparative study of adaptive crossover operators for genetic algorithms to resolve the traveling salesman problem." arXiv preprint https://arxiv.org/abs/1203.3097 (2012).
  24. Varun Kumar, S. G., and R. Panneerselvam. "A study of crossover operators for genetic algorithms to solve VRP and its variants and new sinusoidal motion crossover operator." Int. J. Comput. Intell. Res 13.7 (2017): 1717-1733.
  25. Stehling, Thiago Muniz, and Sergio Ricardo de Souza. "A Comparison of Crossover Operators Applied to the Vehicle Routing Problem with Time Window." 2017 Brazilian Conference on Intelligent Systems (BRACIS). IEEE, 2017.
  26. Lopez-Ibanez M., Paquete L., and Stutzle T. “Exploratory Analysis of Stochastic Local Search Algorithms in Biobjective Optimization”, Experimental Methods for the Analysis of Opt. Alg. (2010): 209-222.
  27. Whitley, L. Darrell, Timothy Starkweather, and D’Ann Fuquay. “Scheduling problems and traveling salesmen: The genetic edge recombination operator.” ICGA. Vol. 89. 1989.