Abstract
In this paper we present new local search algorithms for the Probabilistic Traveling Salesman Problem (PTSP) using sampling and ad-hoc approximation. These algorithms improve both runtime and solution quality of state-of-the-art local search algorithms for the PTSP.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Complete Numerical Results, http://www.idsia.ch/~weyland
Balaprakash, P., Birattari, M., Stützle, T., Dorigo, M.: Adaptive sample size and importance sampling in estimation-based local search for stochastic combinatorial optimization: A complete analysis. Technical Report TR/IRIDIA/2007-015, IRIDIA, Université Libre de Bruxelles, Brussels, Belgium (September 2007)
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. Technical report, Brussels, Belgium (September 2008)
Bianchi, L., Dorigo, M., Gambardella, L.M., Gutjahr, W.J.: A survey on metaheuristics for stochastic combinatorial optimization problems. Accepted for publication at Natural Computing (2008), doi. 10.1007/s11047-008-9098-4
Bianchi, L., Gambardella, L.M., Dorigo, M.: An ant colony optimization approach to the probabilistic traveling salesman problem. In: PPSN VII: Proceedings of the 7th International Conference on Parallel Problem Solving from Nature, pp. 883–892. Springer, Heidelberg (2002)
Bianchi, L., Gambardella, L.M., Dorigo, M.: Solving the homogeneous probabilistic traveling salesman problem by the aco metaheuristic. In: ANTS 2002, pp. 176–187. Springer, Heidelberg (2002)
Birattari, M., Balaprakash, P., Stützle, T., Dorigo, M.: Estimation-based local search for stochastic combinatorial optimization. Technical Report TR/IRIDIA/2007-003, IRIDIA, Université Libre de Bruxelles, Brussels, Belgium (February 2007)
Jaillet, P.: Probabilistic Traveling Salesman Problems. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA (1985)
Johnson, D.S., McGeoch, L.A.: The traveling salesman problem: A case study. In: Aarts, E.H.L., Lenstra, J.K. (eds.) Local Search in Combinatorial Optimization, pp. 215–310. Wiley, Chichester (1997)
TSPLIB, http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Weyland, D., Bianchi, L., Gambardella, L.M. (2009). New Approximation-Based Local Search Algorithms for the Probabilistic Traveling Salesman Problem. In: Moreno-Díaz, R., Pichler, F., Quesada-Arencibia, A. (eds) Computer Aided Systems Theory - EUROCAST 2009. EUROCAST 2009. Lecture Notes in Computer Science, vol 5717. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04772-5_88
Download citation
DOI: https://doi.org/10.1007/978-3-642-04772-5_88
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04771-8
Online ISBN: 978-3-642-04772-5
eBook Packages: Computer ScienceComputer Science (R0)