应急物资的无人机与车辆并行在线配送问题

doi:10.3778/j.issn.1002-8331.2206-0137

计算机工程与应用 ›› 2023, Vol. 59 ›› Issue (19): 247-254.DOI: 10.3778/j.issn.1002-8331.2206-0137

应急物资的无人机与车辆并行在线配送问题

余海燕，苟梦圆，吴腾宇

1.重庆交通大学经济与管理学院，重庆 400074
2.重庆口岸物流与航运发展研究中心，重庆 400074
3.智能物流网络重庆市重点实验室，重庆 400074
4.重庆邮电大学经济管理学院，重庆 400065

出版日期:2023-10-01 发布日期:2023-10-01

Online Truck-Drone Parallel Delivery Problem of Emergency Supplies

YU Haiyan, GOU Mengyuan, WU Tengyu

1.School of Economics and Management, Chongqing Jiaotong University, Chongqing 400074, China
2.Chongqing Key Research Base of Port Logistics and Maritime Development, Chongqing 400074, China
3.Chongqing Key Laboratory of Intelligent Logistics Network, Chongqing 400074, China
4.School of Economics and Management, Chongqing University of Posts and Telecommunications, Chongqing 400065, China

Online:2023-10-01 Published:2023-10-01

摘要/Abstract

摘要： 针对应急配送中需求的实时、紧迫等特点，提出无人机与车辆并行配送的在线订单分配及路径优化问题。构建无人机与车辆并行配送的在线模型，运用竞争分析方法证明得到问题下界为1.5；基于重规划思想设计在线均衡算法，运用最坏情形分析法证明其竞争比为2.5；研究在线算法中调用的离线算法，建立离线问题模型并设计无人机优先均衡算法，在小规模情形下通过与CPLEX所求的最优解进行对比，验证其算法的有效性。最后，通过仿真实验进行在线均衡算法分析，结果显示在输入参数改变下其性能稳定。结论可为应急物资车辆与无人机并行配送提供在线优化策略。

关键词: 无人机与车辆并行配送, 应急物资, 在线配送, 竞争分析

Abstract: Considering the real-time and urgent request in emergent delivery, an online truck-drone parallel delivery problem for request allocation and route plan is proposed. Firstly, an online delivery model is constructed, and the lower bound of the problem is proved to be 1.5 by online analysis. Secondly, an online equalization algorithm is designed based on plan-at-home idea, the competitive ratio of the algorithm is proved to be 2.5 by the worst-case analysis. Considering the online equalization algorithm invokes an offline algorithm, a corresponding offline problem is studied and a drone priority balance algorithm is designed. Its effectiveness is verified by comparing with the persecution results in small-scale cases. Finally, the stability of the online equalization algorithm with different input parameters is verified by simulation. This study provides online algorithm for truck-drone parallel delivery of emergency supplies.

Key words: truck-drone parallel delivery, emergency supplies, online delivery, competitive analysis

余海燕, 苟梦圆, 吴腾宇. 应急物资的无人机与车辆并行在线配送问题[J]. 计算机工程与应用, 2023, 59(19): 247-254.

YU Haiyan, GOU Mengyuan, WU Tengyu. Online Truck-Drone Parallel Delivery Problem of Emergency Supplies[J]. Computer Engineering and Applications, 2023, 59(19): 247-254.

参考文献

