基于并行模拟退火算法求解时间依赖型车辆路径问题

doi:10.13196/j.cims.2015.06.027

计算机集成制造系统 ›› 2015, Vol. 21 ›› Issue (第6期): 1626-1636.DOI: 10.13196/j.cims.2015.06.027

基于并行模拟退火算法求解时间依赖型车辆路径问题

穆东¹,王超²⁺,王胜春³,周圣川⁴

1.北京交通大学经济管理学院
2.北京工业大学经济与管理学院
3.北京交通大学计算机与信息技术学院
4.青岛市勘察测绘研究院

出版日期:2015-06-30 发布日期:2015-06-30
基金资助:
国家自然科学基金重点资助项目(71132008);国家自然科学基金面上资助项目(71473013);国家留学基金委公派访学资助项目(201207090034)。

Solving TDVRP based on parallel-simulated annealing algorithm

Online:2015-06-30 Published:2015-06-30
Supported by:
Project supported by the National Natural Science Foundation,China(No.71132008,71473013),and the China Scholarship Council,China(No.201207090034).

摘要/Abstract

摘要： 为提高传统串行模拟退火算法求解时间依赖型车辆路径问题的效率,提出一种并行模拟退火算法。该算法首先使用前向插入启发式算法生成初始解,在主从式并行模拟退火算法框架下使用4种邻域搜索法对初始解进行优化。采用Figliozzi测试数据库(包含56个测试问题,顾客数均设定为100)对算法性能进行测试,结果表明在不同时间依赖型行驶函数情形下,当使用6个线程时,并行模拟退火算法相对于传统串行模拟退火算法可以得到近似于5倍的加速比,且均能在较快时间内得到比Figliozzi算法更优的解。因此,并行模拟退火算法能有效地求解时间依赖型车辆路径问题,并且可以灵活地扩展解决其他车辆路径问题和组合优化问题。

关键词: 车辆路径, 时间依赖型, 并行算法, 模拟退火

Abstract: To improve the efficiency of sequential Simulated Annealing(SA)for solving Time Dependent Vehicle Routing Problem(TDVRP),a parallel-Simulated Annealing(p-SA)algorithm was proposed.Push Forward Insertion Heuristic(PFIH)was implemented to generate an initial solution,and four kinds of local search moves within the structure of master-slave p-SA were developed to optimize the initial solution.Computational results were reported for 56 test problems with 100 customers from Figliozzi's benchmark,and the results showed that p-SA could get 5 times speedup when 6 threads was used by comparing with traditional sequential SA,and could get better solutions than Figliozzi's algorithm within an accepted computational time.Therefore,p-SA could solve TDVRP effectively and could be extended to handle other variants of vehicle routing problems and other combinatorial optimization problems.

Key words: vehicle routing, time dependent speeds, parallel algorithm, simulated annealing

中图分类号:

穆东,王超,王胜春,周圣川. 基于并行模拟退火算法求解时间依赖型车辆路径问题[J]. 计算机集成制造系统, 2015, 21(第6期): 1626-1636.

[1]	尚正阳,顾寄南,王建平. 求解带能力约束车辆路径优化问题的改进模拟退火算法[J]. 计算机集成制造系统, 2021, 27(8): 2260-2269.
[2]	李国明,李军华. 带软时间窗随机需求车辆路径问题的算法研究[J]. 计算机集成制造系统, 2021, 27(8): 2270-2281.
[3]	王奕祺,张晓冬. 基于仿真评价方法的适应性合作换线策略[J]. 计算机集成制造系统, 2021, 27(7): 1918-1928.
[4]	尚正阳,顾寄南,潘家保. 考虑LIFO约束的2L-CVRP优化[J]. 计算机集成制造系统, 2021, 27(7): 2134-2143.
[5]	董舒豪,徐志刚,常艳茹,秦开仲,朱建峰,苏开远. 考虑物料装卸点与搬运通道的多行设施布局[J]. 计算机集成制造系统, 2021, 27(5): 1269-1280.
[6]	李海龙,陈发源,计效园,李建斌,周建新. 基于改进SPEA2算法的铸造并行车间主生产计划[J]. 计算机集成制造系统, 2021, 27(4): 1072-1080.
[7]	夏扬坤,邓永东,庞燕,王忠伟,高亮. 带客户分级和需求可拆分的生鲜车辆路径问题[J]. 计算机集成制造系统, 2021, 27(4): 1238-1248.
[8]	高鹏,苏雍贺,靳健,谢祥颖,张长志,陶飞. 基于分布式光伏运维的多类型资源调度技术[J]. 计算机集成制造系统, 2021, 27(3): 787-799.
[9]	杨丽丽,李文龙,孔祥龙,许浩. 混合不确定性鲁棒协同优化设计方法[J]. 计算机集成制造系统, 2021, 27(11): 3282-3290.
[10]	陈久梅,李英娟,胡婷,但斌,李俊. 开放式带时间窗车辆路径问题及变邻域搜索算法[J]. 计算机集成制造系统, 2021, 27(10): 3014-3025.
[11]	任腾,陈玥,向迎春,邢立宁,李思迪. 考虑客户满意度的低碳冷链车辆路径优化[J]. 计算机集成制造系统, 2020, 26(第4): 1108-1117.
[12]	张景玲,冯勤炳,赵燕伟,刘金龙,冷龙龙. 基于强化学习的超启发算法求解有容量车辆路径问题[J]. 计算机集成制造系统, 2020, 26(第4): 1118-1129.
[13]	黄联标,敖银辉. 基于模拟退火算法的多工段系统预防维护策略[J]. 计算机集成制造系统, 2020, 26(9): 2404-2411.
[14]	张景玲,刘金龙,赵燕伟,王宏伟,冷龙龙,冯勤炳. 时间依赖型同时取送货VRP及超启发式算法[J]. 计算机集成制造系统, 2020, 26(7): 1905-1917.
[15]	庞燕,罗华丽,夏扬坤. 基于禁忌搜索算法的废弃家具回收车辆路径优化[J]. 计算机集成制造系统, 2020, 26(5期): 1425-1433.

基于并行模拟退火算法求解时间依赖型车辆路径问题

Solving TDVRP based on parallel-simulated annealing algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics