滕 泉，沈景鳳，徐 斌，王瑋瑋

(1.上海理工大學 機械工程學院，上海200082;2上海材料研究所 減振技術事業(yè)部，上海 200082；3.大連海事大學 交通運輸管理學院，遼寧 大連 116026)

基于貪婪算法的旅游路線優(yōu)化問題

滕 泉1，沈景鳳1，徐 斌2，王瑋瑋3

(1.上海理工大學 機械工程學院，上海200082;2上海材料研究所 減振技術事業(yè)部，上海 200082；3.大連海事大學 交通運輸管理學院，遼寧 大連 116026)

針對目前國內旅游線路的設計多偏向于從景區(qū)特色出發(fā)，而較少從旅行時間和路徑入手的問題，利用貪婪算法設計數(shù)學模型。在旅行者不多于15天的旅行約束條件下，對國內201個5A風景區(qū)進行聚類分塊，將201個景區(qū)簡化為31個省市。算得從西安市出發(fā)到各省市的旅行時間并得到21條符合要求的旅行路線。將相關結果以更直觀的圖像形式展現(xiàn)，為旅行路線的設計研究提供了參考。

旅游線路；最優(yōu)化問題；聚類貪婪算法；約束條件

一個旅游區(qū)域內各個景點分布在不同的位置，對這些景點瀏覽的先后順序則有多種方式，可以組合成不同的旅游線路[1-2]。針對目前旅游業(yè)的路線設計成果不完善的情況，為了讓游客花費較少的時間而盡可能多地瀏覽景點，設計出最優(yōu)的旅游線路是必要的[3-4]。本文以西安市為例，運用貪婪算法，對旅游路線進行優(yōu)化，實驗對象為我國部分省市(港澳臺地區(qū)不含5A風景區(qū))200多個5A級風景區(qū)的旅游線路優(yōu)化，得到從西安出發(fā)到各地的最佳旅游線路，并得到線路圖。

1 線路背景

自2007年3月7日至2015年7月13日，全國旅游景區(qū)質量等級評定委員會分29批共批準了201家景區(qū)為國家5A級旅游景區(qū)。依據(jù)常規(guī)作息時間，設定一位自駕游愛好者擬按此景區(qū)名單制定旅游計劃。因時間限制該旅游愛好者每次旅游的時間不超過15天，確定出符合該游客的旅行線路，給出每一次旅游的具體行程。對游客的行車速度做如下參考：在高速公路上的行車平均速度為90 km/h，在普通公路上的行車平均速度為40 km/h。

2 問題分析

此問題中，旅行計劃需設計從西安出發(fā)到各省201個旅游景點的旅行計劃，因數(shù)據(jù)量太大，先對景點進行聚類分塊。根據(jù)201個5A級景點分屬于31個省份(港澳臺地區(qū)不含有5A景區(qū))，以各省會為中心，將201個景點分成31個省區(qū)組[5]。將原201個點簡化成31個，然后制定各省的旅行方案。旅行方案：先從西安出發(fā)到達各個省區(qū)的省會，再從此省省會出發(fā)遍歷該省所有景點，之后再去下一個省。

此問題的約束條件：每次出行不超過15天，可對問題做簡化處理，以15天為界限，設計n條旅行時長<15天旅行路線，再將此n條旅行線路組合使得所用旅行時間最短。

一般各個省的旅行總時間不會超過15天，分別計算各個省最短旅行時間。此步理解為TSP(旅行商問題)中確定最短時間、最優(yōu)路徑、最短路徑的問題，可查閱省內各景點的兩兩相對距離，建立矩陣，利用Lingo軟件編輯算法，計算出每個省區(qū)的旅行時間[6-8]。

3 貪婪算法對旅游路線優(yōu)化設計

