Modulare Fahrzeuge revolutionieren die Effizienz bei der Frachtlieferung

Jüngste Fortschritte zeigen, dass modulare Fahrzeuge (MVs) die Transportsysteme verbessern können, weil sie während einer Fahrt zusammenschliessen und sich wieder trennen können. Auch wenn MVs in verschiedenen Bereichen untersucht wurden, wurde ihre Nutzung in der Logistik, speziell für die Lieferung von Fracht, bisher nicht viel beleuchtet. Diese Studie schaut sich an, wie MVs für die Frachtlieferung eingesetzt werden können, um Geld zu sparen. Wir betrachten das Problem der Güterlieferung mit MVs als eine neue Version des Vehicle Routing Problems, das wir das Modular Vehicle Routing Problem (MVRP) nennen.

Im MVRP können MVs entweder selbstständig an Kunden liefern oder sich mit anderen MVs zusammenschliessen, um eine Gruppe zu bilden, was hilft, die Kosten zu senken. Um dieses Problem zu lösen, haben wir zuerst ein Mixed Integer Linear Programming-Modell erstellt, das mit kommerziellen Optimierungstools gelöst werden kann. Da das Problem ziemlich komplex sein kann, haben wir auch einen Tabu-Suchalgorithmus (TS) mit speziellen Werkzeugen für den MVRP entwickelt. Um zu vermeiden, dass wir in lokalen Lösungen stecken bleiben, haben wir Strategien in unseren TS-Algorithmus eingebaut.

Zusätzlich haben wir verschiedene Anwendungsmöglichkeiten des MVRP in der Logistik untersucht. Die Ergebnisse unserer Tests zeigen, dass der vorgeschlagene Algorithmus effektiv optimale Lösungen für kleinere Probleme findet und auch in grösseren Fällen gut abschneidet. Unsere Methode kann im Vergleich zu traditionellen Liefermethoden etwa 5 % an Kosten sparen. Der Code und die Daten, die in dieser Arbeit verwendet wurden, werden bereitgestellt, sobald das Papier akzeptiert wird.

#Einführung

Das schnelle Wachstum beim Online-Shopping und in lokalen Geschäften hat die Nachfrage nach besseren Lieferdiensten in Städten erhöht. Normalerweise beinhalten die Stadtlogistik grössere Lastwagen, die Waren zu zentralen Hubs bringen, von wo aus kleinere Fahrzeuge den letzten Teil der Lieferung zu lokalen Stellen übernehmen. Diese traditionelle Vorgehensweise bedeutet, dass Logistikunternehmen eine Mischung aus Fahrzeugtypen benötigen, was zu höheren Kosten für Arbeitskräfte, Zeit und Infrastruktur aufgrund der erforderlichen Transfers führt.

Mit neuen MV-Technologien können Fahrzeuge jetzt andocken, sich aufteilen und Waren während der Fahrt transferieren. Der Hauptvorteil von MVs ist ihr flexibles Design, das es ihnen ermöglicht, während einer Fahrt zu verbinden oder sich zu trennen und Gruppen unterschiedlicher Grösse zu bilden. Durch den Einsatz von MVs für Lieferungen entfällt die Notwendigkeit verschiedener Fahrzeugtypen, was die Fahrzeugkosten senkt. Ausserdem können MVs ihre Kapazität während der Fahrt anpassen, was Zeit spart, die sonst mit Laden und Entladen verbracht würde. Im Gegensatz zu traditionellen Fahrzeuggruppen verbinden sich MVs physisch, was zu einem geringeren Kraftstoffverbrauch führt.

Die Nutzung von MVs in der Logistik, insbesondere für Lieferungen auf der letzten Meile, hat mehrere Vorteile.

