An Algorithm for Rescheduling of Trains under Planned Track Closures
Abstract
:1. Introduction and Contributions
1.1. Introduction
1.2. Contributions and Structure of the Paper
- First, we formulate a novel joint train rescheduling and closure planning as the nonlinear mixed integer optimization problem valid for a wide class of railway networks with the possibility of rerouting and substitutive transport launching. Moreover, our model allows to control each event (e.g., each train runs conflict) independently, in contrast to the methods applying aggregated approach e.g., as the one presented in Reference [7]. The proposed model and resulting algorithms enable solving investigated decision-making problems for general railway networks, but they have been developed taking also into account the specificity of such networks in Poland.
- Second, due to the high complexity of the formulated initial problem, we propose a multi-level heuristic solution algorithm based on the decomposition allowing the solution of smaller-size sub-problems. The choice of the heuristic algorithm suitable for real-world applications is justified by the NP-hardness of the problem. The proposed formulation of the optimization problem allows for the rationale of this property.
- Third, we confirm the usefulness of the algorithm via the extensive simulation experiments using both randomly generated data but also data originated from the real-world railway network comprising almost 150 stations and 100 trains. The remainder of this paper is organized as follows. Closure planning practices in Poland are outlined in Section 3, and it follows a brief review of related work given in Section 2. The next section presents the model of the considered joint problem of train rescheduling and track closure planning which is based on the graph-matrix representation of a railway network, a train runs timetable, and track closures. Section 5 is devoted to the detailed description of proposed heuristic solution algorithm. The results of experimental evaluation of the algorithm, both for a single track and, first of all, for a real-world case, are given in Section 6. A real-world railway network consisting of up to 95 train runs and 149 train stations serves for the evaluation of the algorithm’s quality with respect to different algorithm’s, as well as problem’s, parameters. Final remarks complete the paper.
2. Related Work
2.1. Train Rescheduling
2.2. Closure Planning
2.3. Joint Approaches
3. Current Closure Planning Practices in Poland
- long-term planning—performed once a year; there is no initial timetable and only long term closures are known in advance and may be taken into consideration, the aim is to prepare an initial closure plan and a timetable; both may be slightly modified later during the year;
- periodic planning—carried out every two months; the initial closure plan and a timetable which were prepared during long-term planning are given, but there is also number of new closure requests which have been appeared meantime; such closures impose changes in closure plan and timetable, so the aim is to obtain new closure plan and modified timetable; however, the new timetable cannot differ much from the initial one; and
- weekly planning—performed once a week, the valid closure plan and timetable obtained during periodic planning are given, but some new, short-term closure requests may appear, and they can be added to the closure plan if only no changes in closure plan and timetable are required.
4. Joint Problem of Train Rescheduling and Track Closure Planning
4.1. Notation
4.2. Representation of a Railway Network
4.3. Representation of Train Timetable
4.4. Representation of Track Closures
4.5. Mathematical Model
4.5.1. Track Closure Planning
4.5.2. Train Rescheduling
4.5.3. Final Model and Its Analysis
- –
- all obligatory closures are performed (1),
- –
- all closure starting times are feasible (2),
- –
- every pair of closures has to be disjoint (3),
- –
- obligatory train runs from set are present in the new timetable (4),
- –
- run times between adjacent stations are fixed (5),
- –
- substitute transport is allowable for selected paths specified in matrix E and only possible if other tracks are not free (6),
- –
- capacities of stations are limited (only in artificial station ‘0’ capacity is unlimited) (7),
- –
- at most one train can occupy one track at every time moment (8),
- –
- the train cannot run by any track if it is canceled (9),
- –
- the total travel time extension cannot exceed the given limit (10),
- –
- the travel time extension on a given distance cannot exceed the given limit (11),
- –
- standing times of trains at stations are limited by the minimum and maximum feasible values (12),
- –
- trains in both original and new timetables go through the same path of stations, but they may go through different tracks (13),
- –
- departure and arrival lateness at selected stations are bounded (14),
- –
- the arrival time of every train at every station must not be later than corresponding departure time (15), and
- –
- no train can occupy a track during a closure (16).
- —set of closures reporting possession of the same track,
- —sub-set of trains with dwell time on the station i coinciding with that of the train run p,
- —sub-set of train runs going from i to j in time coincided with the run of train p,
- —sub-set of track closures on the path from i to j in time coincided with the run of train p,
- —sub-set of train runs waiting at station i in time coincided with the run of train p,
- —set of stations, for which train run p runs a distance less than , but it will reach or exceed this value on arrival to the next station.
5. Heuristic Solution Algorithm
5.1. Managing of Closures
5.2. Managing of Train Runs
Algorithm 1 selection of closures |
Require: Data of the problem, in particular sets , of obligatory, facultative closures, respectively. Ensure: Values of , , as well as closure plan , and timetable .
end if
End for
end if
End for
end if
|
Algorithm 2 selection of trains |
Require: Data of the problem, , , , , specified closure n. Ensure: , , , for specified closure n.
end if
end if
end if
end if
end for
end if
|
Algorithm 3 decomposition of the railway network |
Require: Data of the problem, in particular sets , of selected closures and train runs, respectively, selected train run for rerouting , current train timetable and track closure plan . Ensure: Closure plan , train timetable .
end if
end for
end if
end for
end if
end for
end if
end for
|
5.3. Determining of Time Shifts for Train Runs and Closures
Algorithm 4 determination of time shifts for train runs and closures |
Require: Data for the sub-network: , , . Train run q () selected for rerouting. Closure ordering matrix . Ensure: Time shifts , , and new train routes for .
end if
end if
end if
|
Algorithm 5 determination of time shifts for train runs and closures |
Require: Data for the sub-network: ,, . Train run q () selected for rerouting. Closure ordering matrix . Ensure: Time shifts , , and new train routes for .
end if
end if
end if
end if
end if
end if
end for
end if
end if
|
Algorithm 6 track usage ordering determination |
Require: Selected track . Data for the sub-network: , , . Closure ordering matrix , sets of train runs and closures on the track. Ensure: Locally optimal ordering , or no solution.
end if
end while
|
Algorithm 7 station usage ordering determination |
Require: Selected station i. Data for the sub-network: , , . The ordering of runs and closures for tracks . Ensure: Locally optimal ordering if one was obtained.
end if
end while
|
6. Simulation Experiments
6.1. Single Track Case
Case 1. , | , | , | . |
Case 2. , | , | , | . |
Case 3. , | , | , | . |
Case 4. , | , | , | . |
6.2. Single Track Timetable
- Run station visit order: , arrival and departure times .
- Run station visit order: , arrival and departure times .
- Run station visit order: , arrival and departure times .
- Run station visit order: , arrival and departure times .
6.3. Network of Tracks Case
7. Final Remarks
Author Contributions
Funding
Conflicts of Interest
References
- Arenas, D.; Chevrier, R.; Rodriguez, J.; Dhaenens, C.; Hanafi, S. Application of a co-evolutionary genetic algorithm to solve the periodic railway timetabling problem. In Proceedings of the 2013 IEEE International Conference on Industrial Engineering and Systems Management (IESM), Agdal, Morocco, 28–30 October 2013. [Google Scholar]
- Goverde, R.M.; Besinovic, N.; Binder, A.; Cacchiani, V.; Quaglietta, E.; Roberti, R.; Toth, P. A three-level framework for performance-based railway timetabling. In Proceedings of the 6th International conference on Railway Operations Modelling and Analysis, RailTokyo 2015, Narashimo, Japan, 23–26 March 2015. [Google Scholar]
- Niu, H.; Zhou, X. Optimizing urban rail timetable under time-dependent demand and oversaturated conditions. Transp. Res. Part C Emerg. Technol. 2013, 36, 212–230. [Google Scholar] [CrossRef]
- Barrena, E.; Canca, D.; Coelho, L.C.; Laporte, G. Exact formulations and algorithm for the train timetabling problem with dynamic demand. Comput. Oper. Res. 2014, 44, 66–74. [Google Scholar] [CrossRef]
- Filcek, G.; Gąsior, D.; Hojda, M.; Józefczyk, J. Joint Train Rescheduling and Track Closures Planning: Model and Solution Algorithm. In Information Systems Architecture and Technology: Proceedings of 36th International Conference on Information Systems Architecture and Technology—ISAT 2015–Part I; Springer International Publishing: Berlin/Heidelberg, Germany, 2016; pp. 215–225. [Google Scholar]
- Hojda, M.; Filcek, G. A Joint Problem of Track Closure Planning and Train Run Rescheduling with Detours. In Advances in Intelligent Systems and Computing—Advances in Systems Science 539; Springer International Publishing: Berlin/Heidelberg, Germany, 2017; pp. 285–294. [Google Scholar]
- Bach, L.; Dollevoet, T.; Huisman, D. Integrating timetabling and crew scheduling at a freight railway operator. Transp. Sci. 2016, 50, 878–891. [Google Scholar] [CrossRef] [Green Version]
- Zhang, Y.; D’Ariano, A.; He, B.; Peng, Q. Microscopic optimization model and algorithm for integrating train timetabling and track maintenance task scheduling. Transp. Res. Part B Methodol. 2019, 127, 237–278. [Google Scholar] [CrossRef]
- Zhang, C.; Gao, Y.; Yang, L.; Gao, Z.; Qi, J. Joint optimization of train scheduling and maintenance planning in a railway network: A heuristic algorithm using Lagrangian relaxation. Transp. Res. Part B Methodol. 2020, 134, 64–92. [Google Scholar] [CrossRef]
- Corman, F.; Meng, L. A Review of Online Dynamic Models and Algorithms for Railway Traffic Management. IEEE Trans. Intell. Transp. Syst. 2015, 16, 1274–1284. [Google Scholar] [CrossRef]
- Schobel, A. A model for the delay management problem based on Mixed Integer Programming. Electron. Notes Theor. Comput. Sci. 2001, 50, 1–10. [Google Scholar] [CrossRef] [Green Version]
- Schobel, A. Capacity constraints in delay management. J. Public Transp. 2009, 1, 135–154. [Google Scholar] [CrossRef] [Green Version]
- Brännlund, U.; Lindberg, P.O.; Nõu, A.; Nilsson, J.-E. Railway timetabling using Lagrangian relaxation. Transp. Sci. 1998, 32, 358–369. [Google Scholar] [CrossRef]
- Petersen, E.; Taylor, A. Line block prevention in rail line dispatch and simulation models. Inf. Syst. Oper. Res. 1983, 21, 46–51. [Google Scholar] [CrossRef]
- Ping, L.; Axin, N.; Limin, J.; Fuzhang, W. Study on intelligent train dispatching. In Proceedings of the IEEE Intelligent Transportation Systems Conference Proceedings, Oakland, CA, USA, 25–29 August 2001. [Google Scholar]
- Zhang, Z.; Zhu, C.; Ma, W. Discrete Optimization on Train Rescheduling on Single-Track Railway: Clustering Hierarchy and Heuristic Search. J. Adv. Transp. 2020, 2020. [Google Scholar] [CrossRef]
- Tornquist, J.; Persson, J. N-tracked railway traffic rescheduling during disturbances. Transp. Res. Part B 2007, 41, 342–362. [Google Scholar] [CrossRef]
- Dessouky, M.M.; Lu, Q.; Zhao, J.; Leachman, R.C. An exact solution procedure to determine the optimal dispatching times for complex rail networks. IIE Trans. 2006, 38, 141–152. [Google Scholar] [CrossRef]
- Acuna-Agost, R.; Michelon, P.; Feillet, D.; Guaye, S. Constraint Programming and Mixed Integer Linear Programming for Rescheduling Trains under Disrupted Operations A Comparative Analysis of Models, Solution Methods, and Their Integration. Springer Lect. Notes Comput. Sci. 2009, 5547/2009, 312–313. [Google Scholar]
- Cacchiani, V.; Huisman, D.; Kidd, M.; Kroon, L.; Toth, P.; Veelentruf, L.; Wagenaar, J. An overview of recovery models and algorithms for real-time railway rescheduling. Transp. Res. Part B Methodol. 2014, 63, 15–37. [Google Scholar] [CrossRef] [Green Version]
- Mascis, A.; Pacciarelli, D. Job shop scheduling with blocking and no-wait constraints. Eur. J. Oper. Res. 2002, 143, 498–517. [Google Scholar] [CrossRef]
- Sama, M.; Pellegrini, P.; D’Ariano, A.; Rodriguez, J.; Pacciarelli, D. The potential of the routing selection problem in real-time railway traffic management. In Proceedings of the 7th International Conference on Railway Operations Modelling and Analysis, Lille, France, 4–7 April 2017. [Google Scholar]
- Harrod, S. Modeling network transition constraints with hypergraphs. Transp. Sci. 2011, 45, 81–97. [Google Scholar] [CrossRef]
- He, B.; Song, R.; He, S.; Xu, Y. High-Speed Rail Train Timetabling Problem: A Time-Space Network Based Method with an Improved Branch-and-Price Algorithm. Math. Probl. Eng. 2014, 2014, 15. [Google Scholar] [CrossRef] [Green Version]
- Acuna-Agost, R. Mathematical Modeling and Methods for Rescheduling Trains under Disrupted Operations; Universitéd’Avignon et des Pays de Vaucluse: Avignon, France, 2010. [Google Scholar]
- Tornquist, J.; Persson, J.A. Train traffic deviation handling using Tabu Search and Simulated Annealing. In Proceedings of the 38th Hawaii International Conference on System Sciences (HICSS38), Big Island, HI, USA, 3–6 January 2005. [Google Scholar]
- Veelenturf, L.P.; Kidd, M.P.; Cacchiani, V.; Kroon, L.G.; Toth, P. A railway timetable rescheduling approach for handling large-scale disruptions. Transp. Sci. 2015, 50, 841–862. [Google Scholar] [CrossRef] [Green Version]
- Andersson, E.; Peterson, A.; Törnquist Krasemann, J. Improved Railway Timetable Robustness for Reduced Traffic Delays–a MILP approach. In Proceedings of the 6th International conference on Railway Operations Modelling and Analysis, RailTokyo 2015, Narashimo, Japan, 23–26 March 2015. [Google Scholar]
- Heydar, M.; Petering, M.E.; Bergmann, D.R. Mixed integer programming for minimizing the period of a cyclic railway timetable for a single track with two train types. Comput. Ind. Eng. 2013, 66, 171–185. [Google Scholar] [CrossRef]
- Louwerse, I.; Huisman, D. Adjusting a railway timetable in case of partial or complete blockades. Eur. J. Oper. Res. 2014, 235, 583–593. [Google Scholar] [CrossRef] [Green Version]
- Wang, Y.; Wei, Y.; Zhang, Q.; Shi, H.; Pang, P. Scheduling overnight trains for improving both last and first train services in an urban subway network. Adv. Mech. Eng. 2019, 11, 1–19. [Google Scholar] [CrossRef] [Green Version]
- Altazin, E.; Dauzère-Pérès, S.; Ramond, F.; Tréfond, S. A multi-objective optimization-simulation approach for real time rescheduling in dense railway systems. Eur. J. Oper. Res. 2020, 286, 662–672. [Google Scholar] [CrossRef]
- Zhong, Q.; Zhang, Y.; Wang, D.; Zhong, Q.; Wen, C.; Peng, Q. A Mixed Integer Linear Programming Model for Rolling Stock Deadhead Routing before the Operation Period in an Urban Rail Transit Line. J. Adv. Transp. 2020, 1–18. [Google Scholar] [CrossRef]
- Dekker, R. Applications of maintenance optimization models: A review and analysis. Reliab. Eng. Syst. Saf. 1996, 51, 229–240. [Google Scholar] [CrossRef] [Green Version]
- Higgins, A.; Ferreira, L.; Lake, M. Scheduling rail track maintenance to minimise overall delays. In Proceedings of the 14th International Symposium on Transportation and Traffic Theory, Jerusalem, Israel, 20–23 July 1999. [Google Scholar]
- Budai, G.; Huisman, D.; Dekker, R. Scheduling preventive railway main- tenance activities. J. Oper. Res. Soc. 2006, 57, 1035–1044. [Google Scholar] [CrossRef] [Green Version]
- Higgins, A. Scheduling of railway track maintenance activities and crews. J. Oper. Res. Soc. 1998, 49, 1026–1033. [Google Scholar] [CrossRef]
- Khalouli, S.; Benmansour, R.; Hanafi, S. An ant colony algorithm based on opportunities for scheduling the preventive railway maintenance. In Proceedings of the Control, Decision and Information Technologies (CoDIT), Saint Julian’s, Malta, 6–8 April 2016. [Google Scholar]
- Lidén, T.; Joborn, M. Dimensioning windows for railway infrastructure maintenance: Cost efficiency versus traffic impact. J. Rail Transp. Plan. Manag. 2016, 6, 32–47. [Google Scholar] [CrossRef] [Green Version]
- Lidén, T. Railway infrastructure maintenance-a survey of planning problems and conducted research. Transp. Res. Procedia 2015, 10, 574–583. [Google Scholar] [CrossRef] [Green Version]
- Lidén, T. Survey of Railway Maintenance Activities from a Planning Perspective and Literature Review Concerning the Use of Mathematical Algorithms for Solving Such Planning and Scheduling Problems; Technical Report; Department of Science and Technology, Linköping University: Linköping, Sweden, 2014. [Google Scholar]
- Kiefer, A.; Schilde, M.; Doerner, K. Scheduling of maintenance work of a large-scale tramway network. Eur. J. Oper. Res. 2018, 270, 1158–1170. [Google Scholar] [CrossRef]
- Jovanovic, D.; Harker, P.T. Tactical scheduling of rail operations: The SCAN I system. Transp. Sci. 1991, 25, 46–64. [Google Scholar] [CrossRef]
- Kraay, D.R.; Harker, P.T. Real-time scheduling of freight railroads. Transp. Res. Part B 1995, 29, 213–229. [Google Scholar] [CrossRef]
- Van Zante-de Fokkert, J.I.; den Hertog, D.; van den Berg, F.J.; Verhoeven, J.H.M. The Netherlands schedules track maintenance to improve track workers’ safety. Interfaces 2007, 37, 133–142. [Google Scholar] [CrossRef]
- Albrecht, A.R.; Panton, D.M.; Lee, D.H. Rescheduling rail networks with maintenance disruptions using problem space search. Comput. Oper. Res. 2013, 40, 703–712. [Google Scholar] [CrossRef]
- Albrecht, A. Integrating Railway Track Maintenance and Train Timetables. Ph.D. Thesis, University of South Australia, Adelaide, Australia, 2009. [Google Scholar]
- Forsgren, M.; Aronsson, M.; and Gestrelius, S. Maintaining tracks and traffic flow at the same time. J. Rail Transp. Plan. Manag. 2013, 3, 111–123. [Google Scholar] [CrossRef]
- Lidén, T.; Joborn, M. An optimization model for integrated planning of railway traffic and network maintenance. Transp. Res. Part C Emerg. Technol. 2017, 74, 327–347. [Google Scholar] [CrossRef] [Green Version]
- Lidén, T. Reformulations for Integrated Planning of Railway Traffic and Network Maintenance. In Proceedings of the 18th Workshop on Algorithmic Approaches for Transp. Modelling, Optimization, and Systems, Helsinki, Finland, 23–24 August 2018; Borndörfer, R., Storandt, S., Eds.; Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: Dagstuhl, Germany, 2018; pp. 1:1–1:10. [Google Scholar]
- Lidén, T.; Kalinowski, T.; Waterer, H. Resource considerations for integrated planning of railway traffic and maintenance windows. J. Rail Transp. Plan. Manag. 2018, 8, 1–15. [Google Scholar] [CrossRef]
- Luan, X.; Miao, J.; Meng, L.; Corman, F.; Lodewijks, G. Integrated optimization on train scheduling and preventive maintenance time slots planning. Transp. Res. Part C Emerg. Technol. 2017, 80, 329–359. [Google Scholar] [CrossRef]
- Aken, S.V.; Bešinović, N.; Goverde, R.M.P. Designing alternative railway timetables under infrastructure maintenance possessions. Transp. Res. Part B Methodol 2017, 98, 224–238. [Google Scholar] [CrossRef]
- Arenas, D.; Pellegrini, P.; Hanafi, S.; Rodriguez, J. Timetable rearrangement to cope with railway maintenance activities. Comput. Oper. Res. 2018, 95, 123–138. [Google Scholar] [CrossRef]
- Zhang, C.; Gao, Y.; Yang, L.; Kumar, U.; Gao, Z. Integrated optimization of train scheduling and maintenance planning on high-speed railway corridors. Omega 2019, 87, 86–104. [Google Scholar] [CrossRef]
- Cavone, G.; Blenkers, T.; van den Boom, T.; Dotoli, M.; Seatzu, C.; De Schutter, B. Railway disruption: A bi-level rescheduling algorithm. In Proceedings of the 6th International Conference on Control, Decision and Information Technologies (CoDIT’19), Paris, France, 23–26 April 2019; pp. 54–59. [Google Scholar]
- Cavone, G.; van den Boom, T.; Blenkers, L.; Dotoli, M.; Seatzu, C.; De Schutter, B. An MPC-Based Rescheduling Algorithm for Disruptions and Disturbances in Large-Scale Railway Networks. IEEE Trans. Autom. Sci. Eng. 2020; in print. [Google Scholar]
- Luan, X.; Wang, Y.; De Schutter, B.; Meng, L.; Lodewijks, G.; Corman, F. Integration of real-time traffic management and train control for rail networks—Part 1: Optimization problems and solution approaches. Transp. Res. Part B 2018, 115, 41-–71. [Google Scholar] [CrossRef]
- Yin, J.; Tang, T.; Yang, L.; Xun, J.; Huang, Y.; Gao, Z. Research and development of automatic train operation for railway transportation systems: A survey. Transp. Res. Part C 2017, 85, 548––572. [Google Scholar] [CrossRef]
- Zasady Organizacji i Udzielania Zamknięć Torowych Ir-19. 2015. Available online: http://www.plk-sa.pl/files/public/user_upload/pdf/Akty_prawne_i_przepisy/Instrukcje/Wydruk/Ir-19.pdf (accessed on 30 August 2016).
- Zasady Organizacji i Udzielania Zamknięć Torowych Ir-19. 2018. Available online: https://www.plk-sa.pl/files/public/user_upload/pdf/Akty_prawne_i_przepisy/Instrukcje/Wydruk/Instrukcja_Ir-19.pdf (accessed on 7 September 2020).
- Hoogeveen, J.; van de Velde, S. Scheduling around a small common due date. Eur. J. Oper. Res. 1991, 55, 237–242. [Google Scholar] [CrossRef] [Green Version]
- lp_solve Reference Guide. Available online: http://lpsolve.sourceforge.net/5.5/ (accessed on 30 October 2016).
- Filcek, G.; Gasior, D.; Hojda, M.; Jozefczyk, J. An Algorithm for Rescheduling of Trains under Planned Track Closures—Auxiliary Problem Formulations; ResearchGate: Berlin, Germany, 2017. [Google Scholar] [CrossRef]
- Gonzaga, C. On the Complexity of Linear Programming. Resenhas IME-USP 1995, 2, 197–207. [Google Scholar]
Symbol | Description | Symbol | Description |
---|---|---|---|
matrix of distances between stations (tracks lengths) | set of stations in a railway network | ||
element of representing distance between stations i and j (tracks length) | V | number of stations in a railway network | |
set of numbers indicating tracks between two stations (by default , “0” means a substitute connection which is not a track) | incidence matrix describing existence of tracks between stations | ||
K | maximal number of tracks allowed between two stations (by default ) | element of indicating the existence of track k connecting stations i and j | |
multigraph representing railway network | capacity of station i (the number of trains that can possess the station in the same time moment) |
Symbol | Description | Symbol | Description |
---|---|---|---|
set of train runs (trains) in the timetable | maximal dwell time of a train at a station | ||
number of trains in the timetable | vector describing the original timetable of trains | ||
binary matrix representing the routes of trains | element of describing the timetable of train p (route with corresponding arrival/departure times) | ||
element of referring to track k connecting stations i and j and being a part of the route of train p. | set of obligatory trains | ||
planned arrival time of train p at station i | number of obligatory trains | ||
planned departure time of train p from station i | limit of the total travel time extension of a train regarding the original timetable | ||
maximal lateness of arrival of train p to station i | travel distance extension of the train regarding the original timetable used to limit travel time | ||
maximal lateness of departure of train p from station i | limit of the travel time extension relating to the distance | ||
minimal dwell time of train p at station i |
Symbol | Description | Symbol | Description |
---|---|---|---|
set of all closures | duration of closure n | ||
C | number of all closures | earliest start time of closure n | |
number of obligatory closures | latest start time of closure n | ||
matrix of closure parameters | binary matrix of precedence constraints among closures | ||
element of representing a tuple describing closure n | element of representing a precedence constraint between closures n and m | ||
matrix of tracks blocked by closure n | time horizon of the investigated problem | ||
element of representing the existence of a blockade of track k between stations i and j to be performed by closure n |
Symbol | Description | Symbol | Description |
---|---|---|---|
binary matrix of closure planning | element of representing time shift of train p arrival to station i | ||
element of indicating the status of closure n | matrix with time shifts of train departures from stations | ||
matrix with time shifts of closure start moments | matrix representing the plan of track closures | ||
element of representing the start time shift of closure n | element of S representing plan for closure n | ||
matrix describing routes of all trains | tracks to be closed during closure n | ||
matrix describing the route of train p being the element of | vector with timetable of trains | ||
element of describing the connection between stations i and j is used in the route of train p | element of given by a tuple representing the timetable of train p | ||
matrix with time shifts of train arrivals to stations | binary matrix describing inclusion of trains into timetable | ||
element of representing time shift of train p departure from station i | element of indicating the possible inclusion of train p into timetable |
Notation Used in Algorithm 1 | |||
Symbol | Description | Symbol | Description |
tracks to be closed during closure n | set of obligatory closures | ||
actual completion time of closure n | set of facultative closures | ||
sequence of obligatory closures | set of selected closures to be passed to Algorithm 2 | ||
Notation Used in Algorithm 2 | |||
Symbol | Description | Symbol | Description |
selected train runs to be passed to Algorithm 3 | variable indicating the run of train p by track k between given stations | ||
parameter of Algorithm 2 representing the limit of time shifts of closures or trains | conflict index for the train run p | ||
Notation Used in Algorithm 3 | |||
Symbol | Description | Symbol | Description |
temporary closure plan | set of stations of the decomposed sub-network n | ||
temporary train timetable | number of sub-networks in the decomposition | ||
set of track assignments to groups used for the decomposition | string of stations representing the path of train p | ||
set of tuples describing each arc that exists in network | set of closures in the decomposed sub-network n | ||
graph representing the decomposed railway sub-network n. | set of trains in decomposed sub-network n | ||
matrix of tracks (matrix extended by virtual tracks) for the decomposed sub-network n | q | train run marked for rerouting | |
Notation Used in Algorithm 4 | |||
Symbol | Description | Symbol | Description |
series of elements indicating tracks that have trains or track closures and their order | set of closures on the given track | ||
element of indicating if tracks have trains or track closures at position m | set of trains going through track | ||
matrix representing the order of track usage by either trains or closures | sub-set of , | ||
element of | total time shift for trains limited to a single track at a time | ||
number of trains and closures on track k connecting stations i and j | set of trains on tracks adjacent to station i. | ||
matrix representing the order of trains entering station i | set of tracks adjacent to station i. | ||
element of indicating number of train entering station i in the order m | total time shift of trains for station i. | ||
number of trains entering station i |
Case 1 | Case 2 | Case 3 | Case 4 | |||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Fail | Fail | Fail | Fail | |||||||||
5 | 4.6 | 4.6 | 0 | 13.6 | 13.6 | 0 | 597 | 601.8 | 0 | 420.1 | 420.1 | 0 |
6 | 21.7 | 21.7 | 0 | 45.4 | 45.4 | 0 | 380.22 | 380.22 | 1 | 562.78 | 570.78 | 1 |
7 | 22.9 | 22.9 | 0 | 39.6 | 39.6 | 0 | 541 | 541 | 2 | 702.67 | 747.56 | 1 |
8 | 18.2 | 18.2 | 0 | 101.2 | 101.2 | 0 | 320.44 | 320.44 | 1 | 698.4 | 699.7 | 0 |
9 | 59.2 | 59.2 | 0 | 60.1 | 60.1 | 0 | 924.1 | 924.2 | 0 | 565.71 | 569.57 | 3 |
10 | 34.3 | 34.3 | 0 | 64.5 | 64.5 | 0 | 1360.22 | 1361.33 | 1 | 1158.8 | 1162.8 | 0 |
Case 1 | Case 2 | Case 3 | Case 4 | |||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Fail | Fail | Fail | Fail | |||||||||
5 | 0.02 | 0.09 | 0 | 0.02 | 0.07 | 0 | 0.13 | 0.1 | 0 | 0.09 | 0.09 | 0 |
6 | 0.04 | 0.13 | 0 | 0.05 | 0.11 | 0 | 0.35 | 0.13 | 1 | 0.37 | 0.14 | 1 |
7 | 0.11 | 0.19 | 0 | 0.1 | 0.17 | 0 | 1.31 | 0.55 | 2 | 1.85 | 0.21 | 1 |
8 | 0.45 | 0.28 | 0 | 0.49 | 0.23 | 0 | 6.44 | 0.41 | 1 | 7.16 | 0.31 | 0 |
9 | 1.54 | 0.38 | 0 | 0.87 | 0.32 | 0 | 26.6 | 0.39 | 0 | 60.85 | 0.4 | 3 |
10 | 2.36 | 0.5 | 0 | 1.36 | 0.8 | 0 | 193.69 | 0.52 | 1 | 168.75 | 0.52 | 0 |
2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
3 | 1 | 1 | 1 | 1 | 1 | 1.09 | 1 | 1 | 1 | 1 | 1 | 1 |
4 | 1.26 | 1 | 1.64 | 1.29 | 1.02 | 1.79 | 1.32 | 1 | 1.82 | 1.27 | 1 | 1.73 |
10 | 1.6 | 1.2 | 2.65 | 1.99 | 1.47 | 2.84 | 2.23 | 1.68 | 2.98 | 2.17 | 1.4 | 2.75 |
20 | 2.17 | 1.35 | 3.14 | 2.43 | 1.58 | 3.24 | 2.52 | 1.67 | 3.33 | 2.66 | 1.62 | 3.34 |
2 | 1 | 1 | 1 | 1 | 1 | 1 | 1.04 | 1 | 1.15 | 1 | 1 | 1.04 |
3 | 1 | 1 | 1 | 1 | 1 | 1 | 1.14 | 1 | 1.33 | 1.01 | 1 | 1.14 |
4 | 1.38 | 1 | 2 | 1.22 | 1 | 1.65 | 1.34 | 1.15 | 1.49 | 1.39 | 1.29 | 1.72 |
10 | 2.87 | 2.17 | 3.32 | 2.11 | 1.12 | 2.51 | 2.68 | 2 | 2.96 | 2.67 | 2.57 | 2.84 |
20 | 2.87 | 2 | 3.51 | 2.8 | 1.56 | 3.36 | 3.19 | 2.52 | 3.82 | 3.32 | 3.3 | 3.36 |
2 | 15 | 14 | 16 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 |
3 | 14 | 13 | 15 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 |
4 | 13 | 13 | 14 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 |
10 | 13 | 13 | 14 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 |
20 | 13 | 13 | 14 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 |
2 | 32 | 30 | 35 | 65 | 60 | 67 | 339 | 275 | 421 | 1308 | 1193 | 1419 |
3 | 31 | 29 | 36 | 64 | 61 | 67 | 316 | 251 | 415 | 1257 | 1201 | 1341 |
4 | 31 | 29 | 34 | 53 | 59 | 63 | 300 | 234 | 401 | 1206 | 1119 | 1250 |
10 | 31 | 28 | 33 | 50 | 46 | 61 | 267 | 210 | 326 | 1216 | 987 | 1233 |
20 | 29 | 28 | 31 | 48 | 39 | 58 | 242 | 107 | 326 | 301 | 151 | 351 |
10 | 1 | 1 | 1 | 1 | 1 | 1 | 1.26 | 1 | 1.64 | 1.6 | 1.2 | 2.65 | 2.17 | 1.35 | 3.14 |
11 | 1 | 1 | 1 | 1 | 1 | 1.09 | 1.29 | 1.02 | 1.79 | 1.99 | 1.47 | 2.84 | 2.43 | 1.58 | 3.24 |
12 | 1 | 1 | 1 | 1 | 1 | 1 | 1.32 | 1 | 1.82 | 2.23 | 1.68 | 2.98 | 2.52 | 1.67 | 3.33 |
13 | 1 | 1 | 1 | 1 | 1 | 1 | 1.27 | 1 | 1.73 | 2.17 | 1.4 | 2.75 | 2.66 | 1.62 | 3.34 |
14 | 1 | 1 | 1 | 1 | 1 | 1 | 1.38 | 1 | 2 | 2.87 | 2.17 | 3.32 | 2.87 | 2 | 3.51 |
15 | 1 | 1 | 1 | 1 | 1 | 1 | 1.22 | 1 | 1.65 | 2.11 | 1.12 | 2.51 | 2.8 | 1.56 | 3.36 |
20 | 1.04 | 1 | 1.15 | 1.14 | 1 | 1.33 | 1.34 | 1.15 | 1.49 | 2.68 | 2 | 2.96 | 3.19 | 2.52 | 3.82 |
30 | 1 | 1 | 1.04 | 1.01 | 1 | 1.14 | 1.39 | 1.29 | 1.72 | 2.67 | 2.57 | 2.84 | 3.32 | 3.3 | 3.36 |
10 | 15 | 14 | 16 | 14 | 13 | 15 | 13 | 13 | 14 | 13 | 13 | 14 | 13 | 13 | 14 |
11 | 14 | 14 | 14 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 |
12 | 14 | 14 | 14 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 |
13 | 14 | 14 | 14 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 | 13 |
14 | 32 | 30 | 35 | 31 | 29 | 36 | 31 | 29 | 34 | 31 | 28 | 33 | 29 | 28 | 31 |
15 | 65 | 60 | 67 | 64 | 61 | 67 | 53 | 59 | 63 | 50 | 46 | 61 | 48 | 39 | 58 |
20 | 339 | 275 | 421 | 316 | 251 | 415 | 300 | 234 | 401 | 267 | 210 | 326 | 242 | 107 | 326 |
30 | 1308 | 1193 | 1419 | 1257 | 1201 | 1341 | 1206 | 1119 | 1250 | 1216 | 987 | 1233 | 301 | 151 | 351 |
2 | 1 | 1 | 1 |
3 | 1 | 1 | 1 |
4 | 1.64 | 1 | 1.26 |
10 | 2.65 | 1.2 | 1.6 |
20 | 3.14 | 1.35 | 2.17 |
10 | 1.64 | 1 | 1.26 |
20 | 1.49 | 1.15 | 1.34 |
30 | 1.72 | 1.29 | 1.38 |
2 | 1 | 15 | 1.05 | 339 | 1 | 1308 | 1.02 | 554 |
3 | 1 | 14 | 1.15 | 315 | 1.01 | 1257 | 1.05 | 529 |
4 | 1.27 | 13 | 1.34 | 300 | 1.4 | 1206 | 1.34 | 506 |
10 | 1.6 | 13 | 1.69 | 267 | 2.68 | 1216 | 1.99 | 499 |
20 | 2.17 | 13 | 2.2 | 242 | 3.33 | 301 | 2.56 | 202 |
2 | 239 | 13 | 2052 | 264 | 11231 | 1292 |
4 | 474 | 14 | 4123 | 274 | 21452 | 1290 |
6 | 931 | 14 | 7905 | 271 | 43041 | 1301 |
10 | 10 | 10 | 10 | 10 | 10 | 10 |
20 | 10 | 10 | 10 | 10 | 10 | 10 |
30 | 10 | 10 | 10 | 10 | 8 | 8 |
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. |
© 2021 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).
Share and Cite
Filcek, G.; Gąsior, D.; Hojda, M.; Józefczyk, J. An Algorithm for Rescheduling of Trains under Planned Track Closures. Appl. Sci. 2021, 11, 2334. https://doi.org/10.3390/app11052334
Filcek G, Gąsior D, Hojda M, Józefczyk J. An Algorithm for Rescheduling of Trains under Planned Track Closures. Applied Sciences. 2021; 11(5):2334. https://doi.org/10.3390/app11052334
Chicago/Turabian StyleFilcek, Grzegorz, Dariusz Gąsior, Maciej Hojda, and Jerzy Józefczyk. 2021. "An Algorithm for Rescheduling of Trains under Planned Track Closures" Applied Sciences 11, no. 5: 2334. https://doi.org/10.3390/app11052334
APA StyleFilcek, G., Gąsior, D., Hojda, M., & Józefczyk, J. (2021). An Algorithm for Rescheduling of Trains under Planned Track Closures. Applied Sciences, 11(5), 2334. https://doi.org/10.3390/app11052334