基于PSO-GA混合算法的時間優(yōu)化的旅行商問題的研究.pdf

1、為了給游客提供更好的路徑推送服務，針對經(jīng)典的旅行商問題(TSP，TravelingSalesman Problem)進行了延伸研究，提出了一種時間優(yōu)化的旅行商問題(TOTSP，Time Optimal TSP)，旨在尋找一條旅行時間最短的游覽路徑。該路徑推送給游客從而節(jié)省游客在景區(qū)內進行游玩的旅行時間。通過混合粒子群遺傳算法(PSO-GA，Particle Swarm Optimization-Genetic Algorithm)對提出

2、的問題進行仿真實驗，并將旅行時間作為PSO-GA的目標函數(shù)，其中的旅行時間包括三個部分:游客從一個景點走向另一個景點所行走的總時間、游客在每個景點排隊等待的總時間以及游客在每個點進行游覽所需要的總時間。本研究將PSO-GA求出的最短旅行時間及所需的CPU執(zhí)行時間同遺傳算法GA以及蟻群算法(ACO，Ant ColonyOptimization)求出的結果進行了對比。仿真實驗表明PSO-GA在解決提出的TOTSP問題上具有較好的性能。

3、>　　本文研究的是時間優(yōu)化的旅行商問題，文中將對TOTSP問題求解得到的路徑稱為時間優(yōu)化的路徑(TOP，Time Optimal Path)，對TSP問題求解得到的路徑稱為長度優(yōu)化的路徑(LOP，Length Optimal Path)。本論文的主要研究工作可以總結為以下幾點:
　　(1)提出TSP問題的一種擴展問題:TOTSP問題，并對其概念和數(shù)學模型進行介紹，將游客的行走、排隊和游玩等因素融入到該模型中;
　　(2)利用