求解车辆路径问题的改进微粒群优化算法

摘要/Abstract

摘要： 微粒群优化算法是求解连续函数极值的一个有效方法。研究了用该算法求解车辆路径的问题。设计了求解车辆路径问题的一种新的实数编码方案，将车辆路径问题转化成准连续优化问题，并采用罚函数法处理约束条件。应用该微粒群优化算法求解了多个车辆路径问题的算例，并与遗传算法和双种群遗传算法进行了比较。计算结果表明，该算法可以更有效地求得车辆路径问题的优化解，是解决车辆路径问题的有效方法。

关键词: 车辆路径问题, 微粒群优化, 实数编码, 组合优化

Abstract: Particle Swarm Optimization (PSO) algorithm is a powerful method to find the extremum of a continuous numerical function. A method based on PSO was researched to solve the discrete Vehicle Routing Problem (VRP). The VRP was changed into a quasi-continuous problem by designing a new real coding. Constrained terms in VRP were processed by the penalty function. This proposed algorithm was applied to illustrate its higher searching efficiency in comparison with standard genetic algorithm & double populations genetic algorithm for VRP. Simulation results of several VRP examples demonstrated the effectiveness of this algorithm.

Key words: vehicle routing problem, particle swarm optimization, real coding, combination optimization

中图分类号:

TP14

肖健梅，李军军，王锡淮. 求解车辆路径问题的改进微粒群优化算法[J]. .

XIAO Jian-mei, LI Jun-jun, WANG Xi-huai. Modified particle swarm optimization algorithm for vehicle routing problem1[J]. .

参考文献

［1］ DANTZING G, RAMSER J. The truck dispatching problem［J］. Management Science, 1959, 10(6): 80-91.

[2] CLARKE G, WRIGHT J. Scheduling of vehicles from a central depot to number of delivery points ［J］. Operations Research, 1964, 12(4): 12-18.

[3] 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.］

[4] ZHAO Yanwei, WU Bin, JIANG Li, et al. Double populations genetic algorithm for vehicle routing problem ［J］. Computer Integrated Manufacturing Systems, 2004, 10(3): 303-306 (in Chinese). ［赵燕伟, 吴斌, 蒋丽，等. 车辆路径问题的双种群遗传算法求解方法［J］. 计算机集成制造系统, 2004, 10(3): 303-306.］

[5] LIU Yunzhong, XUAN Huiyu. Application of the ant algorithm to vehicle routing problem ［J］. Information and Control, 2004, 33(2): 249-252 (in Chinese). ［刘云忠, 宣慧玉. 蚂蚁算法在车辆路径问题中的应用研究［J］. 信息与控制, 2004, 33(2): 249-252.］

[6] EBERHART R C, KENNEDY J. A new optimizer using particles swarm theory ［A］. Proceeding of Sixth International Symposium on Micro Machine and Human Science ［C］. Piscataway, NJ, USA: IEEE Service Center, 1995. 39-43.

[7] LI Junjun, WANG Xihuai. A modified particle swarm optimization algorithm ［A］. Proceedings of the 5th World Congress on Intelligent Control and Automation ［C］. Piscataway, NJ, USA: IEEE Service Center, 2004. 354-356.

[8] WANG Xihuai, LI Junjun. Hybrid particle swarm optimization with simulated annealing ［A］. Proceedings of 2004 International Conference on Machine Learning and Cybernetics ［C］. Piscataway, NJ, USA: IEEE Service Center, 2004. 2402-2405.

[9] LI Jun, XIE Binglei, GUO Yaohuang. Genetic algorithm for vehicle scheduling problem with non-full load ［J］. System Engineering - Theory Methodology Applications, 2000, 20(3): 235-239 (in Chinese). ［李军，谢秉磊，郭耀煌. 非满载车辆调度问题的遗传算法［J］. 系统工程理论方法应用，2000，20(3):235-239.］

[1]	李国明,李军华. 带软时间窗随机需求车辆路径问题的算法研究[J]. 计算机集成制造系统, 2021, 27(8): 2270-2281.
[2]	郭羽含,于俊宇,刘万军,张宇,张美琪. 制造业可持续供应链网络建模及求解[J]. 计算机集成制造系统, 2021, 27(7): 2112-2133.
[3]	尚正阳,顾寄南,潘家保. 考虑LIFO约束的2L-CVRP优化[J]. 计算机集成制造系统, 2021, 27(7): 2134-2143.
[4]	夏扬坤,邓永东,庞燕,王忠伟,高亮. 带客户分级和需求可拆分的生鲜车辆路径问题[J]. 计算机集成制造系统, 2021, 27(4): 1238-1248.
[5]	陈久梅,李英娟,胡婷,但斌,李俊. 开放式带时间窗车辆路径问题及变邻域搜索算法[J]. 计算机集成制造系统, 2021, 27(10): 3014-3025.
[6]	任腾,陈玥,向迎春,邢立宁,李思迪. 考虑客户满意度的低碳冷链车辆路径优化[J]. 计算机集成制造系统, 2020, 26(第4): 1108-1117.
[7]	张景玲,冯勤炳,赵燕伟,刘金龙,冷龙龙. 基于强化学习的超启发算法求解有容量车辆路径问题[J]. 计算机集成制造系统, 2020, 26(第4): 1118-1129.
[8]	张景玲,刘金龙,赵燕伟,王宏伟,冷龙龙,冯勤炳. 时间依赖型同时取送货VRP及超启发式算法[J]. 计算机集成制造系统, 2020, 26(7): 1905-1917.
[9]	庞燕,罗华丽,夏扬坤. 基于禁忌搜索算法的废弃家具回收车辆路径优化[J]. 计算机集成制造系统, 2020, 26(5期): 1425-1433.
[10]	丁雪峰,郑静,高攀,赵旭,陆永军,余毅超. 农村“最后一公里”物流拆分装载策略[J]. 计算机集成制造系统, 2019, 25(第9): 2377-2384.
[11]	罗强,饶运清,刘泉辉,李世红. 求解矩形件排样问题的十进制狼群算法[J]. 计算机集成制造系统, 2019, 25(第5): 1169-1179.
[12]	陈久梅,张松毅,但斌. 求解多隔室车辆路径问题的改进粒子群优化算法[J]. 计算机集成制造系统, 2019, 25(第11): 2952-2962.
[13]	李顺勇,但斌,葛显龙. 多通路网络下多车型低碳城市配送问题[J]. 计算机集成制造系统, 2019, 25(第11): 2973-2982.
[14]	韩亚娟,彭运芳,魏航,史保莉. 超启发式遗传算法求解带软时间窗的车辆路径问题[J]. 计算机集成制造系统, 2019, 25(第10): 2571-2579.
[15]	范厚明,杨翔,李荡,李阳,刘鹏程,吴嘉鑫. 基于生鲜品多中心联合配送的半开放式车辆路径问题[J]. 计算机集成制造系统, 2019, 25(第1): 256-266.