School of Electrical Engineering and Telecommunications, University of New South Wales, Sydney 2052, Australia.
Electrical Computer and Telecommunications Engineering, University of Wollongong, Wollongong 2500, Australia.
Sensors (Basel). 2020 Apr 5;20(7):2045. doi: 10.3390/s20072045.
This paper 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. Its computational complexity is also discussed. Moreover, extensive computer simulations are conducted to demonstrate the scheduling performance of the proposed algorithms and the impacts of several key system parameters are investigated.
本文提出了一种新颖的包裹投递系统，该系统由无人机和公共交通工具（如火车、有轨电车等）组成。该系统涉及两种投递方案：无人机直接投递方案，指的是由无人机直接向客户投递；以及无人机与公共交通工具协作投递方案，指的是基于无人机和公共交通工具的协作向客户投递。本文对包括投递时间、能耗和电池充电在内的基本特征进行建模，并在此基础上针对单个无人机制定了一个与时间相关的调度问题。结果表明该问题是 NP 完全问题，并提出了一种基于动态规划的精确算法。由于其计算复杂度是客户数量的指数级，因此进一步开发了一种次优算法。该算法考虑了投递和充电时间，并首先调度最早返回的客户。还讨论了其计算复杂度。此外，进行了广泛的计算机模拟以验证所提出算法的调度性能，并研究了几个关键系统参数的影响。
