Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction to Location Science Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

13. The Quadratic Assignment Problem

verfasst von : Zvi Drezner

Erschienen in: Location Science

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

The quadratic assignment problem is reviewed in this chapter. Weights between pairs of facilities and distances between the same number of locations are given. The problem is to find the assignment of facilities to locations that minimizes the weighted sum of distances. This problem is considered to be one of the most difficult combinatorial optimization problems. The construction of efficient solution algorithms (exact or heuristic) is challenging and has been extensively investigated by the communities working in Operations Research/Management Science, Industrial Engineering, or Computer Science. Examples of applications are given, the related layout problem is briefly described, exact and heuristic solution algorithms are reviewed, and a list of test problem instances and results are reported.

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 Hub Location Problems
Nächstes Kapitel Competitive Location Models
Literatur
Adams W, Guignard M, Hahn P, Hightower W (2007) A level-2 reformulation-linearization technique bound for the quadratic assignment problem. Eur J Oper Res 180:983–996
Ahuja R, Orlin J, Tiwari A (2000) A descent genetic algorithm for the quadratic assignment problem. Comput Oper Res 27:917–934
Amin S (1999) Simulated jumping. Ann Oper Res 84:23–38
Anstreicher K, Brixius N, Gaux JP, Linderoth J (2002) Solving large quadratic assignment problems on computational grids. Math Program 91:563–588
Anstreicher KM, Brixius NW (2001) A new bound for the quadratic assignment problem based on convex quadratic programming. Math Program 89:341–357
Armour GC, Buffa ES (1963) A heuristic algorithm and simulation approach to relative location of facilities. Manag Sci 9:294–309
Battiti R, Tecchiolli G (1994) The reactive tabu search. ORSA J Comput 6:126–140
Bos J (1993) Zoning in forest management: a quadratic assignment problem solved by simulated annealing. J Environ Manag 37:127–145
Buffa ES, Armour GC, Vollmann TE (1962) Allocating facilities with CRAFT. Harv Bus Rev 42:136–158
Burer S, Vandenbussche D (2006) Solving lift-and-project relaxations of binary integer programs. SIAM J Optimiz 16:726–750
Burkard R, Rendl F (1984) A thermodynamically motivated simulation procedure for combinatorial optimization problems. Eur J Oper Res 17:169–174
Burkard RE (1990) Locations with spatial interactions: the quadratic assignment problem. In: Mirchandani PB, Francis RL (eds) Discrete location theory. Wiley, New York, pp 387–437
Burkard RE, Cela E (1999) Linear assignment problems and extensions. In: Pardalos P, Du D-Z (eds) Handbook of combinatorial optimization. Springer, Dordrecht, pp 75–149
Burkard RE (2013) Quadratic assignment problems. In: Pardalos P, Du D-Z (eds) Handbook of combinatorial optimization, 2nd edn. Springer, New York, pp 2741–2814
Burkard RE, Offermann J (1977) Entwurf von schreibmaschinentastaturen mittels quadratischer zuordnungsprobleme. Math Method Oper Res 21:121–132
Cantú-Paz E (2001) Migration policies, selection pressure, and parallel evolutionary algorithms. J Heuristics 7:311–334
de Carvalho Jr SA, Rahmann S (2006) Microarray layout as a quadratic assignment problem. In: Huson D, Kohlbacher O, Lupas A, Nieselt K, Zell A (eds) Proceedings of the German conference on bioinformatics, vol 83. Gesellschaft für Informatik, Bonn, pp 11–20
Cela E (1998) The quadratic assignment problem: theory and algorithms. Kluwer Academic Publishers, Dordrecht
Connoly D (1990) An improved annealing scheme for the QAP. Eur J Oper Res 46:93–100
Cordeau JF, Gaudioso M, Laporte G, Moccia L (2006) A memetic heuristic for the generalized quadratic assignment problem. INFORMS J Comput 18:433–443
Coxeter HSM (1973) Regular polytopes. Dover Publications, New York
Cung VD, Mautor T, Michelon P, Tavares AI (1997) A scatter search based approach for the quadratic assignment problem. In: Proceedings of the IEEE international conference on evolutionary computation and evolutionary programming (ICEC’97), Indianapolis, pp 165–170
Dickey JW, Hopkins JW (1972) Campus building arrangement using topaz. Transp Res 6:59–68
Drezner T, Drezner Z (2005) Genetic algorithms: mimicking evolution and natural selection in optimization models. In: Bar-Cohen Y (ed) Biomimetics—biologically inspired technologies. CRC Press, Boca Raton, pp 157–175
Drezner T, Drezner Z (2006) Gender specific genetic algorithms. INFOR Inform Syst Oper Res 44:117–127
Drezner Z (1975) Problems in non-linear programming (the allocation problem). Ph.D. thesis, The Technion, Haifa
Drezner Z (1980) DISCON—a new method for the layout problem. Oper Res 28:1375–1384
Drezner Z (1987) A heuristic procedure for the layout of a large number of facilities. Manag Sci 33:907–915
Drezner Z (2002) A new heuristic for the quadratic assignment problem. J Appl Math Decis Sci 6:163–173
Drezner Z (2003) A new genetic algorithm for the quadratic assignment problem. INFORMS J Comput 15:320–330
Drezner Z (2005a) A distance based rule for removing population members in genetic algorithms. 4OR-Q J Oper Res 3:109–116
Drezner Z (2005b) The extended concentric tabu for the quadratic assignment problem. Eur J Oper Res 160:416–422
Drezner Z (2006) Finding a cluster of points and the grey pattern quadratic assignment problem. OR Spectr 28:417–436
Drezner Z (2008a) Extensive experiments with hybrid genetic algorithms for the solution of the quadratic assignment problem. Comput Oper Res 35:717–736
Drezner Z (2010) On the unboundedness of facility layout problems. Math Method Oper Res 72:205–216
Drezner Z, Marcoulides GA (2003) A distance-based selection of parents in genetic algorithms. In: Resende MGC, de Sousa JP (eds) Metaheuristics: computer decision-making. Kluwer Academic Publishers, Boston, pp 257–278
Drezner Z, Misevičius A (2013) Enhancing the performance of hybrid genetic algorithms by differential improvement. Comput Oper Res 40:1038–1046
Drezner Z, Suzuki A (2010) Covering continuous demand in the plane. J Oper Res Soc 61:878–881
Drezner Z, Zemel E (1992) Competitive location in the plane. Ann Oper Res 40:173–193
Drezner Z, Hahn PM, Taillard ÉD (2005) Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods. Ann Oper Res 139:65–94
Drezner Z, Misevičius A, Palubeckis G (2014) Exact algorithms for the solution of the grey pattern quadratic assignment problem. In review
Duman E, Uysal M, Alkaya AF (2012) Migrating birds optimization: a new metaheuristic approach and its performance on quadratic assignment problem. Inform Sci 217:65–77
Elshafei AN (1977) Hospital layout as a quadratic assignment problem. Oper Res Q 28:167–179
Fischetti M, Monaci M, Salvagnin D (2012) Three ideas for the quadratic assignment problem. Oper Res 60:954–964
Fleurent C, Ferland J (1994) Genetic hybrids for the quadratic assignment problem. In: Pardalos P, Wolkowicz H (eds) Quadratic assignment and related problems, DIMACS series in discrete mathematics and theoretical computer science, vol 16. American Methematical Society, Providence, pp 173–187
Fox BR, McMahon MB (1991) Genetic operators for sequencing problems. In: Rawlins G (ed) Foundations of genetic algorithms. Morgan-Kaufmann, San Mateo, pp 284–300
Francis RL, McGinnis LF Jr, White JA (1992) Facility layout and location: an analytical approach, 2nd edn. Prentice Hall, Englewood Cliffs
Gambardella L, Taillard ÉD, Dorigo M (1999) Ant colonies for the quadratic assignment problem. J Oper Res Soc 50:167–176
Geoffrion AM, Graves GW (1976) Scheduling parallel production lines with changeover costs: practical application of a quadratic assignment/lp approa ch. Oper Res 24:595–610
Gilmore P (1962) Optimal and suboptimal algorithms for the quadratic assignment problem. J SIAM 10:305–313
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:533–549
Glover F, Laguna M (1997) Tabu search. Kluwer Academic Publishers, Boston
Hahn P, Grant T (1998) Lower bounds for the quadratic assignment problem based upon a dual formulation. Oper Res 46:912–922
Hahn P, Krarup J (2001) A hospital facility problem finally solved. J Intell Manuf 12:487–496
Hahn PM, Kim BJ, Guignard M, Smith JM, Zhu YR (2008) An algorithm for the generalized quadratic assignment problem. Comput Optim Appl 40:351–372
Hahn PM, Zhu YR, Guignard M, Hightower WL, Saltzman MJ (2012) A level-3 reformulation-linearization technique-based bound for the quadratic assignment problem. INFORMS J Comput 24:202–209
Heffley DR (1977) Assigning runners to a relay team. In: Ladany SP, Machol RE (eds) Optimal strategies in sports. North-Holland, Amsterdam, pp 169–171
Hilbert D, Cohn-Vossen S (1956) Geometry and the imagination (english translation of Anschauliche Geometrie, 1932). Chelsea Publishing Company, New York
Hillier FS, Connors MM (1966) Quadratic assignment problem algorithms and the location of indivisible facilities. Manag Sci 13:42–57
Holland JH (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor
Koopmans TC, Beckmann MJ (1957) Assignment problems and the location of economic activities. Econometrica 25:53–76
Laporte G, Mercure H (1988) Balancing hydraulic turbine runners: a quadratic assignment problem. Eur J Oper Res 35:378–381
Lawler EL (1973) Optimal sequencing of a single machine subject to precedence constraints. Manag Sci 19:544–546
Lee CG, Ma Z (2005) The generalized quadratic assignment problem. Department of Mechanical and Industrial Engineering, University of Toronto, MIE OR Technical Reports (TR2005-01)
Li Y, Pardalos PM (1992) Generating quadratic assignment test problems with known optimal permutations. Comput Optim Appl 1:163–184
Li Y, Pardalos PM, Resende MGC (1994) A greedy randomized adaptive search procedure for the quadratic assignment problem. In: Pardalos PM, Wolkowicz H (eds) Quadratic assignment and related problems, DIMACS series in discrete mathematics and theoretical computer science, vol 16, American Mathematical Society, Providence, pp 237–261
Loiola EM, de Abreu NMM, Boaventura-Netto PO, Hahn P, Querido T (2007) A survey for the quadratic assignment problem. Eur J Oper Res 176:657–690
Love RF, Wong JY (1976) Solving quadratic assignment problems with rectangular distances and integer programming. Nav Res Logist Q 23:623–627
Misevičius A (2003) A modified simulated annealing algorithm for the quadratic assignment problem. Informatica 14:497–514
Misevičius A (2011) Generation of grey patterns using an improved genetic-evolutionary algorithm: some new results. Inf Technol Control 40:330–343
Misevičius A (2012) An implementation of the iterated tabu search algorithm for the quadratic assignment problem. OR Spectr 34:665–690
Misevičius A, Blonskis J (2005) Experiments with tabu search for random quadratic assignment problems. Inf Technol Control 34:237–244
Misevičius A, Guogis E (2012) Computational study of four genetic algorithm variants for solving the quadratic assignment problem. In: Skersys T, Butkienè R, Butleris R (eds) Communications in computer and information science (CCIS). Proceedings of 18th international conference on information and software technologies ICIST 2012, vol 319. Springer, Berlin, pp 24–37
Misevičius A, Tomkevičius A, Karbauskas J (2006) Stagnation-protected tabu search variants for unstructured quadratic assignment problems. Inf Technol Control 35:363–370
Misevičius A, Guogis E, Stanevičienè E (2013) Computational algorithmic generation of high-quality colour patterns. In: Skersys T, Butkienè R, Butleris R (eds) Communications in computer and information science (CCIS). Proceedings of 19th international conference in information and software technologies ICIST 2013. Springer, Berlin, pp 285–296
Misevičius A (2004) An improved hybrid genetic algorithm: new results for the quadratic assignment problem. Knowl-Based Syst 17:65–73
Misevičius A (2005) A tabu search algorithm for the quadratic assignment problem. Comput Optim Appl 30:95–111
Misevičius A (2008) Restart-based genetic algorithm for the quadratic assignment problem. In: Bramer M, Coenen F, Petridis M (eds) Research and development in intelligent systems. Proceedings of AI-2008, the 28th SGAI international conference on innovative techniques and applications of artificial intelligence. Springer, London, pp 91–104
Misevičius A, Rubliauskas D (2009) Testing of hybrid genetic algorithms for structured quadratic assignment problems. Informatica 20:255–272
Misevičius A, Rubliauskas D, Barkauskas V (2009) Some further experiments with the genetic algorithm for the quadratic assignment problem. Inf Technol Control 38:325–332
Nugent C, Vollman T, Ruml T (1968) An experimental comparison of techniques for the assignment of facilities to locations. Oper Res 16:150–173
Nyberg A, Westerlund T (2012) A new exact discrete linear reformulation of the quadratic assignment problem. Eur J Oper Res 220:314–319
Okabe A, Suzuki A (1987) Stability of spatial competition for a large number of firms on a bounded two-dimensional space. Environ Plann A 16:107–114
Oliveira CAS, Pardalos PM, Resende MGC (2004) GRASP with path-relinking for the quadratic assignment problem. In: Ribeiro CC, Martins SL (eds) Efficient and experimental algorithms. Springer, Berlin/Heidelberg, pp 237–261
Pierce JF, Crowston WB (1971) Tree-search algorithms for quadratic assignment problems. Nav Res Logist Q 18:1–36
Pierskalla WP (1967) The tri-substitution method for the three-dimensional assignment problem. CORS J 5:71–81
Pierskalla WP (1968) The multidimensional assignment problem. Oper Res 16:422–431
Ramakrishnan KG, Resende M, Ramachandran B, Pekny J (2002) Tight QAP bounds via linear programming. In: Pardalos PM, Migdalas A, Burkard R (eds) Combinatorial and global optimization. World Scientific Publishing, Singapore, pp 297–303
Rendl F (2002) The quadratic assignment problem. In: Drezner Z, Hamacher H (eds) Facility location: applications and theory. Springer, Berlin
Rendl F, Sotirov R (2007) Bounds for the quadratic assignment problem using the bundle method. Math Program 109:505–524
Resende M, Ramakrishnan K, Drezner Z (1995) Computational experiments with the lower bound for the quadratic assignment problem based on linear programming. Oper Res 43:781–791
Roupin F (2004) From linear to semidefinite programming: an algorithm to obtain semidefinite relaxations for bivalent quadratic problems. J Comb Optim 8:469–493
Sahni S, Gonzalez T (1976) P-complete approximation problems. J ACM 23:555–565
Schaffer JD, Caruana RA, Eshelman LJ (1989) A study of control parameters affecting online performance of genetic algorithms. In: Schaffer JD (ed) Proceedings of the 3rd international conference on genetic algorithms. Morgan Kaufmann, San Mateo, pp 51–60
Sherali HD, Adams WP (1990) A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J Discret Math 3:411–430
Sherali HD, Adams WP (1998) A reformulation-linearization technique for solving discrete and continuous nonconvex problems. Springer, Berlin
Skorin-Kapov J (1990) Tabu search applied to the quadratic assignment problem. ORSA J Comput 2:33–45
Steinberg L (1961) The backboard wiring problem: a placement algorithm. SIAM Rev 3:37–50
Suzuki A, Drezner Z (1996) The p-center location problem in an area. Locat Sci 4:69–82
Suzuki A, Okabe A (1995) Using Voronoi diagrams. In: Drezner Z (ed) Facility location: a survey of applications and methods. Springer, New York, pp 103–118
Szabo PG, Markot M, Csendes T, Specht E (2007) New approaches to circle packing in a square: with program codes. Springer, New York
Taillard ÉD (1991) Robust tabu search for the quadratic assignment problem. Parallel Comput 17:443–455
Taillard ÉD (1995) Comparison of iterative searches for the quadratic assignment problem. Locat Sci 3:87–105
Taillard ÉD (1998) Fant: fast ant system. Technical report, Istituto Dalle Molle Di Studi Sull Intelligenza Artificiale, iDSIA Technical Report IDSIA-46-98
Taillard ÉD (2000) An introduction to ant systems. In: Laguna M, González-Velarde J (eds) Computing tools for modeling, optimization and simulation. Wiley, New York, pp 131–144
Talbi EG, Roux O, Fonlupt C, Robillard D (2001) Parallel ant colonies for the quadratic assignment problem. Futur Gener Comput Syst 17:441–449
Tate D, Smith A (1995) A genetic approach to the quadratic assignment problem. Comput Oper Res 22:73–83
Thonemann U, Bölte A (1994) An improved simulated annealing algorithm for the quadratic assignment problem. Technical report, working paper, School of Business, Department of Production and Operations Research, University of Paderborn, Germany
Wilhelm M, Ward T (1987) Solving quadratic assignment problems by simulated annealing. IIE Trans 19:107–119
Wu Y, Ji P (2008) Solving the quadratic assignment problems by a genetic algorithm with a new replacement strategy. Int J Comput Intell 4:225–229
Metadaten
Titel
The Quadratic Assignment Problem
verfasst von
Zvi Drezner
Copyright-Jahr
2015
Buch
Location Science

Print ISBN: 978-3-319-13110-8

Electronic ISBN: 978-3-319-13111-5

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-13111-5_13

Premium Partner

    Bildnachweise