# 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. unmanned aerial vehicle (UAV); vehicle routing problem with drones (VRPD); last-mile delivery; proactive and reactive approach; dedicated genetic algorithm; decision support +
Footnote †: journal: journal: Applied Computer Science, Kieke University of Technology, 25-314 Kielce, Poland 1  
advantages, such as: avoiding the congestion of road networks, faster and cheaper delivery, ecological aspects related to the use of electric drives (low emissions and noise), the limitation of the human factor, etc. However, some weaknesses in the use of drones for deliveries should be mentioned. The most important of them includes their limited range, low-lifting capacity, etc. Therefore, taking all the advantages and limitations of drones into the context of delivery within the last mile, their effective use must be combined with other means of transportation, e.g., trucks [7, 8]. Such deliveries are carried out together, i.e., trucks deliver the drones to the appropriate points or hubs, and from there, the drones take off with the shipments to customers and then return to the hubs. Many companies such as Amazon, Wal-Mart, Google, DHL, SF Express, etc., are starting to implement such solutions. The key questions to be answered when implementing such deliveries (the tandem truck--drone type) are: (a) How to choose starting points or hubs; (b) how to optimally choose routes for drones; (c) in what order to carry out deliveries; and (d) are the available resources (number of drones and other vehicles) sufficient to complete the deliveries? In order to obtain answers to these and similar questions, the appropriate VRP (vehicle routing problem) is modeled and solved in this study. We also formulated and modeled the EVRPD (extended vehicle routing problem with drones). Our contributions were as follows. Firstly, we presented the assumptions and description of the EVRPD. Secondly, we constructed a mathematical model for the EVRPD as a constraint satisfaction problem (CSP) [9] and a set of questions (Q1-8). The proposed model is universal, flexible, easy to modify, and can be used to support proactive and reactive decisions.