一种城市路网的负载平衡方法

1.一种城市路网的负载平衡方法，其特征在于：它包括以下步骤：
S1.统计给定车流中所有车辆的出发地和目的地信息，将给定车流中具有相同出发地和目的地的所有车辆定义为一条分支车流，计算该条分支车流从出发地到目的地的最短路径；
S2.利用该最短路径构成第一网络拓扑，根据该第一网络拓扑计算现有第二网络拓扑的各链路的权重W，根据各链路的权重W重新计算步骤S1中所述的该条分支车流的最短路径；
所述的步骤S2包括以下子步骤：
S21.根据步骤S1计算出来的最短路径构造第一网络拓扑；
S22.找出该第一网络拓扑中的所有链路中的最小的可通行交通量C；
S23.将步骤S22中得到的最小的可通行交通量C与步骤S1中所述的该条分支车流的车流量进行比较：
若该最小的可通行交通量C小于该条车流的车流量，则根据该最小的可通行交通量对该条分支车流中的部分车辆进行线路规划标记，并为这部分车辆计算最短路径；
若该最小的可通行交通量大于该条分支车流的车流量，则对该条分支车流中的所有车辆进行线路规划标记，并为该条分支车流中的所有车辆计算最短路径；
S24.更新第一网络拓扑上的所有链路的可通行交通量C；
S25.计算步骤S23中计算出来的最短路径上的所有链路的权重W；
步骤S25中所述的链路的权重W通过以下公式计算得出：
W(e)＝W′(e)(1+Q(e)/V(e))
式中：W(e)—链路e修改后的权重，W′(e)—链路e的当前权重，Q(e)—链路e当前的交通量，V(e)—链路e的实际通行能力；
S26.判断步骤S1中所述的该条分支车流中的所有车辆是否都进行了线路规划标记，若该条分支车流中的所有车辆都进行了线路规划标记，则跳转步骤S3，否则跳转步骤S22；
S3.重复步骤S1～S2，为给定车流中的所有车辆计算最短路径。
2.根据权利要求1所述的一种城市路网的负载平衡方法，其特征在于：所述的步骤S1包括以下子步骤：
S11.将出发地定义为源节点s，目的地定义为宿节点t；找出给定车流中的一条分支车流中源节点s的所有出度边上的邻接节点；
S12.根据现有网络拓扑中链路的可通行交通量C设置各链路的权重W，各链路的权重W为该链路可通行交通量C的反比；
S13.根据步骤S12得到的链路的权重计算源节点s的所有出度边上的邻接节点到宿节点t的最短路径。
3.根据权利要求1所述的一种城市路网的负载平衡方法，其特征在于：所述的最短路径为时间最短路径或距离最短路径。

一种城市路网的负载平衡方法\n技术领域\n[0001] 本发明涉及一种城市路网的负载平衡方法。\n背景技术\n[0002] 随着城市化建设进程的逐步现代化，城市交通的日益拥挤为城市建设与生活带来诸多问题，特别是近年来个人汽车消费的提升，而土地资源的稀缺，造成高密集居住环境与高流量交通供求之间的矛盾，导致交通的拥堵问题已经是严重阻碍城市进一步发展的一个重要因素。在交通路网中，寻找车辆的最优路径是出行导航的基本功能。最优路径一般是距离最短的路径或者是时间最短的路径。但是，在路网中上从不同的路口出发的车辆如果都选择这种最优路径，很有可能造成交通的拥堵。\n[0003] 在交通路网中，只是简单的计算的最优的一条路径常常导致路网上的负载不平衡，一些道路拥挤，一些道路空闲，造成城市交通的拥堵。在车流辆较少的情况下，简单计算最优的一条路径这种方法有很好的效果，但是这种方法没有考虑到当前路网上的车流量，所以不能有效的利用路网资源，影响城市交通路网的整体性能。\n发明内容\n[0004] 本发明的目的在于克服现有技术的不足，提供一种城市路网的负载平衡方法，通过对车流进行分流，达到更有效地利用城市路网资源的效果，保证在交通不拥堵的情况下，提高了路网的吞吐量，进而提高城市交通路网的整体性能。\n[0005] 本发明的目的是通过以下技术方案来实现的：一种城市路网的负载平衡方法，它包括以下步骤：\n[0006] S1.统计给定车流中所有车辆的出发地和目的地信息，将给定车流中具有相同出发地和目的地的所有车辆定义为一条分支车流，计算该条分支车流从出发地到目的地的最短路径；\n[0007] S2.利用该最短路径构成第一网络拓扑，根据该第一网络拓扑计算现有第二网络拓扑的各链路的权重W，根据各链路的权重W重新计算步骤S1中所述的该条分支车流的最短路径；\n[0008] S3.重复步骤S1～S2，为给定车流中的所有车辆计算最短路径。\n[0009] 所述的步骤S1包括以下子步骤：\n[0010] S11.将出发地定义为源节点s，目的地定义为宿节点t；找出给定车流中的一条分支车流中源节点s的所有出度边上的邻接节点；\n[0011] S12.根据现有网络拓扑中链路的可通行交通量C设置各链路的权重W，各链路的权重W为该链路可通行交通量C的反比；\n[0012] S13.根据步骤S12得到的链路的权重计算源节点s的所有出度边上的邻接节点到宿节点t的最短路径。\n[0013] 所述的步骤S2包括以下子步骤：\n[0014] S21.根据步骤S1计算出来的最短路径构造第一网络拓扑；\n[0015] S22.找出该第一网络拓扑中的所有链路中的最小的可通行交通量C；\n[0016] S23.将步骤S22中得到的最小的可通行交通量C与步骤S1中所述的该条分支车流的车流量进行比较：\n[0017] 若该最小的可通行交通量C小于该条车流的车流量，则根据该最小的可通行交通量对该条分支车流中的部分车辆进行线路规划标记，并为这部分车辆计算最短路径；\n[0018] 若该最小的可通行交通量大于该条分支车流的车流量，则对该条分支车流中的所有车辆进行线路规划标记，并为该条分支车流中的所有车辆计算最短路径；\n[0019] S24.更新第一网络拓扑上的所有链路的可通行交通量C；\n[0020] S25.计算步骤S23中计算出来的最短路径上的所有链路的权重W；\n[0021] S26.判断步骤S1中所述的该条分支车流中的所有车辆是否都进行了线路规划标记，若该条分支车流中的所有车辆都进行了线路规划标记，则跳转步骤S3，否则跳转步骤S22。\n[0022] 步骤S25中所述的链路W的权重的通过以下公式计算得出：\n[0023] W(e)＝W′(e)(1+Q(e)/V(e))\n[0024] 式中：W(e)-链路e修改后的权重，W′(e)-链路e的当前权重，Q(e)-链路e当前的交通量，V(e)-链路e的实际通行能力。\n[0025] 所述的最短路径为时间最短路径或距离最短路径。\n[0026] 本发明的有益效果是：本发明所提出的方法中为某个车流选择路径时，不止计算了一条路径，计算了多条最短路径，在多条最短路径构成的网络拓扑下，通过改变链路的权重为给定车流的各个车辆重新计算一条最优路径，这样可以通过分流达到更有效地利用城市路网的资源，保证在交通不拥堵的情况下，提高了路网的吞吐量，进而提高城市交通路网的整体性能。\n附图说明\n[0027] 图1为本发明城市路网的负载平衡方法的流程图。\n具体实施方式\n[0028] 下面结合附图进一步详细描述本发明的技术方案，但本发明的保护范围不局限于以下所述。\n[0029] 如图1所示，一种城市路网的负载平衡方法，它包括以下步骤：\n[0030] S1.统计给定车流中所有车辆的出发地和目的地信息，将给定车流中具有相同出发地和目的地的所有车辆定义为一条分支车流，计算该条分支车流从出发地到目的地的最短路径；\n[0031] S2.利用该最短路径构成第一网络拓扑，根据该第一网络拓扑计算现有第二网络拓扑的各链路的权重W，根据各链路的权重W重新计算步骤S1中所述的该条分支车流的最短路径；\n[0032] S3.重复步骤S1～S2，为给定车流中的所有车辆计算最短路径。\n[0033] 所述的步骤S1包括以下子步骤：\n[0034] S11.将出发地定义为源节点s，目的地定义为宿节点t；找出给定车流中的一条分支车流中源节点s的所有出度边上的邻接节点；\n[0035] S12.根据现有网络拓扑中链路的可通行交通量C设置各链路的权重W，各链路的权重W为该链路可通行交通量C的反比；\n[0036] S13.根据步骤S12得到的链路的权重计算源节点s的所有出度边上的邻接节点到宿节点t的最短路径。\n[0037] 所述的步骤S2包括以下子步骤：\n[0038] S21.根据步骤S1计算出来的最短路径构造第一网络拓扑；\n[0039] S22.找出该第一网络拓扑中的所有链路中的最小的可通行交通量C；\n[0040] S23.将步骤S22中得到的最小的可通行交通量C与步骤S1中所述的该条分支车流的车流量进行比较：\n[0041] 若该最小的可通行交通量C小于该条车流的车流量，则根据该最小的可通行交通量对该条分支车流中的部分车辆进行线路规划标记，并为这部分车辆计算最短路径；\n[0042] 若该最小的可通行交通量大于该条分支车流的车流量，则对该条分支车流中的所有车辆进行线路规划标记，并为该条分支车流中的所有车辆计算最短路径；\n[0043] S24.更新第一网络拓扑上的所有链路的可通行交通量C；\n[0044] S25.计算步骤S23中计算出来的最短路径上的所有链路的权重W；\n[0045] S26.判断步骤S1中所述的该条分支车流中的所有车辆是否都进行了线路规划标记，若该条分支车流中的所有车辆都进行了线路规划标记，则跳转步骤S3，否则跳转步骤S22。\n[0046] 步骤S25中所述的链路W的权重的通过以下公式计算得出：\n[0047] W(e)＝W′(e)(1+Q(e)/V(e))\n[0048] 式中：W(e)-链路e修改后的权重，W′(e)-链路e的当前权重，Q(e)-链路e当前的交通量，V(e)-链路e的实际通行能力。链路e表示所有链路中第e条链路。\n[0049] 所述的最短路径可以是时间最短路径，也可以是距离最短路径。\n[0050] 由交通流理论可知，当某一路段的当前交通量Q逐渐增大，达到Q/V＝1时，路段上的车辆将开始产生拥挤。其中，Q为路段当前交通量(辆/h)，V为路段实际通行能力(辆/h)。\n为了减缓交通拥挤，需要保证在Q/V不能超过1的情况下，尽可能的通行更多的车流量，即需要进行城市路网负载平衡。\n[0051] 以G(N，E，W，C)表示图，其中N表示节点集合，E表示链路集合，W表示链路的权重，C表示链路的可用容量，在城市路网中，N相当于路口，E相当于路段，W相当于路段的长度，C相当于路段的可通行交通量，即C＝V-Q。N中的一个子集M＝{(s,t,d)}为给定的车流的出发地和目的地，表示在路网上的车辆可能的不同的出发地到达不同的目的地。其中s为源节点，即出发地，t为宿节点，即目的地，d为出发地到目的地的车流量。