基于蚁群算法的旅游线路优化

刘训星，胡 敏，黎 颖

(宣城职业技术学院， 安徽 宣城 242000)

基于蚁群算法的旅游线路优化

刘训星，胡 敏，黎 颖

(宣城职业技术学院， 安徽 宣城 242000)

旅游成为当今休闲放松的重要方式，每位旅客受空间、时间和经济能力限制具有不同需求，因此游客面临的首要问题就是选择适合的旅游线路。针对宣城市丰富的旅游资源，利用蚁群算法对13个特色景点进行线路规划，然后建立带约束线路规划模型，并通过评价分析求得最优结果。实验表明：该方法能为不同游客推荐不同需求的旅游线路。

蚁群算法; 线路规划; 旅游; 线路优化

随着老百姓生活水平的提高，旅游已成为最时尚的休闲活动，怎样在假期有限、预算不增加的情况下游玩更多的景点是广大旅游爱好者迫切需要解决的问题，所以景点路径规划十分必要，有助于游客寻找最佳旅游路线。

旅游路径规划从区域范围可以分为3个部分：城市之间的旅游路径规划、 城市内各景区的旅游路径规划、 景区内各景点的旅游路径规划。 城市之间的旅游路径规划和景区内各景点的旅游路径规划都是从一点出发，经过其他点，且只经过一次，最后回到出发点的路线规划，即TSP 回路问题。这是一个经典的NP难题，所以解决方法非常多。其中包括：蚁群算法、退火算法、遗传算法、粒子群算法和禁忌搜索算法等。对景点路径规划的研究有助于解决很多类似路径规划问题，所以研究景点路径规划问题具有重要意义。

目前路径规划已经在工业、物流方面大规模应用，国内外学者开展了深入研究，提出许多算法[1]和方案，包括启发式搜索、蚁群算法[2]、Dijkstra、神经网络。宣城市是文房四宝之乡，有着丰富的旅游文化资源，文中首次将蚁群算法应用到宣城市文房四宝文化旅游线路规划，通过在宣城市旅游信息平台的应用，得出了最佳的旅游路线。

1 旅游信息服务平台技术设计分析

1.1 Andriod系统

Andriod系统主要用于平板、手机智能移动终端，具有性能卓越、开源、市场占有率高等特点。Andriod系统具有以下优势：① 任意移动终端生产商能够自由融入Andriod联盟。② Andriod系统具有开源免费的特点，有利于第三方软件开发。③ 用于开发第三方软件，程序java语言也具有开源免费的特点。

Andriod系统提供多种存储方式：文件存储、内容提供器、网络存储[3]和Sqlite存储，文房四宝文化旅游系统采用Sqlite存储数据。

Sqlite具有操作方便、灵活高效、跨平台等特点，能够嵌入应用程序中关联数据库。Sqlite在同一进程空间服务器和客户端同时运行，在应用程序运行时无需管理和网络配置。Sqlite使用权限只与文件系统有关。Sqlite由于高效占用内容空间小，非常适合用户移动终端，在使用过程中只需把Sqlite编译到文房四宝文化旅游信息服务平台中。

Sqlite数据库架构由接口、编译器、虚拟机、后端组成。① 接口：用于Sqlite与文件、程序交互的接口。② 编译器：先对查询语句检查，然后转化语法树，接着生成汇编代码，最后交由虚拟机运行。③ 虚拟机：用于解释运行代码，完成特定的操作。④后端：管理运行数据，搜索数据维系页面关系。

1.2 Web Service

Web Service是一种跨平台应用程序。移动终端及网络终端都能够同时使用Web Service方法。Web Service具有以下优势：① 数据交换更加便利，适合异构系统间数据交换和通信。② 使用了XML技术对对数据进行封装，使用者仅能看到功能列表。③ 用标准的方法把不同语言开发和不同平台程序集成起来。文中将采用Web Service来获取移动终端信息，管理数据库和生成具有导航功能的地图。

1.3 蚁群算法

蚁群算法由Marco Dorigo等[4]受蚂蚁觅食启发提出的一种随机智能算法。蚂蚁在没有辅助的情况下找到巢穴至食物最短路径，蚂蚁选择路径的过程是一种正反馈机制。旅客在不同景点游玩与蚂蚁觅食有惊人的相似处，所以蚁群算法适用于景点间路径规划。

蚂蚁算法的优势表现在以下几个方面：① 蚂蚁算法能够用来解决至今没有找到合适算法的问题。② 蚂蚁算法采用启发式思维算法框架。③ 蚂蚁算法是近似算法，具有较大弹性，可以针对不同应用问题加以改进，运用到不同领域。

