一种低复杂度的网络平均路径优化方法

摘要

一种低复杂度的网络平均路径优化方法，提出了一种新颖的优化网络平均路径长度的快速方法，该方法提出了一种用于评估添加某一连边对于网络平均路径长度带来的降低的指标Ζ_ij，并使用该指标进行网络的逐一添边优化网络平均路径长度。对于网络的某一节点对，Ζ_ij=Ω_ijΞ_ijΨ_ij，其中Ω_ij是添加连边前后连接节点对ij的路径长度的比值，Ξ_ij是添加连边前后连接节点对ij的路径长度的差值，Ψ_ij是同时经过节点对ij的交通流需求。方法在每次添加连边时，首先计算网络中所有节点对的Ζ_ij指标值，然后从中找出指标值最大的节点对添加连边。逐一添加连边的网络优化最终在达到终止条件，例如添加新连边长度超过某一设定值时结束。

主权项

一种低复杂度的网络平均路径优化方法，其特征在于：通过使用新定义的一种关于添加某一连边对网络平均路径长度的降低的估计指标Ζ_ij来进行网络逐一添加连边降低网络平均路径长度，方法的具体步骤如下：步骤一：计算网络中所有节点对间的路径长度，并据此计算所有节点对的Ζ_ij指标；关于添加某一连边对网络平均路径长度的降低的估计指标Ζ_ij＝Ω_ijΞ_ijΨ_ij，上述公式包含三个子项：1)Ω_ij＝l_ij/l_ij'是添加连边ij前后连接节点对ij的路径长度的比值，其中l_ij、l_ij'分别是添加连边ij前后连接节点对ij的路径长度；l_ij可以使用$l_{ij}={\Sigma }_{m\in {\mathrm{PATH}}_{ij}}len\left(m\right)p_{ij}\left(m\right)$进行数学表示，其中PATH_ij是代表连接节点对ij的常用路径集合，len(m)代表路径m的长度，p_ij(m)代表从节点i出发到达节点j的交通流需求中使用路径m的比例；其中总是成立；2)Ξ_ij＝l_ij‑l_ij'是添加连边ij前后连接节点对ij的路径长度的差值，其中l_ij、l_ij'分别是添加连边ij前后连接节点对ij的路径长度；由于添加一条长度为w_ij的连边时，如果w_ij≥l_ij，那么这一新连边不会对网络中的路径产生影响，所以实际添边时，总有l_ij'＝w_ij<l_ij；据此总有：Ω_ij≥1且Ξ_ij≥0；3)是同时经过节点i和j的交通流需求；其中D_od是网络中从节点o出发到达节点d的出行需求分布概率，可通过实际交通流统计得到；PATH_od是代表连接节点对od的常用路径集合；σ_ij(m)是一个变量，当路径m同时经过节点i和j时为1，否则为0；p_od(m)代表从节点o出发到达节点d的交通流需求中使用路径m的比例；如果对Ψ_ij进行归一化处理，使得∑_odD_od＝1，那么最终网络的平均路径长度L即可表示为L＝∑_odl_odD_od，l_od为节点o到节点d之间的路径长度；步骤二：从所有节点对中找出Ζ_ij指标最大的节点对，给该节点对添加一条新连边；步骤三：判断是否到达预设终止条件，未到达，跳转到步骤一；否则，方法结束。