請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/21105完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 朱致遠 | |
| dc.contributor.author | Yi-Ying Lin | en |
| dc.contributor.author | 林依穎 | zh_TW |
| dc.date.accessioned | 2021-06-08T03:27:03Z | - |
| dc.date.copyright | 2020-02-10 | |
| dc.date.issued | 2020 | |
| dc.date.submitted | 2020-01-12 | |
| dc.identifier.citation | 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. 6. Carraresi, P., Malucelli, F., Pallottino, S., 1996. Regional mass transit assignment with resource constraints. Transportation Research Part B: Methodological 30 (2), 81–98. 7. Chakroborty, P., 2003. Genetic algorithms for optimal urban transit network design. ComputerAided Civil and Infrastructure Engineering 18 (3), 184–200. 8. Chen, Y.-C., Lin, K.-S., 2009. Theoretical analysis and empirical estimates of the hourly value of travel time saving for intercity and urban transportation in Taiwan (in Chinese). In: 2009 Conference and Annual Meeting of the Chinese Institute of Transportation. 9. Cordeau, J.-F., Toth, P., Vigo, D., 1998. A survey of optimization models for train routing and scheduling. Transportation science 32 (4), 380–404. 10. Crainic, T. G., Le Cun, B., Roucairol, C., 2006. Parallel branch-and-bound algorithms. In: Talbi, E.-G. (Ed.), Parallel combinatorial optimization. John Wiley & Sons. 11. Desaulniers, G., 2010. Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows. Operations research 58 (1), 179–192. 12. Desaulniers, G., Hickman, M. D., 2007. Public transit. Handbooks in operations research and management science 14, 69–127. 13. Desrosiers, J., Lu¨bbecke, M. E., 2011. Branch-price-and-cut algorithms. Wiley encyclopedia of operations research and management science. 14. Fan, L., Mumford, C. L., 2010. A metaheuristic approach to the urban transit routing problem. Journal of Heuristics 16 (3), 353–372. 15. Gao, Z., Sun, H., Shan, L. L., 2004. A continuous equilibrium network design model and algorithm for transit systems. Transportation Research Part B: Methodological 38 (3), 235–250. 16. Guihaire, V., Hao, J.-K., 2008. Transit network design and scheduling: A global review. Transportation Research Part A: Policy and Practice 42 (10), 1251–1273. 17. Hamdouch, Y., Lawphongpanich, S., 2008. Schedule-based transit assignment model with travel strategies and capacity constraints. Transportation Research Part B: Methodological 42 (7), 663–684. 18. Hamdouch, Y., Szeto, W., Jiang, Y., 2014. A new schedule-based transit assignment model with travel strategies and supply uncertainties. Transportation Research Part B: Methodological 67, 35–67. 19. Hewitt, M., Nemhauser, G., Savelsbergh, M. W., 2013. Branch-and-price guided search for integer programs with an application to the multicommodity fixed-charge network flow problem. INFORMS Journal on Computing 25 (2), 302–316. 20. Hewitt, M., Nemhauser, G. L., Savelsbergh, M. W., 2010. Combining exact and heuristic approaches for the capacitated fixed-charge network flow problem. INFORMS Journal on Computing 22 (2), 314–325. 21. Ibarra-Rojas, O., Delgado, F., Giesen, R., Mun˜oz, J., 2015. Planning, operation, and control of bus transport systems: A literature review. Transportation Research Part B: Methodological 77, 38–75. 22. Jiang, Y., Szeto, W., 2016. Reliability-based stochastic transit assignment: Formulations and capacity paradox. Transportation Research Part B: Methodological 93, 181–206. 23. Kim, D., Barnhart, C., Ware, K., Reinhardt, G., 1999. Multimodal express package delivery: A service network design application. Transportation Science 33 (4), 391–407. 24. Liu, J., Zhou, X., 2016. Capacitated transit service network design with boundedly rational agents. Transportation Research Part B: Methodological 93, 225–250. 25. Magnanti, T. L., Wong, R. T., 1984. Network design and transportation planning: Models and algorithms. Transportation science 18 (1), 1–55. 26. Mandl, C., 1979. Applied network optimization. Academic Press, London, UK. 27. Nayeem, M. A., Rahman, M. K., Rahman, M. S., 2014. Transit network design by genetic algorithm with elitism. Transportation Research Part C: Emerging Technologies 46, 30–45. 28. Nuzzolo, A., Crisalli, U., 2009. The schedule-based modeling of transportation systems: recent developments. In: Schedule-Based Modeling of Transportation Networks. Springer, pp. 1–26. 29. Nuzzolo, A., Crisalli, U., Rosati, L., 2012. A schedule-based assignment model with explicit capacity constraints for congested transit networks. Transportation Research Part C: Emerging Technologies 20 (1), 16–33. 30. Quak, C., 2003. Bus line planning. Master’s thesis, TU Delft. 31. Shrivastav, P., Dhingra, S., 2001. Development of feeder routes for suburban railway stations using heuristic approach. Journal of Transportation Engineering 127 (4), 334–341. 32. Shrivastava, P., Dhingra, S., 2002. Development of coordinated schedules using genetic algorithms. Journal of Transportation Engineering 128 (1), 89–96. 33. Szeto, W., Jiang, Y., 2012. Hybrid artificial bee colony algorithm for transit network design. Transportation Research Record: Journal of the Transportation Research Board (2284), 47–56. 34. Szeto, W., Jiang, Y., 2014. Transit assignment: Approach-based formulation, extragradient method, and paradox. Transportation Research Part B: Methodological 62, 51–76. 35. Szeto, W., Wu, Y., 2011. A simultaneous bus route design and frequency setting problem for Tin Shui Wai, Hong Kong. European Journal of Operational Research 209 (2), 141–155. 36. Taipei City Government, 2013. Report for adjustment of bus fare calculation formula (in Chinese). 37. Vanderbeck, F., 2000. On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Operations Research 48 (1), 111–128. 38. Vanderbeck, F., 2005. Implementing mixed integer column generation. In: Column generation. Springer, pp. 331–358. 39. Yan, S., Chen, H.-L., 2002. A scheduling model and a solution algorithm for inter-city bus carriers. Transportation Research Part A: Policy and Practice 36 (9), 805–825. 40. Yan, S., Chi, C.-J., Tang, C.-H., 2006. Inter-city bus routing and timetable setting under stochastic demands. Transportation Research Part A: Policy and Practice 40 (7), 572–586. 41. Yan, S., Tang, C.-H., 2008. An integrated framework for intercity bus scheduling under stochastic bus travel times. Transportation Science 42 (3), 318–335. 42. Yang, H., Bell, M. G. H., 1998. Models and algorithms for road network design: a review and some new developments. Transport Reviews 18 (3), 257–278. 43. Zhao, F., Zeng, X., 2008. Optimization of transit route network, vehicle headways and timetables for large-scale transit networks. European Journal of Operational Research 186 (2), 841–855. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/21105 | - |
| dc.description.abstract | 本研究採用混合整數規劃(MIP)與平行分支價格切割演算法(BPC)求解都市大眾運輸的路線設計和時刻表整合最佳化問題。演算法最主要的關鍵是以路線和發車時間來建構時刻表，研究也開發貪婪演算法求解價格子問題，並動態加入限制式加強下界。接著進行案例分析以評估模式性能，其結果顯示使用平行BPC演算法求解MIP問題效能優於現有的商用MIP求解器，本研究也針對不同的模式參數求解結果做出分析。 | zh_TW |
| dc.description.abstract | 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 | en |
| dc.description.provenance | Made available in DSpace on 2021-06-08T03:27:03Z (GMT). No. of bitstreams: 1 ntu-109-R05521509-1.pdf: 2934973 bytes, checksum: a2dfca6acb7ed4d8b433522125d11568 (MD5) Previous issue date: 2020 | en |
| dc.description.tableofcontents | 誌謝 i
中文摘要 ii ABSTRACT iii CONTENTS iv LIST OF FIGURES vi LIST OF TABLES vii Chapter 1 Introduction 1 Chapter 2 Mathematical model 6 2.1 Problem statement 6 2.2 Model formulation 7 2.2.1 Route 10 2.2.2 Headway 10 2.2.3 Timetable 12 2.2.4 Fleet size 18 2.2.5 Transit assignment 18 2.3 Passenger path generation 18 2.4 Post-processing submodel for bus assignment and identification of no-waiting transfers 21 Chapter 3 Parallel BPC method 24 3.1 Restricted master problem (RMP) 24 3.2 Row generation 27 3.3 Branching rules 28 3.4 Pricing SP 29 3.5 Integer solution at root node 38 Chapter 4 Computational study 39 Chapter 5 Conclusions and future research 56 REFERENCE 60 | |
| dc.language.iso | zh-TW | |
| dc.title | 市區公車路線設計與時刻表整合最佳化 | zh_TW |
| dc.title | Simultaneous Optimization of Urban Bus Network Design and Timetabling | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 108-1 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 陳柏華,許聿廷 | |
| dc.subject.keyword | 大眾運輸,路線設計,時刻表,分支價格切割法（BPC）,混合整數規劃（MIP）,演算法, | zh_TW |
| dc.subject.keyword | Public Transit,Network Design,Timetable,Branch-and-Price-and-Cut (BPC),Mixed integer Programming (MIP),Algorithm, | en |
| dc.relation.page | 65 | |
| dc.identifier.doi | 10.6342/NTU202000029 | |
| dc.rights.note | 未授權 | |
| dc.date.accepted | 2020-01-13 | |
| dc.contributor.author-college | 工學院 | zh_TW |
| dc.contributor.author-dept | 土木工程學研究所 | zh_TW |
| 顯示於系所單位： | 土木工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-109-1.pdf 目前未授權公開取用 | 2.87 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。