啟發式解法在不同節點空間分布下對旅行推銷員問題適用性之研究

Abstract

一般之車輛路線問題（vehicle routing problem） 在求解的時候，多假設運輪需求 點之分布為均勻分配(uniform distribution） ，以簡化空間分布之影響。事實上， 空間分布不限于均勻分配一種。本研究即以Ripley演算法產生各種隨參數調整之空間 分布形態（pattern） ，作為假想之運輸需求分布點，透過車輛路線問題中之TSP（ traveling salesman problem）之啟發式解法為分析工具，計算其旅行長度，以探討 不同空間分布形態對旅行長度之影響，並對各啟發式解法之效率作一比較。結果發現 分布形態之集中或分散程度對旅行長度有影響，且在所觀察之需求點數下，各啟發式 解法之優劣順序並不因分布形態之不同而有明顯之變化。