作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2012, Vol. 38 ›› Issue (24): 137-140. doi: 10.3969/j.issn.1000-3428.2012.24.033

• 人工智能及识别技术 • 上一篇    下一篇

有数量限制的开放式车辆路径加速算法

陈忆群 1,2,牟来彦 1,陈国明 1,李志业 3   

  1. (1. 广东第二师范学院计算机科学系,广州 510303;2. 中山大学信息科学与技术学院,广州 510275; 3. 广州明舸数码科技有限公司,广州 510315)
  • 收稿日期:2011-09-26 修回日期:2011-12-13 出版日期:2012-12-20 发布日期:2012-12-18
  • 作者简介:陈忆群(1979-),女,讲师、博士研究生、CCF会员,主研方向:机器学习,信息处理;牟来彦,副教授;陈国明,讲师、博士;李志业,高级工程师、硕士
  • 基金资助:
    国家自然科学基金资助项目(61103162);中央高校基本科研业务费专项基金资助项目(1109021170001137105);广东省自然科学基金资助项目(2009170004203010);广东高校优秀青年创新人才培养计划基金资助项目(LYM09137)

Open Vehicle Routing Acceleration Algorithm with Limited Number

CHEN Yi-qun 1,2, MOU Lai-yan 1, CHEN Guo-ming 1, LI Zhi-ye 3   

  1. (1. Department of Computer Science, Guangdong University of Education, Guangzhou 510303, China; 2. School of Information Science and Technology, Sun Yat-Sen University, Guangzhou 510275, China; 3. Guangzhou Mega Digit Tech. Co., Ltd., Guangzhou 510315, China)
  • Received:2011-09-26 Revised:2011-12-13 Online:2012-12-20 Published:2012-12-18

摘要: 设计有数量限制的开放式车辆路径加速禁忌搜索算法,将所有点(包括客户和仓库)做Delaunay三角剖分后,限制问题的解的大多数边与Delaunay三角剖分的边重合。实验结果表明,该算法在保证寻求到相对较优解的前提下,执行速度得到大幅度的提升,解与上界关联紧密,可以应用到其他启发式搜索问题的求解中。

关键词: 开放式车辆路径问题, 禁忌搜索, Delaunay三角剖分, 最近邻居优先, 极坐标扫描

Abstract: This paper makes advantage of the Delaunay triangulation of all customers(including the depot), keeps most edges of the solution overlap the edges of Delaunay triangulation to accelerate an improved Tabu search algorithm. Experimental results show that the algorithm well solves the m-Open Vehicle Routing Problem(OVRP) problem with stable performance, and the solution keeps close with the upper bound. The search techniques proposed can be easily applied for other meta-heuristics for problem solving.

Key words: Open Vehicle Routing Problem(OVRP), Tabu search, Delaunay triangulation, nearest neighbor priority, polar axis scan

中图分类号: