留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

涂 伟,  李清泉,  方志祥

downloadPDF
文章导航 > 武汉大学学报 ● 信息科学版  > 2013 >  38(3): 307-310
涂 伟, 李清泉, 方志祥. 一种大规模车辆路径问题的启发式算法[J]. 武汉大学学报 ● 信息科学版, 2013, 38(3): 307-310.
引用本文: 涂 伟, 李清泉, 方志祥. 一种大规模车辆路径问题的启发式算法[J]. 武汉大学学报 ● 信息科学版, 2013, 38(3): 307-310.
shu
TU Wei, LI Qingquan, FANG Zhixiang. A Heuristic Algorithm for Large Scale Vehicle Routing Problem[J]. Geomatics and Information Science of Wuhan University, 2013, 38(3): 307-310.
Citation: TU Wei, LI Qingquan, FANG Zhixiang. A Heuristic Algorithm for Large Scale Vehicle Routing Problem[J]. Geomatics and Information Science of Wuhan University, 2013, 38(3): 307-310.
shu

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

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

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

  • 中图分类号: P208

A Heuristic Algorithm for Large Scale Vehicle Routing Problem

  • 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长边发现解中不合理的空间结构,引导局部搜索过程,从而优化路径质量。实验结果表明,本文算法的搜索性能良好,能够在较短时间内给出高质量的车辆路径安排方案。
    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.
  • [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
  • [1] 曹志鹏, 姜良存, 黄秋钧, 乐鹏, 上官博屹, 罗啊玲, 梁哲恒.  利用破坏重建算法进行物流车辆动态调度 . 武汉大学学报 ● 信息科学版, 2021, 46(5): 755-765, 776. doi: 10.13203/j.whugis20200017
    [2] 徐文学, 杨必胜, 董震, 彭向阳, 麦晓明, 王珂, 高文武.  标记点过程用于点云建筑物提取 . 武汉大学学报 ● 信息科学版, 2014, 39(5): 520-525. doi: 10.13203/j.whugis20130044
    [3] 李精忠, 吴晨琛, 杨泽龙, 黄进.  一种利用模拟退火思想的线状要素Morphing方法 . 武汉大学学报 ● 信息科学版, 2014, 39(12): 1446-1451.
    [4] 刘耀林, 夏寅, 刘殿锋, 洪晓峰.  基于目标规划与模拟退火算法的土地利用分区优化方法 . 武汉大学学报 ● 信息科学版, 2012, 37(7): 762-765.
    [5] 孟妮娜, 艾廷华, 周校东.  建筑群邻近关系相似性计算 . 武汉大学学报 ● 信息科学版, 2012, 37(7): 775-779.
    [6] 易琳, 袁林旺, 罗文, 俞肇元.  顾及V-邻域结构的局部保形插值算法 . 武汉大学学报 ● 信息科学版, 2012, 37(11): 1285-1288.
    [7] 刘耀林, 洪晓峰, 刘殿锋, 夏寅.  利用模拟退火算法的村镇土地利用空间优化调控模型 . 武汉大学学报 ● 信息科学版, 2011, 36(6): 752-755.
    [8] 陈仁喜, 李鑫慧, 李盛阳.  基于MRF的各向异性图像修复模型 . 武汉大学学报 ● 信息科学版, 2010, 35(10): 1231-1235.
    [9] 唐健, 史文中, 孟令奎.  基于遗传算法的时相关动态车辆路径规划模型 . 武汉大学学报 ● 信息科学版, 2008, 33(8): 875-879.
    [10] 桂岚, 龚健雅.  基于路径和模拟退火的交通网络优化算法研究 . 武汉大学学报 ● 信息科学版, 2008, 33(4): 388-392.
    [11] 胡鹏, 范青松, 胡海.  椭球上的测地变换和Voronoi图的生成——地理空间度量 . 武汉大学学报 ● 信息科学版, 2007, 32(9): 825-828.
    [12] 胡海, 刘经南.  障碍空间最大空隙的地图代数解法MA-MAXG(Ω) . 武汉大学学报 ● 信息科学版, 2006, 31(8): 700-703.
    [13] 胡鹏, 王海军, 邵春丽, 胡海.  论多边形中轴问题和算法 . 武汉大学学报 ● 信息科学版, 2005, 30(10): 853-857.
    [14] 颜辉武, 祝国瑞, 徐智勇.  基于动态Voronoi图的距离倒数加权法的改进研究 . 武汉大学学报 ● 信息科学版, 2004, 29(11): 1017-1020.
    [15] 杜维, 艾廷华, 徐峥.  一种组合优化的多边形化简方法 . 武汉大学学报 ● 信息科学版, 2004, 29(6): 548-550.
    [16] 赖红松, 董品杰, 祝国瑞.  基于GASA混合策略的BP网络在基准地价测算中的应用 . 武汉大学学报 ● 信息科学版, 2004, 29(1): 24-28.
    [17] 祝国瑞, 唐旭, 王平.  模拟退火算法在动态建立基准地价模型中的应用 . 武汉大学学报 ● 信息科学版, 2003, 28(5): 593-595,607.
    [18] 刘少创, 林宗坚.  基于可变模板的航空影像中建筑物提取 . 武汉大学学报 ● 信息科学版, 1997, 22(1): 21-28.
    [19] 陈勇, 邓德祥, 郑宏.  串行Cauchy机引导的影像镶嵌方法研究 . 武汉大学学报 ● 信息科学版, 1995, 20(3): 195-197.
    [20] 赖宝珍, 费立凡.  由计算机产生的等距离区域分界线 . 武汉大学学报 ● 信息科学版, 1988, 13(3): 56-64.
  • 加载中
WeChat 点击查看大图
计量
  • 文章访问数:  1141
  • HTML全文浏览量:  41
  • PDF下载量:  955
  • 被引次数: 0
出版历程
  • 收稿日期:  2012-12-15
  • 刊出日期:  2013-03-05

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

  • 1 武汉大学测绘遥感信息工程国家重点实验室,武汉市珞喻路129号,430079; 2 武汉大学时空数据智能获取技术与应用教育部工程研究中心,武汉市珞喻路129号,430079; 3 时空信息智能感知与服务深圳市重点实验室,深圳市南山区南海大道3688号,518060
    • 基金项目:  国家863计划资助项目(2011AA110403,2011AA110404）;国家973计划资助项目(2010CB732100);湖北省自然科学基金资助项目（2010CDBO8407）.
  • 收稿日期: 2012-12-15
  • 刊出日期: 2013-03-05

  • 中图分类号: P208

摘要: 针对大规模物流配送,提出了一种集成模拟退火机制和Voronoi长边引导优化的启发式算法。模拟退火机制控制局部搜索过程,Voronoi长边发现解中不合理的空间结构,引导局部搜索过程,从而优化路径质量。实验结果表明,本文算法的搜索性能良好,能够在较短时间内给出高质量的车辆路径安排方案。

English Abstract

涂 伟, 李清泉, 方志祥. 一种大规模车辆路径问题的启发式算法[J]. 武汉大学学报 ● 信息科学版, 2013, 38(3): 307-310.
引用本文: 涂 伟, 李清泉, 方志祥. 一种大规模车辆路径问题的启发式算法[J]. 武汉大学学报 ● 信息科学版, 2013, 38(3): 307-310.
shu
TU Wei, LI Qingquan, FANG Zhixiang. A Heuristic Algorithm for Large Scale Vehicle Routing Problem[J]. Geomatics and Information Science of Wuhan University, 2013, 38(3): 307-310.
Citation: TU Wei, LI Qingquan, FANG Zhixiang. A Heuristic Algorithm for Large Scale Vehicle Routing Problem[J]. Geomatics and Information Science of Wuhan University, 2013, 38(3): 307-310.
shu

    全文HTML

参考文献 (12)

目录

    /

    返回文章
    返回

    我要投稿

    投稿攻略

    联系我们

    二维码

    版权所有 © 2013 《武汉大学学报·信息科学版》编辑部

    地址：武汉大学文理学部本科生院楼北5楼邮政编码：430072

    电话：027-68778465,68778045E-mail:whuxxb@vip.163.com

    本系统由 北京仁和汇智信息技术有限公司 开发    百度统计