Change search
Link to record
Permanent link

Direct link
BETA
Törnquist Krasemann, Johanna
Alternative names
Publications (10 of 31) Show all publications
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
Available from: 2019-08-02 Created: 2019-08-02 Last updated: 2019-08-15Bibliographically 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: 2019-12-13Bibliographically 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, ISSN 1999-4893, E-ISSN 1999-4893, 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.

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: 2019-11-14Bibliographically 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
Engineering and Technology
Identifiers
urn:nbn:se:bth-16868 (URN)10.1016/j.trc.2018.07.003 (DOI)000447112500032 ()
Projects
TRANS-FORM
Funder
Swedish Research Council Formas
Note

open access

Available from: 2018-08-15 Created: 2018-08-15 Last updated: 2019-08-15
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: 2018-03-26Bibliographically 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
Josyula, 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.
Open this publication in new window or tab >>Passenger-oriented Railway Traffic Re-scheduling: A Review of Alternative Strategies utilizing Passenger Flow Data
2017 (English)Conference paper, Published paper (Refereed)
Abstract [en]

Developing and operating seamless, attractive and efficient public transport services in a liberalized market requires significant coordination between involved actors, which is both an organizational and technical challenge. During a journey, passengers often transfer between different transport services. A delay of one train or a bus service can potentially cause the passenger to miss the transfer to the subsequent service. If those services are provided by different operators and those are not coordinated and the information about the services are scattered, the passengers will suffer. In order to incorporate the passenger perspective in the re-scheduling of railway traffic and associated public transport services, the passenger flow needs to be assessed and quantified. We therefore perform a survey of previous research studies that propose and apply computational re-scheduling support for railway traffic disturbance management with a passenger-oriented objective. The analysis shows that there are many different ways to represent and quantify the effects of delays on passengers, i.e.“passenger inconvenience”. In the majority of the studies, re-scheduling approaches rely on historic data on aggregated passenger flows, which are independent of how the public transport services are re-scheduled. Few studies incorporate a dynamic passenger flow model that reacts based on how the transport services are re-scheduled. None of the reviewed studies use real-time passenger flow data in the decision-making process. Good estimations of the passenger flows based on historic data are argued to be sufficient since access to large amounts of passenger flow data and accurate prediction models is available today.

Keywords
Train re-scheduling, Passenger satisfaction, Passenger flow dynamics, Delay management
National Category
Infrastructure Engineering Computer Sciences
Identifiers
urn:nbn:se:bth-14114 (URN)
Conference
7th International Conference on Railway Operations Modelling and Analysis, Lille
Projects
TRANS-FORMFLOAT
Available from: 2017-04-19 Created: 2017-04-19 Last updated: 2019-08-15Bibliographically approved
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)
Open this publication in new window or tab >>Transform project deliverable D3.1: A toolbox of real-time strategies for smart transfers
Show others...
2017 (English)Report (Other academic)
Abstract [en]

Organizing, financing and operating public transport service networks can be quite a challenge. The liberalization of the public transport sector within EU has introduced some additional challenges since the public transport systems nowadays more often consist of services operated by multiple organizations. When passengers move between public transport service networks that are operatedby different organizations, the need for effective coordination become evident. The importance of effective coordination and the associated challenge to achieve this – independent of organizational structure - is the point of origin for the TRANS-FORM project. The project focuses on the development of an integrated passenger-focused management approach that takes advantage of multiple datasources and state-of-the-art scheduling support.This document reports on the work performed in task 3.1 entitled “Real-time traffic management optimization” and task 3.2 entitled “Smart real-time strategies” of the TRANS-FORM project. These tasks were performed as part of work package 3 “Methods for Planning and Operating RobustServices”.The work in the mentioned tasks focus on how to model an integrated passenger-focused management approach including developing strategies that enable improved coordination and smooth passenger transfers. This document contains a specification of the configuration of each modelled level (hub,urban and regional) and the proposed types of management strategies as well as the requiredinformation flow. A specification of the proposed integration of those three levels and their interactionis also presented.

Additional project documentation can be found on the project website: 

http://www.transform-project.org/index.php/progress-and-results/. 

Place, publisher, year, edition, pages
ERA-NET Smart Cities and Communities (ENSCC), 2017. p. 25
Series
TRANSFORM project deliverables
Keywords
Public transport, Railway traffic, Bus transport, Mobility, Simulation, Optimization
National Category
Transport Systems and Logistics
Identifiers
urn:nbn:se:bth-18926 (URN)
Funder
Swedish Research Council Formas, 942 - 2015-2034
Note

