EXPLORING THE POTENTIAL OF REINFORCEMENT LEARNING IN OPTIMIZING LAST-MILE DELIVERY ROUTES

ABSTRACT

The rapid development of autonomous delivery services has created a growing need for intelligent route optimization techniques capable of operating in dynamic urban environments. This study explores the application of reinforcement learning (RL) algorithms to optimize last-mile delivery routes, aiming to improve the overall efficiency and adaptability of delivery operations. The main objective is to enhance decision-making processes for autonomous vehicles by using data-driven approaches, specifically leveraging Q-learning methods. Through the simulation of urban delivery scenarios, real-world datasets — including traffic conditions, delivery time windows, and road constraints — are utilized to train and evaluate the RL model. The research highlights the scientific and practical significance of using RL, demonstrating that RL-based optimization solutions outperform traditional heuristic methods in minimizing travel times and increasing delivery reliability. The findings contribute valuable insights to the fields of supply chain management and intelligent transportation systems by showcasing the ability of RL to handle complex, real-time logistical challenges.

АННОТАЦИЯ

Бурное развитие автономных служб доставки вызвало растущую потребность в интеллектуальных методах оптимизации маршрутов, способных эффективно работать в условиях динамичной городской среды. В данном исследовании рассматривается применение алгоритмов обучения с подкреплением (Reinforcement Learning, RL) для оптимизации маршрутов последней мили доставки с целью повышения общей эффективности и адаптивности логистических операций. Основная цель заключается в улучшении процессов принятия решений автономными транспортными средствами с использованием подходов, основанных на данных, в частности, методов Q-обучения. В симулируемых городских сценариях доставки используются реальные наборы данных — такие как дорожная обстановка, временные окна доставки и дорожные ограничения — для обучения и оценки модели RL. Результаты исследования демонстрируют как научную, так и практическую значимость применения RL, показывая его превосходство над традиционными эвристическими методами по таким показателям, как сокращение времени в пути и повышение надежности доставки. Работа вносит ценный вклад в области управления цепями поставок и интеллектуальных транспортных систем, доказывая способность RL справляться со сложными логистическими задачами в реальном времени.

Keywords:  reinforcement learning, route optimization, last-mile delivery, autonomous vehicles, urban logistics, intelligent transportation systems.

Ключевые слова: обучение с подкреплением, оптимизация маршрутов, доставка последней мили, автономные транспортные средства, городская логистика, интеллектуальные транспортные системы.

Introduction

Last-mile delivery, the last link in the supply chain where products are delivered from warehouses to final customers, is receiving more attention as a result of the exponential growth of e-commerce and the rising need for dependable, quick deliveries. Up to 53% of the total cost of shipping is spent on this section, which is frequently the most expensive and time-consuming. During this stage, effective route optimization is essential for raising customer satisfaction, cutting expenses, and lessening environmental effects. Last-mile delivery in urban areas is particularly difficult due to traffic jams, parking shortages, congested streets, and strict delivery windows. These elements make it more difficult to plan and carry out routes, which causes delays and raises operating expenses. Additionally, the rise in customer expectations for same-day or next-day deliveries adds pressure on logistics providers to optimize their operations further [1].

For many years, conventional route optimization techniques, which have their roots in operations research, have been used to solve logistical problems. For finding the shortest paths in static environments, algorithms like Dijkstra's and A* have been used extensively. But in dynamic and unpredictable urban environments, where real-time variables like traffic, weather, and unforeseen interruptions are crucial, these traditional algorithms frequently fail. A promising substitute is provided by Reinforcement Learning (RL), a branch of machine learning that allows systems to discover the best course of action through interactions with their surroundings.

Materials and methods

Last-mile delivery logistical issues have long been addressed by traditional route optimization techniques. Finding the shortest paths in static environments has been made possible by algorithms like Dijkstra's and A*. But in dynamic and unpredictable urban environments, where real-time variables like traffic, weather, and unforeseen interruptions are crucial, these traditional algorithms frequently fail.

The goal of recent research has been to improve these traditional techniques. For example, Cook et al. [2] presented a constrained local search algorithm designed for last-mile routing that enhances route quality by taking operational constraints and driver preferences into account. This strategy's practical applicability was demonstrated by its notable success in the 2021 Amazon Last Mile Routing Research Challenge [3]. Furthermore, Chu et al.  presented a data-driven optimization framework that integrates capacitated vehicle routing optimization with machine learning [4]. Their approach improves performance by 5% over conventional optimization techniques by incorporating predictive models to address delivery time uncertainties.

A viable substitute for dynamic route optimization is Reinforcement Learning (RL). For the Capacitated Electric Vehicle Routing Problem, Yıldız [5] created a Q-learning-based solution that showed notable computation time savings over traditional approaches. Their method demonstrated RL's versatility in challenging, real-world delivery settings [6]. In order to address the pickup and delivery issue, also presented a deep reinforcement learning model with heterogeneous attention mechanisms [6].

