基于ACO的智能终端旅游行程规划系统设计

睢先先　宋夫华

(中国计量学院机电工程学院　浙江 杭州 310018)



基于ACO的智能终端旅游行程规划系统设计

睢先先宋夫华

(中国计量学院机电工程学院浙江 杭州 310018)

旅游行程规划对自助游客来说是一件非常繁琐的事情。针对该问题，对行程规划模型、行程规划算法和实现方案进行研究，构建城市内的旅游行程规划服务平台。结合蚁群优化ACO(Ant Colony Optimization)算法、百度地图API、Android开发、WebService和JSON等技术，改进ACO算法，实现了基于Android智能终端的城市内自助游行程规划系统。实验结果表明，实现的智能终端行程规划系统在城市区域内的旅游行程规划方面具有规划效率高、规划结果合理、信息展示直观、使用方便等优点，具有一定的推广价值。

旅游行程规划ACO算法百度地图Android平台

0　引　言

合理的行程规划对自助游客拥有轻松愉快的旅游体验是必要的。进行行程规划的一般过程包括在各种旅游网站上搜集大量的旅游信息，然后决定去游玩哪些景点、景点游玩顺序、游玩时间和景点之间转移的交通路线等，通常需要花费大量的时间和精力，最终得到的结果却往往不尽如人意。因此，开发一种能够帮助自助游客规划合理行程路线的工具显得非常重要。

互联网和新一代通信技术的出现和迅速发展为在线动态规划行程提供了可能，同时也促进很多学者对如何规划合理的行程路线进行了大量研究，大致可分为两类。一类是从数学理论角度进行分析，旅游行程规划属于NP难题，其解决方法有原始的精确求解法和新兴的启发式算法、智能优化算法等。如文献[1]提出采用遗传算法求解最短路问题，文献[2]在此基础上，对大城市内具有时间约束的行程规划问题进行了分析，提出基于嵌套结构的行程规划方法，主程序和子程序中都采用遗传算法去寻找优化路线，最后根据游客需求和选择的旅游景点自动生成一条相关的旅游行程路线；文献[3,4]在蚁群算法基础上分别结合2-opt算法和模拟退火算法优化旅游路线，从而为该问题的研究积累了十分丰富的经验。

另一类研究从应用分析角度进行，这类研究着重于在优化算法的支撑下，实现一个旅游行程规划系统，如文献[5]利用数学模型和交互式多目标技术设计了个人旅游路线规划系统，可以生成一条基于用户选择的行程路线；文献[6]实现了一个基于网络和手机端的个性化旅游路线推送系统，系统可根据用户一天可以游玩的景点数量、景点游玩时间和开放时间等参数，采用改进的启发式搜索方法推荐出一条近似优化的行程路线；文献[7]从团队定向问题角度对行程规划进行分析，把搜索优化解的过程分成两个阶段，预处理阶段采用MapReduce框架探索出多个一日游路线，下一阶段从中选择优秀的行程路线进行组合排序，推荐给自助游客；文献[8]开发了一个为游客提供城市旅行规划的系统。然而，这些研究大部分是通过理论实验进行的，并没有基于真实的数据进行实验。在实际情况中，通常包括大量的景点和复杂的交通网络，潜在解空间的搜索范围广而且复杂。

本文通过对旅游行程规划和蚁群优化算法的研究，设计了城市区域内能满足自助游客多方面需求、可以进行多景点路线规划的Android智能终端旅游行程规划系统。系统采用三层体系架构，集成了行程规划模型、蚁群优化算法、WebService、JSON、Android平台开发和百度地图API等理论与技术。相对于传统的旅游服务内容，该系统旨在为游客提供智能行程规划服务，属于智慧旅游[9]建设的智慧服务体系中不可缺少的一部分，能够更好满足游客个性化的旅游需求。

1　行程规划系统设计

1.1系统体系架构设计

行程规划系统基于一云多屏的智慧旅游公共服务平台理念，采用结构清晰、明确的三层架构体系，如图1所示。该架构可以降低系统各层之间的依懒，减轻系统后期的维护成本和维护时间，整体具有较强的扩展性、易用性和开放性。其中，表现层包括少部分的逻辑代码，主要负责与用户进行交互，接受用户的请求及数据返回；业务逻辑层属于系统架构的核心，是连接用户端和数据库的桥梁，主要负责按照业务逻辑对数据库进行操作，并将数据结果传给表现层；数据库层主要负责解决大数据存储、数据高并发访问、数据分类、加工、封装和数据服务问题。

图1　系统架构图

系统应用服务器采用Tomcat部署WebService服务，提供行程规划和用户信息管理等服务。应用逻辑被封装到了应用服务器中，当应用逻辑发生变化时，仅需修改服务器中的程序，用户端的应用程序不必更新。用户端与数据库服务器通过应用服务器进行连接，降低系统资源的开销，进而提高系统的可靠性和安全性。

系统数据库采用MySQL构建，存储从云端获取的兴趣点基础数据信息、兴趣点间的交通数据和用户数据信息，并提供数据备份和安全管理等功能。

该系统面向游客提供包括电脑、Android/iOS智能手机、PAD等多种形式的服务终端。用户端通过访问开放的应用程序接口，从兴趣点数据库获取景点信息展示给用户，并从云端或交通信息数据库搜集用户偏好的景点交通信息，采用蚁群优化算法智能生成旅游行程路线，最后在百度地图上将规划结果直观、友好地展示给用户，极大地提升了用户体验。

1.2数据库设计

根据系统架构分析，建立了“TRPData”数据库，主要包括景点信息、交通信息、用户信息和城市信息等多个实体。下面仅对景点信息和交通信息中主要的表进行说明。景点信息表用于存储景点的基本属性信息，字段包括身份id、景点名称name、地址address、电话tel、星级star、门票价格price、开放时间timeframe、经度lonx、纬度laty和最佳游玩时间playtime。交通信息表用于存储景点之间的交通信息，字段包括起点from、目的点to、旅途时间traveltime和旅途费用travelcost。

2　行程规划功能详细设计和算法实现

2.1系统体系架构设计

业务逻辑层承载着系统主要功能模块的实现，行程规划模块作为系统的核心功能，主要向用户提供行程规划服务，其详细设计也是针对业务逻辑层展开。如图2所示是行程规划模块的数据流图，系统根据用户输入的基本信息和从交互平台搜集的用户偏好信息，采用行程规划算法进行行程规划，最后将规划结果展示给用户。

图2　行程规划数据流图

2.2行程规划模型分析

旅游行程规划是指根据游客的旅游需求和个人偏好，搜索旅游综合信息数据库中满足条件的相关信息要素，并对偏好景点进行规划排序，生成一条合理的行程路线。

为了使用计算机或移动终端进行旅游行程规划，有必要把行程规划所涉及到的元素及元素之间的关系转化成完全图G={S,E}进行分析，其中S={si|i=1, 2,…，n}代表游客偏好的景点集合，E={eij|i,j∈S}代表两个景点间的旅游交通路线构成的边集合。对于任意顶点si，t(i)表示在景点i的游玩时间，c(i)表示对应的游览费用；对于任意边eij，t(eij)表示从景点i到景点j的旅途时间，c(eij)表示对应的旅途费用c(eij)。

用R={s1,s2,…，sn-1，sn}表示一条满足要求的行程路线，行程所需的旅游花费C和旅游时间T分别如式(1)、式(2)所示：

(1)

(2)

其中d(i)表示提前到达目的地景点时产生的等待时间，如式(3)所示：

(3)

其中tp(i)为景点关闭时间。

以旅游时间最小化和旅游花费最小化的联合来评价可选行程路线R的优劣，目标函数Φ(R)的表达式如下：

(4)

Tt≤Tmax

(5)

Tc≤Cmax

(6)

