×

A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem. (English) Zbl 1173.90515

Summary: The Probabilistic Traveling Salesman Problem (PTSP) is a variation of the classic Traveling Salesman Problem (TSP) and one of the most significant stochastic routing problems. In the PTSP, only a subset of potential customers need to be visited on any given instance of the problem. The number of customers to be visited each time is a random variable. In this paper, a new hybrid algorithmic nature inspired approach based on Particle Swarm Optimization (PSO), Greedy Randomized Adaptive Search Procedure (GRASP) and Expanding Neighborhood Search (ENS) Strategy is proposed for the solution of the PTSP. The proposed algorithm is tested on numerous benchmark problems from TSPLIB with very satisfactory results. Comparisons with the classic GRASP algorithm, the classic PSO and with a Tabu Search algorithm are also presented. Also, a comparison is performed with the results of a number of implementations of the Ant Colony Optimization algorithm from the literature and in 13 out of 20 cases the proposed algorithm gives a new best solution.

MSC:

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

Software:

MCPSO; TSPLIB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balaprakash, P.; Birattari, M.; Stutzle, T., Engineering stochastic local search algorithms: a case study in estimation-based local search for the probabilistic traveling salesman problem, (Cotta, C.; van Hemert, J., Recent Advances in Evolutionary Computation for Combinatorial Optimization. Studies in Computational Intelligence (2008), Springer: Springer Berlin) · Zbl 1159.90467
[2] Balaprakash P, Birattari M, Stutzle T, Dorigo M. An experimental study of estimation-based metaheuristics for the probabilistic traveling salesman problem. In: Learning and intelligent optimization, LION 2007 II, December 8-12, 2007, Trento, Italy.; Balaprakash P, Birattari M, Stutzle T, Dorigo M. An experimental study of estimation-based metaheuristics for the probabilistic traveling salesman problem. In: Learning and intelligent optimization, LION 2007 II, December 8-12, 2007, Trento, Italy. · Zbl 1188.90208
[3] Banks, A.; Vincent, J.; Anyakoha, C., A review of particle swarm optimization. Part I: background and development, Natural Computing, 6, 4, 467-484 (2007) · Zbl 1125.90065
[4] Banks, A.; Vincent, J.; Anyakoha, C., A review of particle swarm optimization. Part II: hybridisation, combinatorial, multicriteria and constrained optimization, and indicative applications, Natural Computing, 7, 109-124 (2008) · Zbl 1148.68375
[5] Bertsimas DJ. Probabilistic combinatorial optimization problems. PhD thesis, MIT, Cambridge, MA, USA; 1988.; Bertsimas DJ. Probabilistic combinatorial optimization problems. PhD thesis, MIT, Cambridge, MA, USA; 1988.
[6] Bertsimas, D.; Howell, L., Further results on the probabilistic traveling salesman problem, European Journal of Operational Research, 65, 1, 68-95 (1993) · Zbl 0776.90082
[7] Bertsimas, D.; Chervi, P.; Peterson, M., Computational approaches to stochastic vehicle routing problems, Transportation Science, 29, 4, 342-352 (1995) · Zbl 0853.90037
[8] Bianchi L. Ant colony optimization and local search for the probabilistic traveling salesman problem: a case study in stochastic combinatorial optimization. PhD thesis, Universite Libre de Bruxelles, Belgium; 2006.; Bianchi L. Ant colony optimization and local search for the probabilistic traveling salesman problem: a case study in stochastic combinatorial optimization. PhD thesis, Universite Libre de Bruxelles, Belgium; 2006.
[9] Bianchi, L.; Knowles, J.; Bowler, N., Local search for the probabilistic traveling salesman problem: correction to the 2-p-opt and 1-shift algorithms, European Journal of Operational Research, 162, 1, 206-219 (2005) · Zbl 1132.90364
[10] Bianchi, L.; Gambardella, L. M.; Dorigo, M., An ant colony optimization approach to the probabilistic traveling salesman problem, (Merelo Guervòs, J. J.; Adamidis, P.; Beyer, H.-G.; Fernández-Villacañas, J.-L.; Schwefel, H.-P., Proceedings of the seventh parallel problem solving from nature (PPSN VII). Lecture notes in computer science, vol. 2439 (2002), Springer: Springer Berlin), 883-892
[11] Bianchi, L.; Gambardella, L. M.; Dorigo, M., Solving the homogeneous probabilistic traveling salesman problem by the ACO metaheuristic, (Dorigo, M.; DiCaro, G.; Sampels, M., Proceedings of third international workshop ANTS 2002. Lecture notes in computer science, vol. 2463 (2002), Springer: Springer Berlin), 176-187
[12] Birattari, M.; Balaprakash, P.; Dorigo, M., The ACO/F-RACE algorithm for combinatorial optimization under uncertainty, (Doerner, K. F.; etal., Metaheuristics—progress in complex systems optimization. Operations research. Computer science interfaces series (2006), Springer: Springer Berlin, Germany) · Zbl 1173.90587
[13] Birattari, M.; Balaprakash, P.; Stutzle, T.; Dorigo, M., Estimation-based local search for stochastic combinatorial optimization using delta evaluations: a case study in the probabilistic traveling salesman problem, INFORMS Journal on Computing, 20, 4, 644-658 (2008) · Zbl 1243.90154
[14] Bowler, N. E.; Fink, T. M.A.; Ball, R. C., Characterization of the probabilistic traveling salesman problem, Physical Review E, 68, 2, 036703-1-036703-7 (2003)
[15] Branke, J.; Guntsch, M., Solving the probabilistic TSP with ant colony optimization, Journal of Mathematical Modelling and Algorithms, 3, 4, 403-425 (2004) · Zbl 1079.90169
[16] Brits, R.; Engelbrecht, A. P.; van den Bergh, F., Locating multiple optima using particle swarm optimization, Applied Mathematics and Computation, 189, 1859-1883 (2007) · Zbl 1122.65358
[17] Campbell, A. M., Aggregation for the probabilistic travelling salesman problem, Computers and Operations Research, 33, 2703-2724 (2006) · Zbl 1086.90047
[18] Choi, J.; Lee, J. H.; Realff, M. J., An algorithmic framework for improving heuristic solutions: part II. A new version of the stochastic traveling salesman problem, Computers and Chemical Engineering, 28, 8, 1297-1307 (2004)
[19] Clerc, M., Particle swarm optimization (2006), ISTE: ISTE London · Zbl 1130.90059
[20] Dolan, A.; Aldous, J., Networks and algorithms—an introductory approach (1993), Wiley: Wiley Chichester · Zbl 0839.90130
[21] Feo, T. A.; Resende, M. G.C., Greedy randomized adaptive search procedure, Journal of Global Optimization, 6, 109-133 (1995) · Zbl 0822.90110
[22] Garfinkel, R.; Nemhauser, G., Integer programming (1972), Wiley: Wiley New York · Zbl 0259.90022
[23] Glover, F., Tabu search I, ORSA Journal on Computing, 1, 3, 190-206 (1989) · Zbl 0753.90054
[24] Glover, F., Tabu search II, ORSA Journal on Computing, 2, 1, 4-32 (1990) · Zbl 0771.90084
[25] Hansen, P.; Mladenovic, N., Variable neighborhood search: principles and applications, European Journal of Operational Research, 130, 449-467 (2001) · Zbl 0981.90063
[26] Jaillet P. Probabilistic traveling salesman problems. PhD thesis, MIT, Cambridge, MA, USA; 1985.; Jaillet P. Probabilistic traveling salesman problems. PhD thesis, MIT, Cambridge, MA, USA; 1985.
[27] Jaillet, P., A priori solution of a traveling salesman problem in which a random subset of the customers are visited, Operations Research, 36, 6, 929-936 (1988) · Zbl 0665.90096
[28] Jaillet, P.; Odoni, A. R., The probabilistic vehicle routing problem, (Golden, B. L.; Assad, A. A., Vehicle routing: methods and studies (1988), Elsevier Science Publishers B.V., North-Holland: Elsevier Science Publishers B.V., North-Holland Amsterdam), 293-318
[29] Kennedy J, Eberhart R. Particle swarm optimization. In: Proceedings of 1995 IEEE international conference on neural networks, vol. 4, 1995. p. 1942-8.; Kennedy J, Eberhart R. Particle swarm optimization. In: Proceedings of 1995 IEEE international conference on neural networks, vol. 4, 1995. p. 1942-8.
[30] Kennedy J, Eberhart R. A discrete binary version of the particle swarm algorithm. In: Proceedings of 1997 IEEE international conference on systems, man, and cybernetics, vol. 5, 1997. p. 4104-8.; Kennedy J, Eberhart R. A discrete binary version of the particle swarm algorithm. In: Proceedings of 1997 IEEE international conference on systems, man, and cybernetics, vol. 5, 1997. p. 4104-8.
[31] Kennedy, J.; Eberhart, R.; Shi, Y., Swarm intelligence (2001), Morgan Kaufmann Publisher: Morgan Kaufmann Publisher San Francisco
[32] Laporte, G.; Louveaux, E.; Mercure, H., A priori optimization of the probabilistic traveling salesman problem, Operations Research, 42, 543-549 (1994) · Zbl 0810.90124
[33] Lin, S., Computer solutions of the traveling salesman problem, Bell System Technical Journal, 44, 2245-2269 (1965) · Zbl 0136.14705
[34] Liu, Y. H., A hybrid scatter search for the probabilistic traveling salesman problem, Computers and Operations Research, 34, 10, 2949-2963 (2007) · Zbl 1185.90162
[35] Liu Y-H, Jou R-C, Wang C-J. Genetic algorithms for the probabilistic traveling salesman problem. In: Proceedings of the conference on E-logistics, 2004. p. 77-82.; Liu Y-H, Jou R-C, Wang C-J. Genetic algorithms for the probabilistic traveling salesman problem. In: Proceedings of the conference on E-logistics, 2004. p. 77-82.
[36] Marinakis Y. Vehicle routing in distribution problems. PhD thesis, Technical University of Crete, Department of Production Engineering and Management, Chania, Greece; 2005.; Marinakis Y. Vehicle routing in distribution problems. PhD thesis, Technical University of Crete, Department of Production Engineering and Management, Chania, Greece; 2005.
[37] Marinakis, Y.; Migdalas, A.; Pardalos, P. M., Expanding neighborhood GRASP for the traveling salesman problem, Computational Optimization and Applications, 32, 231-257 (2005) · Zbl 1125.90042
[38] Marinakis, Y.; Migdalas, A.; Pardalos, P. M., Expanding neighborhood search GRASP for the probabilistic traveling salesman problem, Optimization Letters, 2, 3, 351-361 (2008) · Zbl 1159.90462
[39] Niu, B.; Zhu, Y.; He, X.; Wu, H., MCPSO: a multi-swarm cooperative particle swarm optimizer, Applied Mathematics and Computation, 185, 1050-1062 (2007) · Zbl 1112.65055
[40] Poli, R.; Kennedy, J.; Blackwell, T., Particle swarm optimization. An overview, Swarm Intelligence, 1, 33-57 (2007)
[41] Powell, W. B.; Jaillet, P.; Odoni, A., Stochastic and dynamic networks and routing, (Ball, M. O.; Magnanti, T. L.; Momma, C. L.; Nemhauser, G. L., Network routing, handbooks in operations research and management science, vol. 8 (1995), Elsevier Science B.V.: Elsevier Science B.V. Amsterdam), 141-295 · Zbl 0870.90059
[42] Psaraftis, H. N., Dynamic vehicle routing problems, (Golden, B. L.; Assad, A. A., Vehicle routing: methods and studies (1988), Elsevier Science Publishers B.V., North-Holland: Elsevier Science Publishers B.V., North-Holland Amsterdam), 223-248
[43] Resende, M. G.C.; Ribeiro, C. C., Greedy randomized adaptive search procedures, (Glover, F.; Kochenberger, G. A., Handbook of metaheuristics (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Boston), 219-249 · Zbl 1102.90384
[44] Rossi, F. A.; Gavioli, I., Aspects of heuristics methods in the probabilistic traveling salesman problem, (Andreatta, G.; Mason, F.; Serafini, P., Advanced school on stochastics in combinatorial optimization (1987), World Scientific Press: World Scientific Press Singapore), 214-227
[45] Shi, Y.; Eberhart, R., A modified particle swarm optimizer, (Proceedings of 1998 IEEE world congress on computational intelligence (1998)), 69-73
[46] Tang, H.; Miller-Hooks, E., Approximate procedures for the probabilistic traveling salesperson problem, Transportation Research Record, 2004, 27-36 (1882)
[47] Tillett, T.; Rao, T. M.; Sahin, F.; Rao, R., Darwinian particle swarm optimization, (Proceedings of the 2nd Indian international conference on artificial intelligence, Pune, India (2005)), 1474-1487
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.