蚁群算法及其在有硬时间窗的车辆路径问题中的应用

摘要/Abstract

摘要： 为求解有硬时间窗的车辆路径问题，提出了一种基于可行解两阶段构造策略的自适应混合蚁群算法。在第一阶段，用蚂蚁的局部遍历代替传统的全局遍历，每个蚂蚁采用蚁群算法进行局部遍历，构造一个回路，蚂蚁转移采用回路两阶段构路策略；在第二阶段，由前一阶段所构造的回路通过采用近似解可行化策略来组合形成可行解。此外，为提高算法的寻优能力，在转移规则中引入了基于时间窗的紧迫性因子和匹配度因子，并与节约算法和爬山法有机结合。实验结果表明，自适应混和蚁群算法性能优良，能够有效地求解有硬时间窗的车辆路径问题。

关键词: 有硬时间窗的车辆路径问题, 自适应混合蚁群算法, 可行解两阶段构造策略, 回路两阶段构造策略, 紧迫性因子, 匹配度因子

Abstract: An Adaptive Hybrid Ant Colony Algorithm (AHACA) based on the two-phase construction procedure of feasible solution was established to solve the Vehicle Routing Problem with Hard Time Window (VRPHTW). There were two phases in the construction of feasible solutions of VRPHTW. In the first phase, ant colony algorithm was applied to construct these sub-tours and the two-phase sub-tour construction procedure was used in its state transition rule. In the second phase, the sub-tours were composed of feasible solutions by means of the feasibility process of approximate solution which could increase the number of optimal feasible solutions in larger scale. Moreover, to increase the ability of optimization and avoid the stagnation phenomenon, some approaches were introduced into the algorithm such as time-window-based urgency degree factor and match degree factor, C-W saving algorithm and 2-opt approach. Experimental results showed that the performance of AHACA was comparable with other meta-heuristic algorithms and could be used in practical VRPHTW with sufficient reliability and speed.

Key words: vehicle routing problem with hard time window, adaptive hybrid ant colony algorithm, two-phase feasible solution construction procedure, two-phase sub-tour construction procedure, urgency degree factor, match degree factor

中图分类号:

刘志硕，柴跃廷，申金升. 蚁群算法及其在有硬时间窗的车辆路径问题中的应用[J]. .

LIU Zhi-shuo,CHAI Yue-ting,SHEN Jin-sheng. Ant colony algorithm for vehicle routing problem with hard time window[J]. .

参考文献

［1］ BALINSKI M, QUANDT R.On an integer program for a delivery problem［J］.Operation Research,1962,10(2):300-304.

[2] RAO M R,ZIONT S.Allocation of transportation units to alternative trips-a column generation scheme with out-of-kilter sub-problems［J］.Operation Research,1968,15(1):52-63.

[3] BERGER J, BARKAOUI M.A parallel hybrid genetic algorithm for the vehicle routing problem with time windows［J］.Computers and Operations Research，2004,31(12):2037-2053.

[4] LI Dawei,WANG Li，WANG Mengguang.Genetic a1gorithm for vehicle routing problem with time windows［J］.Systems Engineering-Theory & Practice,1999,19(8):65-69(in Chinese).［李大卫,王莉,王梦光.遗传算法在有时间窗车辆路径问题上的应用［J］.系统工程理论与实践,1999,19(8):65-69.］

[5] ZHANG Liping,CHAI Yueting,CAO Rui.Improved genetic a1gorithm for vehicle routing problem with time windows［J］.Computer Integrated Manufacturing Systems,2002,8(6):451-454(in Chinese).［张丽萍,柴跃廷,曹瑞.有时间窗车辆路径问题的改进遗传算法［J］.计算机集成制造系统,2002,8(6):451-454.］

[6] BADEAU P,GUERTIN F, GENDREAU M,et al.A parallel tabu search heuristic for the vehicle routing problem with time windows［J］.Transportation Research Part C: Emerging Technologies,1997,5(2):109-122.

[7] PHILIPPE B,FRANCIOS G.A parallel tabu search heuristic for the vehicle routing problem with time window［J］.Transportation Research Part C,1997,5(2):109-122.

[8] ZHANG Jiong,LANG Maoxiang.The tabu search algorithm of distribution vehicle scheduling problem with time windows［J］.Journal of Northern Jiaotong University,2004,28(2):103-106(in Chinese).［张迥,郎茂祥.有时间窗配送车辆调度问题的禁忌搜索算法［J］.北方交通大学学报,2004,28(2):103-106.］

[9] TAN K C, LEE L H, OU K.Artificial intelligence heuristics in solving vehicle routing problems with time window constraints［J］.Engineering Applications of Artificial Intelligence,2001,14(6):825-837.

[10] DORIGO M, MANIEZZO V, COLORNI A.Ant system:optimization by a colony of cooperating agents［A］.IEEE Transaction on System,Man,and Cybernetics,1996,26(1):29-41.

[11] MANIEZZO V,COLORNI A.An ants heuristic for the frequency assignment problem［J］.Future Generation Computer Systems,2000,16(8):927-935.

