Abstracts of 2017 RAS Student Paper Competition awards
First Place
Thomas Breugem, Erasmus University Rotterdam, An Optimization Framework for Fairness-oriented Crew Rostering
Fairness is an important aspect of the crew rostering process. We introduce the Fairness-oriented Crew Rostering Problem (FCRP). In this problem, attractive cyclic rosters have to be constructed, while respecting a pre-specified fairness level. The goal of the FCRP is to make an explicit trade-off between fairness and attractiveness. That is, to present a set of solutions, where each solution is optimal for a different trade-off between fairness and attractiveness. The integration of fairness into crew rostering adds an additional layer of complexity to the problem. We propose a flexible mathematical formulation, able to exploit problem specific knowledge, and develop an exact Branch-and-Price solution method. By partitioning the days of a rota schedule in clusters, and assigning sequences of duties to these clusters, we obtain a tight formulation for the FCRP. We demonstrate the benefit of our approach on practical instances from Netherlands Railways, the largest passenger railway operator in the Netherlands. We are able to construct the explicit trade-off curve between fairness and attractiveness and show that a dichotomous approach can lead to suboptimal results. In particular, we show that by loosening the fairness requirements slightly, the attractiveness of the rosters can be greatly improved.
Second Place
Sofie Van Thielen, KU Leuven, Benefits of a dynamic impact zone when dealing with train conflicts
In a railway system, a conflict occurs when two trains require the same part of the infrastructure at the same time. Generally, a timetable is constructed in such a way that conflicts are avoided during operations. However, in practice, unexpected events cause delays, frequently leading to conflicts. Currently, such conflicts are typically solved manually by experienced dispatchers. However, it is impossible for them to fully anticipate the impact of their actions on the entire network. Conflict detection and resolution tools can help dispatchers make informed decisions. This paper proposes a conflict prevention strategy directly targeting the work of the dispatcher, by focusing on the relevant part of the network and traffic, and proposing a solution to that part only. This is different from monolithic, global optimization approaches, that solve the entire conflict detection and resolution every time, and from a straightforward First Come, First Served or other typical heuristics.
This strategy works by first looking for possible rerouting options by using an optimization model. If no solution is found, then a solution based on delaying one of the trains is required. This retiming heuristic uses information from an offline calculation, for determining related conflicts that frequently occur. In this way, a so called dynamic impact zone is created online for each conflict. When deciding which train to delay, the potential conflicts and the incurred delays of all trains in this dynamic impact zone are taken into account.
The performance of this new conflict prevention strategy is compared to a common dispatching strategy, other heuristics and an exact method. Extensive experiments on a large part of the Belgian railway network show that by creating this dynamic impact zone, the total delay can be decreased at least by 67 % compared to the basic First Come, First Served decision rule. If the conflict prevention strategy is limited to the retiming heuristic, so without the rerouting part, delays can still be decreased with 51 %. Moreover, the dynamic impact zone has a reasonable size, and scales well to large networks, as only the relevant railway conflicts and their expected consequences are considered in detail in this dynamic impact zone, making our heuristic very fast. Also, the retiming heuristic is compared to an exact method which is based on a branch-and-cut algorithm. For computational reasons, these experiments are limited to a part of the network and to a smaller time horizon. However, the gap with our retiming heuristic is on average 7.2 % and at most 20.4 %. The computation time for returning a solution to a conflict with the proposed conflict prevention strategy is for 95 % of the conflicts less than two seconds and takes at most 21 seconds, including the creation of the dynamic impact zone of the conflict.
Third Place
Pan Shang, Tsinghua University, Equity-oriented skip-stopping schedule optimization in an oversaturated urban rail transit network
In this study, we focus on improving system-wide equity performance in an oversaturated urban rail transit network based on passenger-based formulation. From the system perspective, an urban rail transit network is a distributed system, where a set of resources (i.e., train capacity) is shared by a number of users (i.e., passengers), and equitable individuals and groups should receive equal shares of resources. However, when oversaturation occurs in an urban rail transit network during peak hours, passengers waiting at different stations may receive varying shares of train capacity due to the inequity problem under train all-stopping pattern. Therefore, the inequity problem and the first-in-first-out rules in an oversaturated urban rail transit network is analyzed in a new passenger-based modeling framework. In detail, first, discretized states, corresponding to the number of missed trains of passengers, are constructed in a space-time-state 3-demensional network, so that the system-wide equity performance can be viewed as a distribution of all passengers in different states. Different from existing flow-based optimization models, we formulate a passenger-based integer linear programming model to coordinate passengers and trains in a time-discretized 3-dimensional space–time–state network, thereby optimizing the train skip-stopping pattern for improving system-wide equity performance. To quickly solve the proposed model and find an optimal train skip-stopping pattern with better system-wide equity performance, the passenger-based integer linear programming model can be effectively decomposed to a least-cost subproblem with positive arc costs for individual passengers and a least-cost subproblem with negative arc costs for individual trains under a Lagrangian relaxation framework. For application and implementation, the proposed train skip-stopping optimization model is applied to a simple case and a real-world case based on Batong Line of Beijing Subway Network. The simple case demonstrates that our proposed Lagrangian relaxation framework can obtain the approximate optimal value with a small-gap lower bound and a lot of computing time saved compared with CPLEX solver. The real-world case based on Batong Line of Beijing Subway Network compares the equity indices and efficiency indices under all-stopping pattern and skip-stopping pattern to state the advantage of the proposed skip-stopping pattern optimization model.