Hybrid models are the result of combining machine learning methods with classical optimization. A hybrid decision support framework was presented by Dieter et al. (2021) that integrates optimization algorithms with driver behavior data to produce more realistic and effective routing solutions [7, 8]. In order to close the gap between theoretical optimization and real-world implementation [9], participants used historical delivery data to train models that mimic the routing choices made by seasoned drivers.

When network conditions (such as traffic or road closures) are constant, Dijkstra's algorithm performs especially well in static routing scenarios. For example, Dijkstra's algorithm was used in a study by Lusiani [10] to optimize delivery routes for J&T Express in Bandung, Indonesia. The study by Shuaibu [11] emphasized the value of heuristics in improving adaptability and the significance of such optimization algorithms in tackling the challenges of last-mile delivery.

A machine learning technique called reinforcement learning (RL) allows an agent to continuously interact with its surroundings and make the best decisions possible. Unlike conventional optimization techniques, reinforcement learning (RL) learns optimal strategies through experience and dynamically adjusts to changing conditions, eliminating the need for explicit modeling of all environmental details. Because of its versatility, RL is especially well-suited to situations involving uncertainty and complexity, like last-mile delivery route optimization. An agent continuously monitors the state of the environment in RL and acts in response to these observations.

A popular reinforcement learning technique known for its ease of use and efficiency is Q-learning. In Q-learning, the agent develops a decision-making strategy based only on these assessments, learning the relative benefits of each action for each state. Without knowing the environment beforehand, the agent gradually improves its strategy by updating these action-value estimates based on experience.

The Deep Q-Network (DQN) extends traditional Q-learning by using deep neural networks to evaluate decisions. This approach significantly enhances the ability of RL to manage complex environments that involve numerous possible states or continuously changing conditions.

The advantages of both action-value-based (critic) and policy-based (actor) approaches are combined in actor-critical methods. While the "critic" assesses the selected actions to enhance future decision-making, the "actor" chooses which actions to take. By offering consistent and thorough feedback on policy performance, the combination guarantees effective learning. In last-mile delivery situations, where the complexity of the environment necessitates both thorough action evaluation and quick, flexible adaptation to new information, this dual-structure approach works particularly well.

This study uses two extensive and well-known datasets, OpenStreetMap (OSM) and General Transit Feed Specification (GTFS), to compare classical and reinforcement learning algorithms for last-mile delivery route optimization.

The methodology outlined in Figure 1 will be used to assess reinforcement learning (RL) algorithms in the context of last-mile delivery optimization.

Figure 1. Methodology overview

OpenStreetMap is a free, open-source database that offers comprehensive and in-depth geographic data gathered cooperatively by contributors from all over the world. Road networks, bike routes, pedestrian walkways, and points of interest like business establishments, residences, transit hubs, and landmarks are just a few of the geographic features covered by OSM data.

Google^* created the GTFS standard format to represent the routes, stops, and schedules of public transportation. It improves transportation planning and analytics by allowing public transit organizations all over the world to freely share their schedules and route data.

Results and discussions

