臺灣博碩士論文加值系統

在各國電信公司爭相邁入整體服務數位網路（簡稱ISDN）的趨勢中，如何適時且經濟地引進適量的新技術與新設備於電信網路，以滿足顧客各式各樣的服務需求，進而達到增裕盈餘的目標，一直是各國電信公司營運上最重要的考量。
本論文針對電信網路投資比重最大，規劃最複雜也最具挑戰性的用戶幹線網路部份加以探討，並提出一套用戶幹線網路投資規劃程序與方法，來求解投資多傳輸技術/多傳輸設備/多服務之電信用戶幹線網路時，規劃上所面臨的主要問題，即：設置時間、設置地點、設置種類及設置數量之決定，以使規劃年限內總投資最經濟。
首先，根據目標年間各年各服務區內之各式服務需求數（皆以DS0當量需求數來表示），及各類傳輸線與傳輸設備的固定與變動成本（皆以年金現值來表示）等參數值下，將網路拓撲設計問題化成〝最小成本網路流量問題〞，以求解各年用戶幹線網路內，各傳輸線與各傳輸設備之最適設備供應數量（即各年的經濟網路架構與設備供應狀況）。
接下來，再依目前網路設備供應狀況與前面所得的各年經濟網路設備供應狀況，將網路設備擴充規劃問題，視為〝需求確定下之批量採購問題〞，以求解出該用戶幹線網路內，各傳輸線與各傳輸設備在目標年間之最適擴充時程、規格及批量數（即容量擴充計畫）。
最後，本論文依據所提的規劃模式與方法，發展求解程式來進行一連串的實証分析。用此來証明本論文所提之規劃模式與方法，皆屬可行，同時也進一步指出未來研究方向的建議。

The Integrated Services Digital Network (ISDN) has become a trend for the telecoms all over the world. From an operational point of view, however, the most critical considerations for these companies are how to bring the new technologies and new equipment economically and timely so that they can satisfy the demand of various services from customers and increase earnings at the same time.
Local Access Network (LAN) is the most complicated part of the telecommunication network. It usually incurs the highest proportion of the investment for the network deployment. The main problems that planning the investment for LAN will face include timing (when), location (where), typing (what equipment), sizing (how many quantities). This paper proposes a investment planning methodology to make the overall investment most economical.
First, by incorporating the objective years, demands of different services in each distribution point (DP) every year, and cost parameters of different transmission media and equipments. The investment planning problem can be treated and solved as a minimum cost network flow problem with fixed-cost nodes, which yields the most economical conditions of network supply for individual years. And then, based on the results of the first stage as well as the current condition of network supply, the capacity planning is treated as a batch purchase problem under given demands. The time schedule of the most economical network investment plan for the objective years can then be obtained.

封面
博士論文指導教授推薦函
博士論文口試委員審定書(中文)
博士論文口試委員審定書(英文)
中文摘要
英文摘要
誌謝
目錄
表目錄
圖目錄
一、緒言
1.1 研究背景說明
1.2 研究動機
1.3 研究目的
1.4 研究課題
1.5 研究限制與範圍
1.6 論文章節簡介
二、文獻回顧與研究流程
2.1 用戶幹線網路的演進
2.2 用戶幹線網路規劃方法的演進
2.3 用戶幹線網路規劃問題的描述
2.4 研究流程與內容
三、規劃問題之模式化及其假設
3.1 規劃問題的圖示與說明
3.2 模式的假設條件
3.3 規劃問題可化為整數規劃模式
3.4 用戶幹線網路規劃問題的求解策略
3.5 經濟網路供應狀況之求解--平均設備利用率的引進
3.6 本章小節
四、最小成本網路流量問題之求解
4.1 MCNFP之基本理論探討
4.2 求解MCNFP之方法介紹
4.3 資料結構的應用與實例說明
4.4 MCNFP程式流程與內容說明
五、實證分析與比較研究
5.1 實證分析之一:實際網路之應用
5.2 實證分析之二:範例應用及說明
5.3 比較分析
六、結論與建議
6.1 結論
6.2 建議
參考文獻
附錄A:ENS求解程式
附錄B:網路生成程式
林向杰個人簡歷

