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

王　旭,陳金陽,阮曉莉

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

?

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

王旭,陳金陽,阮曉莉

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

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

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

1　問題背景

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

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

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

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

2.1問題簡述

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

2.2模型建立

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

2.3模型求解

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

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

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

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

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

表1　區(qū)域劃分表

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

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

表2　最短路程表

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

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

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

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

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

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

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

3　小結

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

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

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

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

[4]汪曉銀，周保平．數(shù)學建模與數(shù)學實驗[M]．北京：科學出版社，2011．

[5]韓忠庚．數(shù)學建模競賽——獲獎論文精選與點評[M]．北京：科學出版社，2012．

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

[7]姜啟源，謝金星，葉俊．數(shù)學模型(第三版)[M]．北京：高等教育出版社，2005．

[8]王庚，王敏生．現(xiàn)代數(shù)學建模方法[M]．北京：科學出版社，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

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

王旭(1991—)，男，湖北荊州人，碩士研究生，主要研究方向為運籌學與控制論.

O221

A

1009-2714(2016)02- 0064- 03

10.3969/j.issn.1009-2714.2016.02.014