一种城市的有效路径集搜索方法

摘要

本申请涉及一种城市的有效路径集搜索方法。该方法包括：获取目标分配区域内所有节点的节点信息、所有路段的路段信息及所有OD点对的OD点对信息；根据所有节点的所述节点信息和所有路段的所述路段信息，构建电子道路地图网络；根据所述电子道路地图网络，构建对偶的电子道路地图网络；根据所有OD点对的所述OD点对信息及所述对偶的电子道路地图网络进行有效路径集的搜索，获得所述目标分配区域内的有效路径集，能够面向城市大规模网络实现有效路径集的快速搜索，基于确定有效路段，进一步确定有效路径，避免了有效路径集搜索中可能出现的组合爆炸情况，最终实现有效路径的筛选，加速了有效路径集的搜索。

说明书

技术领域

本申请涉及道路交通技术领域，特别是涉及一种城市的有效路径集搜索方法。

背景技术

在交通规划中，常常使用“四阶段”法，即交通发生与吸引预测，交通分布预测，交通方式划分预测及交通分配预测。其中，交通分配是城市交通宏观规划中最核心重要的环节。它将给定的OD交通量，按照一定的原则分配到城市复杂的道路网络上，为城市出行者提供出行建议、为城市规划者提供定量化的分析与评估。

交通分配一般可分为平衡分配与非平衡分配，其中非平衡分配具有模型简洁易懂，分配效率高，贴近实际情况等优点，因而被广泛使用。非平衡分配又可分为多路径分配与单路径分配，其中多路径分配综合考虑了出行者的多路径选择行为。它反映了出行路径的行程时间、距离等因素对出行者的影响，从而确定出行者选择某条出行路径的概率，进而将各交通小区之间的出行次数按比例分配到起讫小区之间的所有有效出行路径上去。因此，应用多路径分配的前提就是确定各交通小区之间的有效出行路径集合。

随着图论、计算机技术的不断发展，利用计算机进行交通分配的算法和技术得到了巨大的提升与进步。众多学者对多路径分配进行了研究，他们考虑了多种实际影响出行者路径选择行为的因素，构建了许多精妙且符合实际的模型。然而，对于有效出行路径集合生成的研究却很少，往往采用朴素的深度优先搜索(DFS)或K-最短路(KSP)等算法。这些现有的有效路径集搜索方法大多局限在中小规模的交通网络上使用，应用到大规模交通网络上的效果往往不尽人意。这些搜索方法极易陷入路径“组合爆炸”的危机中，导致有效路径集搜索的效率低。

发明内容

基于此，有必要针对上述技术问题，提供一种能够提高有效路径集搜索的效率的城市的有效路径集搜索方法。

一种城市的有效路径集搜索方法，所述方法包括：

获取目标分配区域内所有节点的节点信息、所有路段的路段信息及所有OD点对的OD点对信息；

根据所有节点的所述节点信息和所有路段的所述路段信息，构建电子道路地图网络；

根据所述电子道路地图网络，构建对偶的电子道路地图网络；

根据所有OD点对的所述OD点对信息及所述对偶的电子道路地图网络进行有效路径集的搜索，获得所述目标分配区域内的有效路径集。

在其中一个实施例中，所述根据所有OD点对的所述OD点对信息及所述对偶的电子道路地图网络进行有效路径集的搜索，获得所述目标分配区域内的有效路径集的步骤，包括：

根据所有OD点对的所述OD点对信息，确定所有OD点对的OD点对终节点；

基于堆优化的最短路算法，计算所述OD点对终节点到所述对偶的电子道路地图网络的对偶节点集合中所有其他节点的最短距离，获得所述OD点对终节点到所有其他节点的最短距离；

根据所述OD点对终节点到所有其他节点的最短距离，确定有效路段；

根据所述有效路段，在所述电子道路地图网络中进行深度优先搜索，确定所述目标分配区域内的有效路径集。

在其中一个实施例中，所述根据所述OD点对终节点到所有其他节点的最短距离，确定有效路段的步骤，包括：

对所述目标分配区域内所有路段的起节点到所述OD点对终节点的最短距离进行分析，获得起节点到所述OD点对终节点的最短距离；

对所述目标分配区域内所有路段的终节点到所述OD点对终节点的最短距离进行分析，获得终节点到所述OD点对终节点的最短距离；

依次从所述目标分配区域内所有路段中选取当前路段，当所述当前路段的所述起节点到所述OD点对终节点的最短距离大于所述当前路段的终节点到所述OD点对终节点的最短距离时，确定所述当前路段为有效路段；

当所述当前路段的所述起节点到所述OD点对终节点的最短距离小于等于所述当前路段的终节点到所述OD点对终节点的最短距离时，确定所述当前路段为无效路段。

在其中一个实施例中，所述根据所述有效路段，在所述电子道路地图网络中进行深度优先搜索，确定所述目标分配区域内的有效路径集的步骤，包括：

