【正文】 hL??，??? rs由第一式得，0?rskh時(shí)，0),(**???rskhhL ?，????? rsKkrs,0?rskh時(shí)，0),(**???rskhhL ?，????? rsKkrs,這里，rskrs KkrsrskrsrskAaxarskhthhdwwchLrsa???????????????????????????? ?? ??? ??//)(0?rsrskaaAaxahxdxdwwcda????????????? ??/)(0 ，????? rsKkrs,AaKkrshhhxrsrskarskKkrskrskarsrskars?????????????????????????,//,??所以，????????????AarsrsrskaaarskrsKkxchL ,)(/,??又因?yàn)椋????Aarsrskaaacxc,)( ?所以有，0?rskh時(shí)，??????? rsKkcrsrsrsk,0?0?rskh時(shí)，??????? rsKkcrsrsrsk,0?b ）解的唯一性證明條件：式 （ 2 ） 式 （ 4 ）形成凸領(lǐng)域，并且式 （ 1 ）為狹義凸函數(shù)。由式 （ 2 ） 式 （ 4 ）知都為線性函數(shù)，所以形成的領(lǐng)域?yàn)橥诡I(lǐng)域。Z函數(shù)為凸函數(shù)的條件為：0/22???axZ由式 （ 1 ）知，AaxcxZaaa????? ),(/badxxdcaaa?? (,0/)(時(shí)）????baxxZ20 ，ba ?(時(shí)），Aba ?? ,所以，海賽矩陣為：????????????nnnaaadxxdcdxxdcdxxdcZ/)(0/)(0/)(1112??????因?yàn)?，一般情況下，路阻函數(shù)為單增函數(shù)，所以，Aadxxdcaaa??? ,0/)(所以，有唯一解。第 4 節(jié) 用戶均衡問題的解法1 ． D ij ks tra 法 （記號確定法）該方法是從離起點(diǎn)最近的點(diǎn)開始，逐漸向全方位枚舉出最短徑路的方法。【 記號 】K : 最短徑路和最小費(fèi)用已經(jīng)確定的節(jié)點(diǎn)集合。?K：最短徑路尚未確定的局部最小費(fèi)用節(jié)點(diǎn)集合。mF：最短徑路的途徑節(jié)點(diǎn)集合。jc：以 o 為起點(diǎn)的最小費(fèi)用。【計(jì)算步驟】Ste p 1 設(shè)所有節(jié)點(diǎn)? ?j的局部最小費(fèi)用為??jc或?yàn)樽銐虼蟮闹?，并設(shè)??? KjFj,0。設(shè) o 為起點(diǎn)，對節(jié)點(diǎn) o 有ojco?? ,0，將節(jié)點(diǎn) o 移到集合 K 。Ste p 2 檢查以節(jié)點(diǎn)i為起點(diǎn)的所有路段的終點(diǎn)? ?m，若滿足 mimdcc ??，則令iFdccmmim??? ,。St ep 3 對最小費(fèi)用尚未確定 的節(jié)點(diǎn)集合?K 中的所有節(jié)點(diǎn)，按下式計(jì)算局部最小費(fèi)用的最小值 jc。?????????Kppccppj:),(m i n。將節(jié)點(diǎn)j移到集合K。St ep 4 如果??pc以外的節(jié)點(diǎn)是否全部被移到集合 K中，則結(jié)束計(jì)算。反之，令ji ?，返回 St ep 2 。【最短徑路的枚舉】 利用 jF枚舉出任意節(jié)點(diǎn)j到起點(diǎn) o 的最短徑路：)()()()( ?????????bghjFfFgFhFj ??起點(diǎn) o【例題】用 Dijkstra 法計(jì)算下圖從點(diǎn) 1 到其它節(jié)點(diǎn)的最短經(jīng)路 。1 5 6 4 7 2 3 2 2 2 1 1 1 1 3 3 4 4 6 8 9 節(jié)點(diǎn)及節(jié)點(diǎn)號碼 路段及路段費(fèi)用 解：將計(jì)算過程列于下圖和 表，可以看出，到第７步 為止，全部節(jié)點(diǎn)都被移到集合 K 中，結(jié)束計(jì)算。例如，從節(jié)點(diǎn)１到節(jié)點(diǎn)６的最短徑路為： 1)(4)(7)(6 476 ?????? FFF1 5 6 4 7 2 3 2 2 2 1 1 1 1 3 3 4 4 6 8 9 表　　 Di jk st ra 法的計(jì)算過程和結(jié)果路段 各節(jié)點(diǎn)的mc 局部最小徑路mF 最小費(fèi)用節(jié)點(diǎn)計(jì)算順序始點(diǎn)終點(diǎn) 節(jié)點(diǎn)號碼 節(jié)點(diǎn)號碼 }{m i nppc1 2 3 4 5 6 7 1 2 3 4 5 6 71 0 ∞ ∞ ∞ ∞ ∞ ∞ 0 0 0 0 0 0 0 12 1 2 ， 4 ， 5 0 2 ∞ 4 9 ∞ ∞ 0 1 0 1 1 0 0 23 2 3 ， 4 0 2 10 4 9 ∞ ∞ 0 1 2 1 1 0 0 44 4 5 ， 7 0 2 10 4 8 ∞ 6 0 1 2 1 4 0 4 75 7 3 ， 6 0 2 9 4 8 7 6 0 1 7 1 4 7 4 66 6 5 ， 7 0 2 9 4 8 7 6 0 1 7 1 4 7 4 57 5 4 ， 6 0 2 9 4 8 7 6 0 1 7 1 4 7 4 32. 全有全無法 （ al l o r no thin g m et ho d ）全有全無分配法是將 OD 交通需求沿最短經(jīng)路一次分配到路網(wǎng)上去的方法，也被稱為交通需求分配。顧名思義，全有 （ al l ）指將 OD 交通需求一次性地全部分配到最短徑路上。全無 （ no th in g ）指對最短徑路以外的徑路不分配交通需求量。全有全無分配法應(yīng)用于沒有通行能力限制的網(wǎng)絡(luò)交通交通量分配等場合。在美國芝加哥城交通解析中，首次獲得應(yīng)用。另外，后述增量分配法和均衡分配法中頻繁使用?！痉峙溆?jì)算步驟】Ste p 1 令0,0 ??ijxn（始點(diǎn) i ，終點(diǎn) j 的路段交通量）。Ste p 2 搜索第 n 個(gè)起點(diǎn)到其余各點(diǎn)的最短徑路，求出最短徑路費(fèi)用? ?ioc ?m i n 和 iF。Ste p 3 按? ?ioc ?m i n 的相反順序，用下式求出流入節(jié)點(diǎn)j并處于最短徑路上的路段)(iFi→j間的交通量 ijx。nsijnsnijnijtxx ????? 11?nijx：分配到第1?n個(gè)交通量發(fā)生點(diǎn)時(shí)，路段ij的交通量。1: 交通量發(fā)生點(diǎn) n 的 OD 對 ns 的最短徑路經(jīng)過路段ij時(shí)。nrsij,?=0: 交通量發(fā)生點(diǎn) n 的 OD 對ns的最短徑路不經(jīng)過路段ij時(shí)。St ep 4 如果 n= N ，則結(jié)束計(jì)算。反之，令 n= n+ 1 返回 St ep2 。 N 為網(wǎng)絡(luò)中交通量發(fā)生點(diǎn)的集合。3. 增量分配法 （ I nc r ement al as sign m en t m et ho d ）增量分配法時(shí)將 OD 交通需求量進(jìn)行適當(dāng)形式的分割（分割數(shù) 、 等分或不等分），然后用全有全無分配法，將分割后的 OD 交通需求量逐漸分配到網(wǎng)絡(luò)上去。實(shí)際工作中，如何分割 OD 交通需求量是很重要的，一般多用 5 ― 10 分割，并且采用不等分?！痉峙溆?jì)算步驟】Ste p 1 根據(jù)需要，以適當(dāng)?shù)男问椒指?OD 交通需求量，即rsnr s ntt ??。令 n=1 ， 0?nijx 。 Ste p 2 更新路段費(fèi)用)(1??nijijnijxcc。Ste p 3 用全有全無分配法將第 n 次分割 OD 交通需求量rsnt分配到最短經(jīng)路上。Ste p 4 如果 n=N ，則結(jié)束計(jì)算。反之，令 n=n+ 1 返回 Ste p2 。 N 為分割次數(shù)。4. 均衡分配 （ Fr an k W ol fe ）法St ep 1 給出初始可能解? ?kax，令 0?k 。一般用前述全有全無分配法求解初始可能解。St ep 2 更新路段費(fèi)用函數(shù))(kakaxc。St ep 3 搜索目標(biāo)函數(shù)的下降方向。用最短徑路搜索法求出各 OD 間的最短徑路，在用全有全無分配法求出探索方向? ?kay。Ste p 4 一維搜索。將下式代入到目標(biāo)函數(shù)中，求出最佳探索步長*? 。)(1 kakakakaxyxx ?????Ste p 5 收斂判定。設(shè) 1?和 2?為任意小數(shù)，若滿足下式，則結(jié)束計(jì)算。反之，返回 Ste p 2 。11)()( ?????? kakaAakakaccxx21/)(m a x ???? kakakaxxx【例題】設(shè)圖示交通網(wǎng)絡(luò)的 OD 交通需求量為 200?t 輛，各徑路的交通費(fèi)用函數(shù)分別為：11 hc ?? ，220 2 hc ?? ，33 hc ??試用全有全無分配法 、 增量分配法和均衡分配法求出分配結(jié)果，并進(jìn)行比較。徑路 3 徑路 1 D 徑路 2 解：1 ． 全有全無分配法 由路段費(fèi)用函數(shù)可知，在路段交通量為零時(shí)，徑路 1最短。利用該方法的以下結(jié)果：15,10,0,200321321????????? ccchhh因?yàn)椋?5,132?? ccc，所以，沒有得到均衡解。目標(biāo)函數(shù)：3 00 00 12 12 233222211??????? hhhhhhZ２． 增量分配法采用 2 等分。（ 1 ） 第 1 次分配全有全無分配法相同，徑路 1 最短。15,10,151 0 ,0,1 0 0321321????????? ccchhh（２）第 2 次分配　最短徑路變?yōu)閺铰?2,0,100,10021321??????????? cchhh，153?c這時(shí)，結(jié)果接近于均衡解。目標(biāo)函數(shù)為：1 2 51 0 0 05 0 05 0 00 1 2 1 2 233222211?????????? hhhhhhZ21 25?３． 均衡分配法【 模型 】m i n 2332222110 1 2 1 2 hhhhhhZ ??????.. ts ???31200kkh)3,2,1(,0 ?? khk（ 1 ） 用全有全無分配法求解初始可能解30 00,15,10,2520 ,0,20 0321030201?????????? Zccchhh。（ 2 ） 求最佳搜索方向繼續(xù)用全有全無分配法求解，得：0,200,0030201??? yyy（４）一維搜索 , 求最佳搜索步長*? 和交通量修正令6 ??)0200(,)2022(0211???????? hh,013?h15,321????????? ccc22200 1 2 2 30 1 2 2 ????????????Z 1 0 2 3 ?????（５） 收斂判定設(shè) 1?= 2?=0 .01 。11)()( ?????? kakaAakakaccxx21/)(ma x ???? kakakaxxx顯然，收斂條件得不到滿足。返回 （ 2 ）繼續(xù)修正計(jì)算 。這時(shí)的最短徑路為徑路 1 。所以，繼續(xù)用全有全無分配法求解，得：0,0,200131211??? yyy)(,)(2221???????? hh023?h222 ????????????Z ?????求最佳探索步長*? 的方法：將)(1 kakakakaxyxx ?????代入目標(biāo)函數(shù)中，得m i n10 ?? ?　? ????Aaxyxakakakadwwc)(0)(?