利用基於群體智慧的最佳化演算法解決旅行推銷員問題， 以進行有效率的路徑規劃

Abstract

旅行推銷員問題（TSP）一直都是個具挑戰性的最佳化問題，促使人們發展各種方法去有效率地解決這個問題。本研究提出了一個改良基於群體智慧的最佳化演算法（Swarm Intelligence-based method）框架的最佳化演算法，並將這改良後的方法論與一些常規的最佳化演算法：基因演算法和蟻群演算法的最佳解和計算時間作比較。在有47 和50 個目的地的非對稱TSP 中，我們提出的方法在最佳解和計算時間方面表現均為最佳。為貼近實際應用，本研究利用了Google Maps API獲取路徑資料，並把結果視覺化，呈現在OpenStreetMap 的地圖上以供參考。

The Travelling Salesman Problem (TSP) has long been a challenging optimization puzzle, prompting the development of various methodologies to seek for efficient solutions. In this paper, we propose an improved optimization algorithm with the implementation of the Swarm Intelligence-based method (SIB). This improved method is compared to conventional optimization techniques, the Genetic Algorithm (GA) and the Ant Colony Optimization (ACO), in terms of solution quality and computational time. In asymmetric TSPs with 47 and 50 destinations, our proposed method has the best performance in terms of solution quality and computational time. To incorporate real world applications, route data are retrieved by using Google Maps API and the results are visualized on OpenStreetMap for reference.