基于Floyd算法的旅游線路優(yōu)化

楊 柳，李苗苗，程 越

(上海工程技術(shù)大學(xué) 管理學(xué)院，上海 201620)

基于Floyd算法的旅游線路優(yōu)化

楊 柳，李苗苗，程 越

(上海工程技術(shù)大學(xué) 管理學(xué)院，上海 201620)

為游客設(shè)計(jì)合理的游覽線路，盡量達(dá)到費(fèi)用最少、旅游體驗(yàn)最好的效果。以分布決策、逐步優(yōu)化為指導(dǎo)，利用Matlab軟件進(jìn)行Floyd運(yùn)算尋找最短路徑，以出發(fā)地為中心在全國(guó)范圍內(nèi)，劃分分支線；以省會(huì)為中心，在省內(nèi)構(gòu)建游覽路線的哈密頓圈(Hamilton)，再根據(jù)時(shí)間、成本，進(jìn)行對(duì)各省份之間進(jìn)行優(yōu)化合并。假設(shè)游客的常住地為西安，設(shè)計(jì)出了兩條線路：一是自駕方式出行的最短路徑，二是可換乘飛機(jī)、高鐵，成本最低的旅游線路。文中將所建立的模型進(jìn)行了推廣應(yīng)用，變化了出發(fā)地點(diǎn)和景區(qū)，并針對(duì)游客和相關(guān)部門(mén)給出了相應(yīng)的建議。

Floyd算法；Matlab；最短路徑；哈密頓圈

隨著生活水平的提高國(guó)內(nèi)旅游人數(shù)急劇增多，中國(guó)成為世界第一國(guó)內(nèi)旅游市場(chǎng)。人們對(duì)旅游的要求也越來(lái)越高，但由于旅游景點(diǎn)眾多、時(shí)間資金問(wèn)題制約，不論是游客還是景區(qū)市場(chǎng)推廣者都需要規(guī)劃旅游線路，提高旅游體驗(yàn)的滿意度，即線路最優(yōu)和費(fèi)用最優(yōu)[1-5]。旅游既是一種時(shí)間的安排，又是一種成本的支出，合理的線路安排可以使游人能夠在最短的時(shí)間獲得最大的觀賞效果，將每個(gè)景點(diǎn)合理貫穿起來(lái)[6-9]。運(yùn)用Floyd算法為游客安排旅游線路，從而實(shí)現(xiàn)線路最優(yōu)、費(fèi)用最優(yōu)。

1 模型建立和假設(shè)

2015年10月8日國(guó)家旅游局新增14個(gè)景點(diǎn)，全國(guó)共201個(gè)5A級(jí)景區(qū)名單，假設(shè)一位自駕游愛(ài)好者擬按此景區(qū)名單制定旅游計(jì)劃，實(shí)現(xiàn)若干年游覽全國(guó)5A級(jí)景區(qū)的目的[10]。該游客常住地是西安，想要在若干年游遍全國(guó)201個(gè)5A級(jí)景區(qū)。一是全程自駕，為其規(guī)劃設(shè)計(jì)旅游線路；二是考慮費(fèi)用問(wèn)題，假如3人同行，綜合考慮前述全程自駕、先乘坐高鐵或飛機(jī)到達(dá)省會(huì)城市后再租車自駕到景區(qū)等出行方式，設(shè)計(jì)一個(gè)10年游遍所有201個(gè)5A景區(qū)、費(fèi)用最優(yōu)、旅游體驗(yàn)最好的旅游線路，旅游要求具體如表1所示。

表1 旅游安排具體要求

本研究的前提假設(shè)：(1)假定游客盡可能多的玩夠15天，避免路途重復(fù)，節(jié)約游玩時(shí)間和成本；(2)行車平均時(shí)速恒定，且不受天氣、路況等客觀因素的影響；(3)不考慮交通意外等突發(fā)事故，并且旅行者在行車過(guò)程中，除在省會(huì)和景點(diǎn)停留外，不做任何停留。

2 最短路徑問(wèn)題分析與解答

