Change search
Link to record
Permanent link

Direct link
Törnquist Krasemann, JohannaORCID iD iconorcid.org/0000-0002-8373-8398
Alternative names
Publications (10 of 35) Show all publications
Yap, M., Cats, O., Törnquist Krasemann, J., van Oort, N. & Hoogendoorn, S. (2022). Quantification and control of disruption propagation in multi-level public transport networks. International Journal of Transportation Science and Technology, 11(1), 83-106
Open this publication in new window or tab >>Quantification and control of disruption propagation in multi-level public transport networks
Show others...
2022 (English)In: International Journal of Transportation Science and Technology, ISSN 2046-0430, Vol. 11, no 1, p. 83-106Article in journal (Refereed) Published
Abstract [en]

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

Place, publisher, year, edition, pages
Elsevier, 2022
Keywords
Dynamic assignment, Optimisation, Public transport, Train rescheduling, Vulnerability analysis
National Category
Transport Systems and Logistics
Identifiers
urn:nbn:se:bth-21418 (URN)10.1016/j.ijtst.2021.02.002 (DOI)001045843700001 ()2-s2.0-85105259516 (Scopus ID)
Funder
Swedish Research Council Formas, 942 - 2015-2034
Note

open access

Available from: 2021-05-21 Created: 2021-05-21 Last updated: 2024-01-01Bibliographically approved
Josyula, S. P., Törnquist Krasemann, J. & Lundberg, L. (2021). Parallel computing for multi-objective train rescheduling. IEEE Transactions on Emerging Topics in Computing, 9(4), 1683-1696
Open this publication in new window or tab >>Parallel computing for multi-objective train rescheduling
2021 (English)In: IEEE Transactions on Emerging Topics in Computing, ISSN 2168-6750, Vol. 9, no 4, p. 1683-1696Article in journal (Refereed) Published
Abstract [en]

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

Place, publisher, year, edition, pages
IEEE Computer Society, 2021
Keywords
decision support, parallel algorithms, Transportation, tree search strategies, Forestry, Depth first search, Multi objective, Problem size, Railway traffic systems, Search trees, Single objective, Train rescheduling, Upper Bound, Trees (mathematics)
National Category
Computer Sciences
Identifiers
urn:nbn:se:bth-20644 (URN)10.1109/TETC.2020.3030984 (DOI)000725807100007 ()2-s2.0-85092933988 (Scopus ID)
Funder
Swedish Research Council Formas
Note

open access

Funded by FR8Rail II project 826206

Available from: 2020-11-03 Created: 2020-11-03 Last updated: 2021-12-16Bibliographically approved
Josyula, S. P., Törnquist Krasemann, J. & Lundberg, L. (2020). An evaluation framework and algorithms for train rescheduling. Algorithms, 13(12), Article ID 332.
Open this publication in new window or tab >>An evaluation framework and algorithms for train rescheduling
2020 (English)In: Algorithms, E-ISSN 1999-4893, Vol. 13, no 12, article id 332Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
MDPI AG, 2020
Keywords
Algorithm evaluation, Decision support systems, Multi-objective optimization, Parallel algorithms, Train rescheduling, Integer programming, Railroads, Traffic control, Complex disturbance, Evaluation framework, Infrastructure failures, Multi objective algorithm, Railway traffic systems, Traffic controllers, Train rescheduling algorithms, Heuristic algorithms
National Category
Transport Systems and Logistics Computer Sciences
Identifiers
urn:nbn:se:bth-20887 (URN)10.3390/a13120332 (DOI)000601873200001 ()2-s2.0-85098057885 (Scopus ID)
Funder
Swedish Transport Administration, 108023,826206
Note

open access

Available from: 2021-01-06 Created: 2021-01-06 Last updated: 2023-03-29Bibliographically approved
Josyula, S. P., Törnquist Krasemann, J. & Lundberg, L. (2019). Exploring the Potential of GPU Computing in Train Rescheduling. In: Proceedings of the 8th International Conference on Railway Operations Modelling and Analysis, Norrköping, 2019.: . Paper presented at 8th International Conference on Railway Operations Modelling and Analysis.
Open this publication in new window or tab >>Exploring the Potential of GPU Computing in Train Rescheduling
2019 (English)In: Proceedings of the 8th International Conference on Railway Operations Modelling and Analysis, Norrköping, 2019., 2019Conference paper, Published paper (Refereed)
National Category
Computer Sciences
Identifiers
urn:nbn:se:bth-18510 (URN)
Conference
8th International Conference on Railway Operations Modelling and Analysis
Note

