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

江雨星; 牛惠民; 高如虎

doi:10.3963/j.jssn.1674-4861.2021.01.014

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

doi: 10.3963/j.jssn.1674-4861.2021.01.014

兰州交通大学交通运输学院兰州 730070

基金项目:

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

详细信息

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

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

中图分类号: U294.3
计量
- 文章访问数: 460
- HTML全文浏览量: 231
- PDF下载量: 16
- 被引次数: 0
出版历程
- 收稿日期: 2020-08-07
- 刊出日期: 2021-02-28

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

School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou 730070, China

摘要

摘要: 充分考虑箱流的中转方案，研究铁路集装箱运输动态服务网络的设计方法。以总成本最小为优化目标，构建了铁路集装箱运输动态服务网络设计的线性规划模型。根据模型特点，采用Benders算法进行求解，将问题分解为服务网络设计的主问题及箱流分配的子问题，通过计算子问题的对偶模型不断产生主问题的割平面，由此进行迭代求解。为克服算法收敛速度慢的缺点，在主问题模型中添加有效不等式，使主问题更加紧致。以北京、郑州等集装箱办理站构建的运输网络为例，验证了模型和算法的有效性。算例结果表明，对于求解大规模的集装箱运输动态服务网络设计问题，改进后的算法运行46 s得到优化解，GAP为1.56%，未改进的Benders算法运行相同时间后，GAP为45.17%，改进策略的运用有效提高了计算效率; 所得服务网络的总成本比所有箱流均采用直达运输模式服务网络的总成本减少了20%;与现有集装箱班列开行方案相比，优化后的班列发车时段、开行频率在满足运输需求的同时，保证了各组箱流能在规定运到期限内送至目的站。
- 轨道交通 /
- 集装箱运输 /
- 动态服务网络 /
- 线性混合整数规划 /
- Benders分解算法
Abstract: A method of dynamic service network design for railway container transportation is studied, considering the transfer schemes of containers. A linear programming model of the dynamic service network design for railway container transportation is constructed to minimize the total cost.In accordance with the characteristics of the problem, a solution approach based on Benders decomposition is developed. Then, the formulation is decomposed into a master problem of service network design and subproblems of container flow allocation. The cuts of the master problem are constantly generated by utilizing the solutions of dual subproblems to solve them iteratively. Some valid inequalities are used to tighten the master problem, thus overcoming slow convergence. The effectiveness of the model and algorithm is demonstrated, taking the network constructed by railway container terminals in Beijing and Zhengzhou as a case study. The numerical results indicate that for the design of large-scale dynamic service network, the improved algorithm spends 46 s to obtain an optimized solution, and the Gap is 1.56%. The unimproved Benders decomposition takes the same time, and the Gap is 45.17%. The application of improved strategies can improve calculation. The total cost of the optimized service network is reduced by about 20% compared to the service network with direct transportation organization. Compared with the existing plans for container train service, the optimized departure time and operation frequency of container trains can meet the transportation demand, ensuring that each container flow can be delivered to the destination within the specified transit period.
- rail transit /
- container transport /
- dynamic service network /
- linear mixed-integer programming /
- Benders decomposition

HTML全文

图 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

参考文献(19)

[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