Optimierte Güterverkehrsplanung mit Evolutionären Algorithmen

                                  T. Weise u.a.: Optimierte Güterverkehrsplanung mit Evolutionären Algorithmen




                    Optimierte
            Güterverkehrsplanung mit
            Evolutionären Algorithmen
 Thomas Weise, Universität Kassel, Alexander Podlich, Manfred
Menze, Micromata GmbH, Kassel und Christian Gorldt, Universität
                           Bremen

Dipl.-Inf. Thomas Weise arbeitet als wissen-        verglichen. Weiterhin werden unter-        sich. Er muss sehr dynamisch sein um
schaftlicher Mitarbeiter in der Verteilte Systeme
Gruppe der Universität Kassel. Sein Forschungs-     schiedliche Einstellungen für den evo-     auf Verkehrsbehinderungen schnell re-
thema sind Evolutionäre Algorithmen.                lutionären Algorithmus experimentell       agieren und die Route eines Verkehrs-
Dipl.-Inf. Alexander Podlich arbeitet als Soft-     untersucht und deren Nutzbarkeit           trägers zeitnah anpassen zu können.
wareentwickler bei der Firma Micromata GmbH.        durch statistische Tests verifiziert.      Das in diesem Beitrag vorgestellte Sy-
Dipl.-Ing. Manfred Menze arbeitet als Projekt-                                                 stem soll als Unterstützungshilfe für
leiter für Individualsoftware-Projekte mit dem         Mit dem aus dem Handel innerhalb        den Disponenten verstanden werden,
Schwerpunkt Logistik bei der Micromata GmbH
in Kassel.                                          der Europäischen Union und dem glo-        um diesen bei der Zusammenstellung
                                                    balen Import und Export resultierenden     der Tourenpläne zu unterstützen. Die
M.Sc. Christian Gorldt arbeitet als wissen-
schaftlicher Mitarbeiter am BIBA - Bremer           stetig ansteigenden Straßengüterverkehr    Daten stammen aus einem Transports-
Institut für Produktion und Logistik GmbH an        wächst das Bedürfnis einer intelligenten   zenario in dem als Verkehrsträger als
der Universität Bremen im Bereich Intelligente
Produktions- und Logistiksysteme.                   Lösung für die strategische Planung in     Wechselbehälter bezeichnete Contai-
                                                    der Logistik. Solch ein Planungsprozess    ner eingesetzt werden. Wechselbehälter
   In diesem Beitrag wird ein Ansatz                verfolgt die Ziele wie                     werden von Frachtführern per LKW
der Frachttransportplanung mithilfe                 (1) Maximierung der Gewinne bei            transportiert. Pro LKW können zwei
von evolutionären Algorithmen vor-                  (2) Sicherstellung der pünktlichen Ein-    Wechselbehälter befördert werden.
gestellt. Ziel ist es, eine Entschei-                   sammlung und Lieferung aller Gü-           In der Literatur wird im Wesentlichen
dungsunterstützung im Bereich der                       ter und                                zwischen exakten und stochastischen
Transportplanung zu schaffen um die                 (3) Nutzung aller verfügbaren Mög-         Verfahren in der Frachttransportplanung
Disponenten bei der täglichen Planung                   lichkeiten für effiziente Transporte   unterschieden. Insbesondere die zur
zu unterstützen. Ein wichtiges Ziel-                    (Schiene, LKW), d.h. Reduzierung       letzteren Gruppe gehörenden metaheu-
kriterium ist dabei möglichst umwelt-                   der gesamten Transportwege durch       ristischen Ansätze sind in den letzten
schonende Transporte zu disponieren,                    bessere Kapazitätenauslastung.         Jahren populär geworden. Bezogen auf
um so z.B. die Transportleistung (km)               (4) Außerdem soll der CO2 Ausstoß          die existierende Problemstellung bieten
zu minimieren. Der in diesem Beitrag                    reduziert werden, um die Umwelt-       diese im Vergleich zu den klassischen
vorgestellte Prototyp wurde mit realen                  freundlichkeit zu steigern.            Verfahren in einer sehr viel kürzeren Re-
Daten der DHL auf die Eignung in                    Der letzte Punkt ist in diesem Zu-         chenzeit eine sehr gute Lösungsqualität.
der Transportplanung getestet. Die                  sammenhang als Nebeneffekt der an-         Bekannte Ansätze für unterschiedliche
Ergebnisse der Berechnung werden                    deren Ziele zu sehen, da z.B. die          Arten von Tourenplanungsproblemen
dabei mit den realen Frachtplänen                   Nutzung des Transportträgers Schiene       und Frachttransportplanungen sind u.
                                                    die Reduzierung der Lenkzeiten der         a. die Tabu-Suche [1-4], Simulated
                                    Kontakt:        LKW-Fahrer ermöglicht. Jedoch stehen       Annealing [5, 6], Ameisensysteme [7,
                    Alexander Podlich               nicht ausschließlich die ökonomischen      8] und insbesondere die evolutionären
                    Micromata GmbH                  Gesichtspunkte (z.B. Personalkosten)       Algorithmen [9-12]. Die genannten
                 Marie-Calm-Straße 3                im Vordergrund. Auch ökologische           Veröffentlichungen betrachten jedoch
                         34131 Kassel               Zielgrößen werden bei der Planung          meist spezielle Probleme des Tourenpla-
                     0561 / 31679327                berücksichtigt.                            nungsproblems und beschäftigen sich
     E-Mail: a.podlich@micromata.de                    Ein effizienter Frachtplanungspro-      oft mit der geeigneten Implementierung
       URL: http://www.micromata.de                 zess bringt weitere Besonderheiten mit     von Nebenbedienungen. Die Größe der



