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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview 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)