to(i)≤t(i)≤tp(i)

(7)

其中ω0是衡量旅游时间与旅游费用之间关系的一个权重系数。Tmax代表游客可支配的旅游时间，Cmax代表根据游客需求所得的费用预算。式(5)是对旅游时间的约束；式(6)是对旅游花费的约束；式(7)是对每个景点游玩时间的约束，以确保为游客提供的行程安排落在景点开放时间的范围之内。

2.3行程规划算法设计

根据上述分析可知，行程规划实质上是一类含有多个约束条件的组合优化问题，高效、科学、强壮的算法是解决问题的关键[10]。为生成合理的行程路线，本系统采用ACO算法进行路线寻优。

ACO算法是一种基于蚂蚁群体觅食行为的启发式优化算法[11,12]，通过模拟蚂蚁群体使用信息素轨迹进行交流判断，成功找到较短觅食路线的过程，对问题可能的解空间进行搜索优化。算法实现的过程主要包括：蚂蚁群体构建问题解和路径上的信息素更新两个步骤。首先，蚂蚁个体会根据路径上的信息素浓度和启发式信息，并结合相应的状态转移规则，判断每一步的转移方向。然后算法根据问题的目标函数对每个蚂蚁形成的路线进行评价，更新路径信息素。经过反复迭代搜索，算法最终收敛于最优的蚂蚁个体，也就找到了问题的优化解。

使用蚂蚁个体模拟游客进行旅游行程路线选择的过程中，把游客通常关心的旅游时间、景点开放时间、费用预算等需求参数设计到算法模型中去，对ACO算法进行改进。

(1) 行程路线的构建

假设蚂蚁k(k=1, 2,…,m)在当前节点i选择下一个游览景点j，所有可选的景点存放在集合Rk中。改进的算法模型中，蚂蚁个体不仅感知路径上的信息素强度τ(i,j)和路径启发式信息η(i,j)，而且还会判断景点j开放时间段的约束ω(u)对其吸引度，ω(u)的表达式为如式(8)所示：

ω(u)=C/(tp(u)-to(u))

(8)

其中，C是一个常数。

蚂蚁个体计算可选景点的选择概率时采用改进的状态转移规则，如式(9)所示：

(9)

其中，参数α、β、ν分别表示信息素浓度、启发式信息和开放时间约束的相对重要性。显然，在相同条件下，景点开放时间较短的景点将会被优先选择进行游览。

同时，为了兼顾游客的多重需求，将路径启发式信息η(i,j)从时间和费用两个方面重新设计，改进后的启发式信息计算模型如式(10)、式(11)所示：

(10)

(11)式中参数γ1、γ2分别表示时间和花费的重要程度，管理员可以根据游客的需求对其取值进行调节。显然，由于各景点的最佳游览时间和旅游费用不同，路径(i,j)和(j,i)上启发式信息也相应不同。蚂蚁群体在构建行程路线时交替使用两种启发式信息，旨在寻找到一条满足时间和费用联合最小化的行程线路。

目标节点j的确定方式采用伪随机比例规则，首先根据式(9)求得各景点的选择概率，然后产生一个[0,1]内均匀分布的随机变量q，与控制参数q0(q0∈[0,1])进行比较。如果q≤q0，下一个目标景点j采用确定性方式进行选择，由式(12)确定；如果q>q0，根据已有的选择概率，采用轮盘赌的选择方法确定下一个目的景点j。

j=argmaxpk(i,j)

(12)

(2) 路径信息素的更新

蚂蚁群体构建完成各自的行程路线后，进行路径信息素的更新，用ρ(0<ρ≤1)表示路径信息素衰减度，具体更新规则为：

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

(13)

式中Δτ(i,j)表示蚂蚁个体构建的行程路线R上信息素增量，计算公式为：

(14)

式中Φ(R)为上一节行程规划模型分析得出的评价路线R的目标函数。

根据行程规划算法设计，算法实现的流程如图3所示。

图3　行程规划算法流程图

