基于ACO的智能旅游景区路线规划系统设计

郝 标，谭云兰，王伟年，贾金原



基于ACO的智能旅游景区路线规划系统设计

郝 标1，*谭云兰2，王伟年3，贾金原1

（1.同济大学软件学院，上海 201804；2.井冈山大学电子与信息工程学院，江西，吉安 343009；3.井冈山大学商学院，江西，吉安 343009）

针对目前旅游景区路线系统因景点数量多、景点间差异度大而导致线路规划不合理等问题，对路线规划算法和实现方案进行研究，并提出了交互式智能旅游路线规划系统的解决方案。通过研究ACO蚁群优化算法(Ant Colony Optimization)、百度地图API接口、Bootsrap等技术，改进ACO算法模型，引入流式栅格布局，架构了基于B/S架构的系统平台。实验结果表明，基于改进的ACO和百度地图所架构的路线规划系统在国内大规模景点规划方面具有规划速度快、规划结果合理、信息显示全面等优点。

ACO算法；旅游路线规划；交互式系统；百度地图

随着互联网产业的蓬勃发展，旅游产业科技化含量也越来越高，基于web3d技术的虚拟旅游[1]已经让旅游突破了传统的模式有了新的意义，而无论对于实体旅游还是虚拟旅游，合理的旅游规划都显得特别重要。针对目前旅游景区路线系统因景点数量多、景点间差异度大而导致线路规划不合理等问题，本文通过对蚁群算法[2-3]的研究提出了综合考虑多因素的、可以完成大规模景点规划的交互式智能旅游规划系统。系统采用了目前流行的B/S架构，集成了php、html5、javascript、css、ajax等技术，并引入了Bootstrap框架和百度地图API接口，并接入井冈山虚拟漫游平台。井冈山虚拟漫游平台是建立在现实旅游景观基础上的，通过模拟现实景观而打造的一个集虚拟旅游、旅游信息展示、电子商务、虚拟社区、全景漫游管理、旅游信息管理系统、电子商务管理系统和虚拟社区管理系统于一体的综合型虚拟旅游网站[4]。交互式智能旅游规划系统作为井冈山虚拟漫游平台的一个主干模块，开发过程中充分考虑了与系统其它模块之间的数据共享以及数据通信，为系统的其它模块以及整个系统的高质量开发打下坚实基础。

1 系统架构

由于传统的C/S架构存在需要安装客户端、对系统硬件要求比较苛刻、安装复杂等缺点，本系统采用当前已被广泛应用的B/S架构(浏览器和服务器结构)来实现，是WEB兴起后的一种网络结构模式，由于WEB浏览器是客户端最主要的应用软件，这种模式统一了客户端，将系统功能实现的核心部分集中到了服务器上，简化了客户端电脑载荷，减轻了系统维护与升级的成本和工作量，降低了用户的总体成本，而且可以满足用户随时随地使用本系统的需求。

图1 系统架构图

本系统完整架构设计包括后端设计和前端设计，考虑到与井冈山虚拟旅游系统开发平台WordPress的兼容性，后端设计采用PHP和MySQL数据库进行开发，主要实现的后台功能包括前端基本设置、景点信息管理、景点网络化管理、登录用户管理以及预开发功能社交系统评介管理、云端信息同步管理、基于XML的管理后台定制等。前端设计主要负责实现与用户的交互，通过百度地图的API向用户直观地展现景点信息并对用户的旅游偏好进行采集，根据与用户的交互结果以及后台数据库数据，通过蚁群算法智能推荐路线并友好的将结果展示给用户。

2 智能规划算法及数据模型设计

2.1 基于Floyd的智能规划前置算法设计

Floyd算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法，其原理是动态规划。为了给蚁群算法提供满足算法条件的数据，采用如下算法描述对景点数据进行预处理：

2.2 智能规划算法设计

为了更好的完成路线智能规划，系统采用仿生学算法蚁群算法[5]，即Ant Colony Optimization，ACO是一种用来在图中寻找优化路径的仿生线性优化算法，具有并行性、正反馈性和全局极小搜索能力强等特点。它由Marco Dorigo于1992年在他的博士论文“Ant system: optimization by a colony of cooperating agents”中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，主要用来解决TSP问题，在现实的应用中，对于解决调度问题、车辆路径问题、分配问题、设置问题、数据聚类分析以及电信路由问题方面都有较好的表现。

蚁群算法是受自然界中真实蚂蚁的行为启发而提出的一种仿生学算法，其基本思想是对蚂蚁寻找食物的过程进行模拟，并加入一些制约因素。蚂蚁个体之间是通过一种称之为信息素的物质进行信息传递的，模拟若干蚂蚁，每只蚂蚁在解空间中独立寻找解，并在其所寻找的解上留下信息素，解的性能越好，留下的信息素也就会越多，根据蚂蚁路径选择模型，信息素越多的解被再次选择的概率也就越大，通过正反馈，会有越来越多的蚂蚁选择该解，理想的情况下最后所有的蚂蚁都会选择该路径，整个系统收敛到该解，即最优解。

对蚁群算法的模拟过程如下，首先假设有只蚂蚁，对于每个蚂蚁，它会根据结点距离和连接边上信息素的数量等为变量的概率函数选择下一个结点，通过禁忌表阻止蚂蚁访问已访问的结点，蚂蚁周游一周后会在每条访问的边上留下信息素。初始时刻各条路径上信息素都相等为常数。蚂蚁在运动过程中，根据各条路径上的信息素量决定转移方向，表示在时刻蚂蚁由位置转向位置的概率，

(2)

2.3 智能路线规划数据模型设计

为了完成兼顾所有因素的路线智能推介，需要对蚁群算法进行改进，将算法中的参数替换为自己的模型，按照设计需求，需要考虑的因素包括景点到景点之间的距离，参观过景点的游客对景点的推荐度，景点的星级，景点是否适宜当前季节旅行，景点参观需要花费的时间，景点的管理员调整参数，通过以上因素综合考虑，可以推荐出最适合用户的路线规划结果。参数模型为：

图2 数据处理流程图

Fig.2 Data process flow chart

3 用户交互界面构建

3.1 交互前端构建

考虑到目前市场上浏览器种类纷杂，如Chrome、Firefox、IE、Safari、360浏览器等，每种浏览器对W3C标准的遵循程度都不同，甚至同一浏览器的不同版本对js和css的解析也不同。为了尽可能的兼容更多的浏览器和不同分辨率的显示器，同时也为了满足系统本身景点较多，友好直观展示出众多景点关系有一定挑战性的问题，系统开发过程中引入了Bootstrap框架[7]。Bootstrap是Twitter推出的一个开源的用于前端开发的工具包。它由Twitter的设计师Mark Otto和Jacob Thornton合作开发，是一个CSS/HTML框架。Bootstrap提供了优雅的HTML和CSS规范，它是由动态CSS语言Less写成，其一直是GitHub上的热门开源项目。Bootstrap中包含了丰富的Web组件，包括下拉菜单、按钮组、按钮下拉菜单、导航、导航条、面包屑、分页、排版、缩略图、警告对话框、进度条、媒体对象等，系统开发过程中采用了bootstrap的流式栅格布局，并引入了轻量级导航条、缩略图、模态、模态对话框、按钮组等组件。

图3 流式栅格布局效果

3.2 路线规划交互地图构建

交互地图的构建无论对于用户交互选择景点还是向用户直观清晰的展示景点网络结构、景点详情都至关重要，交互地图的构建主要需要完成地图创建、地图配置、景点坐标拾取、景点信息展示、景点拖拽选择以及路径规划结果展示等几大功能，需要使用百度地图API、百度地图坐标拾取系统以及HTML5新的拖拽特性[8]等共同集成实现。

3.2.1 引入百度地图Javascript API

