一种基于文化基因算法的旅游路线规划方法

摘要

本发明公开一种基于文化基因算法的旅游路线规划方法，具体步骤包括：步骤1，获取用户潜在偏好数据；步骤2，获取路网数据并进行清洗；步骤3，获取POI的用户交互信息数据，形成POI属性表中；步骤4，根据用户潜在偏好数据、路网数据和POI的属性表，对路网进行建模，并根据用户查询条件提取能够从起点到达终点的有效边；步骤5，根据用户潜在偏好数据、路网数据和POI的属性表，获取有效边的风景值；步骤6，使用文化基因算法对路网中的有效边和风景值进行搜索，为用户规划出一条风景值和用户满意度都较高的风景旅游路线。本发明解决了现有技术中存在的进行路径规划时未考虑用户偏好、路径风景值和用户个性化需求的问题。

说明书

技术领域

本发明属于线路规划技术领域，涉及一种基于文化基因算法的旅游路线规划方法。

背景技术

随着人们生活水平的提高，越来越多的人选择把旅游作为娱乐消遣的一种方式，同时，这些人希望能以尽可能近的距离和尽可能少的开销到达目的地，以此提升整体的旅游体验。因此，各类路线规划算法层出不穷，合理的路线规划能够为用户节约出行成本，大大提升用户的旅游兴趣，对旅游业的发展具有重要的意义。

传统的路线规划方法旨在为用户规划一条距离短、用时少、花销小的从源到目的地的路线，这些路线规划方法只考虑用户的出行效率，忽略了用户的个人偏好、路径的风景值和用户的个性化需求等问题，即当用户想要驾车出行时，沿途的符合用户偏好的风景能在一定程度上提升用户的旅游体验，对用户来说非常重要。

发明内容

本发明的目的是提供一种基于文化基因算法的旅游路线规划方法，解决了现有技术中存在的进行路径规划时未考虑用户偏好、路径风景值和用户个性化需求的问题。

本发明所采用的技术方案是，

一种基于文化基因算法的旅游路线规划方法，具体步骤包括：

步骤1，根据用户历史签到数据和POI(Point of Interest,兴趣点)类型特征数据获取用户对POI的潜在偏好；

步骤2，从OSM(OpenStreetMap,开放街道地图)上获取路网数据并进行数据预处理；

步骤3，获取POI的用户交互信息数据，包括照片数、评论数、等级、评分等信息，并添加到相应POI属性表中；

步骤4，根据用户潜在偏好数据、预处理后的路网数据和POI的属性表，对路网进行建模，并根据用户查询条件提取能够从起点到达终点的有效边；

步骤5，根据用户潜在偏好数据、预处理后的路网数据和POI的属性表，计算有效边的风景值；

步骤6，使用文化基因算法对路网中的有效边和风景值进行搜索，为用户规划出一条风景值和用户满意度都较高的风景旅游路线。

本发明的特点还在于：

其中步骤1包括：

步骤1.1，从旅游网站上获取用户的历史签到数据，数据内容为txt文本，一行表示一个用户的签到信息，由一到多个POI组成；

步骤1.2，从各个旅游网站获取用户签到过的POI的基本信息，数据内容包括旅游景点的名称、地理位置、类型特征、开放时间；

步骤1.3，通过标签分类统计的方法对步骤1.1和步骤1.2获取的信息进行用户偏好提取，得到用户潜在偏好数据，具体步骤为：

步骤1.3包括：

步骤1.3.1，根据用户历史签到数据获取用户-POI签到矩阵UC；矩阵中每个元素uc

其中uc

步骤1.3.2，根据POI类型特征数据和签到数据获取POI-类型矩阵PT；矩阵中每个元素pt

其中pt

步骤1.3.3，根据用户-POI签到矩阵和POI-类型矩阵获取用户-类型签到矩阵UT；矩阵中每个元素ut

其中ut

