王　旭,陳金陽,阮曉莉

(湖北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，湖北 黃石　435002)

?

旅游路線規(guī)劃問題

王旭,陳金陽,阮曉莉

(湖北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，湖北 黃石435002)

為研究最佳旅游線路設(shè)計(jì)問題，通過建立網(wǎng)絡(luò)圖模型，利用Dijkstra算法及哈密頓回路法，分析、計(jì)算比較得出最優(yōu)解.

最短路徑樹； Dijkstra算法；哈密頓回路法；改良圈算法

1　問題背景

旅游活動(dòng)正在成為全球經(jīng)濟(jì)發(fā)展的重要?jiǎng)恿χ?，它加速國際資金流轉(zhuǎn)和信息、技術(shù)管理的傳播，創(chuàng)造高效率消費(fèi)行為模式、需求和價(jià)值等。隨著我國國民經(jīng)濟(jì)的快速發(fā)展，人們生活水平得到很大提升，越來越多的人積極參與有益于身心健康的旅游活動(dòng).

科學(xué)的旅游路線，有助于旅游景區(qū)之間的相互對比，統(tǒng)籌配置，這是旅游業(yè)發(fā)展到一定程度之后必須面對和解決的問題，也使得旅游者的需求達(dá)到更大程度的滿足.現(xiàn)在在國內(nèi)已經(jīng)有了一些研究成果，徐鋒等在文獻(xiàn)[1]中提出了一種基于改進(jìn)蟻群算法的旅游路線規(guī)劃問題，主要解決旅游景區(qū)的負(fù)載均衡問題. 栗雪娟等在文獻(xiàn)[2]中采用了Hopfield神經(jīng)網(wǎng)絡(luò)的算法和優(yōu)化模型，基于地圖上的幾何坐標(biāo)來規(guī)劃最佳旅游線路. 李麗華等在文獻(xiàn)[3]中以秦皇島市旅游路線的優(yōu)化問題為例，利用二叉樹算法，求出其旅游路線的優(yōu)質(zhì)解.

這些算法的研究主要集中在某個(gè)較小景區(qū)內(nèi)最優(yōu)線路的設(shè)計(jì)問題上，沒有考慮到景區(qū)之間的距離，以及旅游的時(shí)間安排. 本文旨在研究全國(全球)旅游線路的最佳出行方式，包括線路安排，時(shí)間安排等，通過網(wǎng)絡(luò)圖模型理論，設(shè)計(jì)最優(yōu)的旅行路線，為自駕游愛好者及旅游社提供方便.

2　最優(yōu)(時(shí)間最短)線路規(guī)劃模型

2.1問題簡述

假設(shè)旅游者在西安居住，希望用最短的時(shí)間自駕游遍全國201個(gè)5A級(jí)景區(qū). 出行過程中有以下幾個(gè)條件：(1)每次旅游時(shí)間不超過T1d；基于個(gè)人旅游偏好確定了在每個(gè)5A級(jí)景區(qū)最少的游覽時(shí)間為T2d；(2)行車時(shí)間限定于每天7:00-19:00，每天開車時(shí)間不超過8 h；若全天游覽，開車時(shí)間不超過3 h，半天游覽，開車時(shí)間不超過5 h；景區(qū)開放時(shí)間統(tǒng)一為8:00-18:00；(3)采用高速優(yōu)先的策略，高速公路上的平均速度為V1km/h，普通公路上的行車平均速度為V2km/h；(4)每個(gè)省會(huì)城市至少停留T3d(為了安排專門時(shí)間去游覽城市特色建筑和體驗(yàn)當(dāng)?shù)仫L(fēng)土人情)。

2.2模型建立

即求游遍全國所有5A景區(qū)最少的出行次數(shù)n，滿足每次出行不超過T1d.

2.3模型求解

為了簡化計(jì)算，首先制定如下旅游規(guī)則：

規(guī)則1(分區(qū)旅游)：將全國28個(gè)省市以出發(fā)地(西安)為中心,按地域大致化為西北、西南、東北、東南4個(gè)區(qū)域，分區(qū)域規(guī)劃旅游線路.

規(guī)則2(完整旅游)：每個(gè)景點(diǎn)若能在有效時(shí)間內(nèi)一次游完，則全部游完或者路過.若不能一次游完，則分k次游完，則前k-1次專游該省市.

規(guī)則3(由遠(yuǎn)及近旅游)：對每個(gè)區(qū)域的省市，距離出發(fā)地最遠(yuǎn)的省市最先游覽.

