×

A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms. (English) Zbl 1332.90332

Summary: This paper proposes a new crossover operator called two-part chromosome crossover (TCX) for solving the multiple travelling salesmen problem (MTSP) using a genetic algorithm (GA) for near-optimal solutions. We adopt the two-part chromosome representation technique which has been proven to minimise the size of the problem search space. Nevertheless, the existing crossover method for the two-part chromosome representation has two limitations. Firstly, it has extremely limited diversity in the second part of the chromosome, which greatly restricts the search ability of the GA. Secondly, the existing crossover approach tends to break useful building blocks in the first part of the chromosome, which reduces the GA’s effectiveness and solution quality. Therefore, in order to improve the GA search performance with the two-part chromosome representation, we propose TCX to overcome these two limitations and improve solution quality. Moreover, we evaluate and compare the proposed TCX with three different crossover methods for two MTSP objective functions, namely, minimising total travel distance and minimising longest tour. The experimental results show that TCX can improve the solution quality of the GA compared to three existing crossover approaches.

MSC:

90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming
90C27 Combinatorial optimization

Software:

GALib; TSPLIB; VRP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bektas, T., The multiple traveling salesman problem: an overview of formulations and solution procedures, Omega, 34, 209-219 (2006)
[2] Bellmore, M.; Hong, S., Transformation of multisalesmen problem to the standard traveling salesman problem, Journal of the Association Computer Machinery, 21, 500-504 (1974) · Zbl 0283.90036
[3] Bo, Z. W.; Hua, L. Z.; Yu, Z. G., Optimization of process route by genetic algorithms, Robotics and Computer-Integrated Manufacturing, 22, 180-188 (2006)
[5] Carter, A. E.; Ragsdale, C. T., A new approach to solving the multiple traveling salesperson problem using genetic algorithms, European Journal of Operational Research, 175, 246-257 (2006) · Zbl 1137.90690
[6] Chatterjee, S.; Carrera, C.; Lynch, L. A., Genetic algorithms and traveling salesman problems, European Journal of Operational Research, 93, 490-510 (1996) · Zbl 0912.90276
[7] Christofides, N.; Mingozzi, A.; Toth, P., Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations, Mathematical Programming, 20, 255-282 (1981) · Zbl 0461.90067
[8] Cus, F.; Balic, J., Optimization of cutting process by GA approach, Robotics and Computer-Integrated Manufacturing, 19, 113-121 (2003)
[9] Davis, L., Applying adaptive algorithms to epistatic domains, (The International Joint Conference on Artificial Intelligence (1985), IEEE Computer Society Press.: IEEE Computer Society Press. Los Angeles), 162-164
[12] Gavish, B.; Srikanth, K., An optimal solution method for large-scale multiple traveling salesmen problems, Operations Research, 34, 698-717 (1986) · Zbl 0612.90099
[13] Gen, M.; Cheng, R., Genetic Algorithms and Engineering Design (1997), Wiley: Wiley New York
[14] Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning (1989), Addison Wesley Longman: Addison Wesley Longman Boston, MA · Zbl 0721.68056
[16] Gorenstein, S., Printing press scheduling for multi-edition periodicals, Management Science, 16, B373-383 (1970)
[17] Holland, J. H., Adaptation in Natural and Artificial Systems (1975), University of Michigan Press: University of Michigan Press Ann Arbor, Michigan
[18] Holland, J. H., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence (1992), MIT Press: MIT Press Cambridge, MA
[19] Kellegöz, T.; Toklu, B.; Wilson, J., Comparing efficiencies of genetic crossover operators for one machine total weighted tardiness problem, Applied Mathematics and Computation, 199, 590-598 (2008) · Zbl 1140.90402
[20] Kim, K. H.; Park, Y. M., A crane scheduling method for port container terminals, European Journal of Operational Research, 156, 752-768 (2004) · Zbl 1062.90027
[21] Kulkarni, A. J.; Tai, K., Probability collectives: a multi-agent approach for solving combinatorial optimization problems, Applied Soft Computing, 10, 759-771 (2010)
[23] Malmborg, C., A genetic algorithm for service level based vehicle scheduling, European Journal of Operational Research, 93, 121-134 (1996) · Zbl 0912.90177
[25] Park, Y. B., A hybrid genetic algorithm for the vehicle scheduling problem with due times and time deadlines, International Journal of Productions Economics, 73, 175-188 (2001)
[27] Ryan, J. L.; Bailey, T. G.; Moore, J. T.; Carlton, W. B., Reactive tabu search in unmanned aerial reconnaissance simulations, (The 30th Conference on Winter Simulation (1998), IEEE Computer Society Press: IEEE Computer Society Press Los Alamitos, CA), 873-879
[28] Singh, A.; Baghel, A. S., A new grouping genetic algorithm approach to the multiple traveling salesperson problem, Soft Computing, 13, 95-101 (2009)
[29] Smith, G. C.; Smith, S. S.F., An enhanced genetic algorithm for automated assembly planning, Robotics and Computer-Integrated Manufacturing, 18, 355-364 (2002)
[30] Spears, W. M.; DeJong, K. A., An analysis of multi-point crossover, (Rawlins, J. E., Foundations of Genetic Algorithms (1991), Morgan Kaufman: Morgan Kaufman San Mateo, CA), 301-315
[31] Svestka, J. A.; Huckfeldt, V. E., Computational experience with an \(m\)-salesman traveling salesman algorithm, Management Science, 17, 790-799 (1973) · Zbl 0255.90033
[32] Tang, L.; Liu, J.; Rong, A.; Yang, Z., A multiple traveling salesman problem model for hot rolling scheduling in Shangai Baoshan Iron & Steel Complex, European Journal of Operational Research, 124, 276-282 (2000) · Zbl 1025.90523
[33] Walpole, R. E.; Myers, R. H.; Myers, S. L.; Ye, K., Probability & Statistics for Engineers & Scientists (2006), Prentice Hall: Prentice Hall Upper Saddle River, NJ · Zbl 1248.00007
[34] Wang, X. B.; Regan, A. C., Local truckload pickup and delivery with hard time window constraints, Transportation Research Part B, 36, 97-112 (2002)
[35] Xu, Z.; Xu, L.; Rodrigues, B., An analysis of the extended Christofides heuristic for the k-depot TSP, Operations Research Letters, 39, 218-223 (2011) · Zbl 1219.90149
[36] Yuan, S.; Skinner, B. T.; Huang, S. D.; Liu, D. K.; Dissanayake, G.; Lau, H.; Pagac, D., A job grouping approach for planning container transfers at automated seaport container terminals, Advanced Engineering Informatics, 25, 413-426 (2011)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.