旅游線路優化設計探討

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

關鍵詞 最優旅游路線 排列組合原理 最鄰近插入法 分枝定界法

中圖分類號：F590.1 文獻標識碼：A

一、問題的提出

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

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

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

二、景點選取

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

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

設定：

1、景區級別：世界文化遺產或世界地質公園=10分；AAAAA級=8分；AAAA級=6分（AAAA以下不考慮）；

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

3、集群狀況：50km內有其他景點加3分；

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

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

根據河南省導游圖和上面設定的旅游價值指標體系，選出的景點如表1：

表1 所選取的最優景點

三、模型假設與符號說明

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

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

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

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

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

6、沒有超出景區承載力；

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

四、具體解法

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

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

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

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

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

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

圖1 景點距離關系無向圖G

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

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

接下來，由于頂點5最鄰近頂點3，將頂點5插入上面閉旅程，根據排列組合原理計算，得到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插入上面最短閉旅程，根據排列組合原理計算，得到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插入上面最短閉旅程，根據排列組合原理計算，得到閉旅程120個及其長度，要從中選擇最短旅程，計算過程就比較復雜。下面用“分枝定界法”尋找近似的最佳旅游線路。

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

尋找這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。顯然，長度最短的閉旅程就是所要尋找的近似最佳旅游線路。□

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

參考文獻：

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

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

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

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

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

[6]方冬云.圖論在旅游線路選擇中的應用.長春工業大學學報，2009