在完成各省的時間計算后，利用貪婪算法，設計從西安出發(fā)到各省的旅行路線[9-10]。貪心策略為：(1)從西安出發(fā)，首先選擇其他30個省省會之一C0作為下一游覽??；(2)計算西安到該省會時間di0、在該省游玩的時間ti、以及該省返回西安的時間D，若上述時間之和<15天，再選擇離C0市最近的省會城市作為第二游覽省，依次選擇第三游覽省、第i游覽省，直到旅行時長大于15天，輸出第一條旅行線路；(3)將選過的省去除，再執(zhí)行第2步，直到游遍31個省區(qū)，依次輸出第2條、第3條、…、第n條線路；(4)計算以C0市作為第一游覽城市該路線需要的總時間；(5)將其他29個省的省會C1、C2、…、Ci作為第一游覽城市，計算路線總時間；(6)比較得出30種方法的最優(yōu)路線計劃。

3.1 名詞和符號說明

在運用貪婪算法進行旅游線路設計時的符號如表1所示。

表1 貪婪算法的符號說明

3.2 模型的基本假設

(1)不考慮高鐵和航班的推遲或取消，忽略天氣影響或不可預測的事故； (2)旅館處于非滿客狀態(tài)，即總可預訂到房間；(3)在時間的認識上，將當天早8點到次日的早8點定義為一天； (4)不考慮實際生活中出現(xiàn)的堵車等車等不可知現(xiàn)象。

4 模型建立及求解

根據(jù)此問題約束條件：每次出行不超過15天。做簡化處理，以15天為界，設計n條旅行時長<15天旅行路線，再將此n條旅行線路組合得最短時間路線。

旅行計劃需要設計從西安到201個旅游景點的旅行計劃，因數(shù)據(jù)量太大，先對景點進行聚類分塊，根據(jù)201個5A級景點分屬于31個省份，以各省省會為中心，將201個景點分成31個省區(qū)組。旅行方案為先從西安出發(fā)到達某省區(qū)的省會，再從該省省會出發(fā)遍歷該省所有景點，再去下一個省游玩。若到達某省后返回西安時間達到15天，則旅行終止，該行程為符合要求的一條線路[11-12]。將游玩過的城市去掉，執(zhí)行上述循環(huán)，直到游玩遍所有省區(qū)為止。

4.1 數(shù)據(jù)處理與聚類分塊

根據(jù)201個5A級景點分屬于31個省份，以各省省會為中心，將201個景點分成31個省區(qū)組(注：若A省內存在離B省城市更近的景點，則此景點劃入B省)。通過百度地圖，查找某省內景區(qū)間各景點所在城市兩兩之間的距離dij，列出矩陣，以河南省為例，如表2所示。

表2 河南省內主要旅游城市相對距離(數(shù)據(jù)來源：百度地圖2015-00-20)

4. 2 各省省內旅行最短時間的計算

一般各個省的旅行總時間不會超過15天，先分別計算各個省最短旅行時間。從某省的省會城市出發(fā)，依次走完這個省的所有景區(qū)，然后回到省會城市，形成一閉合環(huán)路。欲求走完此環(huán)路所用時間最短，即求此環(huán)路的路程最短。此問題即TSP中確定最短時間、最優(yōu)路徑、最短路徑的問題[13]。數(shù)學模型如下：

圖1 河南省旅行示意圖

查閱相關數(shù)據(jù)，以此方法，分別求得31個省內路線，并計算游完每個省所用的時間T(T與最后規(guī)劃時間前后誤差≤0.5天)，如表3所示。

表3 各省份區(qū)遍歷所有景點所需要的時間

5 啟發(fā)式算法制定全國最短路線

在完成各省旅行時間計算之后，將全國201個5A級景區(qū)簡化為31個點，從西安出發(fā)向外輻射設計線路。此步利用貪婪算法設計從西安出發(fā)到各省的旅行路線[14]。貪心策略為：

(1)從西安出發(fā)，首先選擇其他30個省省會之一C1作為下一游覽省；

(2)計算西安到該省會時間di0、在該省游玩的時間ti、以及該省返回西安的時間D，若上述時間之和<15天，再選擇離C1市最近的省會城市作為第二游覽省，依次選擇第三游覽省、第i游覽省，直到旅行時長>15天，輸出第一條旅行線路；