OtHer funders: JPI Urban Europe/ENSCC (Project nr: 438.15.404)2;  Karlshamns kommun

Available from: 2019-11-14 Created: 2019-11-14 Last updated: 2019-11-15Bibliographically approved
Törnquist Krasemann, J. (2015). Computational decision-support for railway traffic management and associated configuration challenges: An experimental study. Journal of Rail Transport Planning & Management, 5(3), 95-109, Article ID 10.1016/j.jrtpm.2015.09.002.
Open this publication in new window or tab >>Computational decision-support for railway traffic management and associated configuration challenges: An experimental study
2015 (English)In: Journal of Rail Transport Planning & Management, ISSN 2210-9706, Vol. 5, no 3, p. 95-109, article id 10.1016/j.jrtpm.2015.09.002Article in journal (Refereed) Published
Abstract [en]

This paper investigates potential configuration challenges in the development of optimization-based computational re-scheduling support for railway traffic networks. The paper presents results from an experimental study on how the characteristics of different situations influence the problem formulation and the resulting re-scheduling solutions. Two alternative objective functions are applied: Minimization of the delays at the end stations which exceed three minutes and minimization of delays larger than three minutes at intermediary commercial stops and at end stations. The study focuses on the congested, single-tracked Iron Ore line located in Northern Sweden. A combinatorial optimization model adapted to the special restrictions of this line is applied on 20 different disturbance scenarios and solved using commercial optimization software. The resulting re-scheduling solutions are analyzed numerically and visually in order to better understand the practical impact of using the suggested problem formulations in this context. The results show that the two alternative, objective functions result in structurally, quite different re-scheduling solutions. All scenarios were solved to optimality within 1 minute or less, which indicates that commercial solvers can handle practical problems of a relevant size for this type of setting, but the type of scenario has also a significant impact on the computation time.

Place, publisher, year, edition, pages
Elsevier, 2015
Keywords
Railway traffic management, Real-time scheduling, Decision Support, Optimization, Job Shop Scheduling
National Category
Computer Systems
Identifiers
urn:nbn:se:bth-11114 (URN)10.1016/j.jrtpm.2015.09.002 (DOI)
Projects
Flexibel Omplanering av Tåglägen (FLOAT) www.bth.se/float
Funder
Swedish Transport Administration
Available from: 2015-12-03 Created: 2015-12-03 Last updated: 2015-12-07Bibliographically approved
Törnquist Krasemann, J. (2015). Configuration of an optimization-based decision support for railway traffic management in different contexts. In: 6th International Conference on Railway Operations Modelling and Analysis, Tokyo, March 23-26, 2015: . Paper presented at RailTokyo.
Open this publication in new window or tab >>Configuration of an optimization-based decision support for railway traffic management in different contexts
2015 (English)In: 6th International Conference on Railway Operations Modelling and Analysis, Tokyo, March 23-26, 2015, 2015Conference paper, Published paper (Refereed)
Abstract [en]

This paper investigates potential configuration challenges in the development of optimization-based computational re-scheduling support for railway traffic networks. The paper presents results from an experimental study on how the characteristics of different situations and the network influence the problem formulation and the resulting re-scheduling solutions. Two alternative objective functions are applied: a) Minimization of the delays at the end stations which exceed three minutes and b) minimization of delays larger than three minutes at intermediary commercial stops and at end stations. The study focuses on the congested, single-tracked Iron Ore line located in Northern Sweden and partially Norway. A combinatorial optimization model adapted to the special restrictions of this line is applied and solved using commercial optimization software. 20 different disturbance scenarios are solved and the resulting re-scheduling solutions are analyzed numerically and visually in order to better understand their practical impact. The results show that the two alternative, but similar, objective functions result in structurally, quite different re-scheduling solutions. The results also show that the selected objective functions have some flaws when it comes to scheduling trains that are ahead of their schedule by early departure, or by having a lot of margin time due to waiting time in meeting/passing locations. These early trains are not always “pushed” forward unless the objective function promotes that in some way. All scenarios were solved to optimality within 1 minute or less, which indicates that commercial solvers can handle practical problems of a relevant size for this type of setting.

Keywords
Optimization, Traffic Management, Real-time scheduling, Decision support system, Modelling
National Category
Computer Systems
Identifiers
urn:nbn:se:bth-618 (URN)
Conference
RailTokyo
Projects
FLOAT - www.bth.se/float
Note

Research funded by the Swedish Transport Administration (Trafikverket) via the national research program KAJT (www.kajt.org)

Available from: 2015-05-04 Created: 2015-05-04 Last updated: 2015-05-11Bibliographically approved
Organisations

Search in DiVA

Show all publications