Adaptive Hybrid Ant Colony Optimization for Capacitated Vehicle Routing Problem

doi:10.12068/j.issn.1005-3026.2023.12.003

Abstract

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

CLC Number:

TP273

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.

References

[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.)