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

doi:10.3969/j.issn.1000-3428.2012.24.033

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

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

陈忆群^1,2，牟来彦 ¹，陈国明 ¹，李志业 ³

(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 ¹, CHEN Guo-ming¹, LI Zhi-ye ³

(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

摘要/Abstract

摘要： 设计有数量限制的开放式车辆路径加速禁忌搜索算法，将所有点(包括客户和仓库)做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

中图分类号:

TP301.6

陈忆群, 牟来彦, 陈国明, 李志业. 有数量限制的开放式车辆路径加速算法[J]. 计算机工程, 2012, 38(24): 137-140.

CHEN Yi-Qun, MAO Lai-Pan, CHEN Guo-Meng, LI Zhi-Ye. Open Vehicle Routing Acceleration Algorithm with Limited Number[J]. Computer Engineering, 2012, 38(24): 137-140.

参考文献

[1] Ruiz R, Maroto C, Alcaraz J. A Decision Support System for a Real Vehicle Routing Problem[J]. European Journal of Operational Research, 2004, 153(3): 593-606.
[2] Kortesis G S, Synefaki A, Kalfakakou R. Solving a Vehicle Routing Problem by Balancing the Vehicles Time Utilization[J]. European Journal of Operational Research, 2004, 152(2): 520-527.
[3] Jaszkiewicz A, Kominek P. Genetic Local Search with Distance Preserving Recombination Operator for a Vehicle Routing Problem[J]. European Journal of Operational Research, 2003, 151(2): 352-364.
[4] Prins C. A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem[J]. Computer & Operations Research, 2004, 31(12): 1985-2002.
[5] Brandao J. A Tabu Search Algorithm for the Open Vehicle Routing Problem[J]. European Journal of Operational Research, 2004, 157(3): 552-564.
[6] Lau Hoong-Chuin, Sim M, Teo Kwong-Meng. Vehicle Routing Problem with Time Windows and a Limited Number of Vehicles[J]. European Journal of Operational Research, 2003, 148(3): 559-569.
[7] 王素欣, 高利, 崔小光, 等. 多需求点车辆调度模型及其群体智能混合求解[J]. 自动化学报, 2008, 34(1): 104-106.
[8] Fisher M L. Optimal Solution of Vehicle Routing Problems Using Minimum k-Trees[J]. Operations Research, 1994, 42(4): 626-642.
[9] Fisher M L. A Polynomial Algorithm for the Degree Constrained Minimum k-Tree Problem[J]. Operations Research, 1994, 42(4): 775-779.
[10] Martinhon C, Lucena A, Maculan N. Stronger K-tree Relaxations for the Vehicle Routing Problem[J]. European Journal of Operational Research, 2004, 158(1): 56-71.
[11] Huang G, Lim A. Fragmental Optimization on the 2-machine Bicriteria Flowshop Scheduling Problem[C]//Proc. of the 15th IEEE International Conference on Tools with Artificial Intelligence. [S. l.]: IEEE Press, 2003.
[12] 王凌. 智能优化算法及其应用[M]. 北京: 清华大学出版社, 2001.
[13] Solomon M M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints[J]. Operations Research, 1987, 35(2): 254-265.

[1]	郑春荟,许瑞. 用于求解单机调度问题的混合禁忌搜索算法[J]. 计算机工程, 2016, 42(4): 282-287,294.
[2]	杨大江,宋常建,钟子发. 高阶多输入多输出系统下基于禁忌搜索的信号检测[J]. 计算机工程, 2015, 41(12): 140-143,149.
[3]	靳玉萍, 苏丹丹. 基于TIN的三维地质建模研究[J]. 计算机工程, 2012, 38(7): 279-280,283.
[4]	李勇刚, 邓艳青. 结合禁忌搜索的改进粒子群优化算法[J]. 计算机工程, 2012, 38(18): 155-157.
[5]	周喆, 吕思哲, 顾力栩. 基于Loose r-sample的网格质量保持技术[J]. 计算机工程, 2012, 38(16): 219-222.
[6]	潘立军, 符卓, 刘喜梅. 带工作时间与时间窗的开放式车辆路径问题[J]. 计算机工程, 2012, 38(04): 17-19.
[7]	唐英, 李应珍. 线性支持向量机多类分类器几何构造方法[J]. 计算机工程, 2012, 38(04): 152-154.
[8]	张爱君, 秦新强, 龚春琼. 求解0-1二次规划问题的迭代禁忌搜索算法[J]. 计算机工程, 2012, 38(01): 140-142.
[9]	张永, 朱林杰. 基于遗传禁忌搜索的分类器选择集成方法[J]. 计算机工程, 2011, 37(8): 183-185.
[10]	李三彬, 柴玉梅, 王黎明. 需求可拆分的开放式车辆路径问题研究[J]. 计算机工程, 2011, 37(6): 168-171.
[11]	李三彬, 王黎明. 求解OVRPTW的多开始禁忌搜索算法[J]. 计算机工程, 2011, 37(6): 187-189.
[12]	宋建文, 黄扬帆, 刘艳飞, 周洋生, 段淑玉. 基于网格模型的运动补偿帧频提升研究[J]. 计算机工程, 2011, 37(3): 281-283.
[13]	朱红求, 许珂, 阳春华. 基于TS-GA的LS-SVM参数优选?[J]. 计算机工程, 2011, 37(24): 266-268.
[14]	罗汶锋, 罗家祥. 基于表面贴装分配的改进型禁忌搜索算法[J]. 计算机工程, 2011, 37(13): 288-290.
[15]	彭碧涛, 周永务. 基于禁忌搜索的三维装载车辆路径问题研究[J]. 计算机工程, 2011, 37(11): 190-191,194.

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

Open Vehicle Routing Acceleration Algorithm with Limited Number

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10