基于群智感知的旅游路线个性化推荐方法   0    0

本发明揭示了一种基于群智感知的旅游路线个性化推荐方法,该方法在用户兴趣匹配的基础上，融入群智感知的POI社交评分以及群智感知的POI区位评分，使得评分细则更加全面。此外，提出的适用于无必去景点的景点推荐算法，即变近邻旅游路线推荐算法以及适用于含有必去景点的单/多POI类型两段式贪心旅游路线推荐算法不仅时间复杂度低，并且更加符合用户的偏好以及更具合理性。

1.基于群智感知的旅游路线个性化推荐方法，其特征在于：
S1、对实际路网进行建模，并根据所建立的路网模型构建POI区位关系聚类；
S2、构建用户多元约束兴趣模型；
S3、据用户多元约束兴趣模型以及POI相关信息，计算用户与景点、餐馆的兴趣匹配分值，融入POI的群智感知社交评分以及POI的群智感知区位评分，得到目标函数；
S4、对于无必去景点的单POI类型路线推荐，将距离衰减值融入目标函数得到综合评分，然后采用变近邻贪心旅游路线推荐算法，动态插入综合评分最高的景点得到符合用户偏好的最优路线；
S5、对于含必去景点的推荐，采用单/多POI类型两段式贪心旅游路线推荐算法：先利用随机分割旅游路线推荐算法得到只含必去景点的基础路线，再利用聚类排序插队旅游路线推荐算法对基础路线进行扩充，从而得到最终的符合用户偏好的路线；
所述S2构建用户ud的多元约束兴趣模型：
其中， 为景点aj与用户ud终点 的最短路网距离， 为景点aj的推荐游玩时间， 为景点aj的开放时间， 分别为用户ud设置的时间约束、费用约束
和景点个数约束，Cj为景点aj的门票费用；
此外， 为游完景点aj的结束时间，即
为到达景点aj的时间，即
所述S3包括以下步骤：
定义TA＝{ta1,ta2,ta3,…,tam}为景点的标签总集合，TR＝{tr1,tr2,tr3,…,trn}为餐馆的标签总集合，用户ud的兴趣标签为 景点ai标签为
餐馆rj标签
S31、构建用户景点、餐馆模型，然后构建兴趣匹配布尔矩阵 之后得到用户与景点、餐馆的兴趣匹配分值
S32、计算景点群智感知社交评分 餐馆群智感知社交评分 以及宾馆群智感知社交评分
S33、计算景点区位分布对景点评分贡献的群智感知区位评分 餐馆区位分布对景点评分贡献的群智感知区位评分 以及宾馆区位分布对景点评分贡献的群智感知区位评分
S34、在景点、餐馆、宾馆对景点的群智感知区位评分的基础上，引入参数ka、kr和kh三个权重系数来平衡各类POI的群智感知评分，得到综合群智感知区位评分
其中， 分别为景点ai半径r内餐馆数、宾馆数和除景点ai外的景点数；
S35、通过公式融合用户兴趣匹配分、群智感知社交评分以及综合群智感知区位评分，得到所述目标函数：
其中，α为平衡因子，用于调节兴趣标签匹配值与群智感知评分的重要程度；
所述S4包括以下步骤：
S A D D
S41、通过公式G＝θG+(1‑θ)G 得到将距离因素融入目标函数得到综合评分,其中，G 为距离衰减值，也是距离评分；
S42、采用变近邻贪心旅游路线推荐算法，动态插入综合评分最高的景点得到符合用户偏好的最优路线；
所述S41包括以下步骤：
设 为用户ud出发位置， 为用户终点位置， 用户出发时间，NAd为用户必去景点集合，A为所有景点集合；
D S
首先，计算各景点与用户ud出发点 之间的距离衰减值G，按G的分值由高到低进行排序，选出分值最高者 对应的景点ai，如果这个满足约束的分值最高的景点存在，则按前后顺序放入集合Route中，执行Update(res)函数，更新时间预算 费用预算 以及游览该景点后的结束时间 将该景点放入Route中，并将其从A中移除，之后对A中每一个景点做判断；如果不满足约束，则直接结束，否则以上一个按顺序放入Route的景点为参照，再D A
对景点集合A进行基于路程距离的G以及景点自身的综合评分G的排序，如果存在满足约束的拥有最高分值的景点存在，则更新约束，将该景点放入Route中，并将其从A中移除以及将该景点作为下一次循环的参照景点，最后，求得扩充路线集合Route；
所述步骤S42中，先找出起点到Route中最近的景点，然后更新相关信息，将其作为上一景点，然后以它为参照，求Route中除了它之外的距离它路程最短的景点，接着判断求出的景点是否能在规定时间内游玩，如果不符合，则回溯，将上一个景点置换为该景点，然后以该景点为上一景点，继续求Route中除了它之外的距离它路程最短的景点，直到Route中的景点都已被放入Route′，最后比较调整后与调整之前的路线总时间，从而决定最终的推荐路线是Route还是Route′。

2.根据权利要求1所述的基于群智感知的旅游路线个性化推荐方法，其特征在于：所述步骤S5包括以下步骤：
S51、由于用户ud提供必去景点，先采用随机分割旅游路线推荐算法生成一条仅含必去景点的基本路线，由于采用贪心的思想，该路线符合局部最优的特点；
S52、在生成的局部最优的路线基础之上，采用聚类排序插队旅游路线推荐算法，将符合用户个性化偏好的可选景点依据目标函数进行排序，然后以必去景点为中心景点，依次插入符合用户约束的可选景点，得到最终的最优路线。

3.根据权利要求2所述的基于群智感知的旅游路线个性化推荐方法，其特征在于：所述步骤S51中随机分割旅游路线推荐算法的效用函数为筛选标准，在随机分割旅游路线推荐算法中，计算得到起点到必去景点集合NAd中时间最短的景点，以及基于前一必去景点搜索NAd中距其时间最短的景点加入推荐路线，在计算过程中，将已经筛选出来的必去景点从必去景点集合NAd中移除，并按顺序将其加入到Route中。

4.根据权利要求2所述的基于群智感知的旅游路线个性化推荐方法，其特征在于：所述步骤S52中聚类排序插队旅游路线推荐算法：
首先，将用户要求的必去景点作为中心景点，以一定的半径rM画圆，通过函数AreaSceneDispose(A)得到每个必去景点圆域内其他景点的个数以及景点的相关信息；
以随机分割旅游路线推荐算法得出的路线集合Route′，将路线集合Route′转化为列表list，存放必去景点的下标；
初始化type和count分别为1和0，type用来区分插入的情况，count用来记录成功插入的景点的个数；
判断每一个非必去景点所在圆域的中心景点在list中的下标，之后，分类进行插入；
分类包括：
如果preLoc为0，则有两种情况，若起点到该非必去景点ai所在圆区域内的圆心景点即Route′中第一个景点的路程时间大于到该点ai的路程时间，插入后能满足多元约束，则插在起点后，否则插在圆心景点后；
如果ai后面的点是终点，则存在另两种情况，若终点到ai所在圆区域内的圆心景点的路程时间小于到ai的路程时间，插入后能满足多元约束，则插在该圆心景点前，否则，插在终点前；
若不属于上述两大种类型，并且上一个景点的下标不为负数，则存在另两种情况，若前一个景点到该点所在圆区域内的圆心景点的路程时间大于到该点的路程时间，并且插入后能满足多元约束则插在该圆心景点前，否则插在该圆心景点后。