Please activate JavaScript!
Please install Adobe Flash Player, click here for download

Leseprobe "Modellbasiertes Logistikmanagement mit Excel"

Inhaltsverzeichnis XV 8.3.1.1 Das Sortieren der Orte nach Polarwinkeln............................465 8.3.1.2 Beispiel: TSP_DepotDdorf_Polarwinkel................................467 8.3.1.3 Das Sortieren der Orte nach Kurswinkeln auf der Kugeloberfläche....................................................................469 8.3.1.4 Beispiel: TSP_DepotDdorf_Kurswinkel.................................471 8.3.1.5 Das Verfahren des besten Nachfolgers ................................476 8.3.1.6 Beispiel: TSP_DepotDdorf_BesterNachfolger.......................476 8.3.1.7 Das Verfahren der sukzessiven Einbeziehung......................479 8.3.1.8 Beispiel: TSP_DepotDdorf_SukzEinbeziehung.....................480 8.3.1.9 Das Verfahren von Christofides ............................................487 8.3.1.10 Beispiel zur Berechnung eines Minimalen Spannenden Baumes (MSB): TSP_DepotDdorf_Christofides/MSB...........490 8.3.1.11 Beispiel zur Berechnung eines Minimalen Kosten Matchings (MKM): TSP_DepotDdorf_Christofides/MKM ......494 8.3.1.12 Beispiel zur Berechnung einer Rundreise in MSBuMKM: TSP_DepotDdorf_Christofides/Rundreise ............................498 8.3.2 Verbesserungsverfahren: 2-opt-, 3-opt- und k-opt-Verfahren............504 8.3.2.1 Beispiel: TSP_DepotDdorf_2opt ...........................................505 8.3.2.2 Beispiel: TSP_DepotDdorf_3opt ...........................................508 8.4 Kapazitätsbeschränkte Tourenplanung (Capacitated Vehicle Routing Problem) ......................................................................................................513 8.4.1 Ökonomische Problembeschreibung.................................................513 8.4.2 Mathematische Formulierung des Problems (CVRP) ........................513 8.4.3 Mathematisches Modell.....................................................................514 8.4.4 Das TSP als Spezialfall des CVRP....................................................516 8.4.5 Die verallgemeinerte MTZ-Bedingung ...............................................516 8.4.6 Gleichzeitige Auslieferung und Abholung von Gütern .......................516 8.5 Beispiele zur kapazitätsbeschränkten Tourenplanung.................................517 8.5.1 CVRP.................................................................................................517 8.5.2 CVRP_DepotDdorf ............................................................................524 8.6 Heuristiken für Tourenplanungsprobleme....................................................534 8.6.1 Das Savings-Verfahren......................................................................534 8.6.1.1 Allgemeine Idee des Savings-Verfahren...............................534 8.6.1.2 Iterativer Lösungsansatz.......................................................536 8.6.1.3 Qualität des Savings-Verfahren ............................................537 8.6.2 Beispiel CVRP_Depot_Ddorf_Savings ..............................................538 8.6.3 Das Sweep-Verfahren .......................................................................548 8.6.3.1 Allgemeine Idee des Sweep-Verfahrens...............................548 8.6.3.2 Iterativer Lösungsalgorithmus...............................................549 8.6.3.3 Qualität des Sweep-Algorithmus...........................................549 8.6.4 Beispiel CVRP_Depot_Ddorf_Sweep................................................550 8.6.5 Petal-Algorithmen ..............................................................................554 8.6.5.1 Allgemeine Idee der Petal-Algorithmen.................................554 8.6.5.2 Lösungsalgorithmus..............................................................554 8.6.5.3 Qualität und Erweiterungsmöglichkeiten...............................555 8.6.6 Beispiel CVRP_Depot_Ddorf_Petal...................................................556 8.7 Kapazitätsbeschränkte Tourenplanung mit Zeitfenstern (Capacitated Vehicle Routing Problem with Time Windows) .......................566 8.7.1 Ökonomische Problembeschreibung.................................................566 8.7.2 Mathematische Formulierung des Problems (CVRPTW)...................567 8.7.3 Mathematisches Modell.....................................................................567

Pages