百度地图JavaScript API[9]是一套由JavaScript语言编写的应用程序接口，主要包括基本地图功能、地图控件展示功能、覆盖物功能、工具类功能、定位功能、右键菜单功能、鼠标交互功能、驾车导航功能等大的功能块接口，系统开发过程中采用百度地图1.5版本，开发过程中需要首先通过js脚本将API引入界面中，由于百度地图自1.5之后版本需要申请秘钥，所以需要首先在百度地图官网申请秘钥。引入百度地图脚本如下：

3.2.2 提取景点坐标

由于井冈山景区的景点大部分没有在百度地图上标识，为了在路径规划时能够智能动态显示详细的景点位置，我们使用经纬度来定位井冈山景点位置。而通过GPS照相设备获取的经纬度属于WGS84坐标系，这是一个比较通用的坐标体系，目前国内不能直接使用WGS84坐标，因此百度地图API的经纬度是经过加密偏移的。一般百度地图API默认使用墨卡托投影(Mercator Projection)[10]，由于投影参数不同，同样的墨卡托投影也会有所差别，所以为了在地图中标注所有景点的位置，并不直接通过GPS来获取景点的实际坐标，而是通过百度地图提供的BMap.MercatorProjection类来实现坐标转换，方可在百度地图中获取正确的景点位置信息。本系统开发过程中使用了百度地图拾取坐标系统，通过拾取坐标系统可以很方便的获取所有景点在百度地图中的平面坐标，能在规划界面上准确地显示所有景点的信息和路线规划结果。

3.2.3 创建地图框架

根据百度地图API文档首先通过创建地图容器，然后通过以下脚本创建地图实例。

之后所有的地图控件和覆盖物都需要添加在该容器中，系统根据需要添加了基于Control基类的缩略图控件、比例尺控件和地图类型控件。覆盖物控件是景点显示的重要窗口，首先根据用户选择的条件对符合条件景点在地图中对应的经纬度位置渲染出默认标注红气球，同时在附近创建自定义的覆盖物展示景点信息，浮动显示景点图片和景点介绍信息并完成拖拽选择景点功能的实现。根据百度地图API以及用户的交互结果在地图上展示出最佳的游览线路，路线规划结果支持卫星展示和行政区域展示，用户可以通过两种不同的展示效果更好的识别地形和行政区域。如图4所示, 图4 (a) 是在百度三维地图上进行路线规划的效果图，图4 (b)是在行政区域地图上路线规划的效果图。

(a)Baidu三维地图规划效果

(b)行政区域地图规划结果

图4 路线规划结果展示

Fig.4 Result of route planning

3.2.4 百度地图功能改进

景点拖拽选择实现：鉴于百度地图不支持将景点拖动出地图容器，为了实现景点拖拽功能，首先基于百度地图API创建Maker对象，并在Maker对象上添加onMouseOver监听，实时获取鼠标位置，当鼠标浮动到自定义覆盖物上时，以鼠标位置为中心生成隐藏浮动框，当鼠标click事件被触发时将隐藏的浮动窗口显示出来，并调用HTML5的拖拽特性，从而实现景点的拖拽选择特效。

多景点路线联绘实现：鉴于百度地图并不支持多点规划路线，只支持两点间路线的绘制，为了将多景点的路线规划结果直观的绘制在百度地图上，首先记录智能路线规划算法计算出来的景点顺序，然后将每两点的路线记录下来，再通过百度的Polyline 覆盖物折线基类绘制接口将所有景点间路线按照顺序渲染出来，从而完成对景点规划结果的联绘实现，折线基类构造函数如下：

Polyline(points:Array[, opts:PolylineOptions])

4 结语与展望

目前旅游行业已经拥有各种类型的旅游规划系统，可以完成基础的旅游路线规划功能，但是类似于本系统的综合考虑各个因素的全方位智能旅游规划的并不多见。另外本系统采用蚁群算法进行规划可以实现大规模景点无重叠规划，这也是其它规划算法所不具有的优势和竞争力。系统在未来的完善过程可以通过云端并行计算进一步是提高规划性能，也可以通过数据挖掘技术将社交系统、旅游网站等相关平台的用户数据汇总分析使得旅游规划更加科学，更加可靠。

