留言板

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

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

考虑整理车厢成本和回程取货的车辆路径问题求解

邢占文,  郭晓汾,  魏娟

downloadPDF
文章导航 > 交通运输工程学报  > 2011 >  11(1): 95-99
邢占文, 郭晓汾, 魏娟. 考虑整理车厢成本和回程取货的车辆路径问题求解[J]. 交通运输工程学报, 2011, 11(1): 95-99. doi: 10.19818/j.cnki.1671-1637.2011.01.016
引用本文: 邢占文, 郭晓汾, 魏娟. 考虑整理车厢成本和回程取货的车辆路径问题求解[J]. 交通运输工程学报, 2011, 11(1): 95-99. doi: 10.19818/j.cnki.1671-1637.2011.01.016
shu
XING Zhan-wen, GUO Xiao-fen, WEI Juan. Solution of vehicle routing problem with backhauls considering cost of arranging freight in carriage[J]. Journal of Traffic and Transportation Engineering, 2011, 11(1): 95-99. doi: 10.19818/j.cnki.1671-1637.2011.01.016
Citation: XING Zhan-wen, GUO Xiao-fen, WEI Juan. Solution of vehicle routing problem with backhauls considering cost of arranging freight in carriage[J]. Journal of Traffic and Transportation Engineering, 2011, 11(1): 95-99. doi: 10.19818/j.cnki.1671-1637.2011.01.016
shu

考虑整理车厢成本和回程取货的车辆路径问题求解

doi: 10.19818/j.cnki.1671-1637.2011.01.016
  • 1.

    长安大学 汽车学院，陕西 西安 710064

  • 2.

    北京交通大学 经济管理学院，北京 100044

基金项目: 

"十一五"国家科技支撑计划项目 2009BAG13A04

详细信息
    作者简介:

    邢占文(1974-), 男, 内蒙古赤峰人, 长安大学工学博士研究生, 从事物流信息化研究

    郭晓汾(1939-), 男, 北京人, 长安大学教授

  • 中图分类号: U492.31

Solution of vehicle routing problem with backhauls considering cost of arranging freight in carriage

  • 1.

    School of Automobile, Chang'an University, Xi'an 710064, Shaanxi, China

  • 2.

    School of Economics and Management, Beijing Jiaotong University, Beijing 100044, China

