×

zbMATH — the first resource for mathematics

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
PDF BibTeX XML Cite
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, () · 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. · 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.
[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.
[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, (), 883-892
[11] Bianchi, L.; Gambardella, L.M.; Dorigo, M., Solving the homogeneous probabilistic traveling salesman problem by the ACO metaheuristic, (), 176-187
[12] Birattari, M.; Balaprakash, P.; Dorigo, M., The ACO/F-RACE algorithm for combinatorial optimization under uncertainty, () · 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 London · Zbl 1130.90059
[20] Dolan, A.; Aldous, J., Networks and algorithms—an introductory approach, (1993), 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 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.
[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, (), 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.
[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.
[31] Kennedy, J.; Eberhart, R.; Shi, Y., Swarm intelligence, (2001), 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.
[36] 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, (), 141-295 · Zbl 0870.90059
[42] Psaraftis, H.N., Dynamic vehicle routing problems, (), 223-248
[43] Resende, M.G.C.; Ribeiro, C.C., Greedy randomized adaptive search procedures, (), 219-249 · Zbl 1102.90384
[44] Rossi, F.A.; Gavioli, I., Aspects of heuristics methods in the probabilistic traveling salesman problem, (), 214-227
[45] Shi, Y.; Eberhart, R., A modified particle swarm optimizer, (), 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, (), 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.