open access

Available from: 2019-08-02 Created: 2019-08-02 Last updated: 2021-10-07Bibliographically approved
Törnquist Krasemann, J. & Rydergren, C. (2019). Passagerar-fokuserad hantering av störningar i den regionala tågtrafiken: En sammanställning av arbete och resultat från den svenska delen av TRANSFORM-projektet. Karlskrona
Open this publication in new window or tab >>Passagerar-fokuserad hantering av störningar i den regionala tågtrafiken: En sammanställning av arbete och resultat från den svenska delen av TRANSFORM-projektet
2019 (Swedish)Report (Other academic)
Abstract [sv]

Bakgrund och syfte

Informationstjänster för kollektivtrafikresenärer blir allt bättre, men vid störningar är det fortfarande mycket svårt som resenär att få tillräcklig och aktuell information om hur resan kommer att kunna fullföljas. För planerare och trafikledning är det också en enorm utmaning i att skapa robusta planer som medför flexibilitet i driften, att övervaka trafikläget och att styra systemet på ett proaktivt sätt som balanserar interna prioriteringar med resenärernas. Inom projektet har vi därför studerat två alternativa principer och metoder för att omplanera tågtrafiken vid störningar – där den ena är mer resenärsfokuserad och den andra mer trafiksystem-fokuserad.

Metodik

Den förstnämnda metoden inkluderar i omplaneringen av tågen vid störningar även regionala bussar. Metoden beaktar resandeutbyten och alternativa resvägar för att, om möjligt, minska resenärers försening genom att samordna tåg- och/eller bussanslutningar. Här används en matematisk modell som utvecklats i projektet och optimeringsproblemet löses med hjälp av kommersiell mjukvara, Gurobi. Vi använder även anonymiserad, filtrerad, resekortsdata för att modellera passagerarflöden och relevanta anslutningar. Den andra metoden omplanerar tågtrafiken utan hänsyn till annan kollektivtrafik och möjliggör en viktning (dvs. prioritering) av tåg med ett större antal avstigande resenärer. Här används en parallelliserad algoritm som på ett effektivt sätt ska kunna planera om tågen vid störningar baserat på ett antal kvalitetsindikatorer. Båda metoderna har tillämpats i datorbaserade experiment för störningarsscenarier på Blekinge Kustbana och anslutande banor.

Resultat och slutsatser

Resultaten från projektet visar på vikten av att utforma beräkningsstöd för tågtrafikledning som inkluderar flera olika målkriterier och kvalitetsindikatorer vid omplaneringen av tåg vid störningar. Vilka kriterier och indikatorer som är mest relevanta att fokusera på i den operativa driften är en bedömning som bör göras dels utifrån ett användarperspektiv, dels baserat på gällande lagstiftning inklusive aktuella operativa regler definierade i järnvägsnätsbeskrivningen för innevarande år.

 

Preliminära resultaten från studierna visar även på möjligheterna med att samordna den regionala tåg- och busstrafiken i större utsträckning än vad som är praktiskt möjligt idag. Tillgången till data ökar samt olika mer eller mindre avancerade digitala hjälpmedel för resenärer såväl som för trafikledning föreslås och diskuteras av branschen och inom forskarsamhället, men hur man uppnår en effektiv hantering av störningar och säkerställer ändamålsenlig trafikinformation till resenärer är först och främst en organisatorisk fråga, snarare än en teknisk utmaning.

Place, publisher, year, edition, pages
Karlskrona: , 2019. p. 29
Series
TRANSFORM project deliverables
Keywords
Kollektivtrafik, Optimering, Järnvägstrafik, Algoritmer, Operationsanalys
National Category
Computer Sciences
Identifiers
urn:nbn:se:bth-19008 (URN)
Funder
Swedish Research Council Formas, 942 - 2015-2034
Note

Finansierat via utlysningen ”the ERA-NET Smart Cities and Communities (ENSCC)” av JPI Urban Europe.