步骤1.3.4，对用户-类型签到矩阵中POI类型特征按用户签到次数降序排序，取签到次数最多的TOP-N个类型为用户偏好，并用独热编码进行编码，得到用户偏好向量，即为用户潜在偏好数据。

步骤2的具体步骤为：从OSM上下载城市的路网数据，保留路网数据中的国道、省道、县道、乡镇村道、大学、公园、POI数据，其他数据做清除处理，得到预处理后的城市路网数据。

步骤3的具体步骤为：提取旅游网站中用户对POI的评分、评论数、等级、照片数信息，并标注到对应的POI上，形成POI属性表。

其中步骤4包括：

步骤4.1，路网建模：一个路网被建模为一个图G＝(N,E)，其中N是节点(交叉路口和死胡同)的集合，E∈N×N是有向边的集合；

步骤4.2，路径定义：一条路径是由路网中多条边依次连接形成的，一条从源点n

步骤4.3，用户查询定义：用户查询定义为三元组，表示为Q＝＜n

步骤4.4，确定有效区域：以用户定义的起点和终点的中点作为圆心，以用户允许的最大出行距离为直径，画圆，圆内区域即为有效区域，有效区域内的边即为有效边；

步骤4.5，获取近邻表：有效边上的风景值是根据与边近邻的POI的风景值进行计算的，因此需要设置近邻距离，获取边的近邻表；表的内容包括：边的ID及名称、与边近邻的POI的ID与名称、近邻距离。

其中步骤5包括：

步骤5.1，建立风景值数学模型，风景值数学模型包括POI之间的共访概率函数、POI之间的相似性函数和POI之间的相关度函数，共访概率函数公式为：

其中，Co-VP(i,j)表示POI

POI之间的相似性函数公式为：

其中，Sim(i,j)表示POI

POI之间的相关度函数公式为：

r(i,j)＝Co_VP(i,j)×Sim(i,j) (6)

其中，r(i,j)表示POI

步骤5.2，计算风景值：风景值的计算包括三部分：POI风景值计算、边的风景值计算、路径的风景值计算，具体如下：

POI的风景值主要由POI对应的评分(score)、等级(level)、照片数(pictures)、评论数(comCount)等决定，这些值越大，则POI的风景值就越大，计算方式为：

