Refine
Document Type
- ZIB-Report (3)
- Article (1)
- In Proceedings (1)
- Master's Thesis (1)
Language
- English (6)
Is part of the Bibliography
- no (6)
Keywords
- Periodic Event Scheduling (1)
- Public Transport (1)
- Timetabling (1)
- crew scheduling (1)
- delay management (1)
- hypergraph (1)
- mixed-integer linear program (1)
- mixed-integer linear programming (1)
- rostering (1)
- scheduling (1)
The optimization of periodic timetables is an indispensable planning task in public transport. Although the periodic event scheduling problem (PESP) provides an elegant mathematical formulation of the periodic timetabling problem that led to many insights for primal heuristics, it is notoriously hard to solve to optimality. One reason is that for the standard mixed-integer linear programming formulations, linear programming relaxations are weak and the integer variables are of pure technical nature and in general do not correlate with the objective value. While the first problem has been addressed by developing several families of cutting planes, we focus on the second aspect. We discuss integral forward cycle bases as a concept to compute improved dual bounds for PESP instances. To this end, we develop the theory of forward cycle bases on general digraphs. Specifically for the application of timetabling, we devise a generic procedure to construct line-based event-activity networks, and give a simple recipe for an integral forward cycle basis on such networks. Finally, we analyze the 16 railway instances of the benchmark library PESPlib, match them to the line-based structure and use forward cycle bases to compute better dual bounds for 14 out of the 16 instances.
It is well-known that optimal solutions are notoriously hard to find for the Periodic Event Scheduling Problem (PESP), which is the standard mathematical formulation to optimize periodic timetables in public transport. We consider a class of incremental heuristics that have been demonstrated to be effective by Lindner and Liebchen (2023), however, for only one fixed sorting strategy of lines along which a solution is constructed. Thus, in this paper, we examine a variety of sortings based on the number, weight, weighted span, and lower bound of arcs, and test for each setting various combinations of the driving, dwelling, and transfer arcs of lines. Additionally, we assess the impact on the incremental extension of the event-activity network by minimizing resp. maximizing a connectivity measure between subsets of lines. We compare our 27 sortings on the railway instances of the benchmarking library PESPlib within the ConcurrentPESP solver framework. We are able to find five new incumbent solutions, resulting in improvements of up to 2%.
The optimization of periodic timetables is an indispensable planning task in public transport. Although the periodic event scheduling problem (PESP) provides an elegant mathematical formulation of the periodic timetabling problem that led to many insights for primal heuristics, it is notoriously hard to solve to optimality. One reason is that for the standard mixed-integer linear programming formulations, linear programming relaxations are weak, and the integer variables are of pure technical nature and in general do not correlate with the objective value. While the first problem has been addressed by developing several families of cutting planes, we focus on the second aspect. We discuss integral forward cycle bases as a concept to compute improved dual bounds for PESP instances. To this end, we develop the theory of forward cycle bases on general digraphs. Specifically for the application of timetabling, we devise a generic procedure to construct line-based event-activity networks and give a simple recipe for an integral forward cycle basis on such networks. Finally, we analyze the 16 railway instances of the benchmark library PESPlib, match them to the line-based structure, and use forward cycle bases to compute better dual bounds for 14 out of the 16 instances.
It is well-known that optimal solutions are notoriously hard to find for the Periodic Event Scheduling Problem (PESP), which is the standard mathematical formulation to optimize periodic timetables in public transport. We consider a class of incremental heuristics that have been demonstrated to be effective by Lindner and Liebchen (2023), however, for only one fixed sorting strategy of lines along which a solution is constructed. Thus, in this paper, we examine a variety of sortings based on the number, weight, weighted span, and lower bound of arcs, and test for each setting various combinations of the driving, dwelling, and transfer arcs of lines. Additionally, we assess the impact on the incremental extension of the event-activity network by minimizing resp. maximizing a connectivity measure between subsets of lines. We compare our 27 sortings on the railway instances of the benchmarking library PESPlib within the ConcurrentPESP solver framework. We are able to find five new incumbent solutions, resulting in improvements of up to 2%.
For the yearly over 500,000 vehicle inspections of the German Federal Logistics and Mobility Office (BALM), crew rosters must be scheduled to efficiently achieve Germany's road inspection control targets. For that, we present a model to solve the respective duty scheduling and crew rostering problem in order to obtain duty rosters that comply with numerous legal regulations while maximizing the 'control success' to achieve the control targets. We formulate the Template Assignment Problem, which can be modelled as a large scale mixed-integer linear program. Here, feasible combinations of control topics are assigned to the duties using a hypergraph approach. The model is used in production by BALM, and we prove its effectiveness on a number of real-world instances.
In railway traffic, delays occur every day, causing deviations from the planned timetable and potentially leading to significant delays for passengers, crew members, and trains. In such cases, the original timetable may become infeasible. Therefore, the delay management problem focuses on the construction of a disposition timetable that minimizes the inconvenience for passengers. In this context, two dispatching decisions must be made: wait–depart decisions, which determine whether trains should wait for delayed feeder trains in order to maintain passenger transfers, and precedence decisions, which define the order of trains while respecting the limited capacity of the railway network.
For the extensively researched Offline Delay Management Problem (ODM), it is assumed that source delays are fully known and stable over an extended planning period. In this thesis, we relax this assumption and propose the Stochastic Delay Management Problem (DM), which handles source delays as constant within an initial control horizon and as random variables following a delay distribution thereafter. We introduce a two-stage stochastic mixed-integer linear programming formulation for the problem and prove NP-hardness for a special case. Moreover, we analyze different fixations of the wait-depart and precedence decisions. For those, we derive bounds for optimal solutions as well as for the optimal objective values, including tightness results.
In practice, numerous simple dispatching rules are applied to guide decisions. To achieve comparability with DM, we integrate seven different rules for wait-depart and precedence decisions into our optimization framework. We then study the price of the rules and show that each examined rule can lead to arbitrarily poor disposition timetables compared to DM. In particular, we present an algorithm corresponding to the case where no dispatching is performed and study the price of non-dispatching.
We compare the performance of DM to the performance of the Offline Delay Management Problem and the seven dispatching rules in a computational experiment for the Berlin S-Bahn with different delay scenarios. It becomes evident that taking stochastic delays into account yields on average 1.7% better disposition timetables, but at the cost of higher runtime. Additionally, the average price of non-dispatching of 2.7% indicates that dispatching is desirable, but not as much as one might expect. Three dispatching rules achieve similarly satisfactory results compared to DM. In particular, the rule that neglects all wait-depart decisions finds similarly good or slightly better disposition timetables than DM within a marginally shorter average runtime.