Available from: 2019-12-12 Created: 2019-12-12 Last updated: 2020-10-05Bibliographically approved
Gholami, O. & Törnquist Krasemann, J. (2018). A Heuristic Approach to Solving the Train Traffic Re-Scheduling Problem in Real Time. Algorithms, 11(4), 1-18, Article ID 55.
Open this publication in new window or tab >>A Heuristic Approach to Solving the Train Traffic Re-Scheduling Problem in Real Time
2018 (English)In: Algorithms, E-ISSN 1999-4893, Vol. 11, no 4, p. 1-18, article id 55Article in journal (Refereed) Published
Abstract [en]

Effectiveness in managing disturbances and disruptions in railway traffic networks, when they inevitably do occur, is a significant challenge, both from a practical and theoretical perspective. In this paper, we propose a heuristic approach for solving the real-time train traffic re-scheduling problem. This problem is here interpreted as a blocking job-shop scheduling problem, and a hybrid of the mixed graph and alternative graph is used for modelling the infrastructure and traffic dynamics on a mesoscopic level. A heuristic algorithm is developed and applied to resolve the conflicts by re-timing, re-ordering, and locally re-routing the trains. A part of the Southern Swedish railway network from Karlskrona centre to Malmö city is considered for an experimental performance assessment of the approach. The network consists of 290 block sections, and for a one-hour time horizon with around 80 active trains, the algorithm generates a solution in less than ten seconds. A benchmark with the corresponding mixed-integer program formulation, solved by commercial state-of-the-art solver Gurobi, is also conducted to assess the optimality of the generated solutions.

Place, publisher, year, edition, pages
MDPI, 2018
Keywords
railway traffic; disturbance management; real-time re-scheduling; job-shop scheduling; optimization; alternative graph
National Category
Transport Systems and Logistics
Identifiers
urn:nbn:se:bth-16113 (URN)10.3390/a11040055 (DOI)000435177500022 ()
Projects
FloatBLIXTEN
Funder
Swedish Transport Administration
Note

open access

Available from: 2018-04-24 Created: 2018-04-24 Last updated: 2023-03-29Bibliographically approved
Josyula, S. P., Törnquist Krasemann, J. & Lundberg, L. (2018). A parallel algorithm for train rescheduling. Transportation Research Part C: Emerging Technologies, 95, 545-569
Open this publication in new window or tab >>A parallel algorithm for train rescheduling
2018 (English)In: Transportation Research Part C: Emerging Technologies, ISSN 0968-090X, E-ISSN 1879-2359, Vol. 95, p. 545-569Article in journal (Refereed) Published
Abstract [en]

One of the crucial factors in achieving a high punctuality in railway traffic systems, is the ability to effectively reschedule the trains when disturbances occur. The railway traffic rescheduling problem is a complex task to solve both from a practical and a computational perspective. Problems of practically relevant sizes have typically a very large search space, making them time-consuming to solve even for state-of-the-art optimization solvers. Though competitive algorithmic approaches are a widespread topic of research, not much research has been done to explore the opportunities and challenges in parallelizing them. This paper presents a parallel algorithm to efficiently solve the real-time railway rescheduling problem on a multi-core parallel architecture. We devised (1) an effective way to represent the solution space as a binary tree and (2) a novel sequential heuristic algorithm based on a depth-first search (DFS) strategy that quickly traverses the tree. Based on that, we designed a parallel algorithm for a multi-core architecture, which proved to be 10.5 times faster than the sequential algorithm even when run on a single processing core. When executed on a parallel machine with 8 cores, the speed further increased by a factor of 4.68 and every disturbance scenario in the considered case study was solved within 6 s. We conclude that for the problem under consideration, though a sequential DFS approach is fast in several disturbance scenarios, it is notably slower in many other disturbance scenarios. The parallel DFS approach that combines a DFS with simultaneous breadth-wise tree exploration, while being much faster on an average, is also consistently fast across all scenarios.

Place, publisher, year, edition, pages
Elsevier, 2018
Keywords
Railway traffic; Rescheduling; Parallel depth-first search; Optimization
National Category
Computer Sciences
Identifiers
urn:nbn:se:bth-16868 (URN)10.1016/j.trc.2018.07.003 (DOI)000447112500032 ()
Funder
Swedish Research Council Formas
Note

open access

