关键词: 卡车与无人机协同配送, 实时需求, 在线算法, 两阶段离线算法

Abstract: With the continuous improvement of economic level, people have higher requirements for the timeliness of logistics and distribution, especially for high-value and time-sensitive goods such as fresh food and medicine. Traditional logistics and distribution methods are restricted by road conditions, traffic rules and other factors, which can hardly meet people's consumption needs. The truck and drone combination mode is an innovative logistics and distribution mode, which makes full use of the flexibility of drones and the load capacity of trucks, and realizes the complementary advantages of the two transportation tools. This mode can shorten the delivery time, improve the delivery quality, and adapt to people's consumption upgrading needs. However, in the actual delivery process, the dynamic and uncertainty of demand increase the difficulty of delivery. Therefore, the online and offline problems of truck and drone collaborative delivery under real-time demand are proposed.
At present, the research on truck and drone collaborative delivery is still in its infancy, and most of the studies are based on static conditions, that is, the customer demand and location are fixed, and they ignore the dynamic changes that may occur in the actual delivery process, such as demand update, traffic condition, etc. Online algorithm is an effective method to deal with dynamic problems, which can adjust the delivery plan according to the real-time information, but the existing online algorithms are mainly for the traditional vehicle delivery problem, and there are few studies on the online algorithm for truck and drone collaborative delivery. Therefore, it is of practical significance to consider the dynamic factors and design the online algorithm for truck and drone collaborative delivery.
The second part studies the online problem of truck and drone collaborative delivery. First, we prove that the lower bound of the competitive ratio for this problem is 1+52. Second, we design an online RAR algorithm and prove that its upper bound of the competitive ratio on general networks is 3. The core idea of the RAR algorithm is to make action decisions based on whether the truck is at the origin. When there is no pending demand, the truck will stay at the origin. When a new demand arrives, the truck will make a decision based on its current location. If the truck is at the origin, it calls the TSOA algorithm to solve. If the truck is not at the origin, it returns to the origin by the shortest path, and then calls the TSOA algorithm to solve.
The third part studies the offline problem of truck and drone collaborative delivery. Given the order information, the problem aims to determine the demand allocation, rendezvous points and delivery routes for the truck and drones, so as to minimize the latest time for the truck and drones to deliver all demands and return to the delivery center. To solve this problem, we formulate a mixed integer programming model and design a two-stage offline TSOA algorithm, which uses CPLEX solver to solve the model. By comparing the results of the TSOA algorithm and the CPLEX solver, we find that the relative error of the TSOA algorithm is between 0% and 2.74%, which proves the effectiveness of the TSOA algorithm.
The fourth part uses MATLAB software to conduct case simulation and sensitivity analysis for the RAR algorithm, and compares the results of the RAR algorithm and the offline algorithm. It is found that the performance ratio of the RAR algorithm is less than the upper bound of the competitive ratio derived from the theoretical analysis, which indicates that the algorithm performs better than the theoretical expectation in the actual scenario, and verifies the effectiveness of the algorithm.
To summarize, this paper investigates the online and offline problems of truck-UAV cooperative delivery, develops the relevant mathematical model and algorithm, and validates the performance of the algorithm via simulation experiments. Truck-UAV cooperative delivery is a novel logistics delivery mode that can enhance delivery efficiency, lower delivery cost, and accommodate various delivery situations. The research of this paper offers some guidance for the decision-making and planning for logistics delivery in enterprises, and opens up a new avenue for the scientific exploration of this mode. Future research may explore the problem of cooperative delivery with multiple trucks and multiple drones and conduct a deeper analysis.

Key words: trucks and drones coordinate deliveries, real-time demand, online algorithm, two-stage offline algorithm