A Lagrangian Relaxation Algorithm for the Drone Routing Problem with Backhauls and Wind

Most urban logistics providers are able to deliver goods efficiently using conventional vehicles, except in areas that have low quality road infrastructure and steep road slopes, which pose a challenge for delivery. This lowers the quality of delivery services, creating pockets of underserved populations in urban areas, which is undesirable from an economic and social perspective. The flexibility of drones has made them an attractive option for last-mile delivery in this context. Optimizing the utilization of remaining energy and payload capacity during drone return trips is essential for maximizing overall utility. However, prior studies have overlooked the consideration of backhaul in the context of drone-only systems, as well as the assessment of energy consumption under wind conditions. This paper proposes a new model for the Drone Delivery Routing Problem with Backhaul (DDRPB), which incorporates both wind conditions and backhauling requirements, and is applicable for areas that have high delivery demand and return requests, but suffer from low delivery service quality. We introduce a linearized drone-wind-energy consumption model and design a Lagrangian relaxation heuristic algorithm to solve the resulting NP-hard optimization problem efficiently. A case study of an urban area with delivery challenges in Seoul, South Korea is presented. The results show that the proposed model effectively decreases overall costs.