Während einige Studien die Anwendungen von MVs diskutiert haben, konzentrieren sich die meisten auf öffentliche Verkehrssysteme, wie Shuttle- und Taxidienste. Forschungen zeigen, dass MVs die Kosten in diesen Systemen erheblich senken können. Nur wenige Studien haben MVs für den Rettungsdienst (EMS) und den kombinierten Personen- und Frachttransport untersucht, was ihre Vorteile in diesen Bereichen bestätigt. Unternehmen wie Next Future Transportation Inc. führen die Entwicklung von MV-Technologien an und haben bereits modulare Busse entwickelt, die ihre Kapazität durch Andocken und Aufteilen ändern können, um Probleme wie Verzögerungen effektiv anzugehen.

Trotz des Interesses an MVs hat sich die meiste vorhandene Forschung auf den öffentlichen Verkehr konzentriert, nicht auf logistische Anwendungen. Die Integration von MVs in traditionelle Lieferprobleme bringt einzigartige Herausforderungen in der Modellierung und im Algorithmusdesign mit sich.

Das MVRP berücksichtigt die dynamische Natur der MV-Kapazität, da sie zusammen andocken können, um Gruppen zu bilden. Das bedeutet, dass die Kapazität dieser Gruppen variiert, während MVs hinzukommen oder abziehen, was eine kontinuierliche Verfolgung ihres Status in Raum und Zeit erfordert.

#Problemdefinition

Unser Problem ist in einem gerichteten Graphen angesiedelt, wobei Knoten das Depot und die Kunden repräsentieren. Das Depot ist der Ausgangs- und Endpunkt aller Routen. Jeder Kunde hat eine spezifische Nachfrage, und die Fahrzeuge müssen diese Anforderungen erfüllen, während die Kosten minimiert werden. Das Ziel ist, die Fahrzeuge so effizient wie möglich zu betreiben.

Das Ziel unseres Problems ist es, die Gesamtkosten für die Lieferung von Waren zu minimieren, während alle Kundenanforderungen erfüllt werden. Die Kosten für die Lieferung können je nach Anzahl der MVs in einer Gruppe und der zurückgelegten Distanz variieren.

Um unser Problem zu formalisieren, haben wir ein dreidimensionales Mixed Integer Linear Programming (MILP)-Modell verwendet.

#Algorithmusentwicklung

Während das MILP-Modell optimale Lösungen finden kann, kann es zeitaufwendig sein, bei grösseren Problemen. Das MVRP ist herausfordernd, da einige seiner Elemente es schwieriger machen, mit traditionellen Methoden zu lösen. Um grössere Probleme effektiv anzugehen, haben wir einen Tabu-Suchalgorithmus (TS) eingeführt.

#Lösungsdarstellung

Um unsere Lösungen besser zu verstehen, verwenden wir ein bestimmtes Format mit einer zweigeteilten Struktur: dem Directed Acyclic Graph (DAG) und einem Gantt-Diagramm. Der DAG repräsentiert die Bewegung der MVs, während das Gantt-Diagramm die Zeit und Reihenfolge der Lieferaufgaben zeigt.

#Nachbarschaftsstruktur

Der TS-Algorithmus basiert stark auf der Nachbarschaftsstruktur, wo verschiedene Operatoren verwendet werden können, um bestehende Lösungen zu verändern und bessere Ergebnisse zu finden. Häufig verwendete Methoden in traditionellen Vehicle Routing Problems können aufgrund ihrer unterschiedlichen Strukturen nicht direkt auf das MVRP angewendet werden. Daher haben wir spezialisierte Zusammenführungsstechniken entwickelt.

1. Serial Merging Operator (SMO): Diese Methode kombiniert Routen, indem sie Kunden sequenziell in ein Segment einfügt. Das Ziel ist es, die Anzahl der verwendeten MVs zu verringern und gleichzeitig die Effizienz aufrechtzuerhalten.

2. Parallel Merging Operator (PMO): Diese Methode integriert eine Einzelroute in ein Segment, um eine Gruppe zu bilden, was flexiblere Kombinationen von MVs ermöglicht.

