長治市旅游線路的優化模型

郭偉，常金勇

（1.長治學院數學系，山西長治046011；2.中國科學院信息工程研究所，北京，100093）

長治市旅游線路的優化模型

郭偉1，常金勇2

（1.長治學院數學系，山西長治046011；2.中國科學院信息工程研究所，北京，100093）

為了研究如何選擇最短旅游路徑，在山西省長治市周邊11個縣中，各選取了1個具有代表性的旅游景點。通過分析，運用旅行售貨商（TSP）模型，建立長治市旅游線路的優化模型，并借助LINGO工具編寫程序，求出了一條最短路徑。

旅游線路；優化模型；LINGO

1　引言

某位旅游愛好者打算在暑假期間到長治市各個縣城的一些著名景點旅游。在山西省長治市周邊的11個縣中，各選取了1個具有代表性的旅游景點。他計劃把長治市各個縣城的最著名的景點旅游一遍，最后回到出發地，請問該游客應該選擇怎樣的旅游路線[1]，才能使他的總行程最短？

2　模型簡介

求總行程最短可以利用旅行售貨商（TSP）模型[2]來解決。我們首先查找景點位置，并計算任意兩景點距離，最后建立模型并求解。

3　模型建立

3.1模型假設

1、在總行程最短的方案中我們不考慮堵車等情況；

2、繪制路線圖時，把各景點的路線看做一個賦權的平面圖[3]。

3、i：第i個景點，i=1，2，…，11

j：第j個景點，j=1，2，…，11

dij：第i個景點與第j個景點之間的距離

3.2模型的建立與求解

通過Google電子地圖查出長治市旅游地圖如圖1所示﹙其中地圖比例尺為1:1180000﹚。

不妨把長治市的旅游地圖中各個縣的著名景點進行處理，把地圖上的每一條線路用線段表示，用頂點表示地圖上的岔路口，即多條線段的交點，這樣就形成了一個由點和線段組成的圖。我們可以在每條線段上標上數字，表示兩旅游景點之間的實際距離。在山西省長治市周邊的各個縣城所有景點中選擇一個最具有代表性的著名景點，如表1所示。

表1　各個縣城所選的著名旅游景點

記沁源縣靈空山編號為1，其它景點依次編號為2、3、…、11，最后回到出發地，再重復時的編號為12。通過Google電子地圖，查到各個景點的地理坐標（經度和緯度）如表2所示。

表2　各個著名旅游景點所在的地理位置

下面必須求出任意兩個景點之間的實際距離。雖然地球不是一個標準的球體，但南北與東西長度相差不大，可以假設地球為一個球體，球體半徑R=6371229公里。根據球面定理計算出東西方向的距離差為：

則可以計算出各個旅游景點之間的距離。

以點0表示出發點,稱為原點，點1，2，…，n表示n個該游客需訪問的景點。dij表示景點i到景點j的距離；xij=1表示該游客需要從景點i到景點j，因為該游客一定離開某一個景點去另一個景點，所以i≠j；xij=0表示不需要從景點i到景點j；ui表示旅游景點的順序數。

其中輔助條件ui（i=1，2，…，n）可以是連續變化的，顯然這些變量在最優解中是普通的整數值。以總行程最短為原則，利用整數規劃模型可求得各景點的旅行優先順序。編寫LINGO程序如下：

4　結果

只選取xij=1的結果，求得最優解為456.6公里，該游客的旅游路線如圖2所示。

圖2　旅游線路

顯然這是一個循環圈，無論從哪個景點開始，順序或逆序長治市旅游線路的總行程長度都是456.6公里。

［1］姜啟源,謝金星,葉俊.數學模型［M］.北京:高等教育出版社,2003.80-90.

［2］甘應愛,田豐,李維錚.運籌學［M］.北京:清華大學出版社,2005.126-130.

［3］于東凱,劉玉樹.基于平面圖的最短路徑算法的研究［J］.北京理工大學學報,2001，21（1）:31-34.

［4］謝金星,薛毅.優化模型與LINDO/LINGO軟件［N］.北京:清華大學出版社,2005.124-186.

（責任編輯趙巨濤）

O224

A

1673-2014（2016）05-0026-03

山西省高校科技開發項目（2013158）；長治學院教學研究項目（JY201602）。

2016—07—13

郭偉（1982—），男，山西長治人，講師，碩士，主要從事基礎數學教學與研究。