混合超启发式法求解大规模VRP的优化研究

摘要：

车辆路径是一类NP(non-deteministic polynomial)完全问题,研究解决车辆路径问题的高质量启发式算法有着重要理论价值和现实意义.提出一种将最近邻搜索法和禁忌搜索法优势相结合的混合超启发式算法,用来解决带容量约束的车辆路径问题.先利用最近邻搜索法构建初步路线,再利用禁忌搜索法对内部线路和互跨线路进行优化.通过对基于标准数据集和6 772个烟草客户真实数据集进行应用验证,新算法在减少线路的总路程上具有显著效果,为大规模车辆路径问题的求解提供了新的求解思路.

关键词：大规模车辆路径问题、容量约束、最近邻搜索、禁忌搜索、混合启发式算法

所属期刊栏目：28

分类号：TP301.6(计算技术、计算机技术)

资助基金：湖北省自然科学基金项目2009CDB338

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

页数：共6页

页码：62-67