一种大规模车辆路径问题的启发式算法

涂 伟; 李清泉; 方志祥

一种大规模车辆路径问题的启发式算法

涂伟^1,2,
李清泉^3,1,2,
方志祥^1,2

1 武汉大学测绘遥感信息工程国家重点实验室,武汉市珞喻路129号,430079; 2 武汉大学时空数据智能获取技术与应用教育部工程研究中心,武汉市珞喻路129号,430079; 3 时空信息智能感知与服务深圳市重点实验室,深圳市南山区南海大道3688号,518060

基金项目: 国家863计划资助项目(2011AA110403,2011AA110404）;国家973计划资助项目(2010CB732100);湖北省自然科学基金资助项目（2010CDBO8407）.

详细信息

中图分类号: P208
计量
- 文章访问数: 1629
- HTML全文浏览量: 80
- PDF下载量: 969
出版历程
- 收稿日期: 2012-12-14
- 发布日期: 2013-03-04

A Heuristic Algorithm for Large Scale Vehicle Routing Problem

TU Wei^1,2,
LI Qingquan^3,1,2,
FANG Zhixiang^1,2

1 State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing,Wuhan University, 129 Luoyu Road , Wuhan 430079, China;2 Engineering Research Center for Spatial\|temporal Data Smart Acquisition and Application, Ministry of Education,Wuhan University, 129 Luoyu Road, Wuhan 430079, China;3 Shenzhen Key Laboratory of Spatial\|temporal Smart Sensing and Services, 3688 Nanhai Avenue, Shenzhen 518060, China

摘要

摘要: 针对大规模物流配送,提出了一种集成模拟退火机制和Voronoi长边引导优化的启发式算法。模拟退火机制控制局部搜索过程,Voronoi长边发现解中不合理的空间结构,引导局部搜索过程,从而优化路径质量。实验结果表明,本文算法的搜索性能良好,能够在较短时间内给出高质量的车辆路径安排方案。
- 物流 /
- 车辆路径问题 /
- 模拟退火 /
- 局部搜索 /
- Voronoi
Abstract: A heuristic algorithm integrating simulated annealing and Voronoi long edge guided optimization is proposed for large scale vehicle routing problem. The simulated annealing strategy is employed to accept some bad neighborhood solutions in local search. Voronoi long edge guides to improve the unreasonable local structure in routes. A large scale vehicle routing benchmark instances is designed to test the proposed algorithm. The results show that the proposed algorithm can provide high quality solution in a short time.
- logistic /
- vehicle routing problem /
- simulated annealing /
- local search /
- Voronoi

HTML全文

参考文献(12)

[1]	Santos L, Joo C R, Carlos H A. A Web Spatial Decision Support System for Vehilce Routing Using Google Maps[J]. Descision Support Systems, 2011,51: 1\\|9
[2]	梅新,崔伟宏,高飞,等.基于空间聚类的物流配送决策研究[J].武汉大学学报\5信息科学版,2008, 33(4): 371\\| 375
[3]	Laporte G. Fifty Years of Vehicle Routing [J]. Transportation Science, 2009, 43(4): 408\\|416
[4]	Yellow P C. A Computational Modification to the Savings Method of Vehicle Scheduling[J]. Operational Research Quarterly, 1970, 21(2): 281\\|283
[5]	史亚容,万迪昉,李双燕,等.基于GIS的物流配送路线规划研究[J].系统工程理论与实践, 2009, 29(10): 76\\|84
[6]	李清泉,张金亭,黄经南. 一个物流配送优化算法[J]. 武汉大学学报\5信息科学版, 2003, 28(1):9\\|13
[7]	胡大伟,朱志强,胡勇. 车辆路径问题中的模拟退火算法[J]. 中国公路学报, 2006, 19(4): 123\\|126
[8]	Golden B, Raghavan S, Wasil E. The Vehicle Routing Problem: Latest Advances and New Challenges[M]. New York: Springer\\|Verlag, 2008
[9]	Li F Y, Golden B, Wasil E. Very Large\\|Scale Vehicle Routing: New Test Problems, Algorithms, and Results[J]. Computers & Operations Research, 2005,32(5):1 165\\|1 179
[10]	Mester D, Brysy O. Active\\|guided Evolution Strategies for Large\\|scale Capacitated Vehicle Routing Problems[J]. Computers & Operations Research, 2007, 34(10): 2 964\\|2 975
[11]	Chen Jun, Zhao Renliang, Li Zhilin. Voronoi\\|based k\\|order Neighbour Relations for Spatial Analysis[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2004, 59(1/2): 60\\|72
[12]	Okabe A, Satoh T, Furuta T, et al.Generalized Network Voronoi Diagrams: Concepts, Computational Methods, and Application[J]. International Journal of Geographical Information Science, 2008, 22(9): 965\\|994

施引文献

资源附件(0)

计量

文章访问数: 1629
HTML全文浏览量: 80
PDF下载量: 969
被引次数: 0

一种大规模车辆路径问题的启发式算法

计量

出版历程

A Heuristic Algorithm for Large Scale Vehicle Routing Problem

计量

出版历程

目录