路由對(duì)策的算法研究.pdf

1、將交通網(wǎng)絡(luò)在圖論中進(jìn)行抽象，同時(shí)又根據(jù)圖論中最大流、最短路、最小費(fèi)用流等的性質(zhì)，對(duì)局中人在網(wǎng)絡(luò)中選擇自己路由的策略作了進(jìn)一步的研究，具體分為以下幾部分:
　　第一部分從網(wǎng)絡(luò)流模型出發(fā)，研究網(wǎng)絡(luò)中的最優(yōu)流以及納什均衡流，并給出了它們的有效算法。在限定容量的網(wǎng)絡(luò)中，通過(guò)引入邊-路徑模型得出了最大流，并得出網(wǎng)路最大流量唯一但最大流量的分流并不唯一的結(jié)論。根據(jù)網(wǎng)絡(luò)的最大流的模型可以判定所給出的網(wǎng)絡(luò)流是否為可行流。在給出網(wǎng)絡(luò)流為可行流時(shí)，得

2、到了網(wǎng)絡(luò)的最優(yōu)流及納什均衡流的有效算法，并證明了一般網(wǎng)絡(luò)的納什均衡流問(wèn)題為NP-完全問(wèn)題。
　　第二部分在信息對(duì)稱(chēng)且路由環(huán)境為自私的情況下，研究無(wú)政府代價(jià)的大小。當(dāng)網(wǎng)絡(luò)中各邊的成本為線性函數(shù)時(shí)，若網(wǎng)絡(luò)流為可分流時(shí)得出網(wǎng)絡(luò)的無(wú)政府代價(jià)不超過(guò)4/3的結(jié)論;若網(wǎng)絡(luò)流為不可分流時(shí)，得出網(wǎng)絡(luò)的無(wú)政府代價(jià)至多為(√5+1)/2。無(wú)政府代價(jià)對(duì)網(wǎng)絡(luò)路由的影響非常大，它在一定程度上反應(yīng)了局中人由于自己的利益而導(dǎo)致網(wǎng)絡(luò)社會(huì)成本的增加，同時(shí)也說(shuō)明了納什

3、均衡流時(shí)局中人的選擇并不一定是網(wǎng)絡(luò)的最優(yōu)路由選擇。
　　第三部分由于最優(yōu)流為網(wǎng)絡(luò)的最優(yōu)選擇，但是，它卻在一定程度上損害了部分局中人的利益。該部分研究了頂點(diǎn)對(duì)間和每個(gè)頂點(diǎn)對(duì)的最優(yōu)流的不公平性，并得出在路由成本為線性函數(shù)時(shí)至多為1的結(jié)論。
　　第四部分通過(guò)引入某個(gè)城市中定點(diǎn)對(duì)的路由選擇和多個(gè)城市間的路由選擇研究網(wǎng)絡(luò)路由對(duì)策在實(shí)際中的應(yīng)用。針對(duì)不同的路由選擇，局中人在掌握交通狀況的條件下根據(jù)自身的路由選擇模型選擇最佳路由。在不考慮