主管：中国科学院
主办：中国优选法统筹法与经济数学研究会
　　　中国科学院科技战略咨询研究院
中国管理科学

中国管理科学 ›› 2011, Vol. 19 ›› Issue (2): 99-109.

• 论文 • 上一篇    下一篇

多车场带时间窗车辆路径问题的变邻域搜索算法

王征1, 张俊1, 王旭坪2   

  1. 1. 大连理工大学软件学院, 辽宁大连 116620;
    2. 大连理工大学系统工程研究所, 辽宁大连 116024
  • 收稿日期:2010-06-17 修回日期:2011-03-20 出版日期:2011-04-30 发布日期:2011-04-30
  • 作者简介:王征(1978- ),男(汉族),辽宁大连人,大连理工大学软件学院讲师,博士,研究方向:物流配送、智能优化算法分析与设计。
  • 基金资助:

    国家自然科学基金资助项目(70801008);国家自然科学基金重大研究计划(90924006);国家杰出青年基金(70725004);辽宁省博士启动基金(20071091,20081093)

A Modified Variable Neighborhood Search Algorithm for the Multi Depot Vehicle Routing Problem with Time Windows

WANG Zheng1, ZHANG Jun1, WANG Xu-ping2   

  1. 1. School of Software, Dalian University of Technology, Dalian 116620, China;
    2. Institute of System Engineering, Dalian University of Technology, Dalian 116024, China
  • Received:2010-06-17 Revised:2011-03-20 Online:2011-04-30 Published:2011-04-30

PDF (PC)

2486

被引次数

57

摘要： 多车场带时间窗车辆路径问题是车辆路径问题集合中的一个极为复杂、且仍未得到较好解决的问题。针对这一问题,建立了它的整数规划数学模型,提出了一种改进型变邻域搜索算法。该算法在初始解的构造阶段采用聚类方法完成客户的分配,运用混合算子进行局部搜索,通过后优化过程增强寻优效果,引入模拟退火模型对新解的接受进行控制。最后,在Cordeau提出的标准用例上对改进型变邻域算法进行了实验,实验结果更新了大部分目前该问题的最优解,并在算法的稳定性和求解时间上体现出一定优势。实验表明,该算法是一种求解多车场带时间窗车辆路径问题的有效方法。

关键词: 多车场带时间窗车辆路径问题, 变邻域搜索, 后优化, 模拟退火

Abstract: The Multi Depot Vehicle Routing Problem with Time Windows(MDVRPTW)is an important variant of the Vehicle Routing Problem(VRP),which is extremely complex and still not resolvedr well.To solve the problem,mathematical model of the MDVRPTW is constructed and a modified variable neighborhood search algorithm is proposed.In the algorithm,a clustering algorithm is utilized to allocate customers in the initial solution construction phase,a hybrid operator is applied in the local search phase to come up with a local optimal solution,apost optimization procedure is incorporated to further improve the best found solutions,the idea of simulated annealing is introduced to take control of the acceptance of new solutions.The performance of the proposed algorithm is tested on the benchmark instances proposed by Cordeau and compared with other algorithms in the literature.The results indicate that the proposed algorithm is effective in solving the MDVRPTW and showes some advantage both in stability and runtime.And finally most of the old optimal solutions are updated.

Key words: multi depot vehicle routing problem with time windows, variable neighborhood search, post optimization, simulated anneali

中图分类号: