改进的最大-最小蚂蚁算法在有时间窗车辆路径问题中的应用

摘要/Abstract

摘要： 利用最大－最小策略，最大最小蚂蚁算法减小了蚂蚁算法陷入局部陷阱的可能性。基于对最大最小信息素策略和信息素更新方式的改进，结合快速产生初始解的算法，提出了一种新方法。把该方法应用于有时间窗车辆路径问题，试验结果表明该算法是有效的。

关键词: 蚂蚁算法, 车辆路径问题, 时间窗

Abstract: Max-Min Ant System (MMAS) reduced the possibility of ant system being dropped into the local trap via Max-Min strategy. By improved Max-Min pheromone strategy and the way of updating pheromone，an improved algorithm was proposed by based on the traditional algorithm which gave initial results fast. The proposed algorithm was applied to the Vehicle Routing Problem with Time Window（VRPTW）. The experiment results indicates that the new algorithm is effective.

Key words: ant system, vehicle routing problem, time window

中图分类号:

万旭，林健良，杨晓伟. 改进的最大-最小蚂蚁算法在有时间窗车辆路径问题中的应用[J]. .

WAN Xu ， LIN Jian-liang ， YANG Xiao-wei. Improved MMAS for vehicle routing problem with time window[J]. .

参考文献

［1］ COLORNI A， DORIGO M， MANIEZZO V. Distributed optimization by ant colonics［A］. Proceedings of 1st European Conference on Artificial Life (ECAL91)［C］. Paris, France：Elsevier Publishing，1991. 134-142.

[2] SAVELSBERGH M. Local search for routing problem with time windows［J］. Annals of Operations Research， 1985，16(4)：285-305.

[3] MARIUS M，SOLOMON M. Algorithms for vehicle routing and scheduling problems with time window constraints［J］. Operations Research， 1987，35(2)：763-781.

[4] THANGIAH S，NYGARD K，JUELL P G. A genetic algorithm system for vehicle routing with time window［A］. Proceedings of the Seventh Conference on Artificial Intelligence Applications［C］. Florida， USA: Morgan Koufmann Publishers, 1991.322-325.

[5] JOE L，ROGER L. Multiple vehicle routing with time and capacity constrains using genetic algorithms［A］. Proceedings of the Fifth International Conference on Genetic Algorithms［C］. Florida， USA: AAAI, 1993.452-459.

[6] ZHANG Liping，CHAI Yueting，CAO Rui. Improved genetic algorithm 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.］

[7] LI Jia，WANG Mengguang，TANG Lixin，et al. Special kind of vehicle routing problem［J］. Journal of Northeastern University(Natural Science Edition)， 2001，22(3)：245-248 (in Chinese).［李嘉，王梦光，唐立新，等. 一类特殊的车辆路径问题(VRP)［J］. 东北大学学报(自然科学版)，2001，22(3)：245-248.］

[8] STTZLE T，HOOS H H. Max-Min Ant System［J］. Future Generation Computer Systems， 2000，16(9)： 889-914.

[1]	李国明,李军华. 带软时间窗随机需求车辆路径问题的算法研究[J]. 计算机集成制造系统, 2021, 27(8): 2270-2281.
[2]	尚正阳,顾寄南,潘家保. 考虑LIFO约束的2L-CVRP优化[J]. 计算机集成制造系统, 2021, 27(7): 2134-2143.
[3]	张海平,邓建新. 有决策时间窗匹配问题的决策优化支持模型[J]. 计算机集成制造系统, 2021, 27(6): 1728-1740.
[4]	葛显龙,冉小芬. 基于时间窗指派的污染路径问题[J]. 计算机集成制造系统, 2021, 27(4): 1178-1187.
[5]	夏扬坤,邓永东,庞燕,王忠伟,高亮. 带客户分级和需求可拆分的生鲜车辆路径问题[J]. 计算机集成制造系统, 2021, 27(4): 1238-1248.
[6]	陈久梅,李英娟,胡婷,但斌,李俊. 开放式带时间窗车辆路径问题及变邻域搜索算法[J]. 计算机集成制造系统, 2021, 27(10): 3014-3025.
[7]	任腾,陈玥,向迎春,邢立宁,李思迪. 考虑客户满意度的低碳冷链车辆路径优化[J]. 计算机集成制造系统, 2020, 26(第4): 1108-1117.
[8]	张景玲,冯勤炳,赵燕伟,刘金龙,冷龙龙. 基于强化学习的超启发算法求解有容量车辆路径问题[J]. 计算机集成制造系统, 2020, 26(第4): 1118-1129.
[9]	张景玲,刘金龙,赵燕伟,王宏伟,冷龙龙,冯勤炳. 时间依赖型同时取送货VRP及超启发式算法[J]. 计算机集成制造系统, 2020, 26(7): 1905-1917.
[10]	邱晗光,高敏,甄杰,周继祥. 可选交付方式及时间窗下城市配送服务选项多目标联合定价[J]. 计算机集成制造系统, 2020, 26(7): 1965-1975.
[11]	庞燕,罗华丽,夏扬坤. 基于禁忌搜索算法的废弃家具回收车辆路径优化[J]. 计算机集成制造系统, 2020, 26(5期): 1425-1433.
[12]	王超,高扬,刘超,王明刚. 基于回溯搜索优化算法求解带时间窗和同时送取货的车辆路径问题[J]. 计算机集成制造系统, 2019, 25(第9): 2237-2247.
[13]	丁雪峰,郑静,高攀,赵旭,陆永军,余毅超. 农村“最后一公里”物流拆分装载策略[J]. 计算机集成制造系统, 2019, 25(第9): 2377-2384.
[14]	陈久梅,张松毅,但斌. 求解多隔室车辆路径问题的改进粒子群优化算法[J]. 计算机集成制造系统, 2019, 25(第11): 2952-2962.
[15]	李顺勇,但斌,葛显龙. 多通路网络下多车型低碳城市配送问题[J]. 计算机集成制造系统, 2019, 25(第11): 2973-2982.