Abstract
The traveling salesman problem with time windows is known to be a really difficult benchmark for optimization algorithms. In this paper, we are interested in the minimization of the travel cost. To solve this problem, we propose to use the nested Monte-Carlo algorithm combined with a Self-Adaptation Evolution Strategy. We compare the efficiency of several fitness functions. We show that with our technique we can reach the state of the art solutions for a lot of problems in a short period of time.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Baker, E.: An exact algorithm for the time-constrained traveling salesman problem. Operations Research 31(5), 938–945 (1983)
Beyer, H.-G.: The Theory of Evolution Strategies. Natural Computing Series. Springer, Heidelberg (2001)
Beyer, H.-G., Sendhoff, B.: Covariance matrix adaptation revisited - the CMSA evolution strategy. In: Rudolph, G., Jansen, T., Lucas, S.M., Poloni, C., Beume, N. (eds.) Proceedings of PPSN, pp. 123–132 (2008)
Cazenave, T.: Nested Monte-Carlo search. In: IJCAI, pp. 456–461 (2009)
Christofides, N., Mingozzi, A., Toth, P.: State-space relaxation procedures for the computation of bounds to routing problems. Networks 11(2), 145–164 (1981)
Dumas, Y., Desrosiers, J., Gelinas, E., Solomon, M.: An optimal algorithm for the traveling salesman problem with time windows. Operations Research 43(2), 367–371 (1995)
Focacci, F., Lodi, A., Milano, M.: A hybrid exact algorithm for the TSPTW. INFORMS Journal on Computing 14(4), 403–417 (2002)
Gendreau, M., Hertz, A., Laporte, G., Stan, M.: A generalized insertion heuristic for the traveling salesman problem with time windows. Operations Research 46(3), 330–335 (1998)
López-Ibáñez, M., Blum, C.: Beam-ACO for the travelling salesman problem with time windows. Computers & OR 37(9), 1570–1583 (2010)
Pesant, G., Gendreau, M., Potvin, J., Rousseau, J.: An exact constraint logic programming algorithm for the traveling salesman problem with time windows. Transportation Science 32(1), 12–29 (1998)
Potvin, J., Bengio, S.: The vehicle routing problem with time windows part II: genetic search. INFORMS Journal on Computing 8(2), 165 (1996)
Rechenberg, I.: Evolutionstrategie: Optimierung Technischer Systeme nach Prinzipien der Biologischen Evolution. Fromman-Holzboog Verlag, Stuttgart (1973)
Savelsbergh, M.: Local search in routing problems with time windows. Annals of Operations Research 4(1), 285–305 (1985)
Schwefel, H.-P.: Adaptive Mechanismen in der biologischen Evolution und ihr Einfluss auf die Evolutionsgeschwindigkeit. Interner Bericht der Arbeitsgruppe Bionik und Evolutionstechnik am Institut für Mess- und Regelungstechnik Re 215/3, Technische Universität Berlin, Juli (1974)
Solomon, M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research 35(2), 254–265 (1987)
Teytaud, F.: A new selection ratio for large population sizes. In: Applications of Evolutionary Computation, pp. 452–460 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rimmel, A., Teytaud, F., Cazenave, T. (2011). Optimization of the Nested Monte-Carlo Algorithm on the Traveling Salesman Problem with Time Windows. In: Di Chio, C., et al. Applications of Evolutionary Computation. EvoApplications 2011. Lecture Notes in Computer Science, vol 6625. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20520-0_51
Download citation
DOI: https://doi.org/10.1007/978-3-642-20520-0_51
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-20519-4
Online ISBN: 978-3-642-20520-0
eBook Packages: Computer ScienceComputer Science (R0)