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

Research on Online and Offline Problems of Truck-drone Distribution

在长期疫情时起时伏情况下,卡车支持无人机配送模式可在避免交叉感染方面发挥重要作用。针对现实生活中应急需求具有很强动态性的特征,提出卡车支持无人机在线配送问题。使用竞争分析方法证明此问题的下界为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 in different cases.If the truck is at the distribution center,it will directly call the offline TSOOA algorithm to solve it.If the truck is not at the distribution center,the offline TSOOA algorithm will be called after the truck returns to the distribution center along the shortest path.The third part of this paper researches on the offline distribution problem of truck-drones,which aims at the shortest total time to serve all orders and return to the distribution center,which is how to choose the truck stop,how to distribute orders and how to plan the truck’s route when all information of the orders is known.For the offline problem,a model is established,a three-stage offline algorithm TSOOA algorithm is designed,and CPLEX is used to solve the linear model.For the same input information,the minimum relative error between the result of TSOOA algorithm and that of offline optimal algorithm is 0%,and the maximum is 6.69%,which proves the effectiveness of TSOOA algorithm.The fourth part of this paper uses professional numerical simulation software MATLAB programming to simulate and analyze the OCOA algorithm.In order to research on the effectiveness of the algorithm in different networks,two representative network data are selected for comparison.The ratio of the lower bound of the OCOA algorithm and the offline TSOOA algorithm is calculated to be about 1.75 for the two networks of the simulated network and the real network.The application effect of OCOA algorithm in real scenes is better than that of the upper bound of the competitive ratio.To sum up,the truck-drone distribution mode is a new mode that can be selected for daily life distribution in the future under the distribution orders in the post epidemic era and the rapid development of science and technology.The research on the online and offline problems of truck-drone distribution can provide some reference for decision-making and scheduling in real life,and expand the scientific research of this mode.In the future,we can research on the online distribution problem of trucks-drones and the distribution problem of trucks-drones with time window constraints.