Unmanned aerial vehicles, or drones, have the potential to significantly reduce the cost and time of making last-mile deliveries and responding to emergencies. Despite this potential, little work has gone into developing vehicle routing problems (VRPs) specifically for drone delivery scenarios. Existing VRPs are insufficient for planning drone deliveries: either multiple trips to the depot are not permitted, leading to solutions with excess drones, or the effect of battery and payload weight on energy consumption is not considered, leading to costly or infeasible routes. We propose two multitrip VRPs for drone delivery that address both issues. One minimizes costs subject to a delivery time limit, while the other minimizes the overall delivery time subject to a budget constraint. We mathematically derive and experimentally validate an energy consumption model for multirotor drones, demonstrating that energy consumption varies approximately linearly with payload and battery weight. We use this approximation to derive mixed integer linear programs for our VRPs. We propose a cost function that considers our energy consumption model and drone reuse, and apply it in a simulated annealing (SA) heuristic for finding suboptimal solutions to practical scenarios. To assist drone delivery practitioners with balancing cost and delivery time, the SA heuristic is used to show that the minimum cost has an inverse exponential relationship with the delivery time limit, and the minimum overall delivery time has an inverse exponential relationship with the budget. Numerical results confirm the importance of reusing drones and optimizing battery size in drone delivery VRPs.
VRPs @cite_26 @cite_20 have been applied to solve delivery problems that, at first glance, appear similar to the DDPs proposed in this paper. A VRP attempts to find the optimal routes for one or more vehicles to deliver commodities to a set of locations. Each location may have a unique demand representing the number or size of commodities it requires, or a time window in which the vehicle should arrive. Vehicles typically leave from one or more depots, deliver their commodities, and then return to the depots. This section will explain why existing VRPs are not adequate for the drone delivery problem.
@cite_26 @cite_20
2342478160 2471190594 2621937623 2212025445
In this paper, we introduce the vehicle routing problem with drones (VRPD). A fleet of trucks equipped with drones delivers packages to customers. Drones can be dispatched from and picked up by the trucks at the depot or any of the customer locations. The objective is to minimize the maximum duration of the routes (i.e., the completion time). The VRPD is motivated by a number of highly influential companies such as Amazon, DHL, and Federal Express, actively involved in exploring the potential use of commercial drones for package delivery. After stating our simplifying assumptions, we pose a number of questions in order to study the maximum savings that can be obtained from using drones; we then derive a number of worst-case results. The worst-case results depend on the number of drones per truck and the speed of the drones relative to the speed of the truck. Unmanned aerial vehicles, or drones, have the potential to significantly reduce the cost and time of making last-mile deliveries and responding to emergencies. Despite this potential, little work has gone into developing vehicle routing problems (VRPs) specifically for drone delivery scenarios. Existing VRPs are insufficient for planning drone deliveries: either multiple trips to the depot are not permitted, leading to solutions with excess drones, or the effect of battery and payload weight on energy consumption is not considered, leading to costly or infeasible routes. We propose two multitrip VRPs for drone delivery that address both issues. One minimizes costs subject to a delivery time limit, while the other minimizes the overall delivery time subject to a budget constraint. We mathematically derive and experimentally validate an energy consumption model for multirotor drones, demonstrating that energy consumption varies approximately linearly with payload and battery weight. We use this approximation to derive mixed integer linear programs for our VRPs. We propose a cost function that considers our energy consumption model and drone reuse, and apply it in a simulated annealing (SA) heuristic for finding suboptimal solutions to practical scenarios. To assist drone delivery practitioners with balancing cost and delivery time, the SA heuristic is used to show that the minimum cost has an inverse exponential relationship with the delivery time limit, and the minimum overall delivery time has an inverse exponential relationship with the budget. Numerical results confirm the importance of reusing drones and optimizing battery size in drone delivery VRPs. 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 In the pickup and delivery problem with time windows (PDPTW), vehicles have to transport loads from origins to destinations respecting capacity and time constraints. In this paper, we present a two-phase method to solve the PDPTW. In the first phase, we apply a novel construction heuristics to generate an initial solution. In the second phase, a tabu search method is proposed to improve the solution. Another contribution of this paper is a strategy to generate good problem instances and benchmarking solutions for PDPTW, based on Solomon's benchmark test cases for VRPTW. Experimental results show that our approach yields very good solutions when compared with the benchmarking solutions.