×

A hybrid scatter search for the probabilistic traveling salesman problem. (English) Zbl 1185.90162

Summary: The probabilistic traveling salesman problem (PTSP) is an important theoretical and practical topic in the study of stochastic network problems. It provides researchers with a modeling framework for exploring the stochastic effects in routing problems. This paper focuses on developing the hybrid scatter search (HSS) by incorporating the nearest neighbor rule (NNR), threshold accepting (TA) and edge recombination (ER) crossover into a scatter search conceptual framework to solve the PTSP. A set of numerical experiments were conducted to test the validity of the HSS based on the test problems from Tang and Miller-Hooks’ study. The numerical results showed that the HSS can effectively solve the PTSP in most of the tested cases in terms of objective function value. Moreover, the results also indicated that incorporating threshold accepting into the scatter search framework can further increase the computation efficiency while maintaining solution quality. These findings show the potential of the proposed HSS in solving the large-scale PTSP.

MSC:

90C15 Stochastic programming
90C27 Combinatorial optimization

Software:

Scatter Search
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Jaillet P. Probabilistic traveling salesman problems. Dissertation, Massachusetts Institute of Technology, USA, 1985.; Jaillet P. Probabilistic traveling salesman problems. Dissertation, Massachusetts Institute of Technology, USA, 1985.
[2] Bertsimas D. Probabilistic combinatorial optimization problems. Dissertation, Massachusetts Institute of Technology, USA, 1988.; Bertsimas D. Probabilistic combinatorial optimization problems. Dissertation, Massachusetts Institute of Technology, USA, 1988.
[3] Bertsimas, D.; Jaillet, P.; Odoni, A. R., A priori optimization, Operations Research, 38, 6, 1019-1033 (1990) · Zbl 0721.90062
[4] 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
[5] Bartholdi, J. J.; Platzman, L. K., Heuristics based on spacefilling curves for combinatorial problems in Euclidean space, Management Science, 34, 3, 291-305 (1988) · Zbl 0639.90068
[6] Bartholdi, J. J.; Platzman, L. K.; Collins, R. L.; Warden, W. H., A minimal technology routing system for meals on wheels, Interfaces, 13, 3, 1-8 (1983)
[7] Tang, H.; Miller-Hooks, E., Approximate procedures for the probabilistic traveling salesperson problem, Transportation Research Record, 1882, 27-36 (2004)
[8] Bertsimas, D.; Chervi, P.; Peterson, M., Computational approaches to stochastic vehicle routing problems, Transportation Science, 29, 4, 342-352 (1995) · Zbl 0853.90037
[9] Jaillet, P., Stochastic routing problems, (Andreatta, G.; Mason, F.; Serafini, P., Advanced school on stochastics in combinatorial optimization (1987), World Scientific Publisher: World Scientific Publisher Singapore), 192-213
[10] 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
[11] Bianchi, L.; Knowles, J.; Bowler, N., Local search for the probabilistic traveling salesman problemcorrection to the 2-p-opt and 1-shift algorithms, European Journal of Operational Research, 162, 1, 206-219 (2005) · Zbl 1132.90364
[12] Rossi, F.; Gavioli, I., Aspects of heuristic method in the “probabilistic traveling salesman problem”, (Andreatta, G.; Mason, F.; Serafini, P., Advanced school on stochastics in combinatorial optimization (1987), World Scientific Publisher: World Scientific Publisher Singapore), 214-227
[13] Laporte, G.; Louveaux, F.; Mercure, H., A priori optimization of the probabilistic traveling salesman problem, Operations Research, 42, 3, 543-549 (1994) · Zbl 0810.90124
[14] Bianchi L, Gambardella LM, Dorigo M. An ant colony optimization approach to the probabilistic traveling salesman problem. In: Merelo Guervós JJ, Adamidis P, Beyer H-G, Fernández-Villacañas J-L, Schwefel H-P, editors. Proceedings of the seventh parallel problem solving from nature (PPSN VII), Lecture notes in computer science, vol. 2439. Berlin: Springer; 2002. p. 883-92.; Bianchi L, Gambardella LM, Dorigo M. An ant colony optimization approach to the probabilistic traveling salesman problem. In: Merelo Guervós JJ, Adamidis P, Beyer H-G, Fernández-Villacañas J-L, Schwefel H-P, editors. Proceedings of the seventh parallel problem solving from nature (PPSN VII), Lecture notes in computer science, vol. 2439. Berlin: Springer; 2002. p. 883-92.
[15] Bianchi L, Gambardella LM, Dorigo M. Solving the homogeneous probabilistic traveling salesman problem by the ACO metaheuristic. In: Dorigo M, DiCaro G, Sampels M, editors. Proceedings of third international workshop ANTS 2002, Lecture notes in computer science, vol. 2463. Berlin: Springer; 2002. p. 176-87.; Bianchi L, Gambardella LM, Dorigo M. Solving the homogeneous probabilistic traveling salesman problem by the ACO metaheuristic. In: Dorigo M, DiCaro G, Sampels M, editors. Proceedings of third international workshop ANTS 2002, Lecture notes in computer science, vol. 2463. Berlin: Springer; 2002. p. 176-87.
[16] 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
[17] Liu, Y-H.; Jou, R-C.; Wang, C-J., Genetic algorithms for the probabilistic traveling salesman problem, (Proceedings of the conference on E-logistics, Taoyuan, Taiwan (2004)), 77-82
[18] Bowler, N. E.; Fink, T. M.A.; Ball, R. C., Characterization of the probabilistic traveling salesman problem, Physical Review E, 68, 3, 036703 (2003)
[19] Glover F. A template for scatter search and path relinking. In: Hao J-K, Lutton E, Ronald E, Schoenauer M, Snyers D, editors. Artificial evolution, Lecture notes in computer science, vol. 1363. Berlin: Springer; 1998. p. 3-51.; Glover F. A template for scatter search and path relinking. In: Hao J-K, Lutton E, Ronald E, Schoenauer M, Snyers D, editors. Artificial evolution, Lecture notes in computer science, vol. 1363. Berlin: Springer; 1998. p. 3-51.
[20] Laguna, M.; Martí, R., Scatter searchmethodology and implementations in C (2003), Kluwer Academic Publishers: Kluwer Academic Publishers London
[21] Liu Y-H. Incorporating scatter search and threshold accepting in multinomial probit model estimation. Technical Report NSC 93-2416-H-260-002, National Science Council, Taiwan, 2005.; Liu Y-H. Incorporating scatter search and threshold accepting in multinomial probit model estimation. Technical Report NSC 93-2416-H-260-002, National Science Council, Taiwan, 2005.
[22] Bulut G. Robust multi-scenario optimization of an air expeditionary force: force structure applying scatter search to the combat forces assessment model. Thesis, Air Force Institute of Technology, USA, 2001.; Bulut G. Robust multi-scenario optimization of an air expeditionary force: force structure applying scatter search to the combat forces assessment model. Thesis, Air Force Institute of Technology, USA, 2001.
[23] Hung, W. N.N.; Song, X.; Aboulhamid, E. M.; Driscoll, M. A., BDD minimization by scatter search, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 21, 8, 974-979 (2002)
[24] Liu Y-H, Jou R-C, Yeap B-K. Multinomial probit (MNP) model estimation—comparisons of different optimization methods. Journal of the Chinese Institute of Civil and Hydraulic Engineering 2005, in press.; Liu Y-H, Jou R-C, Yeap B-K. Multinomial probit (MNP) model estimation—comparisons of different optimization methods. Journal of the Chinese Institute of Civil and Hydraulic Engineering 2005, in press.
[25] Glover, F.; Laguna, M.; Martí, R., Scatter search and path relinkingadvances and applications, (Glover, F.; Kochenberger, G., Handbook of metaheuristics (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Boston), 1-36
[26] Greistorfer, P., A tabu scatter search metaheuristic for the arc routing problem. Computer and Industrial Engineering, 44, 2, 249-266 (2003)
[27] García-López, F.; Melián-Batista, B.; Moreno-Pérez, J. A.; Moreno-Vega, J. M., Parallelization of the scatter search for the \(p\)-median problem, Parallel Computing, 29, 5, 575-589 (2003)
[28] Jaillet, P.; Odoni, A. R., The probabilistic vehicle routing problem, (Golden, B. L.; Assad, A. A., Vehicle routingmethods and studies (1988), North-Holland: North-Holland Amsterdam), 293-318
[29] Rosenkrantz, D. J.; Stearns, R. E.; Lewis II, P. M., An analysis of several heuristics for the traveling salesman problem, SIAM Journal of Computing, 6, 3, 563-581 (1977) · Zbl 0364.90104
[30] Hurkens, C. A.J.; Woeginger, G. J., On the nearest neighbor rule for the traveling salesman problem, Operations Research Letters, 32, 1, 1-4 (2004) · Zbl 1056.90117
[31] Potvin, J. Y., Genetic algorithms for the traveling salesman problem, Annals of Operations Research, 63, 339-370 (1996) · Zbl 0851.90130
[32] Whitley, D.; Starkweather, T.; Fuquay, D., Scheduling problems and traveling salesmenthe genetic edge recombination operator, (Proceedings of the third international conference on genetic algorithms (ICGA ‘89) (1989), Morgan Kaufmann: Morgan Kaufmann Palo Alto, CA), 133-140
[33] Dueck, G.; Scheuer, T., Threshold acceptinga general purpose optimization algorithm appearing superior to simulated annealing, Journal of Computational Physics, 90, 1, 161-175 (1990) · Zbl 0707.65039
[34] Schneider, J.; Froschhammer, C.; Morgenstern, I.; Husslein, T.; Singer, J. M., Searching for backbones—an efficient parallel algorithm for the traveling salesman problem, Computer Physics Communications, 96, 2-3, 173-188 (1996) · Zbl 0921.90143
[35] Schrimpf, G.; Schneider, J.; Stamm-Wilbrandt, H.; Dueck, G., Record breaking optimization results using the ruin and recreate principle, Journal of Computational Physics, 159, 2, 139-171 (2000) · Zbl 0997.90105
[36] Tafelmayer, R.; Hoffmann, K. H., Scaling features in complex optimization problems, Computer Physics Communications, 86, 1-2, 81-90 (1995) · Zbl 0879.90156
[37] Tarantilis, C. D.; Kiranoudis, C. T.; Vassiliadis, V. S., A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem, European Journal of Operational Research, 152, 1, 148-158 (2004) · Zbl 1045.90007
[38] Bräysy, O.; Hasle, G.; Dullaert, W., A multi-start local search algorithm for the vehicle routing problem with time windows, European Journal of Operational Research, 159, 3, 586-605 (2004) · Zbl 1065.90013
[39] Lin, S.; Kernighan, B. W., An effective heuristic algorithm for the traveling salesman problem, Operations Research, 21, 2, 498-516 (1973) · Zbl 0256.90038
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.