Online Truck-Drone Parallel Delivery Problem of Emergency Supplies

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

Computer Engineering and Applications ›› 2023, Vol. 59 ›› Issue (19): 247-254.DOI: 10.3778/j.issn.1002-8331.2206-0137

• Engineering and Applications • Previous Articles Next Articles

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

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

余海燕，苟梦圆，吴腾宇

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

Abstract

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

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

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

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.

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

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Recommended Articles

Metrics

[1]	WANG Qingrong, MA Chenkun. Forecast of Emergency Supplies for Case Consumption Reasoning [J]. Computer Engineering and Applications, 2021, 57(22): 281-287.
[2]	WANG Liang, XIE Jiancang, LUO Jungang. Emergency supplies scheduling based on K-mean cluster and LK algorithm [J]. Computer Engineering and Applications, 2012, 48(21): 35-40.