收送货同时的城市无人物流配送问题研究  

Research on city unmanned logistics distribution with simultaneous delivery and pickup

作　　者：张昀蔚 韩曙光[1] ZHANG Yunwei;HAN Shuguang(School of Science,Zhejiang Sci-Tech University,Hangzhou 310018,Zhejiang,China;School of Mathematics,Southeast University,Nanjing 211189,Jiangsu,China)

机构地区：[1]浙江理工大学理学院,浙江杭州310018 [2]东南大学数学学院,江苏南京211189

出　　处：《运筹学学报》2023年第3期53-67,共15页Operations Research Transactions

基　　金：国家自然科学基金(No.12071436)。

摘　　要：随着节能减碳的需求和人工智能的快速发展,以无人电动车等为配送装置的城市无人物流配送渐成现实。本文考虑电池容量约束和取送货同时装载容量约束,以最小配送成本为目标函数构建数学规划模型(E-VRPSDP);以列生成法和双向动态标签算法为基础,设计了分支定价算法实现模型的精确求解;针对大规模E-VRPSDP,设计改进模拟退火算法,引入构造可行解算子,将原始解进化成符合约束的可行解,提高了算法的搜索能力;最后,利用已有标准测试集生成测试算例以验证所设计的算法。本文可以为城市无人物流配送的发展提供理论指导和算法支持。With the requirement for the protection of energy saving and emission reduction and also the development of the artificial intelligence,the city logistics distribution that uses unmanned aerial vehicle as distribution device has gradually turned into reality.Considering the battery capacity constraints of device,the charging decision and the pickup and delivery simultaneous demands,a mathematical programming model is constructed with the objective of minimizing the distribution cost(E-VRPSDP).A new branch-cut-and-price algorithm is provided to solve the exact solution based on the column generation method and bi-directional dynamic programming.To solve the large size E-VRPSDP,an improved simulated annealing algorithm is designed.A new operator is introduced as the constructing feasible solution operator which evolves the original solution into a feasible solution,thereby improving the searching ability of the algorithm.Finally,the suitable data examples are generated based on the standard test set to verify the proposed algorithms.The theoretical guidance and algorithm support for city logistics enterprises is provided to develop the driver-less logistics distribution.

关 键 词：车辆路径问题 无人配送 收送货同时 分支定价 模拟退火 

分 类 号：O221.2[理学—运筹学与控制论]