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.