ArcGIS Network Analyst extension 所用的算法

ArcGIS Network Analyst extension 中的路径求解程序(即,路径求解程序、最近设施点求解程序和 OD 成本矩阵求解程序)均基于用于查找最短路径的众所周知的 Dijkstra 算法。这些求解程序中的每一种均可执行两种类型的路径查找算法。第一类算法可用于查找精确最短路径,而第二类算法则属于可以提高性能的等级路径求解程序。经典 Dijkstra 算法在无向的非负加权图形中求解最短路径问题。要将该算法应用到实际交通数据中,则需要对该算法进行修改以便在最小化用户指定的成本属性的同时遵照用户设置(如单行限制、转弯限制、交汇点阻抗、障碍和街边约束)。选用较适合的数据结构(如 d-heap)可以进一步提高 Dijkstra 算法的性能。此外,算法必须计算到边上的任意位置而不仅限于交汇点。

Dijkstra 算法

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

路径

路径求解程序将使用上述众所周知的 Dijkstra 算法。

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

最近设施点

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

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

OD 成本矩阵

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

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

等级路径

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

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

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

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

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

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

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

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

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

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

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

了解有关车辆配送的详细信息

服务区

服务区求解程序也基于 Dijkstra 算法遍历网络。其目标是返回连接的边要素的子集,以使它们在指定的网络距离或成本中断之内。另外,它可以返回由一组边可能位于其中的休息点值分类的行。服务区求解程序可以生成线或其周围的面,也可以同时生成线和其周围的面。

通过按用户提供的距离缓冲线来生成面。用户也可以创建高质量的面,使得面包含相比于非遍历线更接近遍历线的所有区域,直至达到用户提供的距离。

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

位置分配

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

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

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