Entsprechend unseren guten Erfahrungen mit den auf Linearer Programmierung basierten Ansätzen für das Fleet- und Crew-Assignment-Problem verwenden wir auch hier zur Lösung eine Set-Partitioning Formulierung, wobei die Berechnung der mitgenommenen Passagiere über ein integriertes Set-Packing Subproblem geschieht.
Aufgrund der geringen Festlegung durch globale Restriktionen ist die Anzahl der möglichen Flugzeugrouten extrem hoch, weil grundsätzlich, abgesehen von Reichweitebedingungen, fast jedes Flugzeug jede Strecke bedienen könnte. Als Konsequenz benutzen wir auch hier einen dynamischen Spaltengenerierungsansatz. Das Subproblem zur Erzeugung neuer Flugzeugumläufe läßt sich dabei wieder als restringiertes Kürzeste Wege-Problem formulieren und mit einem Multi-Label-Algorithmus lösen.
Im Gegensatz zu unseren Erfahrungen mit den Fleet Assignment und den Crew Scheduling Problemen stellt die LP-Relaxierung bei dieser neuen Problemklasse eine schlechte Approximation des Raumes aller möglichen ganzzahligen Lösungen dar. Zur Zeit liegen die nachweisbaren Gütegarantien um 10-15%. Um diese zu verbessern und auch hier Optimalität zu beweisen, arbeiten wir zur Zeit an einem kombinierten Branch-&-Cut-&-Price Ansatz, bei dem das ,,Gap`` durch zusätzliche Schnittebenen verkleinert wird.