旅游線路的最優(yōu)規(guī)劃實(shí)質(zhì)就是求圖上最短路徑問(wèn)題。由題中所給的各省會(huì)之間的直達(dá)路徑，利用Floyd 算法求出任意兩點(diǎn)間的最短路徑，任意兩個(gè)頂點(diǎn)用一條邊相連，邊的權(quán)值為這兩點(diǎn)的最短距離，這樣就可以構(gòu)造出一個(gè)完全圖。西安X1到其他省會(huì)的30個(gè)Z1，Z2，Z3，…，Z30之間旅游景點(diǎn)的安排，通過(guò)合理的規(guī)劃，減少出行時(shí)間，從而使旅行者在規(guī)定的出行時(shí)間內(nèi)游玩更多的地方[11-13]。

首先采用方法T對(duì)西安X1到其他省會(huì)的30個(gè)Z1，Z2，Z3，…，Z30進(jìn)行分組，假設(shè)將其分為n組(n=1,2,…,30)，分別記為V1，V2，…，VK。設(shè)VK={Zl1，Zl2，…，Zlk}分組需要滿足以下約束條件：每一個(gè)分組都需要包含西安X1，每個(gè)分組要包括西安和所有的省會(huì)。

設(shè)旅行者每次出行到達(dá)Zj1，Zj2，…，Zjk的旅游景點(diǎn)，完成這些景點(diǎn)游玩，形成一條路徑，即對(duì)應(yīng)一個(gè)閉合圖形。旅行者行車從西安出發(fā)依次旅游景點(diǎn)Zj1，Zj2，…，Zjk游玩后再返回西安的旅游線路記為Zj1，Zj2，…，Zjk，對(duì)應(yīng)完全圖中的圈X1，Zj1，Zj2，…，Zjm，X1。兩個(gè)旅游景點(diǎn)之間的最短距離記為|Z1Zm|。由于在完全圖中，任意兩點(diǎn)都相鄰，當(dāng)旅行者從西安出發(fā)到省會(huì)及旅游景點(diǎn)，再回來(lái)，則視為一條路徑。這樣，每一條路與完全圖中的哈密頓圈一一對(duì)應(yīng)，只需要研究完全圖中經(jīng)過(guò)景點(diǎn)的圈即可。

2.1 省份之間模型建立

行程和游玩時(shí)間對(duì)旅游線路規(guī)劃起到約束，首先必須考慮如何進(jìn)行區(qū)域劃分，再進(jìn)行區(qū)域內(nèi)優(yōu)化。在整個(gè)線路優(yōu)化過(guò)程中，采用分段決策的思想，首先將全國(guó)201個(gè)景點(diǎn)按省份進(jìn)行分組，尋找省份內(nèi)最短路徑，省份內(nèi)景點(diǎn)調(diào)整優(yōu)化。其次毗鄰省份之間優(yōu)化調(diào)整，逐步將全國(guó)景點(diǎn)進(jìn)行優(yōu)化調(diào)整的思路，反復(fù)利用Floyd算法合并優(yōu)化[14]。最終形成全國(guó)出行最優(yōu)線路圖。

基于Floyd算法，將各省會(huì)之間距離輸入Matlab，得出了省份之間最短距離，經(jīng)過(guò)GIS數(shù)據(jù)庫(kù)驗(yàn)證，證實(shí)了該結(jié)論。考慮到地理面積覆蓋，距離在-20～20 km范圍區(qū)間，在高速路上行駛時(shí)間在15 min以內(nèi)，視其為合理范圍，那么就可以得到10條主干線，如圖1所示。

以西安為中心到全國(guó)各地有10條分支線，本文以直線代曲線表示方向，簡(jiǎn)化作圖。在優(yōu)化調(diào)整過(guò)程中，以全國(guó)10個(gè)分支線為基準(zhǔn)，對(duì)分支線所經(jīng)省市進(jìn)一步優(yōu)化。

表2 以西安為中心旅游線路規(guī)劃 /km

2.2 省內(nèi)景點(diǎn)模型建立

