Multi-period line planning problem in public transportation

Official URL: https://risc01.sabanciuniv.edu/record=b2758679_(Table of contents)

Urban transportation systems deal with high fluctuations in demand over the day. To capture both temporal and spatial changes in transit demand, we propose a multi-period line planning approach. If such systems are also subject to limitations of resources, a dynamic transfer of resources from one line to another throughout the planning horizon should also be considered. A mathematical modeling framework is developed to solve the line planning problem with a cost-oriented approach considering transfer of resources during a finite length planning horizon of multiple periods. Given the NP-hard nature of the line planning problem, we first present a heuristic approach based on the generic local branching algorithm. We use real-life public transportation network data for our computational results. We conduct extensive computational experiments to demonstrate the efficiency of the algorithms. We show that the local branching algorithm significantly improves solution quality and computing time in comparison to the commercial solver. We also develop various Benders decomposition schemes to solve our multi-period line planning problem. As the traditional Benders decomposition does not show a promising performance, we resort to logic-based Benders decomposition which uses constraint propagation. We demonstrate that the proposed logic-based decomposition outperforms the local branching algorithm; it is able to find high-quality solutions or medium and large instances. Finally, we present a second logic-based Benders decomposition with a smaller master problem while the subproblem is larger and more difficult to solve. We solve this challenging subproblem by reformulating it as a maximum flow problem; this decomposition produces a very effective solution method. Through computational experiments, we show that this algorithm performs better than all other approaches.