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

張成龍

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

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

張成龍

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

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

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

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

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

1 城市旅游路線模型描述

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

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

則其目標函數為

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

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

粒子群算法(ParticleSwarm Optimization,PSO)[5-6]，1995 年由 Russell Eberhart博士和 James Kennedy博士提出，多年以來經過數學、物理學、生物學、心理學等諸多領域專家的研究與改進，現今廣泛應用于求解各類工業(yè)、經濟和社會等實際應用中需要優(yōu)化的多目標問題、約束問題、動態(tài)問題，具有參數少，簡單易于理解實現等特點。

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

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

圖1 粒子群算法流程

3 實驗仿真

3.1 實驗環(huán)境

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

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

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

4 結論

圖2 城市旅游路線距離值

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

本文針對城市內旅游景點眾多，交通路線復雜，為能夠對外來游客提供更為優(yōu)質的服務，降低出行成本，節(jié)約出行時間，基于經典的旅行商問題，提出一種城市旅游路線模型，并利用粒子群算法進行模型的求解與路徑規(guī)劃，通過MATLAB仿真驗證，本文提出模型具有一定的實際應用價值，能夠有效的規(guī)劃游客出行路線，為游客提供便利。

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

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

[3]孫凱,吳紅星,王浩,等.蟻群與粒子群混合算法求解TSP問題[J].計算機工程與應用,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—)，男，山東棗莊人，碩士，主要研究方向為無線傳感器網絡、多源數據融合與集成。