臺灣博碩士論文加值系統

早期在歐幾里德平面求解韋伯點問題，韋伯點依照兩點直線距離總和最小化來搜尋，若應用在平面空間可能會存在障礙物甚至複雜多邊形障礙物，使得各個來源點的連結路徑上及尋找韋伯點更加相形複雜。
本研究中，尋找韋伯點的方法可處理在歐式平面中存在多個複雜多邊形障礙物情況下找到韋伯點趨近解。本文中，一歐式平面空間存在多個來源點及多邊形障礙物，並以蜂巢狀的方式加入輔助點，其輔物點的目的是為了我們在以限制型三角剖分所有點後，使韋伯點潛在三角網格之範圍縮小，有助於減少尋找韋伯點的潛在範圍與時間，接著應用波形擴散找到韋伯點潛在區位後利用可見度圖(Visibility Graph)與Ahuja-Dijkstra找到韋伯距離最小值，並進一步搜尋更準確之韋伯點潛在三角網格，最後求得韋伯點趨近解。
本研究結合許多演算法來尋找韋伯避障趨近解，應用Visibility Graph將平面上的點連結後建構連結圖其時間複雜度為O(n^2)並利用Ahuja-Dijkstra演算法選擇路徑找出韋伯距離最小值之三角網格最短路徑，但因為有n個來源點，此時時間複雜度為O(n^3)，進一步搜尋韋伯點潛在三角網格並分解k次，最後總時間複雜度為O(kn^3)。



關鍵字：Ahuja-Dijkstra演算法、三角網格、可見度圖、波形傳遞、限制型三角剖分、重心點、避障、韋伯點

The well-known classical Weber problem, an economic problem of great practical importance, is to determine the location of a warehouse such that the total travel distance between the warehouse and a set of spatially distributed customers is minimized.
This thesis presents an efficient method for finding an obstacle avoiding approximation of the Weber point on the Euclidean space. This proposed method searches for the approximation of Weber point based on the triangle mesh-based approach and the concepts of wave propagation, visibility graph and Ahuja-Dijkstra shortest path-finding. The time complexity of our algorithm is O(kn^2 log⁡n) that is proved theoretically and experimentally, where k is the iterations of approximation and n is the number of source points.

致謝.....................................................I
摘要....................................................II
Abstract...............................................III
目錄....................................................IV
圖目錄..................................................V
表目錄..................................................VI
第一章 緒論..............................................1
第二章 文獻探討與研究背景.................................2
2.1 最佳設置位置考量因素之文獻............................2
2.2 最佳設置位置方法的相關文獻............................2
2.3 最佳設置位置加入障礙物之區位問題相關文獻...............2
2.4 研究背景............................................3
第三章 演算法.............................................4
第四章 效能分析...........................................7
第五章 實驗結果...........................................8
第六章 結論與未來展望.....................................11
參考文獻.................................................12

[1] A. Weber, Uber den Standort der Industrien (Mohr, Tubingen, 1909), translated by Carl J. Friedrich as “Alfred Weber’s Theory of the Location of Industries,” Chicago: University of Chicago Press, 1929.
[2] J. Latombe, Robot Motion Planning. Norwell, MA, USA: Kluwer, 1991.
[3] H. Choset, K Lynch , S. Hutchinson, G. Kantor, W. Burgard, L. Kavraki, and S. Thrun, Principles of Robot Motion: Theory, Algorithms, and Implementations. Cambridge, MA, USA: MIT Press, 2005.
[4] J. Barraquand and J. C. Latombe, 1991. “Robot motion planning: A distributed representation approach.” International Journal of Robotics Research., pp. 628–649.
[5] D. F. Watson, “Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes,” Computer Journal, vol. 24, no. 2, 1981. pp. 167–172.
[6] L. P. Chew, “Constrained Delaunay triangulations,” Proceedings of the Third Annual Symposium on Computational Geometry, 1987, pp. 215–222.
[7] E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, 1959, pp. 269–271.
[8] L. Anderegg, M. Cieliebak and G. Principe, “The Weber point can be found linear time for points in biangular configuration,” Technical Report Univ. di Pisa TR-03-01, Jan 12, 2003.
[9] Y. M. Hu, “多面體表面最短路徑實作.” 臺北大學電機工程學系學位論文, 2015.
[10] G. E. Jan, K.Y. Chang, S. Gao, ACM Transactions on Design Automation of Electronic Systems, Vol. 10, No. 1, 2005, pp. 116–135.
[11] R. Ahuja, K. Mehlhorn , J. Orlin, and R. Tarjan,” Faster algorithms for the shortest path problem,” J. ACM, vol. 37, 1990, pp. 213–223.
[12] R. M. Paul, Jr. and F.W. Donald, “Contemporary Logistics,” 8th Edition, Prentice Hall, Inc., 2004.
[13] I. N. Katz and L. Cooper, “Facility location in the presence of forbidden regions I: Formulation and the case of Euclidean distance with one forbidden circle,” European Journal of Operational Research, No. 6, 1981, pp. 166–173.
[14] Y. P. Aneja and M. Parlar, “Algorithm for Weber facility location in the presence of forbidden regions and/or barriers to travel,” Transportation Science, No. 28, 1994, pp. 70–76.
[15] S. E. Butt and T. M. Cavalier, “An efficient algorithm for facility location in the presence of forbidden regions,” European Journal of Operational Research, Vol. 90, 1996, pp. 56–70.
[16] P. M. Dearing and R. Segars, Jr., “An equivalence result for single facility planar location problems with rectilinear distance and barriers,” Annals of Operations Research, Vol. 111, 2002, pp. 89–110.
[17] L. Frei  , K. Klamroth and M. Sprau, “A wavefront to center location problems with barriers,” Annals of Operations Research, Vol.136, 2005, pp. 35–48.
[18] C. Y. Lee, “An algorithm for path connection and its applications,” IRE Transactions on Electronic Computers, EC-10, 1961, pp. 345–346.
[19] K.-Y. Chang, C. M. Su, G. E. Jan, and C. P. 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, 2013, pp. 2060–2076.