参考文献：

[1] 谭云兰,贾金原,彭硕,等.基于Web3D的虚拟旅游关键技术研究进展[J].系统仿真学报,2014,26(7): 1541-1549.

[2] Gambardella M, Martinoli M B A, Stützle R P T. Ant Colony Optimization and Swarm Intelligence[C]//5th International Workshop. 2006.

[3] Zheng X, Luo J, Song A. Ant Colony System Based Algorithm for QoS-Aware Web Service Selection[C]// GSEM. 2007: 39-50.

[4] 谭云兰,贾金原,康永平,等.基于 WebVR 的井冈山虚拟旅游系统架构设计[J]. 井冈山大学学报:自然科学版, 2012, 33(6): 46-50.

[5] 段海滨,王道波,朱家强,等. 蚁群算法理论及应用研究的进展[J]. 控制与决策,2004,19(12): 1321-1326.

[6] 高尚. 解旅行商问题的混沌蚁群算法[J]. 系统工程理论与实践, 2005, 25(9): 100-104.

[7] Bootstrap中文网,Bootstrap2文档[EB/OL]. [2014]. http://v2.bootcss.com/getting-started.html.

[8] Lubbers P, Albers B, Salim F, et al. Pro HTML5 programming[M]. New York, NY, USA:: Apress, 2011.

[9] 百度地图,Baidu Map JS API[EB/OL].[2014].http:// developer.Baidu.com/map/index.php?title=Jspopular.

[10] 360百科. 墨卡托投影 [EB/OL]. 2014.http:// baike. baidu.com/view/301981.htm?fr=aladdin.

INTELLIGENT TOURISM ROUTE PLANNING SYSTEM BASED ON ANT COLONY OPTIMIZATION

HAO Biao1,*TAN Yun-lan2, WANG Wei-nian3, JIA Jin-yuan1

(1.School of Software Engineering, Tongji University, Shanghai 201804,China;2.School of Electronic Information and Engineering，Jinggangshan University, Ji’an, Jiangxi 343009, China; 3.School of Business，Jinggangshan University, Ji’an, Jiangxi 343009, China)

The tourism route planning systems are often unreasonable because of a large number of scenic spots and large differences among them. Base on the research about route planning algorithms and their implementation schemes, we proposed a solution of interactive intelligent tourism route planning system. Furthermore, we construct a platform of tourism route planning system on Browser/Server architecture, which is blended several technologies, such as Ant Colony Optimization algorithm, Baidu map API interface and Bootsrap. In addition, we also improved AC Optimization algorithm model and introduced flow grid layout. The experiment and analysis show that the system makes the route planning more reasonable and scientific because Baidu map can provide wider coverage areas, more comprehensive information and higher speed of loading.

Ant Colony Optimization algorithm; tourism route planning; interactive system; Baidu map

1674-8085(2015)01-0008-06

TP391

A

10.3969/j.issn.1674-8085.2015.01.002

2014-09-21；修改日期：2014-12-28

国家十二五计划重大科技支撑项目(2012BAC11B01-04)

郝 标(1989-)，男，河南平顶山人，硕士生，主要从事WEB相关技术研究(E-mail:Brian.Hao211@gmail.com);

*谭云兰(1972-)，女，江西新干人，副教授，博士生，主要从事虚拟现实,图像处理等研究(E-mail: tanyunlan@163.com);

王伟年(1970-)，女，江西吉安人，教授，博士，主要从事旅游规划方面的研究(E-mail: wwnian@126.com);

贾金原(1963-)，男，山东乐陵人，教授，博导，主要从事图形学，分布式虚拟现实，Web3D，游戏引擎等研究(E-mail: jyjia@tongji.edu.cn).