旅游線路優(yōu)化設(shè)計探討

摘 要 本文主要探討最佳旅游線路的設(shè)計問題，在滿足相關(guān)約束條件的情況下，用最少的天數(shù)游覽盡可能多的景點是我們追求的目標(biāo)。本文以運籌學(xué)中最優(yōu)化理論和圖論的相關(guān)知識為基礎(chǔ)，對河南省旅游線路設(shè)計的問題加以分析。

關(guān)鍵詞 最優(yōu)旅游路線 排列組合原理 最鄰近插入法 分枝定界法

中圖分類號：F590.1 文獻標(biāo)識碼：A

一、問題的提出

隨著生活水平的不斷提高和精神壓力的不斷增加，旅游已成為人們調(diào)節(jié)心情、釋放壓力、提高生活質(zhì)量的重要活動。旅游本身應(yīng)該是一個讓人身心愉悅的過程。但是實際上，經(jīng)常會聽到旅途中的游客抱怨“累死了”、“我還沒來得及拍照呢”?？梢?，選擇合理的旅游線路是很有必要的。

一個旅游區(qū)域內(nèi)的若干景點各在不同的空間位置，對這些景點游覽或活動參與的先后順序與連接方式，可有多種不同的串連方式，由此產(chǎn)生組合成不同的旅游線路。旅游線路設(shè)計可以分為四類：第一類指區(qū)域旅游規(guī)劃中的線路設(shè)計；第二類指景區(qū)內(nèi)部的游道設(shè)計；第三類指旅行社線路設(shè)計；第四類指旅游者自主旅游所設(shè)計的旅游線路。本文探討的旅游線路設(shè)計是第四種，即游客根據(jù)自己的喜好所設(shè)計的旅游線路。

在編制線路時應(yīng)充分考慮到節(jié)省游客的每一分花費，使游客每一個景點都要游覽，并且不走回頭路，同時不同的旅游類型的線路設(shè)計應(yīng)有差別。下面用最優(yōu)化的知識探討一下性價比最高的休閑度假游的河南自駕游方案。

二、景點選取

旅游界流傳著這樣的說法：我國旅游看“三南”，一個是海南，一個是云南，再一個就是河南。河南省旅游資源得天獨厚，高品位的人文勝跡與諸多的自然景點交相輝映。按照中國旅游資源普查規(guī)定，將旅游資源分為6類74種基本類型，河南的旅游資源幾乎全部覆蓋，現(xiàn)已形成以鄭州、洛陽、開封三大旅游城市為中心，輻射全省的旅游發(fā)展格局。其中擁有世界文化遺產(chǎn)3個，分別是龍門石窟、安陽殷墟、登封“天地之中”歷史建筑群；世界地質(zhì)公園4個，分別是云臺山、嵩山、王屋山——黛眉山、伏牛山；全國5A級旅游景區(qū)9家：登封嵩山少林景區(qū)、洛陽龍門石窟景區(qū)、焦作云臺山、開封清明上河園、安陽殷墟、洛陽嵩縣白云山風(fēng)景區(qū)、焦作云臺山―神農(nóng)山景區(qū)、焦作青天河景區(qū)、堯山—中原大佛景區(qū)； AAAA級景區(qū)72個，分別是白馬寺、雞公山、南灣湖、關(guān)林，相國寺等。

根據(jù)河南省旅游景區(qū)概況，下面以景區(qū)級別、交通通達度、景區(qū)集群狀況、游客個人喜好、旅游紀(jì)念品五大因素作為景點旅游價值指標(biāo)體系，給各個景點進行賦值，利用Excel進行排名，進而選出在這些條件下能代表河南的6大旅游景點。旅游行政部門與游客可根據(jù)不同需要進行調(diào)整、建立相應(yīng)的旅游價值指標(biāo)體系。

設(shè)定：

1、景區(qū)級別：世界文化遺產(chǎn)或世界地質(zhì)公園=10分；AAAAA級=8分；AAAA級=6分（AAAA以下不考慮）；

2、交通通達度：高速沿線=10分，國道沿線=6分，省道沿線=3分；

3、集群狀況：50km內(nèi)有其他景點加3分；

4、游客個人喜好：自然景觀=10分；人文景觀=6分；

5、旅游紀(jì)念品：有=5分。據(jù)調(diào)查，景區(qū)中50元以下的中低價位旅游紀(jì)念品銷路最好，紀(jì)念品花費一般占旅游者景點總花費的10%—15%。

根據(jù)河南省導(dǎo)游圖和上面設(shè)定的旅游價值指標(biāo)體系，選出的景點如表1：

表1 所選取的最優(yōu)景點

三、模型假設(shè)與符號說明

1、旅行者前往下一個目的地時，不會出現(xiàn)被滯留等意外情況；

2、僅考慮路費與門票費，其它費用不計；

3、將城市看作點（旅行路線的總路程不包括在某一城市中觀光旅游的路程）；

4、兩城市之間的距離可以近似看作直線距離；

5、通過查找資料所獲取的城市信息是真實可靠的，具有使用價值；

6、沒有超出景區(qū)承載力；

7、假設(shè)公路沒有等級差別，即可將所有路面的狀況視為等同且汽車恒速。

四、具體解法

隨著生活節(jié)奏的不斷加快，在旅游舒適度不受影響及體力許可的情況下，用最少的錢與天數(shù)游覽盡可能多的景點是游客追求的目標(biāo)，由于門票價格固定，旅游所用的時間與旅游路程成正比關(guān)系，從而把問題轉(zhuǎn)化為制定一個合理的路線，盡量縮短旅游的路程，使總路程最短，即求最短的旅游線路問題。由于各景點距離依托城市（鄭州）的距離較遠，加上游客不走“回頭路”與“冤枉路”的原則，要走的是環(huán)形回路，放射形回路顯然是不可取的。這個問題可以用求加權(quán)無向圖總權(quán)數(shù)最小的哈密頓圈來尋找近似的最短旅游線路。

下面運用圖論中的“最鄰近插入法”來尋找近似最佳旅游線路，其算法與具體求解過程如下：把每個旅游景點看作加權(quán)無向圖中的各個頂點，各景點之間的直達公路看作加權(quán)無向圖中對應(yīng)頂點間的邊，各條公路的長度看作對應(yīng)邊上的權(quán)。若景點之間沒有直達的公路．則加權(quán)無向圖中對應(yīng)頂點之間用“邊”相連，而這條“邊”的含義是：由其中一個景點出發(fā)，通過中轉(zhuǎn)站到達另一景點所需的最短距離，這樣所旅游的各個景點間的公路網(wǎng)就轉(zhuǎn)化為加權(quán)無向圖(各邊的權(quán)數(shù)是對各景點間距離取整而得)，所旅游各個景點的近似最佳旅行線路問題，就轉(zhuǎn)化為在給定的加權(quán)無向圖中，尋找從給定的頂點出發(fā)，行遍所有頂點只有一次再回到該指定的頂點，使得總權(quán)數(shù)(總路程)最小。尋找近似最佳旅游線路的算法如下：

步驟1：用Floyd算法求出加權(quán)無向圖中任意兩點之間的最短路程，形成一條邊的初始路，其權(quán)限w(i，j)。

步驟2：設(shè)z表示最新加到這條路上的景點，從而不在這條路上的所有景點中選一個與z景點最靠近的景點y，把連接z景點與y景點的邊加到這條路上。重復(fù)這一步，直到加權(quán)無向圖中所有景點都包含此路上。

步驟3：將連接起點與最后加入景點之間的邊加到這條路上，就得到一個總權(quán)數(shù)最小的哈密頓回路。

對三中所選6個景點旅游線路的優(yōu)化問題可以描述為：從河南省會鄭州市出發(fā)，遍訪各個景點一次且僅有一次后，再返回鄭州，求總路程最短的閉合路徑，那么這6個景點之間的距離關(guān)系可用一個加權(quán)無向圖G來表示，如下圖1所示：

圖1 景點距離關(guān)系無向圖G

由河南省典型景點的加權(quán)無向圖G尋找這6個景點的近似最佳旅游線路的具體過程如下：

開始于頂點1，組成閉旅程11，在下一階段最鄰近1的頂點為頂點2，建立閉旅程121，頂點3最鄰近頂點2，建立閉旅程1231。

接下來，由于頂點5最鄰近頂點3，將頂點5插入上面閉旅程，根據(jù)排列組合原理計算，得到6個閉旅程，它們的長度分別如下：

12351：60+75+140+143=418，

12531：60+116+140+124=440，

13251：124+75+116+143=458，

13521：124+140+116+60=440，

15231：143+116+75+124=458，

15321：143+140+75+60=418。

在這些閉旅程中選取長度最短的旅程為12351或15321。