利用GIS數(shù)據(jù)庫(kù)，獲取省內(nèi)各景點(diǎn)之間的距離，統(tǒng)計(jì)出景點(diǎn)之間的需要的行程時(shí)間。再次利用Floyd算法，生成了景點(diǎn)之間的最短距離。反復(fù)使用Floyd運(yùn)算求矩陣，以山西7個(gè)景點(diǎn)為例的編程代碼，如圖2所示，其中7×7矩陣中的數(shù)值為任意兩景點(diǎn)間的距離，進(jìn)行運(yùn)算可得D矩陣和R矩陣，在所得矩陣基礎(chǔ)上選用最小元素法構(gòu)成一個(gè)哈密頓圈(Hamilton)，即形成省會(huì)到省內(nèi)各景點(diǎn)的游玩線路閉合圈。按照此方法，各省內(nèi)都可求出游覽的最短路徑的哈密頓圈。

圖2 Matlab進(jìn)行Floyd算法程序代碼

以山西為例，利用Floyd算法和Matlab軟件進(jìn)行計(jì)算結(jié)果，可得出游覽路徑⑦-⑥-①-⑤-④-③-②-⑦這樣一個(gè)哈密頓圈，即可選擇的旅游線路為：晉中市平遙縣平遙古城景區(qū)→晉中市喬家大院文化園區(qū)→太原市→晉中市介休市綿山風(fēng)景名勝區(qū)→晉城陽(yáng)城縣皇城相府生態(tài)文化旅游區(qū)→忻州五臺(tái)山風(fēng)景名勝區(qū)→大同云岡石窟，形成一個(gè)閉合的回路。通過(guò)上述方式，全國(guó)各省內(nèi)景點(diǎn)依次構(gòu)成封閉的哈密頓圈。

圖3 山西游玩路線哈密頓圈

2.3 出行線路進(jìn)一步優(yōu)化

基于安全考慮，行車時(shí)間限定于每天7:00～19:00之間，且每天開(kāi)車時(shí)間不超過(guò)8 h；在每天的行程安排上，若安排全天游覽則開(kāi)車時(shí)間控制在3 h內(nèi)，安排半天景點(diǎn)游覽，開(kāi)車時(shí)間控制在5 h內(nèi)；在高速公路上的行車平均速度為90 km/h，在普通公路上的行車平均速度為40 km/h。景區(qū)開(kāi)放時(shí)間統(tǒng)一為8:00～18:00。根據(jù)兩地的實(shí)際距離和速度，就可得行車時(shí)間。

基于上述因素，需要對(duì)已有線路進(jìn)行下一步優(yōu)化。以浙江省為例，研究發(fā)現(xiàn)旅行者以此線路游玩浙江省全部5A級(jí)景區(qū)僅需10天，但考慮到有些地方景點(diǎn)較少，利用省份的劃分，在支干線上進(jìn)行合并優(yōu)化。那么，根據(jù)每次出行時(shí)間不超過(guò)15天的因素，可以考慮將其他線路與之合并，到達(dá)出行時(shí)間盡可能接近15天，避免了來(lái)回路程的重復(fù)，同時(shí)依據(jù)地域的臨近原則，節(jié)約出行成本，進(jìn)行的合并線路形成更為優(yōu)化的旅行路線，即“西安-浙江-上海-西安”出行線路。

對(duì)全國(guó)10大支線上省份之間進(jìn)行合并優(yōu)化，在出行不超過(guò)15天因素的限制下，最終形成24條旅游線路。經(jīng)核算，該旅行者至少需要12年，才能游遍全國(guó)5A級(jí)景區(qū)。

3 費(fèi)用最優(yōu)問(wèn)題的分析和解答

在費(fèi)用問(wèn)題上需要考慮交通方式的改變，提供了時(shí)間的充裕，在使用時(shí)間相對(duì)較少的情況下，使得費(fèi)用最少、旅游體驗(yàn)最好的旅游線路。

在最短路徑問(wèn)題的基礎(chǔ)上根據(jù)Floyd算法，可以得到省內(nèi)的游覽路線。省內(nèi)的游覽路線已經(jīng)優(yōu)化調(diào)整，考慮到省內(nèi)景點(diǎn)與省內(nèi)景點(diǎn)距離較近，可乘坐高鐵或飛機(jī)到達(dá)景區(qū)相鄰的省會(huì)城市，而后采用租車的方式自駕到景區(qū)游覽。步驟如下：

