# A Proactive Approach to Extended Vehicle Routing Problem with Drones (EVRPD)
## 2 Vehicle Routing Problem with Drones-Literature Review
The drones take off from the vehicles, deliver the parcels to the customers, return to the take-off site or another place the vehicle has moved to, and then return with the truck to the central depot. The objective of the VRPD is most commonly to minimize the time (cost) required for the delivery of parcels. Some modifications to the VRPD as described in [46] were proposed in [47]. It has been proposed that drones allow trucks to perform tasks in parallel and be able to travel while the drone is in flight. In [48], the authors analyzed how drones can be combined with conventional delivery vehicles to improve same-day delivery performance. They proposed a dynamic vehicle routing problem called the same-day delivery routing problem with heterogeneous fleets of drones and vehicles (SDDPHF). Some assumptions and constraints have been made in this problem. The most important were: customers order goods over the course of the day; the shipments can be delivered either by drones or vehicles; drones are faster but have a limited capacity as well as charging times; vehicle capacities are unlimited, but vehicles are slow due to congestion of road networks. On the other hand, the use of drones for last-mile deliveries is a completely new topic that has not yet been as deeply researched as the classic VRP variants. Some researchers classify VRPDs into two groups. The first is for variants with one truck, and the second for ones with many trucks. A review of VRPDs in this aspect was presented in [31]. It should be noted that planning routes for drones is quite a challenge due to multi-operability that was not available in classic VRPs. There are the following challenges: multi-trip operations, calculating energy consumption, recharge planning, etc. In this context, a multi-trip drone routing problem (MTDRP) was introduced with a time window that explicitly considers the influence of the payload and distance on flight duration [3]. What undoubtedly distinguishes the considered EVRPD from the problems discussed in points (a)-(e) above is the joint-location routing problem (LPR) with a dynamic selection of starting points for drones and the problem of allocating shipments to drones and drones to trucks. At the same time, we considered the possibility of two-way deliveries for various types of shipments. VRPD variants are most often modeled as a MILP (mixed-integer linear programming), ILP (integer linear programming), or BIP (binary linear programming). In the area of modeling, what distinguished the proposed EVRPD model was its structure (a set of constraints and a set of questions), which facilitates its expansion and selection of decision variables so that the modeled problem always had a solution. For example, in [49], the authors proposed two multi-trip VRPs (MTVRPs) for drone delivery that compensated for each drone's limited carrying capacity by reusing drones. The problems were modeled as MILPs and solved based on the simulated annealing heuristic. In [50], the authors proposed a task allocation model for UAVs based on problems with routing vehicles within time windows (VRPTW). The improved particle swarm optimization (PSO) algorithm was used to solve the problem of assigning multiple constraint tasks. In [47], the variable-speed Dubins-path vehicle-routing problem (VS-DP-VRP) was considered, and a model was established that considered the dynamic constraints of UAVs. Due to their computational complexity (most often combinatorial optimization), heuristics, metaheuristics, hybrid methods, etc., are usually used to solve them. The authors proposed a DGA (dedicated genetic algorithm); it had an original method of coding the modeled problem--routes were not coded, but they provided information about which drone delivered the package to which customer. The route was calculated by solving the TSP. This approach significantly simplified the coding of the problem and reduced the size of the chromosomes.