The efficiency and dynamism of Unmanned Aerial Vehicles (UAVs), or drones, present substantial application opportunities in several industries in the last years. Notably, the logistic companies gave close attention to these vehicles envisioning reduce delivery time and operational cost. A variant of the Traveling Salesman Problem (TSP) called Flying Sidekick Traveling Salesman Problem (FSTSP) was introduced involving drone-assisted parcel delivery. The drone is launched from the truck, proceeds to deliver parcels to a customer and then is recovered by the truck in a third location. While the drone travels through a trip, the truck delivers parcels to other customers as long as the drone has enough battery to hover waiting for the truck. This work proposes a hybrid heuristic that the initial solution is created from the optimal TSP solution reached by a TSP solver. Next, an implementation of the General Variable Neighborhood Search is used to obtain the delivery routes of truck and drone. Computational experiments show the potential of the algorithm to improve the delivery time significantly. Furthermore, we provide a new set of instances based on well-known TSPLIB instances.
@cite_0 discuss two different problems in their work. First, a Heterogeneous Delivery Problem (HDP) as a discrete optimal path planning problem that seeks to minimize the total cost of deliveries in routes computed for a truck and a drone. To solve the HDP, they devise a reduction to obtain a Generalized Traveling Salesman Problem (GTSP) and be able to use already available solvers. This paper uses three different edges cost: one for drone flight edges, one for truck street edges and one for when the truck transports the drone. The second problem presented is called Multiple Warehouse Delivery Problem (MWDP). In MWDP only drones perform the delivery of parcels, again they use reduction to GTSP to solve this problem with known solvers.
@cite_0
1650780448 2609088824 2163352112 2342478160
This paper addresses the task scheduling and path planning problem for a team of cooperating vehicles performing autonomous deliveries in urban environments. The cooperating team comprises two vehicles with complementary capabilities, a truck restricted to travel along a street network, and a quadrotor micro-aerial vehicle of capacity one that can be deployed from the truck to perform deliveries. The problem is formulated as an optimal path planning problem on a graph and the goal is to find the shortest cooperative route enabling the quadrotor to deliver items at all requested locations. The problem is shown to be NP-hard. A solution is then proposed using a novel reduction to the Generalized Traveling Salesman Problem, for which well-established heuristic solvers exist. The heterogeneous delivery problem contains as a special case the problem of scheduling deliveries from multiple static warehouses. We propose two additional algorithms, based on enumeration and a reduction to the traveling salesman problem, for this special case. Simulation results compare the performance of the presented algorithms and demonstrate examples of delivery route computations over real urban street maps. Introduce a new time-dependent UAV heterogeneous fleet routing problem.Consider several objective functions and respect drones operational requirements.Design a MILP model in order to find sets of non-dominated solutions.Consider a model able to tackle multi-layer scenarios with package exchanging points.Integrate UAV into the new concepts of mini microgrid systems inside smart cities. This paper introduces an Unmanned Aerial Vehicle (UAV) heterogeneous fleet routing problem, dealing with vehicles limited autonomy by considering multiple charging stations and respecting operational requirements. A green routing problem is designed for overcoming difficulties that exist as a result of limited vehicle driving range. Due to the large amount of drones emerging in the society, UAVs use and efficiency should be optimized. In particular, these kinds of vehicles have been recently used for delivering and collecting products. Here, we design a new real-time routing problem, in which different types of drones can collect and deliver packages. These aerial vehicles are able to collect more than one deliverable at the same time if it fits their maximum capacity. Inspired by a multi-criteria view of real systems, seven different objective functions are considered and sought to be minimized using a Mixed-Integer Linear Programming (MILP) model solved by a matheuristic algorithm. The latter filters the non-dominated solutions from the pool of solutions found in the branch-and-bound optimization tree, using a black-box dynamic search algorithm. A case of study, considering a bi-layer scenario, is presented in order to validate the proposal, which showed to be able to provide good quality solutions for supporting decision making. We consider the courier delivery problem (CDP), a variant of the vehicle routing problem with time windows (VRPTW) in which customers appear probabilistically and their service times are uncertain. We use scenario-based stochastic programming with recourse to model the uncertainty in customers and robust optimization for the uncertainty in service times. Our proposed model generates a master plan and daily schedules by maximizing the coverage of customers and the similarity of routes in each scenario, while minimizing the total time spent by the couriers and the total earliness and lateness penalty. To solve large-scale problem instances, we develop an insertion-based solution heuristic, called master and daily scheduler (MADS), and a tabu search improvement procedure. The computational results show that our heuristic improves the similarity of routes and the lateness penalty at the expense of increased total time spent when compared to a solution of independently scheduling each day. Our experimental results also show improvements over current industry practice on two real-world data sets. 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.