簡易檢索 / 詳目顯示

回結果列表
研究生： 王建傑
Wang, Michael
論文名稱： 大眾運輸路網中最短時間及最少旅費之行程規劃研究
Optimal Paths Based on Time and Fares in Transit Networks
指導教授： 王逸琳
Wang, I-Lin
學位類別： 碩士
Master
系所名稱： 管理學院 - 資訊管理研究所
Institute of Information Management
論文出版年： 2008
畢業學年度： 96
語文別： 英文
論文頁數： 93
中文關鍵詞： 時刻表 、行程規劃 、大眾運輸路網 、最短路徑 、旅費
外文關鍵詞： shortest path, transit network, multimodal transportation, trip planning, timetable-based algorithm, non-linear fare structure
相關次數： 點閱：97  下載：8 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 　　在現代化的都會區中，大眾運輸是日常生活中不可或缺的工具。過去大部分乘客都利用時刻表手冊等資訊來規劃其行程，然而隨著交通逐漸繁忙，大眾運輸路網不斷擴建，現今的大眾運輸路網業已十分複雜，往往需要個人導航與行程規劃系統協助方能有效使用；然而，市面上的導航與行程規劃系統多為汽車駕駛者所量身打造，相較之下可提供大眾運輸乘客導航與行程規劃服務之工具幾乎屈指可數；由於大眾運輸路網具有路線固定、規律的營運時間、以及非線性的收費標準等等諸多特殊性，導致原來適用於一般道路路網之導航或行程規劃系統不再適用，因此發展適用於大眾運輸乘客便捷實用的行程規劃系統誠為當務之急。
    　　在使用者輸入起訖點及其出發時間後，本論文提出數個數學模型與演算法以在具有時刻表的大眾運輸路網中規劃最短旅行時間以及最少旅費之行程。在規劃最短旅行時間行程方面，我們首先僅針對搭乘公車、捷運等大眾運輸工具之行程進行規劃，接著再進一步將步行亦列入行程考量，並提出加速方法縮小路網規模以提升行程規劃效率。在最少旅費之行程規劃方面，本論文提出數學模型與演算法來處理其非線性的旅費結構，並針對大台北地區大眾運輸路網的旅費特性提出較簡化的特殊展開網路，以更有效率的方式求解包括轉乘優惠、兩段票等情況之最少旅費行程規劃。

    In a public transportation oriented metropolis such as Tokyo or Taipei, transit system is a convenient means for personal trip. Historically, most transit passengers rely on printed schedules for trip planning. However, the transit network nowadays has become too complicated to navigate manually. With the advance of technology, various navigation applications have been developed for guiding private vehicles, but few are designed for public transportation. Given an origin, destination, and intended departure time, this study proposes two timetable-based algorithms to search for optimal itineraries so that the total travel time for an individual is minimized in an transit network. Itineraries showing the suggested routes with walking access and egress, bus stops, and Mass Rapid Transit (MRT) information will be generated, considering the time to wait for, to transfer between, and to stay in transit vehicles, as well as the time to walk between transit stations. In addition, this study proposes an innovative fare-based algorithm to search for the cheapest itineraries with non-linear fare structure, and an alternative fare model is specifically developed for Taipei transit system. Optimizing trip planning according to time or fare meets the common practices of passengers using transit system in a metropolitan area.

    List of Tables v List of Figures viii Chapter 1. INTRODUCTION 1 1.1. Background and Motivation 1 1.2. Problem De…nition and Methodology 4 1.3. Database and Database Management 5 1.4. Structure of Thesis 7 Chapter 2. LITERATURE REVIEWS 8 2.1. Trip Planning Systems 8 2.2. Shortest Path Algorithms 11 2.3. Timetable Information Problems 12 2.4. Multimodal Transit Problems 16 2.5. Fare Problems 17 Chapter 3. METHODOLOGIES ON A BASIC TIMETABLE INFORMATION PROBLEM 19 3.1. Spatial Data and Temporal Data 21 3.2. Construction of a Basic Timetable-based Network 23 3.3. Query and Solution Method on the Basic Timetable-based Network 25 3.3.1. Procedures 25 3.3.2. An Illustrative Example 28 3.4. Computational Experiments 29 3.4.1. Settings and Problem Sets for the Implementation 29 3.4.2. Algorithmic Running Time Comparison 30 3.5. Speed-up Techniques 32 3.6. Summary 34 Chapter 4. METHODOLOGIES ON A MULTIMODAL TIMETABLE INFORMATION PROBLEM WITH WALKING TRANSFER 36 4.1. Spatial Data and Temporal Data 37 4.2. Construction of a Multimodal Timetable-based Network 41 4.3. Query and Solution Method on a Multimodal Timetable-based Network 44 4.3.1. Procedures 44 4.3.2. An Illustrative Example 46 4.4. Computational Experiments 47 4.4.1. Settings and Problem Sets for the Implementation 48 4.4.2. Algorithmic Running Time Comparison 49 4.5. Speed-up Techniques 50 4.6. Summary 53 Chapter 5. METHODOLOGIES ON FARE INFORMATION PROBLEMS 55 5.1. Spatial Data and Fare Data 56 5.2. Construction of a Fare-based Network 58 5.3. Query and Solution Method on Fare-based Networks 59 5.3.1. Procedures 60 5.3.2. An Illustrative Example 60 5.4. Computational Experiments 61 5.4.1. Settings and Problem Sets for the Implementation 62 5.4.2. Algorithmic Running Time Comparison 63 5.5. Alternative Fare Models 65 5.5.1. Fixed Fare Rate and Variable Fare Rate 65 5.5.2. Transfer Discount 67 5.6. Computational Experiments on Alternative Fare Models 68 5.6.1. Settings and Problem Sets for the Implementation 69 5.6.2. Algorithmic Running Time Comparison 69 5.7. Summary 71 Chapter 6. CONCLUSIONS AND FUTURE RESEARCH 72 6.1. Summary and Contributions 72 6.2. Applications on Di¤erent Platforms 74 6.2.1. Platforms 74 6.2.2. Shortest Path Algorithms 76 6.3. Future Research 78 6.3.1. Multiobjective Shortest Path Problem 78 6.3.2. Dynamic Information 79 6.3.3. Geographic Information System 80 References 81 Appendix A. COMPUTATIONAL EXPERIMENTS ON BASIC TIMETABLE INFORMATION PROBLEMS 86 Appendix B. COMPUTATIONAL EXPERIMENTS ONMULTIMODAL TIMETABLE INFORMATION PROBLEMS WITH WALKING TRANSFER 88 Appendix C. COMPUTATIONAL EXPERIMENTS ON FARE INFORMATION PROBLEMS 90 Appendix D. COMPUTATIONAL EXPERIMENTS ON FARE INFORMATION PROBLEMS WITH ALTERNATIVE FARE MODEL 92

    [1] Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network ‡ows: theory, algorithms and applications. Englewood Cli¤s, NJ: Prentice Hall.
    [2] Ahuja, R. K., Mehlhorn, K., Orlin, J. B., & Tarjan, R. E. (1990). Faster algorithms for the shortest path problem. Journal of the ACM, 37(2), 213-223.
    [3] Cathey, F. W., & Dailey, D. J. (2003). A prescription for transit arrival/departure prediction using automatic vehicle location data. Transportation Research Part C, 11(3-4), 241-264.
    [4] Caul…eld, B., & O’Mahony, M. (2007). An examination of the public transport information requirements of users. IEEE Transactions on Intelligent Transportation Systems, 8(1), 21-30.
    [5] Cheng, S.-T., Liu, J.-P., Kao, J.-L., & Chen, C.-M. (2002). A new framework for mobile web services. Paper presented at the Applications and the Internet (SAINT) Workshops, Nara City, Japan.
    [6] Cherkassky, B. V., Goldberg, A. V., & Radzik, T. (1996). Shortest paths algorithms: theory and experimental evaluation. Mathematical Programming, 73(2), 129-174.
    [7] Chriqui, C. (1975). Common bus lines. Transportation Science, 9(2), 115-121.
    [8] Corman, T. H., Leiserson, C. E., & Riverst, R. L. (1990). Introduction to algorithms. Cambridge, MA: MIT Press.
    [9] Dial, R. B. (1969). Algorithm 360: shortest-path forest with topological ordering. Communications of the ACM, 12(11), 632-633.
    [10] Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
    [11] Fredman, M. L., & Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3), 596-615.
    [12] Friedrich, M., Hofsaess, I., & Wekeck, S. (2001). Timetable-based transit assignment using brand and bound techniques. Journal of the Transportation Research Board: Transportation Research Records, 1752, 100-107.
    [13] Gentile, G., Nguyen, S., & Pallottino, S. (2005). Route choice on transit networks with online information at stops. Transportation Science, 39(3), 289-297.
    [14] Goldberg, A. V., & Radzik, T. (1993). A heuristic improvement of the Bellman-Ford algorithm. Applied Mathematical Letters, 6(3), 3-6.
    [15] Granat, J., & Guerriero, F. (2003). The interactive analysis of the multicriteria shortest path problem by the reference point method. European Journal of Operational Research, 151(1), 103-118.
    [16] Hall, R. W. (1996). Route choice and advanced traveler information systems on a capacitated and dynamic network. Transportation Research Part C, 4(5), 289-306.
    [17] Hickman, M. (2002). Robust passenger itinerary planning using transit AVL data. Paper presented at the IEEE 5th International Conference on Intelligent Transportation Systems, Singapore.
    [18] Horn, M. E. T. (2004). Procedures for planning multi-leg journeys with …xed-route and demand-responsive passenger transport services. Transportation Research Part C, 12(3-4), 33-55.
    [19] Huang, R., & Peng, Z.-R. (2002). Schedule-based path-…nding algorithms for transit trip-planning systems. Journal of the Transportation Research Board: Transportation Research Records, 1783, 142-148.
    [20] Institute of Transportation. (2001). Conditions of Transportation and Communications in Taiwan Area. Taipei, Taiwan: Institute of Transportation, Ministry of Transportation and Communications.
    [21] Koncz, N., Greenfeld, J., & Mouskos, K. (1996). A strategy for solving static multiple-optimal-path transit network problems. Journal of Transportation Engineering, 122(3), 218-225.
    [22] Koncz, N., & Greenfeld, O. (1995). The development of a GIS-based transit advanced traveler information system. Paper presented at the Annual Conference of the Urban and Regional Information Systems Association, Wash-
    ington, D.C.
    [23] Lam, W. H. K., Cheung, C. Y., & Poon, Y. F. (1999). A study of passenger discomfort measures at Hong Kong mass transit railway system. Journal of Advanced Transportation, 33(3), 389-399.
    [24] Le Clercq, F. (1972). A public transport assignment method. Tra￠ c Engineering and Control, 14(2), 91-96.
    [25] Levinson, D. (2003). The value of advanced traveler information systems for route choice. Transportation Research Part C, 11(1), 75-87.
    [26] Lo, H. K., Yip, C. W., & Wan, K. H. (2003). Modeling transfer and nonlinear fare structure in multi-modal network. Transportation Research Part B, 37(2), 149-170.
    [27] Lo, H. K., Yip, C.-W., & Wan, Q. K. (2004). Modeling competitive multimodal transit services: a nested logit approach. Transportation Research Part C, 12(3-4), 251-272.
    [28] Lozano, A., & Storchi, G. (2002). Shortest viable hyperpath in multimodal networks. Transportation Research Part B, 36(10), 853-874.
    [29] McCormack, J. E., & Roberts, S. A. (1996). Exploiting object oriented methods for multi-modal trip planning systems. Information and Software Technology, 38(6), 409-417.
    [30] Mirchandani, P. B., & Wiecek, M. M. (1993). Routing with nonlinear multiattribute cost functions. Applied Mathematics and Computation, 54(2-3), 215-239.
    [31] Modesti, P., & Sciomachen, A. (1998). A utility measure for …nding multiobjective shortest paths in urban multimodal transportation networks. European Journal of Operational Research, 111(3), 495-508.
    [32] Mouskos, K. C., & Greenfeld, J. (1999). A GIS-based multimodal advanced traveler information system. Computer-Aided Civil and Infrastructure Engineering, 14(4), 267-279.
    [33] Muller-Hannemann, M., Schulz, F., Wagner, D., & Zaroliagis, C. (2007). Timetable information: models and algorithms. In Algorithmic Methods for Railway Optimization. Berlin, Germany: Springer.
    [34] Nachtigal, K. (1995). Time depending shortest-path problems with applications to railway networks. European Journal of Operational Research, 83(1), 154-166.
    [35] Nes, R. V., & Bovy, P. (2004). Multimodal traveling and its impact on urban transit network design. Journal of Advanced Transportation, 38(3), 225-241.
    [36] Nguyen, S., & Pallottino, S. (1989). Hyperpaths and shortest hyperpaths. Paper presented at the Lectures given at the third session of the Centro Internazionale Matematico Estivo (C.I.M.E.) on Combinatorial optimization.
    [37] Orda, A., & Rom, R. (1990). Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. Journal of the ACM, 37(3), 607-625.
    [38] Peng, Z.-R., & Huang, R. (2000). Design and development of interactive trip planning for web-based transit information systems. Transportation Research
    Part C, 8(1-6), 409-425.
    [39] Peng, Z.-R., Kim, E., & Weng, Y. (2006). Performance enhancement for online transit trip planning systems: a dynamic reduction of transit networks. Paper presented at the Annual Meeting of Transportation Research Board.
    [40] Rehrl, K., Bruntsch, S., & Mentz, H.-J. (2007). Assisting multimodal travelers: design and prototypical implementation of a personal travel companion. IEEE Transactions on Intelligent Transportation Systems, 8(1), 31-42.
    [41] Schulz, F., Wagner, D., & Weihe, K. (2000). Dijkstra’s algorithm on-line: an empirical case study from public railroad transport. Journal of Experimental Algorithmics, 5, Article 12.
    [42] F. Schulz, D. Wagner, and C. Zaroliagis. (2002) Using multi-level graphs for timetable information in railway systems. Paper presented at the 4th Workshop on Algorithm Engineering and Experiments.
    [43] Sen, S., Pillai, R., Joshi, S., & Rathi, A. K. (2001). A mean-variance model for route guidance in advanced traveler information systems. Transportation Science, 35(1), 37-49.
    [44] Spiess, H., & Florian, M. (1989). Optimal strategies: a new assignment model for transit networks. Transportation Research Part B, 23(2), 83-102.
    [45] Taniguchi, E., & Shimamoto, H. (2004). Intelligent transportation system based dynamic vehicle routing and scheduling with variable travel times. Transportation Research Part C, 12(3-4), 235-250.
    [46] Tong, C. O., & Richardson, A. J. (1984). A computer model for …nding the time-dependent minimum path in a transit system with …xed schedules. Journal of Advanced Transportation, 18(2), 145-161.
    [47] Tong, C. O., & Wong, S. C. (1999). A stochastic transit assignment model using a dynamic schedule-based network. Transportation Research Part B, 33(2), 107-121.
    [48] Vuchic, V. (1981). Urban Public Transportation Systems and Technology. Englewood Cli¤s, NJ: Prentice-Hall.
    [49] Wang, I.-L. (2003). Shortest paths and multicommodity network ‡ows. Dissertation Abstracts International, 64(03), 1472B. (AAT 3085008)
    [50] Wang, I.-L., Johnson, E. L., & Sokol, J. S. (2005). A multiple pairs shortest path algorithm. Transportation Science, 39(4), 465-476.
    [51] Wong, K. I., Wong, S. C., Tong, C. O., Lam, W. H. K., Lo, H. K., Yang, H., et al. (2005). Estimation of origin-destination matrices for a multimodal public transit network. Journal of Advanced Transportation, 39(2), 139-168.
    [52] Wu, C. H., Su, D. C., Chang, J., Wei, C. C., Lin, K. J., & Ho, J. M. (2003). The design and implementation of intelligent transportation web services. Paper presented at the IEEE Conference on Electronic Commerce, Newport Beach, CA.
    [53] Wu, Q., & Hartley, J. (2004). Accommodating user preferences in the optimization of public transport travel. International Journal of Simulation, 5(4), 12-25.
    [54] Yang, H., & Huang, H.-J. (2004).Modeling user adoption of advanced traveler information systems: a control theoretic approach for optimal endogenous growth. Transportation Research Part C, 12(3-4), 193-207.
    [55] Yin, Y., Lam, W. H. K., & Miller, M. A. (2004). A simulation-based reliability assessment approach for congested transit network. Journal of Advanced Transportation, 38(1), 27 - 44.
    [56] Zhan, F. B., & Noon, C. E. (1998). Shortest path algorithms: an evaluation using real road networks. Transportation Science, 32(1), 65-73.

    下載圖示 校內：立即公開
    校外：2008-08-25公開
    QR CODE