https://scholars.lib.ntu.edu.tw/handle/123456789/435369
標題: | Mixed-integer programming model and branch-and-price-and-cut algorithm for urban bus network design and timetabling | 作者: | Chu, J.C. CHIH-YUAN CHU |
關鍵字: | Algorithm; Branch-and-price-and-cut (BPC); Mixed-integer programming (MIP); Network design; Public transit; Timetable | 公開日期: | 2018 | 卷: | 108 | 起(迄)頁: | 188-216 | 來源出版物: | Transportation Research Part B: Methodological | 摘要: | This study solves the simultaneous planning problem of network design and timetabling for urban bus systems. An innovative mixed-integer programming (MIP) model is formulated and a parallel branch-and-price-and-cut (BPC) algorithm is proposed to solve the problem. The key idea of the model formulation and the solution algorithm is to represent a bus timetable with a route and a dispatch pattern. An aggregation and greedy algorithm is developed to efficiently solve the pricing subproblem. The cuts of disaggregate coupling inequalities are dynamically added to strengthen the lower bound. A computational study is conducted to evaluate the performance of the proposed methodology. The comparison with alternative solution approaches indicates that the parallel BPC algorithm is superior to solving the MIP formulations with the off-the-shelf MIP solver. Different values of model parameters are also tested, and various statistics of operators and passengers are reported for the cases. © 2017 Elsevier Ltd |
URI: | https://scholars.lib.ntu.edu.tw/handle/123456789/435369 | DOI: | 10.1016/j.trb.2017.12.013 | SDG/關鍵字: | Algorithms; Buses; Costs; Scheduling; Branch-and-price-and-cut; Mixed integer programming (MIP); Network design; Public transit; Timetable; Integer programming; algorithm; bus transport; network design; numerical model; optimization; public transport; urban transport |
顯示於: | 土木工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。