1. 中華電信公司，電信網路統計, 中華電信公司網路處編印, 民國87年出版。
2. 何業勤、陳俊賢，用戶光纖網路架構成本分析模式，交通部電信研究所內部報告，83-NP-804，民國83年1月。
3. 林向杰，「求解最小成本網路流量問題之程式設計與應用領域探討」，交通部電信研究所內部研究報告，民國75年8月。
4. 林向杰，「未來用戶幹線網路規劃模式與方法研究」，交通部電信研究所內部研究報告，民國76年11月。
5. 曹善信，「音頻電纜與PCM系統經濟比較之研究」，交通部電信研究所研究報告彙編，第10卷第3期，民國69年11月。
6. 曾耀煌、趙宏南譯，存貨控制-理論與實務，東海出版社，民國67年8月。原著：Martin, K.S. and W.M. David, Inventory Control: theory and practice.
7. 網路架構演進工作小組接取網路分組，第四篇：接取網路架構演進計畫，中華電信公司，民國87年10月。
8. AT&T Bell Laboratories, Engineering and Operations in the Bell System, Murray Hill, NJ, 1986.
9. Balakrishnan, A., and S.C. Graves, "A Composite Algorithm for a Concave-Cost Network Flow Problem," NETWORKS, Vol. 19, pp. 175-202, 1989.
10. Balakrishnan, A., T.L. Magnanti, and R.T. Wong, "A Dual Ascent Procedure for Large-scale Uncapacitated Network Design," Operations Research, Vol. 37, pp. 716-740, 1989.
11. Balakrishnan, A., T.L. Magnanti, A. Shulman and R.T. Wong, "Model for Planning Capacity Expansion in Local Access Telecommunication Networks," Annals of Operations Research, Vol. 33, pp. 239-284, 1991.
12. Balakrishnan, A., T.L. Magnanti, and P. Mirchandani, "A Dual-based Algorithm for Multi-level Network Design," Management Science, Vol. 40, No. 5, pp. 567-581, 1994.
13. Balakrishnan, A., T.L. Magnanti, and P. Mirchandani, "Modeling and Heuristic Worst-Case Performance Analysis of the Two-level Network Design Problem," Management Science, Vol. 40, No. 7, pp. 846-867, 1994.
14. Balakrishnan, A., T.L. Magnanti, and R.T. Wong, "A Decomposition Algorithm for Local Access Telecommunications Network Expansion Planning," Operations Research, Vol. 43, No.1, pp. 58-76, 1995
15. Bazaraa, M.S. and J.J. Jarvis, Linear Programming and Network Flows, John Wiley & Sons, Inc., 1977.
16. Bean, J.C., and R.L. Smith, "Optimal Capacity Expansion over an Infinite Horizon," Management Sciences, Vol. 31, No. 12, pp. 1523-1532, 1985.
17. Bermond, J.C., and D. Tzvieli, "Minimal Diameter Double-Loop Networks: Dense Optimal Families," NETWORKS, Vol. 21, pp. 1-9, 1991.
18. Bienstock, D., "Computational Experience with an Effective Heuristic for Some Capacity Expansion Problems in Local Access Networks," Telecommunication Systems - Modeling, Analysis, Design and Management, Vol. 1, No. 4, pp. 379-400, 1993.
19. Bradley, G.H., G.G. Brown, and G.W. Graves, "Design and Implementation of Large Scale Primal Transshipment Algorithms," Management Science, Vol. 24, No. 1, pp. 1-34, September 1977.
20. Bulcha, B., L.E. Kodrich, D.B. Luber, W.J. Mitchell, M.A. Schwartz and F.N. Woomer, "Feeder Planning Methods for Digital Loop Carrier," The Bell System Technical Journal, Vol. 61, pp. 2129-2141, 1982
21. Campbell, L.H. and R.F. Laing, "Expansion Planning for Local Telephone Networks," TIMS/ORSA Joint National Meeting, San Francisco, May 14-16, 1984.
22. Campbell, L.H. and R.F. Laing, "Technology Decisions in Local Telephone Networks," IFORS International Conference on Operational Research, Washington, August 6-10, 1984.
23. Cares, G. D., "New and Future Technologies in the Local Telephone Network - The Victoria System," Proceeding IEEE 1986 International Communications Conference, pp. 410-412, 1986.
24. Chang, P.L. and H.C. Lin, "An Investment Planning Methodology of Local Access Networks toward ISDN,?National Symposium on Telecommunications, Chia-Yi, Taiwan, ROC, Dec. 20-21, 1994.
25. Chang, S.G., and B. Gavish, "Tight Lower Bounding Procedures for Multi-period Telecommunications Network Expansion Problems," Telecommunication Systems Conference, Modeling and Analysis, Nashville, USA, pp. 4-21, 1993.
26. Chang, S.G., and B. Gavish, "Telecommunications Network Topological Design and Capacity Expansion: Formulations and Algorithms," Telecommunication Systems - Modeling, Analysis, Design and Management, Vol. 1, No. 2, pp. 99-131, 1993.
27. Chang, S.G., and B. Gavish, "Lower Bounding Procedures for Multi-period Telecommunications Network Expansion Problems," Operations Research, Vol. 43, No. 1, pp. 43-57, 1995.
28. Chen, K.J., J. F. Stach, and T.H. Wu, "Topological Design for the Interconnection of Local Area Networks," IEEE (CH0742-1303), PP. 69-75, 1985.
29. Ciesielka, A. J., and D. C. Douglas, "Electronics in the Suburban and Light Urban Loop Networks," The Bell System Technical Journal, Vol. 59, pp. 417-439, 1980.
30. Ciesielka, A. J., and N. G. Long, "New Technology for Loops-A Plan for the 80''s," IEEE Trans. Comm. COM-28, pp. 923-930, 1980.
31. Cunningham, W.H., "A Network Simplex Method," Mathematical Programming, Vol. 11, pp. 105-116, 1976.
32. Cunningham, W.H., "Theoretical Properties of the Network Simplex Method," Mathematics of Operations Research, Vol. 4, No. 2, pp.196-208, May 1979.
33. Dal Bons, P., A. Del Pistoia, R. Molpen and G. Roso, "GENARC: A Flexible Tools to Design Multi-service Access Networks," NETWORKS''89 - Proceedings of the Fourth International Network Planning Symposium, Palma de Mallorca, Spain, pp. 39-44, 1989.
34. Diogo, J.M.B., J.C.N. Climaco, P.M.N. Nordeste, and J.M.F. Craveirinha, "Dynamic Planning Model for Urban Telephone Networks and Its Applications," IEEE Proceeding I [Communications, Speech and Vision], Vol. 136, No. 4, pp. 283-90, 1989.
35. Dorros, Irwin, "Evolution for the Information Age - The Challenge to Network Planning," NETWORKS''86 - Third International Network Planning Symposium, Innisbrook Tarpon Springs, Florida, pp. 1-4, USA, 1986.
36. Du, D.Z., D.F. Hsu, Q. Li, and J. Xu, "A Combinatorial Problem Related to Distributed Loop Networks," NETWORKS, Vol. 20, pp. 173-180, 1990.
37. Elken, T.R., "The Application of Mathematical Programming to Loop Feeder Allocation," The Bell System Technical Journal, Vol. 59, pp. 479-500, 1980.
38. Fisher, Marshall L., "The Lagrangian Relaxation Method for Solving Integer Programming Problems, " Management Science, Vol. 27, No. 1, pp. 1-18, 1981.
39. Fong, C.O., and V. Srinivasan, "The Multi-Region Dynamic Capacity Expansion Problem, Part I," Operations Research, Vol. 29, No. 4, pp. 787-799, 1981.
40. Fong, C.O., and V. Srinivasan, "The Multi-Region Dynamic Capacity Expansion Problem, Part II," Operations Research, Vol. 29, No. 4, pp. 800-828, 1981.
41. Fong, C.O., and V. Srinivasan, "The Multi-Region Dynamic Capacity Expansion Problem: An Improved Heuristic," Management Science, Vol. 32, No. 9, pp. 1140-1152, 1986.
42. Freidenfelds J., and C.D. Mclaughlin, "A Heuristic Branch-and-Bound Algorithm for Telephone Feeder Capacity Expansion," Operations Research, Vol. 27, No. 3, pp. 567-582, 1979
43. Fujimoto, N., T. Ishihara, A. Taniguchi, H. Yamashita, and K. Yamaguchi, "Experimental Broadband Drop/Insert/Cross-Connect System: 1.8 Gbit/s Optical Shuttle Bus," GLOBECOM''88 IEEE Global Telecommunications Conference and Exhibition - Communications for the Information Age, Vol. 2, pp. 954-9,1988.
44. Gavish, B., and K. Altinkemer, "Parallel Savings Heuristics for the Topological Design of Local Access Tree Networks," Proceeding IEEE INFOCOM''86, pp.130-139, 1986.
45. Gavish, B., "Topological Design of Telecommunication Networks - Local Access Design Methods," Annals of Operations Research, Vol. 33, pp. 17-71, 1991.
46. Gavish, B., "Configuring Wide Area Computer Networks-Problems and Models," OR Spektrum, Vol. 14, No. 3, pp. 115-28, 1992.
47. Gersht, A., and R. Weihmayer, "An Optimization Model for Multi-facility Data Network Evolution Planning," Teletraffic Science for New Cost - Effective Systems, Networks and Services, ITC-12. Proceedings of the Twelfth International Teletraffic Congress, Vol. 1, pp. 473-9, 1988.
48. Glover, F., D. Karney, and D. Klingman, "Implementation and Computational Comparisons of Primal, Dual and Primal-Dual Computer Codes for Minimum Cost Network Flow Problems," NETWORKS, Vol. 4, pp. 191-212, 1974.
49. Goldstein, A.J., "A Directed Hypergraph Database: A Model for the Local Loop Telephone Plant," The Bell System Technical Journal, Vol. 61, No. 9, pp. 2529-2554, 1982.
50. Gouveia, L., and M.J. Lopes, "Using Generalized Capacitated Trees for Designing the Topology of Local Access Networks," 3rd International Conference on Telecommunication Systems, Modeling and Analysis, pp. 320-7, 1995.
51. Helme, M.P., C. Jack and A. Shulman, "Planning for New Service in the Local Loop, " Proceeding International Telecommunication Conference 12, pp. 5.2B.1.1- B.1.12, 1988.
52. Higle, J.L., and C.J. Corrado, "Economic Investment Times for Capacity Expansion Problems," European Journal of Operational Research, Vol. 59, No. 2, pp. 288-293, 1992.
53. Hillier, F.S. and Lieberman, G.J., Introduction to Operations Research, 3rd Ed., Holden-Day, Inc., 1980.
54. Hills, T., "Europe Enters the Broadband Age," Telecommunications, Vol. 28, No. 3, pp. 103-111, 1994.
55. Jack, C., S.R. Kai, and A. Shulman, "NETCAP-An Interactive Optimization System for GTE Telephone Network Planning," INTERFACES, Vol. 22, No. 1, pp. 72-89, 1992.
56. Jack, C., S.R. Kai, and A. Shulman, "Design and Implementation of an Interactive Optimization System for Telephone Network Planning," Operations Research, Vol. 40, No. 1, pp. 14-25, 1992.
57. Kershenbaum, A., and S. Peng, "Neighbor Finding Algorithms for CMST Calculation," Proceeding IEEE INFOCOM''86, pp. 140-147, 1986.
58. Kim, J.G., and D.W. Tcha, "Optimal Design of A Two-level Hierarchical Network with Tree-Star Configuration," Computers & Industrial Engineering, Vol. 22, No. 3, pp. 273-281, 1992.
59. Klingman, D., A. Napier, and J. Stutz, " NETGEN : A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems," Management Science, Vol. 20, No. 5, pp. 814-821, January 1974.
60. Konangi, V.K., C.R. Dhas, and S.G. Belovich, "Topological Design of Local Access Networks," Ninth Annual International Phoenix Conference on Computers and Communications (Cat. No.90CH2799-5), pp. 661-5, 1990.
61. Koontz, W.L.G., "Economic Evaluation of Subscriber Pair Gain System Applications," The Bell System Technical Journal, Vol. 57, No. 4, pp. 825-848, 1978.
62. Koontz, W.L.G., "Economic Evaluation of Loop Feeder Relief Alternatives," The Bell System Technical Journal, Vol. 59, No. 3, pp. 277-293, 1980.
63. Lavin, J.S., "Optimally Rehoming Local Serving Offices to a New Point of Presence," AT&T Technical Journal, Vol. 66, pp. 50-54, 1987.
64. Lee, C.H., H.B. Ro, and D.W. Tcha, "Topological Design of a Two-level Network with Ring-Star Configuration," Computers & Operations Research, Vol. 20, No. 6, pp. 625-37,1993.
65. Leung, J., and T.L. Magnanti, "Valid Inequalities and Facets for Capacitated Plant Location Problems," Mathematical Programming, Vol. 44, pp. 271-292, 1989.
66. Luna, H.P.L., N. Ziviani and R.H.B. Cabral, "The Telephonic Switching Center Network Problem: Formalization and Computational Experience," Discr. Appl. Mathematics, Vol. 18, pp. 199-210, 1987.
67. Luss, H., "Operations Research and Capacity Expansion Problems: A Survey," Operations Research, Vol. 30, No.5, pp. 907-947, 1982.
68. Luss, H., "A Multi-facility Capacity Expansion Model with Joint Expansion Set-Up Costs," Naval Research Logistics Quarterly, Vol. 30, pp. 97-111, 1983.
69. Luss, H., "A Capacity Expansion Model with Applications to Multiplexing in Communication Networks," IEEE Transactions on Systems, Man, and Cybernetics, Vol. SMC-14, No. 3, pp. 419-423, 1984.
70. Luss, H., "A Heuristic for Capacity Expansion Planning with Multiple Facility Types, " Naval Research Logistics Quarterly, Vol. 33, pp. 685-701, 1986.
71. Magnanti, T.L., P. Mirchandani, and R. Vachani, "Modeling and Solving the Two-Facility Capacitated Network Loading Problem," Operations Research, Vol. 43, No. 1, pp. 142-157, 1995.
72. Minoux, M., "Network Synthesis and Dynamic Network Optimization," Ann. Discr. Mathematics, Vol. 31, pp. 283-324, 1987.
73. Minoux, M., "Network Synthesis and Optimum Network Design Problems: Models, Solution Methods and Applications," Networks, Vol. 19, pp313-360, 1989.
74. Monma, C.L. and Segal, M., " A Primal Algorithm for Finding Minimum Cost Flows in Capacitated Networks with Applications," The Bell System Technical Journal, Vol. 61, No. 6, pp. 949-968, 1982.
75. Mukhopadhyaya, K. and B.P. Sinha, "Optimal Design and Routing of Distributed Loop Networks," IEEE International Symposium on Circuits and Systems (Cat. No.91CH30016-4), Vol. 2, pp. 1021-4, 1991
76. Mukhopadhyaya, K., and B.P. Sinha, "Fault-Tolerant Routing in Distributed Loop Networks," IEEE Transactions on Computers, Vol. 44, No. 12, pp. 1452-6, 1991.
77. Murphy, F.H., and A.L. Soyster, "End Effects in Capacity Expansion Models with Finite Horizons, " Naval Research Logistics Quarterly, Vol. 33, pp. 373-383, 1986.
78. Naver, J. R. and S. Petersen, "Determination of the Supply Quality for Specific Consumers and Ways to Improve this Supply Quality," 12 International Conference on electricity Distribution. CIRED (Conf. Publ. No. 373), Vol. 6, pp. 6.15/1-7, 1993.
79. Neebe, A.W., and M.R. Rao, "Sequencing Capacity Expansion Projects in Continuous Time," Management Science, Vol. 32, No. 11, pp. 1467-1479, 1986.
80. Parrish, S.H., T. Cox, W. Kuehner, and Y. Oiu, "Planning for Optimal Expansion of Leased Line Communication Networks," Annals of Operations Research, Vol. 36, No. 1-4, pp. 347-364, 1992.
81. Peha, J.M., and F.A. Tobagi, "Analyzing the Fault Tolerance of Double-Loop Networks," IEEE/ACM Transactions on Networking, Vol. 2, No. 4, pp. 363-73, 1994.
82. Peha, J.M., and F.A. Tobagi, "Fault Tolerance of a Class of Double-Loop Networks," Proceedings IEEE INFOCOM''90-The Conference on Computer Communications. Ninth Annual Joint Conference of the IEEE Computer and Communication Societies, Vol. 2, pp. 512-9, 1990.
83. Pirkul, H., "Location of Concentrators in Designing Local Access Networks," Proceeding IEEE INFOCOM''86, pp. 148-154, 1986.
84. Rocklin, S.M., A. Kashper, and G.C. Varvaloucas, "Capacity Expansion/Contraction of a Facility with Demand Augmentation Dynamics," Operations Research, Vol. 32, No. 1, pp. 133-147, 1984.
85. Roy, T.J.V. "A Cross Decomposition Algorithm for Capacitated Facility Location," Operations Research, Vol. 34, No. 1, pp. 145-163, 1986.
86. Roy, T.J.V., and D. Erlenkotter, "A Dual-Based Procedure for Dynamic Facility Location," Management Science, Vol. 28, No. 10, pp. 1091-1105, 1982.
87. Saniee, I., "An Efficient Algorithm for the Multi-period Capacity Expansion of One Location in Telecommunications," Operations Research, Vol. 43, No. 1, pp. 187-190, 1995.
88. Sen, S., S.K. Saraf, A.L. Soyster, and F.H. Murphy, "The Capital Supply Curve In Capacity Expansion Models: Some Economic and Algorithmic Aspects," Naval Research Logistics Quarterly, Vol. 31, pp. 199-212, 1984.
89. Shulman, A. and R. Vachani, "An Algorithm of Capacity Expansion of Local Access Networks," IEEE INFOCOM''90, San Francisco, U.S.A., Vol. 1, pp. 221-229, 1990.
90. Shulman, A. and R. Vachani, "A Decomposition Algorithm for Capacity Expansion of Local Access Networks," Proceeding IEEE Transactions on Communications, Vol. 41, No. 7, pp. 1063-1073, 1993.
91. Soi, I.M. and K.K. Aggarwal "Overall Reliability Evaluation for Large Computer Communication Networks: an MHC Approach," Microelectronic Reliability, Vol. 25, No. 2, pp. 215-222, 1985.
92. Wang, W.F., and L.Y. Kung, "A High-Speed Double Loop Network with Buffer Insertion Access Scheme for Supporting Multi-media Communication Services," Proceedings of IEEE Singapore International Conference on Networks/ International Conference on Information Engineering, pp. 237-41, 1995.
93. Wilson, D.K., " The Packaging of Optical Network Units - A New Paradigm or The Topological Tyranny of the PCB," Proceedings of the 1995 International Electronics Packaging Conference, pp. 818-26, 1995.
94. Zadeh, N., " A Bad Network Problem for the Simplex Method and Other Minimum Cost Flow Algorithms," Mathematical Programming, Vol. 5, pp. 255-266, 1973.
95. Zheng C., and T. Berger, "Reliability and Availability Analysis of Manhattan Street Networks," IEEE Transactions on Communications, Vol. 43, No. 2-4, pp. 511-22, 1994.