長(zhǎng)治市旅游線路的優(yōu)化模型

郭偉，常金勇

（1.長(zhǎng)治學(xué)院數(shù)學(xué)系，山西長(zhǎng)治046011；2.中國(guó)科學(xué)院信息工程研究所，北京，100093）

長(zhǎng)治市旅游線路的優(yōu)化模型

郭偉1，常金勇2

（1.長(zhǎng)治學(xué)院數(shù)學(xué)系，山西長(zhǎng)治046011；2.中國(guó)科學(xué)院信息工程研究所，北京，100093）

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

旅游線路；優(yōu)化模型；LINGO

1　引言

某位旅游愛(ài)好者打算在暑假期間到長(zhǎng)治市各個(gè)縣城的一些著名景點(diǎn)旅游。在山西省長(zhǎng)治市周邊的11個(gè)縣中，各選取了1個(gè)具有代表性的旅游景點(diǎn)。他計(jì)劃把長(zhǎng)治市各個(gè)縣城的最著名的景點(diǎn)旅游一遍，最后回到出發(fā)地，請(qǐng)問(wèn)該游客應(yīng)該選擇怎樣的旅游路線[1]，才能使他的總行程最短？

2　模型簡(jiǎn)介

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

3　模型建立

3.1模型假設(shè)

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

2、繪制路線圖時(shí)，把各景點(diǎn)的路線看做一個(gè)賦權(quán)的平面圖[3]。

3、i：第i個(gè)景點(diǎn)，i=1，2，…，11

j：第j個(gè)景點(diǎn)，j=1，2，…，11

dij：第i個(gè)景點(diǎn)與第j個(gè)景點(diǎn)之間的距離

3.2模型的建立與求解

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

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

表1　各個(gè)縣城所選的著名旅游景點(diǎn)

記沁源縣靈空山編號(hào)為1，其它景點(diǎn)依次編號(hào)為2、3、…、11，最后回到出發(fā)地，再重復(fù)時(shí)的編號(hào)為12。通過(guò)Google電子地圖，查到各個(gè)景點(diǎn)的地理坐標(biāo)（經(jīng)度和緯度）如表2所示。

表2　各個(gè)著名旅游景點(diǎn)所在的地理位置

下面必須求出任意兩個(gè)景點(diǎn)之間的實(shí)際距離。雖然地球不是一個(gè)標(biāo)準(zhǔn)的球體，但南北與東西長(zhǎng)度相差不大，可以假設(shè)地球?yàn)橐粋€(gè)球體，球體半徑R=6371229公里。根據(jù)球面定理計(jì)算出東西方向的距離差為：

則可以計(jì)算出各個(gè)旅游景點(diǎn)之間的距離。

以點(diǎn)0表示出發(fā)點(diǎn),稱為原點(diǎn)，點(diǎn)1，2，…，n表示n個(gè)該游客需訪問(wèn)的景點(diǎn)。dij表示景點(diǎn)i到景點(diǎn)j的距離；xij=1表示該游客需要從景點(diǎn)i到景點(diǎn)j，因?yàn)樵撚慰鸵欢x開(kāi)某一個(gè)景點(diǎn)去另一個(gè)景點(diǎn)，所以i≠j；xij=0表示不需要從景點(diǎn)i到景點(diǎn)j；ui表示旅游景點(diǎn)的順序數(shù)。

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

4　結(jié)果

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

圖2　旅游線路

顯然這是一個(gè)循環(huán)圈，無(wú)論從哪個(gè)景點(diǎn)開(kāi)始，順序或逆序長(zhǎng)治市旅游線路的總行程長(zhǎng)度都是456.6公里。

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

［2］甘應(yīng)愛(ài),田豐,李維錚.運(yùn)籌學(xué)［M］.北京:清華大學(xué)出版社,2005.126-130.

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

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

（責(zé)任編輯趙巨濤）

O224

A

1673-2014（2016）05-0026-03

山西省高?？萍奸_(kāi)發(fā)項(xiàng)目（2013158）；長(zhǎng)治學(xué)院教學(xué)研究項(xiàng)目（JY201602）。

2016—07—13

郭偉（1982—），男，山西長(zhǎng)治人，講師，碩士，主要從事基礎(chǔ)數(shù)學(xué)教學(xué)與研究。