蚁群算法应用领域很广泛，刘利强等研究在水下三维空间路径规划；朱庆保研究机器人路径规划；张维泽等研究物流配送规划；王慧等[5]研究旅游线路规划。

2 旅游信息服务平台功能设计分析

2.1 系统框架设计

文房四宝旅游文化信息服务系统中客户端采用Android系统使用Sqlite数据库，服务器采用linux系统使用mysql数据库，实现了多媒体播放、电子地图、天气查询、交友等功能。

图1 旅游信息平台框架

2.2平台功能模[6]块设计

1) 定位、显示附近用户

定位：① 首先使用MyLocation Overlay类创建对象，在列表中添加创建对象。② 定时将自己最新位置发送到服务器，以便其他用户获取。

显示附近用户：首先，向服务器申请获取附近用户位置；其次，服务器向用户移动终端返回JSON的字符串，解析字符串封装成对象加入到附近用户列表；最后，修改Constant类，在用户客户端显示附近用户。

2) 地图应用

百度地图API[7]使用JavaScript实现程序接口。程序员通过接口使用百度地图数据和服务，创建功能全变应用程序。① 下载API包，百度地图API包含libBMapApiEngine.so 和baidumapspi.jar两个文件。② 程序使用百度地图API进行开发，需要使用百度地图提供用于开发类库，只有拥有API密钥才能使用百度地图提供的类，所以需要申请API Key。③ 先将上述两个包拷贝到工程目录下，然后将baidumapapi.jar导入应用工程，最后将mapapi.Mapview加入布局文件里。④ 使用蚁群算法规划行程路线。⑤ 将规划线程显示在地图上。

3) 旅游路线规划

① 旅游景点信息

通过poilist类实现，首先读取用户信息；其次在客户端通过listview将景点信息展现出来；最后根据游客操作记录游客对景点的偏好。

② 线路规划

景点路线规划的结果通过两种方式展示：第1种，通过旅客游玩先后顺序显示各个景点；第2种，直接在百度地图上显示。

图2 景点线路规划流程

4) 多媒体应用[8]

通过预览景区图片、播放景区视频，能够提供景区四季景色和景区历史图片。Android提供丰富的编码格式，能够方便地将音频、图片、视频等集成到应用程序中。

① 音频播放功能

通过audioframeactivity类创建景点音频信息列表，再使用audioplayactivity类播放音频列表中的音频。

图3 Audioplayactivity与audioframeactivity通信流程

② 图片浏览功能

通过pictureviewactivity和pictureframeactivity展示游客选择图片。Pictureframeactivity继承listactivity类，使用simpleadapter绑定显示的数据。Pictureviewactivity主要使用gallery组件和imageswitcher组件。首先使用findviewbyid()方法引用switcher；其次使用setfactory()方法视图切换；接着使用setoutanimation()方法和setinanimation()方法设置图片切换动画效果；最后使用setadpter()方法设置imageadapter。

③ 视频点播功能

通过videoplayactivity类和videoframeactivity类实现。Videoframeactivity用于显示景点风景的经典图片、景点相关介绍和视频大小。Videoplayactivity定义3个runnable对象，用于视频播放开始计数、重置和暂停。视频播放核心代码如下：

Runnable rnable1,rnable2,rualbe3;

run(){

counts=counts+1

t.setText(ntime2(counts));

handler.postDelayer(this,2000);

}

handler.removeCallbacks(rnalbe2);

handler.removeCallbacks(rnalbe1,2000);

handler.removeCallbacks(rnalbe3);

5) 天气查询应用

系统借助景点的经纬度坐标使用Google Weather API查询景点天气，先输入景点的经纬度，Google Weather API返回xml文件，然后解析xml文件，Android系统有SAX、DOM、XMLPull 3种方式解析xml文件,使用方便、占用资源少，本系统采用XMLPull方式解析xml文件。

6) 游记应用

游记应用模块为旅游者提供发表旅游过程中心情、感悟的功能。包括文章题目、时间、图片和文字。为了实现游记功能，首先实现游记信息发布功能(recordactivity类)；其次实现信息修改功能(recordeditactivity类)；最后实现sqlite数据库操作功能(dbadapter类)。

recordactivity类实现游记信息发布，通过listview组件布局，使用renderlistview()显示信息数据，使用onemenuitemselecter()方法建立(creatediary())、删除(deleteDiary())游记信息，最后使用recordeditactivity类onactivityresult()方法使得界面与数据信息保持一致。

3 行程规划算法

3.1析规划行程模型[9]

(1)

(2)

(3)