© GITO-Verlag                                                                                                                        37
Transport-und Lagerplanung


betrachteten Tourenplanungsprobleme        eine Vermischung des Erbgutes beider       onäre Zyklus beginnt in der nächsten
ist meist auf ungefähr 100 Kunden          Elternteile, auch Rekombination oder       Generation mit der Evaluierung der
oder Aufträge begrenzt [13,14]. Um         Crossover genannt, statt. Da auch auf      neu erzeugten Population von vorne
die oben genannten Verfahren effek-        die Nachkommengeneration wieder Se-        und setzt sich fort, bis eine ausreichend
tiv zu nutzen ist weiterhin umfang-        lektionsdruck lastet und wieder nur die    gute Lösung gefunden wurde oder
reiches Wissen über die Aufgabenstel-      am besten angepassten Individuen ihre      ein anderes Abbruchkriterium, wie der
lung (auch: Domänenwissen) bzw. über       Eigenschaften weiter vererben können,      Ablauf einer vordefinierten, maximalen
das Szenario notwendig [15,16]. Die        findet eine langsame Anpassung der         Laufzeit, eingetreten ist.
in diesem Betrag vorgestellte Methode      Lebewesen an ihre Umgebung statt aus
integriert Domänenwissen in speziell       der aber auch selten sprunghaft gänz-               Struktur des
einen für die Tourenplanung- und Op-       lich neue Charakteristika hervorgehen            Anwendungsbeispiels
timierung entwickelten evolutionären       können.
Algorithmus. Dabei zeigte sich, dass          Dieser natürliche Kreislauf aus „Eva-      Eine der ersten Entscheidungen, die
dieser Ansatz bei nahezu beliebigen        luierung“ der Individuen, Selektion und    bei der Verwendung eines evolutionären
Einstellungen klassischen Verfahren fast   Fortpflanzung (Mutation, Rekombina-        Algorithmus zu treffen sind, ist die Ko-
immer überlegen ist und Einsparungen       tion) [17,18] wird in evolutionären        dierung der Lösungskandidaten. Um
in der Gesamtfahrstrecke von bis zu        Algorithmen (EAs) nachempfunden, um        die aus der Praxis gestellte, komplexe
16 % erzielen kann.                        schwierigste Problemstellungen zu lö-      logistische Planungsaufgabe zu lösen,
                                           sen. Wie die natürliche Evolution ar-      können traditionelle Kodierungen, wie
     Evolutionäre Algorithmen              beiten auch EAs auf einer Menge von        z.B. binäre Verschlüsselung [19], ein-
                                           Lösungskandidaten, der sogenannten         fache Zahlenfelder, Matrizen oder reale
   Evolutionäre Algorithmen sind Op-       Population. Jede Iteration (Generation)    Vektoren nicht verwendet werden. Für
timierungsverfahren, die sich an dem       eines EAs beginnt mit der Evaluierung      die Tourenplanung und -optimierung
Vorbild der biologischen Evolution         aller Individuen der Population hin-       muss ein Tourenplan ermittelt wer-
orientieren. Die natürliche Evolution      sichtlich der Zielkriterien des Optimie-   den, welcher unter Beachtung von
beruht auf wenigen einfachen Me-           rungsprozesses, welche als Funktionen      zeitlichen, räumlichen, materiellen und
chanismen. Zum einen stehen Orga-          definiert sind. Abhängig von diesen        logistischen einschränkenden Bedin-
nismen im ständigen Wettstreit um          Ergebnissen wird jedem Lösungskandi-       gungen gültig, d.h. durchführbar, ist
überlebenswichtige Ressourcen. Dabei       daten eine relative Fitness zugeordnet.    und eine fristgerechte Transportauf-
haben diejenigen, welche am besten an      Diese Fitnesswerte bildet die Grundlage    tragserfüllung sicherstellt. Im Rahmen
ihre Umwelt angepasst sind, die besten     für einen Selektionsprozess, der die       dieser Problemstellung wurden hier die
Chancen, diesem Selektionsdruck stand-     besten Individuen mit einer hohen          Lösungskandidaten als eine Menge von
zuhalten. Sie können sich fortpflanzen     Wahrscheinlichkeit auswählt und den        Tourenplänen (Phänotyp R) modelliert.

Lesen Sie weiter im PDF