留言板

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

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

铁路集装箱运输动态服务网络设计及Benders分解算法

江雨星 牛惠民 高如虎

江雨星, 牛惠民, 高如虎. 铁路集装箱运输动态服务网络设计及Benders分解算法[J]. 交通信息与安全, 2021, 39(1): 118-127. doi: 10.3963/j.jssn.1674-4861.2021.01.014
引用本文: 江雨星, 牛惠民, 高如虎. 铁路集装箱运输动态服务网络设计及Benders分解算法[J]. 交通信息与安全, 2021, 39(1): 118-127. doi: 10.3963/j.jssn.1674-4861.2021.01.014
JIANG Yuxing, NIU Huimin, GAO Ruhu. A Dynamic Service Network Design for Railway Container Transportation and Benders Decomposition[J]. Journal of Transport Information and Safety, 2021, 39(1): 118-127. doi: 10.3963/j.jssn.1674-4861.2021.01.014
Citation: JIANG Yuxing, NIU Huimin, GAO Ruhu. A Dynamic Service Network Design for Railway Container Transportation and Benders Decomposition[J]. Journal of Transport Information and Safety, 2021, 39(1): 118-127. doi: 10.3963/j.jssn.1674-4861.2021.01.014

铁路集装箱运输动态服务网络设计及Benders分解算法

doi: 10.3963/j.jssn.1674-4861.2021.01.014
基金项目: 

国家自然科学基金面上项目 71771109

详细信息
    作者简介:

    江雨星(1989—),博士研究生,讲师.研究方向:交通运输规划与管理.E-mail:jiangyx@mail.lzjtu.cn

    通讯作者:

    牛惠民(1963—),博士,教授.研究方向:交通运输规划与管理.E-mail:hmniu@mail.lzjtu.cn

  • 中图分类号: U294.3

