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

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

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

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

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

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

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

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

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

1 線路背景

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

2 問題分析

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

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

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

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

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

3.1 名詞和符號(hào)說明

在運(yùn)用貪婪算法進(jìn)行旅游線路設(shè)計(jì)時(shí)的符號(hào)如表1所示。

表1 貪婪算法的符號(hào)說明

3.2 模型的基本假設(shè)

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

4 模型建立及求解

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

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

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

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

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

4. 2 各省省內(nèi)旅行最短時(shí)間的計(jì)算

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

圖1 河南省旅行示意圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表4 21條旅游路線

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

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

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

6 結(jié)束語

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

[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] 楚義芳.關(guān)于旅游線路設(shè)計(jì)的初步研究[J].旅游學(xué)刊,1992(2):9-13.

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

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

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

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

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

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

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

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

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

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

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

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

[16] 潘玉俠,梁勤歐.基于遺傳算法的旅游線路優(yōu)化[J].浙江師范大學(xué)學(xué)報(bào):自然科學(xué)版,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-)，女，博士，副教授。研究方向：機(jī)械設(shè)計(jì)與理論等。

10.16180/j.cnki.issn1007-7820.2017.09.038

TP306.1；F592

A

1007-7820(2017)09-142-04