Ir al contenido

Documat

Iterated local search, iterated greedy and applications

  • Helena Ramalhinho [1] ; Thomas Stützle [2] Árbol académico
    1. [1] Universitat Pompeu Fabra

      Universitat Pompeu Fabra

      Barcelona, España

    2. [2] Université Libre de Bruxelles

      Université Libre de Bruxelles

      Arrondissement Brussel-Hoofdstad, Bélgica

  • Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 33, Nº. Extra 2, 2025 (Ejemplar dedicado a: Metaheuristics), págs. 229-261
  • Idioma: inglés
  • DOI: 10.1007/s11750-025-00699-x
  • Enlaces
  • Resumen

    • Iterated local search and iterated greedy are two stochastic local search methods. The first one iterates through perturbation phases and local searches, while the second one iterates through destruction/construction phases and optionally through local searches. The destruction/construction phase in iterated greedy can be consider as a perturbation in iterated local search that leads to many commonalities between these two methods. However, iterated greedy can function without the local search phase. In this article, we review the two methods and detail their main principles. After some experiments with these methods on the permutation flow-shop problem, we review recent applications where these two methods have been successfully employed. We then delve into the historical development of these approaches, which reveals that many methods with different names have been proposed, but they ultimately align with one of these two approaches.

  • Referencias bibliográficas
    • Adriaensen S, Brys T, Nowé A (2014) Fair-share ILS: a simple state-of-the-art iterated local search hyperheuristic. In: Arnold DV (ed) Genetic...
    • Aguiar Santos VL, Mota Carvalho TF, Pereira de Assis L et al (2022) Multi-objective iterated local search based on decomposition for job scheduling...
    • Ahmadi S, Osman IH (2004) Density based problem space search for the capacitated clustering p-median problem. Ann Oper Res 131:21–43
    • Ahuja RK, Ergun O, Orlin JB et al (2002) A survey of very large-scale neighborhood search techniques. Discret Appl Math 123(1–3):75–102
    • Applegate D, Bixby RE, Chvátal V et al (1995) Finding cuts in the TSP. Technical report 95-05, DIMACS Center, Rutgers University, Piscataway,...
    • Applegate D, Bixby RE, Chvátal V et al (1999) Finding tours in the TSP. Technical report 99885, Forschungsinstitut für Diskrete Mathematik,...
    • Applegate D, Cook WJ, Rohe A (2003) Chained Lin–Kernighan for large traveling salesman problems. INFORMS J Comput 15(1):82–92. https://doi.org/10.1287/ijoc.15.1.82.15157
    • Archetti C, Feillet D, Mor A et al (2018) An iterated local search for the traveling salesman problem with release dates and completion time...
    • Arroyo J, Leung J, Tavares RG (2019) An iterated greedy algorithm for total flow time minimization in unrelated parallel batch machines with...
    • Bäck T, Fogel DB, Michalewicz Z (1997) Handbook of evolutionary computation. IOP Publishing, Bristol
    • Balas E, Ho A (1980) Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study. Math Progr...
    • Bao H, Pan Q, Ruiz R et al (2023) A collaborative iterated greedy algorithm with reinforcement learning for energy-aware distributed blocking...
    • Battiti R, Brunato M, Mascia F (2009) Reactive search and intelligent optimization, operations research/-computer science interfaces, vol...
    • Baum EB (1986a) Iterated descent: a better algorithm for local search in combinatorial optimization problems, manuscript
    • Baum EB (1986b) Towards practical “neural” computation for combinatorial optimization problems. In: Neural networks for computing, AIP conference...
    • Baxter J (1981) Local optima avoidance in depot location. J Oper Res Soc 32(9):815–819
    • Benavides AJ, Ritt M (2018) Fast heuristics for minimizing the makespan in non-permutation flow shops. Comput Oper Res 100:230–243
    • Bentley JL (1992) Fast algorithms for geometric traveling salesman problems. ORSA J Comput 4(4):387–411
    • Bergsten Mendes A, Pereira e Alvelos F, (2023) Iterated local search for the placement of wildland fire suppression resources. Eur J Oper...
    • Bertsekas DP, Tsitsiklis JN, Wu C (1997) Rollout algorithms for combinatorial optimization. J Heuristics 3(3):245–262
    • Bouamama S, Blum C, Pinacho-Davidson P (2022) A population-based iterated greedy algorithm for maximizing sensor network lifetime. Sensors...
    • Brandão J (2018) Iterated local search algorithm with ejection chains for the open vehicle routing problem with time windows. Comput Ind Eng...
    • Brandão J (2020) A memory-based iterated local search algorithm for the multi-depot open vehicle routing problem. Eur J Oper Res 284:559–571
    • Brimberg J, Hansen P, Mladenović N et al (2000) Improvements and comparison of heuristics for solving the multisource Weber problem. Oper...
    • Brucker P, Hurink J, Werner F (1996) Improving local search heuristics for some scheduling problems—part I. Discret Appl Math 65(1–3):97–122
    • Brucker P, Hurink J, Werner F (1997) Improving local search heuristics for some scheduling problems—part II. Discret Appl Math 72(1–2):47–69
    • Brum A, Ruiz R, Ritt M (2022) Automatic generation of iterated greedy algorithms for the non-permutation flow shop scheduling problem with...
    • Brusco MJ, Jacobs LW, Thompson GM (1999a) A morphing procedure to supplement a simulated annealing heuristic for cost- and coverage-correlated...
    • Brusco MJ, Jacobs LW, Thompson GM (1999b) A morphing procedure to supplement a simulated annealing heuristic for cost- and coverage-correlated...
    • Burke EK, Gendreau M, Hyde MR et al (2013) Hyper-heuristics: a survey of the state of the art. J Oper Res Soc 64(12):1695–1724
    • Calmels D (2022) An iterated local search procedure for the job sequencing and tool switching problem with non-identical parallel machines....
    • Casado A, Bermudo S, López-Sánchez AD et al (2023) An iterated greedy algorithm for finding the minimum dominating set in graphs. Math Comput...
    • Cerný V (1985) A thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. J Optim Theory Appl 45(1):41–51
    • Cesta A, Oddi A, Smith SF (2000) Iterative flattening: a scalable method for solving multi-capacity scheduling problems. In: Kautz HA, Porter...
    • Codenotti B, Manzini G, Margara L et al (1996) Perturbation: an efficient technique for the solution of very large instances of the Euclidean...
    • Congram RK, Potts CN, van de Velde S (2002) An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem....
    • Contreras-Bolton C, Parada V (2021) An effective two-level solution approach for the prize-collecting generalized minimum spanning tree problem...
    • Culberson JC (1992) Iterated greedy graph coloring and the difficulty landscape. Technical report 92-07, Department of Computing Science,...
    • Dao SD, Mallágol A, Meyer P et al (2022) A hybrid iterated greedy algorithm for hydrographic survey routing problem. Mar Geod 45(1):75–100
    • Deb K, Pratap A, Agarwal S et al (2002) A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197....
    • Dees WA Jr, Karger PG (1982) Automated rip-up and reroute techniques. In: DAC’82, Proceedings of the 19th design automation workshop. IEEE...
    • Delgado-Antequera L, Caballero R, Sánchez-Oro J et al (2020) Iterated greedy with variable neighborhood search for a multiobjective waste...
    • Dell’Amico M, Diaz JC, Hasle G et al (2016) An adaptive iterated local search for the mixed capacitated general routing problem. Transp Sci...
    • Demir Y (2024) An iterated greedy algorithm for the planning of yarn-dyeing boilers. Int Trans Oper Res 31:115–139
    • den Besten ML, Stützle T, Dorigo M (2001) Design of iterated local search algorithms: an example application to the single machine total weighted...
    • Dorigo M, Stützle T (2004) Ant colony optimization. MIT Press, Cambridge
    • Dorigo M, Maniezzo V, Colorni A (1996) Ant system: optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybern Part B 26(1):29–41
    • Dubois-Lacoste J, Pagnozzi F, Stützle T (2017) An iterated greedy algorithm with optimization of partial solutions for the permutation flowshop...
    • Duin C, Voß S (1999) The pilot method: a strategy for heuristic repetition with application to the Steiner problem in graphs. Networks 34(3):181–191
    • Estrada-Moreno A, Savelsbergh M, Juan AA et al (2019) Biased-randomized iterated local search for a multiperiod vehicle routing problem with...
    • Feo TA, Resende M (1995) Greedy randomized adaptive search procedures. J Glob Optim 6(2):109–113
    • Fernandes Muritiba AE, Bonates TO, Oliveira Da Silva S et al (2021) Branch-and-cut and iterated local search for the weighted k-traveling...
    • Fernandez-Viagas V, Framiñán JM (2014) On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem. Comput...
    • Fernandez-Viagas V, Framinan JM (2019) A best-of-breed iterated greedy for the permutation flowshop scheduling problem with makespan objective....
    • Fernandez-Viagas V, Valente JM, Framinan JM (2018) Iterated-greedy-based algorithms with beam search initialization for the permutation flowshop...
    • Ferone D, Hatami S, González-Neira EM et al (2020) A biased-randomized iterated local search for the distributed assembly permutation flow-shop...
    • Glover F (1977) Heuristics for integer programming using surrogate constraints. Decis Sci 8:156–166
    • Glover F (1986) Future paths for integer programming and links to artificial intelligence. Comput Oper Res 13(5):533–549
    • Glover F (1989) Tabu search—part I. INFORMS J Comput 1(3):190–206. https://doi.org/10.1287/ijoc.1.3.190
    • Glover F, Kochenberger GA (1996) Critical event Tabu search for multidimensional knapsack problems. In: Osman IH, Kelly JP (eds) Metaheuristics:...
    • Glover F, Laguna M (1997) Tabu search. Kluwer Academic Publishers, Boston
    • Glover F, Kochenberger GA, Alidaee B (1998) Adaptive memory Tabu search for binary quadratic programs. Manage Sci 44(3):336–345
    • Glover FW (1996) Ejection chains, reference structures and alternating path methods for traveling salesman problems. Discret Appl Math 65(1–3):223–253
    • Grasas A, Juan AA, Ramalhinho Lourenço H (2017) SimILS: a simulation-based extension of the iterated local search metaheuristic for stochastic...
    • Han X, Han Y, Zhang B et al (2022) An effective iterative greedy algorithm for distributed blocking flowshop scheduling problem with balanced...
    • Han B, Pan QK, Gao L (2023) A cooperative iterated greedy algorithm for the serial distributed permutation flowshop scheduling problem. Int...
    • Hansen P, Mladenović N (2001) Variable neighborhood search: principles and applications. Eur J Oper Res 130(3):449–467
    • He P, Hao JK, Xia J (2014) Learning-guided iterated local search for the minmax multiple traveling salesman problem. Technical report
    • Helsgaun K (2000) An effective implementation of the Lin–Kernighan traveling salesman heuristic. Eur J Oper Res 126:106–130
    • Helsgaun K (2009) General k-opt submoves for the Lin–Kernighan TSP heuristic. Math Program Comput 1(2–3):119–163
    • Hong I, Kahng AB, Moon BR (1997) Improved large-step Markov chain variants for the symmetric TSP. J Heuristics 3(1):63–81
    • Hoos HH, Stützle T (2005) Stochastic local search—foundations and applications. Morgan Kaufmann Publishers, San Francisco
    • Jacobs LW, Brusco MJ (1995) A local search heuristic for large set-covering problems. Nav Res Logist 42(7):1129–1140
    • Johnson DS (1990) Local optimization and the traveling salesman problem. In: Paterson M (ed) Automata, languages and programming, 17th international...
    • Johnson DS, McGeoch LA (1997) The traveling salesman problem: a case study in local optimization. In: Aarts E, Lenstra JK (eds) Local search...
    • Johnson DS, McGeoch LA (2002) Experimental analysis of heuristics for the STSP. In: Gutin G, Punnen A (eds) The traveling salesman problem...
    • Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671–680
    • Kreipl S (2000) A large step random walk for minimizing total weighted tardiness in a job shop. J Sched 3(3):125–138
    • Lawler EL, Lenstra JK, Rinnooy Kan A et al (1985) The traveling salesman problem. Wiley, Chichester
    • Lin S, Kernighan BW (1973) An effective heuristic algorithm for the traveling salesman problem. Oper Res 21(2):498–516
    • Liu F, Li G, Lu C et al (2024) A tri-individual iterated greedy algorithm for the distributed hybrid flow shop with blocking. Expert Syst...
    • Londoño JC, Tordecilla RD, do C. Martins L et al (2021) A biased-randomized iterated local search for the vehicle routing problem with optional...
    • López-Ibáñez M, Dubois-Lacoste J, Pérez Cáceres L et al (2016) The irace package: iterated racing for automatic algorithm configuration. Oper...
    • Lourenço HR (1995) Job-shop scheduling: computational study of local search and large-step optimization methods. Eur J Oper Res 83(2):347–364
    • Lourenço HR, Martin O, Stützle T (2002) Iterated local search. In: Glover F, Kochenberger G (eds) Handbook of metaheuristics. Kluwer Academic...
    • Lourenço HR, Martin O, Stützle T (2019) Iterated local search: framework and applications. In: Gendreau M, Potvin JY (eds) Handbook of metaheuristics....
    • Lozano M, Glover F, García-Martínez C et al (2014) Tabu search with strategic oscillation for the quadratic minimum spanning tree. IIE Trans...
    • Lu Y, Tang Q, Pan Q et al (2023) A heuristic-based adaptive iterated greedy algorithm for lot-streaming hybrid flow shop scheduling problem...
    • Ma Z, Wu G, Suganthan PN et al (2022) Performance assessment and exhaustive listing of 500+ nature-inspired metaheuristic algorithms....
    • Marchiori E, Steenbeek AG (1998) An iterated heuristic algorithm for the set covering problem. In: Mehlhorn K (ed) Algorithm engineering,...
    • Marchiori E, Steenbeek AG (2000) An evolutionary algorithm for large scale set covering problems with application to airline crew scheduling....
    • Marmion ME, Mascia F, López-Ibáñez M et al (2013) Automatic design of hybrid stochastic local search algorithms. In: Blesa MJ, Blum C, Festa...
    • Martin O, Otto SW (1995) Partitioning of unstructured meshes for load balancing. Concurr Pract Exp 7(4):303–314
    • Martin O, Otto SW (1996) Combining simulated annealing with local search heuristics. Ann Oper Res 63:57–75
    • Martin O, Otto SW, Felten EW (1991) Large-step Markov chains for the traveling salesman problem. Complex Syst 5(3):299–326
    • Martin O, Otto SW, Felten EW (1992) Large-step Markov chains for the TSP incorporating local search heuristics. Oper Res Lett 11(4):219–224
    • Martinho WC, Melo RA, Sörensen K (2021) An enhanced simulation-based iterated local search metaheuristic for gravity-fed water distribution...
    • Mascia F, López-Ibáñez M, Dubois-Lacoste J et al (2014) Algorithm comparison by automatically configurable stochastic local search frameworks:...
    • Máximo VR, Nascimento M (2021) A hybrid adaptive iterated local search with diversification control to the capacitated vehicle routing problem....
    • Máximo VR, Cordeau JF, Nascimento M (2022) An adaptive iterated local search heuristic for the heterogeneous fleet vehicle routing problem....
    • Mecler D, Abu-Marrul V, Martinelli R et al (2022) Iterated greedy algorithms for a complex parallel machine scheduling problem. Eur J Oper...
    • Meignan D, Knust S (2019) A neutrality-based iterated local search for shift scheduling optimization and interactive reoptimization. Eur J...
    • Mendoze-Gómez R, Ríos-Mercado RZ, Valenzuela-Ocaña KB (2020) An iterated greedy algorithm with variable neighborhood descent for the planning...
    • Merz P, Huhse J (2008) An iterated local search approach for finding provably good solutions for very large TSP instances. In: Rudolph G et...
    • Michel LD, van Hentenryck P (2004) Iterative relaxations for iterative flattening in cumulative scheduling. In: Zilberstein S, Koehler J,...
    • Missaoui A, Ruiz R (2022) A parameter-less iterated greedy method for the hybrid flowshop scheduling problem with setup times and due date...
    • Moscato P (1989) On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms. Caltech Concurrent Computation...
    • Mühlenbein H (1991) Evolution in time and space—the parallel genetic algorithm. In: Rawlins G (ed) Foundations of Genetic Algorithms (FOGA)....
    • Nawaz M, Enscore EJ Jr, Ham I (1983) A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega 11(1):91–95
    • Nogueira B, Pinheiro R, Subramanian A (2018) A hybrid iterated local search heuristic for the maximum weight independent set problem. Optim...
    • Ochoa G, Burke EK (2014) HyperILS: an effective iterated local search hyper-heuristic for combinatorial optimisation. In: 10th International...
    • Oddi A, Cesta A, Policella N et al (2008) Combining variants of iterative flattening search. Eng Appl Artif Intell 21(5):683–690
    • Oddi A, Cesta A, Policella N et al (2010) Iterative flattening search for resource constrained scheduling. J Intell Manuf 21(1):17–30
    • Oddi A, Rasconi R, Cesta A et al (2011) Iterative flattening search for the flexible job shop scheduling problem. In: Walsh T (ed) Proceedings...
    • Osorio-Mora A, Willmer Escobar J, Toth P (2023) An iterated local search algorithm for latency vehicle routing problems with multiple depots....
    • Ozsoydan FB, Sağir M (2021) Iterated greedy algorithms enhanced by hyper-heuristic based learning for hybrid flexible flowshop scheduling...
    • Pagnozzi F, Stützle T (2019) Automatic design of hybrid stochastic local search algorithms for permutation flowshops problems. Eur J Oper...
    • Pagnozzi F, Stützle T (2021) Automatic design of hybrid stochastic local search algorithms for permutation flowshop problems with additional...
    • Pérez-Peló S, Sánchez-Oro J, López-Sánchez AD et al (2019) A multi-objective parallel iterated greedy for solving the p-center and p-dispersion...
    • Piotrowski AP, Napiorkowski JJ, Rowinski PM (2014) How novel is the “novel” black hole optimization approach? Inf Sci 267:191–200
    • Pisinger D, Ropke S (2010) Large neighborhood search. In: Gendreau M, Potvin JY (eds) Handbook of metaheuristics, International Series in...
    • Queiroga E, Pinheiro R, Christ Q et al (2021) Iterated local search for single machine total weighted tardiness batch scheduling. J Heuristics...
    • Riahi V, Chiong R, Zhang Y (2020) A new iterated greedy algorithm for no-idle permutation flowshop scheduling with the total tardiness criterion....
    • Richmond AJ, Beasley JE (2004) An iterative construction heuristic for the ore selection problem. J Heuristics 10(2):153–167
    • Rubin F (1974) An iterative technique for printed wire routing. In: DAC’74, Proceedings of the 11th Design Automation Workshop. IEEE Press,...
    • Ruiz R, Maroto C (2005) A comprehensive review and evaluation of permutation flowshop heuristics. Eur J Oper Res 165(2):479–494
    • Ruiz R, Stützle T (2007) A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur J Oper Res...
    • Sabar NR, Goh SL, Turky A et al (2022) Population-based iterated local search approach for dynamic vehicle routing problems. IEEE Trans Autom...
    • Schettini T, Gendreau M, Jabali O et al (2023) An iterated local search metaheuristic for the capacitated demand-driven timetabling problem....
    • Schmidt J, Irnich S (2022) New neighborhoods and an iterated local search algorithm for the generalized traveling salesman problem. EURO J...
    • Schrimpf G, Schneider J, Stamm-Wilbrandt H et al (2000) Record breaking optimization results using the ruin and recreate principle. J Comput...
    • Shaw P (1998) Using constraint programming and local search methods to solve vehicle routing problems. In: Maher M, Puget JF (eds) Principles...
    • Siqueira de Almeida F, Seido Nagano M (2023) An efficient iterated greedy algorithm for a multi-objective no-wait flow shop problem with sequence...
    • Stützle T (1998) Applying iterated local search to the permutation flow shop problem. Technical report AIDA-98-04, FG Intellektik, FB Informatik,...
    • Stützle T, Hoos HH (2001) Analysing the run-time behaviour of iterated local search for the travelling salesman problem. In: Hansen P, Ribeiro...
    • Stützle T, Ruiz R (2018a) Iterated greedy. In: Martí R, Pardalos PM, Resende M (eds) Handbook of Heuristics. Springer International Publishing,...
    • Stützle T, Ruiz R (2018b) Iterated local search. In: Martí R, Pardalos PM, Resende M (eds) Handbook of Heuristics. Springer International...
    • Sun W, Li W, Hao JK et al (2023) Learning-based multi-start iterated local search for the profit maximization set covering problem. Inf Sci...
    • Sun W, Chen C, Hao JK et al (2024) A knowledge-based iterated local search for the weighted total domination problem. Inf Sci 665:120364
    • Taillard ÉD (1990) Some efficient heuristic methods for the flow shop sequencing problem. Eur J Oper Res 47(1):65–74
    • Taillard ÉD (1993) Benchmarks for basic scheduling problems. Eur J Oper Res 64(2):278–285
    • Villalon CC, Dorigo M, Stützle T (2023) Exposing the grey wolf, moth-flame, whale, firefly, bat, and antlion algorithms: six misleading optimization...
    • Wang Y, Li X, Ruiz R et al (2018) An iterated greedy heuristic for mixed no-wait flowshop problems. IEEE Trans Cybern 48(5):1553–1566
    • Wang X, Wang S, Wang L et al (2020) An effective iterated greedy algorithm for online route planning problem. In: 2020 IEEE Congress on Evolutionary...
    • Wang Y, Wang Y, Han Y (2023) A variant iterated greedy algorithm integrating multiple decoding rules for hybrid blocking flow shop scheduling...
    • Watkins C (1989) Learning from delayed rewards. Ph.D. thesis, University of Cambridge
    • Watkins C, Dayan P (1992) Q-Learning. Mach Learn 8(3–4):279–292
    • Weyland D (2010) A rigorous analysis of the harmony search algorithm: How the research community can be misled by a “novel” methodology. Int...
    • Xie F, Potts CN, Bektaş T (2017) Iterated local search for workforce scheduling and routing problems. J Heuristics 23:471–500
    • Zhang Q, Li H (2007) MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput 11(6):712–731. https://doi.org/10.1109/TEVC.2007.892759
    • Zheng J, Wang L, Wang L et al (2023) Solving stochastic online food delivery problem via iterated greedy algorithm with decomposition-based...
    • Zitzler E, Laumanns M, Thiele L (2002) SPEA2: improving the strength Pareto evolutionary algorithm for multiobjective optimization. In: Giannakoglou...
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno