基于TSP旅行商模型的杭州旅游線路設計

吳莉莉 朱雪 徐俊康

摘 要：以美麗的西湖山水著稱于世的杭州的旅客逐年增長，由于到達杭州的外來旅客一般停留時間短暫。因此，如何在較短的時間內，盡可能地欣賞更多的美景將成為旅客首要考慮的問題。對此，本文通過聚類分析，建立基于TSP旅行商模型的多目標優化模型，設計出在保證景點的價值最大的同時滿足旅游總費用最低的路線。

關鍵詞：熵權法；聚類分析；TSP旅行商模型；多目標

中圖分類號：TP301.6 文獻標識碼：A 文章編號：2096-4706（2019）04-0094-03

Hangzhou Tourism Route Design Based on TSP Traveler Model

WU Lili，ZHU Xue，XU Junkang

（Zhejiang Chinese Medical University，Hangzhou 310053，China）

Abstract：Visitors in Hangzhou known for their beautiful West Lake landscape are growing year by year as foreign visitors to Hangzhou generally have a short stay. Therefore how to appreciate more beautiful scenery in a shorter period of time will become a top priority for passengers. In this regard through cluster analysis this paper establishes a multi-objective optimization model based on TSP traveler model and designs a route that Satisfies the lowest total tourism cost while ensuring the maximum value of the attraction.

Keywords：entropy method；cluster analysis；TSP traveler model；multi-objective

1 問題的提出

1.1 背景

隨著經濟的發展，居民的生活水平不斷地提高，在滿足物質基礎的同時，人們有了更高的追求，而在精神的追求中，旅游業就是人們的首選。其中，以其美麗的西湖山水著稱于世的杭州，2016年接待中外游客達到1.4億人次，2017年的G20更將這個美麗的城市推向國際大舞臺。作為八大古都之一的杭州擁有豐富的旅游資源：一個國家級度假區、兩處國家級風景名勝、兩個國家級自然保護區、五個國家級森林公園，而且杭州市政府也不斷出臺相關政策，加大對杭州市旅游產業的扶持力度，使得杭州迎來更多的游客。而在有限的時間內，觀賞到景點的數量寥寥無幾。

1.2 問題

為提高旅游的價值，本文借助計算機TSP旅行商模型，通過聚類分析，設計出在保證景點的價值最大的同時滿足旅游總費用最低的路線。對此，本文以設計杭州二日游為例，進行旅游價值最大化。

2 算法

2.1 獲取景點價值

2.1.1 選取景點與指標

首先搜索杭州市內知名景點，確定20個主要景點；然后查閱文獻并結合實際，確定影響景點旅游價值主要指標，結果如表1所示。

2.1.2 基于熵權法對指標進行賦權

將景點作為行，評價指標作為列構建矩陣，對數據標準化處理，通過計算比重、熵值，從而得到指標權重矩陣ωj為：ωj=[0.137 0.05 0.079 0.042 0.047 0.043 0.165 0.106 0.088 0.039 0.037 0.158]。

2.1.3 計算景點旅游價值

通過查閱文獻得到不同景點在各指標下的原始數據，將實際數據轉化為指標得分，通過指標權重矩陣，計算出各景點旅游價值，并排序，結果如表2所示。

2.1.4 計算任意兩景點間距離

在Google地圖上獲取20個景點的經緯度，再將經緯度轉化為坐標，則景點i和景點j間的距離dij為：

2.2 TSP模型

2.2.1 建立TSP模型

Step1 建立目標函數。設第i個景點的旅游價值為yi，假設，旅客在路上的費用與距離成正比，設比例系數為k，從景點i出發到景點j最短距離和為D，即路上費用為kD。旅客觀賞所有景點所需總費用為路上的費用與景點門票pi的費用之和，則可得到旅游總價值Y和費用P：

其中，xij表示景點i是否去往景點j。

Step2 確定約束條件。時間最多為48小時，每個景點最多去一次，出發點和終點需保持一致，即：

Step3 旅游路線的性價比。在此，我們用性價比來衡量路線的優劣，定義總的旅游景點的價值與總費用的比值為性價比W，即：

對此，假設兩天內最多去a個旅游景點，本文采用TSP旅行商模型，以旅游價值和消費總費用為約束條件，將多目標規劃變為單目標規劃，建立旅游景點總價值最高、消費費用最小、觀賞所有景點路徑和最小目標函數：

2.2.2 確定最終路線

由于有旅游價值最大和消費總費用最小兩個目標，為了求解方便，我們將性價比作為目標函數，將旅游價值和消費總費用作為約束條件，并將計劃游覽的景點數設置為定值，將多目標規劃變為單目標規劃。然后不斷改變設定的景點數，就不同景點數情況下的性價比進行對比求出最優值，即：

由于西湖旅游價值最高，并且杭州以西湖聞名于世，故將起點定為西湖。通過遍歷求解確定最佳路線，得到不同路線方案，如表3所示。

兩日游有效游玩時間應在16小時內，由此得出杭州兩日游最佳路線為：西湖→西湖博物館→河坊街→雷峰塔→虎跑公園→宋城→千島湖→靈隱寺，總價格為436元，性價比為2.959。

3 結 論

本文在TSP旅行商模型的基礎上，通過聚類分析，設計出了杭州最佳二日游路線，為眾多來到杭州的旅客提供了一個最大程度欣賞杭州美景的方案，在保證景點的價值最大的同時滿足旅游總費用最低的目標，但本文模型并未考慮到旅客的喜好，旅游公司在未來還應增加旅客喜好的目標，進行更多目標化的模型構建。

參考文獻：

[1] 劉嘯.旅游資源的資源、環境、區位、口碑評價模式——以北京市旅游資源為例 [J].中國集體經濟，2008（4）：41-42.

[2] 諶靜.紅色旅游目的地競爭力評價指標體系構建 [J].信陽農業高等專科學校學報，2009，19（4）：68-70.

作者簡介：吳莉莉（1998-），女，漢族，浙江溫州人，本科在讀，研究方向：計算機科學與技術。