nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

3. Single Solution Metaheuristics

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

Metaheuristic approaches can be classified according to different criteria, one being the number of solutions that are evolved at each stage of the algorithm: one single solution or more than one. This chapter deals with metaheuristic algorithms that evolve one single solution; they are all enhancements of a basic local search procedure. Many different approaches have been presented, which could be included here. We choose six of them, namely Simulated Annealing, Tabu Search, GRASP, Iterated Local Search, Variable Neighborhood Search, and Ejection chains, as representative of the class and as the most widely used in the matheuristic literature. Matheuristic algorithms have in fact been used to complement each of them, along with others of the unreported ones. The techniques used to include mathematical components in the basic metaheuristic structure tend to be general and independent of the specific single solution metaheuristic they have been reported for.

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 Automatic Design for Matheuristics

Nächstes Kapitel Population-Based Metaheuristics

For more on this, see Lourenço et al. (2002).

We remind that in the computational traces the decision variables are indexed from 0.

Adamo T, Ghiani G, Guerriero E, Manni E (2017) Automatic instantiation of a variable neighborhood descent from a mixed integer programming model. Oper Res Perspect 4:123–135

Andersen AC, Funch C (2008) Rostering optimization for business jet airlines. Master thesis, Department of Transport, Technical University of Denmark Kongens Lyngby

Archetti C, Feillet D, Hertz A, Speranza MG (2010) The undirected capacitated arc routing problem with profits. Comput Oper Res 37(11):1860–1869CrossRef

Avella P, D’Auria B, Salerno S, Vasil’ev I (2007) A computational study of local search algorithms for Italian high-school timetabling. J Heuristics, 543–556

Belvaux G, Wolsey LA (2000) bc-prod: a specialized branch-and-cut system for lot-sizing problems. Management Science 46(5):724–738CrossRef

Chouman M, Crainic T (2010) MIP-tabu search hybrid framework for multicommodity capacitated fixed-charge network design. Technical report CIRRELT-2010-31

Codenotti B, Manzini G, Margara L, Resta G (1996) Perturbation: An efficient technique for the solution of very large instances of the Euclidean TSP. INFORMS J Comput 8(2):125–133CrossRef

Della Croce F, Salassa F (2014) A variable neighborhood search based matheuristic for nurse rostering problems. Ann OR 218:185–199CrossRef

Dolgui A, Eremeev A, Guschinskaya O (2009) MIP-based grasp and genetic algorithm for balancing transfer lines. In: Maniezzo V, Stützle T, Voß S (eds) Matheuristics. Annals of Information Systems, vol 10. Springer, Boston, MA

Feo TA, Resende MGC (1989) A probabilistic heuristic for a computationally difficult set covering problem. Oper Res Lett 8:67–71CrossRef

Feo TA, Resende MGC (1995) Greedy randomized adaptive search procedures. J Global Optim 6:109–133CrossRef

Fernandes S, Lourenço HRA (2008) Simple optimised search heuristic for the job shop scheduling problem. In: Cotta C, van Hemert J (eds) Recent advances in evolutionary computation for combinatorial optimization. Studies in computational intelligence, vol 153. Springer, Berlin, Heidelberg, pp 203–218CrossRef

Ferreira D, Morabito R, Rangel S (2010) Relax and fix heuristics to solve one-stage one-machine lot-scheduling models for small-scale soft drink plants. Comput Oper Res 37(4):684–691CrossRef

Fonseca GH, Santos HG, Carrano EG (2016) Integrating matheuristics and metaheuristics for timetabling. Comput Oper Res 74:108–117CrossRef

Gabrielli R, Guidazzi A, Boschetti MA, Roffilli M, Maniezzo V (2006) Practical origin-destination traffic flow estimation. In: ODYSSEUS 2006, Third international workshop on freight transportation and logistics, Altea (Spain), pp 23–26

Gendron B, Hanafi S, Todosijević R (2016) An efficient matheuristic for the multicommodity fixed-charge network design problem. IFAC-PapersOnLine 49(12):117–120CrossRef

