Change search
ExportLink to record
Permanent link

Direct link
BETA

Project

Project type/Form of grant
Title [sv]
TRANS-FORM - Smart transfers through unravelling urban form and travel flow dynamics
Title [en]
TRANS-FORM - Smart transfers through unravelling urban form and travel flow dynamics
Abstract [sv]
Smart cities and communities rely on efficient, reliable and robust transport systems. Managing urban public transport systems is becoming increasingly challenging with a pronounced shift towards multiply actors operating in a multi-modal multi-level networks. This calls for the development of an integrated passenger-focused management approach which takes advantage of multiple data sources and state-of-the-art scheduling support. TRANS-FORM, a cooperation between universities, industrial partners, public authorities and private operators, will develop, implement and test a data driven decision making tool that will support smart planning and proactive and adaptive operations. The tool will integrate new concepts and methods of behavioural modelling, passenger flow forecasting and network state predictions into real-time operations. New empirical knowledge and modelling foundations will be developed by undertaking a multi-level approach for monitoring, mapping, analysing and managing urban dynamics in relation to interchanging travel flows. Analysis of pedestrian and traveller flows at the hub, urban and regional networks is facilitated by data secured from case studies in Switzerland, the Netherlands and Sweden, respectively. Project outcomes will allow policy makers and service providers to better understand how travel demand evolves, model traveller flows and interchange activities, develop different strategic and operational measures, and evaluate their impacts.
Publications (9 of 9) 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. (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
Josyula, S. P. (2019). Parallel algorithms for real-time railway rescheduling. (Licentiate dissertation). Sweden: Blekinge Institute of Technology
Open this publication in new window or tab >>Parallel algorithms for real-time railway rescheduling
2019 (English)Licentiate thesis, comprehensive summary (Other academic)
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. The train rescheduling problem is a complex task to solve, both from a practical and a computational perspective. From the latter perspective, a reason for the complexity is that the rescheduling solution(s) of interest may be dispersed across a large solution space. This space needs to be navigated fast while avoiding portions leading to undesirable solutions and exploring portions leading to potentially desirable solutions. The use of parallel computing enables such a fast navigation of the search tree. Though competitive algorithmic approaches for train rescheduling are a widespread topic of research, limited research has been conducted to explore the opportunities and challenges in parallelizing them.

This thesis presents research studies on how trains can be effectively rescheduled while considering the perspectives of passengers along with that of other stakeholders. Parallel computing is employed, with the aim of advancing knowledge about parallel algorithms for solving the problem under consideration.

The presented research contributes with parallel algorithms that reschedule a train timetable during disturbances and studies the incorporation of passenger perspectives during rescheduling. Results show that the use of parallel algorithms for train rescheduling improves the speed of solution space navigation and the quality of the obtained solution(s) within the computational time limit.

This thesis consists of an introduction and overview of the work, followed by four research papers which present: (1) A literature review of studies that propose and apply computational support for train rescheduling with a passenger-oriented objective; (2) A parallel heuristic algorithm to solve the train rescheduling problem on a multi-core parallel architecture; (3) A conflict detection module for train rescheduling, which performs its computations on a graphics processing unit; and (4) A redesigned parallel algorithm that considers multiple objectives while rescheduling.

Place, publisher, year, edition, pages
Sweden: Blekinge Institute of Technology, 2019. p. 184
Series
Blekinge Institute of Technology Licentiate Dissertation Series, ISSN 1650-2140 ; 9
National Category
Computer Sciences
Identifiers
urn:nbn:se:bth-18511 (URN)978-91-7295-378-9 (ISBN)
Presentation
2019-10-17, J1640, Campus Gräsvik, Karlskrona, 09:00 (English)
Opponent
Supervisors
Available from: 2019-08-02 Created: 2019-08-02 Last updated: 2020-10-05Bibliographically 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
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
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
FLOAT
Available from: 2017-04-19 Created: 2017-04-19 Last updated: 2021-12-16Bibliographically 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: 2020-10-05Bibliographically approved
Josyula, S. P., Törnquist Krasemann, J. & Lundberg, L.A parallel algorithm for multi-objective train rescheduling.
Open this publication in new window or tab >>A parallel algorithm for multi-objective train rescheduling
(English)Manuscript (preprint) (Other academic)
National Category
Computer Sciences
Identifiers
urn:nbn:se:bth-18542 (URN)
Available from: 2019-08-15 Created: 2019-08-15 Last updated: 2021-02-23Bibliographically approved
Principal InvestigatorTörnquist Krasemann, Johanna
Coordinating organisation
Blekinge Institute of Technology
Funder
Period
2016-01-01 - 2016-12-31
Identifiers
DiVA, id: project:1991Project, id: 2015-02034_Formas

Search in DiVA

Search outside of DiVA

GoogleGoogle Scholar