步驟1 在上述結(jié)論的基礎(chǔ)上，考慮到出行方式多樣化和滿意原則，并采用分部決策的方式，24條線路進(jìn)行優(yōu)化，即選擇綜合性價(jià)比高的線路，并得出游玩線路表；

步驟2 在最新線路表的基礎(chǔ)上，對(duì)線路景點(diǎn)的行車費(fèi)用、住宿、景區(qū)費(fèi)用、高鐵、飛機(jī)費(fèi)用、租車等費(fèi)用進(jìn)行核算，依次得出各線路所需費(fèi)用；

步驟3 綜合分析，得出旅行者每次出行具體線路和旅行費(fèi)用；

步驟4 對(duì)模型進(jìn)一步優(yōu)化。

3.1 旅行線路優(yōu)化問(wèn)題

依據(jù)最短路徑問(wèn)題得出的旅行線路表，旅行者可以綜合考慮高鐵、飛機(jī)、自駕等出行方式，在其他條件不變的基礎(chǔ)上，可以對(duì)旅行線路進(jìn)一步優(yōu)化，從而得到費(fèi)用最優(yōu)和旅行體驗(yàn)最好的旅行線路。

由最短路徑問(wèn)題結(jié)論可知，省內(nèi)游玩線路為最優(yōu)線路?，F(xiàn)引入出行方式和旅行體驗(yàn)因素，為更加準(zhǔn)確的分析和評(píng)估旅行線路，對(duì)旅游體驗(yàn)最好的旅游線路做出以下假設(shè)：

假設(shè)1 旅行者連續(xù)開(kāi)車超過(guò)8 h，即放棄；

假設(shè)2 乘坐高鐵超過(guò)6 h，旅行者放棄，轉(zhuǎn)而選擇飛機(jī)；

假設(shè)3 為提高旅行舒適度，盡量減少換乘次數(shù)。

旅行方式的選擇受到行程時(shí)間、距離、換乘次數(shù)等因素的影響，在已有旅游線路的基礎(chǔ)上，運(yùn)用分步?jīng)Q策的方式，綜合考慮上述因素對(duì)線路進(jìn)行進(jìn)一步優(yōu)化，得出新的優(yōu)化線路。通過(guò)對(duì)已有的24條出行線路進(jìn)行優(yōu)化，得出以下結(jié)論：出行線路由24條線路優(yōu)化到19條，即12年縮減到9.5年。從而可以看出，靈活選擇出行方式，不僅可以縮短旅游所需時(shí)間，還可以提高旅游品質(zhì)，達(dá)到費(fèi)用最優(yōu)、旅游體驗(yàn)最好的線路。

3.2 旅行線路費(fèi)用問(wèn)題

省內(nèi)的行車時(shí)間和游覽時(shí)間已知，該旅游愛(ài)好者3人同行，住宿費(fèi)簡(jiǎn)化為省會(huì)城市和旅游景區(qū)200元/人·天，地級(jí)市150元/人·天，縣城100元/人·天；高速公路的油耗加過(guò)路費(fèi)平均為1.00元/公里， 普通公路上油耗平均為0.60元/km。由于高速公路和普通公路收費(fèi)和油費(fèi)標(biāo)準(zhǔn)不同，查閱相關(guān)資料和進(jìn)行數(shù)據(jù)分析，發(fā)現(xiàn)幾省的景點(diǎn)具體行車?yán)锍讨懈咚俟放c普通公路之比近似為8:2，同時(shí)符合二八原則，將這一準(zhǔn)則推行至全國(guó)其它省份。在優(yōu)化的旅行線路圖中，分別對(duì)各優(yōu)化線路的游玩行車費(fèi)用、住宿、景區(qū)費(fèi)用及租車費(fèi)用進(jìn)行計(jì)算和匯總。

3.3 出行線路進(jìn)一步優(yōu)化

