Change search
Link to record
Permanent link

Direct link
BETA
Törnquist Krasemann, Johanna
Alternative names
Publications (10 of 29) 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
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: 2018-06-28Bibliographically 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. (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
Ramstedt, L., Törnquist Krasemann, J. & Davidsson, P. (2013). Movement of people and goods. In: Edmonds B., Meyer R. (eds) (Ed.), Understanding Complex Systems: (pp. 705-720). Springer Verlag (9783319669472)
Open this publication in new window or tab >>Movement of people and goods
2013 (English)In: Understanding Complex Systems / [ed] Edmonds B., Meyer R. (eds), Springer Verlag , 2013, no 9783319669472, p. 705-720Chapter in book (Refereed)
Abstract [en]

Due to the continuous growth of traffic and transportation and thus an increased urgency to analyze resource usage and system behavior, the use of computer simulation within this area has become more frequent and acceptable. This chapter presents an overview of modeling and simulation of traffic and transport systems and focuses in particular on the imitation of social behavior and individual decision-making in these systems. We distinguish between transport and traffic. Transport is an activity where goods or people are moved between points A and B, while traffic is referred to as the collection of several transports in a common network such as a road network. We investigate to what extent and how the social characteristics of the users of these different traffic and transport systems are reflected in the simulation models and software. Moreover, we highlight some trends and current issues within this field and provide further reading advice. © 2017, Springer International Publishing AG.

Place, publisher, year, edition, pages
Springer Verlag, 2013
Series
Understanding Complex Systems, ISSN 1860-0832
Keywords
Behavior modeling, Control, Environment, External restrictions, Flow, Freight, Imitation, Individual decision-making, Intentions, Intersections, Networks, Passengers, Stakeholders, Supply chains, Traffic, Transportation
National Category
Infrastructure Engineering Information Systems
Identifiers
urn:nbn:se:bth-15660 (URN)10.1007/978-3-319-66948-9_26 (DOI)2-s2.0-85035350800 (Scopus ID)978-3-540-93812-5 (ISBN)978-3-540-93813-2 (ISBN)
Available from: 2017-12-14 Created: 2017-12-14 Last updated: 2018-01-13Bibliographically approved
Iqbal, S. M., Grahn, H. & Törnquist Krasemann, J. (2013). Multi-Strategy Based Train Re-Scheduling During Railway Traffic Disturbances. In: : . Paper presented at 5th International Seminar on Railway Operations Modelling and Analysis (RailCopenhagen). Copenhagen, Denmark: Technical University of Denmark
Open this publication in new window or tab >>Multi-Strategy Based Train Re-Scheduling During Railway Traffic Disturbances
2013 (English)Conference paper, Published paper (Refereed)
Abstract [en]

Disruptions and delays in railway traffic networks due to different types of disturbances is a frequent problem in many countries. When disruptions occur, the train traffic dispatchers may need to re-schedule the traffic and this is often a very demanding and complicated task. To support the train traffic dispatchers, we propose to use a parallelized multi-strategy based greedy algorithm. This paper presents three different parallelization approaches: (i) Single Strategy with a Partitioned List (i.e. the parallel processes originate from different starting points), (ii) Multiple Strategies with a Non-Partitioned List, and (iii) Multiple Strategies with a Partitioned List. We present an evaluation for a busy part of the Swedish railway network based on performance metrics such as the sum of all train delays at their final destinations and the number of delayed trains. The results show that parallelization helps to improve the solution quality. The parallel approach (iii) that combines all re-scheduling strategies with a partitioned list performs best among the three parallel approaches when minimizing the total final delay. The main conclusion is that the multi-strategy based parallel approach significantly improves the solution for 11 out of 20 disturbance scenarios, as compared to the sequential re-scheduling algorithm. The approach also provides an increased stability since it always delivers a feasible solution in short time.

Place, publisher, year, edition, pages
Copenhagen, Denmark: Technical University of Denmark, 2013
National Category
Computer Sciences
Identifiers
urn:nbn:se:bth-6846 (URN)oai:bth.se:forskinfo2479F542343187D4C1257C2F004FBF66 (Local ID)oai:bth.se:forskinfo2479F542343187D4C1257C2F004FBF66 (Archive number)oai:bth.se:forskinfo2479F542343187D4C1257C2F004FBF66 (OAI)
Conference
5th International Seminar on Railway Operations Modelling and Analysis (RailCopenhagen)
Available from: 2013-11-29 Created: 2013-11-26 Last updated: 2018-02-02Bibliographically approved
Organisations

Search in DiVA

Show all publications