應用改良式粒子群演算法於旅行銷售員問題

10.6451/JETE.201109.0533

莊凱智；黃士滔

旅行銷售員問題 ； 粒子群演算法 ； 基因演算法 ； 改良式粒子群演算法

工程科技與教育學刊

8卷3期（2011 / 09 / 01）

533 - 546

繁體中文

旅行銷售員問題(Traveling Salesman Problem, TSP)以往用傳統整數規劃求解時常遇到問題規模愈大其求解時間呈指數成長，求解時間長且毫無效率的情況。本研究以粒子群演算法(Particle swarm optimization, PSO)爲基礎，尋找出可接受的可行解路徑，再以基因演算法(Genetic algorithm, GA)作爲粒子變異的方法，替換城市的順序。對於演算法的效能分析，本研究則利用多個國際標竿例題來測試，並以改良式粒子群演算法、粒子群結合蟻群演算法和改良的最大最小螞蟻系統(Modified max-min ant system, MMMAS)來做比較，在bier127、kroB200和pr1002三種國際標竿問題下，結果皆顯示改良式粒子群演算法求解的品質較佳。