在所述电子道路地图网络中，按照以OD点对的OD点对起节点到OD点对终节点进行深度优先搜索，确定所有OD点对对应的有效路径；

根据所有OD点对对应的有效路径的路径阻抗对所有OD点对对应的有效路径进行筛选，确定所述目标分配区域内的有效路径集。

上述城市的有效路径集搜索方法，通过获取目标分配区域内所有节点的节点信息、所有路段的路段信息及所有OD点对的OD点对信息；根据所有节点的所述节点信息和所有路段的所述路段信息，构建电子道路地图网络；根据所述电子道路地图网络，构建对偶的电子道路地图网络；根据所有OD点对的所述OD点对信息及所述对偶的电子道路地图网络进行有效路径集的搜索，获得所述目标分配区域内的有效路径集，能够面向城市大规模网络实现有效路径集的快速搜索，基于确定有效路段，进一步确定有效路径，避免了有效路径集搜索中可能出现的组合爆炸情况，最终实现有效路径的筛选，加速了有效路径集的搜索。

附图说明

图1为一个实施例中城市的有效路径集搜索方法的流程示意图；

图2为一个实施例中Sioux Falls道路网络示意图；

图3为一个实施例中Sioux Falls路段编号及阻抗信息；

图4为一个实施例中交通网络中所有节点到节点20的最短距离；

图5为一个实施例中Sioux Falls道路网络有效路段示意图；

图6为一个实施例中给定OD点对的最终有效路径集。

具体实施方式

为了使本申请的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本申请进行进一步详细说明。应当理解，此处描述的具体实施例仅仅用以解释本申请，并不用于限定本申请。

在一个实施例中，如图1所示，提供了一种城市的有效路径集搜索方法，包括以下步骤：

步骤S220，获取目标分配区域内所有节点的节点信息、所有路段的路段信息及所有OD点对的OD点对信息。

其中，目标分配区域是指当前需要进行交通分配的区域。节点信息包括节点数目n，以及每个节点对应的编号，相邻节点集合数目和相邻节点集合等属性，可表示为：v

路段信息包括路段数目m，以及每个路段的编号、起点、终点和阻抗等属性，可以表示为：e

OD点对信息包括OD点对数目u，OD点对的起点和终点等属性，可以表述为od

步骤S240，根据所有节点的节点信息和所有路段的路段信息，构建电子道路地图网络。

其中，电子道路地图网络可表示为G＝；其中，G为电子道路地图网络，V为节点集合，E是路段集合。电子道路地图网络是计算机技术表达的交通实体，目标分配区域的所有路段的起点和终点构成一个节点集合，所有路段构成路段集合；每条路段都有一对起点节点和终点节点；每一个节点都连接至少一条路段，电子道路地图网络的节点集合和路段集合构成了计算机技术表达技术中的图结构。

步骤S260，根据电子道路地图网络，构建对偶的电子道路地图网络。

其中，将路段集合E中所有个体e

步骤S280，根据所有OD点对的OD点对信息及对偶的电子道路地图网络进行有效路径集的搜索，获得目标分配区域内的有效路径集。

在一个实施例中，根据所有OD点对的OD点对信息及对偶的电子道路地图网络进行有效路径集的搜索，获得目标分配区域内的有效路径集的步骤，包括：根据所有OD点对的OD点对信息，确定所有OD点对的OD点对终节点；基于堆优化的最短路算法，计算OD点对终节点到对偶的电子道路地图网络的对偶节点集合中所有其他节点的最短距离，获得OD点对终节点到所有其他节点的最短距离；根据OD点对终节点到所有其他节点的最短距离，确定有效路段；根据有效路段，在电子道路地图网络中进行深度优先搜索，确定目标分配区域内的有效路径集。

其中，基于堆优化的最短路算法，计算OD点对终节点到对偶的电子道路地图网络的对偶节点集合中所有其他节点的最短距离，获得OD点对终节点到所有其他节点的最短距离，具体地：在G′中执行一次基于堆优化的最短路(Dijkstra)算法，计算d

在一个实施例中，根据OD点对终节点到所有其他节点的最短距离，确定有效路段的步骤，包括：对目标分配区域内所有路段的起节点到OD点对终节点的最短距离进行分析，获得起节点到OD点对终节点的最短距离；对目标分配区域内所有路段的终节点到OD点对终节点的最短距离进行分析，获得终节点到OD点对终节点的最短距离；依次从目标分配区域内所有路段中选取当前路段，当当前路段的起节点到OD点对终节点的最短距离大于当前路段的终节点到OD点对终节点的最短距离时，确定当前路段为有效路段；当当前路段的起节点到OD点对终节点的最短距离小于等于当前路段的终节点到OD点对终节点的最短距离时，确定当前路段为无效路段。

其中，对于E中所有路段e