Glover F (1989) Tabu search – part I. ORSA J Comput 1(3):190–206CrossRef

Glover F (1990) Tabu search – part II. ORSA J Comput 2(1):14–32CrossRef

Glover F (1992a) Ejection chains and combinatorial leverage for traveling salesman problems. Tech. rep., School of Business, University of Colorado, Boulder, CO

Glover F (1992b) New ejection chain and alternating path methods for traveling salesman problems. In: Balci, Sharda, Zenios (eds) Computer science in operations research: New developments in their interfaces, Pergamon, pp 491–507

Glover F (1996) Ejection chains, reference structures and alternating path methods for traveling salesman problems. Discrete Appl Math 65(1–3):223–253CrossRef

Glover F, Laguna M (1997) Tabu search. Kluwer Academic Publishers, BostonCrossRef

Gunawan A, Ming Ng K, Leng Poh K (2012) A hybridized Lagrangian relaxation and simulated annealing method for the course timetabling problem. Comput Oper Res 39(12):3074–3088CrossRef

Hansen P, Mladenovic N, Perez-Britos D (2001) Variable neighborhood decomposition search. J Heuristics 7(4):335–350CrossRef

Harvey WD, Ginsberg ML (1995) Limited discrepancy search. In: Proc. of IJCAI-95, Morgan Kaufmann, Montreal, Quebec, p 607–613

Hoos H, Stützle T (2004) Stochastic local search-foundations and applications. Morgan Kaufmann, San Francisco, CA, USA

Hu B, Raidl GR (2006) Variable neighborhood descent with self-adaptive neighborhood ordering. In: Proceedings of the 7th EU/ME meeting on adaptive, self-adaptive and multi-level metaheuristics

Hu B, Leitner M, Raidl GR (2008) Combining variable neighborhood search with integer linear programming for the generalized minimum spanning tree problem. J Heuristics 14(5):473–499CrossRef

Hubscher R, Glover F (1992) Ejection chain methods and tabu search for clustering. Tech. rep., School of Business, University of Colorado, Boulder, CO

Kirkpatrick S, Gelatt C, Vecchi M (1983) Optimization by simulated annealing. Science 220:671–680CrossRef

Laguna M, Kelly J, Gonzales-Velarde L, Glover F (1995) Tabu search for the multilevel generalized assignment problem. Eur J Oper Res 82:176–189CrossRef

Lazić J (2010) New variants of variable neighbourhood search for 0-1 mixed integer programming and clustering. Tech. rep., School of Information Systems, Computing and Mathematics. Brunel University London

Lopes R, Morais VW, Noronha TF, Souza V (2015) Heuristics and matheuristics for a real-life machine reassignment problem. Int Trans Oper Res 22:77–95CrossRef

Lourenço HR, Martin O, Stützle T (2002) Iterated local search. In: Glover F, Kochenberger G (eds) Handbook of metaheuristics. International series in operations research & management science. Kluwer Academic Publishers, pp 321–353

Lourenço HR, Martin O, Stützle T (2010) Iterated local search: Framework and applications. Handbook of metaheuristics, 2nd edn. International series in operations research & management science, vol 146. Kluwer Academic Publishers, pp 363–397

Manerba D, Mansini R (2014) An effective matheuristic for the capacitated total quantity discount problem. Comput Oper Res 41:1–11CrossRef

Maniezzo V, Boschetti MA, Carbonaro A, Marzolla M, Strappaveccia F (2019) Client-side computational optimization. ACM Trans Math Softw 45(2):1–16CrossRef

Metropolis N, Rosenbluth AW, Rosenbluth MN, Teller AH, Teller E (1953) Equation of state calculations by fast computing machines. J Chem Phys 21(6):1087–1092CrossRef

Mitra D, Romeo F, Vincentelli AS (1986) Convergence and finite-time behavior of simulated annealing. Adv Appl Probab, 747–771

Mladenovic N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24(11):1097–1100CrossRef

