旅游線路的優化設計

摘要 本文主要研究最佳旅游路線的設計問題，在滿足相關約束條件的情況下，在規定的時間內花最少的錢游覽盡可能多的景點是本設計的理想目標。基于對此的研究，建立數學模型，設計出最佳的旅游路線。

關鍵詞 最佳線路 TSP Hamilton圈 綜合評判 0-1變量

中圖分類號：F592文獻標識碼：A

Optimization of Tourism Route

CHEN Xin， LIU Hanqing， XU Changheng

(College of Mechanical Engineering， Southwest Jiaotong University， Chengdu， Sichuan 611756)

AbstractThis paper studies the problem of optimal design of tourist routes， to meet the constraints related to the case， within the prescribed time to spend the least money to visit as many attractions is the ideal goal of this design. Based on this study， a mathematical model， to design the best tourist routes.

Key wordsbest route; TSP Hamilton;comprehensive evaluation; 0-1 variable

隨著經濟的發展，人們的生活水平不斷提高，旅游已成為日常生活中一項重要活動。江蘇徐州的一位旅游愛好者打算今年的五月一日早上8點之后出發，到全國十個著名景點旅游，最后再回到徐州。他考慮到跟團旅游受限太大，打算自己作為背包客出游。為了讓他能有一個快樂順利的旅程，我們針對如下的幾種情況，為他設計出詳細的行程表，該行程表包括具體的交通信息(車次、航班號、起止時間、票價等)、賓館地點和名稱，門票費用，在景點的停留時間等信息。

針對選取在規定時間內花最少錢游覽盡可能多的景點，我們分成五個步驟來研究，先研究在時間不限的情況下或者旅游費用不限的情況下，游客將十個景點全游覽完，分別至少需要多少旅游費用；再研究游客準備2000元旅游費用或者旅客只有5天的時間，想盡可能多游覽景點，分別設計旅游行程表；最后綜合以上的研究結果，游客在只有5天的時間和2000元的旅游費用下，想盡可能多游覽景點，建立數學模型并設計旅游行程表。

步驟一：是一個典型的最佳旅行商問題，簡稱TSP問題。一個單一旅行者由起點出發，經過所有給定需求點，最終回到出發點的最小路徑成本問題。旅行總費用包括交通費用和在景點游覽時的費用，由于每個景點都要游覽，景點游覽時的費用為必須的消費，所以應從交通費和縮短時間著手進行設計，綜合考慮所有約束條件做出最低成本的方案。

一般游覽的總費用由兩部分組成，分別為交通總費用和旅游景點的花費，交通總費用中的各城市間火車費用和各城市車站到景區公交時間、費用的數據都可以通過調查得到。

因為xij表示從第i個景點到第j個景點所需的交通費用，而rij是判斷游客是否從第i個景點直接到第j個景點的0-1變量，因此我們可以很容易得到交通總費用為：

旅游景點的費用：m2

根據查閱門票價格，可得到門票總費用為1225元。住宿費用可通過查閱當地所選擇的住宿地的價格記錄可以得到。餐飲等其它費用：每天60元。

因為Ci表示在各景點的門票，而整個旅游路線又是一個環形，因此我們可得旅游景點的花費為：

從而我們可以得到總費用是交通總費用和在所有旅游景點的總費用的總和。

根據以上計算可以看出，線路可設計為徐州→武漢→廬山→黃山→普陀山→常州→嶗山→北京→祁縣→西安→洛陽→徐州，最低的總費用為2887元。

步驟二：是在不考慮費用約束，要求在最短時間游覽所有景點，縮短時間最有效的方式是乘坐最快捷的交通工具。這樣就可以把路程轉換為時間來計算，將地圖中的網絡圖轉化成加權網絡圖，從原點徐州出發前往各個點，最終回到原點，求出最小路徑。通過運用步驟一的模型，改變目標為最短時間，并作出相應的約束調整，得出最佳線路為：徐州→祁縣→嶗山→普陀山→北京→洛陽→西安→黃山→廬山→武漢→常州→徐州。

步驟三：求在步驟一的基礎上充分考慮費用的限制設計出最佳旅游線路，根據約束做出一個最佳Hamilton圈，使得景點數目最多且費用在2000元以內。費用在2000元之內成為了約束條件，根據實際情況，可以得到以下：

使用Lingo對模型求解得最優線路為：

徐州→常州→廬山→武漢→北京→祁縣→西安→洛陽→徐州

步驟四：限定了時間為5天，不考慮費用的情況下游覽盡量多的景點。在步驟二的基礎上充分考慮時間的限制，做一個以5天為約束條件類似于步驟三的最佳Hamilton圈，從而做出最佳線路：徐州→北京→洛陽→西安→山西→武漢→常州→徐州，共游覽6個景點。

步驟五：實際上是對步驟三和步驟四的綜合考慮，不僅要考慮時間限制問題，還要考慮費用在預算范圍內的問題，在三、四問基礎上加上以5天和費用小于2000元的約束做出最佳Hamilton圈，得出最佳線路。根據分析可知，在步驟二的基礎上加入兩個約束條件：

根據步驟三的約束條件，再加上時間小于5天。

使用Lingo對模型求解得最優線路為：

徐州→北京→祁縣→西安→武漢→常州→徐州

注：

①i，j——第i個或者第j個景點i，j，=1，2，……，11；分別表示徐州、常州、青島、北京、祁縣、洛陽、黃山、武漢、西安、廬山、舟山；

②c——旅游總花費；

③n——旅游景點數目；

④ti——第i個景點的逗留時間；

⑤ci——在第i個景點的總消費；

⑥tij——從第i個景點到第j個景點所需的交通時間；

⑦cij——從第i個景點到第j個景點所需的交通費用；

⑧

⑨

⑩Zi——在第i個景點的住宿費用

參考文獻

[1]姜啟源，謝金星，葉俊.數學模型(第三版).北京:高等教育出版社，2003.

[2]謝金星，薛毅.優化建模與LINDO/LINGO軟件.北京:清華大學出版社，2005.

[3]周仁郁.SPSS13.0統計軟件.成都:西南交通大學出版社，2005.