式中:C表示旅游花费，T表示旅游时间，R={S1,S2,…,Sn-1,Sn}是一条符合旅游需求的路线。d(i)表示提前到达景点等待所花时间。t0(i)表示景点开门时间，ta(i)表示到达景点时间，tp(i)表示景点闭门时间。

(4)

式中:ω0表示旅游时间与费用关系的权重参数，Tmax代表可支配最长时间，cmax代表可消费最大预算。

3.2 构建行程路线

(5)

式中：C表示常数，w(u)表示景点营业时间约束段旅客吸引度。

(6)

式中:P(i,j)代表景点选择概率；α代表信息浓度约束重要性；β代表启发式信息约束重要性；υ代表开放时间约束重要性。

(7)

(8)

式中:γ1代表时间约束重要性；γ2代表花费约束重要性；η(i,j)代表路径启发式信息。

j=arg maxpk(i,j)

(9)

若q≤q0，下个景点j由式(9)确定；若q>q0，下个景点j由式(4)获得选择概率，然后使用轮盘赌方式确定。

3.3 更新行程信息素

τ(i,j)=(1-ρ)τ(i,j)+Δτ(i,j)

(10)

式中：ρ表示信息素减少度，取值范围为0<ρ≤1。Δτ(i,j)代表形成路线信息素升高度。

(11)

式中Φ(R)表示评价路线的目标函数。

4蚁群算法在文房四宝旅游信息平台应用

4.1实验数据

宣城市是文房四宝之乡，有着丰富的旅游资源，从中选择有代表性的景点13处：① 中国鳄鱼湖，② 恩龙世界木屋村，③ 皖南事变烈士陵园，④ 安徽宣砚文化有限公司，⑤ 中国宣纸文化园，⑥ 桃花潭风景区，⑦ 绩溪龙川景区，⑧ 夏林风景区，⑨ 太极洞风景名胜区，⑩ 江村古建筑群，徽杭古道，敬亭山风景名胜区，宁国华东大裂谷。

4.2蚁群算法[10]应用

1) 经纬度

查阅资料获得上述景点的经度与纬度。

只获取经纬度还不够，还必须计算出景点间距离,τdp表示单个景点旅客游玩时间，时间是根据景点类型和景点景区大小粗略估计，游客一天游玩时间以9h计算。

2) 景点间距离

C=sin(90-X(i))sin(90-X(j))·

cos(Y(i)-Y(j))+

sin(X(i))sin(X(j))

(12)

distance(i,j)=R·αcos(C)·π/180

(13)

式中:X(i)表示经度，Y(i)表示纬度，R表示地球半径，distance(i,j)表示景点i与景点j的距离。

运用式(6)～(13)进行计算，结果见表1。

表1 景点与经纬度

4.3 路线规划

假设：① 实验运行参数值如表2所示。② 旅客一天游玩有效时间为8小时。③ 总共运行8次。

在使用蚂蚁算法8次求解中，从表3能够看出：① 得到高质量的解。在所有解中最好的为91.85 km。② 计算结果比较稳定，最差解比最好解多2.71%。③ 平均求解用时为2.17 s，求解效率较高。④ 线路1:0—1—12—9—0；线路2:0—5—3—6—0；线路3:0—10—4—7—11—0；线路4:0—2—13—8—0。通过以上可以看出：使用蚂蚁算法可以得到比较理想的结果。

图4 景点分布

名称Mnτmaxτij游玩最大路程游玩最小路程αβγρ1ρ2Q1Q2Q3γ0值8040101505110.50.850.9510501001

表3 实验结果

4.4 评价路线

通过使用蚂蚁算法得到理想状态下的4条路线，然而在实际旅游过程中还需要考虑游客对景点评价、交通状况、景点门票和住宿等费用。

1) 景点等级(g)。依据国家旅游网景区等级划分、宣传宣城“文房四宝之乡”的意义、景点人气和景点开发时间并给予评定，分为4个等级，系数分别是1.1、1.2、1.3、1.4。

2) 交通状况(t)。依据道路性质、旅游资源配套设施、“携程旅行网”游客反馈意见和对我校导游专业学生调查问卷，通过汇总分析。分为5个等级，系数分别是0.6、0.7、0.8、0.9、1.0。

3) 费用水平(c)。依据景区门票价格、住宿花费、餐饮花费，分为3个等级，系数分别为0.9、1.0、1.1。

4) 景区影响力综合指数是衡量景点对游客吸引力综合评价指标(f)。

(14)

式中:fi为景区影响力综合指数；ρ为花费超支惩罚系数；gi为景点等级指数；μ为景区人气缩放系数；ti为交通状况及配套设施综合评价指数；ci为景区消费指数；γ为景区消费缩放系数。

