Technische Universität Darmstadt

Quadratische Zuordnungsprobleme in

der Layoutplanung

Vorgelegt am

Fachbereich Rechts- und Wirtschaftswissenschaften

Fachgebiet Operations Research

Bearbeitet von

Andreas Eismann - Wirtschaftsinformatik

Thomas Fischer - Wirtschaftsingenieurwesen

Darmstadt, Juli 2008

Seite I

---

1

Einleitung 1

2

Überblick über die Problemstellung 1

2.1

Begriffe 1

2.1.1

Quadratisches Zuordnungsproblem 1

2.1.2

Organisationseinheiten 2

2.1.3

Standortträger 2

2.2

Komplexität 2

2.3

Modellierung bei gleichem Flächenbedarf der OE 2

2.4

Modellierung bei ungleichem Flächenbedarf der OE 4

2.5

Lösungsverfahren 5

2.5.1

Exakte Lösungsverfahren 6

2.5.2

Heuristische Lösungsverfahren 6

3

Aktuelle wissenschaftliche Arbeiten 7

3.1

A survey for the quadratic assignment problem 7

3.2

A Solution Method for the Quadratic Assignment Problem 8

3.3

Cunning Ant System for QAP with Local Search and Parallelization 8

3.4

A shape-based layout approach to facility layout problems using hybrid

algorithms 9

3.5

An Algorithm for the generalized QAP 10

3.6

A hybrid optimization approach for layout design of unequal-area facilities 11

4

Ausführliche Beschreibung einzelner Arbeiten 11

4.1

Zwei Heuristische Lösungsansätze bei ungleichem Flächenbedarf 12

4.1.1

Verfahren von Mir & Imam 2001 12

4.1.2

Verfahren von Lee & Lee 2002 16

4.2

Exakte Lösung bei ungleichem Flächenbedarf 19

4.2.1

Überblick 19

4.2.2

Ansatzpunkte zur Verbesserung des B&B-Algorithmus 20

4.2.3

Formelle Problembeschreibung 20

4.2.4

Mathematische Vorgehensweise 21

4.2.5

Kalkulation des lower bound 22

4.2.6

Überlegungen zum Linear Programming 23

4.2.7

Vorteile von RLT1 Dual Ascent 24

4.2.8

Branch & Bound 24

4.2.9

Zusammenfassung 25

5

Fazit und Ausblick 26

6

Anhang 28

Seite II

---

6.1

Literaturverzeichnis 28

6.2

Abbildungsverzeichnis 30

Seite III

---

Abkürzungsverzeichnis

AC

Adaptive Crossover Rate

ACO

Ant Colony Optimization

AOT

Analytische Optimierungstechnik

B&B

Branch & Bound

cAS

cunning Ant System

DAP

Dual Ascent Procedure

GA

Genetischer Algorithmus

GLB

Gilmore Lawler Bound

GQAP

Generalized Quadratic Assignment Problem

GQZOP

Generalisiertes quadratisches Zuordnungsproblem

HGA

Hybrider Genetischer Algorithmus

HOT

Hybride Optimierungstechnik

LIP

Linearized mixed Integer Problem

LP

Linear Programming

MMAS

Max Min Ant System

OE

Organisationseinheit(en)

RLT

Reformulation Linearization Technique

SA

Simulated Annealing

SBL

Shape Based Layout

TS

Tabu Search

TSP

Travelling Salesman Problem

QAP

Quadratic Assignment Problem

QZOP

Quadratisches Zuordnungsproblem

Seite IV

---

1 Einleitung

Ein Teilgebiet der innerbetrieblichen Standortplanung oder Layoutplanung sind

Quadratische Zuordnungsprobleme (QZOP). Diese Formulierung geht auf

Koopmans

und Beckmann 1957

[16] zurück. Grundproblem ist es einzelne Organisationseinhei-

ten auf einer rechteckigen Grundfläche so anzuordnen, dass die Summe der Trans-

portkosten minimiert wird. In diesem Zusammenhang wird zwischen Problemen mit

gleichem sowie ungleichem Flächenbedarf der Organisationseinheiten unterschie-

den. Zunächst werden die grundlegenden Begriffe geklärt. Außerdem werden die

wichtigsten Modellierungsverfahren für Probleme mit gleichem und ungleichem Flä-

chenbedarf sowie wichtige Lösungsalgorithmen und Heuristiken vorgestellt. Diese

Arbeit gibt einen allgemeinen Überblick über die Literatur der Jahre 2001 bis 2008.

Sechs Arbeiten aus diesem Zeitraum werden in Abschnitt 3 kurz vorgestellt. Im dar-

auffolgenden Abschnitt wird auf drei ausgewählte Arbeiten detaillierter eingegangen.

Der Fokus liegt hier auf Lösungsmöglichkeiten für Probleme mit ungleichem Flä-

chenbedarf, die auch in der Praxis eine wichtigere Rolle spielen.

2

Überblick über die Problemstellung

Zum Verständnis des Themenkomplexes sowie der Einordnung von Quadratischen

Zuordnungsproblemen in den Gesamtkontext der innerbetrieblichen Standortplanung

werden im Folgenden die grundlegenden Fakten und Merkmale dieser Probleme

betrachtet.

2.1 Begriffe

