ArcGIS Network Analyst 扩展模块所使用的算法

ArcGIS Network Analyst 扩展模块中的路径求解程序(即路径求解程序、最近设施点求解程序和 OD 成本矩阵求解程序)均基于 Dijkstra 算法,用于查找最短路径的著名算法。这三种求解程序都实现了两种类型的路径查找算法。第一种精确的最短路径求解算法,第二种则是一种可提高性能的等级路径求解程序。经典的 Dijkstra 算法解决了无向的非负加权图形中的最短路径求解问题。为了应用于实际的交通数据中,该算法进行了修改以便在最小化用户指定的成本属性的同时充分遵照用户的设置(如单行限制、转弯限制、交汇点阻抗、障碍和街边约束)。而且,通过选用更好的数据结构(如 d-heap),Dijkstra 算法的性能得到了进一步的提高。此外,还要求算法能够计算沿着边的任意位置而不仅限于交汇点。

Dijkstra 算法

经典 Dijkstra 算法解决了加权图形中的单源最短路径求解问题。为查找从起始位置 s 到目标位置 d 的最短路径,Dijkstra 算法保留了一组交汇点 S,这组交汇点距离 s 的最终最短路径已经计算完成。该算法将在交汇点集中反复查找具有最小最短路径估值的交汇点,然后将其添加到交汇点集 S 中,同时更新所有不在 S 中却与该交汇点相邻的点的最短路径估值。继续执行该算法,直到目标交汇点得以添加到 S 中。

路径求解

将使用上述著名的 Dijkstra 算法。

了解有关查找最佳路线的详细信息

最近设施点求解

将使用基于 Dijkstra 算法的多起始点—多目的地算法。可以选择只计算最短路径(如果路径位于指定的中断范围内),也可以求出固定数目的最近设施点。

了解有关查找最近设施点的详细信息

OD 成本矩阵求解

将使用基于 Dijkstra 算法的多起始点—多目的地算法。可以选择只计算最短路径(如果路径位于指定的中断范围内),也可以求出固定数目的最近目的地。OD 成本矩阵求解程序与最近设施点求解程序类似,不同之处仅在于前者不计算所生成最短路径的形状,以便减少系统开销并提高性能。

了解有关 OD 成本矩阵的详细信息

等级路径

由于需要搜索大量的边,因此在全国性的网络数据集中查找精确最短路径比较耗时。因此为了提高性能,网络数据集可以模拟运输系统中的固有分级,即驾驶员更希望在州际高速公路上行驶而不是在地方道路上行驶。等级网络创建完成后,将使用双向 Dijkstra 改进算法计算起始点和目的地之间的路径。

此时的总体目标是在支持网络中存在的高阶等级的同时使阻抗最小化。要实现此目标,可以在起始地位置和目的地位置,以及通往更高级别的道路连接或入口点中同时进行搜索,然后搜索更高级别的道路,直到从起始点位置和目的地位置出发的线段相交。由于搜索被限制在较高等级范围内,因此会对较少量的边进行搜索,从而可以提高性能。请注意,这是一种启发式算法;其目的是提高性能并获得有效的解决方案,但无法保证找到最短路径。为成功执行该启发式算法,必须连接最高等级,因为即使执行算法时到达死角,最高等级也不会下降为较低等级。

通常,可以对边权重基于行程时间的等级网络使用该求解程序。这类似人们在高速公路网络上正常行驶。

了解有关使用等级结构进行网络分析的详细信息

使用路径求解程序求解流动推销员问题

路径求解程序可以生成访问停靠点位置的最佳顺序。这便是流动推销员问题或 TSP。TSP 是一个组合问题,表示无法直接找到最佳顺序。启发式算法用于在很短的时间内找到解决此类问题的有效方案。Network Analyst 中的 TSP 实施还要处理停靠点处的时间窗;即,该算法将在最短的时间内找到访问停靠点的最佳顺序。