Using scenarios derived from OpenStreetMap (OSM) and General Transit Feed Specification (GTFS) data, this section compares the performance of classical route optimization algorithms (Dijkstra's and A*) against reinforcement learning (RL) techniques (Q-Learning, Deep Q-Network, Policy Gradient, and Actor-Critic).

The total travel distance and delivery times under both static and dynamic conditions are used to assess route efficiency. Under static conditions, Dijkstra's and A* both reliably produced extremely effective routes by utilizing the thorough spatial information offered by OSM data. In particular, A*'s heuristic-driven search outperformed Dijkstra's, leading to average route computation times across tested scenarios that were about 12% shorter. But when it came to handling dynamic changes like unforeseen traffic jams or road closures, both approaches demonstrated serious shortcomings. Delivery delays were frequently exacerbated by their incapacity to quickly adapt to real-time information, averaging 25% longer than originally estimated in dynamic urban conditions.

Reinforcement learning algorithms, such as Q-Learning, DQN, Policy Gradient, and Actor-Critic, have shown competitive or better performance, especially in dynamic environments. Because of their ability to take into account and adjust to changes in real time, Deep Q-Network (DQN) and Actor-Critic approaches in particular performed exceptionally well. When RL-optimized routes were exposed to real-time changes like traffic jams and fluctuating demand scenarios, they demonstrated notable delays reductions and averaged 18% faster overall than classical algorithms.

Delivery delays were frequently exacerbated by their incapacity to quickly adapt to real-time information, averaging 25% longer than originally estimated in dynamic urban conditions. As shown in Table 1, classical algorithms work well in environments that are stable and predictable, but as the environment becomes more complex, their efficacy quickly declines.

Table 1.

Comparative Performance Summary

On the other hand, reinforcement learning techniques, particularly Deep Q-Network and Actor-Critic, perform exceptionally well in the dynamic, uncertain urban environments that are typical of last-mile delivery tasks. Several significant implications for logistics management are highlighted by this comparative analysis:
- Because RL algorithms are responsive to real-time changes, businesses seeking resilient and adaptive routing systems should think about incorporating them.
- Although RL approaches require a large initial training investment, these expenses are outweighed by the long-term operational benefits, particularly in dynamic environments.

As shown in Figure 2, the graphical representation illustrates the average delivery times under static versus dynamic conditions for reinforcement learning algorithms (Q-Learning, DQN, and Actor-Critic) and classical algorithms.

Figure 2. Average Delivery Times under Static Vs. Dynamic Conditions

In comparison to classical methods, this chart graphically illustrates how reinforcement learning algorithms—particularly DQN and Actor-Critic—maintain more reliable and effective delivery times under dynamic conditions.

Despite the encouraging results, RL techniques are practical challenges for smaller businesses or companies with limited resources because they require a large amount of historical data and computational resources for initial trainingConclusion

Thus, the obtained results indicate the need to develop a universal mobile application that will combine the convenience of the interface, automation of financial accounting, analytics and forecasting, and also provide users with free access to the main functions. This will increase user satisfaction, simplify the financial management process and make personal budgeting more effective.

Conclusion

In order to address the crucial problem of last-mile delivery route optimization, this study compared traditional route optimization algorithms (Dijkstra's and A*) with reinforcement learning (RL) techniques (Q-Learning, Deep Q-Network, and Actor-Critic). Assuring practical relevance and applicability to real-world logistics, the evaluation used realistic urban scenarios derived from the General Transit Feed Specification (GTFS) and OpenStreetMap (OSM) datasets. The results unequivocally showed that traditional algorithms, like Dijkstra's and A*, operate well in environments that are stable and predictable and have fixed route parameters. However, in the dynamic and uncertain environment of contemporary urban logistics, where traffic patterns, unforeseen circumstances, and operational limitations are constantly changing, their performance drastically deteriorates. In conclusion, this comparative study highlights the benefits of RL-based techniques for optimizing last-mile deliveries, especially in dynamic urban settings. It is recommended that businesses use or incorporate RL approaches into their routing systems if they want logistics operations that are responsive, scalable, and future-proof. Future studies ought to examine hybrid models that combine the adaptive power of reinforcement learning with the efficiency of classical algorithms, as this could provide well-rounded solutions that capitalize on the benefits of both approaches.

References:

1. Farooq U., Rahim M. S. M., Sabir N., Hussain M. A comprehensive survey on transportation problems solved using metaheuristics and machine learning // Neural Computing and Applications. – 2021. – Vol. 33. – P. 14357–14399.
2. Liu Y., Ye Q., Escribano-Macias J., Feng Y., Candela E., Angeloudis P. Reinforcement learning for dynamic fleet management: A review and future perspectives // arXiv preprint arXiv:2209.04265. – 2022.
3. Chen Z., Xu H., Wang H. Urban freight transportation mode optimization using deep learning // Transportation Research Part E: Logistics and Transportation Review. – 2020. – Vol. 142. – Article 102063.
4. Li J. GNN-based optimization for last-mile delivery // arXiv preprint arXiv:2110.02634. – 2021.
5. Li X., Chen Y., Li K. Vehicle routing problem optimization using deep reinforcement learning // IEEE Access. – 2021. – Vol. 9. – P. 140947–140965.
6. Greenberg I., Sielski P., Linsenmaier H., Gandham R., Mannor S., Fender A., Chechik G., Meirom E. GRouteNet: A graph neural network for route optimization // arXiv preprint arXiv:2301.01817. – 2023.
7. Pan Z., Lin X., Qiao Y., Wang S., Lin H., Wu J. Dynamic route planning for autonomous delivery using DRL // arXiv preprint arXiv:2311.08615. – 2023.
8. Li K., Wu Y., Liang Y., Wang F. Deep reinforcement learning for urban logistics routing // Expert Systems with Applications. – 2022. – Vol. 208. – Article 118169.
9. Zhao Y., Li L., Song X., Song Y. Spatiotemporal attention-based reinforcement learning for smart logistics // arXiv preprint arXiv:2306.12483. – 2023.
10. Du Y., Zhang S., Wu Y., Li S. Autonomous vehicle fleet management using actor-critic methods // IEEE Transactions on Intelligent Transportation Systems. – 2021. – Vol. 22(5). – P. 2918–2928.
11. Tang J., Liu D., He X. DeepMetaRL: A meta-reinforcement learning approach for adaptive route optimization // arXiv preprint arXiv:2305.08972. – 2023.
12. Luo Y., Zhou F., Sun Y. Gated GNNs for delivery route prediction // arXiv preprint arXiv:2204.10010. – 2022.
13. Tan L., Sun J., Liu Z. Real-time traffic aware route optimization using DRL and GNNs // Transportation Research Part C: Emerging Technologies. – 2023. – Vol. 148. – Article 103952.
14. Yuan F., Feng S., Zhang W., Guo Y. Route optimization for on-demand delivery via multi-agent DRL // arXiv preprint arXiv:2310.01936. – 2023.

^*По требованию Роскомнадзора информируем, что иностранное лицо, владеющее информационными ресурсами Google является нарушителем законодательства Российской Федерации – прим. ред.)