Developing Efficient Routing Algorithms for Sustainable City Logistics

Abstract

La planificació de rutes per a vehicles en la distribució de mercaderies ha estat durant molt de temps un objectiu primordial en logística. Investigadors i professionals han dedicat considerables esforços a desenvolupar models i mètodes de resolució per a optimitzar rutes per a flotes de vehicles que transporten béns des de punts de subministrament a punts de demanda. No obstant això, la crisi ambiental global, profunditzada per la ràpida industrialització, el creixement de la població i la urbanització, han subratllat la necessitat de solucions sostenibles per a les operacions logístiques. Les creixents preocupacions sobre la contaminació ambiental, el soroll, la congestió deguda al trànsit i el creixement de la població, especialment en les grans ciutats, destaquen la necessitat de considerar els problemes socials i ambientals juntament amb l'eficiència econòmica i operativa en el disseny dels sistemes logístics.

En aquesta línia, aquesta tesi aborda la necessitat crítica de sostenibilitat en la logística urbana explorant solucions avançades que integren vehicles elèctrics (EVs) i sistemes de distribució de múltiples nivells en els Problemes d'Enrutament de Vehicles. Situat a la intersecció de la optimització combinatòria i la logística urbana sostenible, aquest treball se centra tant en els avenços algorísmics com en el desenvolupament de models d'enrutament integrals.

Les contribucions algorísmiques involucren principalment la millora i aplicació de l'algorisme Construir, Fusionar, Resoldre i Adaptar (CMSA), particularment desenvolupant una variant auto-adaptativa coneguda com Adapt-CMSA. Aquesta variant aborda el repte de la sensibilitat als paràmetres en les metaheurístiques, on el rendiment sovint depèn en gran mesura de configuracions de paràmetres específics. Adapt-CMSA té com a objectiu reduir-ne aquesta sensibilitat, assegurant-ne un rendiment robust en diverses mides i complexitats de problemes sense la necessitat de reajustar-ne els paràmetres. La seva efectivitat va ser particularment evident en ser aplicat al Problema del Conjunt Dominant de Influència Positiva Mínima, on va superar el CMSA estàndard en ajustar dinàmicament els seus paràmetres, millorant-ne així l'eficiència i l'escalabilitat.

Des d'un punt de vista pràctic, aquesta tesi aborda la formulació de problemes complexos d'enrutament que reflecteixen escenaris del món real en la logística urbana sostenible. Introdueix models per als Problemes d'Enrutament de Vehicles Elèctrics i Problemes d'Enrutament de Vehicles Elèctrics de Dos Nivells, integrant restriccions crítiques com ara finestres de temps, recollides i entregues simultànies, i estratègies de recàrrega parcial. A més, la tesi va més enllà de les funcions objectiu tradicionals de minimització de distàncies en considerar també la minimització d'energia, afectada per diversos factors com ara la velocitat del vehicle i la seva càrrega. En emprar de manera efectiva una gamma d'enfocs heurístics i metaheurístics, la tesi proporciona solucions pràctiques a variants complexes dels problemes abordats.

La planificación de rutas para vehículos en la distribución de mercancías ha sido durante mucho tiempo un objetivo primordial en logística. Investigadores y profesionales han dedicado considerables esfuerzos a desarrollar modelos y métodos de resolución para optimizar rutas para flotas de vehículos que transportan bienes desde puntos de suministro a puntos de demanda. Sin embargo, la crisis ambiental global, profundizada por la rápida industrialización, el crecimiento de la población y la urbanización, ha subrayado la necesidad de soluciones sostenibles para tales operaciones logísticas. Las crecientes preocupaciones sobre la contaminación ambiental, el ruido, la congestión ocasionada por el tráfico y el crecimiento de la población, especialmente en las grandes ciudades, destacan la necesidad de considerar los problemas sociales y ambientales junto con la eficiencia económica y operativa en el diseño de los sistemas logísticos.

En esta línea, esta tesis aborda la necesidad crítica de sostenibilidad en la logística urbana explorando soluciones avanzadas que integran vehículos eléctricos (EVs) y sistemas de distribución de múltiples niveles en los Problemas de Enrutamiento de Vehículos. Situado en la intersección de la optimización combinatoria y la logística urbana sostenible, este trabajo se centra tanto en los avances algorítmicos como en el desarrollo de modelos de enrutamiento integrales.

Las contribuciones algorítmicas involucran principalmente la mejora y aplicación del algoritmo Construir, Fusionar, Resolver y Adaptar (CMSA), particularmente desarrollando una variante auto-adaptativa conocida como Adapt-CMSA. Esta variante aborda el desafío de la sensibilidad a los parámetros en las metaheurísticas, donde el rendimiento a menudo depende en gran medida de configuraciones de parámetros específicos. Adapt-CMSA tiene como objetivo reducir esta sensibilidad, asegurando un rendimiento robusto en diversos tamaños y complejidades de problemas sin la necesidad de reajustar los parámetros. Su efectividad fue particularmente evidente cuando se aplicó al Problema de Conjunto Dominante de Influencia Positiva Mínima, donde superó al CMSA estándar al ajustar dinámicamente sus parámetros, mejorando así la eficiencia y la escalabilidad.

Desde un punto de vista práctico, esta tesis aborda la formulación de problemas complejos de enrutamiento que reflejan escenarios del mundo real en la logística urbana sostenible. Introduce modelos para los Problemas de Enrutamiento de Vehículos Eléctricos y Problemas de Enrutamiento de Vehículos Eléctricos de Dos Niveles, integrando restricciones críticas como ventanas de tiempo, recogidas y entregas simultáneas, y estrategias de recarga parcial. Además, la tesis va más allá de las funciones objetivo tradicionales de minimización de distancias al considerar también la minimización de energía, afectada por varios factores como la velocidad del vehículo y su carga. Al emplear efectivamente una gama de enfoques heurísticos y metaheurísticos, la tesis proporciona soluciones prácticas a variantes complejas de los problemas abordados.

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.

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.

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.

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.