Abstract
Late Acceptance Hill Climbing (LAHC) is a recent metaheuristic in the realm of local search based procedures. The basic idea is to delay the comparison between neighborhood solutions and to compare new candidate solutions to a solution having been current several steps ago. The LAHC was first presented at the PATAT 2008 conference and successfully tested for exam timetabling, the traveling salesman problem (TSP) and the magic square problem and the results seemed extraordinary. The purpose of this paper is to analyze the behavior of the method and to provide some extended understanding about its success and limitations. To do so, we investigate the method for a generalized version of the TSP, the traveling purchaser problem.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Abuhamdah, A.: Experimental result of late acceptance randomized descent algorithm for solving course timetabling problems. International Journal of Computer Science and Network Security 10(1), 192–200 (2010)
Angelelli, E., Mansini, R., Vindigni, M.: Look-ahead heuristics for the dynamic traveling purchaser problem. Computers & Operations Research 38, 1867–1876 (2011)
Bellmore, M., Nemhauser, G.L.: The traveling salesman problem: A survey. Operations Research 16, 538–558 (1968)
Boctor, F., Laporte, G., Renaud, J.: Heuristics for the traveling purchaser problem. Computers & Operations Research 30, 491–504 (2003)
Burke, E.K., Bykov, Y.: A late acceptance strategy in hill-climbing for exam timetabling problems. In: Proceedings of the 7th Int. Conf. on the Practice and Theory of Automated Timetabling, PATAT 2008 (2008)
Cambazard, H., Penz, B.: A constraint programming approach for the traveling purchaser problem. In: Milano, M. (ed.) CP 2012. LNCS, vol. 7514, pp. 735–749. Springer, Heidelberg (2012)
Goldbarg, M.C., Bagi, L.B., Goldbarg, E.F.G.: Transgenetic algorithm for the traveling purchaser problem. European Journal of Operational Research 199, 36–45 (2009)
Golden, B., Levy, L., Dahl, R.: Two generalizations of the traveling salesman problem. Omega 9, 439–441 (1981)
Gouveia, L., Paias, A., Voß, S.: Models for a traveling purchaser problem with additional side-constraints. Computers & Operations Research 38, 550–558 (2011)
Infante, D., Paletta, G., Vocaturo, F.: A ship-truck intermodal transportation problem. Maritime Economics & Logistics 11, 247–259 (2009)
Karg, R.L., Thompson, G.L.: A heuristic approach to solving travelling salesman problems. Management Science 10, 225–248 (1964)
Laporte, G., Riera-Ledesma, J., Salazar-González, J.: A branch-and-cut algorithm for the undirected traveling purchaser problem. Operations Research 51, 940–951 (2003)
Ong, H.L.: Approximate algorithms for the travelling purchaser problem. Operations Research Letters 1, 201–205 (1982)
Özcan, E., Bykov, Y., Birben, M., Burke, E.K.: Examination timetabling using late acceptance hyper-heuristics. In: IEEE Congress on Evolutionary Computation, CEC 2009, pp. 997–1004 (2009)
Ramesh, T.: Traveling purchaser problem. Opsearch 18, 78–91 (1981)
Riera-Ledesma, J., Salazar-González, J.: A heuristic approach for the travelling purchaser problem. European Journal of Operational Research 162, 142–152 (2005)
Riera-Ledesma, J., Salazar-González, J.: Solving the asymmetric traveling purchaser problem. Annals of Operations Research 144, 83–97 (2006)
Singh, K.N., van Oudheusden, D.L.: A branch and bound algorithm for the traveling purchaser problem. European Journal of Operational Research 97, 571–579 (1997)
Teeninga, A., Volgenant, A.: Improved heuristics for the traveling purchaser problem. Computers & Operations Research 31, 139–150 (2004)
Verstichel, J., Berghe, G.: A late acceptance algorithm for the lock scheduling problem. In: Voß, S., Pahl, J., Schwarze, S. (eds.) Logistik Management, pp. 457–478. Physica, Heidelberg (2009)
Voß, S.: Dynamic tabu search strategies for the traveling purchaser problem. Annals of Operations Research 63, 253–275 (1996)
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Goerler, A., Schulte, F., Voß, S. (2013). An Application of Late Acceptance Hill-Climbing to the Traveling Purchaser Problem. In: Pacino, D., Voß, S., Jensen, R.M. (eds) Computational Logistics. ICCL 2013. Lecture Notes in Computer Science, vol 8197. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41019-2_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-41019-2_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41018-5
Online ISBN: 978-3-642-41019-2
eBook Packages: Computer ScienceComputer Science (R0)