旅游路线规划问题

王　旭,陈金阳,阮晓莉

(湖北师范大学 数学与统计学院，湖北 黄石　435002)



旅游路线规划问题

王旭,陈金阳,阮晓莉

(湖北师范大学 数学与统计学院，湖北 黄石435002)

为研究最佳旅游线路设计问题，通过建立网络图模型，利用Dijkstra算法及哈密顿回路法，分析、计算比较得出最优解.

最短路径树； Dijkstra算法；哈密顿回路法；改良圈算法

1　问题背景

旅游活动正在成为全球经济发展的重要动力之一，它加速国际资金流转和信息、技术管理的传播，创造高效率消费行为模式、需求和价值等。随着我国国民经济的快速发展，人们生活水平得到很大提升，越来越多的人积极参与有益于身心健康的旅游活动.

科学的旅游路线，有助于旅游景区之间的相互对比，统筹配置，这是旅游业发展到一定程度之后必须面对和解决的问题，也使得旅游者的需求达到更大程度的满足.现在在国内已经有了一些研究成果，徐锋等在文献[1]中提出了一种基于改进蚁群算法的旅游路线规划问题，主要解决旅游景区的负载均衡问题. 栗雪娟等在文献[2]中采用了Hopfield神经网络的算法和优化模型，基于地图上的几何坐标来规划最佳旅游线路. 李丽华等在文献[3]中以秦皇岛市旅游路线的优化问题为例，利用二叉树算法，求出其旅游路线的优质解.

这些算法的研究主要集中在某个较小景区内最优线路的设计问题上，没有考虑到景区之间的距离，以及旅游的时间安排. 本文旨在研究全国(全球)旅游线路的最佳出行方式，包括线路安排，时间安排等，通过网络图模型理论，设计最优的旅行路线，为自驾游爱好者及旅游社提供方便.

2　最优(时间最短)线路规划模型

2.1问题简述

假设旅游者在西安居住，希望用最短的时间自驾游遍全国201个5A级景区. 出行过程中有以下几个条件：(1)每次旅游时间不超过T1d；基于个人旅游偏好确定了在每个5A级景区最少的游览时间为T2d；(2)行车时间限定于每天7:00-19:00，每天开车时间不超过8 h；若全天游览，开车时间不超过3 h，半天游览，开车时间不超过5 h；景区开放时间统一为8:00-18:00；(3)采用高速优先的策略，高速公路上的平均速度为V1km/h，普通公路上的行车平均速度为V2km/h；(4)每个省会城市至少停留T3d(为了安排专门时间去游览城市特色建筑和体验当地风土人情)。

2.2模型建立

即求游遍全国所有5A景区最少的出行次数n，满足每次出行不超过T1d.

2.3模型求解

为了简化计算，首先制定如下旅游规则：

规则1(分区旅游)：将全国28个省市以出发地(西安)为中心,按地域大致化为西北、西南、东北、东南4个区域，分区域规划旅游线路.

规则2(完整旅游)：每个景点若能在有效时间内一次游完，则全部游完或者路过.若不能一次游完，则分k次游完，则前k-1次专游该省市.

规则3(由远及近旅游)：对每个区域的省市，距离出发地最远的省市最先游览.

根据规则1，将全国28个省市按地域化为4个区域(以出发地西安为中心)：西北、西南、东北、东南，每个区域包含的省市如表1：

表1　区域划分表

下面以西北地区为例，来说明求解过程.

1.利用Dijkstra算法求出发点(西安)到西北各省之间的最短路程，可得到路上花费的时间如表2：(假设全程高速V1=90km/h，每次出行时间最多T1=15 d)。

表2　最短路程表

根据规则3知先游新疆，每次在新疆境内最多游8 d .

利用哈密尔顿改良圈算法得到新疆境内具体的最佳旅游线路：

路线一(乌鲁木齐北疆7日游)：

路线二(乌鲁木齐南疆7日游)：

路线三(乌鲁木齐南疆4日游)：

故新疆要分三次游览，前两次(线路一，线路二)专游新疆，第三次新疆游4 d，西安游3 d.

类似地，游览银川需要4 d，西宁3 d，兰州5 d，总共12 d，此外加上西安共4个城市存在省际最优哈密顿回路(3 d)，总计天数为15 d在规定时间内游完.

3　小结

本文建立了单目标的优化模型，将各景点的路线转化为纯数学形式的点线集合，进行了图论方面的分析，利用Dijkstra算法求最短路程来设计时间最短的最佳旅游线路. 此模型可以通过修改赋权图的权值(路程变为费用)，推广应用到设计费用最少的最佳路线.

[1]徐锋，杜军平．改进蚁群算法在旅游路线规划中的应用研究[J]．计算机工程与应用,2009, 45(23)：193～195．

[2]栗雪娟，崔尚森，张柯．最佳旅游路线选择的神经网络方法[J]．交通与计算机,2006,24(5)：103～106．

[3]李丽华，陈丽萍，刘新荣．运用二叉树方法优化旅游路线[J]．湖南冶金职业技术学院学报,2005,5(2)：197～199．

[4]汪晓银，周保平．数学建模与数学实验[M]．北京：科学出版社，2011．

[5]韩忠庚．数学建模竞赛——获奖论文精选与点评[M]．北京：科学出版社，2012．

[6]肖华勇．实用数学建模与软件应用[M]．西安：西北工业大学出版社，2008．

[7]姜启源，谢金星，叶俊．数学模型(第三版)[M]．北京：高等教育出版社，2005．

[8]王庚，王敏生．现代数学建模方法[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)，湖北师范学院研究生创新科研基金项目.

王旭(1991—)，男，湖北荆州人，硕士研究生，主要研究方向为运筹学与控制论.

O221

A

1009-2714(2016)02- 0064- 03

10.3969/j.issn.1009-2714.2016.02.014