臺灣博碩士論文加值系統

本論文以Alfred Weber所提出工業區位 (Industrial Location)及韋伯點 (Weber Points) 觀念為基礎，從歷年計算幾何學 (Computational Geometry)領域中的相關研究可以發現，對於韋伯理論的區位設置方面，尚未得知以多項式時間能夠求出韋伯點位置之演算法。歷年來學者對於尋找韋伯點的嘗試多以趨近為主，且演算過程中需花費不少的計算時間。
　　基於上述情況，本研究以啟發式(Heuristics)思維探討時間複雜度為O(n)之韋伯點近似解，並參考歐幾里得距離 (Euclidean Distance)與曼哈頓距離 (Manhattan Distance)兩者的特性，以正三角形鑲嵌 (Triangle Tiling)的方式著手，將平均值與中位數兩種起始三角形尋找方式納入演算法流程，並比較兩者所得到的近似點於歐幾里得距離 (Euclidean Distance)中的韋伯距離數據，其執行過程中也包含比較鄰近三角形重心計算出的韋伯距離。我們並於論文中整理實驗結果的比較資料，在來源點數量 (Source Points) |S|=3情況中透過本論文之演算法所得到的韋伯距離數據，與費馬點 (Fermat Point)所得到的韋伯距離數據僅相差百分之二以內。當來源點數量持續增加時，本演算法亦可找出近似點及韋伯距離數值的區域型最佳解 (Local Optimum)近似數據。

The research of this thesis was inspired by the concept named after Alfred Weber. From the related work of Weber Point in Computational Geometry, the polynomial time algorithm for finding the Weber Point in any situation is not well known. Most of the approaches for finding that point are generated by time-consuming approximations in the literature.

In the thesis, our algorithm was inspired by heuristic techniques and the features of both Euclidean Distance and Manhattan Distance. Our proposed method searches for the approximation of Weber point based on the concepts of Triangle Tiling and Recursive Decomposition.

The time complexity of our algorithm is O(n) that is proved theoretically and experimentally, where n is the number of source points. The experimental results of this algorithm with more than 1000 source points are presented as well.

謝詞
中文摘要
英文摘要
目錄
圖目錄
表目錄
第一章 緒論
1.1研究背景與動機
1.2研究目的
第二章 文獻探討
2.1韋伯理論相關文獻
2.2鑲嵌方式相關文獻
第三章 演算法設計
3.1演算法參數及其說明
3.2演算法執行步驟
3.3演算法實際執行範例
第四章 實驗數據與演算法效能分析
4.1計算時間複雜度
4.2執行時間統計
4.3韋伯距離數據比較
第五章 結論
參考文獻