考虑交通、景点影响力和花费等多方面影响，运用蚂蚁算法得出理想旅游线路，重新评价分析得出以下结论：线路1:0—1—12—9—0，路线景点影响力综合评价1.17；线路2:0—5—3—6—0，路线景点影响力综合评价0.96；线路3:0—10—4—7—11—0，路线景点影响力综合评价0.95；线路4:0—2—13—8—0，路线景点影响力综合评价0.99。通过综合分析得出：线路1线路4线路2线路3，因此最佳旅游线路为线路1：0—1—12—9—0。

表4 景点影响力指数

5 结束语

本文提出了基于蚂蚁算法的文房四宝旅游信息服务平台的建设，能够为旅游爱好者提供便捷、人性化的服务，有助于“山水诗乡，多彩宣城”旅游产业又快又好的发展。

蚁群算法应用在宣城市文房四宝旅游平台应用，体现出蚁群算法在景点数量较少时规划路径的优越性。文中介绍了蚁群算法路径规划的思想和算法，结合“山水诗山，多彩宣城”丰富的旅游资源和独特的文化底蕴，为广大旅客寻找到符合各自需求的最佳旅游线路。

平台采用Android系统，具有功能实用、界面友好和操作方便等特点，同时还能将该应用开发推广到其他领域，如城智能城市公共交通工具选择、船舶导航和物流配送。该平台还需进一步改进，如将该应用程序与微信、QQ平台融合，有助于该应用程序的推广和完善。完善应用程序可根据用户的独特需求与爱好实现智能路径规划推送功能[11]。

[1] 唐良,方廷键.基于改进蚁群算法的路径规划方法[J].中国科学技术大学学报,2009,39(9):980-984.

[2] 李旭,汪海妹，刘家堡,等.基于蚁群算法的旅游线路优化研究[J].重庆工商大学学报(自然科学版),2015,32(2):67-70.

[3] 舒贤华.基于Android平台的收集Web地图服务设计[D].大连海事大学,2009：128-211.

[4] 段海滨.蚁群算法原理及其应用[M].北京：科学出版社,2015,5-123.

[5] 刘利强,戴运桃，王丽华，等.基于蚁群算法的水下潜器全局路径规划技术研究[J].系统仿真学报,2007,19(18):4174-4177.

[6] 韩瑞东.基于Android的运程“智慧旅游”手机APP应用[J].计算机时代,2016(11):44-47.

[7] 付林，闫强，李祥.基于百度地图的小区域导航实现方案研究[J].计算机技术与发展.2014,24(5):223-226.

[8] 包冬梅.基于Android平台的旅游系统的设计[J].呼伦贝尔学员学报,2016,24(2):92-95.

[9] 睢先先，宋夫华.基ACO的智能旅游行程规划系统设计[J].计算机应用与软件,2016,33(9):231-234.

[10] 王慧,刘昌华，王育玲，等.蚁群算法在旅游路线规划中的应用[J].软件导刊,2016,15(4):44-46.

[11] 李霞,尹川东，袁云.旅游路线个性化推荐算法比较分析[J].计算机技术与发展,2016,26(9):73-77.

(责任编辑杨黎丽)

TheAntColonyAlgorithm-BasedResearchonCulturalTouristRouteOptimization

LIU Xunxing, HU Min, LI Ying

(Xuancheng Vocational and Technical college, Xuancheng 242000, China)

Nowadays, tourism has become an important way of recreation. Every tourist possesses different demands restricted by space, time and economic capability, thus, the first question facing tourists is how to choose a proper tourism route. The thesis, aiming at abundant tourism resources of Xuancheng city, conducts a route plan on 13 scenic spot in a way of ant algorithm, and establishes constrained route plan model and pursues the best results through making an analysis. The experiment shows that this way can provide various tourism route for different tourists.

ant colony algorithm; route planning; tourism; path optimization

2017-08-01

安徽省高等学校自然科学重点研究项目(KJ2016A784)

刘训星(1981—)，男，安徽宣城人，硕士，讲师，主要从事网络并行分布计算、数据挖掘、教育信息化研究，E-mail: 826038115@qq.com。

刘训星，胡敏，黎颖.基于蚁群算法的旅游线路优化[J].重庆理工大学学报(自然科学)，2017(10):158-164.

formatLIU Xunxing, HU Min, LI Ying.The Ant Colony Algorithm-Based Research on Cultural Tourist Route Optimization[J].Journal of Chongqing University of Technology(Natural Science)，2017(10):158-164.

10.3969/j.issn.1674-8425(z).2017.10.025

O211;TP319

A

1674-8425(2017)10-0158-07