\documentstyle[din_a4, german, epsf, anwendungsbericht]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Beispiel fuer das Layout eines Anwendungsberichts des ZPR
% 30.11.94 MW
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frenchspacing
\parindent 0pt
\parskip 5pt

\begin{document}

\kopf{18}

\mbox{
  \begin{tabular}[b]{c}
      \epsfxsize=4cm
      \epsfbox{profis-logo.ps}\\
      {\bf \LARGE Packverfahren f"ur Artikel} \\ 
      {\bf \LARGE mit komplexer Geometrie} \\
      \ \\
      \
  \end{tabular}
  \hspace*{7mm}
  \hfill
      \epsfxsize=2.5cm
      \epsfbox{profis2-bild1.ps} \
      \epsfxsize=2.5cm
      \epsfbox{profis2-bild2.ps} \
      \epsfxsize=2.5cm
      \epsfbox{profis2-bild3.ps} \
}

    F"ur Hersteller von Artikeln mit komplexer Geometrie wie z.B. 
    Badewannen und Duschwannen stellt sich das Problem,
    t"aglich mehrere Hundert Euro--Paletten optimal verpackt
    an Zwischenh"andler verschicken
    zu m"ussen. Dabei ist die Anzahl und die Art der jeweils bestellten
    Artikel abh"angig von der Auftragslage und der Produktion, so da"s
    der Planungshorizont bei wenigen Tagen liegt.
    Die Wannen werden entweder als Vollpaletten eines Fabrikats, als
    kommissionierte Badewannen- oder Duschwannenpaletten oder als
    kombinierte Badewannen--Duschwannen--Kommissionierpalette ausgeliefert.

    Bei der gro"sen Zahl an t"aglich zu verladenden Paletten ergibt sich
    in verschiedenen Phasen der Verwaltung (Neben der Versandabteilung
    z.B. auch im Vertrieb)
    die Notwendigkeit, die f"ur den momentanen Auftragsbestand
    notwendige Anzahl Paletten zu bestimmen mit dem Ziel, t"aglich m"oglichst
    viele Wannen zu verschicken. Als Nebenbedingungen treten
    dabei unter anderem Gewichts- und Stabilit"atsrestriktionen auf.
%  \fbox{\rule{0cm}{7.5cm}\makebox[5cm]{Zeichnung: kommissionierte Palette}}
  \hspace{5.1mm}                                 

\section*{Problemstellung}

Zu gegebenen Auftragspositionen wird versucht, m"oglichst wenig Paletten 
zu benutzen, und infolgedessen die Fahrzeuge m"oglichst gut auszulasten. 
Da Vollpaletten eines Modells optimal gepackt sind, k"onnen sie im Vorfeld
herausgesucht werden und gehen nicht in das Packproblem ein.
Aus Gr"unden der Stabilit"at d"urfen Badewannen und Duschwannen nicht
beliebig aufeinander gestapelt werden, sondern es ist notwendig, zuerst den 
Palettenplatz von Duschwannen und Badewannen getrennt zu optimieren,
und erst die "ubrigbleibenden Teilpaletten in der heterogenen 
Kommissionierung zu bearbeiten.\\
Die Badewannen stehen dabei jeweils senkrecht auf den Paletten, die Duschwannen
werden liegend ausgeliefert. Bei heterogener Kommissionierung werden die 
"ubriggebliebenen Duschwannen auf die angefangenen Badewannenpaletten 
hinzugestellt. Jede Wanne kann in jede andere gestapelt verschickt werden.
Somit basieren die homogenen Packungsverfahren auf einer vollst"andigen 
Abstandsmatrix, die eventuell an einigen Stellen sehr hohe Werte enth"alt.

\section*{Mathematische Modellierung}

Das zugrundeliegende mathematische Problem bei der homogenen Packung 
ist ein Verpackungsproblem mit nachfolgerabh"angigen Gr"o"sen 
der einzelnen Teile. Es l"a"st sich somit einerseits als spezielles 
eindimensionales Bin--Packing Problem ansehen, andererseits aber auch 
als Vehicle Routing Problem. Dabei nehmen die Paletten die Rolle der 
Fahrzeuge ein und die Palettenenden die Rolle des Depots. 
Gegen"uber dem Standard--VRP ist allerdings die Minimierung der 
Tourl"ange nicht Bestandteil der Zielfunktion, und die einzige 
Nebenbedingung ist die Kapazit"atsbeschr"ankung.

\newpage

\epsfxsize=7cm
\begin{table}
  \begin{center}
    \
    \epsfbox{profis2-bild4.ps}
  \end{center}
\caption{Struktur des Pack--Verfahrens}
\end{table}

\section*{Algorithmen}
F"ur die homogenen Packungsprobleme wurden drei algorithmische Ans"atze
untersucht:
\newcounter{liste}
\begin{list}{\arabic{liste}.}{\usecounter{liste} 
                   \itemsep0cm \parsep0cm \topsep0cm \parskip0cm \partopsep0cm}
  \item Greedy--Heuristiken "ahnlich der First--Fit--Heuristik 
    (First--Fit--Decreasing, Best--Fit--Decr., etc.),
  \item Vehicle Routing Algorithmen f"ur die vorliegende spezielle Zielfunktion
    (nur die Touranzahl wird minimiert) aus dem Bereich der Savings-- und 
    Insertion--Verfahren, sowie
  \item Enumerationsverfahren (nur f"ur Probleme mit wenigen Wannen)
\end{list}
Die heterogenen Packverfahren sind meist f"ur wesentlich kleinere Probleme
zu l"osen und obendrein sehr stark von durch die Stabilit"ats-- und 
Gewichtsnebenbedingungen begr"undeten Regeln dominiert. 
Deshalb f"uhrt hier schon eine einfache Kombination aus einer 
Standard--Greedy--Heuristik und der vollst"andigen Suche zum Erfolg.

\section*{Ergebnisse}
Analysen der Algorithmen haben gezeigt, da"s bei kleinen Praxisproblemen
die Greedy--Verfahren in nahezu allen F"allen schon das Optimum liefern.
Durch die Nebenbedingungen und die D"unnbesetztheit der Matrizen ist 
der L"osungsraum so eingeschr"ankt, da"s mit Heuristiken gute Ergebnisse 
erzeilt werden k"onnen. 
Der Einsatz von Vehicle--Routing Verfahren ist f"ur dieses Problem m"oglich,
er ist jedoch speziell optimierten Fit--Heuristiken unterlegen.

Die entwickelten Verfahren wurden inzwischen von Profi.S implementiert
und werden von einem gro"sen deutschen Wannenhersteller erfolgreich
eingesetzt. Die Laufzeit f"ur eine Tour betr"agt dabei nur wenige 
Zehntel Sekunden.

\rule{\textwidth}{1pt}                    

{\Large \bf Ansprechpartner}              

\begin{tabular}{lll}                       
Dipl.--Math. Michael Wi"sborn             & 
                        \multicolumn{2}{l}{Dipl.--Math. J"org Schepers}      \\
                      & \multicolumn{2}{l}{Dipl.--Math. Michael Wottawa}     \\
Profi.S --- Gesellschaft f"ur logistische & 
                        \multicolumn{2}{l}{Zentrum f"ur Paralleles Rechnen}  \\
Softwareentwicklung und Operations Research mbH \hspace{1cm} 
                      & \multicolumn{2}{l}{Universit"at zu K"oln}            \\
Berghauser Str. 62    & \multicolumn{2}{l}{Weyertal 80}                      \\
42859 Remscheid       & \multicolumn{2}{l}{50931 K"oln}                      \\
Tel: 02191/900-418    & \multicolumn{2}{l}{Tel: 0221/470-6022}               \\
Fax: 02191/900-412    & \multicolumn{2}{l}{Fax: 0221/470-5160}               \\
                      & E-Mail: & schepers@ZPR.Uni-Koeln.DE                  \\
                      &         & wottawa@ZPR.Uni-Koeln.DE                   \\
\\
K"oln, \today.
\end{tabular}                               

\end{document}

