Open Vehicle Routing Acceleration Algorithm with Limited Number

doi:10.3969/j.issn.1000-3428.2012.24.033

Computer Engineering ›› 2012, Vol. 38 ›› Issue (24): 137-140. doi: 10.3969/j.issn.1000-3428.2012.24.033

• Networks and Communications • Previous Articles Next Articles

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

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

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

(1. 广东第二师范学院计算机科学系，广州 510303；2. 中山大学信息科学与技术学院，广州 510275； 3. 广州明舸数码科技有限公司，广州 510315)

作者简介:陈忆群(1979－)，女，讲师、博士研究生、CCF会员，主研方向：机器学习，信息处理；牟来彦，副教授；陈国明，讲师、博士；李志业，高级工程师、硕士
基金资助:
国家自然科学基金资助项目(61103162)；中央高校基本科研业务费专项基金资助项目(1109021170001137105)；广东省自然科学基金资助项目(2009170004203010)；广东高校优秀青年创新人才培养计划基金资助项目(LYM09137)

Abstract

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

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

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

CLC Number:

TP301.6

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.

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

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.3969/j.issn.1000-3428.2012.24.033

http://www.ecice06.com/EN/Y2012/V38/I24/137

References

[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]	ZHENG Chunhui,XU Rui. Hybrid Tabu Search Algorithm for Solving Single Machine Scheduling Problem [J]. Computer Engineering, 2016, 42(4): 282-287,294.
[2]	YANG Dajiang,SONG Changjian,ZHONG Zifa. Signal Detection Based on Tabu Search Under High-order Multiple Input Multiple Output System [J]. Computer Engineering, 2015, 41(12): 140-143,149.
[3]	WANG Meng,LIU Xiaoping,ZOU Yanni. Spherical Texture Mapping Method for Large-scale Point Cloud Data [J]. Computer Engineering, 2015, 41(1): 218-222.
[4]	LI Yu-jian, YIN Chuang-ye, YANG Yong. Image Maximum Weight Matching Model Based on Weight Learning [J]. Computer Engineering, 2014, 40(6): 247-251.
[5]	JIN Yu-Ping, SU Dan-Dan. Research on TIN-based 3D Geological Modeling [J]. Computer Engineering, 2012, 38(7): 279-280,283.
[6]	LI Yong-Gang, DENG Yan-Jing. Improved Particle Swarm Optimization Algorithm with Tabu Search [J]. Computer Engineering, 2012, 38(18): 155-157.
[7]	ZHOU Zhe, LV Sai-Zhe, GU Li-Xu. Mesh Quality Maintenance Technology Based on Loose r-sample [J]. Computer Engineering, 2012, 38(16): 219-222.
[8]	TANG Yang, LI Ying-Zhen. Geometric Construction Method of Linear SVM Multi-class Classifier [J]. Computer Engineering, 2012, 38(04): 152-154.
[9]	BO Li-Jun, FU Zhuo, LIU Chi-Mei. Open Vehicle Routing Problem with Working Time and Time Windows [J]. Computer Engineering, 2012, 38(04): 17-19.
[10]	ZHANG Ai-Jun, QIN Xin-Jiang, GONG Chun-Qiong. Iterated Tabu Search Algorithm for Solving 0-1 Binary Quadratic Programming Problem [J]. Computer Engineering, 2012, 38(01): 140-142.
[11]	ZHANG Yong, SHU Lin-Jie. Classifier Selection Integrated Method Based on Genetic Tabu Search [J]. Computer Engineering, 2011, 37(8): 183-185.
[12]	LI San-Ban, WANG Li-Meng. Multi-start Tabu Search Algorithm for Solving OVRPTW [J]. Computer Engineering, 2011, 37(6): 187-189.
[13]	LI San-Ban, CHAI Yu-Mei, WANG Li-Meng. Research on Split Delivery Open Vehicle Routing Problem [J]. Computer Engineering, 2011, 37(6): 168-171.
[14]	SONG Jian-Wen, HUANG Yang-Fan, LIU Yan-Fei, ZHOU Xiang-Sheng, DUAN Chu-Yu. Research of Motion Compensation Frame Rate Up-conversion Based on Mesh Model [J]. Computer Engineering, 2011, 37(3): 281-283.
[15]	SHU Gong-Qiu, HU Ke, YANG Chun-Hua. LS-SVM Parameter Optimized Selection Based on TS-GA [J]. Computer Engineering, 2011, 37(24): 266-268.

Please choose a citation manager

Content to export

Open Vehicle Routing Acceleration Algorithm with Limited Number

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

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

模态框（Modal）标题

Please choose a citation manager

Content to export

Open Vehicle Routing Acceleration Algorithm with Limited Number

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

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments