用于在道路系统上实时最近邻搜寻的方法、装置与流程

1.本公开的各个方面涉及用于在道路系统上实时确定最近邻车辆的方法及装置。
背景技术：
：：2.叫车应用程序利用车辆位置信息将一车辆与叫车应用程序用户进行匹配。叫车应用程序用户可以从用户的乘车请求位置处请求乘车。叫车应用程序可使用车辆位置来将一车辆与基于乘车请求位置的叫车应用程序用户进行匹配。然而，当车辆沿着一道路系统行驶时，车辆位置可能会改变。因此，需要实时车辆位置信息来提供不中断的用户体验。此外，具有在车辆位置与乘车请求位置之间最短距离(直线距离)的车辆可能不是用于乘车请求的最佳车辆。例如，离乘车请求位置最近的车辆可能在一单行道路上正驶离乘车请求位置。因此，当确定一车辆的行驶距离并将车辆与乘车请求匹配时，需要考虑道路系统信息。技术实现要素：3.各种实施例涉及一种用于更新包括位置信息的车辆信息的叫车方法。叫车方法可以以高的频率更新车辆信息。根据各种实施例，叫车方法可包括被配置为定义车辆更新频率的一频率参数。车辆信息可以包括地理位置、速度、和/或方向。4.此外，各种实施例涉及一种用于确定在乘车请求位置附近的车辆间的行驶距离的叫车方法。行驶距离可包括一车辆可以沿着道路系统行驶到乘车请求位置的距离。确定行驶距离可以包括车辆信息和/或地图数据。乘车方法可以基于到乘车请求位置的行驶距离来确定这些最近的车辆。5.根据各种实施例，叫车方法可以确定一车辆到达请求位置的估计时间。6.根据各种实施例，叫车方法可以更新一车辆的信息，车辆的信息包括位置信息。7.根据各种实施例，叫车方法可以使用地图数据来确定行驶距离。地图数据可以包括交通、道路类型(州际公路、本地道路)、和/或车辆信息。8.根据一个实施例，一种装置可被配置来执行确定最近车辆的叫车方法。9.根据一个实施例，一种非暂时性的计算机可读介质可以储存计算机可执行代码，计算机可执行代码包括用于确定最近车辆的叫车方法的指令。10.根据一个实施例，一种计算机可执行代码包括用于执行确定最近车辆的叫车方法的指令。附图说明11.参考结合非限制性实例及附图来考虑的详细说明，将可更佳地理解本发明，附图中：12.·图1a展示出根据各种实施例的更新车辆信息的方法的示例性流程图；13.·图1b展示出根据各种实施例的确定最近车辆的方法的示例性流程图；14.·图2展示出根据各种实施例的执行乘车请求的方法的示例性流程图；15.·图3a及图3b展示出根据各种实施例的道路系统的示例性视图；16.·图4展示出根据各种实施例的原始地图数据的示例性地图节点及路；17.·图5展示出用于将车辆位置转换为在基于边的图形(ebg)内的车辆对象位置的示例性方法；18.·图6展示出根据各种实施例的用于确定最近车辆的示例性架构；19.·图7展示出根据各种实施例的用于更新及储存车辆位置信息的示例性流程图；20.图8展示出根据各种实施例的用于生成最近车辆列表的示例性流程图。具体实施方式21.以下的详细描述参考了附图，所述附图通过说明的方式图示出可在其中实践本公开的具体细节及实施例。这些实施例以足够详细的方式被描述以使本领域的普通技术人员能够实践本公开。在不脱离本公开范围的情况下，其他实施例可被利用并且可以进行结构及逻辑上的改变。各种实施例不一定是相互排斥的，因为一些实施例可以与一个或多个其他的实施例相结合以形成新的实施例。22.在所附组件、车辆、或方法中之一的上下文中所描述的实施例类似地适用于其他所附组件、车辆、或方法。类似地，在所附组件的上下文中所描述的实施例类似地适用于车辆或方法，反之亦然。23.在实施例的上下文中所描述的特征可相应地适用在其他实施例中相同或相似的特征。在实施例的上下文中所描述的特征可相应地适用于其他的实施例，即使在这些其他实施例中并没有被明确地描述。此外，针对在实施例上下文中一特征所描述的添加和/或组合和/或替代可相应地适用于在其他实施例中相同或相似的特征。24.在不同实施例的上下文中，关于一特征或组件所使用的冠词「一」、「一个」及「」包括对所述特征或组件的一个或多个的引用。25.如在本文中所使用的，用词「和/或」包括所述相关联所列项目的一个或多个的任意及所有的组合。26.如在本文中所用的并且根据各种实施例，用语「用于…方法」也可以包括「…的方法」的含义。27.如在本文中所用的并且根据各种实施例，表达「节点特征」及「节点向量」(及其复数形式)可被互换使用。28.如在本文中所用的并且根据各种实施例，术语“位置”或“位置信息”可以包括地理数据，诸如地理空间坐标，并且还可包括例如由全球定位系统gps所提供的时间。gps坐标可以根据世界大地测量系统wgs84，例如版本g1674。29.对于在道路系统上的车辆的识别，位置信息是真实世界的数据，例如真实世界的gps数据。相应地，地理周长代表在地球表面上的周长。30.如在本文中所用的并且根据各种实施例，术语「地理」及「地理空间」可被互换使用。31.如在本文中所用的并且根据各种实施例，术语「车辆对象」及「司机对象」可被互换使用。车辆可以是自动驾驶车辆或人类驾驶车辆。32.叫车服务在很大程度上依赖于数字地图数据及车辆信息。随着车辆沿着道路系统移动，经常更新车辆信息至关重要。经常更新车辆信息可确保车辆信息尽可能为最新的。实时定位乘车请求位置附近的车辆可以创造更好的乘车体验。例如，乘车请求应实时识别乘车请求位置附近的一辆或多辆车辆，以增加乘车请求会被车辆所接受的机会。识别在乘车请求位置附近的车辆的一个挑战为：随着时间的推移，车辆所在的地方或位置可能随着车辆沿着道路系统移动而改变。另一个挑战为在乘车请求位置与车辆之间的直线距离可能不会考虑行驶距离。例如，如果直线距离最近的车辆是在州际公路上，则它可能无法像直线距离较大但正在本地道路上行驶的另一辆车辆那样快地到达乘车请求位置。本公开的各种实施例使用地图数据及车辆信息以根据从车辆位置到乘车请求位置的行驶距离和/或估计到达时间来确定针对乘车请求位置的最近的车辆。33.图1a示意性地示出用于更新车辆信息的方法100的示意图。车辆信息是叫车应用程序的重要组成部分，并且拥有实时车辆信息可以提供不间断的用户体验。用于更新车辆信息的方法100可以包括步骤102、104及106。步骤102可以包括接收周期性请求以更新车辆信息，车辆信息包括车辆位置信息。例如，叫车应用程序可以识别出正在道路系统上行驶的配备有叫车应用程序的车辆。车辆更新请求可被配置成每分钟多次。步骤104可以包括将多辆车辆中的每一辆车辆的车辆位置转换为在图形上的车辆位置，其中图形表示道路系统。步骤106可以包括更新车辆信息，包括更新在图形上的车辆位置。此外，车辆更新请求可以包括更新其他的信息，诸如速度、方向等等。34.图1b示出了用于确定一辆或多辆最近车辆的方法110的示意图。用于确定一辆或多辆最近车辆的方法110可以包括步骤112、114、116及118。步骤112可以包括接收乘车请求。步骤114可以包括确定乘车请求的位置并将位置转换为在图形上的位置。步骤116可以包括从乘车请求的位置遍历图形以在图形上搜寻车辆对象。步骤118可以包括确定在图形上所找到的一辆或多辆车辆与乘车请求位置之间的最短行驶距离，其中行驶距离包括车辆必须从其位置行驶到乘车请求位置的距离。35.图2示出了针对乘车请求位置识别出最近车辆的方法200的示意图。方法200可以包括与方法100及110相同的一些步骤。步骤202可以包括基于原始地图数据获得一图形。图形可以表示道路系统并且包括与图形所表示的地理区域相关联的一地图id。步骤204可以包括获得多辆车辆的车辆位置。步骤208可以包括将车辆位置转换为在基于边的图形的边上的位置。步骤210可以包括接收包含乘车请求位置的乘车请求。乘车请求位置可以包括地理数据。36.步骤206可以包括针对被定位在图形上的每一个车辆对象更新车辆位置信息。之后，针对每一个车辆对象的经更新的车辆位置信息可被使用以针对乘车请求位置识别出最近的车辆。请注意，车辆更新可能会频繁地发生且独立于乘车请求。步骤206可以包括与在图1a中所描述的相同或相似的步骤。37.步骤212可包括识别出在图形上对应于乘车请求位置的地理位置的最近的边。从在图形上被识别出的位置开始，可以搜寻最近邻车辆。可以在最接近乘车请求位置的边来搜寻车辆对象。步骤214确定在图形的边上是否有任何车辆对象。如果有的话，则在步骤218将车辆添加到最近车辆列表中。如果没有的话，则方法在步骤216移动到相邻边并重复过程。38.步骤220可通过对方法110中所确定的行驶距离进行升序来对步骤218的最近车辆列表进行排序。39.步骤222可以确定最近车辆列表是否有足够的车辆用于乘车请求。例如，如果在请求位置的预定附近中有30辆车辆，但确定只需要识别出5辆车辆就可以成功地满足乘车请求，则方法可以在前5辆最近车辆被发现之后停止搜寻更多车辆。步骤224可以包括在乘车请求位置的一预定半径内的一区域的地理数据。地图数据可以包括位于地理区域或乘车请求位置附近内的道路系统，并且仅搜寻在预定半径内的道路系统。例如，如果在乘车请求位置的预定半径内只有3辆车辆，则方法200会停止搜寻更多车辆来满足乘车请求。这是因为搜寻得更远可能会使得任何随后找到车辆的行驶距离增加。车辆越远接受乘车请求的可能性就越小并会增加乘车请求用户的等待时间。40.图3a示出了车辆位置如何随时间变化并且可能需要车辆更新。乘车请求位置302可以包括在第一时间300a及第二时间300b的地理位置。如在图3a中所示，三辆车辆310、312及314正在沿着道路系统320行驶。在第一时间300a，车辆310最接近乘车请求位置302。另外，在第一时间300a，车辆312及314分别是第二接近及第三接近。在第二时间300b，车辆310、312及314相对于乘车请求位置302的位置可能已经改变，影响了在车辆310、312及314与乘车请求位置302之间的行驶距离。41.叫车应用程序经常更新车辆位置以确保将乘车请求发送到最近的车辆或行驶距离最短的车辆，这一点很重要。例如，在第一时间300a，车辆310可能拒绝来自乘车请求位置302的乘车请求。如果车辆位置没有更新，则可能会在第二时间300b向车辆312发送第二乘车请求，但是这不会是最佳选择，因为在第二时间300b时车辆312与乘车请求位置不在同一条道路上。若要为乘车请求选择最佳的车辆，应考虑行驶距离。行驶距离可以考虑车辆位置、速度、方向、道路规则、道路系统等等。行驶距离可以帮助推断出一车辆的估计到达时间(eta)。对与较短eta相关联的车辆的乘车请求可以减少乘车请求拒绝或取消，并提高乘车请求完成率。42.图3b示出了在车辆位置与乘车请求位置之间的最短直线距离可能不是在车辆位置与乘车请求位置之间的最短行驶距离的一种情况。例如，在地图部分340上，在乘车请求位置342处发出乘车请求。两辆车辆350及352可能在乘车请求位置342的附近中。车辆350与乘车请求位置342间是直线距离为370并且在方向360上行驶。车辆352与乘车请求位置342间是直线距离372并且在方向362上行驶。距离372可能比距离370短。然而，因为方向360朝向乘车请求位置342而方向362是远离乘车请求位置342，与车辆352相比，车辆350可能可更早到达乘车请求位置342。因此，应将乘车请求发送给车辆350。叫车应用程序考虑行驶距离以确定距离乘车请求位置最近的车辆是重要的，这可能会缩短乘车请求用户的等待时间，从而提高用户满意度和/或降低取消率。43.叫车应用程序需要准确的地图数据来生成表示道路系统的图形。原始地图数据可被转换为基于边的图形(ebg)。图形生成方法可将包括节点、路、及关系(relations)(包括速度、方向)的原始地图数据划分为段。图形生成方法可以进一步将段转换为压缩边图形。如以下所述，图形生成方法可以从压缩边图形来生成ebg，以有效地确定沿着道路系统的路线安排。44.下面我们将描述如何将原始地图数据转换为用于叫车应用程序的图形的一个实例。也可使用生成图形来确定路线安排的其他方法。原始地图数据可以从包括节点、路、及关系的一开源地图(osm)中收集。一节点可以表示在包括地理数据的地图上的一点。路可以连接两个或更多个节点，因此可以由包含有一个或多个段的线来表示，并且可以包括限速或其他道路规则信息。多条路可以在两条路相交的地方共享同一个节点。关系描述了在几个节点或路或两者组合之间的关系。关系可以描述转弯限制、路线等等。关系通常不是实体结构，而是一种抽象，诸如一公交车路线。45.图4示意性示出由原始osm地图数据所提供的几个节点及路。图形生成方法可以将osm地图数据转换为边扩展图形或基于边的图形(ebg)，其可能更适合于对转弯成本及转弯限制进行建模。例如，osm可以表示包含有两条路420及422的道路系统，其包括五个节点402、404、406、408、及410。第一路420可以包括节点402、404及406来表示第一道路。第二路422可以包括节点408、406、及410以表示第二道路。第一路420可以在节点406处与第二路422相交。这些路可以被划分成针对一对节点的单独段：402-404、404-406、406-408及406-410。对于在osm中的每一个段，针对ebg创建两个节点，段的每一个方向一个节点。这些可以称为基于边的节点。例如，在ebg上的基于边的节点(ebn)可以表示从节点402到节点404的方向(402-404)，而在ebg上的另一个ebn可以表示从节点404到节点402的方向(404-402)。可以针对在两个ebn之间每一个可能的移动生成边。这可以称为基于边的边(ebe)。ebe可以被定义为一对ebn，起始节点-结束节点，并表示从一个ebn移动到另一个ebn。先前描述的ebn(402-404)及(404-402)是两个实例。46.ebg可以包括ebn及ebe。ebn表示一osm段的一特定方向(向前或向后)。对于双向路段会有两个ebn。然而，单向路段只有一个ebn。ebe连接ebn，并表示从一个osm段的一特定方向的移动向另一个(或相同)osm段的特定方向的移动的转移。转移可经由从一条路到另一条路的一转向、做一u型回转、或沿着相同的路从段移动到段。47.如之前所述，其他方法可以生成适合于确定路线安排的图形。48.图5示出了表示在乘车请求位置502附近中的道路系统的基于边的图形(ebg)500。ebn508及510可以表示在基于节点的节点(nbn)502、504、及506之间的移动，其中基于节点的节点(nbn)502、504、及506表示在请求位置502附近的道路系统。ebn可以由nbn502、504及506的一对来定义，以描述沿着道路系统的一段的行进方向。叫车应用程序可以获得车辆对象并且可以生成表示在ebg500上的车辆对象的假想节点522或524。例如，车辆对象520可以包括gps位置。基于车辆对象520的gps位置，一种方法可以确定车辆对象520的位置落在ebn508与510之间。因为车辆应位于道路系统上，所以方法可以将假想节点522或524添加到ebg500来表示车辆对象520。方法可通过从地理位置到ebn绘制垂直线来将假想节点投影到最近的ebn508或510。投影的点被表示为假想节点。方法可以基于哪一个最能代表车辆对象520的gps坐标在假想节点522或524之间进行选择。方法可以基于在车辆对象520与假想节点522或524的gps坐标之间的距离来选择假想节点522或524，其中可以选择具有最短距离的假想节点。例如，可以选择假想节点522来表示车辆对象520，因为假想节点522可以最好地表示车辆对象520的gps坐标。方法可以计算投影比526以表示在投影位置与观察位置之间的差异。每一个假想节点可能只是在ebg上的车辆的记忆(memory)表示，并且实际上并未被添加到ebg500。每一个假想节点可以包含有关于其投影位置的信息(诸如与其投影位置最接近的基于边的节点(ebn)的id)、投影比等等。最接近的假想节点被绑定到原始车辆位置(520)，以提供有关于在ebg上的车辆位置的信息。49.图6示出了叫车解决方案的示例性架构600。在实施例中，示例性架构600可以包括计算机程序产品。根据各种实施例，计算机程序产品可以储存包括用于识别出k辆最近车辆的指令的计算机可执行代码。在实施例中，计算机可执行代码可以是计算机程序。在实施例中，计算机程序产品可以是非暂时性计算机可读介质。50.架构600可以包括代理层602、节点层604及模型层606。每一个实例610、620及630包括层602、604及606的每一个。代理层602可以接收车辆更新请求和/或乘车请求并根据包括在请求中的地图id来分发请求。地图id可以识别出表示地理区域或城市的图形的分区。代理可以检查用于地图id的当前实例或查看地图id的路线表(routetable)以确定叫车解决方案的哪些实例包括地图id。路线表可包含从地图id到实例的ip地址的映射，其中实例包含包括地图id的模型。如图所示，实例620的代理层602可以接收请求。如果地图id包括在不同的实例中，代理层602可将请求转发到在不同实例(装置)上的一节点。例如，实例610、620及630可被储存在分开的装置上。51.节点层604的每一个节点可以储存用于模型层606的一个或多个模型616的地图id的索引。当节点层604的节点接收到来自代理层602的请求时，节点藉由地图id识别出正确的模型616并将请求转发到正确的模型616。当正确的模型616从节点层604接收到请求时，模型616可以执行请求。52.模型层606的每一个模型616可以储存车辆信息。模型616可以从代理层和/或节点层接收车辆对象。每一个车辆对象可以包括车辆信息，其包括车辆id、地图id、车辆载客量、状态、车辆位置(gps坐标)、及其他的元数据。模型可以基于在请求中所包括的地图来确定一地图。如前所述，模型616还可以基于车辆对象的车辆位置储存在ebg上的假想节点位置。模型616还可以识别出在ebg上离假想节点最近的基于边的节点(ebn)，并将最近ebn的ebnid与车辆对象信息一起储存。53.模型616可以转换车辆对象在图5中的地理位置520并将地理位置投影到代表道路系统的ebg上的位置。投影假想节点可以返回假想节点列表，其按照从车辆地理位置到假想节点的半正矢距离以升序排列。54.如前所述，可以跨不同的实例来复制模型以实现容错。例如，可以跨节点层604的每一个节点复制每一个模型。更新在任一个实例的车辆信息被转发到包含针对给定地图id的副本的其他实例。例如，实例610可将车辆更新请求转发给实例620及630。模型层606的多个模型616可被储存在同一节点中以优化叫车应用程序的实例。55.节点层604的节点可以藉由它们的地图id来索引模型616。叫车应用程序可以使用自适应基数树(art)来有效地从ebg索引车辆。每一个模型维护两个art，车辆art及ebnart。可以在表示道路系统的图形与车辆对象之间创建双向索引，用以进行有效的索引及车辆更新。车辆art可以储存包括车辆信息的车辆对象并且使用车辆id作为车辆的索引。ebnart可以使用ebnid作为ebn的索引。每一个ebn可以储存其位置在ebn上的车辆对象的列表，其中车辆对象的列表被储存为art并且ebn可以包括指向车辆art的根的指针。56.在一实施例中，模型616可首先使用其车辆id检查车辆对象是否已经存在。如果不存在，模型616可将车辆对象添加到车辆art及ebnart。如果车辆对象已经存在的话，则新的车辆对象将替换在车辆art上的旧的车辆对象。对于ebnart，可能需要先删除在先前ebn上的旧的车辆对象，然后才能将新的车辆对象添加到当前ebn。每一次插入或删除都会修改两个art，其可能会导致对根的更改。由于模型616仅储存art的根，为了防止竞态条件，可以使用锁定来防止其他读取或写入操作存取art同时更改art根。57.当接收到车辆附近请求时，可能需要两个art的根。在一实施例中，可以在并行的车辆更新及附近请求期间实现同步。例如，当有两辆车a及b被储存并且这两辆车位于同一个ebn上时，当有一附近请求时，两个art的当前的根会被返回。在处理此附近请求时，有可能会有可能会修改art的正在进行的车辆更新，例如由于车辆c的更新而导致一新的根。正在进行的车辆更新不会影响正在进行的车辆附近请求，因为它们正使用不同的根。随后的附近请求将使用新的art根来查找附近的车辆。在ebn与车辆对象之间的双向索引提供了在车辆对象与ebn之间的有效检索。在实践中，车辆id及ebnid可以是数字索引关键词。与诸如字母关键词的稀疏关键词相比，art对数字关键词具有一更好的产出量。58.图7示出了车辆更新方法700。方法700可以使用与在图6中所描述的相同的架构。随着车辆沿着道路系统移动，方法700可以更新车辆对象以反映实时车辆位置信息。方法700可以以周期性间隔安排车辆更新以实时更新车辆信息，车辆信息包括车辆的地理位置。代理704可以接收车辆更新请求702并且根据包括在车辆更新请求中的地图id来分发请求。在接收到要更新车辆对象的车辆更新请求702时，代理704可以确定针对车辆更新请求的车辆id是否已经存在有车辆对象。添加新车辆对象或更新现有车辆对象的过程类似。59.如果它不存在，则代理704根据更新请求702信息构建车辆对象，包括车辆id、地图id、gps坐标等等。代理704可通过检查当前的实例和/或查看路线表来确定哪些实例包括在车辆更新请求中所包括的地图id。如果地图id包括在当前的实例中，则会执行自我更新。例如，当前实例的节点712可以包括车辆更新请求的地图id并且与代理704在同一装置上，如在图7中所示。如果地图id包括在其他的实例中，则车辆更新请求被转发到那些其他的实例。例如，节点714及716可以在不同的装置上并且包括地图id。代理704可以查看路线表以确定节点714及716的ip地址并将车辆更新请求转发到节点714及716，如在图7中所示。代理704使用唯一的地图id作为关键词来查看路线表并获取包含具有相同唯一地图id的车辆对象的所有实例的ip地址。每一个实例能够确定更新请求从不同的实例(在不同的装置上)的代理所接收到的。如果实例确定是从不同的实例接收到更新请求702，则更新请求和/或车辆对象将被直接转发到节点而不用检查路线表，因为最初接收到车辆更新请求的代理已经查看了路线表。60.节点层720的节点722、724、及726可基于车辆更新请求和/或车辆对象的唯一地图id来识别模型。节点722、724及726可基于车辆位置信息确定在ebg的ebn上的车辆对象位置。然后车辆对象在ebnart上及车辆art上被更新，如先前所述。如果代理704在当前的实例712上没有找到车辆对象的地图id，则什么都不做，并且也不会引发错误。这是因为如果实例712不包括车辆更新请求的地图id，则包含有地图id的模型被储存在其他的实例上，并且代理704会将车辆更新请求702转发到包括地图id的其他的实例714及716。可被观察到的是，可扩展的记忆内解决方案可保持的是最终一致性而不是强一致性。在实践中，最终一致性有利于高产出量而胜过k最近邻(knn)查询结果的一轻微不一致性，因为后者不会显著地影响分配性能。61.节点识别车辆更新请求的地图id，并在ebnart与车辆art之间的双向索引中查找它，以确定正确的模型。节点将车辆对象转发到正确的模型。如前所述，模型更新及储存车辆对象信息。62.图8示出了基于乘车请求的附近车辆请求方法800。附近车辆请求方法800可以使用与在图6中所描述的相同的架构。用户发起的乘车请求可触发附近车辆请求。可以从上游接收附近车辆请求并将其分发到叫车应用程序的实例中之一。每一个实例可能在不同的装置上。在从上游接收到附近车辆请求时，负载平衡技术可以将请求分发到代理，诸如代理层的代理804。代理804可以将附近车辆请求转换为附近车辆对象。每一个模型820可以与地图id相关联以用于简化查找。代理804可以检查以确定当前的实例是否包括地图id。如果当前实例包括地图id，则附近车辆对象被传递给当前实例的节点以执行附近车辆请求，例如节点810。如果当前实例不包括地图id，则代理可以查看路线表，由地图id所索引，以确定哪些实例包含地图id并可能为附近车辆请求提供服务。例如，负载平衡技术可以实现循环以从包含有附近车辆请求的地图id的确定的实例中选择一个实例。在确定了用于附近车辆请求的一个实例后，代理将附近车辆请求转发给该一个实例。代理层被配置成确定附近车辆请求从另一台机器所接收到，并将附近车辆对象直接传递给节点层的节点。在接收到附近车辆对象时，节点810基于唯一地图id作为搜寻关键词来搜寻正确的模型。例如，节点810可以确定模型820是正确的模型并将附近车辆对象传递给模型820。模型820对最近的车辆对象执行knn搜寻。搜寻可被配置成寻找在乘车请求位置的预定距离内的固定数量的车辆对象或所有车辆对象。例如，模型820可通过将乘车请求的位置转换成假想节点来执行knn搜寻，并且使用这个假想节点作为用于ebg扩展的起始节点，如以下所述。63.从在ebg上的起始节点开始，开始k辆最近车辆搜寻。在knn搜寻过程中使用了两个优先队列。ebnpq被使用来追踪附近的ebn，以及vehiclepq被使用以追踪在扩展期间所发现的车辆。在车辆与乘车请求位置之间的行驶距离也在vehiclepq中被追踪。64.在执行knn搜寻之前拍摄当前车辆储存器(使用当前art的根)的快照。快照包括在代理接收附近车辆请求时在道路系统上的车辆位置。从每一个起始节点，找到父ebn并将位于这些ebn上的车辆附加到vehiclepq。knn搜寻扩展到相邻的ebn并将这些ebn附加到ebnpq。迭代所有的节点之后，在vehiclepq中将会有一些初始车辆以及在ebnpq中将会有未被扩展的相邻ebn。65.每次从ebnpq中移除最近的ebn时，位于ebn上的车辆都会被附加到vehiclepq中。在vehiclepq中最近的车辆被移除，并且如果车辆满足乘车请求过滤要求，则将其附加到有资格的车辆的数组中。重复此步骤，直到vehiclepq并传回有资格的车辆的列表为止。在此过程中，如果有资格的车辆数量达到最大车辆限制，则knn搜寻停止并传回有资格的车辆的列表。66.在vehiclepq变空后，当前ebn的相邻ebn被扩展并被附加到ebnpq。重复此过程，直到预定的区域已被搜寻为止。例如，代表原始起始节点的三公里半径的区域。最近的ebn从ebnpq中被删除并且位于ebn上的车辆被附加到vehiclepq。过程继续进行，直到ebnpq为空为止。车辆数组作为附近车辆搜寻的结果被返回。67.附近车辆请求可以包括与车辆元数据做比较的一组过滤器参数，以将用户乘车请求与在knn搜寻中的车辆进行匹配。过滤器参数可被认为是服务上的需求。例如，用户请求可以请求具有至少4个可用座位的车辆。附近车辆请求方法可以查询车辆元数据以确定车辆对象是否满足请求。68.车辆元数据还可以包括更新时间戳。附近搜寻可以过滤掉具有过期时间戳的车辆。车辆元数据还可以包括车辆状态及用于过滤的特定的分配偏好。69.在以下附近车辆算法中描述了最近车辆的knn搜寻：70.附近车辆查询算法：[0071][0072]虽然已经参考了特定的实施例具体地示出及描述了本公开，但本领域的普通技术人员应当理解的是，在不脱离如由所附权利要求所限定的本公开精神及范围的情况下，可以在其中进行形式及细节上的各种改变。因此，本公开的范围由所附权利要求来指出并因此旨在包括落入所述权利要求等价物的含义及范围内所有的变化。当前第1页12当前第1页12
技术特征：
1.一种用于识别最近车辆列表的方法，包括：确定在基于边的图形上的起点，其中所述起点定位在所述基于边的图形的多条边中的一边上；判定一个或多个车辆对象是否被定位在所述一边上，并且如果一个或多个车辆对象被定位在所述一边上，则将所述一个或多个车辆对象附加到所述最近车辆列表；以及遍历所述多条边中的相邻边并判定一个或多个其他车辆对象是否被定位在所述相邻边上，并且如果所述一个或多个其他车辆对象被定位在所述相邻边上，则将所述一个或多个其他车辆对象附加到所述最近车辆列表。2.如权利要求1所述的方法，还包括：针对所述车辆对象中的至少一个车辆对象确定行驶距离，其中所述行驶距离包含沿着所述边在所述起点与所述车辆对象中的所述至少一个车辆对象的位置之间的距离。3.如权利要求2所述的方法，还包括：比较两个或多于两个所述车辆对象的行驶距离；以及基于比较确定最短行驶距离。4.如权利要求1至3中任一项所述的方法，其中，所述多条边中的每一条边包含地理数据。5.如权利要求1至4中任一项所述的方法，其中，所述一个或多个车辆对象中的每一者包含地理数据。6.如权利要求2所述的方法，还包括：基于所述行驶距离而确定所述至少一个车辆对象的估计到达时间，其中，所述估计到达时间包含从至少一辆车辆的位置到起始位置行驶的时间。7.如权利要求6所述的方法，还包括：比较两个或多于两个所述车辆对象的估计到达时间；以及基于比较而确定最短时间。8.如权利要求1至7中任一项所述的方法，还包括：周期性地更新所述一个或多个车辆对象中每一者的位置以获得一个或多个经更新的车辆对象位置。9.如权利要求8所述的方法，还包括：基于所述一个或多个经更新的车辆对象位置而判定一个或多个车辆对象是否定位在所述一边上。10.一种用于识别最近车辆的方法，包括：接收包含有请求位置的乘车请求；获取多辆车辆的车辆信息，其中，所述车辆信息包含车辆位置；将所述多辆车辆中每一者的车辆位置信息转换为在基于边的图形上的车辆位置，其中，所述基于边的图形表示道路系统；以及确定在所述多辆车辆中至少一量车辆的车辆位置与所述请求位置之间的行驶距离，其中，所述行驶距离包含沿着所述基于边的图形始于所述多辆车辆中至少一量车辆的车辆位置到所述请求位置的路径，以及其中，所述行驶距离是在所述车辆位置与所述请求位置之间的最快路径。11.如权利要求10所述的方法，还包括：获取地图数据，其中，所述地图数据包括地理数据；
将所述地图数据转换为多条边及多个节点，其中，所述多条边及所述多个节点包含地理数据；基于所述多条边及所述多个节点的所述地理数据而生成所述基于边的图形；以及将所述车辆位置叠加在所述基于边的图形上。12.如权利要求10或权利要求11所述的方法，还包括一交通延迟以及进一步基于所述交通延迟而确定所述行驶距离。13.如权利要求10至12中任一项所述的方法，还包括一交通规则以及进一步基于所述交通规则而确定所述行驶距离。14.如权利要求13所述的方法，其中，所述交通规则包含确定一边对应于单行道路。15.如权利要求10至14中任一项所述的方法，还包括比较所述多辆车辆中两辆或多于两辆车辆的所述行驶距离；以及基于比较而确定最短行驶距离。16.如权利要求15的所述方法，还包括向对应于所述最短行驶距离的车辆发送满足乘车请求的消息。17.如权利要求10至16中任一项所述的方法，还包括：周期性地更新所述多辆车辆中每一者的位置以获得一个或多个经更新的车辆对象位置。18.如权利要求17的所述方法，基于所述一个或多个经更新的车辆对象位置而确定在所述多辆车辆中的至少一辆车辆与所述请求位置之间的所述行驶距离。19.一种用于根据权利要求10至18中任一项来识别最近车辆的装置。20.一种储存有计算机可执行代码的非暂时性计算机可读介质，所述计算机可执行代码包含有用于根据权利要求1至19中任一项来识别最近车辆的指令。

技术总结
各方面涉及用于识别最近车辆列表的方法，包括：接收包含请求位置的乘车请求；获取多辆车辆的车辆信息，其中车辆信息包含车辆位置；将多辆车辆中每一车辆的车辆位置信息转换为在基于边的图形上的位置，其中基于边的图形表示道路系统；以及确定在多辆车辆的车辆位置中的至少一个与请求位置之间的行驶距离，其中行驶距离包含至少一辆车辆沿着道路系统行驶到达请求位置的距离。达请求位置的距离。达请求位置的距离。


技术研发人员：吴昊 苏明磊 坦赫
受保护的技术使用者：格步计程车控股私人有限公司
技术研发日：2022.03.30
技术公布日：2023/9/9