A New Parcel Delivery System | Encyclopedia MDPI

A New Parcel Delivery System: Comparison

Please note this is a comparison between Version 1 by Hailong Huang and Version 3 by Camila Xu.

This papentryr proposes a novel parcel delivery system which consists of a drone and public transportation vehicles such as trains, trams, etc. This system involves two delivery schemes: drone-direct scheme referring to delivering to a customer by a drone directly and drone–vehicle collaborating scheme referring to delivering a customer based on the collaboration of a drone and public transportation vehicles. The fundamental characteristics including the delivery time, energy consumption and battery recharging are modelled, based on which a time-dependent scheduling problem for a single drone is formulated. It is shown to be NP-complete and a dynamic programming-based exact algorithm is presented. Since its computational complexity is exponential with respect to the number of customers, a sub-optimal algorithm is further developed. This algorithm accounts the time for delivery and recharging, and it first schedules the customer which leads to the earliest return.

droens
public vehicles
parcel delivery

1. Introduction

With the fast development of drones (also called unmanned aerial vehicles (UAVs)) technology, drones have found various applications in civilian domains [1], such as wireless communication support [2], structural health inspection [3], farming [4], surveillance and monitoring [5,6,7] and parcel delivery [8,9]. Thanks to their mobility and flexibility, many logistics companies and many advanced control approaches such as autonomous landing [10], such as Amazon, Alibaba, DHL, SF Express, etc., have started to pay more attention to the application of drones in parcel delivery. Researchers and logistics companies have conducted much research on designing cost-and-time efficient systems such that the delivery can be done in a fast and low-cost way. One model, which has attracted much attention in the research community, is called drone–truck collaboration [11]. Specifically, a truck is equipped with one or several drones. The drones can launch from the truck, deliver to some customers, and then fly to somewhere to dock with the truck. Meanwhile, the truck can service some other customers. Some variants of this model have also been published, such as clustering TSP [12], TSP with drone (TSP-D) [13], minimum cost TSP [14], TSP with Drone Station (TSP-DS) [15], Heterogeneous Delivery Problem (HDP) [16,17], Drone Scheduling Problem (DSP) [18], and Vehicle Routing Problem with Drones (VRPD) [19].

With the fast development of drones (also called unmanned aerial vehicles (UAVs)) technology, drones have found various applications in civilian domains ^[1], such as wireless communication support ^[2], structural health inspection ^[3], farming ^[4], surveillance and monitoring ^[5][6][7] and parcel delivery ^[8][9]. Thanks to their mobility and flexibility, many logistics companies and many advanced control approaches such as autonomous landing ^[10], such as Amazon, Alibaba, DHL, SF Express, etc., have started to pay more attention to the application of drones in parcel delivery. Researchers and logistics companies have conducted much research on designing cost-and-time efficient systems such that the delivery can be done in a fast and low-cost way. One model, which has attracted much attention in the research community, is called drone–truck collaboration ^[11]. Specifically, a truck is equipped with one or several drones. The drones can launch from the truck, deliver to some customers, and then fly to somewhere to dock with the truck. Meanwhile, the truck can service some other customers. Some variants of this model have also been published, such as clustering TSP ^[12], TSP with drone (TSP-D) ^[13], minimum cost TSP ^[14], TSP with Drone Station (TSP-DS) ^[15], Heterogeneous Delivery Problem (HDP) ^[16][17], Drone Scheduling Problem (DSP) ^[18], and Vehicle Routing Problem with Drones (VRPD) ^[19].

Another model is to equip a depot with a fleet of drones, and the drones fly between customers and the depot ^[20]. An important problem is the delivery scheduling problem. A number of publications present some theoretical results for this model ^[21][22]. Comparing to the first model, this model can further reduce the human labour participation. However, the currently available commercial drones are often constrained in flight distance due to the limited on-board battery capacity. For example, Amazon released that their commercial delivery drone can fly about half an hour and travel up to 32 km (

Another model is to equip a depot with a fleet of drones, and the drones fly between customers and the depot [20]. An important problem is the delivery scheduling problem. A number of publications present some theoretical results for this model [21,22]. Comparing to the first model, this model can further reduce the human labour participation. However, the currently available commercial drones are often constrained in flight distance due to the limited on-board battery capacity. For example, Amazon released that their commercial delivery drone can fly about half an hour and travel up to 32 km (

https://www.cbsnews.com/news/amazon-unveils-futuristic-plan-delivery-by-drone/

). If a customer is located slightly outside the delivery area, they cannot be served by the drones. Therefore, the delivery area of this model is also limited.

Following the second model, some publications have considered the facility location problem under the context of drone delivery to extend the delivery area ^[23][24]. Clearly, one disadvantage of this method is the investment in constructing the new facilities. The current paper also focuses on addressing this shortcoming. Unlike ^[23][24] to place more facilities, we introduce the idea of drone–vehicle collaboration ^[25][26]. Here, the vehicle refers to the public transportation vehicles. Unlike the trucks in the first model, the public transportation vehicles have their own routes and timetables, and they cannot be controlled like the trucks by the logistics companies. The public transportation vehicles can take drones to some places which are unreachable by flying themselves. More importantly, as public transportation vehicles are natural mobile platforms which have already existed in the urban area, this model does not introduce much extra cost.

Following the second model, some publications have considered the facility location problem under the context of drone delivery to extend the delivery area [23,24]. Clearly, one disadvantage of this method is the investment in constructing the new facilities. The current paper also focuses on addressing this shortcoming. Unlike [23,24] to place more facilities, we introduce the idea of drone–vehicle collaboration [25,26]. Here, the vehicle refers to the public transportation vehicles. Unlike the trucks in the first model, the public transportation vehicles have their own routes and timetables, and they cannot be controlled like the trucks by the logistics companies. The public transportation vehicles can take drones to some places which are unreachable by flying themselves. More importantly, as public transportation vehicles are natural mobile platforms which have already existed in the urban area, this model does not introduce much extra cost.

2. Discussion

We propose a novel parcel delivery system involving two delivery schemes. The first one, hereafter called drone-direct scheme, uses a drone to directly fly to the customer and then return to the depot. The second one, hereafter called drone–vehicle scheme, makes use of public transportation vehicles. A drone can travel with a vehicle to some position near the customer like a passenger. Differently, it rests on the roof of the vehicle. Then, the drone leaves the vehicle and flies to the customer. After dropping the parcel, it then flies to another vehicle that can transport it back to the depot. In the two schemes, the drone operates autonomously. Comparing these two schemes, the drone-direct scheme generally achieves fast delivery than the drone–vehicle scheme. However, the former may also consume more energy than the latter, since all the trip is made by a drone itself. In contrast, the drone–vehicle scheme explores the vehicle mobility, which saves the energy for the drone. Thus, after delivery, a drone that follows the drone-direct scheme may need longer time for recharging the battery than the drone–vehicle scheme.

Although the delivery time may be longer as the drone needs to wait for the transportation of the public vehicles, the second scheme creates the possibility of delivering to a customer in a low-cost manner. It is quite useful for a supplier that wishes to cost-effectively deliver to a non-urgent customer. One challenge brought by the drone–vehicle scheme is the collaboration between the drone and the vehicles. With the development of vehicle-to-vehicle communication technology, we believe that in the future a drone can also talk to a normal vehicle to collect the trip information of the vehicle. Then, there will be more options for the drone to travel. In this paper, we limit ourselves to a situation where the vehicle-to-vehicle communication technology is not used, and the drone only travels with public vehicles, whose trip information can be well managed.