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

Carter, Arthur E.; Ragsdale, Cliff T.

Eur. J. Oper. Res. 175, No. 1, 246-257 (2006).

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

Keywords:

genetic algorithms; scheduling; traveling salesman

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
[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
[10]	Holland, J. H., Adaptation in Natural and Artificial Systems (1975), MIT Press: MIT Press Cambridge, MA
[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
[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)
[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