Ngueveu SU, Prins C, Wolfler R (2009) A hybrid tabu search for the m-peripatetic vehicle routing problem. In: Maniezzo V, Stützle T, Voß S (eds) Matheuristics. Annals of information systems, vol 10. Springer, Boston, MA

Pirkwieser S, Raidl GR (2010) Variable neighborhood search coupled with ILP-based very large neighborhood searches for the (periodic) location-routing problem. In: Blesa M, Blum C, Raidl G, Roli A, Sampels M (eds) Hybrid metaheuristics, HM 2010. Lecture notes in computer science, vol 6373. Springer, pp 174–189

Prandtstetter M, Raidl GR (2008) An integer linear programming approach and a hybrid variable neighborhood search for the car sequencing problem. Eur J Oper Res 191(3):1004–1022CrossRef

Puchinger J, Raidl GR (2008) Bringing order into the neighborhoods: Relaxation guided variable neighborhood search. J Heuristics 14(5):457–472CrossRef

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

Roshani A, Giglio D, Paolucci M (2017) A relax-and-fix heuristic approach for the capacitated dynamic lot sizing problem in integrated manufacturing/remanufacturing systems. IFAC-PapersOnLine 50(1):9008–9013CrossRef

Sadykov R, Vanderbeck F, Pessoa A, Uchoa E (2015) Column Generation Based Heuristic for the Generalized Assignment Problem. XLVII Simpósio Brasileiro de Pesquisa Operacional, Porto de Galinhas, Brazil

Sahni S (1975) Approximates for the 0/1 knapsack problem. J Assoc Comput Mach 22(1):115–124CrossRef

Santos HG, Toffolo TAM, Ribas S, Gomes RAM (2012) Integer programming techniques for the nurse rostering problem. In: Proceedings of PATAT 2012. Lecture notes in computer science. Springer, pp 256–283

Shmoys DB, Tardos E (1993) An approximation algorithm for the generalized assignment problem. Mathematical Programming 62(1-3):461–474CrossRef

Strodl J, Doerner KF, Tricoire F, Hartl RF (2010) On index structures in hybrid metaheuristics for routing problems with hard feasibility checks: an application to the 2-dimensional loading vehicle routing problem. In: Blesa M, Blum C, Raidl G, Roli A, Sampels M (eds) Hybrid metaheuristics, HM 2010. Lecture notes in computer science, vol 6373. Springer, pp 160–173

Toledo CFM, da Silva A, M H, M Y B PMF, Akartunali K (2015) A relax-and-fix with fix-and-optimize heuristic applied to multi-level lot-sizing problems. J Heuristics 21(5):687–717

Tomazic A, Ljubic I (2008) A grasp algorithm for connected facility location. In: International symposium on applications and the internet. IEEE Computer Society Press, pp 257–260

Umetani S, Yagiura M, Ibaraki T (2003) One-dimensional cutting stock problem to minimize the number of different patterns. Eur J Oper Res 146(2):388–402CrossRef

Walla J, Ruthmair M, Raidl GR (2009) Solving a video-server load rebalancing problem by mixed integer programming and hybrid variable neighborhood search. In: Blesa M, Blum C, Raidl G, Roli A, Sampels M (eds) Hybrid metaheuristics, HM 2010. Lecture notes in computer science, vol 6373. Springer, pp 84–99

Wilcox SP (1989) A new multiplier adjustment method for the generalized assignment problem, Working paper, General Research Corporation, Mc Lean, VI

Yaghini M, Karimi M, Rahbar M, Akhavan RA (2011) Hybrid simulated annealing and simplex method for fixed-cost capacitated multicommodity network design. Int J Appl Metaheuristic Comput 2(4):13–28CrossRef

Yaghini M, Karimi M, Rahbar MA (2013) Hybrid metaheuristic approach for the capacitated p-median problem. Appl Soft Comput 13(9):3922–3930CrossRef

Titel: Single Solution Metaheuristics
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_3

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"