張成龍

(茅臺學(xué)院 釀酒工程自動化系，貴州 遵義 564500)

基于粒子群算法的城市旅游路線優(yōu)化研究

張成龍

(茅臺學(xué)院 釀酒工程自動化系，貴州 遵義 564500)

針對城市內(nèi)旅游景點眾多，游客出行路線復(fù)雜等問題，提出一種基于經(jīng)典旅行商問題的城市旅游路線模型，并利用粒子群算法對該模型進(jìn)行求解優(yōu)化，最后利用MATLAB進(jìn)行仿真實驗，實驗結(jié)果表明，粒子群算法能夠有效實現(xiàn)城市旅游路線的優(yōu)化，降低游客城市旅行的出行成本，節(jié)約游玩時間。

粒子群算法；路徑優(yōu)化；旅行商問題

“互聯(lián)網(wǎng)＋旅游”戰(zhàn)略的提出，越來越多的景點開始響應(yīng)這一發(fā)展戰(zhàn)略，不斷完善景區(qū)的基礎(chǔ)設(shè)施建設(shè)，為游客提供更為優(yōu)質(zhì)的服務(wù)，從而吸引了大量國內(nèi)外游客。但是城市內(nèi)旅游景點眾多，交通路線復(fù)雜，為降低游客出行成本，節(jié)約出行時間，有必要對出行路線進(jìn)行規(guī)劃。

城市旅游路線優(yōu)化問題可以看作經(jīng)典的旅行商問題(Traveling Salesman Problem,TSP)，目前用來求解TSP問題的方法主要有遺傳算法[1]、模擬退火算法[2]、蟻群算法[3]、粒子群算法[4]等群體智能優(yōu)化算法。其中粒子群算法具有種群搜索能力強、運算效率高等特點，成為了近年來求解TSP問題的一個常用方法，因此本文采用粒子群算法進(jìn)行城市旅游路線模型求解優(yōu)化。

1 城市旅游路線模型描述

因為經(jīng)典旅行商問題有如下定義：給定一系列城市和兩兩城市之間的距離，求解訪問每一座城市一次并回到起始城市的最短回路。所以我們可以將經(jīng)典旅行商問題中的城市看作旅游景點，定義城市旅游路線模型如下：

首先將某城市內(nèi)各旅游景點之間構(gòu)成的網(wǎng)絡(luò)圖轉(zhuǎn)換為帶權(quán)完全無向圖。按照圖論思想描述為：G=(V,A)，V表示為圖中結(jié)點的集合，一個結(jié)點代表城市內(nèi)的某個旅游景點，A表示圖中弧的集合，已知各結(jié)點間的連接距離，找一個權(quán)值最小的Hamilton回路。即遍歷所有頂點一次且僅一次的最短回路，設(shè) dij為城市內(nèi)旅游景點 i與 j之間的距離，即弧(i,j)長度，引入決策變量：

則其目標(biāo)函數(shù)為

TSP問題模型雖然簡單，但是由于該問題的可行解是所有頂點的全排列組合，且隨著頂點數(shù)的增加，易產(chǎn)生組合爆炸，導(dǎo)致求解困難，因此本文選擇采取粒子群算法進(jìn)行TSP問題求解。

2 基本粒子群優(yōu)化

粒子群算法(ParticleSwarm Optimization,PSO)[5-6]，1995 年由 Russell Eberhart博士和 James Kennedy博士提出，多年以來經(jīng)過數(shù)學(xué)、物理學(xué)、生物學(xué)、心理學(xué)等諸多領(lǐng)域?qū)＜业难芯颗c改進(jìn)，現(xiàn)今廣泛應(yīng)用于求解各類工業(yè)、經(jīng)濟(jì)和社會等實際應(yīng)用中需要優(yōu)化的多目標(biāo)問題、約束問題、動態(tài)問題，具有參數(shù)少，簡單易于理解實現(xiàn)等特點。