[12] COLORNI A,DORIGO M,MANIEZZO V,et al.Ant system for job shop scheduling［J］.Operations Research,1994,34(1):39-53.

[13] JOHN E B,PATRICK R M.Ant colony optimization techniques for the vehicle routing problem［J］.Advanced Engineering Informatics,2004,18:41-48.

[14] REIMANN M,DOERNER K, HARTL R F.D-ants: savings based ants divide and conquer the vehicle routing problem［J］.Computers & Operations Research,2004,31:563-591.

[15] GAMBARDELLA L M, TAILLARD E, AGAZZI G.MACS-VRPTW:a multiple ant colony system for vehicle routing problems with time windows［A］.New Ideas in Optimization［C］.London，U.K.:McGraw-Hill,1999.63-73.

[16] REIMANN M, DORENER K, HARTL R F.Insertion based ants for vehicle routing problems with backhauls and time windows［A］.Ant Algorithms［C］.Berlin/Heidelberg,Germany:Springer LNCS 2463,2002.135-147.

[17] LIU Zhishuo.Study on theory and method of intelligent logistics system［D］.Beijing:Beijing Jiaotong University,2004(in Chinese).［刘志硕.智能物流系统理论与方法研究［D］.北京：北京交通大学,2004.］

[18] DORIGO M, LUCA M.A study of some properties of ant-Q［A］.Proceedings of 4th International Conference on Parallel Problem Solving form Nature (PPSN) ［C］.Berlin，Germany:Springer Verlag,1996.656-665.

[19] CLARCK G, WRIGHT J W.Scheduling of vehicles form a central depot to a number of delivery points［J］.Operations Research,1964,12(4):568-581.

[20] STUTZLE T, HOOS H.MAX-MIN ant system［J］.Future Generation Computer Systems Journal,2000,16(8): 889-914.

[21] LANG Maoxiang.Study on models and algorithms for distribution vehicle scheduling problem［D］.Beijing:Beijing Jiaotong University,2002(in Chinese).［郎茂祥.物流配送车辆调度问题的模型与算法研究［D］.北京：北京交通大学,2002.］

[1]	詹欣隆,张超勇,孟磊磊,连裕翔,薛燕社. 面向高效低碳的切削参数与柔性作业车间调度集成建模与优化[J]. 计算机集成制造系统, 2021, 27(12): 3519-3535.
[2]	英聪,张领,肖人彬. 面向圆形布局位置选择的蚁群劳动分工算法[J]. 计算机集成制造系统, 2021, 27(12): 3578-3590.
[3]	苏兆婧,余隋怀,初建杰,于明玖,宫静,黄悦欣. 需求驱动的云平台产品关键设计特征识别方法[J]. 计算机集成制造系统, 2021, 27(12): 3604-3613.
[4]	连裕翔,张超勇,孟磊磊,薛燕社,詹欣隆,吕畅. 基于改进Jaya算法的柔性作业车间调度问题[J]. 计算机集成制造系统, 2021, 27(11): 3172-3184.
[5]	刘雪红,段程,王磊. 基于改进候鸟算法的柔性作业车间分批调度问题[J]. 计算机集成制造系统, 2021, 27(11): 3185-3195.
[6]	孙晨,文龙,李新宇,高亮,丛建臣. 基于自动机器学习的不平衡故障诊断方法[J]. 计算机集成制造系统, 2021, 27(10): 2837-2847.
[7]	顾文斌,李育鑫,钱煜晖,肖紫涵,秦展鹏. 基于激素调节机制IPSO算法的相同并行机混合流水车间调度问题[J]. 计算机集成制造系统, 2021, 27(10): 2858-2871.
[8]	汤雅惠,李彤,朱锐,南峰涛,付会林. 基于执行者过程树的双维度遗传过程挖掘方法[J]. 计算机集成制造系统, 2021, 27(9): 2680-2690.
[9]	尚正阳,顾寄南,王建平. 求解带能力约束车辆路径优化问题的改进模拟退火算法[J]. 计算机集成制造系统, 2021, 27(8): 2260-2269.
[10]	李国明,李军华. 带软时间窗随机需求车辆路径问题的算法研究[J]. 计算机集成制造系统, 2021, 27(8): 2270-2281.
[11]	杨旭亭,王孜悦,李凤鸣,宋锐. 基于过程建模的机器人分阶引导装配方法[J]. 计算机集成制造系统, 2021, 27(8): 2321-2330.
[12]	赵转哲,叶国文,张宇,刘永明,张振,何康. 基于改进的二进制蚁狮算法的特征选择模型及应用[J]. 计算机集成制造系统, 2021, 27(7): 1898-1908.
[13]	赵芮,顾幸生. 基于引力搜索算法的混合零空闲置换流水车间调度[J]. 计算机集成制造系统, 2021, 27(7): 1909-1917.
[14]	尚正阳,顾寄南,潘家保. 考虑LIFO约束的2L-CVRP优化[J]. 计算机集成制造系统, 2021, 27(7): 2134-2143.
[15]	王勇,周雪,刘永,许茂增. 基于车辆共享的多中心共同配送联盟优化[J]. 计算机集成制造系统, 2021, 27(6): 1820-1832.