\documentstyle[din_a4, anwendungsbericht]{article}
\begin{document}
%\leftpicture{zprlogo.eps}
\kopf{10}

\mbox{                                              % NICHT AENDERN !!
  \begin{minipage}[b]{7cm}                         % NICHT AENDERN !!
%BEGIN TEXT             
    \begin{center}
      \
      \epsfxsize=4cm
      \epsfbox{optilrv-logo.ps}
    \end{center}    
    { Das Projekt {\it Optimale Linienf"uhrung und Routenplanung im
        Verkehr} (kurz: OptiLRV) wird vom Bundesministerium f"ur
      Bildung und Forschung (BMBF) gef"ordert. Es handelt sich hierbei
      um ein Teilvorhaben des BMBF--F"orderprogrammes {\it
        Anwendungsorientierte Verbundvorhaben auf dem Gebiet der
        Mathematik}. In diesem Programm werden mathematische
      Forschungsvorhaben gef"ordert, die einen sehr konkreten
      Praxisbezug nachweisen k"onnen.}
  \end{minipage}                                   % NICHT AENDERN !!
  \hspace{5.1mm}                                   % NICHT AENDERN !!
%  \fbox{\rule{0cm}{7.5cm}\makebox[5cm]{Photo: kommissionierte Palette}}
    \epsfxsize=8cm
    \epsfbox{profis-bild1.ps}
  % alternativ: epsf-File der selben Groesse
}


\section*{Projektbeschreibung}

Ziel des Projektes OptiLRV ist die Entwicklung eines Softwarepaketes
zur zentralen Disposition der Transportauftr"age aus den neun deutschen
Niederlassungen der Gerresheimer Glas AG. In Gerresheim werden z.Zt.
die Transportauftr"age aus drei Niederlassungen gemeinsam disponiert. Bei
den Auftr"agen handelt es sich zu "uber 90 \% um Komplettladungen, die
vom Werk bzw. Lager direkt zum Kunden gebracht werden m"ussen.

Die Tourenplanung geschieht im Laufe eines Tages f"ur den n"achsten
Tag bzw. f"ur die Verladung am selben Abend.  Es wird eine
Wochenplanung durchgef"uhrt, so da"s die Fahrer m"oglichst am
Wochenende (evtl. auch 1-2 mal in der Woche) zu Hause sein k"onnen.
Bei der Routenplanung -- vor allem f"ur die Tage Donnerstag und
Freitag -- sind also die Heimatstandorte der Fahrzeuge stark zu
beachten.

Zentrales Thema in diesem Projekt ist die Online--Disposition, da sich
w"ahrend eines Tages die Auftragslage laufend durch Stornierungen,
Umbuchungen und zus"atzliche kurzfristige Zusatzbuchungen ver"andert.
Das zu erstellende Softwarepaket soll dem Disponenten als
Planungsinstrument an die Hand gegeben werden, um ihm einen "Uberblick
"uber die schon geplanten Touren zu geben und auf Knopfdruck f"ur die
aktuelle Auftragslage aus dem bisherigen Informationsstand einen
optimalen Tourenplan zu erstellen.


Es wurde eine Rohversion des Programmes erstellt, in dem die
Stammdatenverwaltung incl.~Datenbankanschlu"s und deren Schnittstelle
zu den Algorithmenmodulen implementiert wurde. Durch die Nutzung von
C++ als Programmiersprache und der GUI--Klassenbibliothek XVT ist das
Programm plattformunabh"angig und das Benutzerinterface
fensterorientiert. Um auf die gro"sen Datenfiles der Ortsdatenbank und
der Distanzmatrix in kurzer Zeit zugreifen zu k"onnen, wurde die
Struktur der Cache--Arrays entwickelt.

Bisher wurde das Simulated--Trading--Verfahren eingebunden, f"ur das
die Kostenfunktionen noch genau modelliert und an das praktische
Problem angepa"st werden m"ussen.  In der Modellierungsphase befindet
sich ein Algorithmus auf Basis von Matchingsuche in bipartiten
Graphen.
       

\section*{Mathematische Modellierung}


Das Dispositionsproblem der Gerresheimer Glas AG kann als
Vehicle-Routing-Problem mit Pick--Up--and--Delivery--Auftr"agen
incl. Zeitfensterrestriktionen aufgefa"st werden, dem eine
zeitabh"angige Distanzmatrix zugrundeliegt. Der allgemeine
L"osungsansatz basiert auf dem am Lehrstuhl von Prof.~Bachem
entwickelten Simulated--Trading--Verfahren.

