×

A new approach to solving the multiple traveling salesperson problem using genetic algorithms. (English) Zbl 1137.90690

Summary: The multiple traveling salesperson problem (MTSP) involves scheduling \(m > 1\) salespersons to visit a set of \(n > m\) locations so that each location is visited exactly once while minimizing the total (or maximum) distance traveled by the salespersons. The MTSP is similar to the notoriously difficult traveling salesperson problem (TSP) with the added complication that each location may be visited by any one of the salespersons. Previous studies investigated solving the MTSP with genetic algorithms (GAs) using standard TSP chromosomes and operators. This paper proposes a new GA chromosome and related operators for the MTSP and compares the theoretical properties and computational performance of the proposed technique to previous work. Computational testing shows the new approach results in a smaller search space and, in many cases, produces better solutions than previous techniques.

MSC:

90C35 Programming involving graphs or networks
90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bellmore, M.; Malone, J., Pathology of traveling-salesman subtour elimination algorithms, Operations Research, 19, 2, 278-307 (1971) · Zbl 0219.90032
[2] Carter, A. E.; Ragsdale, C. T., Scheduling pre-printed newspaper advertising inserts using genetic algorithms, Omega, 30, 6, 415-421 (2002)
[3] Chatterjee, S.; Carrera, C.; Lynch, L., Genetic algorithms and traveling salesman problems, European Journal of Operational Research, 93, 3, 490-510 (1996) · Zbl 0912.90276
[4] Davis, L., 1985. Job shop scheduling with genetic algorithms. In: Proceedings of the International Conference on Genetic Algorithms, London, pp. 136-140.; Davis, L., 1985. Job shop scheduling with genetic algorithms. In: Proceedings of the International Conference on Genetic Algorithms, London, pp. 136-140.
[5] Falkenauer, E., Genetic Algorithms and Grouping Problems (1998), John Wiley & Sons: John Wiley & Sons New York · Zbl 0803.68037
[6] Fox, B. R.; McMahon, M. B., Genetic operators for sequencing problems, (Rawlings, G. J.E., Foundations of Genetic Algorithms (1991), Morgan Kaugmann Publishers: Morgan Kaugmann Publishers San Mateo, CA), 284-300
[7] Glover, F., Artificial intelligence, heuristic frameworks and tabu search, Managerial and Decision Economics, 11, 5, 365-378 (1990)
[8] Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0721.68056
[9] Goldberg, D.E., Lingle, R.J., 1985. Alleles, loci, and the traveling salesman problem. In: Proceedings of the International Conference on Genetic Algorithms, London, pp. 154-159.; Goldberg, D.E., Lingle, R.J., 1985. Alleles, loci, and the traveling salesman problem. In: Proceedings of the International Conference on Genetic Algorithms, London, pp. 154-159. · Zbl 0674.90095
[10] Holland, J. H., Adaptation in Natural and Artificial Systems (1975), MIT Press: MIT Press Cambridge, MA
[11] Jog, P., Suh, J.Y., Van Gucht, D., 1989. The effects of population size, heuristic crossover and local improvement on a genetic algorithm for the traveling salesman problem. In: Proceedings of the Third International Conference on Genetic Algorithms, Los Altos, CA, pp. 110-115.; Jog, P., Suh, J.Y., Van Gucht, D., 1989. The effects of population size, heuristic crossover and local improvement on a genetic algorithm for the traveling salesman problem. In: Proceedings of the Third International Conference on Genetic Algorithms, Los Altos, CA, pp. 110-115.
[12] Katayama, K.; Sakamoto, H.; Narihisa, H., The efficiency of hybrid mutation genetic algorithm for the traveling salesman problem, Mathematical and Computer Modeling, 31, 10-12, 197-203 (2000) · Zbl 1042.90651
[13] Knosala, R.; Wal, T., A production scheduling problem using genetic algorithm, Journal of Materials Processing Technology, 109, 1-2, 90-95 (2001)
[14] Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A.; Shimoys, D., The Traveling Salesman Problem (1985), John Wiley & Sons: John Wiley & Sons New York · Zbl 0563.90075
[15] Liaw, C., A hybrid genetic algorithm for the open shop scheduling problem, European Journal of Operational Research, 124, 1, 28-42 (2000) · Zbl 0960.90039
[16] Little, J.; Murty, D.; Sweeney, D.; Karel, C., An algorithm for the traveling salesman problem, Operations Research, 11, 6, 972-989 (1963) · Zbl 0161.39305
[17] Malmborg, C., A genetic algorithm for service level based vehicle scheduling, European Journal of Operational Research, 93, 1, 121-134 (1996) · Zbl 0912.90177
[18] Moon, C.; Kim, J.; Choi, G.; Seo, Y., An efficient genetic algorithm for the traveling salesman problem with precedence constraints, European Journal of Operational Research, 140, 3, 606-617 (2002) · Zbl 0998.90066
[19] Oliver, I., Smith, D., Holland, J., 1987. A study of permutation crossover operators on the traveling salesman problem. In: Proceedings of the Second International Conference on Genetic Algorithms, London, pp. 224-230.; Oliver, I., Smith, D., Holland, J., 1987. A study of permutation crossover operators on the traveling salesman problem. In: Proceedings of the Second International Conference on Genetic Algorithms, London, pp. 224-230.
[20] Park, Y. B., A hybrid genetic algorithm for the vehicle scheduling problem with due times and time deadlines, International Journal of Productions Economics, 73, 2, 175-188 (2001)
[21] Poon, P. W.; Carter, J. N., Genetic algorithm crossover operators for ordering applications, Computers and Operations Research, 22, 1, 135-147 (1995) · Zbl 0813.90098
[22] Potvin, J., Genetic algorithms for the traveling salesman problems, Annals of Operations Research, 63, 330-370 (1996) · Zbl 0851.90130
[23] Qu, L.; Sun, R., A synergetic approach to genetic algorithms for solving traveling salesman problem, Information Sciences, 117, 3-4, 267-283 (1999)
[24] Ragsdale, C. T., Spreadsheet Modeling and Decision Analysis (2001), South-Western College Publishing: South-Western College Publishing Cincinnati, OH
[25] Ross, S., Introduction to Probability Models (1984), Macmillian: Macmillian New York, NY
[26] Schaffer, J. D.; Eshelman, L. J.; Offutt, D., Spurious correlations and premature convergence in genetic algorithms, (Rawlings, G. J.E., Foundations of Genetic Algorithms (1991), Morgan Kaugmann Publishers: Morgan Kaugmann Publishers San Mateo, CA), 102-112
[27] Schmitt, L.; Amini, M., Performance characteristics of alternative genetic algorithmic approaches to the traveling salesman problem using path representation: An empirical study, European Journal of Operational Research, 108, 3, 551-570 (1998) · Zbl 0951.90010
[28] Shirrish, B.; Nigel, J.; Kabuka, M. R., A Boolean neural network approach for the traveling salesman problem, IEEE Transactions on Computers, 42, 10, 1271-1278 (1993)
[29] Starkweather, T., Whitley, D., Whitley, C., Mathial, K., 1991. A comparison of genetic sequencing operators. In: Proceedings of the Fourth International Conference on Genetic Algorithms, Los Altos, CA, pp. 69-76.; Starkweather, T., Whitley, D., Whitley, C., Mathial, K., 1991. A comparison of genetic sequencing operators. In: Proceedings of the Fourth International Conference on Genetic Algorithms, Los Altos, CA, pp. 69-76.
[30] Syswerda, G., 1989. Uniform crossover in genetic algorithms. In: Proceedings of the Third International Conference on Genetic Algorithms, Los Altos, pp. 502-508.; Syswerda, G., 1989. Uniform crossover in genetic algorithms. In: Proceedings of the Third International Conference on Genetic Algorithms, Los Altos, pp. 502-508.
[31] Tang, L.; Liu, J.; Rong, A.; Yang, Z., A multiple traveling salesman problem model for hot rolling schedule in Shanghai Baoshan Iron and Steel Complex, European Journal of Operational Research, 124, 2, 267-282 (2000) · Zbl 1025.90523
[32] Whitley, D., Starkweather, T., Fuquay, D., 1989. Scheduling problems and traveling salesmen: the genetic edge recombination operator. In: Proceedings of the Third International Conference on Genetic Algorithms, Los Altos, CA, pp. 133-140.; Whitley, D., Starkweather, T., Fuquay, D., 1989. Scheduling problems and traveling salesmen: the genetic edge recombination operator. In: Proceedings of the Third International Conference on Genetic Algorithms, Los Altos, CA, pp. 133-140.
[33] Wong, R., 1980. Integer programming formulations of the traveling salesman problem. In: Proceedings of the IEEE International Conference of Circuits and Computers, pp. 149-152.; Wong, R., 1980. Integer programming formulations of the traveling salesman problem. In: Proceedings of the IEEE International Conference of Circuits and Computers, pp. 149-152.
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.