市區公車路線設計與時刻表整合最佳化

Simultaneous Optimization of Urban Bus Network Design and Timetabling

林依穎(Yi-Ying Lin)

指導教授 ： 朱致遠

國立臺灣大學/工學院/土木工程學研究所/碩士(2020年)

https://doi.org/10.6342/NTU202000029

摘要

本研究採用混合整數規劃(MIP)與平行分支價格切割演算法(BPC)求解都市大眾運輸的路線設計和時刻表整合最佳化問題。演算法最主要的關鍵是以路線和發車時間來建構時刻表，研究也開發貪婪演算法求解價格子問題，並動態加入限制式加強下界。接著進行案例分析以評估模式性能，其結果顯示使用平行BPC演算法求解MIP問題效能優於現有的商用MIP求解器，本研究也針對不同的模式參數求解結果做出分析。

關鍵字

大眾運輸 ； 路線設計 ； 時刻表 ； 分支價格切割法（BPC） ； 混合整數規劃（MIP） ； 演算法

並列摘要

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

並列關鍵字

Public Transit ； Network Design ； Timetable ； Branch-and-Price-and-Cut (BPC) ； Mixed integer Programming (MIP) ； Algorithm

參考文獻

1. Ahuja, R. K., Magnanti, T. L., Orlin, J. B., 1993. Network Flow: Theory, Algorithms, and Applications. Prentice-Hall, Inc.

2. Baaj, M. H., Mahmassani, H. S., 1991. An AI-based approach for transit route system planning and design. Journal of advanced transportation 25 (2), 187–209.

3. Barnhart, C., Hane, C. A., Vance, P. H., 2000. Using branch-and-price-and-cut to solve origindestination integer multicommodity flow problems. Operations Research 48 (2), 318–326.

4. Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W., Vance, P. H., 1998. Branchand-price: Column generation for solving huge integer programs. Operations research 46 (3), 316–329.

5. Bra¨nnlund, U., Lindberg, P. O., No˜u, A., Nilsson, J.-E., 1998. Railway timetabling using lagrangian relaxation. Transportation science 32 (4), 358–369.