Developing Efficient Routing Algorithms for Sustainable City Logistics

Abstract

Route planning for vehicles in freight distribution has long been a primary objective in logistics. Researchers and practitioners have devoted considerable effort to developing models and solution methods to optimize routes for a fleet of vehicles transporting goods from supply points to demand points. However, the global environmental crisis, mainly caused by rapid industrialization, population growth, and urbanization, has underscored the need for sustainable solutions for logistic operations. Rising concerns over environmental pollution, noise, traffic congestion, and population growth, especially in large cities, highlight the necessity to consider social and environmental issues alongside economic and operational efficiency in the design of logistics systems._x000D_ _x000D_ In this line, this thesis addresses the critical need for sustainability in urban logistics by exploring advanced solutions that integrate electric vehicles (EVs) and multi-echelon distribution systems into Vehicle Routing Problems. Situated at the intersection of combinatorial optimization and sustainable urban logistics, this work focuses on both algorithmic advancements and the development of comprehensive routing models._x000D_ _x000D_ The algorithmic contributions primarily involve enhancing and applying the Construct, Merge, Solve & Adapt (CMSA) algorithm, particularly by developing a self-adaptive variant known as Adapt-CMSA. This algorithm variant addresses the issue of parameter sensitivity in metaheuristics, where performance often heavily depends on specific parameter settings. Adapt-CMSA aims to reduce this sensitivity, ensuring robust performance across various problem sizes and complexities without the need for parameter re-tuning. Its effectiveness is first shown in the context of the Minimum Positive Influence Dominating Set Problem, where it outperformed the standard CMSA by dynamically adjusting its parameters, thereby enhancing efficiency and scalability._x000D_ _x000D_ From a practical standpoint, this thesis tackles the formulation of complex routing problems that mirror real-world scenarios in sustainable urban logistics. It introduces models for the Electric Vehicle Routing Problems and Two-Echelon Electric Vehicle Routing Problems, integrating critical constraints such as time windows, simultaneous pickup and deliveries, and partial recharging strategies. Additionally, the thesis goes beyond traditional objective functions considering distance minimization. In particular, we consider energy-minimization that is affected by several factors such as vehicle speed and load. By effectively employing a range of heuristic and metaheuristic approaches, the thesis provides practical solutions to complex variants of the addressed problems.

Date of Award	10 Sept 2024
Original language	English
Supervisor	Christian Clemens Blum (Director)