# Reinforcement Learning for Efficient Drone-Assisted Vehicle Routing
## 1 Introduction  
Last-mile delivery represents the critical final stage of the logistics process, encompassing the transportation of parcels from distribution centres to customers' destinations via various vehicles such as trucks, vans, bicycles, or drones. Optimizing this process is essential to providing a seamless and satisfying delivery experience, achieving cost reductions for logistics companies, enhancing operational efficiency, and fostering sustainability and business growth. With a projected 36% increase in delivery vehicles on roads between 2019 and 2030, urban areas face heightened congestion, leading to a 21% rise in average commute times. This surge also brings an additional 6 million tonnes of CO\({}_{2}\) emissions, underscoring the urgency of addressing last-mile delivery challenges effectively [1]. Emerging technologies, particularly drones, have gained traction as innovative solutions for overcoming last-mile delivery challenges. Initially utilized in military and disaster management sectors [2, 3], drones are now being explored for logistics applications due to their lightweight, battery-operated nature [4]. The recent real-world pilot projects, such as Amazon Prime or Google Wings, illustrate how drones can reduce delivery times, bypass traffic congestion, and serve remote locations or areas with poor infrastructure. By offering faster door-to-door services and potentially lower operational costs, drones can improve the efficiency of last-mile logistics, decrease the reliance on large fleets of traditional vehicles, and reduce fuel consumption and emissions. Drones also produce zero direct emissions and can complement truck-based methods by reaching difficult-to-access regions. While trucks excel at delivering heavy packages over long distances, drones are well-suited for transporting small parcels over short distances. Using drones along with traditional trucks for last-mile delivery can save time, lower emissions, and help reduce traffic congestion [5]. The potential for parallel customer service emerges when multiple trucks and drones are incorporated into last-mile delivery systems, leading to shorter delivery completion times and higher overall operational efficiency. For instance, if a drone travels 50% faster than a truck, and each truck is equipped with up to two drones, delivery times can be reduced by up to 75% in optimal scenarios [6]. Beyond these efficiency gains, drones can also support urgent and time-sensitive deliveries such as medical supplies or high-priority goods, further enhancing service quality. However, the combined deployment of drones and trucks introduces complex computational challenges, such as coordinating their routes and identifying optimal launch and retrieval locations. The optimization problem associated with finding efficient routes for multiple drones and trucks in last-mile delivery is known as the Vehicle Routing Problem with Drones (VRPD). This problem is classified as an NP-hard combinatorial optimization problem (COP) [7] due to the intricate constraints involved, including drone battery limitations and diverse launch and retrieval points. Despite existing research efforts [8; 9], current methods often suffer from prolonged computational times and lack adaptability to dynamic customer distribution patterns, particularly for large problem instances. This study proposes a novel heuristic method to address the VRPD by formulating it as a Markov Decision Process (MDP) and leveraging Reinforcement Learning (RL) to train a Neural Network (NN) for routing decisions. RL, a machine learning approach, enables an agent to learn optimal decisions through interaction with the environment and iterative improvements based on cumulative rewards. Recent advancements in machine learning have shown promise in addressing challenging COPs [10; 11; 12]. Among prior studies, the closest work to ours is [13], which applied RL to the Traveling Salesman Problem with Drone (TSPD), a special case of the VRPD involving a single truck and drone without battery limitations.