| 1. |
- Andersson, Emma, 1983-, et al.
(författare)
-
Improved Railway Timetable Robustness for Reduced Traffic Delays – a MILP approach
- 2015
-
Ingår i: 6th International Conference on Railway Operations Modelling and Analysis, Tokyo, Mars 23-26, 2015..
-
Konferensbidrag (refereegranskat)abstract
- Maintaining high on-time performance and at the same time having high capacity utilization is a challenge for several railway traffic systems. The system becomes sensitive to disturbances and delays are easily propagating in the network. One way to handle this problem is to create more robust timetables; timetables that can absorb delays and prevent them from propagating. This paper presents an optimization approach to reduce the propagating of delays with a more efficient margin allocation in the timetable. A Mixed Integer Linear Programming (MILP) model is proposed in which the existing margin time is re-allocated to increase the robustness for an existing timetable. The model re-allocates both runtime margin time and headway margin time to increase the robustness at specific delay sensitive points in a timetable. We illustrate the model’s applicability for a real-world case where an initial, feasible timetable is modified to create new timetables with increased robustness. These new timetables are then evaluated and compared to the initial timetable. We evaluate how the MILP approach affects the initial timetable structure and its capability to handle disturbances by exposing the initial and the modified timetables to some minor initial disturbances of the range 1 up to 7 minutes. The results show that it is possible to reduce the delays by re-allocating margin time, for example, the total delay at end station decreases with 28 % in our real-world example.
|
|
| 2. |
- Gestrelius, Sara
(författare)
-
Mathematical models for optimising decision support systems in the railway industry
- 2015
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- After the deregulation of the Swedish railway industry, train operating companies compete for and on the same infrastructure. This makes the allocation of rail capacity a most delicate problem, and for a well-functioning railway system the allocation must be fair, efficient and functional. The capacity allocation tasks include e.g. constructing the yearly timetable and making track allocation plans for rail yards. The state of practice is that experienced planners construct the schedules manually with little or no decision support. However, as the planners are often faced with large combinatorial problems that are notoriously hard to solve there is a great potential in implementing optimising decision support systems. The research presented in this licentiate thesis aims at developing and examining mathematical models and methods that could be part of such support systems. The thesis focuses on two planning problems in particular, and the presented methods have been developed especially for the Swedish railway system. First of all, a model for optimising a train timetable with respect to robustness is presented. The model tries to increase the number of alternative meeting locations that can be used in a disturbed traffic situation and has an execution time of less than 5 minutes when solving the problem for the track section between Boden and Vännäs. Secondly, the problem of generating efficient classification bowl schedules for shunting yards is examined. The aim is to find the track allocation that minimises the number of required shunting movements while still respecting all operational, physical and time constraints imposed by the yard. Three optimisation models are presented, and simple planning rules are also investigated. The methods are tested on historic data from Hallsberg, the largest shunting yard in Sweden, and the results show that while the simple planning rules are not adequate for planning the classification bowl, two of the optimisation models consistently return an optimal solution within an acceptable execution time.
|
|
| 3. |
- Gholami, Omid, 1979-, et al.
(författare)
-
A Heuristic Approach to Solving the Train Traffic Re-Scheduling Problem in Real Time
- 2018
-
Ingår i: Algorithms. - : MDPI. - 1999-4893. ; 11:4, s. 1-18
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 4. |
- Josyula, Sai Prashanth, 1992-, et al.
(författare)
-
A parallel algorithm for train rescheduling
- 2018
-
Ingår i: Transportation Research Part C. - : Elsevier. - 0968-090X .- 1879-2359. ; 95, s. 545-569
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 5. |
|
|
| 6. |
- Josyula, Sai Prashanth, 1992-
(författare)
-
Parallel algorithms for real-time railway rescheduling
- 2019
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In railway traffic systems, it is essential to achieve a high punctuality to satisfy the goals of the involved stakeholders. Thus, whenever disturbances occur, it is important to effectively reschedule trains while considering the perspectives of various stakeholders. 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.
|
|
| 7. |
- Josyula, Sai Prashanth, 1992-, et al.
(författare)
-
Passenger-oriented Railway Traffic Re-scheduling : A Review of Alternative Strategies utilizing Passenger Flow Data
- 2017
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 8. |
- Khoshniyat, Fahimeh, 1981-, et al.
(författare)
-
An Optimization Approach for On-Demand Railway Slot Allocation
- 2017
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 9. |
- Khoshniyat, Fahimeh, 1981-, et al.
(författare)
-
Analysis of strengths & weaknesses of a MILP model for revising railway traffic timetables
- 2017
-
Ingår i: OpenAccess Series in Informatics. - Dagstuhl, Germany : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. - 9783959770422
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 10. |
- Khoshniyat, Fahimeh
(författare)
-
Optimization-Based Methods for Revising Train Timetables with Focus on Robustness
- 2016
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- With increase in the use of railway transport, ensuring robustness in railway timetables has never been this important. In a dense railway timetable even a small disturbance can propagate easily and affect trains' arrival and departure times. In a robust timetable small delays are absorbed and knock-on effects are prevented effectively. The aim of this thesis is to study how optimization tools can support the generation of robust railway traffic timetables. We address two Train Timetabling Problems (TTP) and for both problems we apply Mixed Integer Linear Programming (MILP) to solve them from network management perspectives. The first problem is how robustness in a given timetable can be assessed and ensured. To tackle this problem, a headway-based method is introduced. The proposed method is implemented in real timetables and evaluated from performance perspectives. Furthermore, the impact of the proposed method on capacity utilization, heterogeneity and the speed of trains, is monitored. Results show that the proposed method can improve robustness without imposing major changes in timetables. The second problem addressed in the thesis is how robustness can be assessed and maintained in a given timetable when allocating additional traffic and maintenance slots. Different insertion strategies are studied and their consequences on capacity utilization and on the properties of the timetables are analyzed. Two different insertion strategies are considered: i) simultaneous and ii) stepwise insertion. The results show that inserting the additional trains simultaneously usually results in generating more optimal solutions. However, solving this type of problem is computationally challenging. We also observed that the existing robustness metrics cannot capture the essential properties of having more robust timetables. Therefore we proposed measuring Channel Width, Channel Width Forward, Channel Width Behind and Track Switching.Furthermore, the experimental analysis of the applied MILP model shows that some cases are computationally hard to solve and there is a need to decrease the computation time. Hence several valid inequalities are developed and their effects on the computation time are analyzed.This thesis contains three papers which are appended. The results of this thesis are of special interests for railway traffic planners and it would support their working process. However, railway traffic operators and passengers also benefit from this study.
|
|