In dieser Sektion werden die Basisbegriffe der quadratischen Zuordnungsprobleme

erläutert, sowie deren Verwendung innerhalb der Problemlösungsstrategien aufge-

zeigt.

2.1.1 Quadratisches Zuordnungsproblem

Das quadratische Zuordnungsproblem wird im Deutschen auch als QZOP und im

Englischen als QAP abgekürzt. Bei Problemen mit ungleichem Flächenbedarf spricht

man auch von Generalized Quadratic Assignment Problems (GQAP). In dieser Ar-

beit werden im Weiteren die Begriffe QZOP und GQZOP (für das generalisierte quad-

ratische Zuordnungsproblem) verwendet. Bei dem QZOP handelt es sich um ein Op-

timierungsverfahren zur Anordnung von Organisationseinheiten auf einer zur Verfü-

gung stehenden Fläche.

Seite 1

---

2.1.2 Organisationseinheiten

Im Kontext der betrachteten Zuordnungsprobleme sind Organisationseinheiten (OE)

quadratische Felder, die auf einem Koordinatensystem bzw. Raster positioniert wer-

den. Bei Zuordnungsproblemen mit gleichem Flächenbedarf sind alle OE gleich groß

und nehmen im Regelfall ein Quadrat der Fläche 1x1 auf dem Standortträger ein.

Werden Zuordnungsprobleme mit ungleichem Flächenbedarf betrachtet, so kann die

Form der OE von der des Quadrates abweichen. Dabei besteht eine OE aus mehre-

ren, aneinander gereihten Quadraten, welche untrennbar miteinander verbunden

sind.

2.1.3 Standortträger

Der Standortträger ist derjenige Raum, auf welchem die OE angeordnet werden sol-

len. Wird das Problem quadratisch gelöst, so wird über den Standortträger ein Koor-

dinatensystem mit quadratischem Raster gelegt. Die Granularität des Rasters richtet

sich dabei an der Größe der OE aus.

2.2 Komplexität

Quadratische Zuordnungsprobleme befinden sich in der Komplexitätsklasse der NP-

vollständigen Probleme (

Cook 1971

[5],

Sahni und Gonzalez 1976

[23]). Für keines

der Probleme in dieser Komplexitätsklasse wurde bisher ein Algorithmus gefunden,

der eine exakte Lösung in polynomieller Zeit liefert. Daher sind QZOP nur für kleine

Probleme in der Größenordnung von etwa 20 - 30 OE exakt lösbar. Eine exakte Lö-

sung von Problemen mit wesentlich größerer Anzahl an OE ist aufgrund der be-

schränkten Rechenleistung nicht möglich. Sind dennoch größere Mengen an OE zu

bewältigen oder genauer gesagt anzuordnen, so wählt man in diesem Fall stattdes-

sen heuristische Verfahren, welche allerdings lediglich eine Annäherung an die exak-

te Lösung errechnen können.

2.3 Modellierung bei gleichem Flächenbedarf der OE

In dem folgenden Abschnitt werden herkömmliche Modellierungsansätze für Quadra-

tische Zuordnungsprobleme für Modelle mit gleichem Flächenbedarf vorgestellt.

Hierbei sind alle OE - wie in Abbildung 1 zu sehen - identisch groß. Die blauen Käst-

chen stellen hierbei die freien Flächen auf dem Standortträger dar.

Minimiert werden soll die Summe der Transportkosten, die abhängig sind von dem

Produkt der Distanz djk und der Transportintensität thi zwischen den Organisations-

einheiten h und i, wenn diese an den Positionen j und k des kontinuierlichen geras-

terten Standortträger angeordnet sind. Insgesamt sollen n OE auf einem Standortträ-

Seite 2

---

ger mit n Plätzen angeordnet werden. Die Kosten seien proportional zur zurückgeleg-

ten Entfernung und der Distanz. Der Proportionalitätsfaktor ist der Einfachheit halber

auf 1 gesetzt. Die allgemeine Formulierung wird auch QZOP1 genannt

(Domschke

und Drexl 1996,

S.195, [6]).

(1)

Unter den Nebenbedingungen:

(2)

ò

(3)

ò

(4)

ò

xhj sind Binärvariablen, wobei der Wert eins bedeutet, dass die OE h an der Stelle j

angeordnet werden soll. Nebenbedingung (3) sagt aus, dass jede OE genau einem

Platz zugeordnet ist. Nebenbedingung (4) bedeutet, dass jeder Platz mit genau einer

OE besetzt ist.

Möchte man den Fall modellieren, dass es mehr freie Plätze m auf dem Standortträ-

ger als Organisationseinheiten n gibt (n m), muss man das Gleichheitszeichen in (4)

durch ein ersetzen. Außerdem erfolgt die Summation in der Zielfunktion bei k und j

sowie in der Nebenbedingung (3) nur bis m.

Abbildung 1: QZOP unter gleichem Flächenbedarf

Des Weiteren unterscheidet man den Fall asymmetrischer und symmetrischer QZO-

Pen. Im zweiten Fall gilt für alle i und j: dij=dji. Bei der Modellierung dieses Falles kann

die Indexbildung auf den Teil unterhalb der Hauptdiagonale beschränkt werden. Die

Zielfunktion sieht wie dann wie folgt aus:

(5)

Seite 3

---