3. Relocate Operators: Diese erlauben es, einen Kunden von einer Position an eine andere zu verschieben, um eine bessere Lieferroute zu finden.

Durch die Kombination dieser Operatoren kann der TS-Algorithmus ein breiteres Spektrum potenzieller Lösungen erkunden.

#Generierung von Anfangslösungen

Um zu vermeiden, dass wir in einem lokalen Optimum stecken bleiben, wird eine Multi-Start-Strategie integriert. Der Clarke-Wright-Einsparungsalgorithmus wird verwendet, um Anfangslösungen zu produzieren, die dann mit unserem TS-Algorithmus weiter optimiert werden.

#Varianten des MVRP

Wir haben auch verschiedene Versionen des MVRP in Betracht gezogen:

1. En-route Cargo Transfer: Diese Möglichkeit ermöglicht den Transfer von Waren zwischen MVs während einer Route, was Flexibilität im Lieferprozess hinzufügt.

2. Time Synchronization: Diese Funktion verfolgt die Zeitpunkte der Lieferungen und stellt sicher, dass MVs gegebenenfalls aufeinander warten können, um ihre Routen zu optimieren.

3. Heterogeneous Modular Units: Verschiedene Arten von MVs können für unterschiedliche Arten von Fracht verwendet werden, um die effizienteste Transportmethode zu gewährleisten.

#Computation Experimente

Unsere Experimente umfassten mehrere Testfälle, um die Leistung unseres TS-Algorithmus zu messen. Wir haben bekannte Benchmarks für traditionelle Vehicle Routing Problems angepasst, um sie an das MVRP anzupassen.

#Leistungsevaluation

Der TS-Algorithmus wurde gegen das MILP-Modell bewertet. Die Ergebnisse zeigten, dass während das MILP-Modell einige kleine Probleme optimal lösen konnte, es erheblich langsamer war. Im Gegensatz dazu schnitt der TS-Algorithmus sowohl bei kleinen als auch bei grossen Problemen gut ab und fand oft bessere Lösungen in kürzerer Zeit.

#Bewertung der Algorithmuskomponenten

Um den Beitrag jeder Komponente innerhalb des TS-Algorithmus zu verstehen, führten wir Tests ohne spezifische Operatoren durch, um zu sehen, wie sie die Ergebnisse beeinflussten. Jeder Operator brachte wichtige Vorteile, besonders bei grösseren Problemen.

#Bewertung von MV-Platooning

Wir analysierten die Auswirkungen der Variation der maximalen Grösse von MV-Platoons. Mit zunehmender Platoon-Grösse beobachteten wir konsequent einen Rückgang der Gesamtkosten. Dies spiegelt die Vorteile der Gruppierung von MVs wider und hebt das Kostensparpotenzial bei einer effektiven Nutzung von MVs hervor.

#Fazit

Dieses Papier hat einen neuen Ansatz für das Vehicle Routing Problem eingeführt, indem modulare Fahrzeuge integriert wurden, die während der Fahrt andocken und sich aufteilen können. Wir haben ein Mixed Integer Linear Programming-Modell entwickelt, um dieses Problem darzustellen und einen Tabu-Suchalgorithmus erstellt, um effiziente Lösungen zu finden.

Die Ergebnisse haben gezeigt, dass unsere Methode effektive optimale Lösungen in kleinen Fällen entdeckt und in grösseren Instanzen gute Leistungen liefert. Darüber hinaus scheint die Nutzung von MV-Platooning die Kosten erheblich zu senken, um bis zu etwa 5 % im Vergleich zu traditionellen Methoden.

Zukünftige Arbeiten könnten sich darauf konzentrieren, den Algorithmus für grössere, komplexere Probleme weiter zu verbessern und die verschiedenen Erweiterungen des MVRP zu erkunden. Es besteht auch Bedarf an der Erforschung effizienterer exakter Methoden zur Lösung des MVRP sowie an der Analyse der Eigenschaften von Problemen durch Tests und Theorie.