(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111467800.0 (22)申请日 2021.12.02 (71)申请人 中国人民解 放军国防科技大 学 地址 410073 湖南省长 沙市开福区德雅路 109号 (72)发明人 熊伟　曹竞之　刘泽邦　陈浩　 陈南宇　陈荦　杨岸然　贾庆仁　 马梦宇　欧阳雪　杜春　吴烨　 李沛秦　钟志农　伍江江　景宁　 李军　彭双　 (74)专利代理 机构 长沙国科天河知识产权代理 有限公司 432 25 代理人 段盼姣 (51)Int.Cl. G06Q 10/04(2012.01)G06F 16/9537(2019.01) G06F 16/951(2019.01) G06K 9/62(2022.01) G06F 16/29(2019.01) (54)发明名称 基于用户活动轨迹的路径规划方法、 装置、 设备及介质 (57)摘要 本发明涉及用户出行规划领域领域， 公开了 一种基于用户活动轨迹的路径规划方法、 装置、 设备及介质， 本发明通过网络爬虫 获取用户的签 到轨迹数据， 所述签到轨迹数据包含POI位置数 据和用户对POI的评价信息； 利用LDA模型对所述 签到轨迹数据进行数据清洗以获得所述用户对 POI的评价信息中的主题信息； 结合所述主题信 息、 所述POI位置 数据以及OSM道路网数据构建异 构信息网； 获取用户上传的查询需求， 根据所述 查询需求在所述信息网中用基于扩展R树的近邻 查询算法获取POI候选点集合； 利用启发式搜索 算法从所述POI候选点集合中生成顾及路径长度 和用户活动的路径作为查询结果， 为用户规划出 经过这些POI点的较短路线， 实现POI多样性和路 径长度之间的合理平衡 。 权利要求书2页 说明书7页 附图4页 CN 114118607 A 2022.03.01 CN 114118607 A 1.一种基于用户活动轨 迹的路径规划方法， 其特 征在于， 所述方法包括： 通过网络爬虫获取用户的签到轨迹数据， 所述签到轨迹数据包含POI位置数据和用户 对POI的评价信息； 利用LDA模型对所述签到轨迹数据进行数据清洗以获得所述用户对POI的评价信息中 的主题信息； 结合所述主题信息、 所述POI 位置数据以及OSM道路网数据构建异构信息网； 获取用户上传的查询需求， 根据所述查询需求在所述信息网中用基于扩展R树的近邻 查询算法获取POI 候选点集合； 利用启发式搜索算法从所述POI候选点集合中生成顾及 路径长度和用户活动的路径作 为查询结果。 2.如权利要求1所述的方法， 其特征在于， 所述通过网络爬虫获取用户的签到轨迹数 据， 所述签到 轨迹数据包 含POI位置数据和用户对POI的评价信息的步骤， 包括： 从旅行网站Tripadvisor上， 利用Scrapy软件获取用户的签到轨迹数据， 所述签到轨迹 数据包括POI 位置数据和用户对POI的评价信息 。 3.如权利要求1所述的方法， 其特征在于， 所述结合所述主题信 息、 所述POI位置数据以 及OSM道路网数据构建异构信息网的步骤， 包括： 获取OSM网站上的路网数据， 所述路网数据为有向加权图G， 所述有向加权图G＝(V,E, w)， 其中V是图G中顶点的集 合， e∈E是图G中边的集 合， 每条边具有权 重w。 将所述POI 位置数据整理成POI数据集 合， 用P表示； 结合所述主题信息， 将所述P通过地图匹配的方法将所述P中的POI点映射到所述有向 加权图G中以构建异构信息网。 4.如权利要求3所述的方法， 其特征在于， 所述结合所述主题信 息， 将所述P通过地图匹 配的方法将所述P中的POI 点映射到所述有向加权图G中以构建异构信息网的步骤， 包括： 采用地图匹配方法将所述POI 点映射到所述道路网G上， 匹配为 新的节点； 根据所述 新的节点， 结合所述主题信息构建融合POI信息和OSM信息的异构信息网。 5.如权利要求4所述的方法， 其特征在于， 所述根据所述新的节点， 结合所述主题信息 构建融合POI信息和OSM信息的异构信息网的步骤， 包括： 采用R树对所述道路网G 建立索引； 增加POI节点到所述道路网G中以成为 新的节点； 利用信息网构建代码输入路网G以及POI集合P以构建异构信息网GP， 其中GP(V,E,w, P)。 6.如权利要求1所述的方法， 其特征在于， 所述获取用户上传的查询需求， 根据所述查 询需求在所述信息网中用基于扩展R树的近邻查询算法获取POI 候选点集合的步骤， 包括： 获取用户上传的查询需求； 根据基于扩展R树的邻 近查询算法和所述查询需求将查询到的路径按照匹配度降序排 列并且包含用户所有活动意图的POI 候选点集合。 7.如权利要求1所述的方法， 其特征在于， 所述利用启发式搜索算法从所述POI候选点 集合中生成顾及路径长度和用户活动的路径作为 查询结果的步骤， 包括： 利用评估函数对所述POI候选点集合进行计算以获取对应的路径计算结果， 其中所述权　利　要　求　书 1/2 页 2 CN 114118607 A 2评估函数为： h(v， ∈)＝score(po iseteu(v， ∈)) 在信息网GP＝(V,E,w,P),v∈V,距离阈值∈， p oiset(v,∈)表示距离节点v基于路网的 距离不大于∈的POI 点集合， poiseteu(v,e)表示距离节点v欧式距离不大于∈的POI 点集合； 建立初始化序列sequence＝(id,priority,f,dis,poicollect,node),其中， id为节点 标识、 priority表示该节点莹莹的评估函数的大小、 dis表示该节点到查询点q基于所述路 网的距离、 poicollect为路径上满足用户查询需求的POI点集合以及below表 示该节点的父 节点； 在所述序列sequence中， 将每 个节点按照pri ority大小 进行降序排列； 在所述序列sequence中满足多样性上限的节点超过POI需求数量时， 直接返回当前路 径； 否则， 继续搜索并将搜索到的新节点的相邻节点添加到序列中； 将所述评估函数计算出的结果 通过初始化序列sequence进行优化以获得查询结果。 8.一种基于用户活动轨 迹的路径规划装置， 其特 征在于， 所述装置包括： 轨迹获取模块， 用于通过网络爬虫获取用户的签到轨迹数据， 所述签到轨迹数据包含 POI位置数据和用户对POI的评价信息； 数据清洗模块， 用于利用LDA模型对所述签到轨迹数据进行数据清洗以获得所述用户 对POI的评价信息中的主题信息； 网络构建模块， 用于结合所述主题信息、 所述POI位置数据以及OSM道路网数据构建异 构信息网； 候选点模块， 用于获取用户上传的查询需求， 根据所述查询需求在所述信息网中用基 于扩展R树的近邻查询算法获取POI 候选点集合； 查询结果模块， 用于利用启发式搜索算法从所述POI候选点集合中生成顾及路径长度 和用户活动的路径作为 查询结果。 9.一种基于用户活动轨迹的路径规划设备， 其特征在于， 所述设备包括： 存储器、 处理 器及存储在所述存储器上并可在所述处理器上运行的基于用户活动轨迹的路径规划程序， 所述基于用户活动轨迹的路径规划 程序配置为实现如权利要求1至7中任一项所述的基于 用户活动轨 迹的路径规划方法的步骤。 10.一种介质， 其特征在于， 所述介质上存储有基于用户活动轨迹的路径规划程序， 所 述基于用户活动轨迹的路径规划程序被处理器执行时实现如权利要求1至7任一项所述的 基于用户活动轨 迹的路径规划方法的步骤。权　利　要　求　书 2/2 页 3 CN 114118607 A 3