MA4512 Technische Universität München Zentrum Mathematik Fallstudien Diskrete Optimierung Dipl.-Math.Oec Melanie Bestle j Dr. Michael Ritter Airline Crew Scheduling 1 Pricing Problem Für das Airline Crew Scheduling müssen ein oder mehrere zulässige Umläufe mit negativen reduzierten Kosten gefunden werden. Zur Vereinfachung nehmen wir an, dass ein Umlauf zulässig ist, wenn • der Umlauf an der Heimatbasis der Crew startet und endet und • die vorgegebenen Abflugzeiten eingehalten werden. Die reduzierten Kosten eines zulässigen Umlaufes u sind X cu f 2u f Dabei gibt cu die Kosten des Umlaufes an. Diese berechnen sich vereinfacht als Gesamtkosten aller Deadheads, also der Flüge bei denen die Crew als Passagier mitreist. 2 Beispiel TUMair ist eine kleine Fluggesellschaft aus München (Basis). Morgen sind folgende Flüge geplant: Flug TUM101 TUM102 TUM103 TUM104 von München Paris London München nach London München Rom Paris Abflug 8:45 13:05 13:15 15:00 Ankunft 10:45 14:35 16:30 16:30 (Alle Zeiten sind in Mitteleuropäischer Zeit angegeben.) TUMair möchte den Einsatz der Kabinencrews planen. Aufgrund von vertraglichen Vereinbarungen von TUMair mit anderen Fluggesellschaften können die Crews jederzeit als Passagiere von einem Flughafen zum anderen gelangen. Die Dauer und Kosten dieser Deadheads sind in den folgenden Tabellen angegeben: London München Paris Rom London München Paris Rom SS 2011 London 0 min 120 min 90 min 210 min London 0e 100 e 75 e 175 e München 120 min 0 min 90 min 100 min München 100 e 0e 100 e 150 e Paris 90 min 90 min 0 min 150 min Paris 75 e 100 e 0e 125 e Rom 210 min 100 min 150 min 0 min Rom 175 e 150 e 125 e 0e MA4512 3 Aufgabe 1. Sei G = (V; A) ein Graph auf der Knotenmenge V und der Menge gerichteter Kanten A. Betrachten Sie V = Basisstart ; Basisend F , wobei F die Menge aller Flüge bezeichnet. Wie muss die Kantenmenge auf diesem Graphen aussehen, damit Pfade im Graphen zulässige Crewbewegungen sind? Zeichnen Sie die Kanten in die Skizze ein. f g[ 2. Tragen Sie nun die Kosten von Deadheads als Kantengewichte in die Skizze ein. 3. Angenommen die Relaxation des reduzierten Problems wurde gelöst. Die Werte der dualen Variablen seien: TUM 101 = 30 TUM 102 = 60 TUM 103 = 130 TUM 104 = 90 Welche Umläufe haben negative reduzierte Kosten? (Warum müssen Sie dafür nicht wissen, welche Umläufe das reduzierte Problem bereits enthält?) 4. Welches graphentheoretische Problem müssen Sie lösen, um diese Umläufe zu finden? Kennen Sie bereits Algorithmen für dieses Problem? SS 2011 MA4512 TUM103 TUM101 TUM102 TUM104 Basisstart Basisend SS 2011
© Copyright 2024 ExpyDoc