距離頂點5最鄰近的為頂點6，將頂點6插入上面最短閉旅程，根據(jù)排列組合原理計算，得到24個閉旅程，它們的長度分別如下：

123561：60+75+140+170+187=632，

123651：60+75+311+170+143=759，

125361：60+116+140+311+187=814，

125631：60+116+170+311+124=781，

126351：60+266+311+140+143=920，

126531：60+266+170+140+124=630；

132561：124+75+116+170+187=672，

132651：124+75+266+170+143=778，

135261：124+140+116+266+187=833，

135621：124+140+170+266+60=760，

136251：124+311+266+116+143=960，

136521：124+311+170+116+60=781；

153261：143+140+75+266+187=811，

153621：143+140+311+266+60=920，

152361：143+116+75+311+187=832，

153261：143+116+266+311+124=960，

156231：143+170+266+75+124=778，

156321：143+170+311+75+60=759；

163251：187+311+75+116+143=832，

163521：187+311+140+116+60=814，

162351：187+266+75+140+143=811，

162531：187+266+116+140+124=833，

165321：187+170+140+75+60=632，

165231：187+170+116+75+124=672。

在這些閉旅程中選取長度最短(632)的旅程為123561或165321。

最后，將頂點4插入上面最短閉旅程，根據(jù)排列組合原理計算，得到閉旅程120個及其長度，要從中選擇最短旅程，計算過程就比較復(fù)雜。下面用“分枝定界法”尋找近似的最佳旅游線路。

“分枝定界法”的圖論模型如下：用階矩陣D中的各個元素來表示各個景點之間的距離，且各個景點之間的距離是沒有方向的，那么n階矩陣D是對稱型矩陣。首先，在這個矩陣D中，抽取每行的最小元素，并令矩陣D每行中的所有元素減去該行的最小元素，得到新的矩陣D1。再抽取矩陣D2每列的最小元素，并令矩陣各列的所有元素減去該列的最小元素，得到新的矩陣，這樣得到的矩陣每行每列都至少有一個零元素存在。然后，選擇起點與某景點之間距離為零的元素，把這個元素所在的行和列從矩陣D2中劃去，得到新的矩陣D3。同時，把起點與某景點組成一條路。對矩陣D3重復(fù)矩陣D變化到矩陣D2的步驟操作，得到新的景點加入到最近路的末頂點的后面，使其成為一條新路。直到得到的最后矩陣是，且這條路包含所有的景點，所有的景點在這條路上只能出現(xiàn)一次，這樣操作才算停止，否則重復(fù)上面的步驟。

尋找這7個景點的近似最佳旅游線路的具體過程如下：

選頂點2，線路1→2，把D1中的第1行第2列劃掉，令d21=∞得

選頂點3，線路1→2→3，把D5中的第1行第2列劃掉，令d31=∞，得

選頂點4，線路1→2→3→4，把中的第1行第2列劃掉，令d41=∞，得

選頂點6，線路1→2→3→4→6，把D9中的第1行第3列劃掉，令d61=∞，得

從而得線路1→2→3→4→6→5→1，長度為60+75+196+259+170+143=903，在這些閉旅程中，選取長度最短(903)的旅程為1234651。顯然，長度最短的閉旅程就是所要尋找的近似最佳旅游線路?！?/p>

（作者：王美香，鄭州旅游職業(yè)學(xué)院教師，鄭州大學(xué)數(shù)學(xué)系在職碩士研究生，研究方向：線性規(guī)劃與最優(yōu)設(shè)計；楊繼奎，鄭州大學(xué)數(shù)學(xué)系碩士研究生，研究方向：圖論與組合最優(yōu)化）

參考文獻：

[1]湯慶園、夏安桃等. 發(fā)展特色河南旅游業(yè)的優(yōu)勢、問題及路徑[J].湖南城市學(xué)院學(xué)報，2010(9)

[2]趙西萍.旅游市場營銷學(xué).高等教育出版社，2002

[3]徐鳳生.最短路徑的求解算法.計算機應(yīng)用，2004(5)

[4]蔡文芳.運籌學(xué)在旅游線路規(guī)劃中的作用.經(jīng)營管理，2009(9)

[5]殷劍宏、吳開亞.圖論及其算法.中國科學(xué)技術(shù)出版社，2003

[6]方冬云.圖論在旅游線路選擇中的應(yīng)用.長春工業(yè)大學(xué)學(xué)報，2009