CN103620345A - 通过信息采集和检索提供路线 - Google Patents

Abstract

本发明提供从点A到点B的方向可以被作为信息检索问题来对待。在一个示例中，接收人们行驶的实际路线，并且将实际路线存储在数据库中。当有人请求从点A到点B的方向时，系统搜索数据库以确定从点A到点B的路线是否存在。如果路线的确存在，则可以响应于请求将路线作为方向提供。如果这样的路线不存在，则系统在数据库中寻找彼此具有一定的重叠量的路线并且尝试通过结合彼此重叠的已知路线来构建从A到B的路线。规则可以支配在将路线结合之前它们将具有的重叠程度。

Description

通过信息采集和检索提供路线

背景技术

许多系统提供驾驶、步行或公共交通方向。必应（BING）地图和MapQuest等Web站点可以提供这些类型的从一个地方到另一个地方的方向。还有汽车导航匣和仪表台等各种独立的系统可以类似地提供方向。正常地，找到从一点到另一点的方向的问题是通过使用代表地图的边加权有向图表并且应用Dijkstra算法或A*等算法以通过该图表找到最低成本路径来解决的。

以这种方式提供方向的一个问题是这样做是假定图表具有正确的连接性信息并且是最新的。连接性是指这样的属性：图表上的分支正确地代表在真实生活地理中可以实施的转向。例如，如果节点A、B和C代表地图上的地方并且如果图表表明有人从节点A可以进行到节点B或到节点C的分支，则认为在真实生活中可以取道任一分支。如果与这些分支对应的转向在真实生活中无法实施，则图表中的连接性信息不正确。而且，在真实生活中因施工而新增或封闭道路、或重新规整道路，因此图表中的信息可能变得过时。

数字地图提供者耗费资源以试图保持其图表正确和最新。但是这样做可能很难，并且使用其技术提供的许多方向可能会不正确。

发明内容

关于存在的路线的信息可以基于人们实际行驶的路线持续地采集。这些路线可以被存储。当有人请求方向时，可以实时地检索路线以提供方向。当存储中没有从点A到点B的完整路线时，可以将存储中存在的路线拼接在一起以创建完整的路线，只要他们以满足某些属性的方式彼此重叠即可。以这种方式，有效地将提供方向的问题缩减成信息检索问题而不是从抽象图表计算的问题。使用人们行驶过的路线使得关于哪些路线存在的信息变得更可靠。而且，由于关于人们行驶哪些路线的信息可以持续地采集，因而关于哪些路线可用的信息很可能是最新的。

为了采集关于人们行驶的路线的信息，观察到许多人携带可以精确定位他们的位置的设备——例如导航匣、配备有全球定位系统（GPS）接收器的智能手机等。尽管一些人出于对隐私的考虑而可能选择关闭这些特征，但是其他人可能愿意“选择进入”以使得设备持续地确定他们的位置并且由服务采集该信息。如果有足够的人愿意使这种类型的信息被采集，则所采集的原始地理坐标提供关于人们行驶哪些路线的持续更新的信息。而且，由于所采集的信息代表实际路线，因而信息提供对以下的持续验证：在真实生活中实际可以实施哪些在地图上出现的转向，行驶这些路线花多长时间，行驶时间和转向的可用性如何与一天的时刻相关，行驶时刻和转向可用性如何与车辆中的人数和其它因素相关。

当采集路线的数据库时，数据库可以被用来响应对方向的请求。如果有人请求从点A到点B的路线，则可以搜索数据库以确定这种路线是否存储在数据库中。如果路线被存储，则它可以被检索并且作为方向而提供。如果这种路线在存储中不存在，则可以搜索数据库以找出从点A附近到点B附近经过的最长路线（或者，在一个示例中，由于长路线的路段与较短路线一致而被证实了的最长路线），然后可以搜索数据库以找出从该长路线的入口点和出口点到实际点A和B经过的路线。在实践中，处理可以首先寻找长路线，然后可以继续寻找要被拼接在一起的较短路线，直到创建完整的方向集合为止。

由于地图上存在的转向在真实生活中既可能存在也可能不存在，因而将部分路线组合起来以创建完整路线的系统可能坚持要求将被结合的路线共享一定数量的共有转向。这种状况防止系统提供在真实生活中未被验证的路线。应当注意，不论是像以上说明的那样通过真实生活数据确定的路线，还是仅从相关地理的抽象表示计算出的路线，都可以使用该路线结合准则。

提供该发明内容是为了以简化的形式介绍概念的选集，这些概念将在下面的详细说明中进一步说明。该发明内容的意图既不是要指明所要求保护的主题的关键特征或必要特征，也不是要被用来限制所要求保护的主题的范围。

附图说明

图1是可以行驶其上的路线的示例地图的方框图。

图2是可以被用来建立已知路线的数据库的组件的示例集合的方框图。

图3是基于GPS踪迹建立路线的数据库的示例处理的流程图。

图4是可以被用来响应路线问询的示例系统的方框图。

图5是通过检索已有的已知路线来响应路线问询的示例处理的流程图。

图6是可以与本文说明的主题的实施结合地使用的示例组件的方框图。

具体实施方式

许多系统提供从点A到点B的方向。例如，必应（BING）地图和MapQuest等Web站点可以在地图上的任意位置之间提供驾驶、步行或公共交通方向。汽车导航匣和仪表导航台可以类似地提供方向。通常，从代表地图的边加权有向图表计算方向。具体地，地图可以被表示成节点的集合、节点间的有向边和与每边关联的权重。每一节点代表地图上的交叉路口。每一边代表从一个交叉路口到另一个交叉路口的路径，其中每当认为在那些交叉路口之间的路径存在时即存在边，并且与每一边关联的权重是沿路径行驶的成本（例如行驶时间）。可以使用Dijkstra算法或A*等算法以找出图表中从一个节点到另一个节点的最低成本路径。以这种方式，可以使用图表来计算从点A到点B的方向。

当以这种方式提供方向时，可能会出现某些问题。首先，图表一般是从已有的地图或从大比例的地理照片的分析构建的，而这些数据源可能不会精确地提供关于连接性的信息。地图可能显示两条道路相交叉，但未必可能从一条道路转向另一条道路，这是例如因为一条道路通过高架桥跨越另一条道路，或是因为当地管理部门树立了“禁止转向”路标，或是因为交通太拥堵以至于驾驶员在实践中避免在该交叉路口转向。例如，如果有人在曼哈顿并且想要从第11大道与第42街的拐角行进到第6大道与中央公园南的拐角，则图表可能显示可以沿第42街向东行进、然后在第6大道左转并且继续向北到中央公园。该路线在真实生活中有理论上的可能，但却没有考虑到这一事实：即纽约市对横跨第42街在第6大道左转做出了时间限制，并且即使在一天中允许该转向的时刻也会因交通拥堵而花太多时间在该转向上，以至于只有非常勇敢的驾驶员才会试图这么做。在像上面提到的曼哈顿的交叉路口那样的非常熟知并且病态的案例中，地图提供者可以投入资源以收集这些问题的知识并且将该知识筹建于其地理模型中。然而，有许多实际与地图所示不匹配的地方，而且难以对全部这些情形进行标识和建模。前述的例子示出了连接性问题：两条道路之间的连接看似在地图上存在，但在实际中连接却不存在，或是仅在一天中的某些时刻存在，或是太难以实施以至于有理由避免将该连接包括在驾驶方向集合中。

第二个出现的问题是可以行驶的路线倾向于随时间变化。增加了新的道路。旧的道路因维护而暂停服务，或者被重新规整。交通图发生变化，使得曾经一度行驶容易的路线行驶起来更加困难。新的交通限制正在增加，使得曾经一度被允许的转向不合法。由于跟进这种变化包括花费资源来采集和分析信息，因而对于地图提供者而言，难以做到这一点并且难以将信息添加到从中计算方向的地理模型（图表或其它）中。

此外，边加权有向图表一般将权重（成本）与图表上的边（即从一个节点到另一个节点的路径）关联。然而，在真实生活中，行程的最昂贵（例如，耗费时间）的部分可能是在交叉路口而不是直路上。例如在上述曼哈顿的示例中，沿第42街驾驶可能只花1分钟，沿第6大道驾驶再花1分钟，但是从一条道路左转进入另一条道路（即使是在一天中允许该转向的时刻）可能要花5分钟。换句话说，未将从特定节点取道特定分支的成本考虑在内的边加权图表可能导致低估进行转向的成本，从而使得整个路线看似成本低于在真实生活中的成本。但是寻找从点A到点B的最快路线的驾驶员可能会非常在意该转向花费多长时间。

本文说明的主题将提供驾驶方向的问题作为信息采集和检索问题来对待。基于人们实际行驶的路线实时地采集关于实际可以行驶的路线的信息。本主题不是从将每一交叉路口作为图表中的节点来对待的地图的抽象模型建立方向，而是将已知信息的集合作为人们实际行驶过的路线的集合来建模，并且通过根据已知的重叠路线将路线拼接在一起而建立方向集合。

路线的知识是从人们携带的或是内置在他们的车辆中的设备的全球定位系统（GPS）踪迹采集的。（如以上所述，虽然出于对隐私的考虑，一些人可能选择不让他们的位置被跟踪，但是许多人很可能同意他们的位置和移动被跟踪。在一些情况下，可以提供激励以鼓励人们明确同意这种跟踪。）随时间变动的来自配备有GPS的设备的原始地理坐标对照着地图被交叉引用，以便将该原始数据转化成人们所行使的实际路线。（例如，可以每隔10秒接收一次坐标；通过将随时间变动的坐标的变化与实际地图做比较，可以确定某人行驶的路线。）将行驶过的路线存储在数据库中。与路线本身在一起的可以是以下信息：关于一天中行驶路线的时刻、行驶路线花多长时间、在行驶路线的时刻有多少人乘坐车辆、使用什么型号的车辆，或任何类型的信息。该信息可以与以下的确定有关：确定某些路线在一天中的某些时刻是否拥挤，或确定路线的某些部分是否受到时间限制（例如从早9点到晚5点禁止左转），或确定路线的某些部分是否受到客容或车型限制（例如，路线可能包括大客容车辆（HOV）车道，这种车道要求在轿车中至少乘坐3人，但在该车道中允许公交车和单人摩托车）。（尽管前面的例子假设位置信息将从GPS踪迹采集，但它也可以通过其它技术来采集－例如，WiFi定位、惯性传感器、三角测量等。如同GPS踪迹一样，这种信息可以依照从用户处接收到的适宜许可来采集）。

假设存在含有已知路线（如使用上述技术采集的路线）的集合的某数据库，则提供方向的系统可以根据已有路线将方向集合拼接在一起。路线由“路段”构成，“路段”是交叉路口之间的段。（这种情况下“交叉路口”是可以转向多于一个方向的点。）如果有人询问点A和点B之间的方向，则系统在数据库中查找以确定在那两点之间是否已知存在实际路线。如果存在这种路线，则可以将路线作为方向提供（尽管系统也会尝试从较短的路线的集合构建出成本更低的路线）。一般地，由于较长的路线代表由实际的人做出的关于如何从一点到另一点的较大的决定集合，因而较长的路线被认为包含更多信息。（看待这种情形的一种方式是：同理于将整句话从一种语言翻译成另一种语言可能比由该句中的单个字词拼凑在一起而来的翻译更精确，较长的路线可能比由较短的路线拼接在一起而来的路线更可靠。）由于较长的路线可能覆盖从一点到另一点的距离的大部分，使得能够减少在使用较短的路线时将不得不做的拼接的量，因而较长的路线也可以简化并且加速寻路处理。（尽管应当注意长路线可能是某个人偶然间行驶过的。因此在某些情况下，除非路线被一些人在一段时间内行驶过，否则可以不认为该路线是权威的。或者，只要长路线的路段被作为其它较短路线的一部分集中地行驶过，使得能够证实长路线的精确性和/或巧妙性，即可认为该长路线是权威的。）然而，如果覆盖从点A到点B的整体距离的路线不可用，则系统可以尝试将其它路线组合。

为了组合路线，系统寻找在至少一个路段上重叠并且具有共同的至少一个转向的路线。路线具有共同转向这一条件是要确保系统在方向集合中不包括从一条路线到在真实生活中尚未被验证的另一条路线的转向。避免这种转向避免了以上说明的问题即包括有看似在地图上存在、但却在真实生活中要么不可能实施要么实施起来不现实的转向。施加将被结合的路线具有共同转向这一条件确保（至少在路线是从人们已经历的真实生活行程中导出的示例中）在方向中包括的转向已被实际的人们验证为可能和现实。（在一些情况下，作为将路线结合在一起的条件，系统可能坚持要求2个、3个或n个顺序的共同转向，这可以导致更符合实际的路线。然而，本文的主题不限于使用这种条件的系统）。

如以上所示，长路线被认为比短路线包含更多信息。因此，当根据已知路线将方向集合拼接在一起时，系统可以从长路线开始（可能受制于这样的条件：即应通过长路线的路段被作为其它较短路线的一部分行驶过来证实这些路段），同时使用较短的路线来填充到端点的间隙或连接。例如，如果有人想从加利福尼亚州的伯克利（Berkeley）行驶到新泽西州的普林斯顿（Princeton），则可以将从伯克利到内华达州的温尼木卡（Winnemucca）、再从温尼木卡到爱达荷州的波卡特洛（Pocatello）、再从波卡特洛到蒙大拿州的西黄石（West Yellowstone）、再从西黄石到怀俄明州的科迪（Cody）等各路线组合起来以拼接出该路线。然而，代替以这种方式将路线拼接在一起，在一个示例中系统可能寻找从伯克利附近的点到普林斯顿附近的点的更长的路线。这样，系统可能以从旧金山到纽约的路线开始，并且可能寻找从伯克利到沿该路线最近的高速公路入口和从高速公路出口到普林斯顿的更短的路线。如果，比方说，没有从伯克利到附近的高速公路入口的已知路线，则系统可能寻找甚至更加细化的路线——例如，从伯克利市区到伯克利的Shattuck大道、再从Shattuck大道到I-580。一般地，系统可能以较长的路线开始，然后搜索继续细化的路线以拼入，直到创建从点A到点B的完整的方向集合为止。

下面看附图，图1示出了可以行驶其上的路线的示例地图100。在该示例中，地图100被图示为具有呈直角的街道的矩形栅格。然而，应当理解，地图可以显示按照任何形状的路径并且以任何方式相交的街道的任何集合。

地图100在水平方向上具有以数字编号的街道（第1街～第7街），并且在垂直方向上具有以字母编号的街道（A街～G街）。沿这些街道的已知路线以沿街道的深粗线被示出。如以上所示，这些路线在已实际地观察到有人沿这些路线行驶的意义上可以是“已知”的。然而，通过除了实际观察到有人行驶该路线以外的其它一些机制，路线也可能成为已知。图1所示的路线展现出路线的和路线所存在的地图的各种属性。这些属性在下文加以说明。

路线102是开始于第6街与A街的拐角处、结束于第7街与B街的拐角处的路线。路线102具有两个路段104和106。“路段”是路线的一部分，对于这一部分而言，没有转向离开路线的可能。这样，路段104覆盖路线102的从第6街与A街的拐角行至第6街与B街的拐角的部分。由于在那两个拐角之间没有交叉路口，因而路线102在那两个拐角之间的部分是路段。类似地，由于第6街与B街的拐角和第7街与B街的拐角之间没有交叉路口，因而路线102的那部分也是路段（路段106）。类似地，路线108是包含路段110、112和114的三路段路线。尽管路线108看似未实施任何“转向”（它沿第6街直行），但路线108在它穿过两个交叉路口、在此行驶者必须对去往哪里做出决定的意义上被认为具有“转向”。例如，因为有可能在第6街与D街的交叉路口处向左转、向右转或直行，所以通过交叉路口继续沿第6街直行的决定被理解成“转向”。沿路线108的两个这样的交叉路口将路线分割成3个路段。

正如通过交叉路口直行可以被解释成“转向”那样，通过物理拐角前行的路线可以被理解成“无转向”。例如，路线116沿G街前行，然后在零（Null）街的拐角处通过90度角前行。然而，由于G街结束而零街开始于靠近该90度角处，因而通过该角前行不被认为是为了确定路线有多少个路段目的的“转向”，这是因为沿G街行驶到零街的人别无选择，只能左转进入零街。

还示出了各种其它路线。路线118从第1街与A街的拐角前行到第3街与C街的拐角。出于以上说明的原因，第1与B、第1与C和第2与C处的交叉路口全都被认为是转向。由于有三个这样的交叉路口，因而路线118是四路段路线。路线120是从第1街与C街前行到第4街与E街的五路段路线。路线122是从第3街与D街前行到第5街与F街的六路段路线。路线124是从第1街与C街前行到第5街与F街的七路段路线。在下文使用这些路线来展现可以如何将已知路线组合以提供方向集合的各种方面。

假设路线102、108、116、118、120、122和124存储在数据库中，并且有人询问了从点X（第1与A的拐角）到点Y（第5与F的拐角）的方向。应当观察到，没有一条实际地从点X行至点Y的单条已知路线。然而，处理该请求的系统（例如，汽车导航系统、或必应地图等Web站点）可以尝试组合已有路线以创建从X到Y的方向。系统可能首先尝试将路线118的头两个路段与路线124的全部路段组合起来。然而，路线118和124没有共同的路段或转向。如以上所讨论的，在一个示例中，本文的主题可以避免创建在真实生活中尚未被验证的转向，因此系统可以避免组合这些路线。尽管这些路线可能看似具有共同的交叉路口（即第1街与C街的拐角），但由于这些路线不表示有人沿第1街直行通过C街处的交叉路口，因而该交叉路口不代表共同的转向。换句话说，由于没有任何人行驶过该路线的证据，因而直行通过C街不是系统“已知”的路线的一部分。（例如，可能在该交叉路口有个阻止直行的混凝土路障，尽管这种路障从地图上不显现。）。

系统还可能尝试结合路线118、120和124。可以看出，路线118和120具有两个重叠的路段（从第1和C到第2和C的路段，以及从第2和C到第3和C的路段）。然而，尽管可能看似路线124的尽头能够接上路线120的截止处，但应当注意路线120和124没有共同的路段和转向。相反，路线120在第4街与E街的拐角处与路线124垂直地结束，因此没有包括从第4街到E街的转向的已知路线。这样，路线124不能被添加至路线118和120的组合。然而，路线122确实与路线120具有两个共同路段——即从第3和D到第4和D的路段，以及从第4和D到第4和E的路段。这样，从X到Y的路线可以通过将路线118、120和122的部分组合来构建。应当注意，由于通过组合路线118、120和122所生成的路线包括从第5街沿E街走到第6街，然后又沿F街从第6街回到第5街，因而该路线显得绕远。然而，该路线可以通过将路线122与路线124组合而多少被缩短。由于路线122和124具有共同的路段（从第4和E到第5和E的路段），因而有可能将路线122与路线124的最后两个路段组合，以避免被迫取道该绕远的路线。（然而，某些实施方式可能坚持要求两条路线具有多于一个共同路段，然后才组合两条路线。具有更大数量共同路段的路线可能带给人们感觉更顺畅且“崎岖”更少的真实生活行程，这是因为这种路线具有被人们实际行驶过的多路段延伸。）。

如果从路线118、120、122和124创建方向集合，则以点划线（线126）来示出从点X到点Y的完整方向。通过将已知路线的集合拼接在一起而构建的这些方向可以作为从点A到达点B的路而提供给请求者。以这种方式，提供方向的问题缩减成从已知路线的数据库检索路线的正确组合以及遵循某些规则将那些路线拼接在一起的问题。

注意到在图1的示例中示出的路线是有方向的，其方向由箭头所示。例如，路线102是从第6街与A街的拐角行至第7街与B街的拐角的路线，它不是以相反方向从第7街与B街的拐角行至第6街与A街的拐角的路线。本文的主题的一个方面是利用关于人们实际行驶过的路线的信息，并且以一个方向行驶路线和以相反方向行驶该路线会遇到不同的问题（例如，街道可能是单行的，或者取决于转去的方向和人正行驶在哪条路上，某些转向可能是不合法的。）然而，本文的主题不限于有方向的路线，而是包括使用无方向路线的系统。

图2示出了可以被用来建立已知路线的数据库的组件的示例集合。图2的示例示出了从人们实际行驶过的路线建立的数据库。然而如以上所述，本文的主题的某些方面不限于以这种方式采集已知路线的情况。

在图2中，车辆202沿路线行驶（如箭头204所示）。通过示例，车辆202被图示为轿车，但是车辆202可以是任何类型的车辆——例如，公交车、卡车、摩托车、自行车等。另外，尽管图2的示例示出了车辆正在行驶的路线，但在另一示例中也可以由不乘坐任何类型车辆移动的步行者来行驶路线。

车辆202配备有GPS设备206。GPS设备206可以是便携导航匣、装载在仪表盘上的导航台、配备有GPS接收器的智能手机或任何其它类型的设备。GPS设备206可以确定它在全球范围的当前位置并且能够将该位置的坐标发送至接收器。（如以上所述，出于对隐私的考虑，有人可能选择不让自己的位置被跟踪和发送，但是也有人自愿选择允许他们的位置被发送。）GPS设备206将它的信息（例如经过蜂窝电话网络）发送至GPS踪迹接收器208。

GPS踪迹接收器208接收到的信息可以是在一段时间内传播的坐标的流。例如，GPS踪迹接收器208可以在车辆202的整个行驶期间每隔10秒接收一次坐标。使用这些坐标可以确定车辆202行驶了哪条路线、行驶该路线花了多长时间、乃至行驶该路线的具体部分花多长时间。GPS踪迹接收器可以将该信息提供给GPS踪迹转地图对应引擎210，该引擎充当基于GPS踪迹的路线的创建者。由于坐标只是原始位置数据（例如纬度和经度坐标），因而引擎210可以将这些坐标应用于实际地图以确定车辆202行驶了哪些路线。例如，GPS踪迹接收器可以发现车辆202在下列时刻处在下列位置：

时间                                位置

1:00:00                            47.606622，－122.333407

1:00:10                            47.607342，－122.334035

1:00:20                            47.608785，－122.335392

然而，引擎210可以确定：这些时刻和坐标表明车辆202正在西雅图Madison与Union大街之间沿第4街向北行驶。

一旦引擎210确定了哪条实际路线212对应于GPS踪迹，则引擎210可以将路线212存储在路线数据库214中。路线数据库214可以包含从车辆202（和从许多其它车辆）的GPS踪迹识别的每条路线212。另外，对于每条路线，数据库214可以存储时间信息216和/或成本信息218。时间信息216指示观察路线的时间和行驶该路线花多长时间。如以上所讨论的，有些路线可能只在一天中的某些时刻可用而在其它时刻不可用（例如，可能有禁止在高峰时段左转的限制，或者某些车道可能在早高峰和晚高峰之间调换方向）。这样，在从已知路线创建方向集合时，知道在何时观察了路线可能是相关的。成本信息218可以指示行驶特定路线的成本。该成本可以基于时间（例如，花费长时间行驶的路线可以被视为比可以花费较少时间行驶的路线具有更高的“成本”）。然而，成本还可以基于其它因素——例如距离、限速、存在已知的超速处罚区、是否存在收费站、或任何其它信息。行驶路线的成本可以由成本分析器220来确定，该成本分析器220可以将这些因素（或其它因素）都考虑在内，并且可以确定任何给定路线的成本信息218。

图3以流程图的形式示出了基于GPS踪迹建立路线的数据库的示例处理。在转到图3的说明之前，应当注意虽然本文（在图3和图5中）包含的流程图是参照图1、2和4所示的组件通过示例说明的，但是这些处理可以在任何系统中执行并且不限于图1、2和4所示的场景。此外，图3和图5中的每一幅流程图都示出了以特定次序执行处理的各阶段的示例（如连接各框的线所指示），但是这些图中所示的各个阶段可以以任何次序执行，或是可以以任何组合或下级组合执行。

在302处，可以接收到GPS踪迹。在304处，可以将GPS踪迹应用于地图以获得GPS踪迹（例如坐标和接收到那些坐标的时刻）所代表的路线，可以对GPS踪迹进行分析以确定汇报那些坐标的GPS设备行驶了哪条（些）道路，何时行驶了那些道路，以及方向如何。

在306处，确定路线是否具有多于一个路段。如以上所述，路段是路线中没有可能转向的部分。只有一个路段的路线是不能与其它路线组合的路线，这是因为单个路段路线不包含转向到不同路线上的路。这样，如果路线不具有多于一个路段，则不存储该路线（在308处）。另一方面，如果路线确实具有多于一个路段，则在310处将路线存储在数据库中。

对于每一条所存储的路线，可以计算与该路线关联的成本（在312处）。成本可以基于各种因素。在图3中示出了那些因素314的一些示例。

一个示例因素是行驶路线所花的时间（框316）。假设人们倾向于寻求从一个地方到另一个地方的最快路线，则花费更长时间行驶的路线可以被视为具有比花费更少时间行驶的路线更高的成本。另一个可以考虑的因素是与路线中的每一转向关联的时间（框318）。由于沿直路行驶（交通罕至时）可以相对较快，因而行驶路线花费的大部分时间可能都花在转向上了。这样，知道这些转向有多费时可能是相关的。此外，由于可以将路线的部分组合在一起以创建方向集合，因而除了行驶路线的总成本以外知道完成特定的转向要花多长时间可能是相关的，这是因为转向的成本决定了将两条路线拼接在一起是如何昂贵。这样，在计算总成本时可以将在路线中实施转向所花的时间考虑在内，并且可以将该时间独立于总成本存储。

另一个可以被考虑在内的因素是一天中路线被行驶的时刻（框320）。例如，如果在下午3:00行驶了路线并且行驶花费20分钟，则在成本计算时该事实可能被视为不同于在下午5:00花20分钟行驶该路线的情况，这是因为人们预期在下午5:00时交通量更大。这样，在确定路线的总成本时，一天中路线被实际行驶的时刻可以被考虑在内。在某些情况下，由于一天中行驶发生的时刻可能与确定向人们推荐哪条路线高度相关，因而可以对于一天的不同时刻计算不同成本。

另一个可以被考虑在内的因素是观察路线时车辆中乘客的人数（框322）。（该信息可以由车辆的驾驶员自行汇报。）乘客的人数可能相关的原因是某些车道具有客容限制（例如华盛顿州SR-520具有HOV车道，只有至少3人以上乘客的轿车才能使用该HOV车道），并且有些收费道路基于车辆中的乘客人数而给予折扣（例如，有至少3人乘客的轿车穿过林肯隧道向东只付2美元而不是正常的8美元通行费）。这样，成本可以基于车辆中有多少乘客。能够在高峰时段使用HOV车道可以极大地减少行驶路线所花的时间，并且减少通行费的量以另一种方式减少了行程的成本。这样，在某些情况下，可以对于车辆中的不同人数计算路线的不同成本。

前述是与路线的成本关联的示例因素的列表，这些示例因素也可以被用来确定将推荐哪些路线。然而，可以考虑其它因素，如驾驶员是本地居民还是到此地的来访者（与本地人相比，来访者可能倾向于偏爱更简单的路线），或是车辆的类型（高的车辆可能难以驶过某些立交桥下；长的车辆可能难以实施某些转向；商用卡车可能在称重站处必须停车）等。

在324处可以存储计算出的成本。应当注意，该成本可以是数字，但也可以是用来基于某些变量生成数字的函数。例如，如果路线的行驶成本基于一天中路线被行驶的时刻（t）和/或车辆中的人数（n），则“成本”可能实际上是C（t，n）等函数，该函数在确定行驶路线的成本时将时刻和车辆的客容考虑在内。取决于环境和情境可以计算其它类型的成本——例如，在购物行程中，由于可能认为人们到访多家店铺的购物行程比人们不停车地迅速驶过道路的购物行程更高效，因而多次停车可以被解释成行程的成本降低（即使停车使得行程花费的时间更长）。

一旦创建了路线的数据库，则可以使用那些路线来响应路线问询。（然而，如以上所示，不管已知路线的数据库是从实际的GPS踪迹创建还是以某种其它方式创建，本文说明的技术都可以用来响应路线问询。）图4示出了可以被用来响应路线问询的示例系统。

问询处理器402接收路线问询404。一个示例路线问询是“从加利福尼亚州的伯克利到新泽西州的普林斯顿”，这是可以将该问询键入到地图Web站点中的形式。然而，问询可以采取如将目的地键入导航匣等任何形式，该形式有效地构成了对从导航匣的当前位置到不论哪个目的地的方向的问询（使得当前位置和指定目的地被当作问询的两个端点）。

将已知路线存储在路线数据库214中。这样，问询处理器402可以查询路线数据库214以确定可以使用哪些已知路线来响应问询404。如果在路线数据库214中存在有行于问询404中指定的两个端点之间的路线，则可以检索该路线并且可以将该路线作为方向406来提供。（如图4所示，方向406的示例是“左转上主路（Main）。进入I-80高速公路。向东行驶900英里……”）。

问询处理器402可以包括路线合成器408，该路线合成器408构成可将数据库214中的路线拼接在一起以合成新路线的软件和/或硬件。如果在路线数据库214中不存在问询的端点之间的路线，则路线合成器408可以从已有的已知路线构建路线，并且所构建的路线可以作为方向406来提供。路线合成器408可以使用以上结合图1说明的并且还将在下文中结合图5更详细地说明的技术来构建该路线。

图5示出了通过检索已有的已知路线来响应路线问询的示例处理。在502处，可以接收到路线问询（例如“从加利福尼亚州的伯克利到新泽西州的普林斯顿”）。在504处，处理可以在路线数据库214中寻找接近问询的端点的最长路线。在某些情况下，路线数据库214将实际地包含问询中两个端点之间的路线，在这种情况下，处理可以简单地通过以方向集合的形式提供该路线来做出响应。然而，在许多情况下，路线数据库214将不包含与问询中端点精确地匹配的路线。在这种情况下，图5的处理尝试从其它路线构建那些端点之间的路线。

为了构建这种路线，通过首先尝试找到从问询中的起点附近的地方行至问询的终点附近的地方的长路线，所述处理可以考虑已有路线的长度。例如，参照伯克利到普林斯顿的问询，旧金山在伯克利附近而纽约在普林斯顿附近。如果数据库214包含旧金山到纽约的路线，则可以使用该路线作为基础来构建伯克利到普林斯顿的路线。旧金山到纽约的路线可以被选为起点；在本示例中做出旧金山到纽约的选择具体地是因为该路线的起点和终点接近问询中指定的端点。由于存在于数据库中的长路线代表人们关于如何从一点行驶到另一点的实际选择，因而它可以被认为是特别可靠的。这样，图5的处理可以从寻找长路线开始，并且可以使用更短的路线来填充间隙。这样，从数据库检索的一条或多条路线是从路线问询中指明的一个端点行至另一端点的、要么是单独的要么是组合的路线。

因此，一旦选择了长路线，则在506处，该处理继续寻找更短的路线以将端点连接到更长的路线。例如，当已选择长的旧金山到纽约的路线作为基础来构建伯克利到普林斯顿的路线时，该处理可以寻找从伯克利行至长路线上的交叉路口的路线和从长路线上的交叉路口行至普林斯顿的其它路线。如果不存在伯克利与旧金山到纽约路线上的交叉路口之间的任何路线，则该处理可以继续寻找更短的路线来构建这种路线。如以上所说明的，可以支配路线选择处理的一个示例规则是仅当两条路线的重叠程度满足某一标准（例如，如果它们具有一定数量的共同路段，以及如果有从一条路线转到另一条路线上的转向）时才结合这两条路线。

一旦已识别出具有共同路段的路线，则可以将这些路线在共同的路段处结合在一起（在508处）。可以重复地执行找出路线的处理，并且可以创建多条路线。在510处可以比较这些竞争路线的成本。在512处，处理可以通过基于最低成本路线提供方向来响应在502处接收到的问询。

图6示出了可以利用本文说明的主题的方面的示例环境。

计算机600包括一个或多个处理器602和一个或多个数据记忆组件604。处理器602典型地是微处理器，例如那些在个人桌面或膝上计算机、服务器、手持计算机或另一种计算设备中可见的微处理器。数据记忆组件604是能够短期或长期地存储数据的组件。数据记忆组件604的示例包括硬盘、可移动盘（包括光盘和磁盘）、易失性和非易失性随机存取存储器（RAM）、只读存储器（ROM）、闪存、磁带等。数据记忆组件是计算机可读存储媒介的示例。计算机600可以包括显示器612或与显示器612关联，该显示器612可以是阴极射线管（CRT）监视器、液晶显示（LCD）监视器或任何其它类型的监视器。

软件可以存储在数据记忆组件604中并且可以在一个或多个处理器602上执行。这种软件的一个示例是可以实施以上结合图1～5说明的一些或全部功能的路线检索和构建软件606，但是也可以使用任何类型的软件。软件606可以例如通过一个或多个组件实施，组件可以是分布式系统、分立的文件、分立的功能、分立的对象、分立的代码行等中的组件。程序被存储在硬盘上、载入RAM并且在计算机的处理器上执行的计算机（例如个人计算机、服务器计算机、手持计算机等）是图6描绘的场景的典型，但是本文说明的主题不限于该示例。

