2017/06/07 by Stefan Poikonen, Xingyin Wang, Bruce Golden · 4 citations
Computer Science · Engineering · #Optimization and Search Problems #Transportation and Mobility Innovations #Vehicle Routing Optimization Methods
paper · doi:10.1002/net.21746
crossref issued 2017/06/07 · crossref published 2017/06/07 · crossref published-online 2017/06/07 · openalex publication_date 2017/06/07 · crossref created 2017/06/07 · crossref published-print 2017/08/01 · crossref deposited 2023/10/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/22 · crossref indexed 2026/08/01
The vehicle routing problem with drones (VRPD) is inspired by the increasing interest in commercial drone delivery by companies such as Amazon, Google, DHL, and Walmart. In our model, a fleet of m homogeneous trucks each carries k drones with a speed of α times that of the truck. Each drone may dispatch from the top of the truck and carry a package to a customer location. The drone then returns to the top of its truck to recharge or swap batteries (we assume instantaneously). The truck itself is allowed to move and deliver packages, but must be stationary at a delivery location or the depot when launching or retrieving drones. The goal is to minimize the completion time to deliver all packages and return all vehicles back to the central depot. In this article, we review and extend several worst‐case results from an earlier paper and we make connections with another practical variant of the vehicle routing problem and with Amdahl's Law. We find that the VRPD model offers some important practical advantages. The drones allow the truck to parallelize tasks and they are able to take advantage of crow‐fly distances. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(1), 34–43 2017