无人机城市配送受扰延误后调度研究

doi:10.3778/j.issn.1002-8331.2205-0118

摘要/Abstract

摘要： 物流无人机在实际配送飞行中会遭遇各种不确定干扰因素，进而导致配送延误。为减小无人机受扰后配送延误带来的损失，提出自救、增派与取消的混合策略，同时加入无人机能耗分段模型，精确计算飞行所需能耗，确保配送方案切实可行。研究了生成无干扰时最优调度方案。随机生成受扰无人机编号、受扰时间与恢复所需时间，将受扰客户救援策略作为决策变量，以最小成本为目标兼顾交货完成率与客户满意度，使用改进蚁群算法对模型求解。运用所罗门算例进行测试。结果表明自救、增派与取消的混合策略较全局重调策略成本平均降低11.5%，交货完成率提高9.5%，客户满意度提高7%。在求解小规模算例时，使用混合策略生成的新方案不仅仅降低了配送成本，同时提高了交货完成率与客户满意度，尽可能使得干扰带来的影响最小。

关键词: 物流无人机, 受扰, 物流调度, 改进蚁群算法

Abstract: Logistics unmanned aerial vehicle（UAV） will encounter various uncertain interference factors in the actual delivery flight, which will lead to delivery delay. In order to reduce the loss caused by UAV delivery delay after being disturbed, a hybrid strategy of self-rescue, additional dispatch and cancellation is proposed. Meanwhile, a subsection model of UAV energy consumption is added to accurately calculate the flight energy consumption to ensure the feasibility of the delivery scheme. Firstly, the optimal scheduling scheme without interference is generated. Secondly, the number of the disturbed UAV, the disturbed time and the recovery time are randomly generated. The rescue strategy of the disturbed customer is taken as the decision variable, and the delivery completion rate and customer satisfaction are taken into account with the goal of minimizing the cost. The improved ant colony algorithm is used to solve the model. Finally, the Solomon example is used to test. The results show that compared with the global rescheduling strategy, the cost of self-rescue, additional dispatch and cancellation strategy is reduced by 11.5% on average, delivery completion rate is increased by 9.5% and customer satisfaction is increased by 7%. When solving small-scale examples, the new scheme generated by using mixed strategy not only reduces the distribution cost, but also improves the delivery completion rate and customer satisfaction, and minimizes the impact of interference as much as possible.

Key words: logistics UAV, disturbed, logistics scheduling, improved ant colony algorithm

武彤, 苟利珍, 王佳雪, 任新惠. 无人机城市配送受扰延误后调度研究[J]. 计算机工程与应用, 2023, 59(15): 310-317.

WU Tong, GOU Lizhen, WANG Jiaxue, REN Xinhui. Research on Scheduling of UAV After Disturbed Delay in Urban Distribution[J]. Computer Engineering and Applications, 2023, 59(15): 310-317.

参考文献

[1] JEONG H Y，SONG B D，LEE S.Truck-drone hybrid delivery routing：payload-energy dependency and no-fly zones[J].International Journal of Production Economics，2019，214：220-233.
[2] ALAN S.Specification for a dynamic vehicle routing and scheduling system[J].International Journal of Transport Management，2002，1（1）：29-40.
[3] MIN W，CORDEAU J F，GIBERT L et al.The dynamic multi-period vehicle routing problem[J].Computers & Operations Research，2010，37（9）：1616-1623.
[4] SACHA W，RICHARD O，CLAUSSEN U.Dynamic vehicle routing either anticipation in disaster relief[J].Social-Economic Planning Sciences，2012（46）：261-271.
[5] VICTOR P，MICHEL G，CHRISTELLE G.A review of dynamic vehicle routing problems[J].European Journal of Operational Research，2013，225（1）：1-11.
[6] 郎茂祥，胡思继.用混合遗传算法求解物流配送路径优化问题的研究[J].中国科学管理，2002，10（5）：51-56.
LANG M X，HU J S.Study on the optimization of physical distribution routing problem by using hybrid genetic algorithm[J].Chinese Journal of Management Science，2002，10（5）：51-56.
[7] 廖良才，王栋，周峰.基于混合遗传算法的物流配送车辆调度优化问题求解方法[J].系统工程，2008，26（8）：27-31.
LIAO L C，WANG D，ZHOU F.Solving method of the optimization problem of logistic distribution vehicle scheduling based on hybrid genetic algorithm[J].Systems Engineering，2008，26（8）：27-31.
[8] 刘霞，齐欢.带时间窗的动态车辆路径问题的局部搜索算法[J].交通运输工程学报，2008，8（5）：114-120.
LIU X，QI H.Local search alogrithm of dynamic vehicle routing problem with time window[J].Journal of Traffic and Transportation Engineering，2008，8（5）：114-120.
[9] 陈晓眯，孟志青，徐杰.基于混合禁忌搜索算法的动态车辆路径研究[J].浙江工业大学学报，2009，37（5）：580-586.
CHEN X M，MENG Z Q，XU J.Research on dynamic vehicle routing problem based on hybrid tabu search algorithm[J].Journal of Zhejiang University of Technology，2009，37（5）：580-586.
[10] 葛显龙，王旭，邢乐斌.动态需求的多车型车辆调度问题及云遗传算法[J].系统工程学报，2012，27（6）：823-831.
GE X L，WANG X，XING L B.Multi-vehicle scheduling problems and cloud GA based on the dynamic needs[J].Journal of Systems Engineering，2012，27（6）：823-831.
[11] TORABBEIGI M，LIM G J，KIM S J.Drone delivery schedule optimization considering the reliability of drones[C]//2018 International Conference on Unmanned Aircraft Systems，2018.
[12] TORABBEIGI M，LIM G J，AHMADIAN N，et al.An optimization approach to minimize the expected loss of demand considering drone failures in drone delivery scheduling[J].Journal of Intelligent & Robotic Systems，2021，102（1）.
[13] GLAUDEL H S，GHATAS R W.Establishing the framework for eVTOL flight mission scenario development for urban air mobility research using cognitive task analysis[C]//AIAA Aviation 2021 Forum，2021.
[14] SAWADSITANG S，NIYATO D，TAN P S，et al.Shipper cooperation in stochastic drone delivery：a dynamic bayesian game approach[J].arXiv：2002.03118，2022.
[15] SAWADSITANG S，NIYATO D，TAN P S，et al.Joint ground and aerial package delivery services：a stochastic optimization approach[J].IEEE Transactions on Intelligent Transportation Systems，2019，20（6）：2241-2254.
[16] SAWADSITANG S，NIYATO D，TAN P S，et al.Multi-objective optimization for drone delivery[C]//2019 IEEE 90th Vehicular Technology Conference（VTC2019-Fall），2019：1-5.
[17] SAWADSITANG S，NIYATO D，TAN P S，et al.Multi-objective optimization for drone delivery[C]//2019 IEEE 90th Vehicular Technology Conference（VTC2019-Fall）.Honolulu，HI，USA：IEEE，2019：1-5.
[18] 任新惠，武彤.考虑能耗分段的物流无人机调度模型[J].计算机工程与应用，2022，58（21）：301-308.
REN X H，WU T.Logistics unmanned aerial vehicles scheduling model considering energy consumption segmentation[J].Computer Engineering and Applications，2022，58（21）：301-308.