Not logged in.
Quick Search - Contribution
Contribution Details
| Type | Master's Thesis |
| Scope | Discipline-based scholarship |
| Title | Alternative Algorithmic Approaches for Crew Diagramming |
| Organization Unit | |
| Authors |
|
| Supervisors |
|
| Language |
|
| Institution | University of Zurich |
| Faculty | Faculty of Business, Economics and Informatics |
| Date | 2022 |
| Abstract Text | The crew diagramming problem has been a challenging task in the railway industry. The massive amount of tasks, requiring multiple crew members to work together under a large set of constrains, create a large scale optimization problem. The common approach to solve this problem which is widely used by the railway companies, is to formulate an integer linear program and decompose it by column generation into a master problem and a sub-problem. However, the sub-problem is often a resource constrained shortest path problem which is NP-hard and the computational time is in the order of hours to days.  We designed an alternative algorithmic approach for the crew diagramming by performing Danztig-Wolfe decomposition on a flow based linear program with set partition constraint. Even though the master problem is still a set partition LP with column generation and minimum cost flow pricing problem, we reduced the number of constraints and avoided solving an NP-hard problem. In order to speed up solving the pricing problem, we split the original network into multiple sub-networks and paralellized the computation of the pricing models. In the end we solved the master problem as an integer programming problem only with the variables selected by the column generation.  This optimization approach was then implemented on real world data provided by Swiss Railways. We compared the results in terms of computational time with the flow based optimizer developed by Algomia GmbH and found that for small and medium-sized depots, our approach is faster on average when compared to the computation time required to arrive only at the LP-solution with Algomia's algorithm. When comparing our results in terms of the number of diagrams with those produced by manual planners, we found a consistent improvement for larger-size depots, where slight adjustments to the constraints often performed by planners have less of an impact on the overall result. |
| PDF File |
Download
|
| Export |
BibTeX
|