頁籤選單縮合
題名 | 旅行推銷員問題之啟發式解法=A Heuristic Algorithm for Traveling Salesman Problems |
---|---|
作者 | 郭人介; 郭幸民; 蘇鈺玲; Kuo, R. J.; Kuo, S. M.; Sue, Y. L.; |
期刊 | 臺北科技大學學報 |
出版日期 | 20000300 |
卷期 | 33:1 2000.03[民89.03] |
頁次 | 頁119-149 |
分類號 | 494.542 |
語文 | chi |
關鍵詞 | 旅行推銷員問題; 車輛路線規劃; 啟發式解法; 物流中心規劃; Traveling salesman problem; Vehicle routing problem; Heuristic; Distribution center planning; |
中文摘要 | 旅行推銷員問題之複雜度屬於NP-hard問題,國內外相關研究多以啟發式解法求 取近似解,但求解品質及速度往往無法兼顧。因此,本研究擬發展一績效良好且速度合理的 啟發式解法,以提供物流業者做為運輸路線規劃之依據。本研究發展的TSP啟發式解法 Modified I3法為三階段之綜合法,第一階段修正原I3第一階段,以構建較佳的初始子路 線;第二階段引用GENIUS 法以路線上數個鄰點進行插入之概念,發展出較簡單的解繫改善 法。本研究於基本配備之486個人電腦,以Turbo C程式發展Modified I3法,其執行速度 合乎實際應用之要求。並從文獻及TSPLIB題庫中選擇30題例題,與原I3法進行解值之比較, 得到10題例題之結果優於或相近於原I3法,其中3題成本低於原I3法2.5%以上,且最佳的情 況則有1題之最小成本誤差百分比僅為0.4%。觀察本演算法解結果良好之例題特性,發現其 點的分佈呈符合實際狀況的聚落分佈情形;而求解不佳之例題,點的分佈與可能的地狀況相 差甚多。 |
英文摘要 | This research develops a three-stage TSP heuristic called Modified I3. The first stage constructs an initial subtour which contains substantially more vertices than the original I3 method. The second stage, a simplification of the GENIUS heuristic, inserts the remaining vertices into the subtour. The third stage, also a simplification of the GENIUS heuristic, adjusts and improves the complete tour. A Turbo C program is developed to evaluate the performance of Modified I3 using 30 test problems selected from the literature and the TSPLIB library. Modified I3 performs close to or better than I3 in 10 test problems and executes much faster than I3. Examining the characteristics of test problems reveals that Modified I3 yields more accurate solutions when the distribution of vertices is close to actual geographical situations. |
本系統之摘要資訊系依該期刊論文摘要之資訊為主。