Multi-period line planning problem in public transportation

Ahmadi Digehsara, Amin (2022) Multi-period line planning problem in public transportation. [Thesis]

[thumbnail of 10309283.pdf] PDF

Download (2MB)


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.
Item Type: Thesis
Uncontrolled Keywords: Public transportation planning. -- Line planning problem. -- Multi-period planning. -- Mixed-integer linear programming. -- Local branching. -- Benders decomposition. -- Logic-based Benders decomposition. -- Kentsel Ulaşım Planlama. -- Hat planlama problemi. -- Çok dönemli Planlama. -- Karışık-tamsayılı doğrusal programlama. -- Yerel dallanma. -- Benders ayrıştırma. -- Mantık tabanlı Benders.
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: Dila Günay
Date Deposited: 24 Apr 2023 09:41
Last Modified: 24 Apr 2023 09:41

Actions (login required)

View Item
View Item