臺灣博碩士論文加值系統

本研究目的主要分析在預算限制下考量多期離散網路設計投資決策模式，本研究問題在考量每期不同預算限制之下如何分期從數個計劃方案中選擇可行方案以使路網總旅行時間達到最小化。模式主要的決策變數包括：每期應執行的計劃組合及每期各路段的流量，本研究將此問題建構為多期二階層混合整數規劃模式，上階層模式表示決策者考量每期預算限制下如何規劃每期應執行的計劃組合，而下階層模式表示用路人在決策者投資決策結果所建構之路網上路徑選擇行為模式。本研究發展混合啓發式演算法進行求解，此演算法可有效率地搜尋到鄰近最佳解，在數個小測試例中與窮舉法之正確解比較，此啓發式演算法與最佳解差距在2%以內，結果顯示本研究可應用於多期大規模離散網路設計問題。

The purpose of this study is to formulate and analyze an investment decision model for multi-period discrete network design with budget considerations. The problem is to determine when to add new links or to increase the capacities of existing links among a set of alternative projects so that the total congestion in the network over the planning horizon is minimized, while keeping the budget within their limits in each period. In this study, at first a multi-period bi-level mixed integer programming model is formulated and then a hybrid heuristic is developed to efficiently find near-optimal solutions. The quality of solutions to a series of small test problems is evaluated – by comparison to the exact solutions by enumeration. In the problems for which exact solutions are available, the heuristic solution is within 2% optimal. The computational procedure appears to hold substantial promise for effective solution for large multi-period discrete network design problems.

目錄
摘要 i
Abstract ii
誌　謝 iii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍 2
1.4 研究架構與流程 2
第二章 文獻回顧 4
2.1 路網均衡指派概念 4
2.2 網路設計（Network Design Problem；NDP） 5
2.3 網路設計之演算法探討 6
2.4 資源分配 10
第三章 問題描述與模式建構 12
3.1 問題描述 12
3.2 模式建構 14
3.2.1 模式基本假設 14
3.2.2 考量預算不留用之多期離散網路設計模式 14
3.2.3 考量預算留用之多期離散網路設計模式 17
第四章 研究方法 19
4.1 窮舉法(Exhaustive Method) 19
4.2 貪婪法(Greedy Method) 22
4.3 啓發式演算法簡介(Heuristic Algorithms) 24
4.3.1 單期演算流程 25
4.3.2 多期演算流程 27
4.3.3 目標值計算 30
4.4 Flank-Wolfe演算法 30
4.5 簡例說明 34
4.5.1 單期簡例測試及說明 34
4.5.2 多期簡例測試及說明 36
4.5.3 小結 37
第五章 測試例分析與比較 39
5.1 測試例說明 39
5.2 計劃基本分析 40
5.3 需求不變分析 41
5.4 小結 44
5.5 整體OD需求成長分析 45
5.6 個別OD需求成長分析 46
5.7 求解品質比較 47
第六章 結論與建議 50
6.1 結論 50
6.2 建議 50
參考文獻 51
附錄 54

參考文獻
1. 李其灃，（民89），「中小型交通建設評估模式之研究」，國立中央大學土木工程學研究所碩士論文。
2. 李信佑，（民92），「宜蘭縣公路建設計畫優先順序之研究」，國立交通大學運輸研究所碩士論文。
3. 凌瑞賢，（民90），運輸規劃原理與實務，鼎漢國際工程顧問股份有限公司出版，台北。
4. 曾國雄、曾勝雄，1993，「連續性均衡網路設計問題求解之研究」，國立交通大學交通運輸研究所博士論文。
5. 劉馨隆，（民89），「公共工程建設計劃時序性組合規劃之研究」，國立中央大學土木工程學系博士論文。
6. AK. Ziliaskopoulos, ”A Linear Programming Model for the Single Destination System Optimum Dynamic Traffic Assignment Problem.” Transportation Science, vol.34, No.1, pp.37-49, 2000.
7. B. L. Garcia, P. Mahey and L. J. LeBlanc, ”Iterative Improvement methods for a Multi-Period Network Design Problem.” European Journal of Operational Research, vol.110, No.1, pp.150-165, 1998.
8. D. Heeremans and L. F. Gelders, ”Multiple Period Repair Kit Problem with a Job Completion criterion：A case study.” European Journal of Operational Research, vol.81, No.2, pp.239-248, 1995.
9. E. R. Petersen, ”A Highway Corridor Planning Model：QROAD.” Transportation Research A, vol.36, No.2, pp.107-125, 2002.
10. EYH. Lin and C-M. Wu, ”The Multiple-Choice Multi-Period Knapsack Problem.” Journal of the Operational Research Society, vol.55, pp.187-197, 2004.
11. Z. G.ao, J. Wu. and H. Sun, ”Solution Algorithm for the Bi-Level Discrete Network Design Problem.” Transportation Research B, vol.39, pp.479-495, 2005.
12. H. Poorzahedy and F. Abulghasemi, ”Application of Ant System to Network Design Problem.” Transportation, vol.32, pp.251-273, 2005.
13. H. Poorzahedy and M. A. Turnquist, ”Approximate Algorithms for the Discrete Network Design Problem.” Transportation Research B, vol.16, pp.45-55, 1982.
14. H. Yang and M. G.. H. Bell, ”Models and Algorithms for Road Network Design：a review and some new development.” Transport Reviews, vol.18, No.3, pp.257-278, 1998.
15. J. Billheimer and P. Gray, ”Network Design with Fixed and Variable Cost Elements.” Transportation Science, vol.7, pp.49-74, 1973.
16. J. D. Murchland, ”Braess’s Paradox of Traffic Flow.” Transportation Research, vol.4, pp.391-394, 1970.
17. J. Alcaraz and C. Maroto, ”A Robust Genetic Algorithm for Resource Allocation in Project Scheduling.” Annals of Operations Research, vol.102, No.1, pp.83-109, 2001.
18. J. W. Herrmann, G.. Ioannou, I. Minis and J. M. Proth, ”A Dual Ascent Approach to the Fixed-Charge Capscitated Network Design Problem.” European Journal of Operational Research, vol.95, pp.476-490, 1996.
19. L. J. LeBlanc, E. K. Morlok and W. Pierskalla, ”An Efficient Approach to Solving the Road Network Equilibrium Traffic Assignment Problem.” Transportation science, vol.9, No.5, pp.309-318, 1975.
20. L. J. Leblanc, ”An Algorithm for the Discrete Network Design Problem.” Transportation Research, vol.9, pp.183-199, 1975.
21. M. Qiu, ”Prioritising and Scheduling Road Projects by Genetic Algorithm.” Mathematics and Computers in Simulation, vol.43, No.3, pp.569-574, 1997.
22. S. W. Chiou, ”Bi level Programming for the Continuous Transport Network Design Problem.” Transportation Research B, vol.39, pp.361-383, 2005.
23. T. L. Magnanti and R. T. Wong, ”Network Design and Transportation Planning：Models and algorithms.” Transportation science, vol.18, pp.1-55, 1983.
24. Turnquist MarkA, ”Investmentin Capacity Changes in Transportation Networks.” Transportation Systems Design, CEE644, 1993.
25. Y. Sheffi, Urban Transportation Network, Englewood Cliffs：Prentice-Hall, 1982.