臺灣博碩士論文加值系統

　　為了因應新型業態興起而產生的物流中心，在商品流通的過程中，扮演整合商流、物流、金流與資訊流等機能的角色，是商業邁向殃代化的整合體，其為滿足客戶的配送需求及追求合理的運輸成本，必須有適量配送人員、車輛與最佳配送路線的決策，因此此類問題為重要的研究課題。而由於路線規畫問題之複雜度屬於NP-hard問題，國內外相關研究多以啟發式解法求取近似解，但求解品質及速度往往無法兼顧，故本研究期望發展一績效良好且速度合理的啟發式解法。
　　本研究發展的TSP啟發式解法Modified I3法為三階段之綜合法，第一階段修正原I3法第一階段，以構建具體的子路線；第二階段引用GENIUS法以路線上數個鄰點進行插入概念，發展出較簡單的鄰點插入法；第三階段引用GENIUS法解繫改善之概念，發展出較簡單的解繫改善法。本研究於基本配備之486個人電腦，以Turbo C程式發展Modified I3法，其執行速度合乎實際應用之要求。並從文獻及TSPLIB題庫中選擇30題例題，與原I3法進行解值之比較，得到10題例題之結果優於或相近於原I3法，其中3題成本低於原I3法2.5%以上，且最佳情況則有1題之最小成本誤差百分比僅為0.4%。觀察本演算法求解結果良好之例題特性，發現其點的分佈呈符合實際狀況的聚落分佈情形；而求解不佳之例題，點的分佈與可能的狀況相差甚多。
　　本研究的Modified I3法應用於以空間涵蓋曲線法進行分群，再建立路線的車輛路線規畫上，一共執行了TSPLIB題庫中7題例題，與其他VRP法進行解值之比較，雖然有1題之結果優於其他方法，但是未來欲改善解之精確度，則有賴TSP與VRP之求解方法的創新與修正。

　　This thesis develops a three-stage TSP heuristic called Modified I3. The first stage constructs an initial subtour which contains substantially more vertives 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.
　　This thesis also applys Modified I3, together with the Spacefilling Curve clustering algorithm, to solve the VRP problem. 7 test problems are selected from the TSPLIB library. Modified I3 and SFC performs better than other VRP heuristis in 1 test problem. The future research direction is to revise the clustering algorithm in order to improve the overall performance.