scenic(i)＝(score(i)+level(i)+picture(i)+comCount(i))×(1+w

其中，scenic(i)是POI

边上的风景值是由与边近邻的POI的风景值决定的，为了搜索方便，将风景值大于0的边记为风景边，公式为：

其中，m是与边e

路径的风景值由路径上包含的边的风景值，计算公式为：

其中步骤6包括：

步骤6.1，染色体编码：首先初始化一条空染色体；其次，从步骤5.2.2得到的风景边中选择一条距离起始点最近的风景边添加到染色体末尾；再次，更新用户查询条件中的d值，即d＝d-dis(e

步骤6.2，染色体解码：对于已编码的染色体，解码的目的是填补两个连续的风景边之间的空隙，即找到被编码染色体在路网上的真实路径，染色体的风景值由风景边的风景值贡献，定义公式(10)作为染色体的适应度函数，将染色体解码成相应的路径，得到真实出行距离；

其中f(R)是染色体的适应度值；Sim(e

步骤6.3，局部搜索，具体如下：

步骤6.3.1，变异：随机选择一条染色体的一条风景边，用另一条风景边代替；在选择新的风景边时要保证不违反用户允许的最大出行距离约束；最后，选择一条最优染色体进行解码；

步骤6.3.2，交叉：在所有染色体中，采用博弈机制选择两条染色体，并选择一个交叉位，交换两条染色体交叉位后其他基因；

步骤6.4，将最终的适应度值最高的路径作为为用户规划的风景旅游路线。

本发明的有益效果是：

本方法引入了用户偏好的概念，即在进行路线规划时，不仅要求路径的风景值更高，而且要求路径的风景尽可能满足用户喜好，使路线规划更具个性化，更能满足用户的个性化需求。其次，在计算风景值时，一条边通常与多个POI近邻，如果仅仅是将近邻POI的风景值求和，就忽略了POI结合时风景值的损失问题。因此，在计算边的风景值之前，先对POI之间的关系进行了建模，考虑了用户对POI的共访概率和POI之间的特征相似性。这样一来，两个POI之间的关系越密切(共访概率越大、特征相似度越大)，对边的风景值贡献越大；反之，对边的风景值贡献越小。这种建模能更精确的计算边的风景值，使得到的路径更优。最后，针对一个POI与多条边近邻的问题，为了不让路径的风景重复，在计算路径风景值时考虑了边特征的相似性，相似性越大，说明重复POI越多，当前边对路径风景值贡献越小；反之，贡献越大。

附图说明

图1是本发明一种基于文化基因算法的旅游路线规划方法的流程图；

图2是本发明一种基于文化基因算法的旅游路线规划方法的流程图中步骤6.1的流程图。

具体实施方式

下面结合附图和具体实施方式对本发明进行详细说明。

本发明一种基于文化基因算法的旅游路线规划方法，如图1，具体步骤包括：

步骤1，根据用户历史签到数据和POI(Point of Interest,兴趣点)类型特征数据获取用户对POI的潜在偏好；

步骤2，从OSM(OpenStreetMap,开放街道地图)上获取路网数据并进行数据预处理；

步骤3，获取POI的用户交互信息数据，包括照片数、评论数、等级、评分等信息，并添加到相应POI属性表中；

步骤4，根据用户潜在偏好数据、预处理后的路网数据和POI的属性表，对路网进行建模，并根据用户查询条件提取能够从起点到达终点的有效边；

步骤5，根据用户潜在偏好数据、预处理后的路网数据和POI的属性表，计算有效边的风景值；

步骤6，使用文化基因算法对路网中的有效边和风景值进行搜索，为用户规划出一条风景值和用户满意度都较高的风景旅游路线。

本发明的特点还在于：

其中步骤1包括：

步骤1.1，从旅游网站上获取用户的历史签到数据，数据内容为txt文本，一行表示一个用户的签到信息，由一到多个POI组成；

步骤1.2，从各个旅游网站获取用户签到过的POI的基本信息，数据内容包括旅游景点的名称、地理位置、类型特征、开放时间；

步骤1.3，通过标签分类统计的方法对步骤1.1和步骤1.2获取的信息进行用户偏好提取，得到用户潜在偏好数据，具体步骤为：

步骤1.3包括：

步骤1.3.1，根据用户历史签到数据获取用户-POI签到矩阵UC；矩阵中每个元素uc

其中uc

步骤1.3.2，根据POI类型特征数据和签到数据获取POI-类型矩阵PT；矩阵中每个元素pt

其中pt

步骤1.3.3，根据用户-POI签到矩阵和POI-类型矩阵获取用户-类型签到矩阵UT；矩阵中每个元素ut

其中ut

步骤1.3.4，对用户-类型签到矩阵中POI类型特征按用户签到次数降序排序，取签到次数最多的TOP-N个类型为用户偏好，并用独热编码进行编码，得到用户偏好向量，即为用户潜在偏好数据。

步骤2的具体步骤为：从OSM上下载城市的路网数据，保留路网数据中的国道、省道、县道、乡镇村道、大学、公园、POI数据，其他数据做清除处理，得到预处理后的城市路网数据。

步骤3的具体步骤为：提取旅游网站中用户对POI的评分、评论数、等级、照片数信息，并标注到对应的POI上，形成POI属性表。

其中步骤4包括：

步骤4.1，路网建模：一个路网被建模为一个图G＝(N,E)，其中N是节点(交叉路口和死胡同)的集合，E∈N×N是有向边的集合；

步骤4.2，路径定义：一条路径是由路网中多条边依次连接形成的，一条从源点n

步骤4.3，用户查询定义：用户查询定义为三元组，表示为Q＝＜n

步骤4.4，确定有效区域：以用户定义的起点和终点的中点作为圆心，以用户允许的最大出行距离为直径，画圆，圆内区域即为有效区域，有效区域内的边即为有效边；

步骤4.5，获取近邻表：有效边上的风景值是根据与边近邻的POI的风景值进行计算的，因此需要设置近邻距离，获取边的近邻表；表的内容包括：边的ID及名称、与边近邻的POI的ID与名称、近邻距离。

其中步骤5包括：

步骤5.1，建立风景值数学模型，风景值数学模型包括POI之间的共访概率函数、POI之间的相似性函数和POI之间的相关度函数，共访概率函数公式为：

其中，Co-VP(i,j)表示POI

POI之间的相似性函数公式为：

其中，Sim(i,j)表示POI

POI之间的相关度函数公式为：

r(i,j)＝Co_VP(i,j)×Sim(i,j) (6)

其中，r(i,j)表示POI

步骤5.2，计算风景值：风景值的计算包括三部分：POI风景值计算、边的风景值计算、路径的风景值计算，具体如下：

POI的风景值主要由POI对应的评分(score)、等级(level)、照片数(pictures)、评论数(comCount)等决定，这些值越大，则POI的风景值就越大，计算方式为：

scenic(i)＝(score(i)+level(i)+picture(i)+comCount(i))×(1+w

其中，scenic(i)是POI

边上的风景值是由与边近邻的POI的风景值决定的，为了搜索方便，将风景值大于0的边记为风景边，公式为：

其中，m是与边e

路径的风景值由路径上包含的边的风景值，计算公式为：

其中步骤6包括：

步骤6.1，染色体编码：首先初始化一条空染色体；其次，从步骤5.2.2得到的风景边中选择一条距离起始点最近的风景边添加到染色体末尾；再次，更新用户查询条件中的d值，即d＝d-dis(e

步骤6.2，染色体解码：对于已编码的染色体，解码的目的是填补两个连续的风景边之间的空隙，即找到被编码染色体在路网上的真实路径，染色体的风景值由风景边的风景值贡献，定义公式(10)作为染色体的适应度函数，将染色体解码成相应的路径，得到真实出行距离；

其中f(R)是染色体的适应度值；Sim(e

步骤6.3，局部搜索，具体如下：

步骤6.3.1，变异：随机选择一条染色体的一条风景边，用另一条风景边代替；在选择新的风景边时要保证不违反用户允许的最大出行距离约束；最后，选择一条最优染色体进行解码；

步骤6.3.2，交叉：在所有染色体中，采用博弈机制选择两条染色体，并选择一个交叉位，交换两条染色体交叉位后其他基因；

步骤6.4，将最终的适应度值最高的路径作为为用户规划的风景旅游路线。

实施例1

本实施例是一种基于改进文化基因算法的风景旅游路线规划方法，具体实现过程如下：

步骤1，根据用户历史签到数据获取用户潜在偏好，具体如下：

首先从携程、途牛、去哪儿等旅游网站上爬取用户的历史签到数据，得到的数据为txt文本，一行表示一个用户历史签到过的POI，且每行包含至少一个POI，并对文本数据进行处理，得到用户签到矩阵；其次，爬取各个POI的类别特征数据；最后，使用标签分类统计的方法，得到用户喜欢的景点类型，并用独热编码进行表示，得到用户的偏好向量P(u)。同时，对POI按其特征类型进行编码，得到POI的特征向量T。此处，随机从签到用户中选择一个用户进行偏好提取，得到用户偏好历史遗迹、宗教、寺庙。

步骤2，从OSM上获取西安市的路网数据，并进行初步的清洗；具体如下：

首先进入OSM官网，找到中国的路网数据，然后按范围选择西安市，导出即得到西安市的路网数据；其次，将得到的路网数据中的.shp文件导入arcGIS中，打开图层数据的属性表，删除无用记录；最后将处理过的路网数据导出并保存。

步骤3，获取POI的用户交互数据，包括照片数、评论数、等级、评分等信息，并添加相应POI的属性表中；具体如下：

首先进入携程网的攻略页，搜索对应的POI，查看其对应的照片数、评论数、等级、评分；然后，在arcGIS打开POI的属性表进行编辑，添加属性字段评分(score)(0.0─5.0)、等级(level)(无、A─AAAAA)、照片数(pictures)、评论数(comCount)，并将携程网上的对应数据进行填入；最后，根据步骤1.2获得的POI类别特征数据，在POI属性表中添加字段类别(type)(本方法将POI类型分为24个)，并将相应的数据填入。

步骤4，根据步骤1，2，3中获得的数据，对路网进行建模，并根据用户查询条件提取能够从起点到达终点的有效边；具体如下：

首先，将处理过的路网数据建模成图G＝(N,E)；然后假设用户查询条件是Q＝＜西安理工大学南门,莲湖公园,7.00km＞，在arcGIS中测量得到，西安理工大学南门与莲湖公园之间的连线距离是5.22km，以连线为对角线画矩形，连接另外一条对角线，两条对角线的交点即为连线的中点，以此中点为圆心，以7.00km为直径，画圆，得到的圆内区域即为有效区域；之后，将有效区域内的数据(点和线)导出，并另存为一个工作空间，以后数据处理只在有效区域内进行；最后，在arcGIS中打开新保存的有效区域的路网数据，使用近邻分析工具，分别对国道、县道、乡镇村道生成与POI之间的近邻表(本方法中认为距离300m以内的POI是可见的，因此近邻分析时近邻距离为300m)，部分近邻表如表1所示。

表1乡镇村道与POI之间的近邻表

表中，OBJECTID*字段是记录的ID，用于表示记录的序号；IN_FID表示进行近邻分析的边在属性表(此处为“乡镇村道”属性表)中的ID；NEAR_FID表示与IN_FID近邻的POI点在属性表(此处1、2行为“其他POI”属性表，3、4行是“学校”属性表)中的ID；NEAR_DIST字段表示NEAR_FID到IN_FID的距离，单位为km；NEAR_FC表示与IN_FID近邻的NEAR_FID所属的表的表名。

步骤5，根据步骤1，2，3中获得的数据，计算路网中有效边上的风景值；具体如下：

首先，根据用户历史签到数据，构造用户-POI签到矩阵；然后，提取有效区域内涉及到的POI，并为这些POI构造共访矩阵，共访概率矩阵的第一行和第一列是POI，矩阵的其他位置的元素表示对应位置的两个POI的共访概率，共访概率由公式(3)结合用户-POI签到矩阵计算得到；之后，再构造一个相似度矩阵，矩阵元素表示两个POI之间的类别特征的相似性；再然后将共访概率矩阵与相似度矩阵进行元素积，得到POI相关度矩阵，矩阵元素表示任两个POI之间关系的密切程度；最后，分别根据公式(6)、(7)、(8)计算POI、边、路线的风景值。

步骤6，基于以上步骤获得的数据，使用文化基因算法对路网中的有效边根据其风景值进行搜索，为用户规划出一条风景值和用户满意度都较高的风景旅游路线；具体如下：

首先，初始化一条空染色体，然后从风景边中选择一条距离起始点最近的风景边添加到染色体末尾，同时更新约束条件；然后循环执行以上选择、插入和更新操作，直到不满足约束条件；之后，对编码的染色体进行解码得到实际的形式距离，并根据公式(10)确定这条染色体的适应度值(此处的物理意义是用户满意度)；最后，进行交叉和变异操作，以提升染色体的适应度值，最终将适应度值最高的染色体转换成实际行驶路线返回给用户，最终路线为：西安理工大学南门出发--->咸宁西路--->环城南路东段--->环城南路西段--->南广济街--->北广济街--->许士庙街--->莲湖公园终点。