\documentclass[11pt]{article}
\usepackage{german}
\usepackage{epsfig}
\usepackage{anwendungsbericht-inf}

%%% document format
\oddsidemargin 0cm
\evensidemargin 0cm
\topmargin -1cm
\textheight 9in % = 22.86cm, 48\baselineskip
\textwidth 6.25in % = 15.875cm, 6.5in = 16.51cm
\frenchspacing
\sloppy
\parindent 0pt
\parskip .3\baselineskip
%%%
\thispagestyle{empty}
\pagestyle{empty}


\begin{document}
\kooperationspartner{(in Kooperartion mit 
  Lufthansa Systems und anderen Universit"aten)}
\leftpicture{inf-logo1.ps}
\arbeitsgruppe{Prof. Dr. R. Schrader}
\telefon{470--6030}
\telefax{470--5160}
\kopf{24}

\begin{minipage}[c]{67mm}
  \begin{center}
    %% \fbox{\rule{0cm}{3cm}\makebox[5cm]{LOGO}}
    \epsfig{file=lhsystems-logo.ps,width=55mm}
  \end{center}
  Die Lufthansa bietet w"ochentlich knapp 10.000 Fl"uge an. Jeder einzelne 
  mu"s von einem der rund 250 Flugzeuge der Flotte geflogen werden.

  Flugzeuge unterscheiden sich nicht nur in der Kapazit"at, also der Anzahl
  der Passagiere, die ein Flugzeug bef"ordern kann, oder der maximalen
  Reichweite, sondern auch in den Kosten, die ein Flugzeug pro geflogenem
  Kilometer und bef"ordertem  Passagier verursacht.
  Untersuchungen haben ergeben, da"s jede Woche einige Fl"uge, zumindest in
  der gewinnbringenden Business-Class, "uberbucht werden, w"ahrend andere
  Fl"uge nicht voll ausgenutzt werden.
\end{minipage}
\hfill
\begin{minipage}[c]{85mm}
  \epsfig{file=world.ps,width=\textwidth}
\end{minipage}

Ziel ist es, durch geschicktes Eingreifen in den
Flugplan - d.h. durch kleinere Verschiebungen der Flugzeiten oder durch
geschicktere Wahl des Flugzeugs, das einen angebotenen Flug bedient - die
Auslastungen der Fl"uge zu verbessern, um so f"ur das Unternehmen eine
Gewinnsteigerung zu erm"oglichen.

\subsection*{Problemstellung}

Bei einem gegebenen Flugplan wird einerseits versucht, durch Ver"anderungen
der Abflugzeiten die Anschl"usse zu optimieren und andererseits durch eine
neue Zuordnung von Flugzeugen zu Flugstrecken eine bessere Auslastung
einzelner Flugzeuge zu erreichen. 

Bei der Verschiebung der Abflugzeiten mu"s sowohl das geltende Recht auf
den Abflugh"afen als auch die Gew"ahrleistung der garantierten
Folgeanschl"usse als Nebenbedingung ber"ucksichtigt werden.

Bei der Flottenzuweisung m"ussen neben offensichtlichen Nebenbedingungen
(Reichweiten etc.), sehr viele subtile beachtet werden
(z.~B. Wartungspl"ane). Da  der Plan sich f"ur Flugzeugtypen unterscheidet,
ist die Rundflugperiode einzelner Flugzeugtypen unterschiedlich. Dar"uber
hinaus bietet der Flugplan Hinweise auf einen sp"ateren
Personaleinsatzplan. Bereits bei der Flottenzuweisung m"ussen elementare
Personalrestriktionen beachtet werden. Die Arbeitsgruppe von
Prof.~R.~Schrader besch"aftigt sich haupts"achlich mit der
Flottenzuweisung. 

\subsection*{Mathematische Modellierung}

Das zugrundeliegende mathematische Problem besteht darin, eine Zuordnung
von Flugzeugen beziehungsweise Flugzeugtypen zu Fl"ugen zu suchen, die den
Gesamtgewinn maximiert. 

Die Untersuchung verschiedener Modellformulierungen und ihrer praktischen
L"osungsm"oglichkeiten hat ergeben, da"s eine Formulierung des Fleet
Assignment Problems als ein Mehrg"uterflu"sproblem mit Nebenbedingungen am
geeignetsten ist. 
%%% 
Hervorzuheben ist, da"s bei der gew"ahlten Modellformulierung eine 
praxisrelevante Tatsache Ber"ucksichtigung findet, die bisher in der
Forschung zur L"osung des Fleet Assignment Problems v"ollig vernachl"assigt
wurde, da das Problem dadurch wesentlich komplexer wird. Die Erl"ose sind
in der Flugplanung nicht in der Form von Erl"osen pro Flug, sondern in
Erl"osen pro Reiseroute (die  in der Regel aus mehreren Fl"ugen besteht) 
gegeben. Unsere Modellformulierung erlaubt es, auch diese komplexere
Fragestellung zu l"osen.

Restriktionen wie Gew"ahrleistung der Wartung, Reichweite, Flottengr"o"sen,
Periodizit"at werden als zus"atzliche Nebenbedingungen in die Formulierung
aufgenommen. In einem weiteren Schritt, dem Crew Assignment, wird auch der
Personaleinsatz ber"ucksichtigt.

\subsection*{Algorithmen}

Zur (exakten) L"osung von kleinen Instanzen der oben genannten Probleme
k"onnen die Methoden der ganzzahligen Linearen Programmierung angewandt
werden, etwa durch Verwendung von kommerziellen LP-L"osern wie
CPLEX\footnote{CPLEX Optimization, \texttt{http://www.cplex.com/}}.
Die Komplexit"at des Problems l"a"st dieses direkte Vorgehen bei den uns
vorliegenden Problemgr"o"sen jedoch nicht mehr zu.

Von uns entwickelte  "`opening heuristics"' versuchen eine erste
m"oglichst gute und zul"assige Flottenzuweisung zu generieren; dies
geschieht mit Kreis"uberdeckungsalgorithmen, die das Flugnetz in Kreise
(i.~e. in Touren einzelner Flugzeuge) zerlegen, und mit
Netzwerkflu"salgorithmen, die auf Teilprobleme mit weniger Flotten
("`divide-and-conquer"'-Prinzip) angewandt werden.

Ausgehend von diesen so erhaltenen Flottenzuweisungen werden nun zum einen 
Verbesserungsheuristiken (wie z.~B. Simulated Annealing oder Genetische
Algorithmen) verwendet. 

Eine andere M"oglichkeit bietet der Column Generation-Ansatz: hier wird
eine geeignete Formulierung des Problems als Lineares Programm (LP)
verwendet, in der jedoch nur eine Teilmenge der m"oglichen Spalten direkt
erzeugt wird. Dadurch ist das LP (das sog. Master-Problem) klein genug, um
effizient mit Simplexalgorithmen gel"ost zu werden. Bei Bedarf werden
dann in Subproblemen neue Spalten erzeugt und diesem LP hinzugef"ugt. Diese
Subprobleme sind in unserem Ansatz Netzwerkflu"sprobleme mit
Nebenbedingungen, die durch Netzwerkalgorithmen (z.~B. Algorithmen auf der
Basis von cost-scaling- und Netzwerksimplexalgorithmen)  effizient gel"ost
werden k"onnen. Um die ben"otigte Ganzzahligkeit der L"osungen
sicherzustellen, werden Branch-and-Bound- und Rundungsstrategien
angewandt. 

Lagrange-Relaxierung ist eine Technik, mit der Schranken f"ur den
Zielfunktionswert berechnet werden k"onnen, die dann zur G"uteabsch"atzung
verwendet werden. Einige Nebenbedingungen werden in die Zielfunktion
aufgenommen, so da"s das Problem wieder in leichtere Subprobleme
zerf"allt. Tats"achlich erhalten wir hier wieder Netzwerkflu"sprobleme als
Subprobleme, die sich wieder mit den oben angesprochenen Methoden l"osen
lassen.


\subsection*{Allgemeine Ergebnisse}

Ziel des Projektes ist es, ein Programmpaket zu erstellen, mit dessen
Hilfe Flugplaner sowohl mittelfristige Flugplan"anderungen durchf"uhren
als auch langfristig hypothetische Szenarien nach ihrer Wirtschaftlichkeit
pr"ufen k"onnen. 
%%%
Durch eine Workbench mit grafischer Benutzeroberfl"ache ist es m"oglich,
s"amtliche implementierte Algorithmen zu starten und zu steuern,
"Anderungen an den Pl"anen per Hand vorzunehmen und die Ergebnisse auf
mehrere verschiedene Arten anzuzeigen (geographische Sicht, als
Gantt-Diagramm, Listen, etc.).  
Verschiedene Rechnerarchitekturen (sequentiell/parallel; PC, Sun, IBM, ...)
werden dabei gleicherma"sen unterst"utzt.


\subsection*{Ergebnisse der Algorithmen}

Zur Entwicklung und zum Vergleich der Algorithmen liegen uns mehrere
Realworld-Datens"atze vor: 
kleine "`interkontinentale"' Datens"atze mit 300 bis 3.500 Flugstrecken,
bis zu 5 verschiedenen Flugzeugtypen und bis zu 50.000 Reiserouten, 
aber auch sehr gro"se "`europ"aische Wochenflugpl"ane"' mit 7.500
Flugstrecken, 35 verschiedenen Flugzeugtypen und 500.000 Reiserouten.
(Im Vergleich dazu: der typische US-amerikanische Flugplan ist ein
Tagesflugplan mit 2.500 Flugteilstrecken, 11 Flugzeugtypen; dieser wird 
"uber lineare Kosten auf den Flugstrecken und nicht "uber Reiserouten
bewertet. Siehe hierzu z.~B. die Artikel von  Prof. Cynthia Barnhart (MIT)
und anderen in Zusammenarbeit mit United Airlines und 
Prof. Soumis (GERAD) und anderen in Zusammenarbeit mit Air France.)

Unter Verwendung der oben angesprochenen Algorithmen ist es uns m"oglich,
s"amtliche Datens"atze optimal bzw. ann"ahernd optimal zu l"osen, wobei die
G"utegarantie durch Lagrangerelaxierung bzw. die (fraktionalen) L"osung des
LPs berechnet wird. \\

F"ur Details und weitere Informationen wenden Sie sich bitte an die unten
angegebenen Ansprechpartner.

\vspace*{3cm}

\noindent\rule{\textwidth}{1pt}

\vspace*{10pt}

\noindent{\Large \bf Ansprechpartner}

\vspace*{10pt}

\noindent
Dipl.-Math. Andreas Erdmann (erdmann@zpr.uni-koeln.de)\\
Dr. rer. nat. Andreas Nolte (nolte@zpr.uni-koeln.de)\\[3mm]
Zentrum f"ur Paralleles Rechnen\\
Universit"at zu K"oln \\
Weyertal 80 \\
50931 K"oln \\
Tel: 0221/470-6030\\
Fax: 0221/470-5160
\end{document}




\newpage{}

\begin{table}[htbp]
\begin{center}
\leavevmode
\begin{tabular}[h]{|l||r|r|r|r|r|}\hline
  Data Set & Legs & Flugh"afen & Flotten & Flugzeuge & Reiserouten 
  \\\hline\hline 
%%%
  icont/3 & & & & &\\ 
  icont/4 & & & & &\\\hline
%%%
  all/2 & & & & &\\
  all/4 & & & & &\\
  all/8 & & & & &\\
  all/16 & & & & &\\
  all & & & & &\\\hline
%%%
  gen/4 & & & & &\\
  gen/5 & & & & &\\
  gen/8 & & & & &\\\hline
\end{tabular}
\caption{Datens"atze}
\label{tab:datasets}
\end{center}
\end{table}

Datens"atze:\\

{\tiny
Mit linearer Kostenfunktion: \\
\begin{tabular}[h]{|l||r||r|r||r||r|r||r|r||r|}\hline
  Data Set & LP & LP-round & \% & optimum & heuristic & \% & lagrange
  & \% & Initial \\\hline\hline
  %%%
icont/3 & 17.796.295 & 17.796.295  & 100 & 17.796.295 & 15.882.375  & 89 &
          18.503.629 &  96 & 14.258.272\\
icont/4 & 10.268.689 & 10.266.935  & 99 & 10.268.474 & 7.877.828 & 76 &
          10.664.293 & 94 & 7.473.415\\
all/2 &   81.964.969 & & & & 74.695.231 & 91 & & & \\
all/4 &   87.366.476 & 86.257.310 & 99 & & 79.368.125 & 90 &
          88.321.461 & 98 &\\ 
all/8 &   88.168.039 & 86.963.472 & 98 & & 81.523.618 & 92 &  
          90.364.879 & 97 &\\ 
all/16 &  102.796.509 & 97.841.692 & 95 & & & & 103.156.942 & 94 & \\
all    &              &110.745.619 & & & 98.267.541 & 98 & 113.249.526 & 97
          & 71.221.696 \\
gen/4 &  156.234 & 151.231 & 98 & 154.286 & 152.264 & 98 & 155.932 &  98 &\\
gen/5 &  628.479 & 621.459 & 99 & 625.793 & & & 629.264 & 98 &\\
gen/8 &1.359.657 & 1.352.694 & 99 & & 1.311.817 & 95 & 1.359.943 & 99 &\\\hline
\end{tabular}

Mit Reiserouten-Kostenfunktion:\\
\begin{tabular}[h]{|l||r||r|r||r||r|r||r|r|}\hline
  Data Set & LP & LP-round & \% & optimum & heuristic & \% & lagrange
  & \% \\\hline\hline
  %%%
icont/3 & 41.559.432 & 39.516.234 & 96 & 40.968.457 & 37.912.540 & 
          92 &  43.213.684 &  94\\
icont/4 & 38.178.647 & 37.203.546 & 98 & 37.703.421 & 31.907.619 & 
          85 &  40.398.421 & 93\\
all/2 & 75.316.498 & 70.019.361 & 93 & 74.186.795 & 62.310.437 & 84 &
          68.708.003 & 92\\
all/4 & 78.624.198 & 74.046.880 & 94 & &  66.770.541 & 85 & 87.272.859 & 90\\
all/8 & 79.526.487 & 76.241.420 & 96 & &  68.731.272 & 86 & 89.355.603 & 89\\
all/16& 89.532.461 & 85.219.579 & 95 & &             &    & 97.342.492 & 92\\
all   &            & 98.546.937 &    & &  93.412.685 &    &116.988.294 &
          84\\\hline
\end{tabular}
}

