完全性路網TSP 問題啟發式解法之研究─兼論類神經網路解法之應用

Abstract

旅行推銷員問題(TSP) 是組合最佳化問題中最具代表性之一種，舉凡運輸上的車輛路 線問題 (VRP) 、儲運(Logostics)，或是工業工程上數值控制機(NC)的平板鑽孔、點 焊接順序等，皆可利用TSP 的觀含來求解。而TSP 問題數學規劃法求解時，不易求得 大型路網的TSP 最佳解，故一般皆採行求取近似解的啟發式(Heuristic) 解法。 本研究考慮完全性路網(Complete graph)，並採用結合起始解求解(Tour constructi on) 與起始解改進(Tour improvement)兩種程序的綜合法，作為啟發式解法的方法架 構，並選擇數種啟發式解法作實征上的分析比較。在啟發式解法的執行方式上，本研 究僅探討1 次執行與n 次執行兩種方式。 在6 組不同規模的36個演算實例上求解結果顯示，2－opt、3－opt改進法在路網規模 愈大時，改進效果愈卓著，一般而言以最遠內插法加上3－opt改進法結果較佳。而1 次結果大多不起出n 次執行最優解4%，若考慮時間效率則以1 次執行為佳。 類神經網路普遍用在圖形辨識(Image Recognition) 與語音(Speech)處理，而其在組 合最佳化問題上的應用，目前文獻所及僅有TSP 問題。本研究以Bermard 演算法作實 證上的嘗試，求解結果略遜於應用3－opt改進的綜合啟發法，但在大型路網TSP 求解 上，類神經網路方法仍相當具有潛力。