卡车支持无人机配送的在线与离线问题研究  

Research on Online and Offline Problems of Truck-drone Distribution

作　　者：余海燕 叶婧 吴腾宇[4] 苟梦圆 YU Haiyan;YE Jing;WU Tengyu;GOU Mengyuan(School of Economics and Management,Chongqing Jiaotong University,Chongqing 400074,China;Chongqing Key Laboratory of Green Logistics Intelligent Technology,Chongqing 400074,China;Chongqing Key Research Base of Port Logistics Management and Maritime Economics,Chongqing 400074,China;School of Economics and Management,Chongqing University of Posts and Telecommunications,Chongqing 400065,China)

机构地区：[1]重庆交通大学经济与管理学院,重庆400074 [2]绿色物流智能技术重庆市重点实验室,重庆400074 [3]重庆口岸物流管理与航运经济研究中心,重庆400074 [4]重庆邮电大学经济管理学院,重庆400065

出　　处：《运筹与管理》2024年第6期51-56,共6页Operations Research and Management Science

基　　金：国家自然科学基金青年基金资助项目(71702016);教育部人文社会科学研究项目(21YJC630159);重庆市教委人文社科项目(22SKJD092);重庆市研究生导师团队建设项目(JDDSTD2018003);重庆交通大学研究生科研创新项目(2022S0062)。

摘　　要：在长期疫情时起时伏情况下,卡车支持无人机配送模式可在避免交叉感染方面发挥重要作用。针对现实生活中应急需求具有很强动态性的特征,提出卡车支持无人机在线配送问题。使用竞争分析方法证明此问题的下界为2-δ,设计调用离线最优算法的在线OCOA算法,分析OCOA算法的竞争比为2.5。设计包含卡车停靠点选址—需求分配—卡车路径优化的三阶段离线TSOOA算法,通过与CPLEX求解结果对比,验证TSOOA算法的有效性。通过在线仿真分析计算出OCOA算法与离线问题下界的比值约为1.75,表明OCOA算法在现实场景中应用效果更好。本文提出的卡车支持无人机在线配送模式可以为疫情物资的实时调度决策提供依据。At the beginning of 2020,COVID-19 broke out all over the world,which seriously affected the normal life of the people.At present,although the epidemic is almost under control,it breaks out on a small scale in various regions,and the society is still in the post epidemic era.In the closed area during isolation,drone distribution can avoid direct contact to prevent the increase in cases.Truck-drone distribution can not only expand the scope of delivery,but also solve the timeliness difficulties of the orders.Therefore,the online and offline problem of truck-drone distribution is worth researching.The truck-drone mode means that a truck carries drones from the distribution center.The truck is regarded as a mobile warehouse on its way.The truck only stops at the corresponding stop to provide materials and charging services for drones.All orders are fulfilled by drones.By consulting relevant literature,the research into truck-drone distribution is in the preliminary stage.Most research considers how to dispatch trucks and drones under static conditions,but this needs to be researched under dynamic conditions.The online method is also an effective method to solve dynamic problems,but the current research on the online method is only limited to the case of traditional vehicle distribution,and there is still a lack of the online research into truck-drone distribution.The second part of this paper researches the problem of truck-drone online distribution,which aims at the shortest total time to serve all the orders and return to the distribution center.Orders are generated in real time and have strong dynamics.Firstly,it is proved that the lower bound of the competitive ratio of the truck-drone distribution problem is 2-δ.Secondly,the online OCOA algorithm that calls the offline TSOOA algorithm is designed,and it is proved that the upper bound of the competition ratio of OCOA algorithm on the general network is 2.5.The core idea of OCOA algorithm is to judge whether the truck is at the distribution center and discuss it

关 键 词：卡车支持无人机 在线算法 三阶段离线算法 竞争比 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] F252[自动化与计算机技术—控制科学与工程]