A Dynamic Service Network Design for Railway Container Transportation and Benders Decomposition

  • 摘要: 充分考虑箱流的中转方案,研究铁路集装箱运输动态服务网络的设计方法。以总成本最小为优化目标,构建了铁路集装箱运输动态服务网络设计的线性规划模型。根据模型特点,采用Benders算法进行求解,将问题分解为服务网络设计的主问题及箱流分配的子问题,通过计算子问题的对偶模型不断产生主问题的割平面,由此进行迭代求解。为克服算法收敛速度慢的缺点,在主问题模型中添加有效不等式,使主问题更加紧致。以北京、郑州等集装箱办理站构建的运输网络为例,验证了模型和算法的有效性。算例结果表明,对于求解大规模的集装箱运输动态服务网络设计问题,改进后的算法运行46 s得到优化解,GAP为1.56%,未改进的Benders算法运行相同时间后,GAP为45.17%,改进策略的运用有效提高了计算效率; 所得服务网络的总成本比所有箱流均采用直达运输模式服务网络的总成本减少了20%;与现有集装箱班列开行方案相比,优化后的班列发车时段、开行频率在满足运输需求的同时,保证了各组箱流能在规定运到期限内送至目的站。

     

  • 图  1  铁路物理网络图

    Figure  1.  Railway physical network

    图  2  动态服务网络

    Figure  2.  Dynamic service network

    图  3  Benders分解算法流程图

    Figure  3.  Flow for Benders decomposition

    图  4  铁路物理网络图

    Figure  4.  Railway physical network

    表  1  班列服务相关参数

    Table  1.   Related parameters of train service

    始发办理站 终到办理站 班列开行成本/(元/列) 班列运行时间/时段 单位集装箱运输成本/(元/箱) 始发办理站 终到办理站 班列开行成本/(元/列) 班列运行时间/时段 单位集装箱运输成本/(元/箱)
    北京 郑州 11 000 2 300 武汉 北京 17 000 4 600
    北京 西安 17 000 4 600 武汉 郑州 11 000 2 300
    北京 武汉 17 000 4 600 武汉 西安 17 000 4 600
    北京 成都 26 000 7 1 050 武汉 成都 23 000 6 900
    北京 兰州 23 000 6 900 武汉 兰州 26 000 7 1 050
    郑州 北京 11 000 2 300 成都 北京 26 000 7 1 050
    郑州 西安 11 000 2 300 成都 郑州 20 000 5 750
    郑州 武汉 11 000 2 300 成都 西安 14 000 3 450
    郑州 成都 20 000 5 750 成都 武汉 23 000 6 900
    郑州 兰州 20 000 5 750 成都 兰州 17 000 4 600
    西安 北京 17 000 4 600 兰州 北京 23 000 6 900
    西安 郑州 11 000 2 300 兰州 郑州 20 000 5 750
    西安 武汉 17 000 4 600 兰州 西安 14 000 3 450
    西安 成都 14 000 3 450 兰州 武汉 26 000 7 1 050
    西安 兰州 14 000 3 450 兰州 成都 17 000 4 600
    下载: 导出CSV

    表  2  箱流信息

    Table  2.   Information of container flows

    箱流序号 出发办理站 目的办理站 箱流量/箱 产生时段 运到期限/时段 最大中转次数
    1 兰州 北京 47 1 7 2
    2 兰州 西安 28 2 5 0
    3 西安 郑州 15 4 4 0
    4 兰州 郑州 20 1 7 1
    5 兰州 武汉 46 1 7 2
    6 西安 成都 25 5 3 1
    7 郑州 西安 12 1 3 0
    8 郑州 成都 23 1 7 2
    9 北京 郑州 35 2 3 0
    10 郑州 武汉 30 4 4 0
    11 北京 武汉 14 1 6 1
    12 郑州 北京 30 5 3 0
    13 西安 兰州 38 4 4 0
    14 郑州 兰州 11 1 6 1
    15 成都 西安 33 1 3 1
    16 成都 郑州 13 1 7 2
    17 武汉 郑州 27 1 4 0
    18 武汉 北京 20 1 7 1
    下载: 导出CSV

    表  3  直达运输模式的集装箱班列开行方案

    Table  3.   Service plan of direct transportation organization

    班列序号 始发办理站 终到办理站 出发时段 班列序号 始发办理站 终到办理站 出发时段
    1 北京 郑州 2 10 西安 兰州 4
    2 北京 武汉 2 11 武汉 北京 1
    3 郑州 北京 5 12 武汉 郑州 2
    4 郑州 西安 1 13 成都 郑州 2
    5 郑州 武汉 5 14 成都 西安 1
    6 郑州 成都 2 15 兰州 北京 1
    7 郑州 兰州 1 16 兰州 郑州 2
    8 西安 郑州 5 17 兰州 西安 2
    9 西安 成都 5 18 兰州 武汉 1
    下载: 导出CSV

    表  4  集装箱班列开行方案

    Table  4.   Service plan of container trains

    班列序号 始发办理站 终到办理站 班列开行频率(列/d) 出发时段 编成箱数
    1 北京 郑州 1 2 共49箱(箱流9的35箱,箱流11的14箱)
    2 郑州 北京 1 6 共50箱(箱流12的30箱,箱流18的20箱)
    3 郑州 西安 1 1 共46箱(箱流7的12箱,箱流8的23箱,箱流14的11箱)
    4 郑州 武汉 1 5 共44箱(箱流10的30箱,箱流11的14箱)
    5 西安 郑州 1 6 共48箱(箱流3的15箱,箱流4的20箱,箱流16的13箱)
    6 西安 成都 1 5 共48箱(箱流6的25箱,箱流8的23箱)
    7 西安 兰州 1 4 共49箱(箱流13的38箱,箱流14的11箱)
    8 武汉 郑州 1 2 共47箱(箱流17的27箱,箱流18的20箱)
    9 成都 西安 1 1 共46箱(箱流15的33箱,箱流16的13箱)
    10 兰州 北京 1 1 共47箱(箱流1的47箱)
    11 兰州 西安 1 2 共48箱(箱流2的28箱,箱流4的20箱)
    12 兰州 武汉 1 1 共46箱(箱流5的46箱)
    下载: 导出CSV

    表  5  箱流中转方案

    Table  5.   Transfer plan of container flows

    箱流序号 出发办理站 目的办理站 中转站 箱流序号 出发办理站 目的办理站 中转站
    1 兰州 北京 10 郑州 武汉
    2 兰州 西安 11 北京 武汉 郑州
    3 西安 郑州 12 郑州 北京
    4 兰州 郑州 西安 13 西安 兰州
    5 兰州 武汉 14 郑州 兰州 西安
    6 西安 成都 15 成都 西安
    7 郑州 西安 16 成都 郑州 西安
    8 郑州 成都 西安 17 武汉 郑州
    9 北京 郑州 18 武汉 北京 郑州
    下载: 导出CSV

    表  6  现有集装箱班列开行方案

    Table  6.   Existing service plan of container trains

    始发办理站 终到办理站 班列开行频率/(列/d) 始发办理站 终到办理站 班列开行频率/(列/d)
    北京 郑州 1.0 武汉 郑州 0.5
    北京 武汉 0.5 西安 郑州 0.5
    郑州 北京 1.0 西安 兰州 1.0
    郑州 西安 0.5 西安 武汉 0.5
    郑州 武汉 0.7 兰州 北京 0.5
    郑州 成都 0.3 兰州 西安 1.0
    武汉 西安 0.5 兰州 成都 1.0
    武汉 成都 0.5
    下载: 导出CSV
  • [1] CRAINIC T G. Service network design in freight transportation[J]. European Journal of Operational Research, 2000, 122 (2): 272-288. doi: 10.1016/S0377-2217(99)00233-7
    [2] DUAN L, TAVASSZY L A, REZAEI J. Freight service network design with heterogeneous preferences for transport time and reliability[J]. Transportation Research Part E: Logistics and Transportation Review, 2019(124): 1-12. http://www.sciencedirect.com/science/article/pii/S1366554518313450
    [3] LULLI G, PIETROPAOLI U, RICCIARDI N. Service net- work design for freight railway transportation: The Italian case[J]. Journal of the Operational Research Society, 2011, 62(12): 2107-2119. doi: 10.1057/jors.2010.190
    [4] 王保华, 何世伟. 考虑车辆周转的铁路动态货运服务网络设计优化模型及其分支-定价-切割算法[J]. 铁道学报, 2018, 40 (2): 8-14. doi: 10.3969/j.issn.1001-8360.2018.02.002

    WANG Baohua, HE Shiwei. Optimization model and branch-pri ce-cut algorithm for design of railway dynamic freight service network considering rolling stock management[J]. Journal of the China Railway Society, 2018, 40(2): 8-14. (in Chinese) doi: 10.3969/j.issn.1001-8360.2018.02.002
    [5] 沈睿. 铁路行包快运服务网络设计理论与方法研究[D]. 北京: 北京交通大学, 2006.

    SHEN Rui. Research on service network for china railway express parcel transportation[D]. Beijing: Beijing Jiaotong University, 2006. (in Chinese)
    [6] 唐金金, 杨露萍, 周磊山. 基于服务网络动态配流的直达列车开行方案优化编制方法[J]. 中国铁道科学, 2016, 37(4): 115-120. doi: 10.3969/j.issn.1001-4632.2016.04.18

    TANG Jinjin, YANG Luping, ZHOU Leishan. Optimal planning method for operation plan of through train based on dynamic traffic assignment of service network[J]. China Railway Science, 2016, 37(4): 115-120. (in Chinese) doi: 10.3969/j.issn.1001-4632.2016.04.18
    [7] 夏阳, 魏玉光, 赖艺欢, 等. 铁路集装箱旅客化运输系统开行方案研究[J]. 交通运输系统工程与信息, 2019, 19(2): 150-156.

    XIA Yang, WEI Yuguang, LAI Yihuan, et al. Line plan of passenger-like transport system of railway container[J]. Journal of Transportation Systems Engineering and Information Technology, 2019, 19(2): 150-156. (in Chinese)
    [8] 张小强, 李保轶, 吴桐, 等. 铁路集装箱班列开行方案与定价综合优化研究[J]. 铁道学报, 2018, 40(11): 1-8.

    ZHANG Xiaoqiang, LI Baoyi, Wu Tong, et al. Research on comprehensive optimization of railway container train scheduling and pricing[J]. Journal of the China Railway Society, 2018, 40(11): 1-8. (in Chinese)
    [9] 闫伟, 朱晓宁, 邓宇君, 等. 中欧班列去程运输组织优化模型[J]. 铁道学报, 2019, 41(2): 1-7. https://www.cnki.com.cn/Article/CJFDTOTAL-TDXB201902001.htm

    YAN Wei, ZHU Xiaoning, DENG Yujun, et al. Optimization model of outbound transportation organization for china railway express[J]. Journal of the China Railway Society, 2019, 41(2): 1-7. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-TDXB201902001.htm
    [10] SHINTANI K, IMAI A, NISHIMURA E, et al. The container shipping network design problem with empty container repositioning[J]. Transportation Research Part E: Logistics and Transportation Review, 2007, 43(1): 39-59. doi: 10.1016/j.tre.2005.05.003
    [11] NGAMCHAI S, LOVELL D J. Optimal time transfer in bus transit route network design using a genetic algorithm[J]. Journal of Transportation Engineering, 2003, 129(5): 510-521. doi: 10.1061/(ASCE)0733-947X(2003)129:5(510)
    [12] CRAINIC T G, HEWITT M, TOULOUSE M, et al. Service network design with resource constraints[J]. Transportation science, 2016, 50(4): 1380-1393. http://d.wanfangdata.com.cn/periodical/04d7d4825db7eca367190a8f48effa9b
    [13] HOLMBERG K, YUAN D. A Lagrangian heuristic based branch-and-bound approach for the capacitated network design problem[J]. Operations Research, 48(3): 461-481. doi: 10.1287/opre.48.3.461.12439
    [14] 高如虎, 牛惠民, 江雨星. 基于多维网络的增开列车条件下高速铁路列车运行图调整[J]. 铁道学报, 2020, 42(5): 1-8. doi: 10.3969/j.issn.1001-8360.2020.05.001

    GAO Ruhu, NIU Huimin, JIANG Yuxing. Train timetable rescheduling based on a time-station-track multi-dimensional network under condition of running extra trains for highspeed railway[J]. Journal of the China Railway Society, 2020, 42(5): 1-8. (in Chinese) doi: 10.3969/j.issn.1001-8360.2020.05.001
    [15] FONTAIN P, MINNER S. Benders decomposition for the hazmat transport network design problem[J]. European Journal of Operational Research, 2018, 267: 996-1002. doi: 10.1016/j.ejor.2017.12.042
    [16] GELAREH S, PISINGER D. Fleet deployment, network design and hub location of liner shipping companies[J]. Transportation Research Part E: Logistics and Transportation Review, 2011, 47(6): 947-964. doi: 10.1016/j.tre.2011.03.002
    [17] 何必胜. 高速铁路列车开行方案与列车运行图协调优化理论与方法研究[D]. 北京交通大学, 2014.
    [18] NAOUM S J, ELHEDHLI S. An interiorpoint Benders based branch-and-cut algorithm for mixed integer programs[J]. Annals of Operations Research, 2013, 210(1): 33-55. doi: 10.1007/s10479-010-0806-y
    [19] FORTZ B, POSS M. An improved Benders decomposition applied to a multilayer network design problem[J]. Operations Research Letters, 2009, 37(5): 359-364. doi: 10.1016/j.orl.2009.05.007
  • 加载中
图(4) / 表(6)
计量
  • 文章访问数:  455
  • HTML全文浏览量:  224
  • PDF下载量:  16
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-08-07
  • 刊出日期:  2021-02-28

目录

    /

    返回文章
    返回