請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/55544
標題: | 在工業設計、製造與管理上幾何計算問題之研究 Geometric Computing for Industrial Design, Manufacturing and Management |
作者: | Bang-Sin Dai 戴邦炘 |
指導教授: | 李德財 |
關鍵字: | 計算幾何,可視性,固體鑄模,路徑規劃,時間凸包, Computational Geometry,Visibility,Solid Moulding,Path Planning,Time Convex Hull, |
出版年 : | 2014 |
學位: | 博士 |
摘要: | 在這份學位論文中,我們從演算法的角度來探討工業應用上的幾何計算問題。這些在工業設計、製造與管理領域中所遭遇到的實際問題被我們以數學模型抽象化的方式規劃成正式的演算法問題。針對這些工業應用上的幾何計算問題,我們分別提出了具有理論作為保證的演算法設計分析與問題困難度的論證、以及從組合數學的面向去探討組合學複雜度,共同構成在這個複雜議題上一份完整且全面性的研究探討。
在工業設計和製造方面,我們考慮了“固體鑄模”問題,這個問題是從鑄模技術的設計程序以及製造程序中許多的最佳化問題所規劃出來。從理論的觀點來看,我們所探討的固體鑄模問題在“計算幾何”領域中一個最古典的研究主題“可視性”裡是相當重要且具有基礎性的議題。針對此問題,我們分別提出了具備嚴謹理論作為保證的演算法設計分析以及問題困難度的證明,在我們獲得的主要研究成果中,問題複雜度與演算法複雜度之間的間隔差距幾乎是封閉的。此外,從組合數學的角度,我們也提出了緊貼的組合學複雜度上界與下界。在實務應用上,我們所設計的演算法相當有效率。 在工業管理方面,我們考慮了“時間凸包”問題,這個問題是由在高速運輸網路存在的情況之下的“路徑規劃”議題及最短路徑問題的進階延伸所引起。對於運輸業而言,將運輸時間與運輸成本最小化是最重要的追求目標之一。在這個問題中,我們探討了最短時間成本的路徑規劃以及“凸包”問題在被導入以“時間”為基礎的概念之下的問題推廣。針對此問題,我們獲得的主要研究成果是在一條直線高速公路存在的情況裡,並且以廣義Lp作為距離的度量底下,一個能透過理論證明為最佳的演算法。就某種意義上,我們的研究成果終結了此問題在這樣的特定網路拓樸底下的研究探討。 This dissertation addresses the geometric computing problems in industrial application from an algorithmic perspective. The practical issues encountered in the fields of industrial design, manufacturing, and management are formulated as algorithmic problems by mathematical abstraction. We present both the algorithmic results and the hardness proofs with theoretical guarantees and also the combinatorial bounds in the aspect of combinatorics to jointly compose a comprehensive study for the entire research. In terms of industrial design and manufacturing, we consider the solid moulding problem, which is formulated from the optimization point of view in the design and manufacturing process of moulding technology. From the theoretical perspective, the solid moulding problem is also fundamental in visibility, one of the most classical topics in computational geometry. We present both the algorithmic results and the hardness proofs for the problems addressed in this dissertation, and the gap between the problem complexity and the algorithm complexity contained in our main results is nearly closed. In the aspect of combinatorics, we provide the tight combinatorial bounds. Our algorithms are efficient in practice. In terms of industrial management, we consider the time convex hull problem, which arises from path planning and further extensions of the shortest path problem, in the presence of high-speed transportation networks. For transportation business, to minimize the transportation time and cost is among the most important objectives. We explore shortest time-path planning and the generalization of convex hull into which the time-based concept is introduced. The main result is an optimal time algorithm for the problem under the general Lp metrics, in the presence of a straight-line highway. Our results in some sense have closed the study of this problem in the particular network topology. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/55544 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-103-1.pdf 目前未授權公開取用 | 2.05 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。