双向行驶的单线铁路列车运行计划问题研究：以“Isaka-Kigali”SGR案例为背景.pdf

Beijing Jiaotong University Masters Thesis 双向行驶的单线铁路列车运行计划问题研究以 “Isaka-Kigali” SGR 案例为背景 Bidirectional Single Track Train Scheduling “Isaka-Kigali” SGR Case Author Prof. Meng Lingyun Advisor Mr. Niyitanga Irene Beijing Jiaotong University May 2021 万方数据 Authorization of Copyright for the thesis The author of this thesis fully understands the regulations of Beijing Jiaotong University concerning the reservation and usage of the theses. Beijing Jiaotong University is authorized to include all or partial content of the thesis into the database for retri, checking and reading, and is also allowed to save and compile the thesis by means of photocopying, reducing and scanning, for consultation and borrowing purposes. Beijing Jiaotong University can the copies and disks of the thesis to relevant state departments or organizations. In addition, Beijing Jiaotong University is authorized to provide document delivery and exchange services to its sister colleges and universities with which interlibrary partnerships have been established. For confidential master’s theses, the authorization is applicable after decryption. Signature of author Signature of advisor Date of signature Date of signature 万方数据 i 学校代码10004 密级公开 University ID 10004 Confidentiality Level Public 北京交通大学 Beijing Jiaotong University Masters Thesis 双向行驶的单线铁路列车运行计划问题研究以“Isaka- Kigali” SGR 案例为背景 Bidirectional Single Track Train Scheduling “Isaka-Kigali” SGR Case Name of author Mr. Niyitanga Irene Student ID 191291458 Name of supervisor Prof. Meng Lingyun Title Professor Master of Engineering in Traffic and Degree Master Transportation Engineering Railway Operation and Management Beijing Jiaotong University May 2021 万方数据 ii Acknowledgement After a very difficult and arduous process, I have finally completed my master’s thesis. Of course I would like to thank my dear teachers, friends and family who supported all along this process. First of all, my esteemed advisor Prof. Meng Lingyun, I would like to thank him from the bottom of my heart i for his full support in all matters which leads me to successfully conduct this research. I am thankful that has been significant in investing his time and ideas, he has been always a good listener and guider which helped me to overcome any challenge and proceed the research. I also acknowledge the ministry of infrastructure in Rwanda and Tanzania Railway Corporation for their supportive data provided to me for this research. special thanks to the advisor of minister for her full support in providing data, advice and suggestions on the use of the data. I am grateful that has been luckiest moment to meet, and discuss with my classmates who have been my supporting team through sharing ideas and challenging each other for bright insights in our research. Thank you all colleagues and friends who supported me all along this journey. My heartfelt thanks goes to my family who always have been my wings and supporting team over the years. They have been there in all life corners to inspire, shape and turn all my thoughts and dreams into reality. 万方数据 北京交通大学硕士专业学位论文 摘要 Beijing Jiaotong University Master’s Thesis Abstract iii “ 由于具有准时性，可靠性和高效性的运输服务，对于货物和旅客而言，铁路运输被 公认为是是陆上运输系统中的最佳的运输方式之一。 因此， 对于铁路运营者而言， 保证旅客运输需求， 提高运输准时性是至关重要的， 并且这也是实现铁路运输行业 经济和环境可持续性的最佳策略之一， 在此方面比其他运输方式更能吸引客户。 优 化列车时刻表能够更加方便旅客从始发站乘车， 并于终到站下车。 在列车时刻表中， 所有列车都有各自的特定路线，在所有车站之间的预定出发和到达时间以及在中 间车站的通过时间。 该列车运行计划问题是所有铁路运营和管理中的关键问题， 涉 及一组列车从始发站，通过中间车站，到达目的地的列车运行计划制定，而又不会 违反列车运行，安全和资源能力约束。 在本文中，我们研究了单线铁路的列车调度问题，并考虑了复杂的运行条件，例如 陆港，国家间站点和边境站点，因为这些站点需要进行大量服务，包括为货物和移 民的海关服务， 海边境和国家间车站的海关服务， 以及主要用于车站的联结和联结 连接到干燥端口，以在货车从干燥端口内的轨道中拉出到货车时允许它们耦合和/ 或解耦。物理上的单线铁路网络是在 Rail Modeler Express 和 EdraMax 编辑器中构 建的， 用于详细描述单线铁路并分析列车时刻表和该线的列车运行。 考虑到列车安 全性， 运行限制以及车站和干线通行能力的限制， 本文提出了一种混合整数线性规 划模型， 旨在最大程度地减少列车运行时间并确保铁路线在两个方向 （东行和西行） 的顺畅运行。 考虑到 Isaka-Kigali 铁路线在边界 Isaka 站有陆港，有位于卢旺达和坦桑尼亚之间 的鲁苏莫边界站以及位于 Keza 的国家间站，该站将伊萨卡（坦桑尼亚）-基加（卢 旺达）标准轨距铁路线连接到邻国布隆迪。本文所提出的数学模型用于 Dar Es Salaam-Isaka-Kigali / Keza-Gitega-Musongati（DIKKM）标准轨距铁路网络。商业 CPLEX 优化软件用于求解该模型，数据来源于卢旺达和坦桑尼亚铁路的运输机构 以及东非运输总体规划的运输部门战略规划报告。 该模型考虑 24 小时的规划时间， 并获得了最优的列车运行时分， 以及东西向行驶的无冲突列车时刻表。 这项研究获 得的结果可作为基础设施和运营计划与管理的基础， 也可作为后续研究的基础， 用 于研究新线建立使得新增的运输需求给线路通过能力带来的影响。 关键词关键词列车运行计划，数学模型，铁路运输，单线铁路，混合整数规划 万方数据 北京交通大学硕士专业学位论文 摘要 Beijing Jiaotong University Master’s Thesis Abstract iv Abstract Railway transportation is known as one of the best modes of land transport system for both freight and passengers due to its punctuality, reliability, and efficiency in terms of service delivery. Thus, it is very important for operators to satisfy customers’ needs through better punctuality as one of the best strategies towards economic and environmental sustainability in the railway transportation sector and attract customers than the rest of the modes of transport. What makes railways to become a better choice for customers is a well-designed schedule/timetable which helps to ensure smooth operations of trains traveling from their origin to the destination stations. In timetable, all trains have their specific routes, predetermined departure and arrival times at/from all stations as well as passing times at the intermediate stations respectively. The train scheduling problem is a critical problem in all railway operations and management, which concerns to the determination of train schedule for a set of trains that travel from their origin stations to their respective destinations visiting some intermediate stations where necessary without violating operational, safety, station and track capacities requirements. In this thesis, we study the single-track train scheduling problem, taking into considerations the stations with complex operations like stations connected to dry port, inter-countries stations, and border stations due to a lot of services which have to be carried out at these stations. These operations Include customs for freights and immigrations services for passengers at both border and inter-countries stations, loading and unloading of both freights and passengers where necessary depending on the demand at the respective stations, as well as coupling and uncoupling mostly for the station which is connected to a dry port to allow coupling and/or uncoupling of wagons when they are pulled from or pushed to the tracks within the dry port. The physical single-track railway line is constructed in rail modeler express and EdraMax editors to detail the single-track railway line and analysis of both timetables and movements of trains along the line. A mixed-integer linear programming MILP model is developed taking into consideration safety, operation constraints as well as station and main track capacity constraints aiming to minimize the trains’ travel time and ensure smooth operations of railway lines in two directions Eastbound and Westbound. 万方数据 北京交通大学硕士专业学位论文 摘要 Beijing Jiaotong University Master’s Thesis Abstract v The developed mathematical model is used in the case study of Dar Es Salaam-Isaka- Kigali/Keza-Gitega-Musongati DIKKM Standard Gauge Railway network, considering the Isaka-Kigali railway line which has a dry port at Isaka station, a border station at Rusumo between Rwanda and Tanzania, and an inter-countries station at Keza which connects the Isaka Tanzania-Kigali Rwanda standard gauge railway line to the Isaka- Musongati branch line of the neighboring country Burundi. A commercial CPLEX optimization software is used to solve the developed mixed-integer linear programming model using data obtained from the feasibility studies and transportation sector strategic planning reports from the institutions responsible for railway transportation in Rwanda and Tanzania as well as in the East African Community transportation master plan. The one-day time horizon was considered and the optimal trains travel times obtained, the free conflicts train schedule/timetable for trains heading to both eastbound and westbound directions is presented from the real-case data. The results obtained in this study can be used by railway operators and decision makers as a basis in planning and management of both infrastructures and operations, and further studies can use it as a basis to carry out the research on the increase of the capacity of this line according to the rise in traffic demand due to the newly built branch lines. Keywords Train scheduling, mathematical model, railway transportation, single-track, mixed-integer linear programming. 万方数据 北京交通大学硕士专业学位论文 目录 Beijing Jiaotong University Master’s Thesis Table of Contents 6 Table of Contents ACKNOWLEDGEMENT .................................................................................................................. II 中文摘要中文摘要 ..................................................................................................................................... III ABSTRACT ................................................................................................................................... IV LIST OF FIGURES ........................................................................................................................ VIII LIST OF TABLES ............................................................................................................................ IX 1 INTRODUCTION .................................................................................................................. 1 1.1 BACKGROUND ........................................................................................................................... 1 1.2 MOTIVATION ............................................................................................................................ 5 1.3 OBJECTIVE ............................................................................................................................... 7 1.4 SCOPE OF THE RESEARCH ............................................................................................................. 8 1.5 SIGNIFICANCE OF THE RESEARCH ................................................................................................... 8 1.6 THESIS OUTLINE ........................................................................................................................ 9 2 LITERATURE REVIEW ......................................................................................................... 10 2.1 REVIEW PAPERS ....................................................................................................................... 10 2.2 LITERATURE ON TRAIN SCHEDULING PROBLEM .............................................................................. 11 2.2.1 Mathematical Programming Models ........................................................................ 12 2.2.2 Simulation Models .................................................................................................... 18 2.3 LITERATURE ON TRAIN RESCHEDULING PROBLEM ........................................................................... 19 2.3.1 Literature with both Mathematical and Simulation Models ..................................... 20 2.3.2 Simulation Models .................................................................................................... 21 2.3.3 Mathematical models ............................................................................................... 23 2.4 LITERATURE ON BOTH TRAIN SCHEDULING AND RESCHEDULING PROBLEMS ......................................... 25 2.5 SUMMARY AND DISCUSSION ON THE LITERATURE REVIEW ............................................................... 27 2.6 REVIEW ON THE FIRST STUDIES IN THE RELEVANT LITERATURE .......................................................... 28 3 MODEL ULATION AND SOLUTION APPROACH .......................................................... 31 3.1 AN OVERVIEW OF SINGLE TRACK RAILWAY SYSTEMS ......................................................................... 31 3.1.1 Train movements over single track railway lines ...................................................... 31 3.1.2 Schedule/Timetable analysis for single track railway systems .................................. 32 万方数据 北京交通大学硕士专业学位论文 目录 Beijing Jiaotong University Master’s Thesis Table of Contents 7 3.2 THE PROBLEM CONCEPTUAL ILLUSTRATION AND ASSUMPTIONS .......................................................... 34 3.3 NOTATIONS ............................................................................................................................ 35 3.3.1 Subscripts .................................................................................................................. 35 3.3.2 Parameters ................................................................................................................ 36 3.3.3 Decision variables ..................................................................................................... 36 3.4 OBJECTIVE FUNCTION ............................................................................................................... 37 3.5 CONSTRAINTS ......................................................................................................................... 38 3.5.1 Operational constraints ............................................................................................ 38 3.6 SOLUTION APPROACH ............................................................................................................... 41 3.6.1 Used software CPLEX optimization software and EdrawMax .................................. 42 3.6.2 Solution framework ................................................................................................... 42 4 COMPUTATIONAL RESULTS ON THE ISAKA-KIGALI RAILWAY LINE CASE STUDY ................... 44 4.1 THE ISAKA-KIGALI STANDARDS GAUGE RAILWAY LINE ..................................................................... 44 4.1.1 Solution procedure of train Scheduling Problem ....................................................... 46 4.2 RESULTS AND ANALYSIS ............................................................................................................. 46 5 CONCLUSION .................................................................................................................... 51 6 REFERENCES ..................................................................................................................... 52 7 AUTHOR PROFILE AND RESEARCH AC