The question of delay management is whether passenger trains should wait for delayed feeder trains or should depart on time. Solutions to this problem strongly depend on the available capacity of the ...railway infrastructure. Although the limited capacity of the tracks has been considered in delay management models, the limited capacity of the stations has been neglected so far. In this paper, we develop a model for the delay management problem that includes the capacities of the stations. This model allows rescheduling the platform track assignment. Furthermore, we propose an iterative heuristic in which we first solve the delay management model with a fixed platform track assignment, and then improve this platform track assignment in each step. We show that the latter problem can be solved in polynomial time by describing it as a minimum cost flow model. Finally, we present an extension of the model that balances the delay of the passengers on one hand and the number of changes in the platform track assignment on the other. All models are evaluated on real-world instances from Netherlands Railways.
We present a Variable Neighborhood Search heuristic for the rolling stock rescheduling problem. Rolling stock rescheduling is needed when a disruption leads to cancellations in the timetable. In ...rolling stock rescheduling, one must then assign duties, i.e., sequences of trips, to the available train units in such a way that both passenger comfort and operational performance are taken into account. For our heuristic, we introduce three neighborhoods, which focus on swapping duties between train units, on improving the individual duties and on changing the shunting that occurs between trips, respectively. These neighborhoods are used for both a Variable Neighborhood Descent local search procedure and for perturbing the current solution in order to escape from local optima. Moreover, we show that the heuristic can be extended to the setting of flexible rolling stock turnings at ending stations by introducing a fourth neighborhood. We apply our heuristic to instances of Netherlands Railways (NS). The results show that the heuristic is able to find high-quality solutions within 1 min of solving time. This allows rolling stock dispatchers to use our heuristic in real-time rescheduling.
•We consider the rescheduling of rolling stock after a disruption occurs.•We propose a Variable Neighborhood Search heuristic for rolling stock rescheduling.•We develop three innovative neighborhoods for local search and perturbation.•We apply the heuristic to real-world instances of Netherlands Railways (NS).•Solutions of high quality can be obtained within short computation times.
Millions of employees around the world work in irregular rosters. The quality of these rosters is of utmost importance. High-quality rosters should be attractive on an individual level, but also ...divide the work fairly over the employees. We develop novel methodology to compute the trade-off between fairness and attractiveness in crew rostering. First, we propose an intuitive fairness scheme for crew rostering and analyze its theoretical performance. To do so, we introduce the approximate resource-allocation problem. This extension of the resource-allocation problem provides a framework for analyzing decision making in contexts where one relies on approximations of the utility functions. Fairness is a typical example of such a context due to its inherently subjective nature. We show that the scheme has “optimal” properties for a large class of approximate utility functions. Furthermore, we provide a tight bound on the utility loss for this scheme. We then present a unified approach to crew rostering. This approach integrates our proposed fairness scheme with a novel mathematical formulation for crew rostering. We call the resulting problem the Fairness-Oriented Crew Rostering Problem and develop a dedicated exact Branch-Price-and-Cut solution method. We conclude by applying our solution approach to practical instances from Netherlands Railways, the largest passenger railway operator in the Netherlands. Our computational results confirm the importance of taking the fairness–attractiveness trade-off into account.
This paper was accepted by Yinyu Ye, optimization.
•We formulate the one-block train formation problem as a binary linear program.•The model incorporates the unitary rule and intree requirement from Chinese practice.•Provably optimal solutions are ...obtained for medium-scale real-world instances.•A novel tree-based decomposition algorithm is developed for large-scale instances.
We investigate the one-block train formation problem (TFP) in the railway freight transportation industry. The input to this problem is a railway network and a set of demands for transportation. Each demand is a request for shipping a number of rail cars from one station to another. The one-block TFP now addresses two subproblems in the tactical level: Which pairs of stations are directly connected via a block (or: train service); and which demands are transported by each block. The aim is to service all demands against minimal costs. Moving beyond current researches on service network design, the unitary rule and the intree rule are taken into account in this study based on the Chinese railway background. We develop a linear binary programming formulation to minimize the total sum of train accumulation costs and car classification costs, subject to limitations on the classification capacity and the number of sort tracks at each station. Furthermore, we propose a novel solution methodology that applies a tree-based decomposition algorithm. Here, we first decompose the whole network into a series of rooted trees for each destination separately. Then, we divide the trees further into sufficiently small subtrees, whose size is regulated by a node size parameter. Finally, we construct a restricted linear binary model for each subtree and solve these models sequentially to find their optimal solutions. The algorithm ensures that an overall feasible solution is obtained if one exists. Our computational results on a realistic network from the Chinese railway system with 83 stations, 158 links and 5700 randomly generated demands show that the proposed algorithm can derive high-quality solutions within a few hours of computation time. These solutions are on average 48.05% better than those obtained after solving the linear binary program with a commercial solver for 1 day.
We provide a preprocessing method to reduce the vehicle capacity for instances of the capacitated vehicle routing problem. This improves the LP bound of many formulations of the capacitated vehicle ...routing problem. It also speeds up common algorithms for which the computation time depends on the vehicle capacity. Our simulation experiments suggest that, perhaps surprisingly, often the vehicle capacity is very tight in the sense that it cannot be reduced by much.
Unmanned Aerial Vehicles (UAVs) can provide significant contributions to information gathering in military missions. UAVs can be used to capture both full motion video and still imagery of specific ...target locations within the area of interest. In order to improve the effectiveness of a reconnaissance mission, it is important to visit the largest number of interesting target locations possible, taking into consideration operational constraints related to fuel usage, weather conditions and endurance of the UAV. We model this planning problem as the well-known orienteering problem, which is a generalization of the traveling salesman problem. Given the uncertainty in the military operational environment, robust planning solutions are required. Therefore, our model takes into account uncertainty in the fuel usage between targets, for instance due to weather conditions. We report results for using different uncertainty sets that specify the degree of uncertainty against which any feasible solution will be protected. We also compare the probability that a solution is feasible for the robust solutions on one hand and the solution found with average fuel usage on the other. These probabilities are assessed both by simulation and by derivation of problem specific theoretical bounds on the probability of constraint feasibility. In doing so, we show how the sustainability of a UAV mission can be significantly improved. Additionally, we suggest how the robust solution can be operationalized in a realistic setting, by complementing the robust tour with agility principles.
We propose a new FPTAS for the multi-objective shortest path problem with non-negative and integer arc costs. The algorithm uses elements from both an exact labeling algorithm and an FPTAS proposed ...by Tsaggouris and Zaroliagis 25. We analyze the running times of these three algorithms both from a theoretical and a computational point of view. Theoretically, we show that there are instances for which the new FPTAS runs arbitrarily faster than the other two algorithms. Furthermore, for the bi-objective case, the number of approximate solutions generated by the proposed FPTAS is at most the number of Pareto-optimal points multiplied by the number of nodes. By performing a set of computational tests, we show that the new FPTAS performs best in terms of running time in case there are many dominated paths and the number of Pareto-optimal points is not too small.
•A new FPTAS for a multi-objective shortest path (MOSP) problem is developed.•The running time of this FPTAS decreases with the size of the Pareto-optimal frontier.•The FPTAS can be arbitrarily faster than one from literature and an exact algorithm.•We provide an instance with maximum sized Pareto-optimal frontier w.r.t. the nodes.•We extensively test FPTASes for the MOSP problem in a computational study.
We investigate to what degree we can integrate a train timetabling/engine scheduling problem with a crew scheduling problem. In the timetabling/engine scheduling problem, we determine for each demand ...a specific time within its time window when the demand should be serviced. Furthermore, we generate engine duties for the demands. In our solution approach for the overall problem, we first obtain an optimal solution for the timetabling/engine scheduling problem. When solving the crew scheduling problem, we then exploit the fact that numerous optimal and near optimal solutions exist for the previous problem. We consider all these solutions that can be obtained from the optimal engine schedule by shifting the demands in time, while keeping the order of demands in the engine duties intact. In particular, in the crew scheduling stage it is allowed to retime the service of demands if the additional cost is outweighed by the crew savings. This information is implemented in a mathematical model for the crew scheduling problem. The model is solved using a column generation scheme. We perform computational experiments based on a case at a freight railway operator, DB Schenker Rail Scandinavia, and show that significant cost savings can be achieved.
Delay management determines which connections should be maintained in case of a delayed feeder train. Recent delay management models incorporate the limited capacity of the railway infrastructure. ...These models introduce headway constraints to make sure that safety regulations are satisfied. Unfortunately, these headway constraints cannot capture the full details of the railway infrastructure, especially within the stations. We therefore propose an optimization approach that iteratively solves a macroscopic delay management model on the one hand, and a microscopic train scheduling model on the other hand. The macroscopic model determines which connections to maintain and proposes a disposition timetable. This disposition timetable is then validated microscopically for a bottleneck station of the network, proposing a feasible schedule of railway operations. We evaluate our iterative optimization framework using real-world instances around Utrecht in the Netherlands.
We study spare parts inventory control for an aircraft component repair shop. Inspection of a defective component reveals which spare parts are needed to repair it, and in what quantity. Spare part ...shortages delay repairs, while aircraft operators demand short component repair times. Current spare parts inventory optimization methods cannot guarantee the performance on the component level, which is desired by the operators. To address this shortfall, our model incorporates operator requirements as time-window fill rate requirements for the repair turnaround times for each component type. In alignment with typical repair shop policies, spare parts are allocated on a first come first served basis to repairs, and their inventory is controlled using (s, S) policies. Our solution approach applies column generation in an integer programming formulation. A novel method is developed to solve the related pricing problem. Paired with efficient rounding procedures, the approach solves real-life instances of the problem, consisting of thousands of spare parts and components, in minutes.
A case study at a repair shop reveals how data may be obtained in order to implement the approach as an automated method for decision support. We show that the implementation ensures that inventory decisions are aligned with performance targets.
•We optimize spare parts inventories for a component repair shop.•Repairs require multiple different spare parts.•To ensure better alignment with practice we set availability targets on component repair level.•Our algorithm scales to problems consisting of thousands of components and spare parts.•Application of the approach at a repair shop significantly improves inventory control.
PDF
