李夢(mèng)丹

摘要：隨著人民需求的日益增長(zhǎng)，出外旅游成了生活的一部分。但是如何規(guī)劃旅游線路節(jié)省時(shí)間使路徑最短是論文考慮的問(wèn)題。文章利用matlab軟件通過(guò)蟻群算法對(duì)西安著名的16個(gè)景點(diǎn)進(jìn)行了路徑規(guī)劃，實(shí)例證明，蟻群算法在解決路徑優(yōu)化這類問(wèn)題是相對(duì)有效的。

Abstract： With the increasing demand of the people， traveling abroad has become a part of life. But how to plan the travel route to save time and make the route shortest is the issue considered by the thesis. The article uses matlab software to carry out path planning on 16 famous scenic spots in Xi'an through ant colony algorithm. The example proves that the ant colony algorithm is relatively effective in solving such problems as path optimization.

關(guān)鍵詞：蟻群算法;最優(yōu)路徑;matlab軟件

Key words： ant colony algorithm;optimal path;matlab software

中圖分類號(hào)：F252? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)：1006-4311（2020

0? 引言

隨著科技的發(fā)展，互聯(lián)網(wǎng)技術(shù)使得網(wǎng)上訂酒店車票非常方便，利用各類app進(jìn)行查詢旅游景點(diǎn)相當(dāng)方便，所以隨著生活水平的提高，自助游將會(huì)越來(lái)越受到人們追捧。人們會(huì)根據(jù)出行的時(shí)間合理的規(guī)劃旅游行程，選擇合適的景點(diǎn)個(gè)數(shù)，但是實(shí)際出行中，還會(huì)伴隨其他問(wèn)題的產(chǎn)生，例如旅游路找的規(guī)劃、旅游費(fèi)用等，這個(gè)時(shí)候需要合理的方法解決這個(gè)問(wèn)題。許多學(xué)者對(duì)這個(gè)問(wèn)題進(jìn)行研究，最早源于TSP旅行商問(wèn)題[1]，隨后對(duì)該問(wèn)題的算法進(jìn)行深入研究，解決這類問(wèn)題常用的方法有蟻群、粒子群、遺傳算法等等。論文結(jié)合蟻群算法，對(duì)陜西省著名旅游景點(diǎn)進(jìn)行路徑規(guī)劃，蟻群算法可以為我們提供最佳的旅游順序。

1? 算法介紹

蟻群算法（Ant Colony Optimization，ACO）于1992年由Marco Dorigo提出，來(lái)源于實(shí)際生活中螞蟻尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為，最早用來(lái)解決旅行商問(wèn)題[2]。

如圖1所示，有兩條路線，ABD和ACD，其中ABD是一條直線，ACD是一條曲線，ACD長(zhǎng)度是ABD長(zhǎng)度的兩倍，C點(diǎn)是曲線ACD的中點(diǎn)。假設(shè)有兩只螞蟻分別為a、b，螞蟻a采取ABD路線，而螞蟻b采取ACD路線。同時(shí)從A地出發(fā)趕往D然后再回A地。當(dāng)a到達(dá)D時(shí)，b正好到達(dá)C，當(dāng)a從D回到A時(shí)，b正好到達(dá)D。此時(shí)殘留在ABD途徑中的激素是ACD途徑中的激素的兩倍[3]。

算法相關(guān)規(guī)則主要包括兩種：

①路徑轉(zhuǎn)移規(guī)則。

開始狀態(tài)，每只螞蟻被隨機(jī)放到其中的一個(gè)城市上，第k只螞蟻在t時(shí)刻從城市i到城市j的轉(zhuǎn)移概率為：

式（1）中，τij（t）表示t時(shí)刻路段（i，j）戶上的信息素的量，在初始時(shí)刻各條路徑上的信息量相等，即τij（0）=常數(shù)，nij（t）為啟發(fā)函數(shù)，nij（t）=■。dij表示路段（i，j）的長(zhǎng)度。allowedk表示螞蟻可選擇的節(jié)點(diǎn)集，α表示軌跡相對(duì)重要性的信息啟發(fā)因子，β表示能見度相對(duì)重要性的期望啟發(fā)因子。

②軌跡更新規(guī)則。

在迭代過(guò)程中，螞蟻需要使用本地更新規(guī)則在移動(dòng)的每個(gè)步驟中更新相應(yīng)路徑上的信息素濃度，更新規(guī)則如式（2）所示：

式（2）中ρ表示信息索揮發(fā)系數(shù)，且ρ的取值范圍為ρ∈（0，1），由于信息素更新策略的不同，全局搜索能使我們得到更好的解決方案，因此采用如式（3）所示的全局信息索更新規(guī)則：

