nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

6. Very Large-Scale Neighborhood Search

verfasst von : Vittorio Maniezzo, Marco Antonio Boschetti, Thomas Stützle

Erschienen in: Matheuristics

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Very Large-Scale Neighborhood Search is not an algorithm or a class of algorithms, but rather a conceptual framework which can be used for solving combinatorial optimization problems. The approach “concentrates on neighborhood search algorithms where the size of the neighborhood is ‘very large’ with respect to the size of the input data.” Typically, the searched neighborhoods are exponentially large, but the term has come to be used more generally to describe algorithms working on neighborhoods that are too large to explicitly search in practice. The search of the large neighborhood has often been made by dedicated mathematical programming modules, deriving from different techniques. This chapter reports on the rich literature following this approach and proposes a possible implementation for the GAP.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Diving Heuristics

Nächstes Kapitel Decomposition-Based Heuristics

Ahuja RK, Magnanti TL, Orlin J (1993) Network flows: Theory, algorithms, and applications. Prentice-Hall, Upper Saddle River, NJ, USA

Ahuja RK, Orlin JB, Sharma D (1999) New neighborhood search structures for the capacitated minimum spanning tree problem. Technical Report 99-2, Department of Industrial and Systems Engineering, University of Florida

Ahuja RK, Orlin JB, Sharma D (2000) Very large-scale neighborhood search. Int Trans Oper Res 7(4-5):301–317CrossRef

Ahuja RK, Ergun O, Orlin JB, Punnen APA (2002) Survey of very large-scale neighborhood search techniques. Discrete Appl Math 123:75–102CrossRef

Ahuja RK, Orlin JB, Pallottino S, Scaparra MP, Scutella MG (2004) A multi-exchange heuristic for the single source capacitated facility location. Management Science 50:749–760CrossRef

Ahuja RK, Ergun O, Orlin JB, Punnen AP (2007) Very large-scale neighborhood search. In: Gonzalez TF (ed) Approximation algorithms and metaheuristics. Chapman & Hall, pp 20–1–20–12

Altner DS (2017) Very large-scale neighborhood search. In: Handbook of discrete and combinatorial mathematics. Chapman and Hall/CRC

Altner DS, Ahuja RK, Ergun O, Orlin JB (2014) Very large-scale neighborhood search. In: Burke E, Kendall G (eds) Search methodologies. Springer, Boston, MA

Brueggemann T, Hurink JL (2007) Two exponential neighborhoods for single machine scheduling. OR Spectrum 29:513–533CrossRef

Brueggemann T, Hurink JL (2011) Matching based very large-scale neighborhoods for parallel machine scheduling. J Heuristics 17(6):637–658CrossRef

Chiarandini M, Dumitrescu I, Stützle T (2008) Very large-scale neighborhood search: Overview and case studies on coloring problems. In: Blum C, Blesa MJ, Roli A, Sampels M (eds) Hybrid metaheuristics, vol. 114. Studies in computational intelligence. Springer, pp 117–150

Congram RK (2000) Polynomially searchable exponential neighbourhoods for sequencing problems in combinatorial optimization. Ph.D. thesis, Southampton University, Faculty of Mathematical Studies, Southampton, UK

Congram RK, Potts CN, van de Velde S (2002) An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem. INFORMS J Comput 14(1):52–67CrossRef

Copado-Méndez P, Blum C, Guillén-Gosálbez G, Jiménez L (2013) Large neighbourhood search applied to the efficient solution of spatially explicit strategic supply chain management problems. Comput Chem Eng 49:114–126CrossRef

Cunha CB, Ahuja RK (2005) Very large scale neighborhood search for the k-constrained multiple knapsack problem. J Heuristics 11:465–481CrossRef

De Franceschi R, Fischetti M, Toth P (2006) A new ILP-based refinement heuristic for vehicle routing problems. Mathematical Programming 105(2-3):471–499CrossRef

Dror M, Levy L (1986) A vehicle routing improvement algorithm comparison of a “greedy” and a “matching” implementation for inventory routing. Comput Oper Res 13:33–45CrossRef

Ergun O, Orlin JB, Steele-Feldman A (2006) Creating very large scale neighborhoods out of smaller ones by compounding moves. J Heuristics 12(1-2):115–140CrossRef