3　智能终端行程规划软件实现

Android操作系统[13]是一个开放的平台，近年来得到了快速发展，在市场份额中占有很大比重。因此，本文以Android开发平台为例，实现杭州市内旅游行程规划系统的用户端，设计出一款界面布局合理、简洁大方、功能完整、符合用户体验的软件，方便用户随时随地规划行程。软件的结构如图4所示，主要包括需求交互功能和地图展示功能两个模块。

图4　客户端软件结构

3.1需求交互功能模块实现

需求交互功能包括输入基本需求、景点信息展示两个界面，主要由界面组件Activity、列表组件ListView和通信组件Intent及相关技术开发实现。界面展示信息通过Android客户端软件访问远程景点数据库获取。由于平台本身没有提供直接调用WebService服务的库，开发时采用第三方的类库Ksoap2实现调用WebServie服务，服务器以JSON对象形式返回数据结果给客户端。JSON对象具有数据量小、可读性强等特点，客户端解析时也不必用额外的类进行处理。

此外，服务器端处理数据时通过在内存中分页来提高运行效率，将结果快速展示到用户界面，并采用缓存技术来提高用户的使用体验。

基本需求确定界面运行效果如图5所示，用户输入基本需求后，点击“选择景点”按钮，提交需求信息，系统跳转至景点信息展示交互界面，运行效果如图6所示，界面上的“选择”和“已选”按钮用来记录用户的偏好选择。点击界面右上角的“查看线路”按钮，客户端向系统服务端发送行程规划的请求，服务器根据请求内容，从系统数据库搜集行程规划所需的偏好景点游玩时间、开放时间、经纬度位置、景点间旅途时间和旅途费用等信息，并调用行程规划算法模块进行路线规划，在地图上显示返回的行程路线结果。

图5　输入基本需求　　　图6　景点信息展示

3.2地图展示功能模块实现

地图展示功能模块主要用于展示行程规划结果和提供景点间交通线路搜索功能。该模块的实现需要调用百度地图Android SDK，它是一套开放给开发者的应用程序接口，用于Android系统移动设备的地图应用开发，可提供基础地图、地图覆盖物、POI检索、线路规划等功能。地图控件的引入及所有相关操作均在DituActivity类中实现。

其中，为景点添加图形覆盖物是显示行程路线详情的重点，首先根据用户与系统的交互结果获取行程规划的路线信息，然后依次对各个景点添加自定义的覆盖物图标，最后根据添加顺序在地图上实现多点划线。重写自定义图标的点击事件onMarkerClick，当用户点击时，可以获取对应景点的信息，运行效果如图7所示。

景点间线路搜索功能采用地图搜索模块RoutePlanSearch开发实现，将线路搜索的城市区域设置为杭州市，并分别提供了公交、驾车和步行线路搜索功能，运行效果如图8所示。

图7　行程规划结果　　　图8　公交路线信息

在该功能模块实现时，根据需求对百度地图功能做了以下改进：

(1) 行程路线绘制：由于百度地图SDK提供的多边形覆盖物是一个封闭的几何图形，在使用多边形覆盖物选项类PolygonOptions绘制行程线路时，改进该类方法对多边形闭合边框的设置，按照行程规划结果，将起点到终点的景点线路绘制出来。

(2) 更改地图中心位置：由于百度地图在移动设备屏幕中心显示的默认位置是北京市，而本文是以杭州市的行程规划为例。为了调用地图模块时可以直观地看到杭州市内的行程路线结果，首先获取行程规划结果起点的经纬度坐标值，然后使用MapStatusUpdate将地图中心状态位置设置为行程路线起点。

4　结　语

目前市场上的一些旅游网站可以提供基本行程规划功能，但类似于本系统综合考虑游客出游时间、费用和景点开放时间等多种需求的行程规划模型还不多见。另外，本系统采用蚁群智能优化算法规划行程路线，可以承受问题规模不断扩大带来的计算压力，这也是其他优化算法不具备的优势。