粒子群算法作為一種隨機優(yōu)化方法，將待優(yōu)化問題潛在解描述為在D維空間內(nèi)以一定的速度“飛行”且沒有質(zhì)量和體積的粒子。其數(shù)學(xué)模型定義為：假設(shè)粒子群中粒子數(shù)量為N，搜索空間維數(shù)為D，那么粒子的空間坐標(biāo)位置向量表示為xi=(xi1,xi2,…,xiD)，粒子的速度向量表示為vi=(vi1,vi2,…,viD)，單個粒子尋優(yōu)過程中其個體最優(yōu)位置表示為Pi=(Pi1,Pi2,…,PiD)，粒子群中最佳位置表示為Pg=(Pg1,Pg2,…,PgD)。粒子的當(dāng)前位置優(yōu)劣由適應(yīng)度函數(shù)評價，在粒子群迭代進(jìn)化過程中，通過粒子的位置和速度更新公式進(jìn)行空間搜索尋得的最優(yōu)位置，其中速度和位置更新公式為[7]：

式中，i=1,2,…,N；ω為慣性權(quán)重系數(shù)；r1和r2是獨立隨機變量，服從(0,1)均勻分布；h1和h2是學(xué)習(xí)因子，且為非負(fù)常數(shù)；vi∈[-vmax,vmax]，vmax是約束速度的常數(shù)，由用戶根據(jù)具體問題設(shè)定。粒子群算法基本流程如圖1所示。

圖1 粒子群算法流程

3 實驗仿真

3.1 實驗環(huán)境

為進(jìn)行城市旅游路線模型驗證求解，選取實驗平臺為Win10/MATLAB(R2010b)，計算機配置為：Intel(R)Core(TM)i3-3240 CPU@3.40GHz，4.00GB RAM，64位操作系統(tǒng)，設(shè)計了基于Matlab的仿真程序。

為模擬某城市內(nèi)旅游景點的布局情況，設(shè)定城市內(nèi)10個旅游景點坐標(biāo)如表1所示，粒子群算法運算過程中的城市旅游路線距離值變化如圖2所示，由運算結(jié)果可知，粒子群算法運行至200代已經(jīng)收斂得到全局最優(yōu)解。同時得出粒子群算法優(yōu)化后的城市旅游路徑如圖3所示，根據(jù)圖3得出最終該城市旅游路線為景點1→景點4→景點5→景點6→景點7→景點8→景點9→景點10→景點2→景點3，最優(yōu)總里程數(shù)為269.0671 km。

表1 城市景點位置坐標(biāo)(單位：km)

4 結(jié)論

圖2 城市旅游路線距離值

圖3 粒子群算法規(guī)劃路徑

本文針對城市內(nèi)旅游景點眾多，交通路線復(fù)雜，為能夠?qū)ν鈦碛慰吞峁└鼮閮?yōu)質(zhì)的服務(wù)，降低出行成本，節(jié)約出行時間，基于經(jīng)典的旅行商問題，提出一種城市旅游路線模型，并利用粒子群算法進(jìn)行模型的求解與路徑規(guī)劃，通過MATLAB仿真驗證，本文提出模型具有一定的實際應(yīng)用價值，能夠有效的規(guī)劃游客出行路線，為游客提供便利。

[1]沈繼紅,王侃.求解旅行商問題的混合粒子群優(yōu)化算法[J].智能系統(tǒng)學(xué)報,2012(2):174-182.

[2]易正俊,李勇霞,易校石.自適應(yīng)蟻群算法求解最短路徑和TSP問題[J].計算機技術(shù)與發(fā)展,2016,(12):1-5.

[3]孫凱,吳紅星,王浩,等.蟻群與粒子群混合算法求解TSP問題[J].計算機工程與應(yīng)用,2012,48(34):60-63.

[4]Li Y,Jiao L,Shang R,et al.Dynamic-context cooperative quantum-behaved particle swarm optimization Based on mul?tilevel thresholding applied to medical image segmentation[J].Information Sciences,2015,294：408-422.

[5]Kennedy J,Eberhart R.Particle swarm optimization[C]//Neu?ral Networks,1995.Proceedings.,IEEE International Confer?ence on.IEEE,1995,4：1942-1948.

[6]Eberhart R C,Kennedy J.A new optimizer using particle swarm theory[C]//Proceedings of the sixth international sympo?sium on micro machine and human science.1995,1：39-43.

[7]Shi Y,Eberhart R.A modified particle swarm optimizer[C]//Evolutionary Computation Proceedings,1998.IEEE World

TP301

A

1672-7517(2017)08-0040-02

2017-07-15

2017-08-25

張成龍(1992—)，男，山東棗莊人，碩士，主要研究方向為無線傳感器網(wǎng)絡(luò)、多源數(shù)據(jù)融合與集成。