考虑超重超远客户的卡车无人机协同配送研究
Truck-drone Joint Delivery with Consideration Given to Customers with Great Demands and at Great Distances
宋瑞 1边疆 1何世伟 1迟居尚1
作者信息
- 1. 北京交通大学综合交通运输大数据应用技术交通运输行业重点实验室,北京 100044
- 折叠
摘要
卡车与无人机配送的母船模式是指卡车搭载无人机至离客户较近的地点后,由无人机起飞配送多个客户点,再与卡车汇合的协同配送方法,是交通工程领域中具有潜力的重要发展方向之一.考虑到现实中存在部分客户点需求量超出无人机最大载重,或所处位置超过无人机最大航程覆盖范围的情况,在母船模式基础上,提出考虑超重超远客户的卡车与无人机协同配送模式(Truck-Drone Joint Delivery with Consideration of Customers with Great Demands and at Great Dis-tances,TDJD-CGDGD).该模式允许卡车服务超重超远客户,并允许无人机起降于不同地点.该模式下待求解的问题为含无人机的旅行商问题.以最小化总配送成本为 目标,构建了混合整数线性规划模型.为高效求解大规模算例,提出了一种融合贪婪随机自适应搜索(GRASP)与 自适应大邻域搜索(ALNS)的混合算法.算法首先在附加约束条件下,生成车机共同配送路径,该约束可简化车机路径优化过程.随后放松附加约束,针对性地调整一部分无人机路径,进一步降低总成本.试验结果表明:所提算法具有较好的计算性能;本协同配送模式与仅由卡车配送的传统模式相比可平均节约成本19％;允许无人机在超重客户点处起降与不允许情况相比可平均节约成本5％.
Abstract
The truck-drone delivery mothership system refers to a joint delivery pattern in which a truck carries drones to locations close to customers,launches these drones to serve multiple customers,and then retrieves the drones.This is an important development direction with potential in the field of traffic engineering.Owing to the demands of some customers related to the load capacity of a drone and locations outside the flight range of a drone,a truck-drone joint delivery system that considers customers with greater demands and at greater distances(TDJD-CGDGD)based on the mothership system is proposed,where the truck is allowed to serve customers in question and drones can be retrieved at different locations from where they are launched.This delivery pattern can be viewed as a traveling salesman problem for drones.An MILP model aimed at minimizing the total delivery cost was formulated.To solve large-scale instances efficiently,an algorithm hybridizing the greedy randomized adaptive search procedure(GRASP)and adaptive large neighborhood search(ALNS)was developed.This algorithm first routes trucks and drones with an additional constraint that can simplify truck-drone simultaneous routing.This additional constraint is then relaxed,and the algorithm focuses on adjusting the drone routes to further reduce the total cost.It was found that our algorithm had good performance;TDJD-CGDGD achieved an average cost saving of 19％compared to truck-only delivery,allowing drones to be launched and retrieved to service customers with high demands,resulting in an average cost saving of 5％compared to not allowing this function.
关键词
交通工程/协同配送/自适应大邻域搜索/无人机/路径规划Key words
traffic engineering/joint delivery/adaptive large neighborhood search/drone/routing problem引用本文复制引用
基金项目
国家自然科学基金(62076023)
中国国家铁路集团有限公司科技研发计划(N2023X028)
出版年
2024
NETL
NSTL
万方数据