Available from: 2018-08-15 Created: 2018-08-15 Last updated: 2022-04-05Bibliographically approved
Lamorgese, L., Mannino, C., Pacciarelli, D. & Törnquist Krasemann, J. (2018). Train Dispatching (268ed.). In: Borndörfer, R. (et al.) (Ed.), Handbook of Optimization in the Railway Industry: (pp. 265-283). Springer New York LLC
Open this publication in new window or tab >>Train Dispatching
2018 (English)In: Handbook of Optimization in the Railway Industry / [ed] Borndörfer, R. (et al.), Springer New York LLC , 2018, 268, p. 265-283Chapter in book (Refereed)
Abstract [en]

Train rescheduling problems have received significant attention in the operations research community during the past 20–30 years. These are complex problems with many aspects and constraints to consider. This chapter defines the problem and summarizes the variety of model types and solution approaches developed over the years, in order to address and solve the train dispatching problem from the infrastructure manager perspective. Despite all the research efforts, it is, however, only very recently that the railway industry has made significant attempts to explore the large potential in using optimization-based decision-support to facilitate railway traffic disturbance management. This chapter reviews state-of-practice and provides a discussion about the observed slow progress in the application of optimization-based methods in practice. A few successful implementations have been identified, but their performance as well as the lessons learned from the development and implementation of those system are unfortunately only partly available to the research community, or potential industry users. © 2018, Springer International Publishing AG.

Place, publisher, year, edition, pages
Springer New York LLC, 2018 Edition: 268
Series
International Series in Operations Research and Management Science, ISSN 0884-8289 ; 268
National Category
Computer Sciences
Identifiers
urn:nbn:se:bth-16026 (URN)10.1007/978-3-319-72153-8_12 (DOI)2-s2.0-85043258670 (Scopus ID)978-3-319-72153-8 (ISBN)
Available from: 2018-03-26 Created: 2018-03-26 Last updated: 2021-12-16Bibliographically approved
Khoshniyat, F. & Törnquist Krasemann, J. (2017). An Optimization Approach for On-Demand Railway Slot Allocation. In: : . Paper presented at 7th International Conference on Railway Operations Modelling and Analysis-RailLille2017, April 4-7, 2017, Lille, France.
Open this publication in new window or tab >>An Optimization Approach for On-Demand Railway Slot Allocation
2017 (English)Conference paper, Published paper (Refereed)
Abstract [en]

This paper addresses a significant challenge experienced by infrastructure managers concerninghandling and scheduling slot requests for additional trains, or urgent track maintenance,after the master timetable has been finalized. In congested railway networks, wherepassenger trains share the tracks with freight trains and where the freight train operatorscannot fully predict the actual need for access to train slots long in advance, there is aneed for a flexible and effective timetabling revision process. Since the re-scheduling oftraffic and maintenance is a demanding task, the benefits of using computational schedulingsupport is evident. From the perspective of an infrastructure manager, we propose andexperimentally evaluate an optimization-based approach for assessment and scheduling ofadditional slot requests. When inserting several trains, the relations between time and routeoverlap as well as direction of trains, and the required computation time are investigated.The optimization-based approach relies on a Mixed Integer Linear Programming formulation.In this model, the explicit capacity restrictions of line segments and station tracks,including track and platform length, are considered. This model also permits bidirectionaltraffic on all lines where relevant. The experimental results show that optimal solutions canbe retrieved quickly in many scenarios, while for certain scenarios the proposed approachis too time-consuming. The required computation time is very dependent on the propertiesof the inserted train and maintenance slots, respectively.

Keywords
Timetabling, Scheduling, Slot Allocation, Robustness, Railway Traffic
National Category
Transport Systems and Logistics
Identifiers
urn:nbn:se:bth-20957 (URN)
Conference
7th International Conference on Railway Operations Modelling and Analysis-RailLille2017, April 4-7, 2017, Lille, France
Funder
Swedish Transport Administration
Note

open access

Available from: 2021-01-22 Created: 2021-01-22 Last updated: 2022-05-25Bibliographically approved
Khoshniyat, F. & Törnquist Krasemann, J. (2017). Analysis of strengths & weaknesses of a MILP model for revising railway traffic timetables. In: OpenAccess Series in Informatics: . Paper presented at 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, (ATMOS), Vienna. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 59, Article ID 131022.
Open this publication in new window or tab >>Analysis of strengths & weaknesses of a MILP model for revising railway traffic timetables
2017 (English)In: OpenAccess Series in Informatics, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2017, Vol. 59, article id 131022Conference paper, Published paper (Refereed)
Abstract [en]

