Mathematical modelling with exact, heuristic and meta-heuristic solution methodologies for the fuel-efficient platooning of heavy duty vehicles on road networks

As the demand for road transportation steadily increases and simultaneously the fuel price grows, transportation companies face with more challenges to reduce their costs, and more importantly, to mitigate the resulted environmental impacts. One promising approach for the sake of fuel consumption reduction is to make Heavy Duty Vehicles (HDVs) drive together in groups called "platoon" behind each other and in close prox- imity like a string. This reduces the aerodynamic drag or resistive force on vehicles and as a result less energy or fuel is required for the same movement. Another benet of platooning is that so the trac congestion of road networks can be lessened. Al- though the idea of platooning has been proposed since long ago, its realisation has only become recently possible due to the late advances in information, communications and computation technology. This doctoral thesis proposes a novel and unique approach to Fuel Ecient Platooning (for ease called FEP in the thesis) on large scale road networks. Two dierent mathematical models are presented which formulate the FEP problem from dierent aspects. Several real-life attitudes such as travel time constraints, maximum allowable distance, and also multiple speeds for vehicles are embedded in the models, which have not been addressed together in any previous work in the literature. Consequently, the main contributions, which are our solution methodologies are pro- posed in three categories. They gradually enable us to tackle bigger sizes of the problem. The rst one is attempting the exact solution of the two models by the powerful solver of CPLEX in the GAMS platform. Due to very high computational complexity, some changes are applied to the models to reduce the complexity and increase the biggest solvable size of the problem by the exact solver. The results of the two models and their decomplexied versions are compared together. Due to the limitations of exact solution approaches in terms of problem scale and the required execution time, heuristic methods are investigated in the next step. Two heuristics from the literature are adapted and modied to deal with our version of the FEP problem. Furthermore, a new ecient heuristic called Global Planning is proposed which is proved to be better than the other two heuristics. Introducing the third group, which are meta-heuristic solution methodologies, is an important part of this thesis. They are designed to deal with samples larger than those solved by the heuristics in a short time. Three famous nature-inspired algorithms which are also appropriate for our problem, namely: Genetic Algorithm (GA), Ant Colony Optimisation (ACO) and Particle Swarm Optimisation (PSO), are chosen. Then suitable and ecient application procedure for each is devised including specic solution encoding, operators and etc. Subsequently, a thorough comparison is made between the performance of the employed meta-heuristics and heuristics. All comparisons in this thesis are done by an appropriate non-parametric statistical method. In the nal part, some sensitivity analyses are conducted which investigate the eects of changing some important input parameters of the problem. Generally, this thesis conducts a comprehensive investigation into the FEP problem and provides appropriate solution approaches that can be used in practice for real cases to achieve signicant nancial and environmental benets.Ein vielversprechender Ansatz zur Reduzierung des Kraftstoverbrauchs von Schwerlastfahrzeugen (HDVs) besteht darin, sie in Gruppen, die als "Platoon" bezeichnet werden, hintereinander und in unmittelbarer Nähe wie eine Schnur zusammenfahren zu lassen. Dies reduziert den Luftwiderstand an Fahrzeugen und führt dazu, dass für die gleiche Bewegung weniger Energie oder Kraftsto benötigt wird. Diese Doktorarbeit schlägt einen neuen und einzigartigen Ansatz für das Fuel Ecient Platooning (FEP) in groÿen Straÿennetzen vor. Es werden zwei verschiedene mathematische Modelle vorgestellt. Mehrere reale Einstellungen wie Zeitbeschränkungen, maximal zulässige Umwege und auch Mehrfachgeschwindigkeiten für Fahrzeuge sind in die Modelle integriert. Folglich werden die wichtigsten Beiträge, die unsere Lösungsmethoden sind, in drei Kategorien vorgestellt. Die erste versucht, exakte Lösungen für die beiden Modelle durch den leistungsstarken Solver von CPLEX in der GAMS-Plattform zu nden. Aufgrund der sehr hohen Rechenkomplexität werden einige Änderungen in den Modellen vorgenommen, um die Komplexität zu reduzieren und die gröÿte mit dem exakten Solver lösbare Gröÿe des Problems zu erhöhen. Die Ergebnisse der beiden Modelle und ihre dekomplexisierten Versionen werden miteinander verglichen. Im Hinblick auf die Grenzen exakter Lösungsansätze bezüglich der Problemgröÿe und der erforderlichen Ausführungszeit werden im nächsten Schritt heuristische Methoden vorgestellt. Zwei Heuristiken aus der Literatur werden angepasst und modiziert, um unsere Version des FEP-Problems zu behandeln. Darüber hinaus wird auch eine neue und eziente Heuristik namens Global Planning vorgeschlagen, die sich als besser erweist als die beiden anderen Heuristiken. Die Einführung der dritten Gruppe, die unsere meta-heuristischen Lösungsmethoden beinhaltet, ist ein wichtiger Teil dieser Arbeit. Diese sind so entworfen, dass sie mit Stichproben gröÿer als die mit den Heuristiken gelösten umgehen können. Drei berühmte von der Natur inspirierte Algorithmen, die auch für unser Problem geeignet sind, nämlich: Genetischer Algorithmus (GA), Ameisenkolonieoptimierung (ACO) und Partikelschwarmoptimierung (PSO) sind ausgewählt. Anschlieÿend wird ein geeignetes und ezientes Applikationsverfahren für jede einzelne Meta-Heuritik entwickelt, einschlieÿlich spezischer Lösungscodierung, Operatoren usw. Folglich wird ein gründlicher Vergleich zwischen der Leistung der verwendeten Meta-Heuristiken und der Heuristiken durchgeführt. Alle Vergleiche in dieser Arbeit werden mit einer geeigneten nicht-parametrischen statistischen Methode durchgeführt. Im letzten Teil sind einige Sensitivitätsanalysen durchgeführt, die die Auswirkungen der Änderung einiger wichtiger Eingabeparameter des Problems untersuchen. Im Allgemeinen führt diese Arbeit eine umfassende Untersuchung des FEP-Problems durch und liefert geeignete Lösungsansätze, die in der Praxis für reale Fälle verwendet werden können, um erhebliche nanzielle und ökologische Vorteile zu erzielen