Keeping cargo on the right track

My name is Rob Werst, I am currently developing a heuristic for a mixed-track cargo-train timetabling problem as part of my master’s thesis and internship at Ab Ovo. Train timetabling is a well-studied problem in optimization, and increasing it’s relevance each day as more and more cargo is transported by rail. To solve the train timetabling problem, it is necessary to decide on the departure and waiting times at the decision points of all trains traversing the network. In addition, for every segment with multiple tracks, an appropriate track allocation must be provided for all trains. This should be done so no collisions occur. All trains make their required stop at stations without causing excessive delays. The challenge comes with many interesting constraints, such as different capacities at stations and trains moving at various speeds on single track railway segments. One single missed overtake opportunity has impact on the entire schedule’s efficiency. The fundamental essence of this problem is how to address the conflict resolution. Deciding which trains have to give way and thus delay their journey in favor of others seems trivial in a small and local setting, but becomes increasingly complex for larger networks and heavier traffic. Many interesting approaches to this problem have been studied before, genetic algorithms, branch and bound models and even models using ant colony optimization.

Expanding the horizon
I am excited to have the opportunity to tackle this challenge, using my own ideas, contributing to the current state of possible solutions. For my thesis I will develop an optimization model using a randomized greedy algorithm resolving collision and overtake conflicts. A randomized choice is made between feasible alternatives for resolving these conflicts, as every viable option is assigned a certain probability to be selected. This is done for all arising conflicts in order to generate feasible solutions. The solutions generated by this procedure are further improved by means of various local search procedures. The benefit of this model is to utilize the speed of a greedy algorithm to quickly find solutions, while making alterations with a set of probabilities so different feasible alternatives are constructed. After obtaining this initial solution, one can vary the resolutions for certain conflicts in the railway timetable that were resolved. A straightforward example is to swap the order of two trains traversing a leg in the network. More complex neighborhoods considering swaps of multiple conflicts can also be considered. The search is continued until no further improvements are found or until a set number of iterations is completed. Afterwards a new initial solution is constructed using again the greedy algorithm. This process is repeated until a certain stopping condition is met and the best solution is chosen from all previously generated.

An algorithm to fit to the customer needs
One advantage of this model is the infamous quality vs time trade-off is customized to the needs of the user. If a functional feasible solution is needed quickly, the algorithm can run with a small number of iterations with a guaranteed feasibility. If one has plenty of time a larger model is run and parameters of the greedy algorithm are adjusted to provide a more diverse pool of initial solutions. Especially for well-studied problems, this flexibility is crucial to develop algorithms fitting customer needs perfectly.

Internships at Ab Ovo
Ab Ovo gives Econometrics/Operations Research students the opportunity to research complex planning puzzles for writing their the master’s thesis or PhD. Solving world class planning puzzles has our interest. At Ab Ovo the academic and business world come together. Are you interested in this research or do you want to know more about Ab Ovo? Please contact us at info@ab-ovo.com