货车搭载多架无人机车辆路径问题模型及算法  

Model and algorithm for a vehicle routing problem using multiple drones

作　　者：刘艳秋[1] 韩晶 LIU Yan-qiu;HAN Jing(School of Management,Shenyang University of Technology,Shenyang 110870,China)

机构地区：[1]沈阳工业大学,管理学院,沈阳110870

出　　处：《交通运输工程与信息学报》2022年第3期102-113,共12页Journal of Transportation Engineering and Information

基　　金：国家自然科学基金资助项目(70431003);辽宁省科技重大专项项目(2019JH1/10100028)。

摘　　要：新冠状病毒的流行促使物流业亟须向智慧化转型,无人机参与末端配送成为重要途径之一。货车搭载无人机联合配送,克服了传统货车配送成本高和无人机续航里程短、载荷小的弊端。论文提出货车和无人机“协同+并行”混合配送模式,以总运营成本最小为目标,建立了搭载多架无人机的车辆路径问题混合整数规划模型,设计了基于变维数矩阵编码的两阶段规划求解算法。第一阶段:使用贪婪算法为每个客户确定配送方式和对接点,并以各个对接点为初心进行聚类,再以车辆路径问题为背景,用蚁群算法规划无人机和货车最短路径;第二阶段:将配送方案编码成为变维数矩阵,再根据设计的交换算子进行局部搜索优化,从而得到最优解。算例测算结果验证了“货车+无人机”混合配送比其他配送模式更节省成本,表明了基于变维数矩阵编码的两阶段规划算法具有较好的计算性能,且企业在研发物流配送无人机时不能一味追求续航里程或装载量单方面的优化,而需将续航里程和载重量均衡考虑。Recently,the need for intelligent transformation in the logistics industry has increased due to the prevalence of COVID-19,consequently increasing drone usage in terminal logistics distribution.Moreover,logistics operation modes that support collaboration with trucks enable the disadvantages of existing modes such as high cost,short endurance mileage,and small load to be overcome.Therefore,“cooperation and parallel”mixed distribution strategies between trucks and drones were proposed in this study,where the problem was formulated as a mixed integer linear program.A twostage programming approach based on variable dimension matrix coding was then proposed.The first stage involved the use of a greedy algorithm to determine each customer’s distribution mode and docking points,and to cluster each docking point as the initial center.An ant colony algorithm was then used to determine the shortest drone and truck path based on the vehicle routing problem background.The second stage involved the conversion of the distribution path into variable dimension coding and obtaining the optimal solution through a local search based on the designed exchange operator characteristics.An example scenario was analyzed and its calculation results used to verify the cost-effectiveness of the“truck and drone”hybrid distribution mode over other distribution modes,and to show that the two-stage planning algorithm based on variable dimension matrix coding has better computational performance.Therefore,during the development of logistics distribution drones,focus should be placed on the need to balance endurance mileage and loading capacity,and not on the unilateral optimization of the endurance mileage or loading capacity.

关 键 词：物流工程 车辆路径问题 两阶段规划算法 变维数矩阵编码 货车+无人机 

分 类 号：U491[交通运输工程—交通运输规划与管理]