Research on Online and Offline Problems of Truck-drone Distribution
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 distri-bution 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 char-ging 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 refer-ence 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.
truck-dronesonline algorithmthree stage offline algorithmcompetitive ratio
万方数据
维普
