單一支撐邊界下二維空間節點連結問題

Routing Problems of Two-Terminal Nets with a Single Boundary in a Two-Dimensional Space

鄭紹亨(Shao-Heng Cheng)

指導教授 ： 洪一勳

國立臺灣大學/工學院/工業工程學研究所/碩士(2022年)

https://doi.org/10.6342/NTU202201645

摘要

圖論之路徑問題研究求解可分為:啟發式演算法及最佳化模型兩種，於大範圍離散空間建構最佳化模型會使得空間使用上浪費及提高求解時間複雜度，而啟發式演算法則可能無法於可行區域求出最佳解。本研究依照該可行空間連續與否分別建構單一邊界路徑連線演算法及節點連接最佳化模型，針對二維連續空間建構路徑連線演算法，透過單一參考邊界盡可能縮小使用之可行空間，並修正各條路徑使其遵守凹口限制，爾後利用兩個案例驗證此演算可行性，並比較此研究與過去演算法結果差異。而對於小範圍離散二維空間則建構最短路徑最佳化模型，提出個別計算單一節點及合併計算多個節點兩種概念，爾後透過兩個案例驗證兩種概念模型可行性並比較其結果及所需運算時間。

關鍵字

路徑問題 ； 節點連接問題 ； 啟發式演算法 ； 最佳化模型

並列摘要

Routing problem approaches can be classified into two classes: optimization models and heuristic algorithms. An optimization model may take a long time to solve a larger discrete space problem, while, a heuristic algorithm may not obtain the best solution in the feasible region. In this study, we construct routing algorithms with a single boundary for a two-dimensional continuous space problem. The proposed heuristic algorithms aim to use less feasible space and to route the paths complying with the notch limit. In addition, we adopt two cases to demonstrate the effectiveness of the proposed heuristic algorithms. Regarding a small discrete two-dimensional space, we formulate optimization models with two concepts: calculation of a single node and calculation of multiple nodes. Finally, a case is investigated to verify the feasibility of the two proposed optimization models.

並列關鍵字

Routing problem ； Two-terminal nets routing problem ； Heuristic algorithms ； Optimization

參考文獻

Akgün, V., Erkut, E., Batta, R. (2000). On finding dissimilar paths. European Journal of Operational Research, 121(2), 232-246.

Cherkassky, B. V., Goldberg, A. V., Radzik, T. (1996). Shortest paths algorithms: Theory and experimental evaluation. Mathematical programming, 73(2), 129-174.

Chen, H. Y., Chang, Y. W. (2009). Global and detailed routing. In Electronic Design Automation (pp. 687-749). Morgan Kaufmann.

Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische mathematik, 1(1), 269-271.

Hart, P. E., Nilsson, N. J., Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2), 100-107.