在線路優(yōu)化的過(guò)程中，發(fā)現(xiàn)新疆省內(nèi)最優(yōu)游玩線路所需時(shí)間已經(jīng)超過(guò)每次出行的預(yù)定時(shí)間15天，因此，以新疆省為例，依據(jù)Floyd原則對(duì)新疆周圍省市進(jìn)一步優(yōu)化。

通過(guò)對(duì)優(yōu)化后的游玩線路進(jìn)行車費(fèi)的核算，得到新疆和寧夏所需總費(fèi)用16 268.08元，出行需22天，與上文中新疆和寧夏總費(fèi)用19 684.78元，出行需19天，相比較節(jié)省了3 416.7元，出行增加3天。但是，飛機(jī)、高鐵與自駕游的靈活出行方式大幅增加了旅行者的旅游舒適度。優(yōu)化后，得出以下結(jié)論：旅行者需出行19次即9.5年，游玩時(shí)間需要253天，出行總費(fèi)用為463 769.74元。

4 模型推廣與建議

4.1 模型的推廣

常住地的改變或者旅游景點(diǎn)增多，建模思路、方式具有一致性，建模步驟如下：

步驟1 基于Floyd算法，將省會(huì)城市間道路信息在Matlab中運(yùn)算，以省份為單位進(jìn)行區(qū)域劃分，形成以游客所在省會(huì)為中心的全國(guó)分支線；

步驟2 反復(fù)運(yùn)用Floyd算法，得出各省省內(nèi)景點(diǎn)之間最短距離，各省省內(nèi)景點(diǎn)分別構(gòu)建哈密頓圈，即各省省內(nèi)游玩的行程路線；

步驟3 省份之間線路逐步優(yōu)化調(diào)整；

步驟4 結(jié)合行車時(shí)間要求和景點(diǎn)開(kāi)放時(shí)間的制約，給出相應(yīng)的優(yōu)化行程線路。

對(duì)于貨物配送、銷售人員銷售、交通線路規(guī)劃等問(wèn)題，本文模型具有一定適用性，可以推廣。

4.2 模型的優(yōu)缺點(diǎn)評(píng)價(jià)

模型的優(yōu)點(diǎn)：(1)在模型建立過(guò)程中，對(duì)全國(guó)5A級(jí)景點(diǎn)首先采用各省會(huì)間最短路徑，得出出行主線，其次分別規(guī)劃各省內(nèi)景點(diǎn)優(yōu)化路徑，最后得出全國(guó)出行優(yōu)化線路圖。這對(duì)旅行者旅游具有一定的指導(dǎo)意義；(2)查閱相關(guān)文獻(xiàn)并且收集大量數(shù)據(jù)，基于Floyd算法，利用Matlab軟件得出所需數(shù)據(jù)和結(jié)論，使用方法的科學(xué)性和數(shù)據(jù)的客觀性。模型也存在這一些缺點(diǎn)：(1)分組是在一定的規(guī)則下進(jìn)行的，其結(jié)果與其所側(cè)重的原則有較大的關(guān)系，不同原則會(huì)導(dǎo)致分組情況變化，進(jìn)而導(dǎo)致線路的變化；(2)充分考慮到全國(guó)景點(diǎn)過(guò)多，數(shù)據(jù)過(guò)大，出行線路仍有優(yōu)化空間。

4.3 建議

對(duì)于游客來(lái)說(shuō)，旅游的目的是愉悅身心、放松享受生活。以此為出發(fā)點(diǎn)，對(duì)旅行者給出以下建議：(1)靈活選擇出行方式，盡量減少換乘次數(shù)和行車時(shí)間；(2)各省省內(nèi)游玩可參考優(yōu)化線路表，合理選擇游玩線路；(3)游玩途中，合理安排住宿、景點(diǎn)選擇，得到最優(yōu)旅游體驗(yàn)。

