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

摘要：

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

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

所属期刊栏目：21

分类号：O221.1;U116.2(运筹学)

资助基金：国家自然科学基金重点资助项目71132008;国家自然科学基金面上资助项目71473013;国家留学基金委公派访学资助项目201207090034.Project supported by the National Natural Science Foundation,China71132008,71473013;the China Scholarship Council,China201207090034

在线出版日期：2015-10-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：1626-1636