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

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

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

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