| 1. |
- Joborn, Martin, et al.
(författare)
-
Description of a decision support tool aimed at advanced Real Time Network Management and requirements for a demonstrator
- 2020
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- In this report we outline a conceptual demonstrator for advanced real time network management for freight rail traffic. The focus is on the coordination between traffic control, train drivers and yard management, three essential parts in the real time management of a rail freight network. The intention is that the demonstrator can support multiple purposes, such as education and training, demonstrating research advancements, and enabling feedback between practitioners, system developers and researchers. The proposed demonstrator has a focus on the interaction between different systems and between humans using these systems, but also on the rail freight system perspective by the inclusion of the connection between the line and the yard. We present a generic architecture and propose existing components that could be combined to such a demonstrator. Thus, even though the demonstrator may seem complex and visionary, the existence of these components makes the realization of the demonstrator realistic. The development roadmap for the demonstrator proposes both a step-wise implementation plan of the complete demonstrator, as well as several partial packages that provide useful sub-demonstrators by themselves.The appendices of the report include contributions to the continued development of two of the components that are part of the demonstrator. Firstly, in order to also better understand the type of situations that yard managers need to handle in operations and what implications these have on the traffic on the line, a Swedish case study has been conducted and the results are presented in Appendix A. More specifically, the case study analyses the factors that influence the departure time deviation for freight trains and how these can be used for predicting the actual departure time. These predictions can be used in a decision support system for yard planning at larger marshalling yards. A conclusion is that no single factor can fully explain the departure time deviation, but many different factors contribute to it, like destination, time of day, train load, number of wagons on the yard, connection time for wagons, and connection time for locomotives.Secondly, to support the traffic controllers and dispatchers with an advanced decision support tool for deviation handling, a selection of different functionalities and algorithms may be required. In Appendix B, two different approaches for disturbance management are presented. Approach 1 (ALG1) is a heuristic, parallel algorithm, while the second approach (ALG2) is an exact algorithm based on state-of-the-art commercial optimization software. In order to classify and evaluate alternative algorithms for train re-scheduling and disturbance management, an assessment framework is also proposed in Appendix B. Based on this framework, the overall strengths and shortcomings of the two mentioned train rescheduling algorithms are assessed while applied on a set of 30 simulated disturbance scenarios of various complexity. The results show that typically, ALG2 obtained good rescheduling solutions for all 30 disturbances, but compared to ALG1, ALG2 is slow in obtaining solutions.ALG1 is good at quickly finding solutions with less passenger delays while it is less effective when it is used to solve disturbances associated with an infrastructure failure. The strength of ALG2 is its ability to reschedule the traffic during infrastructure failures. A detailed presentation of the evaluation is found in Appendix B.
|
|
| 2. |
- Josyula, Sai Prashanth, 1992-, et al.
(författare)
-
An evaluation framework and algorithms for train rescheduling
- 2020
-
Ingår i: Algorithms. - : MDPI AG. - 1999-4893. ; 13:12
-
Tidskriftsartikel (refereegranskat)abstract
- In railway traffic systems, whenever disturbances occur, it is important to effectively reschedule trains while optimizing the goals of various stakeholders. Algorithms can provide significant benefits to support the traffic controllers in train rescheduling, if well integrated into the overall traffic management process. In the railway research literature, many algorithms are proposed to tackle different versions of the train rescheduling problem. However, limited research has been performed to assess the capabilities and performance of alternative approaches, with the purpose of identifying their main strengths and weaknesses. Evaluation of train rescheduling algorithms enables practitioners and decision support systems to select a suitable algorithm based on the properties of the type of disturbance scenario in focus. It also guides researchers and algorithm designers in improving the algorithms. In this paper, we (1) propose an evaluation framework for train rescheduling algorithms, (2) present two train rescheduling algorithms: a heuristic and a MILP-based exact algorithm, and (3) conduct an experiment to compare the two multi-objective algorithms using the proposed framework (a proof-of-concept). It is found that the heuristic algorithm is suitable for solving simpler disturbance scenarios since it is quick in producing decent solutions. For complex disturbances wherein multiple trains experience a primary delay due to an infrastructure failure, the exact algorithm is found to be more appropriate. © 2020 by the authors. Licensee MDPI, Basel, Switzerland.
|
|
| 3. |
- Josyula, Sai Prashanth, 1992-
(författare)
-
Parallel algorithms for solving the train timetable rescheduling problem
- 2021
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In railways, it is essential to achieve high train punctuality. Thus, whenever disturbances occur, it is important to reschedule the trains effectively. This task is typically handled manually by traffic controllers in real-time. This thesis presents efficient computer algorithms for assisting traffic controllers in effectively rescheduling a train timetable during disturbances.The train timetable rescheduling problem is typically hard to solve as the solutions of interest, spread across a vast solution space, need to be searched quickly. Two main solution approaches involve using (i) exact algorithms, which typically search the entire solution space, and (ii) heuristic algorithms, which try to search for a good-enough solution quickly. Although research on competitive algorithms is prevalent, limited research exists on exploring the benefits and challenges of using parallel computing to tackle the problem.The primary objectives of this thesis are: (i) to model the train timetable rescheduling problem's search tree to be well-suited for parallel computing, (ii) to devise parallel heuristic search algorithms that can quickly and effectively solve the problem for one or many rescheduling objectives, (iii) to investigate the potential and limitations of parallel computing in the context of the problem, (iv) to investigate the comparison and evaluation of alternative solution approaches to analyze their strengths and limitations.In this thesis, we model the problem's search tree as a binary tree where the edges represent alternative rescheduling decisions and leaf nodes represent feasible timetables. We solve the problem by searching the tree using a parallel strategy that combines a depth-first search with simultaneous breadth-wise tree exploration. We evaluate our parallel algorithms for various disturbances on a Swedish railway network through experiments.The results of our research show that a parallel depth-first search algorithm can quickly search the devised search tree for solutions. With multiple rescheduling objectives, the parallel search algorithm obtained better solutions and showed higher speedups. Additional problem constraints often improved the search process by making the parallel algorithm reach the solutions faster. The results also show the potential and challenges of using graphics processing units for detecting conflicts in the timetable during the search. In conclusion, this thesis shows that parallel train timetable rescheduling algorithms can improve the search speed and the quality of the solution(s) obtained in real-time within the computational time limit.
|
|
| 4. |
- Josyula, Sai Prashanth, 1992-, et al.
(författare)
-
Parallel computing for multi-objective train rescheduling
- 2021
-
Ingår i: IEEE Transactions on Emerging Topics in Computing. - : IEEE Computer Society. - 2168-6750. ; 9:4, s. 1683-1696
-
Tidskriftsartikel (refereegranskat)abstract
- In railway traffic systems, it is essential to achieve a high punctuality to satisfy the goals of the involved stakeholders. Thus, whenever disturbances occur, it is important to effectively reschedule trains while considering the perspectives of various stakeholders. This typically involves solving a multi-objective train rescheduling problem, which is much more complex than its single-objective counterpart. Solving such a problem in real-time for practically relevant problem sizes is computationally challenging. The reason is that the rescheduling solution(s) of interest are dispersed across a large search tree. The tree needs to be navigated fast while pruning off branches leading to undesirable solutions and exploring branches leading to potentially desirable solutions. The use of parallel computing enables such a fast navigation of the tree. This paper presents a heuristic parallel algorithm to solve the multi-objective train rescheduling problem. The parallel algorithm combines a depth-first search with simultaneous breadth-wise tree exploration while searching the tree for solutions. An existing parallel algorithm for single-objective train rescheduling has been redesigned, primarily, by (i) pruning based on multiple metrics, and (ii) maintaining a set of upper bounds. The redesign improved the quality of the obtained rescheduling solutions and showed better speedups for several disturbance scenarios. CCBY
|
|
| 5. |
- Yap, Menno, et al.
(författare)
-
Quantification and control of disruption propagation in multi-level public transport networks
- 2022
-
Ingår i: International Journal of Transportation Science and Technology. - : Elsevier. - 2046-0430 .- 2046-0449. ; 11:1, s. 83-106
-
Tidskriftsartikel (refereegranskat)abstract
- Due to the multi-level nature of public transport networks, disruption impacts may spill-over beyond the primary effects occurring at the disrupted network level. During a public transport disruption, it is therefore important to quantify and control the disruption impacts for the total public transport network, instead of delimiting the analysis of their impacts to the public transport network level where this particular disruption occurs. We propose a modelling framework to quantify disruption impact propagation from the train network to the urban tram or bus network. This framework combines an optimisation-based train rescheduling model and a simulation-based dynamic public transport assignment model in an iterative procedure. The iterative process allows devising train schedules that take into account their impact on passenger flow re-distribution and related delays. Our study results in a framework which can improve public transport contingency plans on a strategic and tactical level in response to short- to medium-lasting public transport disruptions, by incorporating how the passenger impact of a train network disruption propagates to the urban network level. Furthermore, this framework allows for a more complete quantification of disruption costs, including their spilled-over impacts, retrospectively. We illustrate the successful implementation of our framework to a multi-level case study network in the Netherlands. © 2021 Tongji University and Tongji University Press
|
|
