(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111511976.1 (22)申请日 2021.12.0 6 (71)申请人 中国人民解 放军国防科技大 学 地址 410073 湖南省长 沙市开福区德雅路 109号 (72)发明人 罗玉川　黄俊鑫　徐明　付绍静　 柳林　陈颖文　胡罡　逄德明　 (74)专利代理 机构 长沙国科天河知识产权代理 有限公司 432 25 代理人 赵小龙 (51)Int.Cl. G06Q 10/04(2012.01) G06Q 50/30(2012.01) G06F 16/29(2019.01) G06F 21/62(2013.01) (54)发明名称 基于最短路径的隐私保护拼车方法、 装置、 设备及存 储介质 (57)摘要 本发明涉及网约车领域， 公开了一种基于最 短路径的隐私保护拼车方法、 装置、 设备及存储 介质， 本发明通过获取当前地图信息， 在所述地 图信息中通过设立锚点来进行所述地图信息中 不同区域锚点距离的近似计算； 获取当前地图信 息中的乘 客和司机的粗粒度位置， 对乘客进行过 滤以获得目标司机附近的乘客集合； 根据锚点近 似计算结果， 将乘客集合与司机进行路径遍历以 选取最短行驶距离的方案； 将所述最短行驶距离 方案发送至对应的乘客与司机以实现成功拼车， 通过对乘 客和司机的粗粒度位置进行筛选， 再将 过滤后的乘客集合与司机进行路径遍历以实现 基于最短路径的隐私拼车效果。 权利要求书2页 说明书7页 附图4页 CN 114118625 A 2022.03.01 CN 114118625 A 1.一种基于最短路径的隐私保护拼车 方法， 其特 征在于， 所述方法包括： 获取当前地图信 息， 在所述地图信 息中通过设立锚点来进行所述地图信 息中任意两点 的道路距离的近似计算； 获取当前地图信 息中的乘客和司机的粗粒度位置， 对乘客进行过滤以获得目标司机附 近的乘客 集合； 根据锚点近似计算结果， 将乘客集合与司机进行路径遍历以选取最短行驶距离的方 案； 将所述最短行驶距离方案发送至对应的乘客与司机以实现成功拼车。 2.如权利要求1所述的方法， 其特征在于， 所述获取当前地图信息， 在所述地图信息中 通过设立锚点 来进行所述地图信息中任意两点的道路距离的近似计算的步骤， 包括： 获取当前地图信息， 并将地图划分为预设区域； 在区域之中设置锚点作为参考点， 所述锚点设置考虑自身邻 接边数量以及其到区域中 心的距离； 对所述地图信息中的所有锚点之间的距离进行近似计算并储 存计算结果。 3.如权利要求1所述的方法， 其特征在于， 所述获取当前地图信 息中的乘客和司机的粗 粒度位置， 对乘客进行 过滤以获得目标司机附近的乘客 集合的步骤之前， 还 包括： 在检测到乘客发送拼车请求 时， 通过地图工具结合所述乘客的当前位置信 息计算出乘 客到锚点的行驶时间ts→AP(s)和td→AP(d)， 其中s是乘客出发地， d是乘客目的地。 4.如权利要求3所述的方法， 其特征在于， 所述获取当前地图信 息中的乘客和司机的粗 粒度位置， 对乘客进行 过滤以获得目标司机附近的乘客 集合的步骤， 包括： 获取司机当前上传信息， 所述上传信息包括： 司机当前位置1、 司机荷载客数量CAPd以及 司机现载客数量OBRd， 将所述上传信息生成 获取乘客当前拼车请求 其 中s是乘客出发地， d是乘客目的地； 判断当前OBRd＝0是否等于 0； 在所述OBRd＝0时， 在所有目标半径区域内获取乘客 集合 通过预计算得到AP(ri.z(s))和AP(ri.z(d))之间的最短路径， 以及路径途径区域的序 列ri.Zpath＝{ri.z(s)，…， ri.z(d)}； 选择M个Zpath长度最长的乘客 作为根乘客， 同时构建M个相应的集合 5.如权利要求4所述的方法， 其特征在于， 所述选择M个Zpath长度最长的乘客 作为根乘客， 同时构建M个相应的集 合 的步骤之后， 还 包括： 计算乘客扩展的途径区域r.EZpath， 对于 中除根乘客以外的乘客将按下 式比较其路径和方向是否和任一 根乘客相似：权　利　要　求　书 1/2 页 2 CN 114118625 A 2其中公式1指乘客rj的出发地和目的地在ri行程所在路径上， 当满足公式1时再按公式2 所示判断他们的路径方向是否一 致； 若是， 则将rj则会被加入到集 合 中。 6.如权利要求4所述的方法， 其特征在于， 所述判断当前OBRd＝0是否等于0时的步骤之 后， 还包括： 若OBRd＞0， 则表示司机存在已有行程， 获取司机当前参 考已有行程 根据所述已有行程对应的路径进行乘客的筛 选以获得乘客 合集。 7.如权利要求1所述的方法， 其特征在于， 所述根据锚点近似计算结果， 将乘客集合与 司机进行路径遍历以选取最短行驶距离的方案的步骤， 包括： 根据锚点近似计算结果， 生成司机与所有乘客 集合进行路线组合； 遍历所述路线组合以获得最短行驶路线， 将所述最短行驶路线作为最短行驶距离的方 法。 8.一种基于最短路径的隐私保护拼车装置， 其特 征在于， 所述装置包括： 信息获取模块， 用于获取当前地图信息， 在所述地图信息中通过设立锚点来进行所述 地图信息中任意两点的道路距离的近似计算； 位置获取模块， 用于获取当前地图信息中的乘客和司机的粗粒度位置， 对乘客进行过 滤以获得目标司机附近的乘客 集合； 方案获取模块， 用于根据锚点近似计算结果， 将乘客集合与司机进行路径遍历以选取 最短行驶距离的方案； 方案发送模块， 用于将所述最短行驶距离方案发送至对应的乘客与司机以实现成功拼 车。 9.一种基于最短路径 的隐私保护拼车设备， 其特征在于， 所述设备包括： 存储器、 处理 器及存储在所述存储器上并可在所述处理器上运行的基于最短路径的隐私保护拼车程序， 所述基于最短路径的隐私保护拼车程序配置为实现如权利要求1至7中任一项所述的基于 最短路径的隐私保护拼车 方法的步骤。 10.一种存储介质， 其特征在于， 所述存储介质上存储有基于最短路径的隐私保护拼车 程序， 所述基于最短路径的 隐私保护拼车程序被处理器执行时实现如权利要求 1至7任一项 所述的基于最短路径的隐私保护拼车 方法的步骤。权　利　要　求　书 2/2 页 3 CN 114118625 A 3