\subsubsection*{Das Simulated--Trading--Verfahren}

Im Simulated--Trading--Verfahren werden die einzelnen Touren als {\it
  H"andler} angesehen. Diese k"onnen Auftr"age an eine {\it B"orse}
verkaufen (zu den Kosten, die sie durch Nichtausf"uhrung des Auftrages
einsparen) und an der B"orse angebotene Auftr"age kaufen (zu den
Kosten, die sie f"ur die Ausf"uhrung des Auftrages ben"otigen). Im
B"orsenmodul wird dann ein sogenannter Trading--Graph erstellt,
in dem der optimale zul"assige Austausch von angebotenen Auftr"agen
zwischen den Touren bestimmt wird. In den Touren werden den zum Tausch
in Frage kommenden Auftr"agen entsprechend ihrer G"ute
Wahrscheinlichkeiten zugeordnet und die Auswahl der Auftr"age damit
randomisiert durchgef"uhrt. Dadurch werden erfolgversprechende
Aktionen h"aufiger durchgef"uhrt und das Festh"angen in statischen
Situationen verhindert.\\ 

\noindent 
%
Da bei der Gerresheimer Glas AG zum gr"o"sten Teil Komplettladungen
disponiert werden, bestehen "Uberlegungen, dieses
Tourenplanungsproblem als Matchingproblem zu formulieren.

\subsubsection*{Der Matching--Ansatz}

Ziel bei diesem Ansatz ist die Minimierung von gefahrenen
Leerkilometern. Als Knotenmengen des dem Problem zugrundeliegenden
Graphen werden die Auf-- und Abladestellen der zu betrachtenden
Auftr"age angenommen, wobei f"ur jeden Auftrag genau ein Auf-- und ein
Ablade--Knoten angelegt wird. Kanten zwischen einer Ab-- und einer
Aufladestelle werden eingef"ugt, wenn der aufzuladende Auftrag nach
dem abgeladenen Auftrag durchgef"uhrt werden kann, d.h.~wenn der
Beladezeitpunkt des auszuf"uhrenden Auftrages sp"ater liegt als der
Abladezeitpunkt des ausgef"uhrten Auftrages plus die Fahrtzeit von der
Ab-- zur Aufladestelle. Hierbei ist die Berechnung der Fahrtzeiten und
der Auf-- und Abladezeiten von gro"ser Wichtigkeit. Um die Fahrtzeiten
korrekt berechnen zu k"onnen, mu"s eine zeitabh"angige Distanzmatrix
zugrundegelegt werden. Die Kanten werden mit Kosten bewertet, die die
gefahrenen Leerkilometer ber"ucksichtigen. Au"serdem mu"s in diese
Kosten die Wartezeit einkalkuliert werden, bis der folgende Auftrag
durchgef"uhrt werden kann.

Durch diese Konstruktion entsteht ein bipartiter Graph mit bewerteten
Kanten, in dem ein minimal gewichtetes Matching gesucht wird.

\section*{Realisierung}

Parallel zur Erarbeitung der mathematischen Modelle zur L"osung des
Dispositionsproblemes wurden im Projekt die Grundlagen f"ur die
Realisierung des Programmes konzipiert. Der entstehende Programmcode
soll plattformunabh"angig sein und das Benutzerinterface fensterorientiert
implementiert werden. Deshalb wird die Programmiersprache C++ und die
plattform"ubergreifende GUI--Klassenbibliothek XVT eingesetzt.

Zun"achst wurde der grundlegende Aufbau des Programmes im Modulkonzept
festgelegt. Das Konzept ist auf ein allgemeines Dispositionspaket hin
ausgelegt. Es soll m"oglich sein, verschiedene Algorithmen einfach
einzuh"angen oder Zusatzmodule wie die Laderaumoptimierung zu
integrieren.

\noindent
\rule{\textwidth}{1pt}
{\Large \bf Ansprechpartner}                       % NICHT AENDERN !!

\begin{tabbing}
Herr Raspel \hspace*{3cm} \=  Dipl.-Math.~Anja Hamacher \\
\> \\
Gerresheimer Glas AG \> Zentrum f\"ur Paralleles Rechnen\\
\> Universit\"at zu K\"oln \\
\\
Tel.: 0211/2809-2698 \> Tel.: 0221/470-6011 \\
Fax: 0211/2809-441 \> Fax: 0221/470-5160 \\
 \> E-Mail: ahamach@ZPR.Uni-Koeln.DE \\
\end{tabbing}

\noindent
Stand: 22.03.1995

\end{document}