[1] CHUNG S H，SAH B，LEE J.Optimization for drone and drone-truck combined operations：a review of the state of the art and future directions[J].Computers and Operations Research，2020，123：105004-105033.
[2] MURRAY C C，CHU A G.The flying sidekick traveling salesman problem：optimization of drone-assisted parcel delivery[J].Transportation Research Part C：Emerging Technologies，2015，54：86-109.
[3] DELL’AMICO M，MONTEMANNI R，NOVELLANI S.Algorithms based on branch and bound for the flying sidekick traveling salesman problem[J].Omega，2021，104：102493-102504.
[4] NGUYEN M A，DANG G T，Hà M H，et al.The min-cost parallel drone scheduling vehicle routing problem[J].European Journal of Operational Research，2022，299（3）：910-930.
[5] SALEU R G M，DEROUSSI L，FEILLET D，et al.An iterative two-step heuristic for the parallel drone scheduling traveling salesman problem[J].Networks，2018，72（4）：459-474.
[6] 任璇，黄辉，于少伟，等.车辆与无人机组合配送研究综述[J].控制与决策，2021，36（10）：2313-2327.
REN X，HUANG H，YU S W，et al.Review on vehicle-UAV combined delivery problem[J].Controland Decision，2021，36（10）：2313-2327.
[7] ULMER M W，THOMAS B W.Same-day delivery with heterogeneous fleets of drones and vehicles[J].Networks，2018，72（4）：475-505.
[8] 王新玉，赵志明.动态取送问题研究综述[J].系统工程理论与实践，2021，41（2）：319-331.
WANG X Y，ZHAO Z M.Survey of the dynamic pickup and delivery problems[J].Systems Engineering-Theory & Practice，2021，41（2）：319-331.
[9] SLEATOR D D，TARJAN R E.Amortized efficiency of list update and paging rules[J].Communication of the ACM，1985，28：202-208.
[10] AUSIELLO G，FEUERSTEIN E，LEONARDI S，et al.Algorithms for the on-Line travelling salesman[J].Algorithmica，2001，29（4）：560-581.
[11] 马卫民，王刊良.局内封闭式车辆调度问题及其竞争策略[J].系统工程理论与实践，2004（9）：72-78.
MA W M，WANG K L.Competitive analysis for the close on-line truck scheduling problem with time-window[J].Systems Engineering-Theory & Practice，2004（9）：72-78.
[12] 戴敏，徐寅峰，董玉成，等.带时间窗的局内开放式车调度问题的竞争分析[J].系统工程，2006（4）：93-96.
DAI M，XU Y F，DONG Y C，et al.A competitiveanalysis for the openon-linek trucksscheduling problem with time window[J].Systems Engineering，2006（4）：93-96.
[13] JAILLET P，LU X.Online traveling salesman problems with rejection options[J].Networks，2014，64（2）：84-95.
[14] 马军平，徐寅峰，吴腾宇.有服务时长和服务可选择性的快递车辆调度在线策略研究[J].运筹与管理，2020，29（1）：38-46.
MA J P，XU Y F，WU T Y.A study of Express vehicle online schedule problem with service time and service flexibility[J].Operations Research and Management Science，2020，29（1）：38-46.
[15] 吴腾宇，张景露，余海燕.非对称网络下的在线取送货路径优化问题[J].中国管理科学，2022（5）：1-14.
WU T Y，ZHANG J L，YU H Y.The real-time pick-up and delivery problem with asymmetric network[J].Chinese Journal of Management Science，2022（5）：1-14.

应急物资的无人机与车辆并行在线配送问题

Online Truck-Drone Parallel Delivery Problem of Emergency Supplies

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

编辑推荐

Metrics

[1]	王庆荣，马辰坤. 面向案例消耗推理的应急物资预测[J]. 计算机工程与应用, 2021, 57(22): 281-287.
[2]	李周清1，王绍仁2，王峰3. 区域性应急物资储备库选址－配给模型与算法[J]. 计算机工程与应用, 2014, 50(16): 226-231.
[3]	王婧，王海军. 应急救援中应急物资需求紧迫性分级研究[J]. 计算机工程与应用, 2013, 49(5): 4-7.
[4]	邬开俊1，王铁君2. 带时限的多出救点应急物资调度模型及算法[J]. 计算机工程与应用, 2012, 48(30): 19-23.
[5]	汪亮，解建仓，罗军刚. 基于K均值聚类和LK算法的应急物资调度[J]. 计算机工程与应用, 2012, 48(21): 35-40.
[6]	郭子雪，齐美然. 带有模糊参数的应急物资筹集问题决策模型[J]. 计算机工程与应用, 2011, 47(23): 217-219.
[7]	俞武扬. 大规模应急物资中转运输问题研究[J]. 计算机工程与应用, 2011, 47(17): 1-3.
[8]	郭子雪，齐美然. 模糊环境下的应急物资储备库选址模型及算法[J]. 计算机工程与应用, 2010, 46(25): 214-216.
[9]	郭子雪^1，2，张强²，齐美然¹. 具有模糊约束的应急物资储备库最大覆盖模型[J]. 计算机工程与应用, 2010, 46(24): 210-212.
[10]	郭子雪^1，2，张强². 模糊聚类分析在突发事件应急物资分类中应用[J]. 计算机工程与应用, 2009, 45(35): 208-211.
[11]	郭子雪^1，2，齐美然¹，张强². 应急物资储备库最小加权距离选址模型[J]. 计算机工程与应用, 2009, 45(34): 195-197.