A Proactive Approach to Extended Vehicle Routing Problem with Drones (EVRPD)

Abstract

Unmanned aerial vehicles (UAVs), also known as drones, are increasingly common and popular due to their relatively low prices and high mobility. The number of areas for their practical applications is rapidly growing. The most promising are: last-mile delivery, emergency response, the inspection of technical devices and installations, etc. In these applications, it is often necessary to solve vehicle routing problems, formulated as a variant of the vehicle routing problems with drones (VRPD). This study presents a proactive approach to a modified and extended VRPD, including: the dynamic selection of drone take-off points, bidirectional delivery (delivery and pick up), various types of shipments, allocation of shipments to drones and drones to vehicles, the selection of the optimal number of drones, etc. Moreover, a formal model of constraints and questions for the extended vehicle routing problem with drones (EVRPD) and exact and approximate methods for solving it have been proposed. The proposed model can be the basis for supporting proactive and reactive decisions regarding last-mile delivery, particularly the selection of the necessary fleet, starting points, the identification of specific shipments that prevent delivery with available resources, etc. The study also includes the results of numerous computational experiments verifying the effectiveness of the implementation methods. The time to obtain a solution is at least 20 times shorter for the proposed DGA (dedicated genetic algorithm) than for the mathematical programming solvers such as Gurobi or LINGO. Moreover, for larger-sized data instances, these solvers do not allow obtaining any solution in an acceptable time, or they obtain worse solutions.

Keywords

• unmanned aerial vehicle (UAV)
• vehicle routing problem with drones (VRPD)
• last-mile delivery
• proactive and reactive approach
• dedicated genetic algorithm
• decision support