對(duì)于相關(guān)部門(mén)來(lái)說(shuō)，景區(qū)線路優(yōu)化和市場(chǎng)推廣是其工作的重點(diǎn)。以此為目標(biāo)，對(duì)相關(guān)部門(mén)給出以下建議：(1)強(qiáng)化區(qū)域和和各旅游線路的區(qū)域合作，加強(qiáng)政府間合作，構(gòu)建無(wú)障礙旅游機(jī)制，實(shí)現(xiàn)區(qū)域旅游合作的規(guī)范化和制度化，以達(dá)到旅游資源的最優(yōu)配置；(2)節(jié)假日、旅游旺季，可以適度增加車輛，滿足客流需求；(3)加大旅游線路的宣傳營(yíng)銷力度，塑造整體旅游形象和各旅游線路的特色形象，加強(qiáng)整體營(yíng)銷力度，挖掘潛在的客源市場(chǎng)。

[1] 王徐民,方玉平,張慧慧.旅游線路優(yōu)化設(shè)計(jì)[J].中國(guó)西部科技,2011(24):35-36.

[2] 耿建忠,吳殿廷,葉倩,等.基于圖論的西藏旅游線路評(píng)價(jià)與優(yōu)化研究[J].地域研究與開(kāi)發(fā),2011(1):104-109.

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

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

[5] 徐秀花,程曉錦,寇怡.蟻群算法在旅游交通線路中的應(yīng)用[J].北京印刷學(xué)院學(xué)報(bào),2013(2):48-51,54.

[6] 何紅,孫根年.基于教與學(xué)優(yōu)化算法的智能旅游線路優(yōu)化[J].陜西理工學(xué)院學(xué)報(bào):自然科學(xué)版,2015(1):72-78.

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

[8] 劉斯禹,韓雪,郭天超.基于Matlab圖形界面研究李薩如圖形及其討論[J].科技資訊,2016(6):126-127.

[9] 劉冰,曾國(guó)軍,彭青. 社會(huì)網(wǎng)絡(luò)視角下旅游線路研究-以新疆為例[J].旅游學(xué)刊,2013(11):101-109.

[10] 劉宏盈,韋麗柳,張娟.基于旅游線路的區(qū)域旅游流網(wǎng)絡(luò)結(jié)構(gòu)特征研究[J].人文地理,2012(4):131-136.

[11] 胡曉濤,吳成罡.基于虛擬旅游導(dǎo)航智能選擇系統(tǒng)的Floyd算法[J].統(tǒng)計(jì)與決策,2012(18):74-77.

[12] 王榮,江東,韓惠.基于Floyd方法的最短路徑算法優(yōu)化算法[J].甘肅科學(xué)學(xué)報(bào),2012(4):110-114.

[13] 王佳,趙宏麗.基于Dijkstra算法的京津冀旅游交通線路優(yōu)化研究[J].統(tǒng)計(jì)與決策,2011(13):81-83.

[14] 侯曉利,薛偉坡,張軍委.公交線路選擇問(wèn)題的數(shù)學(xué)模型與算法[J].統(tǒng)計(jì)與決策,2008(18):76-78.

Research of Optimizing Tourism Route Based on the Floyd Algorithm

YANG Liu, LI Miaomiao ,CHENG Yue

(School of Management, Shanghai University of Engineering Science,Shanghai 201620,China)

This paper attempts to design the reasonable tourist path to cost at least as far as possible ,for the tourism experience the best effect. Guided by the optimization of the distribution decisions step by step,firstly,we use Matlab software and Floyd algorithm to find the shortest path, across the country, for the center with origin division branch line;Secondly using the provincial capital as the center, we build a tourist route in the province of Hamiltonian cycle; then according to the time,we optimize the between the provinces merged. The paper assumes that the tourists always live in Xi’an, we design two routes for him: one is the shortest path of drive travel, the other is that the tourist can choose the plane or high iron,the lowest cost of tourism path.We popularize and apply the proposed model in this article-change the place of departure and the change of the scenic spot, and give the corresponding suggestions for tourists and related department.

Floyd algorithm；Matlab；the shortest path；hamiltonian cycle

2016- 07- 05

楊 柳(1991-)，男，碩士研究生。研究方向：旅游管理，企業(yè)管理。李苗苗(1991-)，女，碩士研究生。研究方向：旅游管理，領(lǐng)導(dǎo)力。程越(1993-)，男，碩士研究生。研究方向：企業(yè)管理。

10.16180/j.cnki.issn1007-7820.2017.01.021

TP301.6

A

1007-7820(2017)01-076-04