摘要
为提高传统串行模拟退火算法求解时间依赖型车辆路径问题的效率,提出一种并行模拟退火算法。该算法首先使用前向插入启发式算法生成初始解,在主从式并行模拟退火算法框架下使用4种邻域搜索法对初始解进行优化。采用Figliozzi测试数据库(包含56个测试问题,顾客数均设定为100)对算法性能进行测试,结果表明在不同时间依赖型行驶函数情形下,当使用6个线程时,并行模拟退火算法相对于传统串行模拟退火算法可以得到近似于5倍的加速比,且均能在较快时间内得到比Figliozzi算法更优的解。因此,并行模拟退火算法能有效地求解时间依赖型车辆路径问题,并且可以灵活地扩展解决其他车辆路径问题和组合优化问题。
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 Inser- tion 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.
出处
《计算机集成制造系统》
EI
CSCD
北大核心
2015年第6期1626-1636,共11页
Computer Integrated Manufacturing Systems
基金
国家自然科学基金重点资助项目(71132008)
国家自然科学基金面上资助项目(71473013)
国家留学基金委公派访学资助项目(201207090034)~~
关键词
车辆路径
时间依赖型
并行算法
模拟退火
vehicle routing
time dependent speeds
parallel algorithm
simulated annealing