在一个实施例中，根据有效路段，在电子道路地图网络中进行深度优先搜索，确定目标分配区域内的有效路径集的步骤，包括：在电子道路地图网络中，按照以OD点对的OD点对起节点到OD点对终节点进行深度优先搜索，确定所有OD点对对应的有效路径；根据所有OD点对对应的有效路径的路径阻抗对所有OD点对对应的有效路径进行筛选，确定目标分配区域内的有效路径集。

其中，在电子道路地图网络中，按照以OD点对的OD点对起节点到OD点对终节点进行深度优先搜索，确定所有OD点对对应的有效路径，具体地：以一个OD点对为例，在G中执行从该OD点的o

根据所有OD点对对应的有效路径的路径阻抗对所有OD点对对应的有效路径进行筛选，确定目标分配区域内的有效路径集，具体地：获取所有OD点对对应的有效路径的路径阻抗，将路径阻抗大于H的路径从有效路径中删除，获得目标分配区域内的有效路径集，其中，路径阻抗是指组成该路径的所有路段的阻抗和；H＝(1+μ)*w

上述城市的有效路径集搜索方法，通过获取目标分配区域内所有节点的节点信息、所有路段的路段信息及所有OD点对的OD点对信息；根据所有节点的所述节点信息和所有路段的所述路段信息，构建电子道路地图网络；根据所述电子道路地图网络，构建对偶的电子道路地图网络；根据所有OD点对的所述OD点对信息及所述对偶的电子道路地图网络进行有效路径集的搜索，获得所述目标分配区域内的有效路径集，能够面向城市大规模网络实现有效路径集的快速搜索，基于确定有效路段，进一步确定有效路径，避免了有效路径集搜索中可能出现的组合爆炸情况，最终实现有效路径的筛选，加速了有效路径集的搜索。

在一个实施例中，一种城市的有效路径集搜索方法，以Sioux Falls电子道路地图网络为例，具体包括如下步骤：

S1：获取待研究的Sioux Falls区域内所有节点的节点信息、所有路段的路段信息及所有OD点对的OD点对信息。

如图2所示，该网络共计24个节点、76条路段和24*24个OD点对。节点编号标注在节点上；路段连接起节点与终节点，其编号标注在路段附近；OD点对由24个节点互相生成，共计24*24＝528个。路段的阻抗信息如图3所示。

S2：依据所有节点的节点信息和所有路段的路段信息，构建Sioux Falls电子道路地图网络。

S3：根据电子道路地图网络，构建对偶的电子道路地图网络。

具体地，将路段信息的起点与终点属性值互换，形成新的对偶路段集合；更新节点属性信息，形成新的对偶节点集合；依据新形成的对偶路段与对偶节点，构建Sioux Falls对偶电子道路地图网络。

S4：根据所有OD点对的OD点对信息及对偶的电子道路地图网络进行有效路径集的搜索，获得目标分配区域内的有效路径集。

以OD点对(1，20)为例，叙述具体执行内容。

S4.1：计算交通网络中所有节点到节点20的最短距离。通过在对偶电子道路网络图中使用一次最短路(Dijkstra)算法，可以得到所有点到节点20(即OD点对终节点)的最短路径距离。如图4所示。

S4.2：判断有效路段。具体为，对于所有路段，如果路段起点到节点20的最短距离大于路段终点到节点20的最短距离，那么将其记作有效路段；否则记作无效路段。最终有效路段的示意图如图5所示；图5相比与图2，仅保留了有效路段的显示。

S4.3：有效路径集的搜索，具体包括：

S4.3.1：在G中执行从o

S4.3.2：对通过步骤S4.3.2生成的有效路径集进行筛选。将路径阻抗大于H的路径从有效路径中删除。其中，路径阻抗是指组成该路径的所有路段的阻抗和；H＝(1+μ)*w

上述城市的有效路径集搜索方法，能够面向城市大规模网络实现有效路径集的快速搜索；基于有效路段的概念、有效路径阈值，避免了有效路径集搜索中可能出现的组合爆炸情况，最终实现有效路径的筛选；加速了有效路径集的搜索；本发明设计简单，易于计算；本发明为后续多路径交通分配提供了技术支撑与数据基础。

应该理解的是，虽然图1的流程图中的各个步骤按照箭头的指示依次显示，但是这些步骤并不是必然按照箭头指示的顺序依次执行。除非本文中有明确的说明，这些步骤的执行并没有严格的顺序限制，这些步骤可以以其它的顺序执行。而且，图1中的至少一部分步骤可以包括多个子步骤或者多个阶段，这些子步骤或者阶段并不必然是在同一时刻执行完成，而是可以在不同的时刻执行，这些子步骤或者阶段的执行顺序也不必然是依次进行，而是可以与其它步骤或者其它步骤的子步骤或者阶段的至少一部分轮流或者交替地执行。

以上实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。

以上所述实施例仅表达了本申请的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对发明专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本申请构思的前提下，还可以做出若干变形和改进，这些都属于本申请的保护范围。因此，本申请专利的保护范围应以所附权利要求为准。