(3)將選過的省去除，再執(zhí)行第2步，直到游遍31個省區(qū)，依次輸出第2條、第3條、…、第n條線路；

(4)計算將C1市作為第一游覽城市該路線需要的總時間；

(5)將其他29個省C2、C3、…、Ci作為第一游覽城市，計算路線總時間。

比較得出30種方法的最優(yōu)路線計劃。尋找最優(yōu)路徑的算法為：

(1)統(tǒng)計建立全國各個城市兩兩之間相互時間里程表，形成一個C31×C31的矩陣，建立數(shù)據(jù)庫；

(2)以西安為起點，從其他30個省會城市里任選一個城市作為C0，在C0省游玩的時間為t0，求C0距西安的車程時間為D，消耗時間為T=D+t0；

(3)以第一游覽城市C0為起點，篩選距離西安車程最近的省會城市Ci，記Ci與C0的車程時間為di0，在Ci省游玩的時間為ti，總消耗時間為T=D+t0+di0+ti；

(4)以Ci省的省會城市為起點，重復第一步的過程，篩選距離Ci車程最近的省會城市Cj，記Cj與Ci的距離車程為dji，在Cj省游玩的時間為tj，總游玩時間T=D+t0+di0+ti+dji+tj；

(5)如果T<=15，執(zhí)行上述循環(huán)結構，如果T>15，算法終止，記錄算法終止的前n次計算經(jīng)過的城市Ci，Cj……Cn，打印“西安—Ci—Cj……Cn”作為第一條旅游路線；

(6)將Ci，Cj，…，Cn從數(shù)據(jù)庫中剔除，形成一個C31-n×C31-n的矩陣，形成新的數(shù)據(jù)庫；

(7)在C31-n×C31-n的矩陣的數(shù)據(jù)庫中，繼續(xù)執(zhí)行上述(1)～(5)步，繼續(xù)打印，形成第2,3,4,…,i條旅游路線；

(8)當數(shù)據(jù)庫中全部城市被讀取，形成一個C0×C0的矩陣時，算法終止，統(tǒng)計記錄下全部1，2，3，…，n條線路。計算這些線路總的要花的時間；

(9)依次將其他30個城市作為以第一游覽城市C0執(zhí)行上述過程，求出30條方案，比較他們消耗的時間，選出最優(yōu)解。

利用計算機編程，實現(xiàn)該算法的求解，得到問題的一個較優(yōu)解。分析并調試的此解一共得到21條路線，如表4所示。

表4 21條旅游路線

根據(jù)各省份的線路，繪制直觀圖像如圖1所示。

圖1 西安到各省份的旅游線路圖

分析上表，此路線結果中：從西安出發(fā)到全國各省的旅游線路天數(shù)<10天的有3條，天數(shù)>10天且<15天的有19條。

6 結束語

隨著旅游業(yè)的發(fā)展，設計出合理完善的旅游路線不但有利于我國旅游業(yè)的發(fā)展，而且有利于游客和旅游社在旅行過程中節(jié)約時間和費用成本。然而現(xiàn)階段的旅行線路設計多偏重于景區(qū)的特色搭配，很少從優(yōu)化旅行的時間和距離入手[15-16]。鑒于此情況，本文運用貪婪算法對旅游路線進行設計，根據(jù)游客的時間需求，設計出滿足游客需求的旅游線路，對西安市的旅游愛好者出行旅游起到一定的參考作用。本文在采用貪婪算法進行旅游線路優(yōu)化過程中，模型將201個景區(qū)劃分為31個省，實際問題進行了一定的簡化，導致模型與事實存在一定的偏差，許多方面還有待完善。期望在以后的研究中有更完善的成果，使用該方法規(guī)劃的旅游線路能夠具有一定的方便性，比且和實際能緊密結合，讓這一理論在旅游規(guī)劃方面能夠擴展開來，更好的用于實際中。