[1] Z. Drezner and A. Goldman, "On the set of optimal points to the Weber problem," Transportation science, vol. 25, no. 1, pp. 3-8, 1991.
[2] F. A. Fetter, "The economic law of market areas," The Quarterly Journal of Economics, vol. 38, no. 3, pp. 520-529, 1924.
[3] H. Hotelling, "Stability in competition," The economic journal, vol. 39, no. 153, pp. 41-57, 1929.
[4] J. H. v. Thünen, P. Hall, and J. H. v. Thünen, "Von Thunen's isolated state," 1966.
[5] K.-Y. Chang, C.-M. Su, G. Jan, and C. Chen, "An efficient method for single-facility location and path-connecting problems in a cell map," International Journal of Geographical Information Science, vol. 27, no. 10, pp. 2060-2076, 2013.
[6] A. Tversky and D. Kahneman, "Judgment under uncertainty: Heuristics and biases," science, vol. 185, no. 4157, pp. 1124-1131, 1974.
[7] A. Weber, Ueber den standort der industrien. Рипол Классик, 1909.
[8] E. Carrizosa and A. M. Rodríguez-Chía, "Weber problems with alternative transportation systems," European Journal of Operational Research, vol. 97, no. 1, pp. 87-93, 1997.
[9] A. Weber and C. J. Friedrich, "Alfred Weber's theory of the location of industries," 1929.
[10] Z. Drezner and J. Guyse, "Application of decision analysis techniques to the Weber facility location problem," European Journal of Operational Research, vol. 116, no. 1, pp. 69-79, 1999.
[11] E. Carrizosa, E. Conde, M. Muñoz-Marquez, and J. Puerto, "The generalized Weber problem with expected distances," RAIRO-Operations Research, vol. 29, no. 1, pp. 35-57, 1995.
[12] J. Dattorro, Convex optimization & Euclidean distance geometry. Lulu. com, 2010.
[13] V. Perlibakas, "Distance measures for PCA-based face recognition," Pattern Recognition Letters, vol. 25, no. 6, pp. 711-724, 2004.
[14] E. F. Krause, Taxicab geometry: An adventure in non-Euclidean geometry. Courier Corporation, 1975.
[15] N. Aidara, "Introduction to probability and statistics," 2018.
[16] S. Dean and B. Illowsky, "Descriptive statistics: skewness and the mean, median, and mode," Connexions website http://www.connexions.org. Accessed, vol. 3, 2017.
[17] E. V. Weiszfeld, "Sur le point pour lequel la somme des distances de n points donnes est minimum", Tohoku Mathematical Journal, Vol. 43, pp. 355-386, 1937.
[18] I. Hong and A. T. Murray, "Efficient measurement of continuous space shortest distance around barriers", International Journal of Geographical Information Science, Vol. 27, No. 12, pp. 2302-2318, 2013.
[19] Z. Drezner, "A note on the Weber location problem," Annals of Operations Research, vol. 40, no. 1, pp. 153-161, 1992.
[20] V. Boltyanski, H. Martini, and V. Soltan, Geometric methods and optimization problems. Springer Science & Business Media, 2013.
[21] S. Durocher and D. Kirkpatrick, "The projection median of a set of points," Computational Geometry, vol. 42, no. 5, pp. 364-375, 2009.
[22] E. Jones, "The 3‐vertex single source Weber location problem," International Journal of Mathematical Education in Science and Technology, vol. 19, no. 5, pp. 671-679, 1988.
[23] C. Bajaj, "The algebraic degree of geometric optimization problems," Discrete & Computational Geometry, vol. 3, no. 1, pp. 177-191, 1988.
[24] K. H. Rosen, Handbook of discrete and combinatorial mathematics. CRC press, 1999.
[25] R. Chandrasekaran and A. Tamir, "Algebraic optimization: the Fermat-Weber location problem," Mathematical Programming, vol. 46, no. 1, pp. 219-224, 1990.
[26] P. Indyk, "Sublinear time algorithms for metric space problems," in Proceedings of the thirty-first annual ACM symposium on Theory of computing, 1999, pp. 428-434: ACM.
[27] L. Anderegg, M. Cieliebak, and G. Prencipe, "The weber point can be found in linear time for points in biangular configuration," ed: Università di Pisa, 2003.
[28] P. S. Stanimirović, M. S. Ćirić, L. A. Kazakovtsev, and I. A. Osinuga, "Single-facility Weber location problem based on the lift metric," Facta universitatis-series: Mathematics and Informatics, vol. 27, no. 2, pp. 175-190, 2012.
[29] G. E. Jan, K. Y. Chang, W. J. Chou and Y. C. Lin, “The Approximation of Weber Point,” Proceedings of National Computer Symposium, #7376, National Dong Hwa University, Taiwan, Dec. 2017.
[30] S. Lim and J. Zhu, "Integrated data envelopment analysis: Global vs. local optimum," European Journal of Operational Research, vol. 229, no. 1, pp. 276-278, 2013.
[31] Z. Drezner and H. W. Hamacher, Facility location: applications and theory. Springer Science & Business Media, 2001.
[32] L. Cooper, "An extension of the generalized Weber problem," Journal of Regional Science, vol. 8, no. 2, pp. 181-197, 1968.
[33] J. Pearl, "Heuristics: intelligent search strategies for computer problem solving," 1984.
[34] B. Grünbaum and G. C. Shephard, Tilings and patterns. Freeman, 1987.
[35] P. Mattila, Geometry of sets and measures in Euclidean spaces: fractals and rectifiability. Cambridge university press, 1999.
[36] H. Steinhaus, Mathematical snapshots. Courier Corporation, 2012.
[37] P. S. Stevens and C. P. Stevens, Handbook of regular patterns: an introduction to symmetry in two dimensions. MIT Press Cambridge, MA, 1981.
[38] P. Spain, "The fermat point of a triangle," Mathematics Magazine, vol. 69, no. 2, pp. 131-133, 1996.