A new multiple traveling salesman problem and its genetic algorithm-based solution

Jun Li, Qirui Sun, Meng Chu Zhou, Xianzhong Dai

Research output: Chapter in Book/Report/Conference proceedingConference contribution

31 Scopus citations

Abstract

This work formulates for the first time a multiple traveling salesman problem (MTSP) with ordinary and exclusive cities, denoted by MTSP* for short. In the original MTSP, a city can be visited by any traveling salesman and is thus renamed as an ordinary one in MTSP*. A new class of cities is introduced in MTSP*, called exclusive ones. They are divided into groups, each of which can be exclusively visited by a specified or predetermined salesman. To solve MTSP*, a genetic algorithm is presented. It encodes cities and salesman into two single chromosomes. Accordingly, three modes of crossover and mutation operators are designed, i.e., simple city crossover and mutation (CCM), simple salesman crossover and mutation, and mixed city-salesman crossover and mutation. All the operations of crossover and mutation follow the proper relationship between cities and salesman. With the help of an MTSP* example, the performance of the proposed algorithm with three modes of crossover and mutation operators is compared and analyzed. The simulation results show that the algorithm can solve MTSP* with rapid convergence with CCM being the best mode of the operators.

Original languageEnglish (US)
Title of host publicationProceedings - 2013 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2013
Pages627-632
Number of pages6
DOIs
StatePublished - Dec 1 2013
Event2013 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2013 - Manchester, United Kingdom
Duration: Oct 13 2013Oct 16 2013

Publication series

NameProceedings - 2013 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2013

Other

Other2013 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2013
CountryUnited Kingdom
CityManchester
Period10/13/1310/16/13

All Science Journal Classification (ASJC) codes

  • Human-Computer Interaction

Keywords

  • Genetic algorithm
  • Multiple traveling salesman problem
  • Optimization

Fingerprint Dive into the research topics of 'A new multiple traveling salesman problem and its genetic algorithm-based solution'. Together they form a unique fingerprint.

  • Cite this

    Li, J., Sun, Q., Zhou, M. C., & Dai, X. (2013). A new multiple traveling salesman problem and its genetic algorithm-based solution. In Proceedings - 2013 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2013 (pp. 627-632). [6721865] (Proceedings - 2013 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2013). https://doi.org/10.1109/SMC.2013.112