[1] Denstadli J M, Jacobsen J K S.The long and winding roads:perceived quality of scenic tourism routes[J].Tourism Management,2011,32(4):780-789.

[2] Briedenhann J,Wickens E.Tourism routes as a tool for the economic development of rural areas—vibrant hope or impossible dream?[J].Tourism Management,2004,25(1):71-79.

[3] 楚義芳.關于旅游線路設計的初步研究[J].旅游學刊,1992(2):9-13.

[4] 安賀新.體驗經(jīng)濟時代旅游業(yè)發(fā)展模式研究[J].經(jīng)濟研究參考,2011(17):61-63.

[5] 楊冠軍.基于混合聚類的大本體分塊映射及評價方法研究[D].長沙:中南大學,2009.

[6] 周康,強小利,同小軍,等.求解TSP算法[J].計算機工程與應用,2007,43(29):43-47.

[7] 唐曉云,趙黎明,秦彬.灰色系統(tǒng)理論及其在旅游預測中的應用—以廣西桂林為例[J].西安電子科技大學學報:社會科學版,2007,17(2):1-5.

[8] 曹旭,張喆,馬少仙.最短路問題在旅游線路優(yōu)化中的應用[J].科技廣場,2012(2):115-118.

[9] 姚成果.基于隨機行駛時間的城市旅游線路優(yōu)化研究[D].哈爾濱:哈爾濱工業(yè)大學,2007.

[10] 常友渠,肖貴元,曾敏.貪心算法的探討與研究[J].重慶電力高等?？茖W校學報,2008,13(3):40-42.

[11] 聶小東.基于貪婪算法的排課系統(tǒng)的研究與實現(xiàn)[D].廣州:廣東工業(yè)大學,2006.

[12] 劉月華,呂永標,雷春霞,等.基于貪婪算法的太陽能小屋光伏電池組合分析[J].電子科技,2013,26(4):102-105.

[13] 鄒時林,阮見,劉波,等.最短路徑算法在旅游線路規(guī)劃中的應用—以廬山為例[J].測繪科學,2008,33(5):190-192.

[14] 樊守偉,嚴艷,張少杰,等.Dijkstra算法與旅游路徑優(yōu)化[J].西安郵電大學學報,2014,19(1):121-124.

[15] 岳秋菊,任志國,蔡曉龍,等.基于最短路徑優(yōu)化問題佛洛依德算法系統(tǒng)的設計與實現(xiàn)[J].甘肅高師學報,2010,15(5):41-43.

[16] 潘玉俠,梁勤歐.基于遺傳算法的旅游線路優(yōu)化[J].浙江師范大學學報:自然科學版,2011,34(3):350-354.

Tourism Route Optimization Based on Greedy Algorithm

TENG Quan1，SHEN Jingfeng1，XU Bin2，WANG Weiwei3

(1.School of Mechanical Engineering,University of Shanghai for Science and Technology,Shanghai 200082,China;2.Damping Technology Department,Shanghai Research Institute of Materials,Shanghai 200082,China;3.School of Transportation Management,Dalian Maritime University,Dalian 116026,China)

In view of the present domestic tourist route design much favor from characteristics of scenic spots, and less from the travel time and path,Greedy algorithm is used to establish mathematical model.TIn the traveler not more than 15 days of travel constraints,201 domestic 5A scenic spots were clustered,and the 201 scenic spots will be reduced to 31 provinces and cities,Travel time is from xi ’an to various provinces and cities and get 21 conform to the requirements of the travel routes,The results are presented in a more intuitive image format,an innovative approach in the travel route design research.

tourist routes;optimization problem;clustering greedy algorithm;restrictions

2016- 11- 24

滕泉(1992-)，男，碩士研究生。研究方向：CAE，精密測量。沈景鳳(1968-)，女，博士，副教授。研究方向：機械設計與理論等。

10.16180/j.cnki.issn1007-7820.2017.09.038

TP306.1；F592

A

1007-7820(2017)09-142-04