A New Parcel Delivery System: Comparison
View Latest Version
Please note this is a comparison between Version 3 by Camila Xu and Version 2 by Camila Xu.

This paperntry 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].

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.

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.

 

 

References

  1. Hailong Huang; Andrey V. Savkin; Towards the Internet of Flying Robots: A Survey. Sensors 2018, 18, 4038, 10.3390/s18114038.
  2. Hailong Huang; Andrey V. Savkin; A Method for Optimized Deployment of Unmanned Aerial Vehicles for Maximum Coverage and Minimum Interference in Cellular Networks. Real-Time Optimal Lithium-Ion Battery Charging Based on Explicit Model Predictive Control 2018, 15, 2638-2647, 10.1109/tii.2018.2875041.
  3. Adam Marchewka; Patryk Ziółkowski; Victor Aguilar-Vidal; Framework for Structural Health Monitoring of Steel Bridges by Computer Vision. Sensors 2020, 20, 700, 10.3390/s20030700.
  4. Jayme G.A. Barbedo; Luciano Koenigkan; Thiago Teixeira Santos; Patricia Menezes Santos; A Study on the Detection of Cattle in UAV Images Using Deep Learning. Sensors 2019, 19, 5436, 10.3390/s19245436.
  5. Andrey V. Savkin; Hailong Huang; A Method for Optimized Deployment of a Network of Surveillance Aerial Drones. IEEE Systems Journal 2019, 13, 4474-4477, 10.1109/jsyst.2019.2910080.
  6. Andrey V. Savkin; Hailong Huang; Proactive Deployment of Aerial Drones for Coverage over Very Uneven Terrains: A Version of the 3D Art Gallery Problem.. Sensors 2019, 19, 1438, 10.3390/s19061438.
  7. Andrey V. Savkin; Hailong Huang; Asymptotically Optimal Deployment of Drones for Surveillance and Monitoring.. Sensors 2019, 19, 2068, 10.3390/s19092068.
  8. Andy M. Ham; Integrated scheduling of m-truck, m-drone, and m-depot constrained by time-window, drop-pickup, and m-visit using constraint programming. Transportation Research Part C: Emerging Technologies 2018, 91, 1-14, 10.1016/j.trc.2018.03.025.
  9. Jose Javier Escribano-Macias; Panagiotis Angeloudis; Washington Ochieng; Optimal hub selection for rapid medical deliveries using unmanned aerial vehicles. Transportation Research Part C: Emerging Technologies 2020, 110, 56-80, 10.1016/j.trc.2019.11.002.
  10. Liu; Shifeng Zhang; Tian; Xuancen Liu; Jiayi Tian; Longbin Liu; An Onboard Vision-Based System for Autonomous Landing of a Low-Cost Quadrotor on a Novel Landing Pad. Sensors 2019, 19, 4703, 10.3390/s19214703.
  11. Chase C. Murray; Amanda G. Chu; The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies 2015, 54, 86-109, 10.1016/j.trc.2015.03.005.
  12. Yong Chang; Hyun Jung Lee; Optimal delivery routing with wider drone-delivery areas along a shorter truck-route. Expert Systems with Applications 2018, 104, 307-317, 10.1016/j.eswa.2018.03.032.
  13. Niels Agatz; Paul Bouman; Marie Schmidt; Optimization Approaches for the Traveling Salesman Problem with Drone. SSRN Electronic Journal 2015, null, , 10.2139/ssrn.2639672.
  14. Quang Minh Ha; Yves Deville; Quang Dung Pham; Minh Hoàng Hà; On the min-cost Traveling Salesman Problem with Drone. Transportation Research Part C: Emerging Technologies 2018, 86, 597-621, 10.1016/j.trc.2017.11.015.
  15. Sungwoo Kim; Ilkyeong Moon; Traveling Salesman Problem With a Drone Station. H∞ Output Anti-Disturbance Control of Stochastic Markov Jump Systems With Multiple Disturbances 2018, 49, 42-52, 10.1109/tsmc.2018.2867496.
  16. Neil Mathew; Stephen Smith; Steven L. Waslander; Mathew N.; Smith S.L.; Planning Paths for Package Delivery in Heterogeneous Multirobot Teams. IEEE Transactions on Automation Science and Engineering 2015, 12, 1298-1308, 10.1109/tase.2015.2461213.
  17. Xiaoshan Bai; Ming Cao; Weisheng Yan; Shuzhi Sam Ge; Efficient Routing for Precedence-Constrained Package Delivery for Heterogeneous Vehicles. IEEE Transactions on Automation Science and Engineering 2020, 17, 248-260, 10.1109/tase.2019.2914113.
  18. Nils Boysen; Dirk Briskorn; Stefan Fedtke; Stefan Schwerdfeger; Drone delivery from trucks: Drone scheduling for given truck routes. Networks 2018, 72, 506-527, 10.1002/net.21847.
  19. David Sacramento; David Pisinger; Stefan Røpke; An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones. Transportation Research Part C: Emerging Technologies 2019, 102, 289-315, 10.1016/j.trc.2019.02.018.
  20. Patchara Kitjacharoenchai; Seokcheon Lee; Vehicle Routing Problem with Drones for Last Mile Delivery. Procedia Manufacturing 2019, 39, 314-324, 10.1016/j.promfg.2020.01.338.
  21. Pasquale Grippa; Doris A. Behrens; Friederike Wall; Christian Bettstetter.; Drone delivery systems: job assignment and dimensioning. Autonomous Robots 2018, 43, 261-274, 10.1007/s10514-018-9768-8.
  22. Maryam Torabbeigi; Gino J. Lim; Seon Jin Kim; Drone Delivery Scheduling Optimization Considering Payload-induced Battery Consumption Rates. Journal of Intelligent & Robotic Systems 2019, 97, 471-487, 10.1007/s10846-019-01034-w.
  23. Insu Hong; Michael Kuby; Alan T. Murray; A range-restricted recharging station coverage model for drone delivery service planning. Transportation Research Part C: Emerging Technologies 2018, 90, 198-212, 10.1016/j.trc.2018.02.017.
  24. Seyed Mahdi Shavarani; Sam Mosallaeipour; Mahmoud Golabi; Gokhan Izbirak; A congested capacitated multi-level fuzzy facility location problem: An efficient drone delivery system. Computers & Operations Research 2019, 108, 57-68, 10.1016/j.cor.2019.04.001.
  25. H. D. Yoo; S. M. Chankov; Drone-delivery Using Autonomous Mobility: An Innovative Approach to Future Last-mile Delivery Problems. 2018 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM) 2018, null, 1216-1220, 10.1109/ieem.2018.8607829.
  26. Angelo Trotta; Fabio D Andreagiovanni; Marco Di Felice; Enrico Natalizio; Kaushik Roy Chowdhury; When UAVs Ride A Bus: Towards Energy-efficient City-scale Video Surveillance. IEEE INFOCOM 2018 - IEEE Conference on Computer Communications 2018, null, 1043-1051, 10.1109/infocom.2018.8485863.
More
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/)
ScholarVision Creations
Feedback