应用于实时合乘的最优多会合点路径搜索方法及装置

摘要

本发明提供了一种应用于实时合乘的最优多会合点路径搜索方法及装置，所述方法包括：获取路径搜索预设信息，包括：图G＝(V,E,W)，点集U，α，出发点s，目的点t；初始化队列Q和集合D，将初始状态加入队列Q；当所述队列Q不为空时重复以下步骤：A、弹出队列Q中第一个元素((v,X),cost)；B、如果v＝t同时X＝U则返回cost；C、将状态(v,X)加入集合D；D、对于集合E里的所有(v,u)边循环，更新(Q,D,(v,X),cost+α×w(v,u))；E、对于集合U-X里的所有x点循环，更新(Q,D,(v,X∪{x}),cost+(1-α)×dist(x,v))；循环结束后得到最优路径。本发明提出的最优多会合点路径搜索方法能够高效地解决目前实时合乘应用中尚未解决的技术难点，即，在匹配好了驾驶者和乘客之后，如何快速地确定最优的路径让驾驶者可以接上所有的匹配的乘客，填补了目前实时合乘应用中相关技术的空白。

主权项

一种应用于实时合乘的最优多会合点路径搜索方法，其特征在于，该方法包括：获取路径搜索预设信息，包括：图G＝(V,E,W)，点集U，α，出发点s，目的点t；其中，V、E和W分别为点集、边集和权值的集合；，为顶点的子集；参数α∈(0,1)，用于平衡图G上s～t路径P_st和U中的点到路径P_st之间的距离和的比重；初始化队列Q和集合D，将初始状态加入队列Q；当所述队列Q不为空时重复以下步骤：A、弹出队列Q中第一个元素((v,X),cost)；其中v为子路径的终点，X为纳入子路径的U的子集，cost为状态(v,X)的花费。B、如果v＝t同时X＝U则返回cost；C、将状态(v,X)加入集合D；D、对于集合E里的所有(v,u)边循环，更新(Q,D,(v,X),cost+α×w(v,u))；w(v,u)为边(v,u)的权值；E、对于集合U‑X里的所有x点循环，更新(Q,D,(v,X∪{x}),cost+(1‑α)×dist(x,v))；其中dist(x,v)为点x到点v的距离。循环结束后得到最优路径。