A Multi-Trip Vehicle Routing Problem for Small Unmanned Aircraft Systems-Based Urban Delivery

With the emergence of new technologies for small unmanned aircraft systems (sUAS), such as lightweight sensors and high-efficiency batteries, the operation of small unmanned aerial vehicles (sUAVs) will expand from military use to commercial use. A promising commercial application of sUAS is package delivery because of its potential to reduce acquisition and operating costs of the last-mile delivery system, while enabling new services such as same-day delivery. Moreover, in urban areas, sUAVs can deliver packages to customers without negatively affecting street traffic. To conduct urban operations, sUAS-based delivery systems must obey regulations for sUAS operations and avoid urban obstacles. In this paper, a maximum-flight-time-constrained multitrip vehicle routing problem with time windows optimization model is used to create routes for sUAS-based delivery missions. To address the actual urban environment with the optimization model, a two-layered urban flight network is built by feeding an airborne light detection and ranging sensor data into an algorithm that uses a Voronoi diagram to create collision-free paths. This paper uses this approach to study a possible package delivery using sUAS in San Diego, CA.