运筹与管理2025，Vol.34Issue(7)：69-75,7.DOI:10.12005/orms.2025.0209
实时需求下卡车与无人机协同配送的在线与离线问题研究
Online and Offline Problems of Truck and Drone Collaborative Delivery under Real-time Demand
摘要
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+√5/2.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 algo-rithm is to make action decisions based on whether the truckis 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 informa-tion,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 perform-ance 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 simu-lation 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分类
信息技术与安全科学引用本文复制引用
余海燕,刘李..实时需求下卡车与无人机协同配送的在线与离线问题研究[J].运筹与管理,2025,34(7):69-75,7.基金项目
国家社会科学基金资助项目(23BGL133) （23BGL133）
重庆市教委人文社会科学项目(22SKJD092) （22SKJD092）
智能物流网络重庆市重点实验室开放基金项目(KLILN2023ZD002) （KLILN2023ZD002）
重庆市研究生导师团队建设项目(JDDSTD2022005) （JDDSTD2022005）
重庆市研究生联合培养基地项目(JDLHPYJD2019005) （JDLHPYJD2019005）
重庆交通大学研究生科研创新项目(2023S0132) （2023S0132）
