A Dynamic Service Network Design for Railway Container Transportation and Benders Decomposition
-
摘要: 充分考虑箱流的中转方案,研究铁路集装箱运输动态服务网络的设计方法。以总成本最小为优化目标,构建了铁路集装箱运输动态服务网络设计的线性规划模型。根据模型特点,采用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. -
表 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 表 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 表 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 表 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箱) 表 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 武汉 北京 郑州 表 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 -
[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.002WANG 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.18TANG 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.htmYAN 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.001GAO 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