流动推销员求解程序运行的第一步是在有待排序的所有停靠点之间生成起始-目的地成本矩阵,然后通过基于禁忌搜索的算法查找访问停靠点的最佳顺序。禁忌搜索是求解组合问题的元启发式算法。该算法属于局部搜索算法的范畴。禁忌搜索的具体实施是一个专有过程,但 Esri 内部已经对其进行广泛地研究和开发以期快速取得良好成果。

了解有关查找最佳路线的详细信息

有时间窗的车辆配送 (VRP)

车辆配送 (VRP) 是流动推销员问题的扩展。在 TSP 中,将以最佳方式对一组停靠点进行排序。而在 VRP 中,需要将一组停靠点分配给一组路径或车辆,以便将总路径成本降至最低。还需要考虑实际限制,其中包括车载容量、配送时间窗及司机的特点。VRP 将生成一种解决方案,使得在遵循这些限制的同时,使运行成本和用户偏好(如是否认为满足时间窗较重要)组成的目标函数的值最小。

VRP 求解程序运行的第一步是在网络中的所有停靠点和站点位置之间生成最短路径成本的起始-目的地矩阵。使用该成本矩阵可以通过在最合适路径中一次插入一个停靠点的方式构建初步解决方案。随后可通过以下方式改进初步解决方案:对各路径中的停靠点重新进行排序、将停靠点从一个路径移至另一个路径,或在路径之间交换停靠点。该过程中用到的启发式算法基于禁忌搜索元启发式算法并且归私人专有,但多年来,Esri 内部一直进行着持续的研究和开发,很快将取得良好的成果。

了解有关求解车辆配送 (VRP) 的详细信息

服务区

服务区求解程序也基于 Dijkstra 算法遍历网络。此求解程序的目标是返回已连接的边要素的子集,从而使这些要素位于指定的网络距离或成本中断范围内;此外,还可以返回通过一组中断值进行归类的线,边可能来自这些线中。服务区求解程序可以生成线或其周围的面,也可以同时生成线和其周围的面。

通过将被服务区求解程序遍历的线的几何置于不规则三角网 (TIN) 数据结构中生成这些面。沿线的网络距离将在 TIN 内部用作位置的高度。将服务区求解程序尚未遍历到的位置以更大的高度值置于不规则三角网中。在该 TIN 中,多边形生成例程将用于划分出围绕位于指定间隔值之间区域的地区。多边形生成算法包含生成概化多边形或详细多边形并处理可能遇到的许多特殊情况的附加逻辑。

了解有关计算服务区的详细信息

位置分配

位置分配是求解设施点位置问题的求解程序。即,给定具有权重的 N 候选设施点和 M 请求点,可选择设施点的子集 P,从而使每个 M 到最近的 P 之间的加权距离总和最短。这属于 N 选 P 的组合问题,解空间极大。无法通过检验所有组合获得最优解。例如,即使是像 100 选 10 这样的小问题,也将存在 17 万亿多种组合。此外,位置分配求解程序可以求解各种各样的位置问题,例如最小化加权阻抗、最大化覆盖范围或实现目标市场份额。启发式算法可用于求解位置分配问题。

位置分配求解程序运行的第一步是在网络中的所有设施点和请求点位置之间生成最短路径成本的起始-目的地矩阵。然后通过称为 Hillsman 编辑的进程构建已编辑版本的成本矩阵。该编辑进程使完全相同的求解程序启发式算法得以求解各种不同类型的问题。然后,位置分配求解程序将生成一组半随机的解决方案并应用折点替换启发式算法 (Teitz-Bart) 优化这些解决方案,从而创建一组有效的解决方案。元启发式算法随即会合并这组有效的解决方案以便创建更好的解决方案。如果没有其他改进措施,元启发式算法将返回找到的最佳解决方案。已编辑矩阵的组合、半随机的初步解决方案、折点替换启发式算法和优化的元启发式算法可以快速产生近乎完美的效果。

了解有关执行位置分配分析的详细信息

相关主题

9/15/2013