经过实验，系统运行正常，并且已成功应用到杭州旅委的智慧旅游手机app中，提升了软件的计算效率和导航精度，能够满足游客规划行程的需要。系统可以通过Web服务器集群技术和数据库分库分表进一步增强性能，并与知名旅游网站结合，实现数据共享，进而规划出更加科学和人性化的行程路线。

[1] Abbaspour R A, Samadzadgan F. A solution for Time-Dependent Multimodal Shortest Path Problem[J]. Journal of Applied Sciences, 2009, 9(21): 3804-3812.

[2] Rahim A Abbaspour, Farhad Samadzadegan. Time-dependent personal tour planning and scheduling in metropolises[J]. Expert Systems with Applications, 2011, 38(10): 12439-12452.

[3] 胡国军, 祁亨年, 董峰，等. 一种改进蚁群算法的研究和旅游景区路径规划问题的求解[J]. 计算机应用研究, 2011, 28(5): 1647-1650.

[4] 刘振波, 方志刚, 徐洁. 改进的蚁群算法在智能导游系统路径优化中的应用[J]. 江南大学学报:自然科学版,2008,7(5):561-563.

[5] Beatriz Rodriguez, Julian Molina, Fatima Perez, et al. Interactive design of personalized tourism routes[J]. Tourism Management, 2012, 33(4): 926-940.

[6] Gavalas, D, Kenteris M, Konstantopoulos C, et al. Web application for recommending personalized mobile tourist routes[J]. IET Software, 2012, 6(4): 313-322.

[7] Chen G, Wu S, Zhou J, et al. Automatic Itinerary Planning for Traveling Services[J]. IEEE Transcations on Knowledge and Data Engineering, 2014, 26(3): 514-527.

[8] Pieter V, Wouter S, Greet V B, et al. The City Trip Planner: An expert system for tourists[J]. Expert Systems with Applications, 2011, 38(6): 6540-6546.

[9] 张凌云, 黎巎, 刘敏. 智慧旅游的基本概念与理论体系[J]. 旅游学刊, 2012, 27(5): 66-73.

[10] 刘传昌. Web服务平台关键技术及旅游规划引擎的研究[D]. 北京：北京邮电大学, 2007.

[11] Dorigo M, Stutzle. 蚁群优化[M]. 张军,胡晓敏,罗旭耀,等译. 北京: 清华大学出版社, 2007.

[12] Cook W J. 迷茫的旅行商：一个无处不在的计算机算法问题[M]. 北京: 人民邮电出版社, 2013.

[13] 范怀宁. Android开发精要[M]. 北京: 机械工业出版社, 2012.

DESIGNING ACO-BASED TRAVEL ITINERARY PLANNING SYSTEM WITH SMART TERMINAL

Sui XianxianSong Fuhua

(College of Mechanical and Electrical Engineering, China Jiliang University, Hangzhou 310018, Zhejiang ,China)

Travel itinerary planning is a very complicated issue for self-service travellers. In light of this problem, we studied the itinerary planning model, itinerary planning algorithm and implementation schemes, and constructed a service platform for urban travel itinerary planning. In combination with a variety of technologies such as ant colony optimisation (ACO), Baidu map API, Android development, WebService and JSON, etc., we improved the AOC and realised the Android smart terminal-based urban self-service travel itinerary planning system. Experimental results showed that the implemented itinerary planning system with smart terminal has the advantages of high planning efficiency, reasonable planning results, intuitive information display and easy in use for travel itinerary planning within city region. It has certain popularisation value.

Travel itinerary planningAnt colony optimisationBaidu mapAndroid platform

2015-04-21。国家自然科学基金项目(61272315)；国家科技部创新基金项目(10C26213304114)；浙江省科技厅国际合作专项(2012C24030)。睢先先，硕士生，主研领域：智能优化，计算机应用等。宋夫华，副教授。

TP311

A

10.3969/j.issn.1000-386x.2016.09.055