×

Estimation-based metaheuristics for the probabilistic traveling salesman problem. (English) Zbl 1188.90208

Summary: The probabilistic traveling salesman problem (PTSP) is a central problem in stochastic routing. Recently, we have shown that empirical estimation is a promising approach to devise highly effective local search algorithms for the PTSP. In this paper, we customize two metaheuristics, an iterated local search algorithm and a memetic algorithm, to solve the PTSP. This customization consists in adopting the estimation approach to evaluate the solution cost, exploiting a recently developed estimation-based local search algorithm, and tuning the metaheuristics parameters. We present an experimental study of the estimation-based metaheuristic algorithms on a number of instance classes. The results show that the proposed algorithms are highly effective and that they define a new state-of-the-art for the PTSP.

MSC:

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

Software:

DIMACS; MPFR; Concorde; ACOTSP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Hoos, H.; Stützle, T., Stochastic local search: foundations and applications (2005), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA · Zbl 1126.68032
[2] Jaillet, P., A priori solution of a travelling salesman problem in which a random subset of the customers are visited, Operations Research, 36, 6, 929-936 (1988) · Zbl 0665.90096
[3] Bertsimas D. Probabilistic combinatorial optimization problems. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, 1988.; Bertsimas D. Probabilistic combinatorial optimization problems. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, 1988.
[4] Birattari, M.; Balaprakash, P.; Stützle, 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
[5] Balaprakash, P.; Birattari, M.; Stützle, T.; Dorigo, M., Adaptive sample size and importance sampling in estimation-based local search for the probabilistic traveling salesman problem, European Journal of Operational Research, 199, 1, 98-110 (2009) · Zbl 1176.90479
[6] Dorigo, M.; Stützle, T., Ant colony optimization (2004), MIT Press: MIT Press Cambridge, MA · Zbl 1092.90066
[7] Balaprakash, P.; Birattari, M.; Stützle, T.; Yuan, Z.; Dorigo, M., Estimation-based ant colony optimization and local search for the probabilistic traveling salesman problem, Swarm Intelligence, 3, 3, 223-242 (2009)
[8] Lourenço, H. R.; Martin, O.; Stützle, T., Iterated local search, (Glover, F.; Kochenberger, G., Handbook of metaheuristics. International series in operations research and management science, vol. 57 (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA), 321-353 · Zbl 1116.90412
[9] Moscato P. On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms. C3P Report 826, Caltech Concurrent Computation Program; 1989.; Moscato P. On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms. C3P Report 826, Caltech Concurrent Computation Program; 1989.
[10] Moscato, P., Memetic algorithms: a short introduction, (Corne, D.; Dorigo, M.; Glover, F., New ideas in optimization (1999), McGraw-Hill: McGraw-Hill London, UK), 219-234
[11] Bertsimas, D.; Jaillet, P.; Odoni, A., A priori optimization, Operations Research, 38, 6, 1019-1033 (1990) · Zbl 0721.90062
[12] Kleywegt, A. J.; Shapiro, A.; Homem-de-Mello, T., The sample average approximation method for stochastic discrete optimization, SIAM Journal on Optimization, 12, 2, 479-502 (2002) · Zbl 0991.90090
[13] Laporte, G.; Louveaux, F.; Mercure, H., A priori optimization of the probabilistic traveling salesman problem, Operations Research, 42, 543-549 (1994) · Zbl 0810.90124
[14] Bianchi, L.; Gambardella, L.; Dorigo, M., Solving the homogeneous probabilistic travelling salesman problem by the ACO metaheuristic, (Dorigo, M.; Di Caro, G.; Sampels, M., Ant algorithms, third international workshop, ANTS 2002. Lecture notes in computer science, vol. 2463 (2002), Springer: Springer Berlin, Germany), 176-187
[15] Bianchi, L.; Gambardella, L. M.; Dorigo, M., An ant colony optimization approach to the probabilistic traveling salesman problem, (Guervós, J. J.; Adamidis, P.; Beyer, H.; Martín, J. L.; Schwefel, H.-P., 7th international conference on parallel problem solving from nature, PPSN VII, Lecture notes in computer science, vol. 2439 (2002), Springer: Springer Berlin, Germany), 883-892
[16] Dorigo, M.; Gambardella, L. M., Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, 1, 1, 53-66 (1997)
[17] Branke, J.; Guntsch, M., New ideas for applying ant colony optimization to the probabilistic TSP, (Raidl, G.; Cagnoni, S.; Cardalda, J.; Corne, D.; Gottlieb, J.; Guillot, A.; Hart, E.; Johnson, C.; Marchiori, E.; Meyer, J.-A.; Middendorf, M., Applications of evolutionary computing. Lecture notes in computer science, vol. 2611 (2003), Springer: Springer Berlin, Germany), 127-134 · Zbl 1033.90516
[18] 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
[19] Liu, Y., A hybrid scatter search for the probabilistic traveling salesman problem, Computers & Operations Research, 34, 10, 2949-2963 (2007) · Zbl 1185.90162
[20] Liu, Y., Diversified local search strategy under scatter search framework for the probabilistic traveling salesman problem, European Journal of Operational Research, 191, 2, 332-346 (2008) · Zbl 1149.90128
[21] Bianchi L. Ant colony optimization and local search for the probabilistic traveling salesman problem: a case study in stochastic combinatorial optimization. PhD thesis, Université Libre de Bruxelles, Brussels, 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, Université Libre de Bruxelles, Brussels, Belgium; 2006.
[22] Bianchi L, Gambardella LM. Ant colony optimization and local search based on exact and estimated objective values for the probabilistic traveling salesman problem. Technical Report IDSIA-06-07, IDSIA, USI-SUPSI, Manno, Switzerland; June 2007.; Bianchi L, Gambardella LM. Ant colony optimization and local search based on exact and estimated objective values for the probabilistic traveling salesman problem. Technical Report IDSIA-06-07, IDSIA, USI-SUPSI, Manno, Switzerland; June 2007.
[23] Marinakis, Y.; Marinaki, M., A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem, Computers & Operations Research, 37, 3, 432-442 (2010) · Zbl 1173.90515
[24] Marinakis, Y.; Migdalas, A.; Pardalos, P., Expanding neighborhood search—GRASP for the probabilistic traveling salesman problem, Optimization Letters, 2, 3, 351-361 (2008) · Zbl 1159.90462
[25] Birattari, M.; Zlochin, M.; Dorigo, M., Towards a theory of practice in metaheuristics design: a machine learning perspective, Theoretical Informatics and Applications, 40, 2, 353-369 (2006) · Zbl 1112.68109
[26] Birattari, M., Tuning metaheuristics: a machine learning perspective, Studies in computational intelligence, vol. 197 (2009), Springer: Springer Berlin, Germany · Zbl 1183.68464
[27] Gutjahr, W. J., A converging ACO algorithm for stochastic combinatorial optimization, (Albrecht, A.; Steinhofl, K., Stochastic algorithms: foundations and applications. Lecture notes in computer science, vol. 2827 (2003), Springer: Springer Berlin, Germany), 10-25 · Zbl 1161.90449
[28] Gutjahr, W. J., S-ACO: an ant based approach to combinatorial optimization under uncertainity, (Dorigo, M.; Birattari, M.; Blum, C.; Gambardella, L. M.; Mondada, F.; Stützle, T., Ant colony optimization and swarm intelligence, 5th international workshop, ANTS 2004. Lecture notes in computer science, vol. 3172 (2004), Springer: Springer Berlin, Germany), 238-249
[29] Birattari M, Balaprakash P, Dorigo M. ACO/F-Race: ant colony optimization and racing techniques for combinatorial optimization under uncertainty. In: Doerner KF, Gendreau M, Greistorfer P, Gutjahr WJ, Hartl RF, Reimann M, editors. Proceedings of the 6th metaheuristics international conference, MIC 2005, 2005. p. 107-12.; Birattari M, Balaprakash P, Dorigo M. ACO/F-Race: ant colony optimization and racing techniques for combinatorial optimization under uncertainty. In: Doerner KF, Gendreau M, Greistorfer P, Gutjahr WJ, Hartl RF, Reimann M, editors. Proceedings of the 6th metaheuristics international conference, MIC 2005, 2005. p. 107-12.
[30] Birattari, M.; Stützle, T.; Paquete, L.; Varrentrapp, K., A racing algorithm for configuring metaheuristics, (Langdon, W. B.; etal., Proceedings of the genetic and evolutionary computation conference, GECCO 2002 (2002), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA), 11-18
[31] Bowler, N. E.; Fink, T. M.A.; Ball, R. C., Characterization of the probabilistic traveling salesman problem, Physical Review E, 68, 3, 036703-036710 (2003)
[32] Bentley, J. L., Fast algorithms for geometric traveling salesman problems, ORSA Journal on Computing, 4, 4, 387-411 (1992) · Zbl 0758.90071
[33] Rubinstein, R. Y., Simulation and the Monte Carlo method (1981), Wiley: Wiley New York, NY · Zbl 0529.68076
[34] Johnson, D. S.; McGeoch, L. A., The travelling salesman problem: a case study in local optimization, (Aarts, E. H.L.; Lenstra, J. K., Local search in combinatorial optimization (1997), Wiley: Wiley Chichester, UK), 215-310 · Zbl 0947.90612
[35] Fisher, R. A., Statistical methods for research workers (1925), Oliver and Boyd: Oliver and Boyd London, UK · JFM 51.0414.08
[36] Tukey, J. W., Comparing individual means in the analysis of variance, Biometrics, 5, 2, 99-114 (1949)
[37] 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
[38] Bianchi, L.; Campbell, A., Extension of the 2-p-opt and 1-shift algorithms to the heterogeneous probabilistic traveling salesman problem, European Journal of Operational Research, 176, 1, 131-144 (2007) · Zbl 1137.90686
[39] Merz, P.; Freisleben, B., Memetic algorithms for the traveling salesman problem, Complex Systems, 13, 4, 297-345 (2001) · Zbl 1167.90693
[40] Johnson DS, McGeoch LA, Rego C, Glover F. 8th DIMACS implementation challenge, 2001. URL \(\langle\) http://www.research.att.com/ dsj/chtsp/\( \rangle \); Johnson DS, McGeoch LA, Rego C, Glover F. 8th DIMACS implementation challenge, 2001. URL \(\langle\) http://www.research.att.com/ dsj/chtsp/\( \rangle \)
[41] Stützle T. ACOTSP: a software package of various ant colony optimization algorithms applied to the symmetric traveling salesman problem, 2002. URL \(\langle\) http://www.aco-metaheuristic.org/aco-code/\( \rangle \); Stützle T. ACOTSP: a software package of various ant colony optimization algorithms applied to the symmetric traveling salesman problem, 2002. URL \(\langle\) http://www.aco-metaheuristic.org/aco-code/\( \rangle \)
[42] Penky, J. F.; Miller, D. L., A staged primal-dual algorithm for finding a minimum cost perfect two-matching in an undirected graph, ORSA Journal on Computing, 6, 1, 68-81 (1994) · Zbl 0798.90128
[43] Campbell, A. M., Aggregation for the probabilistic traveling salesman problem, Computers & Operations Research, 33, 9, 2703-2724 (2006) · Zbl 1086.90047
[44] Tang, H.; Miller-Hooks, E., Approximate procedures for probabilistic traveling salesperson problem, Transportation Research Record: Journal of the Transportation Research Board, 1882, 27-36 (2004)
[45] Campbell AM, Thomas BW. Challenges and advances in a priori routing. In Golden B, Raghavan S, Wasil E, editors. The vehicle routing problem: latest advances and new challenges, Operations Research/Computer Science Interfaces, vol. 43. SV, 2008. p. 123-42.; Campbell AM, Thomas BW. Challenges and advances in a priori routing. In Golden B, Raghavan S, Wasil E, editors. The vehicle routing problem: latest advances and new challenges, Operations Research/Computer Science Interfaces, vol. 43. SV, 2008. p. 123-42.
[46] Balaprakash, P.; Birattari, M.; Stützle, T., Improvement strategies for the F-Race algorithm: sampling design and iterative refinement, (Bartz-Beielstein, T.; Blesa, M.; Blum, C.; Naujoks, B.; Roli, A.; Rudolph, G.; Sampels, M., Hybrid metaheuristics, HM 2007. Lecture notes in computer science, vol. 4771 (2007), Springer: Springer Berlin, Germany), 113-127
[47] Gutjahr, W. J.; Pflug, G. C., Simulated annealing for noisy cost functions, Journal of Global Optimization, 8, 1, 1-13 (1996) · Zbl 0857.90095
[48] Fousse, L.; Hanrot, G.; Lefèvre, V.; Pélissier, P.; Zimmermann, P., MPFR: a multiple-precision binary floating-point library with correct rounding, ACM Transactions on Mathematical Software, 33, 2, 1-15 (2007), URL \(\langle\) http://www.mpfr.org/\( \rangle \) · Zbl 1365.65302
[49] Applegate D, Bixby RE, Chvatal V, Cook WJ. Concorde—a code for solving traveling salesman problems, 2001. URL \(\langle\) http://www.math.princeton.edu/tsp/concorde.html \(\rangle \); Applegate D, Bixby RE, Chvatal V, Cook WJ. Concorde—a code for solving traveling salesman problems, 2001. URL \(\langle\) http://www.math.princeton.edu/tsp/concorde.html \(\rangle \)
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.