考虑同时取送货的车机协同路径优化问题  

Vehicle routing problem with drones for simultaneouspickup and delivery services

作　　者：马华伟[1,2] 宋洋 Ma Huawei;Song Yang(School of Management,Hefei University of Technology,Hefei 230009,China;Key Laboratory of Process Optimization&Intelligent Decision,Hefei 230009,China)

机构地区：[1]合肥工业大学管理学院,合肥230009 [2]过程优化与智能决策教育部重点实验室,合肥230009

出　　处：《计算机应用研究》2023年第5期1335-1340,共6页Application Research of Computers

基　　金：国家自然科学基金资助项目(71971075);国家重点研发计划资助项目(2019YFE0110300)。

摘　　要：考虑到传统同时取送货问题模式单一,无法应对复杂多变情况的现实需要,研究了一种考虑同时取送货的路径优化问题(vehicle routing problem with drones for simultaneous pickup and delivery, VRPD-SPD)。首先,以车辆与无人机总成本最小为优化目标,建立了考虑无人机单架次访问顺序约束的混合整数线性规划模型。其次,提出了一种基于遗传思想的两阶段启发式算法(two-stage heuristic algorithm based genetic, TSHAG),第一阶段结合贪婪算法和节约算法生成初始解,第二阶段通过改进的遗传算法优化初始解,设计了多元组编码方式来提高解码效率,改进了交叉算子来增加邻域解的搜索空间,设计了新的变异算子来提高算法全局寻优性能。最后,算例实验结果表明了TSHAG算法能够有效地解决VRPD-SPD问题。Considering that the traditional simultaneous pickup and delivery mode is single and cannot cope with the complex and changeable reality needs,this paper proposed VRPD-SPD.Firstly,the method used a hybrid integer linear programming model to minimize the total cost between vehicles and drones.Secondly,the algorithm made a TSHAG algorithm.In the first stage,the greedy algorithm combined with the saving algorithm to generate the initial solution.In the second stage,in order to optimize initial solution,the solving process used improved genetic algorithm,which constructed the multivariate encoding mode to boost the decoding efficiency,improved the crossover operator to increase the search space of the neighborhood solution,and designed a new mutation operator to improve the global optimization performance of the algorithm.Finally,the experimental results show that the proposed TSHAG algorithm can solve VRPD-SPD problem effectively.

关 键 词：车机协同 同时取送货 两阶段启发式算法 遗传算法 

分 类 号：U116[交通运输工程] TP18[自动化与计算机技术—控制理论与控制工程]