Fischetti M, Lodi A, Salvagnin D (2009) Just MIP it! In: Maniezzo V, Stützle T, Voß S (eds) Matheuristics: Hybridizing metaheuristics and mathematical programming. Annals of information systems, vol 10. Springer, pp 39–70

Frangioni A, Necciari E, Scutellá MG (2004) A multi-exchange neighborhood for minimum makespan parallel machine scheduling problems. J Comb Optim 8(2):195–220CrossRef

Gendreau M, Guertin F, Potvin JY, Seguin R (2006) Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries. Transp Res C Emerg Technol 14:157–174CrossRef

Hewitt M, Nemhauser GL, Savelsbergh MWP (2010) Combining exact and heuristic approaches for the capacitated fixed-charge network flow problem. INFORMS J Comput 22(2):314–325CrossRef

Lin S, Kernighan B (1973) An effective heuristic algorithm for the traveling salesman problem. Operations Research 21:498–516CrossRef

Meyers C, Orlin JB (2006) Very large-scale neighborhood search techniques in timetabling problems. In: Burke EK, Rudová H (eds) Proceedings of the 6th international conference on practice and theory of automated timetabling VI (PATAT’06). Springer, Berlin, Heidelberg, pp 24–39

Mitrović-Minić S, Punnen AP (2008) Very large-scale variable neighborhood search for the generalized assignment problem. J Interdisciplinary Math 11(5):653–670CrossRef

Mitrović-Minić S, Punnen AP (2009) Variable intensity local search. In: Maniezzo V, Stützle T, Voß S (eds) Matheuristics: Hybridizing metaheuristics and mathematical programming. Annals of information systems, vol 10. Springer US, Boston, MA, pp 245–252

Nishi T, Okura T, Lalla-Ruiz E, Voß S (2020) A dynamic programming-based matheuristic for the dynamic berth allocation problem. Ann Oper Res 286:391–410CrossRef

Pisinger D, Ropke S (2010) Large neighborhood search. In: Gendreau M, Potvin J (eds) Handbook of metaheuristics. International series in operations research & management science, vol 146. Springer, Boston, MA, pp 399–419CrossRef

Roli A, Benedettini S, Stützle T, Blum C (2012) Large neighbourhood search algorithms for the founder sequence reconstruction problem. Comput Oper Res 39:213–224CrossRef

Ropke S, Pisinger D (2006) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science 40(4):455–472CrossRef

Salari M, Toth P, Tramontani A (2010) An ILP improvement procedure for the open vehicle routing problem. Comput Oper Res 37(12):2106–2120CrossRef

Sarvanov VI, Doroshko NN (1981) Approximate solution of the traveling salesman problem by a local algorithm with scanning neighborhoods of factorial cardinality in cubic time. Software: Algorithms and Programs, Mathematics Institute of the Belorussia Academy of Science, Minsk, vol 31, pp 11–13

Schmid V, Doerner KF, Hartl RF, Salazar-González JJ (2010) Hybridization of very large neighborhood search for ready-mixed concrete delivery problems. Comput Oper Res 37(3):559–574CrossRef

Shaw P (1998) Using constraint programming and local search methods to solve vehicle routing problems. In: CP-98 (Fourth international conference on principles and practice of constraint programming). Lecture notes in computer science, vol 1520. Springer, pp 417-431

Sourd F (2006) Dynasearch neighborhood for the earliness-tardiness scheduling problem with release dates and setup constraints. Oper Res Lett 34(5):591–598CrossRef

Thompson PM, Psaraftis HN (1993) Cyclic transfer algorithms for multivehicle routing and scheduling problems. Operations Research 41:935–946CrossRef

Yagiura M, Yamaguchi T, Ibaraki T (1998) A variable depth search algorithm with branching search for the generalized assignment problem. Optim Methods Softw 10:419–441CrossRef

Titel: Very Large-Scale Neighborhood Search
verfasst von: Vittorio Maniezzo
Marco Antonio Boschetti
Thomas Stützle
Verlag: Springer International Publishing
Buch: Matheuristics
Print ISBN: 978-3-030-70276-2

Electronic ISBN: 978-3-030-70277-9

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-70277-9_6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"