I am a first year doctoral researcher in the Transport Systems Group at IVT lead by Francesco Corman. My research interest focuses on optimization and learning in railway scheduling. My project is a research collaboration with the Swiss Federal Railways SBB and Siemens Mobility.
I received my masters degree in Electrical Engineering and Information Technology from ETH Zurich. For my Master's Thesis at IBM Research Zurich, I worked on an optimization model for decomposing quantum operations.
Projects
Railway scheduling is a complex task that involves solving recurring instances of constrained optimization problems. Traditionally, each instance is treated as an isolated problem, leading to inefficiencies in computational effort and scalability. This research explores reinforcement learning for optimizing railway timetables based on a graph representation of the scheduling problem.
In railway traffic management, the goal is to handle delays and restore the original schedule. Since operators must act in real time, there is a trade-off between solution quality and computation time. Thus, an approach which generates a feasible solution instantly but may refine it over time is desirable as an operator can balance this trade-off based on the current situation. Here we present such an approach.
Starting from the original feasible schedule—where train paths and precedences between trains are fixed—we model dependencies using a graph over resource occupation events. Nodes represent events where trains occupy track sections, and edges encode precedence constraints. When a delay occurs, some event will be delayed and this delay can be propagated along the links in the graph. For every event in the schedule, there is a deviation from the scheduled time and the delayed time. This new delayed schedule is a feasible starting point for the SMT solver.
The SMT solver finds feasible solutions for a schedule by encoding the routing decisions and precedence decisions between trains as selectable linear constraints. In MaxSMT, one adds weights to certain selectable constraints and the algorithm seeks a solution which minimizes the total weight of violated constraints— prioritizing the satisfaction of more important ones. From the delayed schedule, we constrain event timings to push them closer to their original values. We consider aspects such as fairness in the amount every train is delayed or minimizing delay propagation, favoring trains that were initially unaffected.
In Bender's Decomposition a combinatorial optimization problem is decomposed into a master and multiple subproblems. The variables in the subproblems are disjoint or must be coordinated in the master problem. If the coordination by the master problem is too complicated, the time to solve the master problem will dominate and the benefits of decomposition are dahin. Thus, choosing where to decompose the problem into subproblems to minimize the interaction between subproblems is essential.
This research proposes to optimize a railway schedule using logic-based Bender's decomposition, where the master problem is a mixed-integer program which optimizes the schedule and the subproblems are feasibility problems solving the routing and selection of precedences between trains. The challenge is making sure that the selection of a precedence between trains does not span multiple subproblems and thus needs to be added to the master. To ensure this, the boundaries between subproblems are updated whenever a conflict is active which spans multiple subproblems ensuring that the conflict is contained within a single subproblem only.