根據(jù)規(guī)則1，將全國28個(gè)省市按地域化為4個(gè)區(qū)域(以出發(fā)地西安為中心)：西北、西南、東北、東南，每個(gè)區(qū)域包含的省市如表1：

表1　區(qū)域劃分表

下面以西北地區(qū)為例，來說明求解過程.

1.利用Dijkstra算法求出發(fā)點(diǎn)(西安)到西北各省之間的最短路程，可得到路上花費(fèi)的時(shí)間如表2：(假設(shè)全程高速V1=90km/h，每次出行時(shí)間最多T1=15 d)。

表2　最短路程表

根據(jù)規(guī)則3知先游新疆，每次在新疆境內(nèi)最多游8 d .

利用哈密爾頓改良圈算法得到新疆境內(nèi)具體的最佳旅游線路：

路線一(烏魯木齊北疆7日游)：

路線二(烏魯木齊南疆7日游)：

路線三(烏魯木齊南疆4日游)：

故新疆要分三次游覽，前兩次(線路一，線路二)專游新疆，第三次新疆游4 d，西安游3 d.

類似地，游覽銀川需要4 d，西寧3 d，蘭州5 d，總共12 d，此外加上西安共4個(gè)城市存在省際最優(yōu)哈密頓回路(3 d)，總計(jì)天數(shù)為15 d在規(guī)定時(shí)間內(nèi)游完.

3　小結(jié)

本文建立了單目標(biāo)的優(yōu)化模型，將各景點(diǎn)的路線轉(zhuǎn)化為純數(shù)學(xué)形式的點(diǎn)線集合，進(jìn)行了圖論方面的分析，利用Dijkstra算法求最短路程來設(shè)計(jì)時(shí)間最短的最佳旅游線路. 此模型可以通過修改賦權(quán)圖的權(quán)值(路程變?yōu)橘M(fèi)用)，推廣應(yīng)用到設(shè)計(jì)費(fèi)用最少的最佳路線.

[1]徐鋒，杜軍平．改進(jìn)蟻群算法在旅游路線規(guī)劃中的應(yīng)用研究[J]．計(jì)算機(jī)工程與應(yīng)用,2009, 45(23)：193～195．

[2]栗雪娟，崔尚森，張柯．最佳旅游路線選擇的神經(jīng)網(wǎng)絡(luò)方法[J]．交通與計(jì)算機(jī),2006,24(5)：103～106．

[3]李麗華，陳麗萍，劉新榮．運(yùn)用二叉樹方法優(yōu)化旅游路線[J]．湖南冶金職業(yè)技術(shù)學(xué)院學(xué)報(bào),2005,5(2)：197～199．

[4]汪曉銀，周保平．?dāng)?shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)[M]．北京：科學(xué)出版社，2011．

[5]韓忠庚．?dāng)?shù)學(xué)建模競賽——獲獎(jiǎng)?wù)撐木x與點(diǎn)評[M]．北京：科學(xué)出版社，2012．

[6]肖華勇．實(shí)用數(shù)學(xué)建模與軟件應(yīng)用[M]．西安：西北工業(yè)大學(xué)出版社，2008．

[7]姜啟源，謝金星，葉?。?dāng)?shù)學(xué)模型(第三版)[M]．北京：高等教育出版社，2005．

[8]王庚，王敏生．現(xiàn)代數(shù)學(xué)建模方法[M]．北京：科學(xué)出版社，2008．

Research on the tourism route planning

WANG Xu, CHEN Jin-yang, RUAN Xiao-li

(College of Mathematics and Statistics, Hubei Normal University, Huangshi435002,China)

Through the establishment of the network graph model,by use of Dijkstra algorithm and Hamiltonian circuit,the author conducted analysis,calculation and comparison to get the optimal solution for the design of the best tourist route.

The shortest path tree; Dijkstra algorithm; Hamiltonian Circuit; circle modification algorithm

2016—02—22

國家自然科學(xué)基金項(xiàng)目(61304057，11471105)，湖北省教育廳青年項(xiàng)目(Q20142501)，湖北師范學(xué)院研究生創(chuàng)新科研基金項(xiàng)目.

王旭(1991—)，男，湖北荊州人，碩士研究生，主要研究方向?yàn)檫\(yùn)籌學(xué)與控制論.

O221

A

1009-2714(2016)02- 0064- 03

10.3969/j.issn.1009-2714.2016.02.014