式（3）中，Q表示螞蟻循環(huán)一周時(shí)在一定程度積累的信息素總量Lk表示本次循環(huán)中，螞蟻k所走路段的長(zhǎng)度[4]。

2? 實(shí)例驗(yàn)證

2.1 實(shí)例介紹

陜西省是一個(gè)具有濃厚歷史韻味和人文特色的著名旅游城市，論文選取陜西省16個(gè)著名景點(diǎn)作為分析對(duì)象，其中包含自然景觀、歷史遺址、現(xiàn)代建筑等等相對(duì)具有代表性的旅游景點(diǎn)。其中包含秦始皇陵及兵馬俑、華清池、大雁塔、唐長(zhǎng)安城大明宮遺址、城墻永寧門、鐘鼓樓、回民街、小雁塔、大唐芙蓉園、陜西歷史博物館、西安世博園、白鹿原、西交大（曲江）、西工大、馬嵬驛、華山等16個(gè)景點(diǎn)。這些景點(diǎn)有些分布陜西省城區(qū)，有些分布在西安市內(nèi)，分布不一，如果沒有做好規(guī)劃，會(huì)造成路線的重復(fù)，這樣既浪費(fèi)時(shí)間，又增大成本，因此應(yīng)重點(diǎn)對(duì)旅游的順序進(jìn)行一個(gè)簡(jiǎn)單的排序，論文以距離最小化為求解目標(biāo)，展開西安旅游景點(diǎn)的路徑規(guī)劃。

景點(diǎn)坐標(biāo)如表1所示。

2.2 matlab結(jié)果分析

文章所表示的距離，是用地理坐標(biāo)直接計(jì)算，換算為實(shí)際距離需乘以地球半徑，這里簡(jiǎn)單處理，得出旅游順序即可。通過(guò)matlab結(jié)合蟻群算法，對(duì)旅游路線進(jìn)行規(guī)劃迭代。

將表中的數(shù)據(jù)寫成的矩陣形式導(dǎo)入到MATLAB中，蟻群算法中種群數(shù)量設(shè)置與城市的個(gè)數(shù)相對(duì)應(yīng)為16。根據(jù)若干次MATLAB仿真試驗(yàn)結(jié)果對(duì)蟻群算法的其他參數(shù)進(jìn)行設(shè)定：激素重要程度參數(shù)設(shè)置為1，啟發(fā)因子重要程度參數(shù)設(shè)置為5，激素蒸發(fā)系數(shù)設(shè)置為0.1，激素增強(qiáng)系數(shù)為100，最大迭代的次數(shù)設(shè)置為200，利用同樣的參數(shù)和程序?qū)ξ靼彩新糜尉包c(diǎn)進(jìn)行多次MATLAB仿真計(jì)算。最優(yōu)結(jié)果如圖2所示。

最短距離：3.7215（地球半徑）

最短路徑順序：7—4—6—5—10—3—8—9—13—11—2—1—16—12—14—15—7

3? 結(jié)束語(yǔ)

路徑優(yōu)化是實(shí)際中一個(gè)很常見的問(wèn)題，在生產(chǎn)調(diào)度，資源優(yōu)化等等問(wèn)題中都有較多的應(yīng)用，而論文對(duì)旅游線路的規(guī)劃也具有一定的實(shí)際意義。通過(guò)多次調(diào)整，最終實(shí)現(xiàn)路徑最短，迭代最快，達(dá)到我們所要實(shí)現(xiàn)的目標(biāo)。但是論文對(duì)于實(shí)際中的費(fèi)用等因素沒做考慮，今后的研究應(yīng)重點(diǎn)針對(duì)實(shí)際影響因素，這樣蟻群算法可以更好地解決實(shí)際問(wèn)題。

參考文獻(xiàn)：

[1]鄒臘英.基于TSP問(wèn)題的旅游路線安排[J].蘭州文理學(xué)院學(xué)報(bào)（自然科學(xué)版），2015，29（05）：23-25.

[2]肖艷秋，焦建強(qiáng)，喬?hào)|平，杜江恒，周坤.蟻群算法的基本原理及應(yīng)用綜述[J].輕工科技，2018，34（03）：69-72.

[3]開吉，楊金云，蔣其岑，王玉琴，開晶晶.基于蟻群算法的物流配送路徑的研究[J].物流工程與管理，2018，40（02）：74-76.

[4]萬(wàn)慧云，蔣艷.基于蟻群算法的5A景點(diǎn)旅游路線規(guī)劃問(wèn)題研究[J].軟件導(dǎo)刊，2019，18（04）：141-144.