網路線性之最短路徑問題

The Shortest Path Problems for Linear Network

卓哲強(Jhe-chiang Jhuo)

指導教授 ： 黃俊平

國立虎尾科技大學/管理學院/工業工程與管理研究所/碩士(2006年)

https://doi.org/10.6827/NFU.2006.00005

摘要

許多系統的架構與配置儼然就是在一個有限空間的圖網問題，過去最短路徑相關問題往往僅限於節點之間的關係探討，本文將以多條直線線性底下，對於直線相交求得之各交點所呈現出來的凸多邊形幾何圖形裡，內部行經接觸直線相交軌跡的最短路徑問題作一番研究，本文以兩種特殊圖網演算法來作一番的演算驗證與問題探討，由於不同系統的圖網問題，會因為本身的限制關係，其所求得之結果也會有所差異，結合了既有傳統的旅行者銷售員問題（TSP）與最小伸展樹（MST）的概念，並加入幾何學中費馬點定理應用，來判定凸n邊形共用頂點之規則，依照偶數邊與奇數邊的差異，分別予以不同驗算求解，進而來求得費馬點內接凸多邊形各頂點之特殊的geometric Steiner tree。最後以各邊內接最小周長之多邊形、各節點內接最小周長之多邊形之實例計算與各節點內接特殊的geometric Steiner tree，根據不同邊的差異，進行分類討論與七邊形實例結果比較分析，並於假定問題中得到一組最佳geometric Steiner tree。

關鍵字

圖網問題 ； 最短路徑問題 ； 凸多邊形 ； TSP ； MST

並列摘要

The essence of this research is to investigate two shortest path problems inside a convex polygon. The first one is to find the shortest cycle connecting all the edges of the convex polygon. This problem is a special type of TSP. The major different between this problem and the traditional TSP is that the nodes to be connected in this problem are not fixed points but are located somewhere along the corresponding edges. The second problem is to find the minimum spanning tree to link all the vertices of the convex polygon. It is an Euclidean Steiner tree problem. An algorithm based on Fermat’s point is established to solve this problem. Both problems solved in this research have wide application in industrial network system. The extension of the developed methods into non-convex polygon is a good area worthy of further sturdy.

並列關鍵字

The Shortest Path Problem ； The Convex Hull ； Traveling Salesman Problem ； Minimal Spanning Tree Problem

參考文獻

[7]許晉嘉，2003，宅配業貨物配送路線規劃問題之研究，國立成功大學交通管理科學研究所碩士論文

[13]K. Nachtigall, and S. Voget, “A genetic algorithm approach to periodic railway synchronization”, Computers & Operations Research, Vol.23, Issue: 5, pp. 453-463, 1996.

[15]N. Koncz, J. Greenfeld, and K. Mouskos, “Strategy for Solving Static Multiple-optimal Path Transit Network Problems”, Journal of Transportation Engineering-ASCE, Vol.122, No. 3, pp. 218-225,1996.

[18]Francis J. Vasko , Robert S. Barbieri , Brian Q. Rieksts, Kenneth L. Reitmeyer, Kenneth L. Stott Jr. , “The cable trench problem: combining the shortest path and minimum spanning tree problems”, Computers & Operations Research Vol.29 441–458,2002.

[19]Patrice Perny, Olivier Spanjaard, “A preference-based approach to spanning trees and shortest paths problems”, European Journal of Operational Research Vol.162 584–601,2005.