相关申请的交叉引用
本申请基于以下申请，并要求其优先权日期：
国家 申请号 申请日
美国 62/632,419 2018年2月20日
美国 62/758,710 2018年11月12日
美国 62/780,268 2018年12月16日
美国 62/800,428 2019年2月2日
美国 16274242 2019年2月13日
上述申请通过引用并入本文。
背景技术
本发明涉及搜索(searching)或比较(comparing)地点。传统的搜索目标是从一系列可能的替代方案中找到一个实现优化目标的地点(site)，例如在给定特定行程要求以及所查找的地点的期望特征的情况下，最小的路线长度(route length)。例如，在给定所需的通勤目的地(destinations of commutes)和房地产(real estate property)特征的情况下搜索房地产时，一个目标可能是枚举具有匹配特征且通勤时间最短的房地产。另外的目标可能是使用通勤时间比较任意的房地产。
发明内容
实施例包括用于搜索或比较地点的方法(method)，实现并执行该方法的计算机系统，以及接收(receives)来自用户的搜索或比较请求并以地点和路线信息(information)做出响应(responds)的计算机服务。
根据本发明的实施例，提供了一种使用路线或路线长度进行搜索或比较地点的方法。该方法使用大量的预处理来预先计算(precompute)并在数据库中存储每个地点与交通系统内的代表(representatives)之间的路线或路线长度。该方法引入了地点的搜索或比较框架(framework)。收到包含路线说明的请求后，将从数据库中检索预先计算的数据，以快速计算每个地点的路线或路线长度。可以使用路线或路线长度搜索或比较地点。
根据本发明的实施例，提供了一种使用路线或路线长度进行搜索或比较地点的计算机系统。该系统是硬件和软件的组合。它从一个或多个数据提供者(data providers)获得交通系统和地点的数据。该系统构建的图表(graphs)可对交通系统内的地点和代表之间的行程进行模拟。该系统计算图表路径(graph paths)，并且存储图表路径或图表路径长度。这样可以在收到请求时，快速计算每个地点的路线或路线长度，并且使用路线或路线长度搜索或比较地点。
根据本发明实施例，提供了一种使用路线或路线长度进行搜索或比较地点的计算机服务。该服务允许用户通过设备(例如智能手机)上的用户界面指定搜索或比较请求。该请求包括路线说明和筛选条件(filtering condition)。作为响应，该服务将显示与筛选条件相匹配的地点以及匹配地点的路线或路线长度，或者该服务使用路线或路线长度比较地点。
从根本上来说，必须快速计算每个地点的路线长度。我们概述一个数学证明。考虑任何搜索或比较方法M。我们可以设计一个对抗请求(adversarial request)，该请求将强制M以任何给定的地点排序列表进行响应。对手(adversary)有两种机制可供使用：(1)提供具有路线说明的请求，其指定相对于路线长度的地点顺序(该顺序由对手选择)，以及(2)向与对手选择的地点子集相匹配的地点提供一个带有筛选条件的请求。因此，M必须在请求时提供由对手任意选择的站点的有序列表。证明概述的细节不在本专利申请的范围之内。
所述方法，计算机系统，以及计算机服务各自共同执行的任务不是简单的通用的，也不是现有技术所能很好理解的。现有技术包括：US 8,417,409 B2；延续案US 8,738,286B2；分案US 8,756,014 B2；KR 10-1692501 B1；延续案PCT/KR2016/01083；WO 2017/065431A1；US 2018/0232824 A1以及KR 10-1905593 B1。
这里呈现的本发明的实施例是为了说明的目的；它们不是穷举的。对本领域普通技术人员来说，在不脱离实施例范围和精神的情况下，许多修改和变形将是显而易见的。
在本说明书中，所述术语“第一”，“第二”，“所述”，以及类似术语，不以任何限制意义使用，而是用于区分的目的，除非从上下文中可以清楚地看出。单数形式的表达包含复数，除非上下文另有明确表达。所述术语“具有”，“包括”，“包含”，以及类似术语，表示组件或特征的存在，并不排除其他组件或特征的存在或添加。
附图说明
包括在本发明公开中的附图示例了本发明实施例的各种特征和优点：
·图1：描绘了根据本发明实施例之一的通勤路径的行程时间的彩色渲染图示例，图例：“具有两条通勤路径的房地产的通勤路径的行程时间的彩色渲染示例：房地产→geo.0.0→geo.0.1→房地产，以及房地产→geo.1.0→房地产。我们使用了Google的地图图块引擎，也可以使用其他引擎。”；
·图2：描绘了根据本发明实施例之一的数据的预处理和存储的示例处理流程，图例：“数据的预处理和存储的示例处理流程”；
·图3：描绘了根据本发明实施例之一使用预处理的存储数据对请求作出响应的示例处理流程，图例：“使用预处理存储数据对请求作出响应的示例处理流程”；
·图4：描绘了根据本发明实施例之一的通勤路径的示例，图例：“示例通勤路径”；
·图5：描绘了根据本发明实施例之一的用于预先计算最短图表路径的公共交通系统图的扩展的示例，图例：“用于鱼线计算最短图表路径的公共交通系统图的扩展示例”；
·图6：描绘了根据本发明实施例之一预先计算的最短的行程时间的表/向量存储(vector storage)示例，图例：“预先计算的最短的行程时间的表/向量存储示例”；
·图7：描绘了根据本发明实施例之一的通勤路径分解的示例，图例：“示例通勤路径H→W
·图8：描绘了根据本发明实施例之一的在通勤路径的起点处计算最短行程时间的示例，图例：“在通勤路径的起点处计算最短行程时间的示例”；
·图9：描绘了根据本发明实施例之一在通勤路径的终点处计算最短行程时间的示例，图例：“在通勤路径终点处计算最短行程时间的示例”；
·图10：描绘了根据本发明实施例之一用于在通勤路径起点处计算最短行程时间的伪代码(pseudocode)的示例，图例：“用于计算PathFromHomeDurations(→W)的伪代码的示例”；
·图11：描绘了根据本发明实施例之一的计算机系统的示例流程图，图例：“计算机系统的示例流程图，用于：预先计算并在数据库中存储数据，并使用从数据库检索的数据处理请求”；
·图12：描绘了根据本发明实施例之一的在用户智能手机上的用户请求以及计算机服务的响应的示例，图例：“用户智能手机上的用户请求和计算机服务的响应的示例”。
这些附图仅用于说明目的。本领域普通技术人员将容易认识到，其他附图可以例示本发明而不背离本发明的原理。
4详细说明
本发明涉及使用任意优化目标来搜索或比较任意地点的一般情况，该任意优化目标使用到任意位置的路线或路线长度(routes or route lengths)。然而，为了便于说明，我们首先通过特定的地点(sites)-房地产，特定的位置(places)-工作场所，以及特定的优化目标-最小化房地产和工作场所之间最的通勤行程时间。该说明不是限制性的。在后面的部分中，我们将解释该方法在一般情况下的工作原理。
4.1房地产和通勤路线
寻找住宅是一项复杂的工作。人们花费大量的时间和金钱在搜索上。然而，技术已经开始有所帮助。存在几种在线可用的服务，其汇总房地产清单，并允许人们使用浏览器或智能手机方便地搜索具有特定特征的房地产，例如，价格，地理位置，卧室的数量等等。该搜索产生一个候选名单，然后人们通常会对其进行检查。
位置(location)可以说是任何房地产中最重要的特征，房地产经纪人的“位置，位置，位置”口号证明了这一点。我们的发明涉及该特征。
居民需要通勤去工作，学校或其他地方。这些通勤的行程时间会影响为特定的居民量身定制的房地产的价值。此外，就可以分配给生产活动更多时间，不需要花费精力来使人们四处走动等方面来看，减少大都市区所有居民的行程时间具有很大的全球经济价值。我们的发明有助于实现这些个人和全球价值。
举一个简单的例子，考虑居住在韩国首都的一个两口之家。一人是市政厅的政府职员，另一人是首尔国立大学主图书馆的图书管理员。他们目前居住在面积为69平方米的具有两间卧室和一个卫生间的公寓，需要支付押金350,000,000韩元。该公寓位于经纬度(37.5333,127.0746)附近。他们的每日往返通勤时间总计为1小时41分(单程平均需要25分钟)。但是，事实证明，在他们搬到具有相同特征，但位于(37.5041,126.8888)附近的公寓后，他们可以将行进时时间缩短到1小时16分钟(节省25分钟)。所有公寓中的最短行进时间为50分钟。但是该公约具有其他的价格和尺寸(截止2018年2月19日的插图)。
为什么很难为所有人提供这些改进？一种初级的办法是考虑市场上所有具有家庭所需的尺寸和其他特征的房地产，并在给定工作地点的情况下，通过查询任何现有的在线路由引擎来计算行程时间。然而，这种方法无法扩展。一个问题是在现代大都市区市场中可获得的房地产数量众多。另外的问题是可能希望寻求改进的家庭/用户数量众多。即使我们假设我们可以廉价地查询路由引擎，但是问题的二次性质仍然使查询总体上昂贵。
我们如何才能为所有人提供这些改进？我们的发明给出了解释。其包括以下部分：
1.本发明定义了通勤路径(commute path)的模型。该模型具有通用性，可以覆盖现实中出现的各种通勤路径，例如上学，然后到钢琴班，再然后回家。我们能够快速找到使行程时间最短的房地产，从而提高了模型的实用性。
2.本发明提供了一种快速计算行程时间的优化方法。本发明确定依靠任何房地产的任何通勤路径的部分。这些部分的行程时间已被提前计算并存储。结果就是，当需要找到通勤路径的行程时间时，本发明能够快速组合(assemble)各个时间部分，以产生每个房地产的行程时间。
3.本发明的一个实施例是真是的计算机服务。该服务使得首尔市区的2500万居民能够使用出行时长搜索或比较房地产。
4.2方法概述
我们在广义上使用术语行程(travel)，其包括移动的对象或数据。对行程的描述(description of travel)可以是本领域普通技术人员会命名的任何事物。以下是一些关于出行的描述的示例：(1)“嗨，哥们，你需要向北走一个街区，然后稍微左转”，以及(2)“5美元”。当我们表示对行程的描述时，我们可以使用术语行程路径(travel path)。行程的长度(length of travel)是本领域普通技术人员可以与行程相关联的任何数值(numericvalue)，例如距离，货币成本等。作为其他示例，当我们表示代表时间的行程长度时，我们可以使用术语行程时间(travel duration)。行程长度本身就是对行程的描述。行程的描述：可能不包括任何行程长度，可能仅包括行程长度，或者还可能包括一些其他数据。
我们说明了该方法的一些功能并介绍了随后使用的术语。该方法可以计算每个房地产的通勤路径的行程时间。图1对此进行了说明。大都市区域用正方形着色。颜色代表使用公共交通工具从每个特定区域的房地产中通勤所需的时间：绿色表示通勤时间短，黄色长一些，红色最长。通勤路径从房产property开始，然后访问特定地点geo，...，最后返回到房产property。从某种意义上说，房产property是一个自由变量(free variable)，而geo，...则是固定的。在图1中，有两条通勤路径：一条“抵达一处再从另一处出发”的通勤路径property房产→geo.0.0→geo.0.1→property房产，每周两次，以及一条“往返”通勤路径property房产→geo.1.0→property房产，每周三次。我们可以发现，鉴于这两条通勤路径及其频率，最短旅行时间的加权总和较小的房地产会形成不规则的斑块(深绿色)，鉴于错综复杂的公共交通路线，这并不奇怪。
概括地说，该方法由两部分组成。第一部分计算房地产和代表(representatives)交通系统(transportation system)的站点之间的行程时间。这些行程时间存储(stored)在数据库(database)中，以便在收到请求(request)时可以方便地检索它们。如图2所示。第二部分处理请求。请求包括通勤路径以及房地产的期望的特征(features)。接收到(received)请求后，将从数据库中检索适当的行程时间，并将其与其他数据一起，为具有所需特征的每个房地产生成通勤路径的行程时间。如图3所示。此概述的详细信息及变形将在后续部分中描述。
4.3通勤路径
我们的方法可以处理人们在大都市区内进行的各种通勤。通勤始于我们称为房屋(home)的地点H。H是任意位置。它可以是任何房地产，例如公寓，出租房，带花园的房屋，牧场，酒店等。它还可以是人们工作的场所，餐厅，商店等。然而，作为命名约定，我们在本公开的大部分中，使用短语“房屋”；该约定不是限制性的。在一个实施例中，通勤者前往各个位置，然后返回地点H。
在一个实施例中，通勤时间在一天之内，例如通勤者早上离开H，然后在当天的晚上返回H。在其他实施例中，通勤时间超过一天，例如，某人上夜班，或者上班时间为25个小时。在一个实施例中，任何旅行都可以在具体时间开始，或者在具体时间结束，例如早上8:12。在其他实施例中，任何旅行可以在一定范围时间内开始或结束，例如“在早上”。
以最简单的形式，通勤者从H到W，我们可以称之为工作(work)。W是任意位置。它包括学校，祖父母的家，周末高尔夫球场，最喜爱的餐厅，医生的办公室，礼拜场所等。它还可以是某人居住的地方。然而，作为命名约定，我们在大多数公开内容中使用短语“工作”；该约定不是限制性的。然后通勤者从W返回H。我们将这两个行程称为往返通勤路径。如图4A所示。
抵达一处再从另一处出发的通勤路径是更复杂的通勤的一个示例。如图4B所示。此时通勤者从H到地点W
通常，我们的方法适用于任何旅行。在图4C中，我们看到一个通勤路径的示例，其具有从W
定义1通勤路径是发生在任意时刻的行程W
通勤路径可以看做交通系统内路线的说明(specification)。在定义1中的各种W和H指明了通勤者希望前往的地方。
在一个实施例中，我们考虑一个更简单的通勤路径H→W
我们的方法找到沿任何通勤路径的最短的行程时间。各种现有技术本身已经解决了这一问题。但是，我们的方法可以在大大减少的时间内找到所有房屋的行程时间。
4.4交通系统预处理
该方法预处理有关公共交通系统的数据，以便预先计算(precompute)并存储所有房屋的最短出行。
4.4.1最短行程的计算
我们描述了一种方法用于有效计算所有的房屋和所有的公共交通站点位置之间的最短出行。在大多数的公开内容中，我们称站点为停靠站(stopstations)，并且其包括公共汽车站，地图站台，或者两者都有。
该方法开始于对公共交通系统(public transportation system)建模的任意公共交通系统图(graph)GT，该图可从现有技术中获得。该图可以包含代表公共汽车站，地铁站台或两者的顶点(vertexes)。图表中还可以存在其他顶点，例如，代表车辆的停靠点或转弯处，或者步行的停顿点或转弯处。对应于车辆停靠点的顶点在图中用
STOPSTATION_s
表示，通过s索引。存在有方向的加权边(directed weighted edges)，每个加权边代表沿着从边的源顶点到边的目标顶点的一段的行进时间。图中可能存在其他边。一条边可以表示从一辆车换乘到另一辆车。该图可以包含关于各种公共交通工具的出发时间或到达时间的数据。Dijkstra’s的最短图表路径(shortest graph paths)算法，或A*(A星号)搜索算法，通常用于计算具有最短图表路径长度(权重之和)的图表路径，代表最短行程时间，从
STOPSTATION_s’
到其他的STOPSTATION_s”，
对于任何的s’和s”，还包括行程是在具体时间开始，或者在具体时间结束。
我们的方法扩展了公共交通系统图GT。如图5所示。
第一个扩充引入了停靠站集群(clusters of stopstations)。该方法使用任意集群算法对停靠站进行集群；在一个实施例中，当两个停靠站之间的地理距离至多为阈值(threshold)，例如5米，或者当两个停靠站之间的行程时间至多为临界值时，该方法将两个停靠站放到一个集群中。当我们指集群内的地理位置时，我们可以指集群的位置，例如集群的中心。对于每个停靠站集群c，该方法添加两个顶点
STOPSTATION_CLUSTER_SOURCE_c
以及
STOPSTATION_CLUSTER_TARGET_c
以及将集群与GT的停靠站连接的边
STOPSTATION_CLUSTER_SOURCE_c→STOPSTATION_s’
标记为FirstWaitGetOn，和
STOPSTATION_s’→STOPSTATION_CLUSTER_TARGET_c
标记为Zero,对于任意的s’，只要s’位于集群c中。边的权重为零。结果图由GC表示，具有顶点VC和边EC。所有c的顶点的子集
STOPSTATION_CLUSTER_SOURCE_c
用VS表示。
第二个扩充引入了房屋集群。该方法使用任意集群算法对房屋集群；在一个实施例中，该方法使用与集群停靠站时相同的算法。类似的，我们可能会引用房屋集群的位置。对于每个房屋集群，该方法增加顶点
HOME_CLUSTER_SOURCE_s
以及顶点
HOME_CLUSTER_TARGET_s.
该方法使用步行将每个房屋集群连接到停靠站集群。具体的，如果对于任意的s和c,存在从房屋集群s的位置到停靠站集群c的位置的步行，且边的权重设置为步行的时间，该方法添加边
HOME_CLUSTER_SOURCE_s→STOPSTATION_CLUSTER_SOURCE_c
标记为Walk；以及当对于任意的c和t，存在反方向的从停靠站集群c的位置到房屋集群t的位置的步行，且边的权重设置为步行的时间，一个“反向的”边
STOPSTATION_CLUSTER_TARGET_c→HOME_CLUSTER_TARGET_t
标记为Walk。在一个实施例中，该方法将步行限制为以特定速度(例如4km/h)执行的最短步行，最多持续一个阈值(例如1小时)。结果图用G表示。我们用VH表示所有s的顶点
HOME_CLUSTER_SOURCE_s
的集合；并且用EH表示所有的s和c的边
HOME_CLUSTER_SOURCE_s→STOPSTATION_CLUSTER_SOURCE_c
的集合。
我们感兴趣的是计算从每个停靠站集群到每个房屋集群的最短图表路径，以及反过来从每个房屋集群到每个停靠站集群的最短图表路径。
我们注意到，我们的方法通过“统一”相对于最短图表路径本质上相同的位置，来显著提高最短图表路径计算的性能。例如，在一栋高层公寓大楼中，可能有数百个房屋，我们的方法将把它们“统一”到一个房屋集群中。因此，最短图形路径算法仅需要为一个房屋群集而不是数百个组成房屋计算最短图形路径。
然而，狄克斯特拉算法的标准应用仍会产生较差的性能。该应用程序从每个G中的
STOPSTATION_CLUSTER_SOURCE_c
运算算法，没有任何
HOME_CLUSTER_SOURCE_s
顶点，然后从G中的每个
HOME_CLUSTER_SOURCE_s
运行算法，没有任何
HOME_CLUSTER_TARGE_t
顶点。组合的渐近时间复杂度(asymptotic time complexity)为
O(|VS|·(|EC|+|EH|+(|VC|+|VH|)log(|VC|+|VH|))
+
O(|VH|·(|EC|+|EH|+(|VC|+|VH|)log(|VC|+|VH|))).
我们的方法在此标准应用上有所改进。我们观察到，在给定相同的集群阈值的情况下，在大都市区中，通常情况下，房屋集群的数量明显大于停靠站集群的数量|VH|＞＞|VS|。利用这种观察，我们的方法使用了一种不同的算法用于计算从房屋集群的最短图表路径：该方法反转(reverses)G的边，并针对反转图中的每个
STOPSTATION_CLUSTER_TARGET_c，
使用狄克斯特拉算法(到任意顶点
HOME_CLUSTER_TARGET_t
都可以删除)，计算到所有顶点
HOME_CLUSTER_SOURCE_s
的最短图表路径。这产生了预期的效果，因为当我们在反转图中，反转从
STOPSTATION_CLUSTER_TARGET_c
到
HOME_CLUSTER_SOURCE_s
的任意最短图表路径的边时，我们获得了原始(非反向)图中从
HOME_CLUSTER_SOURCE_s
到
STOPSTATION_CLUSTER_TARGET_c
的最短图表路径。因此，我们方法的渐近时间复杂度只是
O(|VS|·((|EC|+|EH|)+(|VC|+|VH|)log(|VC|+|VH|))).
在实践中，我们的方法可以大大减少首尔市地区图G上的总运行时间。
在相反的情况下，当停靠站集群多于房屋集群|VH|＜|VS|时，所述方法使用对称算法。在那种情况下，当计算从停靠站集群到房屋集群的最短图表路径时，该方法将边反向。
在一个实施例中，该方法使用出发时间(departure times)。对于给定的从
STOPSTATION_CLUSTER_SOURCE_c
的出发时间，该方法计算从每个
STOPSTATION_CLUSTER_SOURCE_c
到每个
HOME_CLUSTER_TARGET_t
的最短图表路径。在那种情况下，该方法使用适当的现有技术图表GT,该图表可以详细说明从公共交通工具站点的出发时间；在这种情况下，有时使用与时间和地理位置对应的顶点，以及代表从当时的地理位置开始的行程时间的边表示。类似地，该方法基于在
STOPSTATION_CLUSTER_TARGET_c
处给定的到达时间在反向图表中进行计算。最短图表路径将这些到达时间转换为从每个
HOME_CLUSTER_SOURCE_s
的出发时间。在给定到达期限(arrival deadline)的情况下，类似的图表可以用于计算最短图表路径。可以使用适当构造的图来计算截止日期之前到达的概率。
在一个实施例中，我们不使用任何顶点
STOPSTATION_CLUSTER_SOURCE_c
或者任何的顶点
STOPSTATION_CLUSTER_TARGET_c
来扩展GT。相反，我们直接使用具有任何顶点
STOPSTATION_s’
的Walk edges连接任意的顶点
HOME_CLUSTER_SOURCE_s
以及任意的顶点
HOME_CLUSTER_TARGET_t。
在一个实施例中，我们不使用任何的顶点
HOME_CLUSTER_SOURCE_s
或任何顶点
HOME_CLUSTER_TARGET_t
来扩展GT.相反，我们添加了顶点
HOME_s,
每个顶点代表一处房屋，我们直接通过Walk edges将其连接到任意顶点
STOPSTATION_s’。
在一个实施例中，我们不对房屋进行集群。
在一个实施例中，我们不对停靠站进行集群。
在一个实施例中，在给定到达期限的情况下我们计算最短图表路径：在给定每个房屋集群到达期限的情况下，计算从停靠站集群到达房屋集群的最短图表路径，或者在给定每个停靠站集群的到达期限的情况下，计算从房屋集群到停靠站集群的最短图表路径。
在一个实施例中，我们使用任意的最短图表路径算法而不使用Dijkstra算法，例如，A*(A星号)搜索算法。在一个实施例中，我们使用一个最短图表路径的近似算法(approximation algorithm)。我们可以使用没有任何性能改进的算法。
在一个实施例中，一些图形的边上的权重代表出行的货币成本，而不是行程时间。然后我们的方法基于通勤路径的货币成本搜索或比较房屋。可以使用边的权重的任何其他语义，例如：公共交通工具之间的换乘次数，等待时间，等待的货币成本，或者行程的距离。
在一个实施例中，我们基于一个多维成本(multi-dimensional cost)应用了多目标优化搜索(multi-objective optimization search)。例如，我们搜索一条最短图表路径，其长度表示行程时间，从而表示图形路径的货币成本至多为阈值，或者当货币成本作为一个补偿被添加到图表路径长度时。
在一个实施例中，出行路径用图表路径表示。我们使用最短图表路径计算最短出行路径的各种特征，例如：最短图表路径的第一个(即，登机)或最后一个(即下车)停靠站，最短图表路径的主要的交通停靠站，车辆换乘次数，出行期间花费最多时间的车辆(例如公共汽车1234)，在停靠站总的等待时间，总的步行距离，特定的最短图形路径通常在高峰时段是否拥堵，或者沿图形路径的一系列地理位置。在请求处理期间这些特征可以被使用，以筛选特征与请求中指定的条件相匹配的出行路径。
在一个实施例中，我们计算一些图表顶点之间的两条或多条图表路径。例如，从顶点u到顶点v的一条图表路径上最多可以有一辆公共汽车，并且从顶点u到顶点v的其他图表路径上可以没有任何地铁，但是比最短图表路径长不超过10分钟。
在一个实施例中，我们计算符合各种筛选条件(filtering conditions)的图表路径。例如，最多换乘一次的图表路径，或者最多特定的步行时间。
在一个实施例中，我们使用路由引擎(例如现有技术)来计算房屋和公共交通站点之间的最短出行。因此，我们有时可能不使用在目前的当前4.4.1部分描述的图表。
在4.4.1部分描述的方法计算从每个房屋到每个停靠站的最短出行，以及反方向上的最短出行。接下来，我们描述了一种数据结构，用于有效存储和处理我们的方法实用的最短出行数据。
4.4.2最短行程的储存
在一个实施例中，我们的方法以向量形式(vector form)存储(stores)行程时间。该方法以某些顺序(例如随机顺序)将停靠站集群排序为s
v
存储一个从s
房屋集群序列简化了到每个房屋集群的最短行程时间的计算。例如，如果通勤者需要从停靠站集群
在一个实施例中，该方法使用相同的房屋集群序列存储从房屋到停靠站的反向行程的时间。即，该方法存储向量
v′
从而v’
通常，同一停靠站集群s
在一个实施例中，该方法使用一个字节的计算机内存来存储四舍五入到最接近的分钟的行程时间，该字节表示为0到254之间的无符号整数，其中255表示未知或太大的行程时间。此存储使用现代计算机硬件支持向量运算(Vector Operations)和饱和运算(Saturation Arithmetic)(例如AVX-512指令集，或GPU内部函数)实现有效的向量加法，同时将误差保持在最多半分钟的可接受水平上，并且覆盖长达超过4小时的普通行程时间。可以使用任何其他舍入方式(rounding)，例如以秒计算的时间可以除以120，然后舍入为整数，它将以2分钟的粒度表示持续时间。
在一个实施例中，该方法存储存储的向量不用于集群。例如，s
在一个实施例中，该方法实用其他形式的向量存储行程时间。例如，哈希图(hashmap)，或者(坐标，值)列表(list)。当存在很多未知的或过长的行程时间时，这些稀疏形式可能是有利的。
在一个实施例中，该方法使用遵循房屋集群序列h
4.5一条通勤路径的行程时间
我们描述了我们的方法如何有效地计算任何通勤路径的最短行程时间。考虑从房屋集群H离开，经过的k≥1工作，返回到房屋集群的任意通勤路径：H→W
4.5.1中间部分：行程W
该方法找到不包括家庭集群的行程W
我们注意到，只需要对路由引擎查询k-1次。该数量与房屋的数量无关。
在一个实施例中，当查询路由引擎时，该方法使用出发时间(departure time)，到达期限(arrival deadline)，或者请求的其他部分。
接下来，该方法计算通勤路径的抵达一处再从另一处出发部分(open-jaw part)的最短行程时间：包括房屋集群的两个部分H→W
4.5.2开始(start)部分：行程H→W
该方法考虑了从H到W
该两种方式的方法可以用于每个房屋集群。我们还记得，向量v'
计算从房屋集群h
在一个实施例中，只有当从房屋集群H
在一个实施例中，由于v'的向量表示，该方法使用对v'的向量运算(vectoroperations)，共同计算每个房屋集群的行程时间，如下所示：
for j＝1 to m
a
for all s
w＝walk(s
for all j∈J
w＝walk(H
a
在一个实施例中，所述方法使用数学公式(mathematical formula)
其中，“+”运算(operation)会向向量的每个坐标值上添加一个数，并且“min”运算(operation)计算多个向量在每个坐标处的最小值。[073]行程时间的向量(a
在一个实施例中，unit8数字格式用于存储a
在一个实施例中，所述方法在停靠站集群位置处使用临近算法(nearest-neighbor)数据结构(例如KD树)，在请求处理期间快速计算集合A。
在一个实施例中，所述方法将集合A限制为最接近W
在一个实施例中，所述方法将集合A限制为距离W
在一个实施例中，所述方法预先计算在距离每个房屋集群位置临界距离内的点和房屋集群位置之间的最短步行时间，或者预先计算距离停靠站集群位置临界距离内的点和停靠站集群位置之间的最短步行时间。然后，在请求处理期间，所述方法不查询任何步行引擎，而是使用预先计算的步行时间。
在一个实施例中，使用忽略任何障碍物的测地线来估计最短的步行时间。这可能会以准确性为代价来加快walk(s
在一个实施例中，公式1中使用了出行路径。例如，如果用户请求指定了限定车辆换乘次数的条件，我们在公式中过滤s
在一个实施例中，就像我们在v'
在一个实施例中，对于i的集合，向量v'
在一个实施例中，对于i的集合，向量v'
4.5.3结束(end)部分：行程W
计算是类似的，但是实用向量v,而不是v'。如图9所示。所述方法计算距离W
与之前类似，在一个实施例中，由于v的向量表示，该方法根据公式2使用对v的向量运算来联合计算到达每个房屋集群的行程时间。在一个实施例中，所述方法使用数学公式
行程时间的向量(b
该方法使用与4.5.2部分类似的实施例。例如，在一个实施例中，该方法使用向量运算来一起计算向量(a
4.5.4组合开始，中间以及结束部分
最后，该方法计算(computes)每个房屋集群的通勤路径的最短行程时间。该方法简单地将两个向量相加，并在坐标处移位值。我们通过
PathDurations(→W
来表示所得的向量，其中，第一个“+”是向量的坐标方向加法，第二个“+”是向量的每个坐标处的值加一个数字。
在一个实施例中，该方法在给定沿任意通勤路径的任意地理位置处的具体的出发时间或到达期限的情况下，计算行程时间。
在一个实施例中，该方法为特定的通勤路径预先计算PathDurations。例如，该方法为学校中的每个W计算并存储
PathFromHomeDurations(→W)
和
PathToHomeDurations(W→)。
在请求处理期间，该方法从数据库中检索预先计算的向量，而不是使用公式1，公式2和公式3计算它们。
在一个实施例中，PathDurations的值可能会改变。考虑一所具有分区要求的学校W，该要求指定只有某些房屋可以将孩子送入学校。这可以通过以下方式简单地实现：对于学校区域(zone)之外地这些房屋集群，将向量PathFromHomeDurations(→W)坐标处的值设定为无穷大，并且类似地，设定向量PathToHomeDurations(W→)坐标处的值。当W是送货范围有限的餐厅，或者是管辖范围有限的政府办公室时，可以进行类似的更改。因此，更改的值可以被存储，并在请求处理期间被检索。
在一个实施例中，我们的方法将任意“操作”(manipulation)函数应用于向量v
在一个实施例中，该方法为房屋集群的子集计算PathDurations。例如，子集是根据用户请求指定的房屋特征的条件确定的。在一个实施例中，我们选择房屋集群的序列h
4.6搜索一间房屋
我们的方法讲授如何利用通勤有效地搜索房屋。在介绍对房屋的一般搜索请求之前，我们先介绍一些搜索请求示例。
4.6.1加权总和请求
考虑一个家庭，一个父母每周在geo1上班五次，同时另一位父母每周在geo2上班三次。该家庭想要寻找一个每周行程时间短的房屋。我们可以为该家庭找到每个房屋集群的每周行程时间，以两个向量的加权和(weighted sum)表示，如下所示：
5*PathDurations(→geo1→)+3*PathDurations(→geo2→)。
4.6.2最低要求
考虑一个在家工作的单身母亲，并且正在送孩子上学。该母亲想要找到一间靠近学区E中的任何学校的房屋。我们可以找到每个房屋集群中孩子的每日行程时间，作为向量的坐标最小值(coordinate-wise minimum)，如下所示：
4.6.3房屋的一般搜索
在一个实施例中，我们的方法将请求定义为通勤路径路径1，...，路径q(q为任意值)的任意序列，以及函数导数：R
PathDurations(路径1)＝(d
PathDurations(路径q)＝(d
并将函数的导数坐标应用到向量上，以得到向量
RequestDurations(路径1，...,、，路径q，导数)＝
(导数(d
导数(d
导数(d
每个房屋集群的“导源”行程时间。
在一个实施例中，该函数导数是数的加权和
导数(x
对于权重w
在一个实施例中，所述函数导数是最小数
导数(x
在一个实施例中，所述函数导数是一个加权和及最小值
导数(x
在一个实施例中，函数的导数是一个条件函数，例如
导数(x
If x
返回x
else
返回∞]，
或任何算法。
4.7比较两个或多个房屋
我们的方法教授如何利用通勤有效地比较多个房屋。在介绍一般的比较请求之前，我们将通过一些示例说明该方法。
4.7.1目前的房屋
考虑目前居住在房屋中的一个家庭。家庭成员都有特定的通往工作场所，学校，或其他地方的通勤路径。该家庭考虑搬到其他房屋，并希望将当前房屋的总行程时间与其他预期房屋的总行程时间进行比较。我们的方法使得这种比较相当简单。
在一个实施例中，该方法计算每个房屋集群的行程时间，包括该家庭目前的房屋S的房屋集群h
RequestDurations＝(q
然后该方法以“差”向量(difference)作为响应：该方法从每个坐标处的值减去第j个坐标处的值
(q
“差”向量的坐标处的负值表示，与该坐标相对应的房屋与当前房屋S(home)相比具有较短的行程时间。
在一个实施例中，该方法对当前房屋使用一些通勤路径，而对其他房屋使用其他通勤路径。因此，该方法可以帮助一个家庭评估假设情景：“假设我们要更换工作场所，并搬到其他地方。新的通勤时间与我们目前的通勤时间相比将如何？”
4.7.2两个或更多房屋的一般比较
考虑一个家庭，其中父母必须继续通勤去相同的工作地点(没有工作变动)，但是孩子可以换学校。考虑两个家庭的其它例子：父母和他们的祖父母。他们想要找到两所房子，这两所房子彼此相距约30分钟内，以便以锁房屋靠近任意医院，同时另一所房屋靠近特定的学校和工作场所。我们的方法使得这种房屋与其他房屋的比较相当简单。
在一个实施例中，该方法计算房屋集群的一系列通勤路径的行程时间PathDurations
PathDurations(路径
PathDurations(路径
然后该方法应用一个“通用”函数导数，该函数不按4.6.3节中的说明进行协调操作，而是在所有q·m行程时间上共同操作，并生成一个或多个数字的向量。换句话说，所述通用函数为
导数：R
对于一些y。
4.8搜索或比较
在一个实施例中，所述的函数的导数(deriver)可以是采用任何输入(例如：通勤路径，最短出行路径，最短行程时间，房屋，或用户请求指定的任何条件)的任意算法，例如随机算法，并产生任何输出(例如，包含满足用户条件的房屋的“排行榜”(top list)，以及具有最短行程同时也满足用户条件的房屋，按最短行程时间排序)。
4.9变体
在不脱离实施例范围和精神的情况下，许多修改和变化对于本领域普通技术人员将是显而易见的。我们提供一些变体进行说明。
4.9.1延长行程
在一个实施例中，该方法首先计算不完整的最短行程，然后将它们延伸(extends)到所选择的房屋集群。由于向量v
该方法确定房屋连接器(connectors)，它们是交通系统的某些要素。在一个实施例中，所述的房屋连接器是房屋的集群或停靠站的集群，其可以与4.4.1部分讨论的集群不同。然后，该方法使用类似于4.4部分中的实施例，预先计算并在数据库中存储停靠站集群和房屋连接器之间的最短行程。
当收到请求时，该方法计算请求中包含的工作W和选定的房屋集群之间的最短行程。为此，该方法确定工作W附近的停靠站集群，并检索预先计算的附近的停靠站集群和房屋连接器之间的最短行程，以计算工作W和房屋连接器之间的最短行程，类似于4.5部分。在一个实施例中，这种计算使用类似于4.5.2部分和4.5.3部分的向量运算。然后，将这些最短行程延伸到房屋连接器之外，以构成工作W和选定的房屋集群之间的最短行程。这可以通过简单地为每个房屋集群找到一个最小的延伸行程(可能不只是步行)来实现，该最小延伸行程穿过房屋集群附近(例如2000米以内)的任何房屋连接器，有时还可以找到工作W和房屋群集之间的直接的最短行程(类似于4.5.2和4.5.3部分)。在一个实施例中，在重叠区域中，该方法使用房屋连接器以及向量v
延伸行程的性能与房屋连接器的总数成正比，并且与任意选定的房屋集群附近的房屋连机器的数量成正比。在一个实施例中，延伸用于大都市区的稀疏部分，在那里两个量可能很低。在一个实施例中，该方法使用性能成本函数来：(1)确定房屋连接器；(2)选择房屋集群，以及(3)确定每个选择的房屋集群附近的房屋连接器的子集。
4.9.2利用汽车通勤
在一个实施例中，我们通过汽车而不是通过公共交通工具来计算通勤路径的行程时间。这可以通过对前面的部分进行简单的修改来实现。
当对房屋的运输系统预处理时，参考第4.4节，我们将GT作为汽车行驶系统图，而不是作为公共佳通系统图。该汽车行驶图可以获得(例如从现有技术获得)。该图可以有表示道路地理位置的顶点，以及表示驾驶汽车或转向汽车的边；边可能包含有关一天中不同时间(例如在高峰时段)行驶持续时间的数据。
我们扩展GT。对于每个房屋集群s，我们添加顶点
HOME_CLUSTER_SOURCE_s
和
HOME_CLUSTER_TARGET_s.
对于至少一个r，我们通过添加顶点
CONNECTOR_r
将每个房屋集群与一些在阈值距离(例如100米)内的道路连接起来。在一个实施例中，顶点表示家庭聚类位置在阈值距离内的道路上的最短距离投影(shortest-distanceprojection)；该道路可以在分配给家庭集群的停车场内。顶点通过标记为Zero0并且权重为0的边连接到两个房屋集群顶点。该顶点还连接到代表路段端点的顶点。不添加停靠站集群，我们在此不需要，因为现在的GT不对任何地铁站或公交车站建模，我们为s’和t’的集合添加顶点
REPRESENTATIVE_SOURCE_s'
和
REPRESENTATIVE_TARGET_t'，
这些顶点代表(represent)最短行程中经常出现(frequently occur)的位置；这些位置可以获得(例如从现有技术获得)。这些顶点可以代表集群。这些顶点使用边与其他顶点适当连接。
我们可能使用与4.4.1部分所述的类似的实施例，使用扩展的GT计算从每个
REPRESENTATIVE_SOURCE_s'
到每个
HOME_CLUSTER_TARGET_s的图表路径的最短持续时间，以及从每个
HOME_CLUSTER_SOURCE_s
到每个
REPRESENTATIVE_TARGET_t’的图表路径的最短持续时间。这些行程时间将以向量形式v
当计算通勤路径的行程时间，我们使用汽车出行，而不是使用4.5部分的步行。
对于行程的开始部分，我们对4.5.2部分进行了以下修改。代替walk(H
REPRESENTATIVE_TARGET_t’
的集合。对于每个s
对于行程的结束部分，我们做类似的修改，但是是针对4.5.3部分。代替walk(W
REPRESENTATIVE_SOURCE_s’
的集合。对于每个s
我们使用4.5部分描述的其他实施例。例如，我们可以使用测地线估算汽车行驶的持续时间。
可以简单扩展4.6部分的搜索框架，以限制每条通勤路径应该使用哪种车辆。结果，例如，我们可以确定一个家庭的每个房屋的通勤路径的行程时间，其中一位父母每周乘车5次到geo1上班，同时另一位父母每周乘公共交通工具3次到geo2上班。
4.7部分的比较框架可以类似地扩展。结果，例如，我们可以搜索一处新的房屋，某人将从该处乘汽车通勤，并且与目前乘公共交通工具的行程时间比较。我们的方法的结果可能被用作鼓励因搬家而购买汽车的动机。
4.9.3通过其他方式通勤
在一个实施例中，该方法通过其他方式使用通勤路径，例如：仅步行；仅自行车；仅快车和步行；仅地铁和步行；仅高速巴士，地铁和步行道；仅可共享面包车和步行；船；飞机等等。我们仅使用与第4.9.2节中描述的修改类似的修改。在一个实施例中，该方法识别其他房屋和其他旅行方式，并将其推荐给用户，并解释与当前房屋和当前旅行方式相比的收益。
可以在不知道图的各个顶点的地理位置的情况下计算给定图中的最短图路径。因此，在一个实施例中，该方法使用其各种要素(elements)缺少地理位置的交通系统。
交通系统无需物理移动物体。该方法仅需要能够确定交通系统的要素之间的路线或路线长度。因此，移动数据的计算机网络是交通系统的一个示例，包括以下交通元素：电线/线路(类似于道路)，以及集线器/开关(类似于车站/转弯)。交通系统的许多其他示例对于本领域普通技术人员将是显而易见的。
4.9.4行程路径的条件
我们可以简单地实现行程路径上的各种筛选条件(filtering conditions)。例如，我们可以构建图表G，该图G在任何的地铁路线之间都没有换乘，只在房屋集群和车站集群之间可以步行。采用类似于4.9.2部分描述的修改，然后，该方法将在上下班途中通勤者可能一直坐着时搜索或比较房屋(房屋和工作都需要在一条地铁线的地铁站的步行距离之内)。类似地，我们可以构建一个G并修改最短图形路径算法，以将图形路径限制为至多一次换乘，或者一次地铁-公交换乘，或者公交-地铁换乘，或在时间窗口内发生的换乘，或者通勤者常用的一种行程路径。如本领域普通技术人员将显而易见的，用于筛选行程路径的其他变型落入我们的方法的范围内。
4.9.5房屋条件
在一个实施例中，所述方法接收关于房屋的各种特征的过滤条件，并且搜索或比较其特征与该条件相匹配的房屋。这些特征可能是：类型(例如，独立式住宅或高层公寓)，交易类型(例如，出售或出租)，价格，房地产经纪人佣金，税金，最高银行贷款金额，卧室或洗手间数量，房屋的面积/尺寸，窗户的朝向，房屋的楼层，建筑物的楼层，或典型的每月管理费。简单地，该方法为每个房屋提供一个特征列表，并在给定条件的情况下确定其特征与该提交相匹配的房屋。这些相匹配的房屋的行程时间可以从房屋集群的行程时间处获得。用于过滤房屋的其他变型落在我们方法的范围内，这对本领域内任何普通技术人员将是显而易见的。
4.9.6元搜索或比较
在一个实施例中，该方法使用先前的搜索或比较请求和响应的集合来搜索或比较房屋。可以将其视为元方法(meta method)(一种使用自身的方法)。例如，它对于估算拟议的新房地产开发的价值很有用。
我们描述了元方法的一个实施例。我们收到通勤路径path
第j个聚合是房屋集群H
元方法的许多其他实施例对于本领域普通技术人员将是显而易见的。在其他实施例中，通勤路径是根据房屋和工作的地理位置生成的。在其他实施例中，对于某些具有最短行程时间的房屋集群，权重设置为非零，其他设置为零。在其他实施例中，数据科学家评估假设情景；由于我们方法的优势，可以快速评估这些情况。在其他是实力中，所述聚合器为任意算法，例如一种计算方差，分位数，累积分布函数或超过阈值的概率的算法。
4.9.7涉及两个或更多房屋的通勤路径
在一个实施例中，一条通勤路径涉及(involves)两个或更多房屋。例如，这在两个或多个家庭共同搜索或比较房屋时很有用。
在一个实施例中，H
在一个实施例中，我们预先计算两个向量(a
在一个实施例中，用于H
更一般而言，该方法计算对于k≥2的任意房屋集群序列H
在一个实施例中，通勤路径包括房屋集群之间的直接行程H
4.9.8空间探索
我们的方法引入了高性能的空间探索算法(exploration algorithms)。考虑通勤者沿着具有特定成本的特定的通勤路径H
空间探索的一个实施例是梯度下降法(gradient descent algorithm)。成本函数可以是任意可微函数(differentiable function)；例如，给定固定的path，该函数将两个房屋H
在一个实施例中，我们预计算消耗线性O(m)空间的向量(a
在一个实施例中，我们不预计算(a
在一个实施例中，空间探索算法可能对房屋有约束。例如，如果我们到某个房屋的往返通勤，约束将是H
在一个实施例中，空间探索算法使用仅涉及一处房屋的通勤路径：H
在一个实施例中，成本函数取决于房屋和工作。例如，当人们试图使花费的时间和金钱的混合最小化时，可以使用这种成本函数。在一个实施例中，成本函数为：H和W之间的行程时间，加上租用H的货币成本，减去W支付的工资，可能带有权重来表示要素的相对重要性。在一个实施例中，由于我们的方法的优势，在这种成本函数中，可以有效地利用梯度下降来搜索房屋和工作。
4.10一般情况
在一个实施例中，词语“房屋”和“工作”具有任何意义。例如，考虑某人正在寻找位于其当前房屋附近的工作的情况。此人不想搬去另一所房子，只是想找一个离现在的房屋近一点的工作。这种情况下，我们的方法可以简单地运用。给出了人们在整个大都市区工作的一系列地点(例如各种办公室，工厂等)，该方法将计算每个工作场所集群与每个停靠站集群之间的行程时间。因此，该方法可以被看做一种“使用通勤的工作搜索或比较”方法。在一个实施例中，该方法基于用户指定的工作类型，或工资范围，同时基于距离用户当前房屋的行程时间，来搜索或比较工作场所。再举一个例子，考虑一家公司想要将其总部迁至新的地点。我们的方法可以用于计算整个大都市区总部每个新地点的总的“公司行程时间”。因此，公司可以确定每个新位置如何影响员工的通勤。例如，可以选择一个新的位置，以便：(1)最坏情况下的通勤时间受到限制；以及(2)平均通勤时间较短；从而满足个人和社会的目标。
到目前为止，我们的描述主要是将出行时长作为搜索或比较目标。然而，该方法可用于任何其他目标，比如：旅行的货币成本；距离的度量；旅行路线的特定特征或属性，例如：换乘的次数，或者步行距离；或者房屋的特点，例如：价格，尺寸或类型。在一个实施例中，这可以通过构建图表并适当地设置边缘权重来简单地实现。可以将各种目标组合到基于多维成本(multi-dimensional cost)的多目标优化搜索(multi-objectiveoptimization search)中，例如，寻找使行程时间最短的房屋，也就是，不利于行程的货币成本。
通常，该方法使用任意地点S
4.11计算机系统
本发明的实施例之一是利用通勤进行搜索或比较房地产的计算机系统(computersystem)。我们在图11中示出了计算机系统的实施例。
我们在描述中使用术语“模块”(module)。在本领域中已知该术语表示提供一些特定功能的计算机(子)系统。我们将计算机系统划分为特定模块的选择是示例性的，而不是强制性的。本领域普通技术人员将注意到，在不脱离本发明的范围的情况下，可以以其他方式将系统组织成模块。
在一个实施例中，沿着任意通勤路径的每次出行都具有具体的出发时间。
系统的一个模块(1108)从数据源(1102)读取有关交通系统的数据，并构造图G。在构造期间，该模块从房地产数据源(1103)检索房屋数据，并从其他数据源(1104)检索房屋集群和停靠站集群之间以及附近的最短步行路程。该模块输出的图形没有任何的顶点vertexes(1105)
HOME_CLUSTER_SOURCE_s，
并且输出不具有任何的顶点
HOME_CLUSTER_TARGET_s,
但具有反向边(1106)的图形。该模块还构建最近的邻近数据结构(1107)，其可以找到距任何给定地理位置的阈值距离以内的停靠站，并且预先计算在房屋集群和停靠站附近的最短的步行路程(1108)。
同时，系统的其他模块(1109)读取两个图表，并且计算最短图表路径。该模块考虑一天中的时间范围，在一个实施例中，每5分钟考虑一次。对于每个出发时间，该模块使用(1105)生产一个具有从停靠站集群到房屋集群的最短行程时间的表(1110)，并且使用(1106)生成具有从房屋集群到停靠站集群的最短行程时间的其他表(1111)。在一个实施例中，将四舍五入到最接近的分钟的每个行程时间存储为C++编程语言的uint8_t类型，其中最大值255被保留以表示未知或太大的行程时间。在一个实施例中，表以行优先顺序(row-major order)布局(laid out)在HDD硬盘上。在一个实施例中，该系统使用的缓存层次结构(cache hierarchy)包括HDD硬盘，SSD硬盘和主内存。在一个实施例中，使用任何压缩算法(比如增量压缩(delta compression))来压缩(compressed)表或其一部分。我们观察到，对于包含房屋集群和停靠站集群的任何一对，一段时间内的行程时间通常是相似的。这种相似性通常也存在于该对的附近。在一个实施例中，我们选择房屋集群的序列h
模块(1101)和(1109)连续运行。结果，该系统会在给定出发时间的情况下，维持有关行程时间的新数据。
同时，路径持续时间模块(1112)计算PathDurations。在给定具有出发时间的通勤路径的情况下，模块查询(1113)已预先计算的任何相关的PathDurations。任何丢失的消息都是从头开始计算：模块查询导航数据源(1114)，以计算通勤路径中不涉及任何房屋的部分的PathNonHomeDuration。该模块还通过查询最近的停靠站(1107)，步行(1108)，以及出发时间的房屋行程时间向量(1110和1111)来计算涉及房屋的行程时间PathFromHomeDurations和PathToHomeDurations。
同时，请求处理模块(1115)搜索或比较房地产。任何请求(1116)都包含通勤路径，包括沿着通勤路径的地理位置和出发时间，以及派生器。当接收到来自用户的请求，该模块从路径持续时间模块(1112)中检索PathDurations，应用Deriver，并用代表Deriver的输出的信息对用户作出响应(1117)。
本发明的各方面可以采取硬件实施例，软件实施例或两者的组合的形式。根据功能或优化的不同，本发明的步骤，例如任何流程图的块，可以不按顺序执行，部分同时执行，或者从高速缓存提供。方面可以采取顺序系统或并行/分布式系统的形式，其中每个组件体现某些方面，可能与其他组件冗余，并且组件可以例如使用任何种类的网络进行通信。没有参考任何特定的编程语言来描述本发明。可以用任何编程语言(例如C++，Java或JavaScript)编写执行针对本发明各方面的操作的计算机程序。任何程序都可以在任意硬件平台(例如中央处理单元(CPU)或图形处理单元(GPU))以及关联的内存或存储设备上执行。程序可以在一个或多个软件平台上执行本发明的各方面，所述软件平台包括但不限于：运行Android或iOS操作系统的智能手机或网络浏览器，例如Firefox，Chrome，InternetExplorer或Safari。
4.12计算机服务
本发明的一个实施例是使用通勤搜索或比较房地产的计算机服务(computerservice)。用户可以通过用户访问设备(例如智能手机应用程序或网页)使用该服务。对本领域普通技术人员来说，显然本发明不限于这些设备。同样显而易见的是，在不脱离本发明范围的情况下，可以修改附图中服务的呈现(通过重新布置，调整大小，改变颜色，形状，添加或移除组件)。
在一个实施例中，通过智能手机应用程序访问所述程序。如图12所示。用户输入请求。在一个实施例中，所述请求包括：
(1)房地产(1201)的所期望的特征，例如“3间卧室，高层建筑，高楼层”；
(2)通勤路径(1202，1203，“陶森德或耶利哥高中的学校”1204)，出发时间(1205，1206)，以及每条通勤路径的频率(1207，1208)；以及
(3)用户当前的房屋(1209)的地理位置。
作为响应，所述服务反馈代表行程时间的信息。例如，所述服务渲染(renders)与用户请求想匹配的房地产的地理位置(1210)。该服务将呈现这些房地产的行程时间与当前房屋的行程时间的比较。该服务将呈现每个匹配放弃产的概要(summary)，例如其价格。所述房地产可以堆叠(stacked)在2D地图上，从而具有较短行程时间的房地产出现在这些行程时间较长的房地产之上。当地图上存在杂乱时，该服务可以代替地呈现一个房地产集群，其大小与集群中房地产地数量相关。集群可以显示概要，例如集群中房地产的数量或典型特征。
在一个实施例中，所述服务以最短行程时间来呈现房地产。还呈现了房地产的概要(1211)。所述房地产可以通过行程时间排序。
在一个实施例中，该服务呈现“热图”(heatmap)，该“热图”使用颜色来指示从大都市区的每个区域出发的行程时间，例如该区域的最小值，如图1所示。热图可以描绘任何房屋的行程时间和用户当前房屋的行程时间之间的差异。在一个实施例中，热图仅呈现与用于期望的房地产特征想匹配的房地产。
在一个实施例中，所述服务呈现行程时间的柱状图(histogram)(1212)。所述柱状图的一个轴是行程时间，另一个轴是产生该行程时间的房地产部分。在一个实施例中，柱状图仅呈现与用户期望的房地产特征相匹配的房地产。在一个实施例中，用户可以在柱状图中滚动(1213)到柱状图的任何部分，而所述服务将呈现该特定部分的行程时间的结果。在一个实施例中，所述方法使用其他形式的柱状图，例如饼图(pie chart)。
在一个实施例中，用户可以限制出行路径(例如通过使用范围滑块(1214))，例如通过限制总的步行时间，限制换乘次数等等。
在一个实施例中，所述服务呈现房地产的出行路径的概要。
在一个实施例中，所述服务以下列中的至少一项对用户做出响应：
(a)一处位置或地点的地理位置，呈现在地图上；
(b)一处位置或地点的出发时间或到达时间；
(c)一处地点的概要；该概要可以包括：该地点的名称或地址，该地点的价格，或者该地点的尺寸中的至少一个；
(d)组成附近地点集群的地点的概要；
(e)附近地点集群的渲染，渲染的尺寸与附近地点集群中的地点的数量相关；
(f)以路径长度对地点在Z轴上进行堆叠，路径长度越短，堆叠的高度越高，呈现在地图上；
(g)关于路线或路线长度的信息；该信息可以包括以下中的至少一个：(i)路线：长度，持续时间，金钱成本，速度或等待时间；(ii)车辆，车辆道路，人行道，车站，转弯，或公共交通工具的中转站的名称；或者(iii)金钱成本，速度，等待时间，车辆，车辆道路，人行道，车站，转弯，或公共交通车辆的中转站的地理位置；
(h)穿过地点的路线长度的柱状图；或者呈现在地图上的各个地点之间的路线长度的热图；
(i)最小路线长度；通过地点的最小路线长度的柱状图；或者呈现在地图上的各个地点之间的最小路线长度的热图；
(j)加权的路线长度；通过各个地点的加权路线长度的柱状图；或者呈现在地图上的各个地点之间的加权的路线长度的热图；
(k)差路线长度；站点之间路线长度不同的柱状图；或在地图上绘制的各个站点之间的路线长度不同的热图；
(l)推导程序返回的输出的呈现；
(m)一个地点，该地点在旅行的货币成本的限制下，使跨地点的路线长度最小化；
(n)受用户指定条件约束的上述(a)至(m)项之一；或者
(o)符合条件的地点，路线和路线长度中的地点的最高列表，按路线长度排序。
4.13有关权利要求的注意事项
本领域普通技术人员将注意到，在不脱离本发明范围的情况下，可以进行各种修改，并且可以用基本等同的方式进行替换。此外，特定情况下可以适用本发明的指导，而不脱离其范围。因此，尽管事实上已经参考公开实施例描述了本发明，但是本发明并不限于这些实施例。相反，本发明将包括落入所附权利要求的范围内的所有实施例。
4.14术语表
我们包括权利要求中出现的所选短语以及说明书的示例参考的术语表。这些参考并非详尽无遗，还有其他参考存在。所选短语遵循短语首次出现在权利要求中的顺序。
权利要求还使用了以下短语，我们对其含义进行解释：
1.短语“至少一个A”等同于“#
2.短语“一个或多个A”等同于“#
3.短语“多个A”等同于“#
4.短语“至少两个A”等同于“#
5.短语“A或B中的一项”等同于“#
6.短语“A或B中的至少一项”等同于“#
7.短语“至少一个B或C”等同于“至少一个A，其中每一个A都表示(B或C)”
机译： 在运输系统中利用站点和地点之间的路线或路线长度搜索或比较站点的方法和装置
机译： 在运输系统中利用站点和地点之间的路线或路线长度搜索或比较站点的方法和装置
机译： 在运输系统中利用站点和地点之间的路线或路线长度搜索或比较站点的方法和装置
