臺灣博碩士論文加值系統

社會上各種基礎建設的設置是實際且相當重要的問題，在不同時間、空間下，對設施的規劃會產生不同的需求。一般而言基礎設施大都是永久性的建築，以提供長期使用，沒辦法經常更新、遷移。倘若基礎設施設置的位置越好，也就越節省其成本以及交通運輸時間，將其設施經濟效益發揮至最大。而在設施配置問題中， p-center問題經常被拿來當作研究課題。p-center 問題是給定一個無向連通圖G = (V,E)與 p 值，然後找出集合大小不超過 p 的點集合。使得除選定的點集合外的其他各點，到距離其最近的選定點之最大距離為最小。本文使用遞迴法(recursive algorithm) 跟分支限制法(branch-and-bound algorithm)兩種演算法求解 p-center 問題，以探討何者較有效率？由實驗結果得知，遞迴法受邊的數量影響，增長的相當快，分支限制法則剛好相反，邊的數量影響並不明顯，而是點數增加跟 p 值影響較大。當圖內的點邊比小於 1.3 倍時，用遞迴法求解 p-center 問題，會比分支限制法來得更有效率。

Public facilities is a quite practical and important issue. Facility plans need to fit all kinds of demands at various times and places. Generally speaking, fundamental facilities are mostly permanent building structures, which provide long-term services to people; and of course, it cannot be renovated or relocated frequently. Moreover, it is presumed that, the better the location the infrastructures are located at, the less costs and transportation it required, and the bigger cost-efficient. The p-center problem have applications in the location allocation problem, the p-center problem is to give a undirected connected graph G = (V,E) and p,then find a subset S∈E of at most p which minimizes the maximum distances from points in V to S.
We employ recursive algorithm and branch-and-bound algorithm for solving the p-center problem and attempt to find out the more efficient algorithm among these two. From the experimental results, the recursive algorithm has affected by the number of edges, which growing quite fast. On the other hand, branch-and-bound algorithm is opposite; and the effect of the number of edge is not obvious. But instead, increasing the number of points and p values has largely affected. When the point of the graph of the inner edge is less than 1.3 times, it will be more efficient solving the p-center problem by using the recursive algorithm method than the branch-and-bound algorithm.

書名頁..i
論文口試委員審定書..ii
中文摘要..iii
英文摘要..iv
誌謝..v
目錄..vi
表目錄..viii
圖目錄..x
一、緒論..1
1.1 研究動機..1
1.2 研究目的..2
二、文獻探討..4
三、演算法..8
3.1 分支限制法..8
3.2 遞迴法..11
四、實驗..15
4.1 實驗環境..15
4.2 實驗結果..16
五、結論與未來研究方向..31
5.1 結論..31
5.2 未來研究方向..31
參考文獻..32

[1] A. Al-khedhairi and S. Salhi. Enhancements to two exact algorithms for solving the vertex p-center problem. Journal of Mathematical Modelling and Algorithms,4(2):129–147, 2005.
[2] E. Balas and M. C. Carrera. A dynamic subgradient-based branch-and-bound procedure for set covering. Operations Research, 44(6):875–890, 1996.
[3] J. E. Beasley. A note on solving large p-median problems. European Journal of Operational Research, 21(2):270–273, 1985.
[4] B. Ben-Moshe, B. Bhattacharya, and Q. Shi. Efficient algorithms for the weighted 2-center problem in a cactus graph. In Algorithms and Computation, pages 693–703. Springer, 2005.
[5] B. Ben-Moshe, B. Bhattacharya, Q. Shi, and A. Tamir. Efficient algorithms for center problems in cactus networks. Theoretical Computer Science, 378(3):237–252, 2007.
[6] R. Chandrasekaran and A. Daughety. Location on tree networks: p-centre and n-dispersion problems. Mathematics of Operations Research, 6(1):50–57, 1981.
[7] M. S. Daskin. Network and discrete location: models, algorithms, and applications. John Wiley & Sons, 2011.
[8] M. E. Dyer and A. M. Frieze. A simple heuristic for the p–centre problem. Operations Research Letters, 3(6):285–288, 1985.
[9] S. Elloumi, M. Labbe, and Y. Pochet. A new formulation and resolution method for the p-center problem. INFORMS Journal on Computing, 16(1):84–94, 2004.
[10] G. Y. Handler. Minimax location of a facility in an undirected tree graph. Transportation Science, 7(3):287–293, 1973.
[11] G. Y. Handler. Finding two-centers of a tree: The continuous case. Transportation Science, 12(2):93–106, 1978.
[12] D. S. Hochbaum and D. B. Shmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Research, 10(2):180–184, 1985.
[13] T. Ilhan, F.A. Ozsoy, and M.C. Pinar. An efficient exact algorithm for the vertex p-center problem and computational experiments for different set covering subproblems. Depatment of Industrial Engineering & Management Sciences, Northwestern University, 60208, 2002.
[14] T. Ilhan and M. C. Pinar. An efficient exact algorithm for the vertex p-center problem. Preprint.[Online]. Available: http://www.ie.bilkent.edu.tr/ mustafap/pubs, 2001.
[15] O. Kariv and S. L. Hakimi. An algorithmic approach to network location problems. ii: The p-medians. SIAM Journal on Applied Mathematics, 37(3):539–560, 1979.
[16] Y.-F. Lan, Y.-L.Wang, and H. Suzuki. A linear-time algorithm for solving the center problem on weighted cactus graphs. Information Processing Letters, 71(5):205–212, 1999.
[17] N. Megiddo and A. Tamir. New results on the complexity of p-centre problems. SIAM Journal on Computing, 12(4):751–758, 1983.
[18] R. G. Michael and S. J. David. Computers and intractability: a guide to the theory of np-completeness. WH Freeman & Co., San Francisco, 1979.
[19] E. Minieka. The m-center problem. Siam Review, 12(1):138–139, 1970.
[20] F.A. Ozsoy and M.C. Pinar. An exact algorithm for the capacitated vertex p-center problem. Computers & Operations Research, 33(5):1420–1436, 2006.
[21] J. Plesnik. A heuristic for the p-center problems in graphs. Discrete Applied Mathematics, 17(3):263–268, 1987.
[22] W. Pullan. A memetic genetic algorithm for the vertex p-center problem. Evolutionary Computation, 16(3):417–436, 2008.
[23] B. Robic and J. Mihelic. Solving the k-center problem efficiently with a dominating set algorithm. Journal of Computing and Information Technology, 13(3):225–234, 2005.
[24] A. Tamir. Improved complexity bounds for center location problems on networks by using dynamic data structures. SIAM Journal on Discrete Mathematics, 1(3):377–396, 1988.
[25] 經濟部通訊產業發展推動小組(2013). 2013第一季通訊產業重要指標：台灣m指標. http://www.communications.org.tw/.