本文说明的主题可以作为软件来实施，该软件存储在一个或多个数据记忆组件604中并且在一个或多个处理器602上执行。作为另一个示例，主题可以作为存储在一个或多个计算机可读存储媒介或计算机可读存储记忆体上的指令来实施。光盘或磁盘等有形媒介是存储媒介的示例。指令可以存在于永久媒介上。这种指令当被计算机或其它机器执行时可以使得计算机或其它机器执行方法的一个或多个动作。执行动作的指令既可以存储在一个媒介上，也可以跨多个媒介分布，使得不论是否全部指令恰好都在同一媒介上，该指令都可以看似集中地处在一个或多个计算机可读存储媒介上。应当注意，“存储”信号的媒介（可称作“存储媒介”）与相对照的发送传播信号的媒介两者之间有区别。DVD、闪存、磁盘等是存储媒介的示例。另一方面，信号短暂地存在于其上的导线或纤维是瞬时信号媒介的示例。

此外，本文说明的任何动作（不论是否在图中示出）都可以作为方法的一部分由处理器（例如，一个或多个处理器602）执行。这样，如果本文说明了动作A、B和C，则可以执行包括A、B和C的动作的方法。另外，如果本文说明了A、B和C的动作，则可以执行包括使用处理器来执行A、B和C的动作的方法。

在一种示例环境中，计算机600可以通过网络608通信地连接至一个或多个其它设备。在结构上可以与计算机600相似的计算机610是可以连接至计算机600的设备的示例，但是其它类型的设备也可以这样连接。

尽管以针对结构特征和/或方法动作的具体语言说明了主题，但是应当理解，在所附权利要求中定义的主题未必仅限于以上说明的具体特征或动作。相反，以上说明的具体特征或动作是作为实施权利要求的示例形式而公开的。

Claims (10)

1.一种提供方向的方法，所述方法包括：

通过采集全球定位系统（GPS）数据并且将所述GPS数据应用于地图来获得人们行驶过的多条路线；

将所述多条路线存储在数据库中；

接收指明第一端点和第二端点的问询；

在所述数据库中搜索一条或多条从所述第一端点行至所述第二端点的、要么是单独的要么是组合的路线；

从所述数据库中检索所述一条或多条路线；

基于所述一条或多条路线创建方向集合；以及

向人提供所述方向集合。

2.根据权利要求1所述的方法，所述动作进一步包括：

将所述一条或多条路线组合在一起以创建从所述第一端点到所述第二端点的完整的路线，所述组合由指定了路线要被组合在一起所要具备的重叠量的规则支配，所述规则指定路线要被组合在一起所要具有的共同路段的数量，每一个路段是路线中无转向的部分。

3.根据权利要求1所述的方法，所述数据库中的每一条路线与成本相关联，该成本将一天中行驶路线的时刻或行驶路线的车辆中的人数考虑在内，所述动作进一步包括：

基于所述成本并且要么基于一天中接收到所述问询的时刻要么基于将使用所述方向的车辆中的人数来选择在所述方向使用所述一条或多条路线中的哪条路线。

4.根据权利要求1所述的方法，其中所述搜索包括：

基于路线的长度，通过首先寻找更长的路线、然后继续寻找更短的路线来搜索路线。

5.根据权利要求1所述的方法，其中所述搜索包括：

基于第一路线的起点与所述第一端点之间的接近性、以及基于第一路线的终点与所述第二端点之间的接近性，在所述数据库中找出所述第一路线；

在所述数据库中找出从所述第一端点到沿所述第一路线的交叉路口的第二路线；以及

在所述数据库中找出从沿所述第一路线的交叉路口到所述第二端点的第三路线。

6.一种具有计算机可执行指令以执行根据权利要求1～5中的任何一个的方法的计算机可读媒介。

7.一种提供方向的系统，所述系统包括：

全球定位系统（GPS）踪迹接收器，所述GPS踪迹接收器从设备接收GPS踪迹；

路线数据库；

路线创建器，所述路线创建器基于所述GPS踪迹识别行驶过的路线并且将所述路线存储在所述路线数据库中；

存储器；

问询处理组件，所述问询处理组件存储在所述存储器中，接收包括第一端点和第二端点的路线问询，从所述数据库中检索集中地从所述第一端点行至所述第二端点的多条重叠路线；以及

路线合成器，所述路线合成器基于所述重叠路线中的哪些满足支配重叠的程度的规则而将所述重叠路线结合在一起，以创建从所述第一端点到所述第二端点的完整的路线，其中所述问询处理组件基于所述完整的路线向人提供方向集合。

8.根据权利要求7所述的系统，其中所述路线合成器在所述完整的路线中仅包括在从所述GPS踪迹创建的路线中实施过的转向。

9.根据权利要求7所述的系统，其中所述路线合成器在确定所述完整的路线中将使用哪些路线时，将每一条所述路线的成本考虑在内，所述成本是基于一天中行驶所述路线的时刻或行驶所述路线的车辆中的人数。

10.根据权利要求7所述的系统，其中所述问询处理器基于第一路线的起点与所述第一端点之间的接近性、以及基于第一路线的终点与所述第二端点之间的接近性，在所述数据库中找出所述第一路线，其中所述问询处理器在所述数据库中找出从所述第一端点到沿所述第一路线的交叉路口的第二路线，并且其中所述问询处理器在所述数据库中找出从沿所述第一路线的交叉路口到所述第二端点的第三路线。

Images