自适应混合蚁群算法求解带容量约束车辆路径问题

doi:10.12068/j.issn.1005-3026.2023.12.003

摘要/Abstract

摘要： 针对带容量约束车辆路径问题(capacitated vehicle routing problem， CVRP)，提出了一种自适应混合蚁群算法.由蚁群算法生成子回路，为增强跳出局部最优能力，在蚁群算法的状态转移规则和信息素更新规则中引入了自适应机制.基于子回路组合，由遗传算法构造近似解，根据问题编码特性设计了适应度函数和遗传算子，提高了构造效率，并采用Clark和Wright节约算法将近似解修复成可行解.采用扫描法和2-opt局部优化方法提高可行解的质量.标准算例的实验结果表明，该算法在求解CVRP问题上具有良好的寻优精度和寻优效率.灵敏度分析结果表明蚂蚁数量对算法性能具有显著影响.

关键词: 带容量约束车辆路径问题；子回路组合；近似解可行化；自适应混合蚁群算法；灵敏度分析

Abstract: To solve the capacitated vehicle routing problem (CVRP)， an adaptive hybrid ant colony optimization algorithm is proposed. A number of subroutes are obtained using ant colony optimization， and in order to enhance the ability to avoid falling into local optima， adaptive mechanisms are introduced to the rules of pheromone updating and state transferring respectively in ant colony optimization. Based on subroute combining， approximate solutions are constructed using genetic algorithm. According to the characteristics of the encoding scheme， the fitness function and genetic operators are designed to improve construction efficiency. Clarke and Wright savings algorithm is adopted to feasibilize the approximate solutions. Sweep algorithm and 2-opt local search are conducted to enhance the quality of feasible solutions. The experimental results based on standard examples show that the algorithm has good optimization accuracy and efficiency in solving the capacitated vehicle routing problem. Sensitivity analysis results show that the ant quantity has a significant impact on algorithm performance.

Key words: capacitated vehicle routing problem； subroute combining； approximate solution feasibilizing； adaptive hybrid ant colony optimization； sensitivity analysis

中图分类号:

TP273

辜勇，刘迪. 自适应混合蚁群算法求解带容量约束车辆路径问题[J]. 东北大学学报（自然科学版）, 2023, 44(12): 1686-1695.

GU Yong， LIU Di. Adaptive Hybrid Ant Colony Optimization for Capacitated Vehicle Routing Problem[J]. Journal of Northeastern University(Natural Science), 2023, 44(12): 1686-1695.

参考文献

[1]李阳，范厚明.求解带容量约束车辆路径问题的混合变邻域生物共栖搜索算法［J］.控制与决策，2018，33(7):1190-1198.(Li Yang，Fan Hou-ming.Hybrid variable neighborhood symbiotic organisms search for capacitated vehicle routing problem［J］.Control and Decision，2018，33(7):1190-1198.)
[2]张瑾，洪莉，戴二壮.求解带容量和时间窗约束车辆路径问题的改进蝙蝠算法［J］.计算机工程与科学，2021，43(8):1479-1487.(Zhang Jin，Hong Li，Dai Er-zhuang.An improved bat algorithm for the vehicle routing problem with time windows and capacity constraints［J］.Computer Engineering & Science，2021，43(8):1479-1487.)
[3]向明尚，张强.求解带容量约束车辆路径问题的离散布谷鸟算法［J］.东北石油大学学报，2021，45(1):95-101，Ⅶ.(Xiang Ming-shang，Zhang Qiang.Discrete cuckoo algorithm for vehicle routing with capacity constraints［J］.Journal of Northeast Petroleum University，2021，45(1):95-101，Ⅶ.)
[4]黄戈文，蔡延光，戚远航，等.自适应遗传灰狼优化算法求解带容量约束的车辆路径问题［J］.电子学报，2019，47(12):2602-2610.(Huang Ge-wen，Cai Yan-guang，Qi Yuan-hang，et al.Adaptive genetic grey wolf optimizer algorithm for capacitated vehicle routing problem［J］.Acta Electronica Sinica，2019，47(12):2602-2610.)
[5]Altabeeb A M，Mohsen A M，Ghallab A.An improved hybrid firefly algorithm for capacitated vehicle routing problem［J］.Applied Soft Computing Journal，2019，84:105728.
[6]Kir S，Yazgan H R，Tüncel E.A novel heuristic algorithm for capacitated vehicle routing problem［J］.Journal of Industrial Engineering International，2017，13(3):323-330.
[7]Sbai I，Krichen S，Limam O.Two meta-heuristics for solving the capacitated vehicle routing problem:the case of the Tunisian Post Office［J］.Operational Research，2022，22:507-549.
[8]Dorigo M，Maniezzo V，Colorni A.Ant system:optimization by a colony of cooperating agents［J］.IEEE Transactions on Systems，Man and Cybernetics，Part B，Cybernetics，1996，26(1):29-41.
[9]刘紫玉，赵丽霞，薛建越，等.面向车辆路径问题的改进蚁群算法研究［J］.河北科技大学学报，2022，43(1):80-89.(Liu Zi-yu，Zhao Li-xia，Xue Jian-yue，et al.Research on vehicle routing problem based on improved ant colony algorithm［J］.Journal of Hebei University of Science and Technology，2022，43(1):80-89.)
[10]唐慧玲，唐恒书，朱兴亮.基于改进蚁群算法的低碳车辆路径问题研究［J］.中国管理科学，2021，29(7):118-127.(Tang Hui-ling，Tang Heng-shu，Zhu Xing-liang.Research on low-carbon vehicle routing problem based on modified ant colony algorithm［J］.Chinese Journal of Management Science，2021，29(7):118-127.)
[11]Zhou Y，Li W D，Wang X M，et al.Adaptive gradient descent enabled ant colony optimization for routing problems［J］.Swarm and Evolutionary Computation，2022，70:101046.
[12]蔡延光，王世豪，戚远航，等.帝国竞争算法求解CVRP［J］.计算机应用研究，2021，38(3):782-786.(Cai Yan-guang，Wang Shi-hao，Qi Yuan-hang，et al.Imperialist competitive algorithm for solving CVRP［J］.Application Research of Computers，2021，38(3):782-786.)
[13]方文婷，艾时钟，王晴，等.基于混合蚁群算法的冷链物流配送路径优化研究［J］.中国管理科学，2019，27(11):107-115.(Fang Wen-ting，Ai Shi-zhong，Wang Qing，et al.Research on cold chain logistics distribution path optimization based on hybrid ant colony algorithm［J］.Chinese Journal of Management Science，2019，27(11):107-115.)
[14]沈斌，周莹君，王家海.基于自适应遗传算法的Job Shop调度问题研究［J］.计算机应用，2009，29(sup2):161-164，188.(Shen Bin，Zhou Ying-jun，Wang Jia-hai.Research of job shop scheduling problem based on self-adaptive genetic algorithm［J］.Journal of Computer Applications，2009，29(sup2):161-164，188.)
[15]刘志硕，申金升，柴跃廷.基于自适应蚁群算法的车辆路径问题研究［J］.控制与决策，2005，20(5):562-566.(Liu Zhi-shuo，Shen Jin-sheng，Chai Yue-ting.Vehicle routing problem based on an adaptive ant colony algorithm［J］.Control and Decision，2005，20(5):562-566.)