{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T08:00:49Z","timestamp":1761897649938,"version":"build-2065373602"},"reference-count":52,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2021,12,24]],"date-time":"2021-12-24T00:00:00Z","timestamp":1640304000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Hyper-heuristics comprise a set of approaches that are motivated (at least in part) by the objective of intelligently combining heuristic methods to solve hard optimization problems. Ant colony optimization (ACO) algorithms have been proven to deal with Dynamic Optimization Problems (DOPs) properly. Despite the good results obtained by the integration of local search operators with ACO, little has been done to tackle DOPs. In this research, one of the most reliable ACO schemes, the MAX-MIN Ant System (MMAS), has been integrated with advanced and effective local search operators, resulting in an innovative hyper-heuristic. The local search operators are the Lin\u2013Kernighan (LK) and the Unstringing and Stringing (US) heuristics, and they were intelligently chosen to improve the solution obtained by ACO. The proposed method aims to combine the adaptation capabilities of ACO for DOPs and the good performance of the local search operators chosen in an adaptive way and based on their performance, creating in this way a hyper-heuristic. The travelling salesman problem (TSP) was the base problem to generate both symmetric and asymmetric dynamic test cases. Experiments have shown that the MMAS provides good initial solutions to the local search operators and the hyper-heuristic creates a robust and effective method for the vast majority of test cases.<\/jats:p>","DOI":"10.3390\/a15010009","type":"journal-article","created":{"date-parts":[[2021,12,27]],"date-time":"2021-12-27T01:00:54Z","timestamp":1640566854000},"page":"9","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Hyper-Heuristic Based on ACO and Local Search for Dynamic Optimization Problems"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0062-5863","authenticated-orcid":false,"given":"Felipe Martins","family":"M\u00fcller","sequence":"first","affiliation":[{"name":"Department of Applied Computing, Federal University of Santa Maria, Santa Maria 97105-900, Brazil"}]},{"given":"Ia\u00ea Santos","family":"Bonilha","sequence":"additional","affiliation":[{"name":"PPGEP, Federal University of Santa Maria, Santa Maria 97105-900, Brazil"}]}],"member":"1968","published-online":{"date-parts":[[2021,12,24]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Gendreau, M., and Potvin, J.-Y. (2010). A classification of hyper-heuristic approaches. Handbookof Metaheuristics, Springer.","DOI":"10.1007\/978-1-4419-1665-5"},{"key":"ref_2","first-page":"463","article-title":"A Survey of hyper-heuristics for dynamic optimization problems","volume":"Volume 862","author":"Castillo","year":"2020","journal-title":"Intuitionistic and Type-2 Fuzzy Logic Enhancements in Neural and Optimization Algorithms: Theory and Applications"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Dorigo, M., and St\u00fctzle, T. (2004). Ant Colony Optimization, MIT Press.","DOI":"10.7551\/mitpress\/1290.001.0001"},{"key":"ref_4","unstructured":"Applegate, D.L., Bixby, R.E., Chvatal, V., and Cook, W.J. (2007). The Traveling Salesman Problem: A Computational Study, Princeton University Press."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1109\/TEVC.2005.846356","article-title":"Evolutionary optimization in uncertain environments\u2014A survey","volume":"9","author":"Jin","year":"2005","journal-title":"IEEE Trans. Evol. Comput."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1016\/j.ijpe.2016.08.032","article-title":"An enhanced sample average approximation method for stochastic optimization","volume":"182","author":"Emelogu","year":"2016","journal-title":"Int. J. Prod. Econ."},{"key":"ref_7","unstructured":"Hart, E., and Ross, P. (1999, January 13\u201317). An immune system approach to scheduling in changing environments. Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation, Orlando, FL, USA."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Mavrovouniotis, M., Bonilha, I.S., M\u00fcller, F.M., Ellinas, G., and Polycarpou, M. (2019, January 10\u201313). Effective ACO-Based Memetic Algorithms for Symmetric and Asymmetric Dynamic Changes. Proceedings of the IEEE Congress on Evolutionary Computation (CEC), Wellington, New Zealand.","DOI":"10.1109\/CEC.2019.8790025"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Mavrovouniotis, M., M\u00fcller, F.M., and Yang, S. (2015, January 11\u201315). An ant colony optimization based memetic algorithm for the dynamic travelling salesman problem. Proceedings of the Conference on Genetic and Evolutionary Computation Conference (GECCO2015), Madrid, Spain.","DOI":"10.1145\/2739480.2754651"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1743","DOI":"10.1109\/TCYB.2016.2556742","article-title":"Ant colony optimization with local search for the dynamic travelling salesman problems","volume":"47","author":"Mavrovouniotis","year":"2017","journal-title":"IEEE Trans. Cybern."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"4023","DOI":"10.1016\/j.asoc.2013.05.022","article-title":"Ant colony optimization with immigrants schemes for the dynamic travelling salesman problem with traffic factors","volume":"13","author":"Mavrovouniotis","year":"2013","journal-title":"Appl. Soft Comput."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1405","DOI":"10.1007\/s00500-010-0680-1","article-title":"A memetic ant colony optimization algorithm for the dynamic travelling salesman problem","volume":"15","author":"Mavrovouniotis","year":"2011","journal-title":"Soft Comput."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/j.trb.2016.01.005","article-title":"Ant colony optimization for the real-time train routing selection problem","volume":"85","author":"Sama","year":"2016","journal-title":"Trans. Res. Part B Methodol."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Cheng, H., and Yang, S. (2011, January 11\u201315). Genetic algorithms with elitism-based immigrants for dynamic load balanced clustering problem in mobile ad hoc networks. Proceedings of the 2011 IEEE Symposium on Computational Intelligence in Dynamic and Uncertain Environments (CIDUE), Paris, France.","DOI":"10.1109\/CIDUE.2011.5948486"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"806","DOI":"10.1016\/j.engappai.2010.01.021","article-title":"Genetic algorithms with immigrants schemes for dynamic multicast problems in mobile ad hoc networks","volume":"23","author":"Cheng","year":"2010","journal-title":"Eng. Appl. Artif. Intell."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Cheng, H., and Yang, S. (2010, January 7\u20139). Multi-population genetic algorithms with immigrants scheme for dynamic shortest path routing problems in mobile ad hoc networks. Proceedings of the European Conference on the Applications of Evolutionary Computation, Istanbul, Turkey.","DOI":"10.1007\/978-3-642-12239-2_58"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"3096","DOI":"10.1016\/j.ins.2008.01.020","article-title":"Multi-strategy ensemble particle swarm optimization for dynamic optimization","volume":"178","author":"Du","year":"2010","journal-title":"Inf. Sci."},{"key":"ref_18","first-page":"295","article-title":"Combinatorial particle swarm optimization for solving blocking flowshop scheduling problem","volume":"3","author":"Eddaly","year":"2016","journal-title":"J. Comput. Des. Eng."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1080\/03052150500340504","article-title":"Rank-based ant colony optimization applied to dynamic traveling salesman problems","volume":"37","author":"Liu","year":"2005","journal-title":"Eng. Optim."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Guntsch, M., and Middendorf, M. (2001, January 18\u201320). Pheromone modification strategies for ant algorithms applied to dynamic TSP. Proceedings of the Workshops on Applications of Evolutionary Computation, Como, Italy.","DOI":"10.1007\/3-540-45365-2_22"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Eyckelhof, C.J., and Snoek, M. (2002, January 12\u201314). Ant systems for a dynamic TSP. Proceedings of the International Workshop on Ant Algorithms, Brussels, Belgium.","DOI":"10.1007\/3-540-45724-0_8"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Mavrovouniotis, M., Yang, S., and Yao, X. (2014, January 9\u201312). Multi-colony ant algorithms for the dynamic travelling salesman problem. Proceedings of the IEEE Symposium on Computational Intelligence in Dynamic and Uncertain Environments, Orlando, FL, USA.","DOI":"10.1109\/CIDUE.2014.7007861"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Guntsch, M., and Middendorf, M. (2002, January 3\u20134). A population based approach for ACO. Proceedings of the Workshops on Applications of Evolutionary Computation, Kinsale, Ireland.","DOI":"10.1007\/3-540-46004-7_8"},{"key":"ref_24","first-page":"165","article-title":"Niching for ant colony optimisation","volume":"210","author":"Angus","year":"2009","journal-title":"Biol.-Inspired Optim. Methods"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Angus, D. (2006, January 4\u20136). Niching for population-based ant colony optimization. Proceedings of the Second IEEE international Conference on e-Science and Grid Computing, Amsterdam, The Netherlands.","DOI":"10.1109\/E-SCIENCE.2006.261199"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Mavrovouniotis, M., and Yang, S. (2011, January 27\u201329). Memory-based immigrants for ant colony optimization in changing environments. Proceedings of the European Conference on the Applications of Evolutionary Computation, Torino, Italy.","DOI":"10.1007\/978-3-642-20525-5_33"},{"key":"ref_27","first-page":"368","article-title":"A modified ant colony optimization algorithm to solve a dynamic traveling salesman problem: A case study with drones for wildlife surveillance","volume":"6","author":"Chowdhury","year":"2019","journal-title":"J. Comput. Des. Eng."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1109\/3477.484436","article-title":"Ant system: Optimization by a colony of cooperating agents","volume":"26","author":"Dorigo","year":"1996","journal-title":"IEEE Trans. Syst. Man Cybern. Part B Cybern."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"889","DOI":"10.1016\/S0167-739X(00)00043-1","article-title":"MAX\u2013MIN ant system","volume":"16","author":"Hoos","year":"2000","journal-title":"Future Gener. Comput. Syst."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BFb0029740","article-title":"Genetic local search algorithms for the traveling salesman problem","volume":"Volume 496","author":"Schwefel","year":"1991","journal-title":"Parallel Problem Solving from Nature"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Stodola, P., Michenka, K., Nohel, J., and Rybansk\u00fd, M. (2020). Hybrid Algorithm Based on Ant Colony Optimization and Simulated Annealing Applied to the Dynamic Traveling Salesman Problem. Entropy, 22.","DOI":"10.3390\/e22080884"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1086","DOI":"10.1287\/opre.40.6.1086","article-title":"New insertion and postoptimization procedures for the traveling salesman problem","volume":"40","author":"Gendreau","year":"1992","journal-title":"Oper. Res."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1287\/opre.21.2.498","article-title":"An effective heuristic algorithm for the traveling salesman problem","volume":"21","author":"Lin","year":"1973","journal-title":"Oper. Res."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/S0377-2217(99)00284-2","article-title":"An effective implementation of the Lin\u2013Kernighan traveling salesman heuristic","volume":"126","author":"Helsgaun","year":"2000","journal-title":"Eur. J. Oper. Res."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Mavrovouniotis, M., and Yang, S. (2010, January 11\u201315). Ant colony optimization with immigrants schemes in dynamic environments. Proceedings of the International Conference on Parallel Problem Solving from Nature, Krakov, Poland.","DOI":"10.1007\/978-3-642-15871-1_38"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1007\/978-3-642-37192-9_61","article-title":"Adapting the pheromone evaporation rate in dynamic routing problems","volume":"Volume 7835","year":"2013","journal-title":"Applications of Evolutionary Computation"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Tin\u00f3s, R., Whitley, D., and Howe, A. (2014, January 12\u201316). Use of explicit memory in the dynamic traveling salesman problem. Proceedings of the Conference on Genetic and Evolutionary Computation, Vancouver, BC, Canada.","DOI":"10.1145\/2576768.2598247"},{"key":"ref_38","first-page":"393","article-title":"Solution of a large-scale traveling-salesman problem","volume":"2","author":"Dantzig","year":"1954","journal-title":"J. Oper. Res. Soc. Am."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/s13676-012-0010-0","article-title":"Models and algorithms for the Asymmetric Traveling Salesman Problem: An experimental comparison","volume":"1","author":"Roberti","year":"2012","journal-title":"EURO J. Transp. Logist."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Mele, U.J., Gambardella, L.M., and Montemanni, R. (2021). A New Constructive Heuristic Driven by Machine Learning for the Traveling Salesman Problem. Algorithms, 14.","DOI":"10.3390\/a14090267"},{"key":"ref_41","unstructured":"St\u00fctzle, T., and Hoos, H. (1997, January 13\u201316). MAX\u2013MIN ant system and local search for the traveling salesman problem. Proceedings of the IEEE International Conference on Evolutionary Computation, Indianapolis, IN, USA."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0167-6377(83)90048-2","article-title":"Transforming asymmetric into symmetric traveling salesman problems","volume":"2","author":"Jonker","year":"1983","journal-title":"Oper. Res. Lett."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0925-5273(96)00031-X","article-title":"A tabu search heuristic for the multiprocessor scheduling problem with sequence dependent setup times","volume":"43","author":"Gendreau","year":"1996","journal-title":"Int. J. Prod. Econ."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.swevo.2016.12.005","article-title":"A survey of swarm intelligence for dynamic optimization: Algorithms and applications","volume":"33","author":"Mavrovouniotis","year":"2017","journal-title":"Swarm Evol. Comput."},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Gambardella, L.M., and Dorigo, M. (1995, January 9\u201312). Ant-Q: A reinforcement learning approach to the traveling salesman problem. Proceedings of the International Conference on Machine Learning, Tahoe City, CA, USA.","DOI":"10.1016\/B978-1-55860-377-6.50039-6"},{"key":"ref_46","first-page":"618","article-title":"Ant colony optimisation applied to a dynamically changing problem","volume":"Volume 2358","author":"Hendtlass","year":"2002","journal-title":"Developments in Applied Artificial Intelligence"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/3-540-45724-0_10","article-title":"Applying population based ACO to dynamic optimization problems","volume":"Volume 2463","author":"Dorigo","year":"2002","journal-title":"Ant Algorithms"},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Bonilha, I.S., Mavrovouniotis, M., M\u00fcller, F.M., Ellinas, G., and Polycarpou, M. (2020, January 1\u20134). Ant colony optimization with heuristic repair for the dynamic vehicle routing problem. Proceedings of the IEEE Symposium Series on Computational Intelligence (SSCI), Canberra, ACT, Australia.","DOI":"10.1109\/SSCI47803.2020.9308156"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1287\/trsc.6.2.149","article-title":"A Man-Machine Approach Toward Solving the Generalized Truck-Dispatching Problem","volume":"6","author":"Krolak","year":"1972","journal-title":"Transp. Sci."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/BF01415960","article-title":"Optimal control of plotting and drilling machines: A case study","volume":"35","author":"Reinelt","year":"1991","journal-title":"ZOR-Methods Models Oper. Res."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1287\/moor.11.4.537","article-title":"Clique Tree Inequalities and the Symmetric Travelling Salesman Problem","volume":"11","author":"Pulleyblank","year":"1986","journal-title":"Math. Oper. Res."},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Ghosh, A., and Tsutsui, S. (2003). Designing evolutionary algorithms for dynamic optimization problems. Advances in Evolutionary Computing, Springer.","DOI":"10.1007\/978-3-642-18965-4"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/1\/9\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:53:17Z","timestamp":1760169197000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/1\/9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,24]]},"references-count":52,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,1]]}},"alternative-id":["a15010009"],"URL":"https:\/\/doi.org\/10.3390\/a15010009","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,12,24]]}}}