运输基础/路径选择/解答

问题

问题

假设从起点“o”到终点“r”的流量为六（6）个单位。在时间函数中，每条路径ab上的流量用Qab表示。应用沃德罗普网络均衡原理（用户在所有使用路径上使出行时间相等）。

A. 网络A中，每条链路的流量和出行时间是多少？（完成下表）

链路属性

链路	链路性能函数	流量	时间
o-p	$C_{op}=5*Q_{op}$
p-r	$C_{pr}=25+Q_{pr}$
o-q	$C_{oq}=20+2*Q_{oq}$
q-r	$C_{qr}=5*Q_{qr}$

B. 系统最优分配是什么？

C. 无政府状态的价格是多少？

示例

解答

部分A

每条链路的流量和出行时间是多少？完成网络A的下表。

链路属性

链路	链路性能函数	流量	时间
o-p	$C_{op}=5*Q_{op}$
p-r	$C_{pr}=25+Q_{pr}$
o-q	$C_{oq}=20+2*Q_{oq}$
q-r	$C_{qr}=5*Q_{qr}$

这四条链路实际上是两条链路O-P-R和O-Q-R，因为根据流量守恒定律，Qop = Qpr和Qoq = Qqr。

链路属性

链路	链路性能函数	流量	时间
o-p-r	$C_{opr}=25+6*Q_{opr}$
o-q-r	$C_{oqr}=20+7*Q_{oqr}$

根据沃德罗普均衡原理，每条使用路径上的出行时间（成本）必须相等。因此$C_{opr}=C_{oqr}$.

或

$25+6*Q_{opr}=20+7*Q_{oqr}$

$5+6*Q_{opr}=7*Q_{oqr}$

$Q_{oqr}=5/7+6*Q_{opr}/7$

根据流量守恒原理

$Q_{oqr}+Q_{opr}=6$

$Q_{opr}=6-Q_{oqr}$

通过代入

$Q_{oqr}=5/7+6/7(6-Q_{oqr})=41/7-6*Q_{oqr}/7$

$13*Qoqr=41$

$Q_{oqr}=41/13=3.15$

$Q_{opr}=2.84$

检验

$42.01=25+6(2.84)$

$42.05=20+7(3.15)$

检验（在舍入误差范围内）

链路属性

链路	链路性能函数	流量	时间
o-p-r	$C_{opr}=25+6*Q_{opr}$	2.84	42.01
o-q-r	$C_{oqr}=20+7*Q_{oq}$	3.15	42.01

或者扩展回原始表格

链路属性

链路	链路性能函数	流量	时间
o-p	$C_{op}=5*Q_{op}$	2.84	14.2
p-r	$C_{pr}=25+Q_{pr}$	2.84	27.84
o-q	$C_{oq}=20+2*Q_{oq}$	3.15	26.3
q-r	$C_{qr}=5*Q_{qr}$	3.15	15.75

用户均衡：总延误 = 42.01 * 6 = 252.06

B部分

什么是系统最优分配？

流量守恒

$Q_{opr}+Q_{oqr}=6\,\!$

$TotalDelay=Q_{opr}(25+6*Q_{opr})+Q_{oqr}(20+7*Q_{oqr})\,\!$

$25Q_{opr}+6Q_{opr}^{2}+(6-Q_{opr})(20+7(6-Q_{opr}))\,\!$

$25Q_{opr}+6Q_{opr}^{2}+(6-Q_{opr})(62-7Q_{opr}))\,\!$

$25Q_{opr}+6Q_{opr}^{2}+372-62Q_{opr}-42Q_{opr}+7Q_{opr}^{2}\,\!$

$13Q_{opr}^{2}-79Q_{opr}+372\,\!$

解析解需要最小化总延误

$\delta C/\delta Q=26Q_{opr}-79=0\,\!$

$Q_{opr}=79/26=3.04\,\!$

$Q_{oqr}=6-Q_{opr}=2.96\,\!$

我们可以计算每条路径上的SO行程时间

$C_{opr,SO}=25+6*3.04=43.24\,\!$

$C_{oqr,SO}=20+7*2.96=40.72\,\!$

注意，与用户均衡解不同，$C_{opr,SO}>C_{oqr,SO}\,\!$

总延误 = 3.04(25+ 6*3.04) + 2.96(20+7*2.96) = 131.45+120.53= 251.98

注意：也可以使用诸如“求解器”算法之类的软件来找到此解决方案。

C部分

无政府状态价格是多少？

用户均衡：总延误 = 252.06 系统最优：总延误 = 251.98

无政府状态价格 = 252.06/251.98 = 1.0003 < 4/3