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

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

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

中圖分類號(hào)：F590.1 文獻(xiàn)標(biāo)識(shí)碼：A

一、問題的提出

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

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

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

二、景點(diǎn)選取

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

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

設(shè)定：

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

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

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

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

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

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

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

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

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

2、僅考慮路費(fèi)與門票費(fèi)，其它費(fèi)用不計(jì)；

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

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

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

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

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

四、具體解法

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

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

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

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

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

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

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

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

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

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

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。

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

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。

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

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

尋找這7個(gè)景點(diǎn)的近似最佳旅游線路的具體過程如下：

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

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

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

選頂點(diǎn)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。顯然，長度最短的閉旅程就是所要尋找的近似最佳旅游線路。□

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

參考文獻(xiàn)：

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

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

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

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

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

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