More Information
    Author Bio:

    XING Zhan-wen(1974-), male, doctoral student, +86-29-82334728, nmgxzw@126.com

    GUO Xiao-fen(1939-), male, professor, +86-29-82334728, xfg@chd.edu.cn

    摘要
  • 摘要: 考虑整理车厢的成本, 建立带回程取货的车辆路径数学模型, 采用禁忌搜索算法对模型进行求解, 并对某大型物流企业在北京市1 d内的配送和收集业务进行了优化, 优化计算在5 s内完成。计算结果表明: 在总路径增长7.8%的情况下, 车辆配送费用比节约算法降低了24.5%, 实现均衡值提高了9.3%。可见, 该算法降低了调度人员工作量, 节约了物流企业运输成本。

     

    Abstract: Considering the cost of arranging freight in carriage, a mathematic model of vehicle routing problem with backhauls was set up, and was solved by using tabu search algorithm. The vehicle routes of a large logistics enterprise with its intraday tasks including delivery and collection business in Beijing were optimized by using the model and the algorithm, and the optimization was completed in 5 s. Calculation result shows that under the condition that the total distance increases by 7.8%, the distribution cost of vehicle reduces by 24.5% compared with saving algorithm, and the equilibrium value increases by 9.3%. The model and the algorithm reduce the workloads of dispatchers and save the transport costs of logistics enterprises.

     

    • HTML全文

  • 图  1  Hi求解框架

    Figure  1.  Solution framework of Hi

    下载: 全尺寸图片 幻灯片

    图  2  禁忌搜索算法求解框架

    Figure  2.  Solution framework of tabu search algorithm

    下载: 全尺寸图片 幻灯片

    图  3  实际路网结构及客户位置

    Figure  3.  Actual network structure and customer locations

    下载: 全尺寸图片 幻灯片

    图  4  实际配送问题的优化结果

    Figure  4.  Optimization result of actual distribution problem

    下载: 全尺寸图片 幻灯片

    表  1  三类算法性能对比

    Table  1.   Performance contrast of three algorithms
    下载: 导出CSV
    • 参考文献(13)
  • [1] 郭伏, 隆颖. 带时窗回程取货的车辆路径问题的算法[J]. 东北大学学报: 自然科学版, 2006, 27(5): 575-578. doi: 10.3321/j.issn:1005-3026.2006.05.027

    GUO Fu, LONG Ying. On the algorithm for VRPBTW(vehicle routing problem with backhauls and time windows)[J]. Journal of Northeastern University: Natural Science, 2006, 27(5): 575-578. (in Chinese) doi: 10.3321/j.issn:1005-3026.2006.05.027
    [2] GOETSCHALCKX M, JACOBS-BLECHA C. The vehicle routing problem with backhauls[J]. European Journal of Operational Research, 1989, 42(1): 39-51. doi: 10.1016/0377-2217(89)90057-X
    [3] DUHAMEL C, POTVI N J Y, ROUSSEAU J M. A tabu search heuristic for the vehicle routing problem with backhauls and time windows[J]. Transportation Science, 1997, 31(1): 49-59. doi: 10.1287/trsc.31.1.49
    [4] TOTHP, VIGO D. A heuristic algorithmfor the symmetric and asymmetric vehicle routing problems with backhauls[J]. European Journal of Operational Research, 1999, 113(3): 528-543. doi: 10.1016/S0377-2217(98)00086-1
    [5] MI NGOZZI A, GIORGI S, BALDACCI R. An exact method for the vehicle routing problem with backhauls[J]. Transportation Science, 1999, 33(3): 315-329. doi: 10.1287/trsc.33.3.315
    [6] SALHI S, NAGY G. Acluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling[J]. Journal of the Operational Research Society, 1999, 50(10): 1034-1042. doi: 10.1057/palgrave.jors.2600808
    [7] 吴泰熙, 陈正芳, 徐俊诚. 含取货之车辆途程问题解法之研究[J]. 工业工程学刊, 2003, 20(6): 651-665.

    WU Tai-shi, CHEN Jeng-fung, XU Jun-cheng. Solving vehicle routing problem with backhauls[J]. Journal of the Chinese Institute of Industrial Engineers, 2003, 20(6): 651-665. (in Chinese)
    [8] KOHEI N. A theorem on the expected complexity of Dijkstra's shortest path algorithm[J]. Journal of Algorithms, 1985, 6(3): 400-408. doi: 10.1016/0196-6774(85)90009-4
    [9] BRANDAO J. A new tabu search algorithmfor the vehiclerouting problem with backhauls[J]. European Journal of Operational Research, 2006, 173(2): 540-555.
    [10] CLARKE G, WRIGHT J W. Scheduling of vehicles from a central depot to a number of delivery points[J]. Operations Research, 1964, 12(4): 568-581. doi: 10.1287/opre.12.4.568
    [11] 胡大伟, 陈诚, 王来军. 带硬时间窗车辆路线问题的混合遗传启发式算法[J]. 交通运输工程学报, 2007, 7(5): 112-117. http://transport.chd.edu.cn/article/id/200705024

    HU Da-wei, CHEN Cheng, WANG Lai-jun. Hybrid-geneticheuristic algorithmof vehicle routing problem with hard timewindows[J]. Journal of Traffic and Transportation Engineering, 2007, 7(5): 112-117. (in Chinese) http://transport.chd.edu.cn/article/id/200705024
    [12] 曹剑东, 郑四发, 廖雁南, 等. 市内集送货问题的混合禁忌搜索算法[J]. 武汉理工大学学报: 交通科学与工程版, 2009, 33(5): 848-851. doi: 10.3963/j.issn.1006-2823.2009.05.009

    CAO Jian-dong, ZHENG Si-fa, LI AO Yan-nan, et al. Optimization of the urban pick up and delivery problem with hybrid tabu search algorithm[J]. Journal of Wuhan University of Technology: Transportation Science and Engineering, 2009, 33(5): 848-851. (in Chinese) doi: 10.3963/j.issn.1006-2823.2009.05.009
    [13] 卜雷, 尹传忠, 赵宜. 铁路行包配送车辆路径问题模型及算法[J]. 同济大学学报: 自然科学版, 2007, 35(8): 1069-1073. doi: 10.3321/j.issn:0253-374X.2007.08.014

    BU Lei, YI N Chuan-zhong, ZHAO Yi. Model and algorithm of vehicle routing problemon railway baggage and parcel[J]. Journal of Tongji University: Natural Science, 2007, 35(8): 1069-1073. (in Chinese) doi: 10.3321/j.issn:0253-374X.2007.08.014
    • 相关文章
    • 施引文献
  • 资源附件(0)
  • 加载中
WeChat 点击查看大图
图(4) / 表(1)
计量
  • 文章访问数:  539
  • HTML全文浏览量:  131
  • PDF下载量:  436
  • 被引次数: 0
出版历程
  • 收稿日期:  2010-09-29
  • 刊出日期:  2011-02-25

目录

    /

    返回文章
    返回

    版权所有《交通运输工程学报》编辑部陕ICP备05001904号-1

    地址：陕西省 西安市 南二环 路中段 长安大学《交通运输工程学报》编辑部（710064） 电话：029-82334388 Email：jygc@chd.edu.cn

    访问总数:今日访问:

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