New heuristics for finding optimal routes for vehicle platoons in road networks

Steinmetz, Dietrich GND

Platooning is the coupling of two or more trucks with small inter-vehicle distance. This technology has the potential to improve road safety, to increase road capacity, and to reduce CO2 emissions. This thesis focuses on minimizing the overall fuel consumption by the centralized formation of vehicles into platoons. Several novel solution strategies are developed for efficiently and effectively tackling large-scale problem instances. One of these strategies stipulates the grouping of vehicles with high platooning incentives and subsequent computation of platooning routes for each vehicle group independently of the other vehicles. This work proposes three lightweight incentive methods based on inexpensive geometric operations. Several grouping approaches, which are using these incentives, are developed to coordinate the vehicles and compared against each other for their efficiency and effectiveness. Our experimental evaluation demonstrates that our proposed grouping-based routing algorithms are more scalable than exact solvers and state-of-the-art routing methods for vehicle platooning. Furthermore, this thesis introduces a new efficient Column Generation formulation for the Vehicle Platooning Problem. An equivalent path-based Master Problem (MP) is given for the Vehicle Platooning Problem (VPP), where the number of variables is much larger than the number of constraints. The Column Generation method restricts and solves the MP iteratively. The corresponding subproblems generate new promising platooning paths and add them to the Restricted Master Problem (RMP). The RMP can be solved very efficiently as only a sufficiently small subset of variables is considered at a time. The composition of our grouping algorithms and our Column Generation (CG)-based routing algorithm enables us to solve extensive problem instances with up to 2000 vehicles on road networks with up to 300,000 edges.

Beim Platooning fahren mehrere Fahrzeuge autonom und mit einem geringen Abstand in einer Kolonne. Diese innovative Technologie bietet großartiges Potenzial zur Optimierung der Verkehrssicherheit sowie zur Auslastung der Autobahnen und des Kraftstoffverbrauchs. Diese Dissertation fokussiert sich insbesondere auf die kostenoptimale Koordination der Fahrzeuge durch die Bildung von kraftstoffeffizienten Platoons. Dabei werden neuartige Strategien zur zentralisierten Koordination der Fahrzeuge für besonders große und datenintensive Problem-Instanzen entwickelt. Eine dieser Strategien ist die Gruppierung der Fahrzeuge mit hohem Platooning-Potenzial und anschließende Bestimmung der Platooning-Routen für die jeweiligen, von einander unabhängigen Fahrzeuggruppen. Dafür wurden in dieser Arbeit mehrere Gruppierungsverfahren entwickelt und hinsichtlich des kostenoptimalen Platoonings untersucht. Unsere experimentellen Untersuchungen haben gezeigt, dass der gruppenbasierte Routing-Ansatz im Vergleich zum exakten Verfahren sowie zu den aktuellsten State-of-the-art-Verfahren deutlich besser skaliert. Darüber hinaus wird in dieser Arbeit eine neue effiziente Column-Generation-Formulierung des Vehicle-Platooning-Problems vorgestellt. Diese Formulierung beinhaltet ein äquivalentes Pfad-basiertes Master-Problem, in dem die Anzahl der Variablen deutlich größer ist als der Anzahl der Nebenbedingungen. Das Column-Generation-Verfahren beschränkt das Master-Problem und löst dieses iterativ. Die dazugehörigen Subprobleme generieren neue vielversprechende Platooning-Pfade und fügen diese zum Restricted-Master-Problem hinzu. Das Restricted-Master-Problem kann sehr effizient gelöst werden, da es nur eine geringe Teilmenge der möglichen Variablen berücksichtigt. Die Komposition unserer Gruppierungsalgorithmen und des Column-Generation-Verfahrens ermöglicht die Lösung besonders großer Problem-Instanzen mit bis zu 2000 Fahrzeugen in Straßennetzen mit bis zu 300.000 Kanten.

Zitieren

Zitierform:

Steinmetz, Dietrich: New heuristics for finding optimal routes for vehicle platoons in road networks. Clausthal-Zellerfeld 2020. Technische Universität Clausthal.

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Rechte

Nutzung und Vervielfältigung:

Export