A railway timetable is typically planned one year in advance, but may be revised several times prior to the time of operation in order to accommodate on-demand slot requests for inserting additional trains and network maintenance. Revising timetables is a computationally demanding task, given the many dependencies and details to consider. In this paper, we focus on the potential of using optimization-based scheduling approach for revising train timetables during short term planning, from one week to few hours before the actual operation. The approach relies on a MILP (Mixed Integer Linear Program) model which is solved by using the commercial solver Gurobi. In a previous experimental study, the MILP approach was used to revise a significant part of the annual timetable for a sub-network in Southern Sweden to insert additional trains and allocate time slots for urgent maintenance. The results showed that the proposed MILP approach in many cases generates feasible, good solutions rather fast. However, proving optimality was in several cases time-consuming, especially for larger problems. Thus, there is a need to investigate and develop strategies to improve the computational performance. In this paper, we present results from a study, where a number of valid inequalities has been selected and applied to the MILP model with the aim to reduce the computation time. The experimental evaluation of the selected valid inequalities showed that although they can provide a slight improvement with respect to computation time, they are also weakening the LP relaxation of the model.

Place, publisher, year, edition, pages
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017
Keywords
Boosting methods, Railway, Short term planning, Timetable, Valid inequalities, Railroad transportation, Railroads, Scheduling, Transportation, Boosting method, Valid inequality, Integer programming
National Category
Information Systems
Identifiers
urn:nbn:se:bth-15477 (URN)10.4230/OASIcs.ATMOS.2017.10 (DOI)2-s2.0-85032450178 (Scopus ID)9783959770422 (ISBN)
Conference
17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, (ATMOS), Vienna
Note

open access

Available from: 2017-11-10 Created: 2017-11-10 Last updated: 2018-01-13Bibliographically approved
Projects
TRANS-FORM - Smart transfers through unravelling urban form and travel flow dynamics [2015-02034_Formas]; Blekinge Institute of Technology; Publications
Yap, M., Cats, O., Törnquist Krasemann, J., van Oort, N. & Hoogendoorn, S. (2022). Quantification and control of disruption propagation in multi-level public transport networks. International Journal of Transportation Science and Technology, 11(1), 83-106Josyula, S. P., Törnquist Krasemann, J. & Lundberg, L. (2021). Parallel computing for multi-objective train rescheduling. IEEE Transactions on Emerging Topics in Computing, 9(4), 1683-1696Josyula, S. P., Törnquist Krasemann, J. & Lundberg, L. (2019). Exploring the Potential of GPU Computing in Train Rescheduling. In: Proceedings of the 8th International Conference on Railway Operations Modelling and Analysis, Norrköping, 2019.: . Paper presented at 8th International Conference on Railway Operations Modelling and Analysis. Josyula, S. P. (2019). Parallel algorithms for real-time railway rescheduling. (Licentiate dissertation). Sweden: Blekinge Institute of TechnologyTörnquist Krasemann, J. & Rydergren, C. (2019). Passagerar-fokuserad hantering av störningar i den regionala tågtrafiken: En sammanställning av arbete och resultat från den svenska delen av TRANSFORM-projektet. KarlskronaJosyula, S. P., Törnquist Krasemann, J. & Lundberg, L. (2018). A parallel algorithm for train rescheduling. Transportation Research Part C: Emerging Technologies, 95, 545-569Josyula, S. P. & Törnquist Krasemann, J. (2017). Passenger-oriented Railway Traffic Re-scheduling: A Review of Alternative Strategies utilizing Passenger Flow Data. In: : . Paper presented at 7th International Conference on Railway Operations Modelling and Analysis, Lille. Törnquist Krasemann, J., Rydergren, C., Cats, O., Molyneaux, N. & Yap, M. (2017). Transform project deliverable D3.1: A toolbox of real-time strategies for smart transfers. ERA-NET Smart Cities and Communities (ENSCC)Josyula, S. P., Törnquist Krasemann, J. & Lundberg, L.A parallel algorithm for multi-objective train rescheduling.
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-8373-8398

Search in DiVA

Show all publications