Loading...

An LP-Based Approximation Algorithm for Drone-Truck Non-Heterogeneous Delivery Problem

Seyed Fatehi, Zahra | 2025

46 Viewed
  1. Type of Document: M.Sc. Thesis
  2. Language: Farsi
  3. Document No: 58581 (01)
  4. University: Sharif University of Technology
  5. Department: Industrial Engineering
  6. Advisor(s): Eshghi, Kourosh
  7. Abstract:
  8. Last-mile delivery is a critical stage in logistics that significantly impacts customer satisfaction and costs, facing challenges such as traffic congestion and environmental concerns. As a promising solution, drones, in conjunction with trucks, can enhance customer deliveries. This research addresses the NP-hard truck-drone routing problem by incorporating the real-world constraint of forbidden paths for the truck. In this model, the truck handles deliveries to customers whose parcels exceed the drone's capacity or who are otherwise ineligible for drone service, while the remaining customers are served by drones. The objective is to minimize the truck's return time to the depot (makespan). To solve this, a polynomial-time approximation algorithm with a guaranteed approximation ratio of1+√5 is presented. The algorithm's efficiency was validated through extensive computational experiments, which showed that it has a significantly lower runtime compared to exact methods. Furthermore, for practical validation, the algorithm was implemented on a real-world case study using data from the city of Bojnourd, demonstrating its high capability in solving large-scale logistics problems
  9. Keywords:
  10. Last Mile Delivery ; Mathematical Programming ; Truck and Drone Routing ; Vehicle Routing Problem ; Approximate Algorithm ; Urban Logistics

 Digital Object List

 Bookmark