第三屆數(shù)學(xué)建模論文Braess悖論

1、第三屆“ScienceWord杯”數(shù)學(xué)中國(guó)數(shù)學(xué)建模網(wǎng)絡(luò)挑戰(zhàn)賽承 諾 書(shū)我們仔細(xì)閱讀了第三屆“ScienceWord杯”數(shù)學(xué)中國(guó)數(shù)學(xué)建模網(wǎng)絡(luò)挑戰(zhàn)賽的競(jìng)賽規(guī)則。我們完全明白，在競(jìng)賽開(kāi)始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問(wèn)題。我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的, 如果引用別人的成果或其他公開(kāi)的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競(jìng)賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有違反競(jìng)賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們?cè)试S數(shù)學(xué)中國(guó)網(wǎng)站()公布論文，

2、以供網(wǎng)友之間學(xué)習(xí)交流，數(shù)學(xué)中國(guó)網(wǎng)站以非商業(yè)目的的論文交流不需要提前取得我們的同意。我們的參賽報(bào)名號(hào)為：參賽隊(duì)員 (簽名) ：隊(duì)員1： 隊(duì)員2：隊(duì)員3： 參賽隊(duì)教練員 (簽名)： 參賽隊(duì)伍組別：2010年第三屆“ScienceWord杯”數(shù)學(xué)中國(guó)數(shù)學(xué)建模網(wǎng)絡(luò)挑戰(zhàn)賽交通網(wǎng)絡(luò)中的Braess悖論及其博弈論分析摘要隨著經(jīng)濟(jì)的發(fā)展和汽車保有量的增加，各大中城市交通擁堵日趨嚴(yán)重，而在平衡交通網(wǎng)絡(luò)中擴(kuò)建道路，有時(shí)候卻出現(xiàn)了Braess悖論現(xiàn)象，即在交通網(wǎng)絡(luò)中增加一條通路反而會(huì)降低網(wǎng)絡(luò)性能。本文在分析悖論產(chǎn)生機(jī)理的基礎(chǔ)上，指出Braess悖論的出現(xiàn)是由于非合作網(wǎng)絡(luò)中Nash平衡點(diǎn)不在Pareto邊界上。以北京

3、市二環(huán)路以內(nèi)的路網(wǎng)中（包括二環(huán)路）出現(xiàn)的交通擁堵為例判斷是否為Braess悖論現(xiàn)象，通過(guò)建立通行時(shí)間與車流量的關(guān)系，并以北京道路中最常見(jiàn)的“日“字型道路作為切入點(diǎn)，來(lái)求解是否存在Breass悖論現(xiàn)象。我們選取了北京二環(huán)以內(nèi)路網(wǎng)中很典型的“日”字結(jié)構(gòu)，通過(guò)谷歌地圖顯示的路況估算出每條路流量和自由通行時(shí)間，得到了延遲參數(shù)，并根據(jù)延遲參數(shù)間的關(guān)系判斷出了是否存在Breass悖論。另一方面從每個(gè)出行者出發(fā)，建立動(dòng)態(tài)博弈模型，說(shuō)明廣泛使用GPS對(duì)于緩解交通壓力的意義。關(guān)鍵詞 Braess悖論 Pareto最優(yōu) 博弈論 交通分配With the development of economy and inc

4、reasing number of cars retained, traffic in large cities become worse and worse. However, sometimes extending roads to traffic network induces the phenomenon of Braess's Paradox in which adding a new link to traffic network results in increased equilibrium travel cost for all travelers. On the b

5、asis of analyzing cause of Braess's Paradox, we state that it occurs when the Nash equilibrium is not Pareto optimal. And we take the Second Ring Road in Beijng for example to determine whether the traffic jams in it was caused by Braess's Paradox. We prove whether Braess's Paradox exist

6、s by establishing the relationship between passing time and traffic flow. We get the traffic flow and free passing time of every road by Google Map, thus obtaining the delay parameter. Then determine whether Braess's Paradox exists by the relationship of different delay parameters. On the other

7、hand, we take everyone into consideration to state the significance to relieve traffic jams of using the GPS guided system. Key Words: Braess's Paradox; Pareto optimal; Game theory; Traffic assignment一、問(wèn)題重述1背景：近年來(lái)，日益嚴(yán)重的堵車問(wèn)題已成了北京交通的難題。造成交通擁堵的直觀原因是城市道路建設(shè)速度趕不上機(jī)動(dòng)車增長(zhǎng)的速度。如果車量不變，單靠擴(kuò)充交通網(wǎng)絡(luò)中道路的通行能力，卻不一定能緩

8、解交通的擁擠堵塞。1968 年Dietrich Braess 在他的一篇論文中提出在平衡交通流網(wǎng)絡(luò)中存在一種看似矛盾的Braess 悖論現(xiàn)象。它的含義是：有時(shí)在一個(gè)交通網(wǎng)絡(luò)上增加一條路段，或者提高某個(gè)路段的局部通行能力，反而使所有出行者的出行時(shí)間都增加了，這種為了改善通行能力的投入不但沒(méi)有減少交通延誤，反而降低了整個(gè)交通網(wǎng)絡(luò)的服務(wù)水平。人們對(duì)這個(gè)問(wèn)題做過(guò)許多研究，在城市建設(shè)當(dāng)中也盡量避免這種現(xiàn)象的發(fā)生。但在復(fù)雜的城市道路當(dāng)中，Braess 悖論仍然不時(shí)出現(xiàn)，造成實(shí)際交通效率的顯著下降。本文分析了悖論產(chǎn)生的機(jī)理,指出Braess 悖論的出現(xiàn)本質(zhì)上是由于非合作網(wǎng)絡(luò)中的Nash平衡點(diǎn)不在Pareto

9、邊界上,這種情況下,存在一種非平衡的流量分布使網(wǎng)絡(luò)相對(duì)平衡流量分布時(shí)，某些用戶的出行時(shí)間縮短, 同時(shí)其他用戶的出行時(shí)間也不會(huì)增加。我們通過(guò)實(shí)例分析說(shuō)明交通規(guī)劃時(shí)應(yīng)該盡量避免設(shè)計(jì)出可能導(dǎo)致Braess悖論發(fā)生的路網(wǎng)結(jié)構(gòu),而對(duì)于現(xiàn)有交通網(wǎng)絡(luò)中存在的Braess悖論現(xiàn)象,可以通過(guò)控制和誘導(dǎo)等策略使交通流的分配達(dá)到Pareto 最優(yōu),從而避免悖論發(fā)生。2問(wèn)題：(1)通過(guò)分析實(shí)際城市的道路交通情況（自行查詢的數(shù)據(jù)需給出引用來(lái)源），建立合理的模型，判斷在北京市二環(huán)路以內(nèi)的路網(wǎng)中（包括二環(huán)路）出現(xiàn)的交通擁堵，是否來(lái)源于Braess 悖論所描述的情況。(2)建立模型以分析：如果司機(jī)廣泛使用可以反映當(dāng)前交通擁堵

10、情況的GPS 導(dǎo)航系統(tǒng)，是否會(huì)緩解交通堵塞，并估計(jì)其效果。（1）一 問(wèn)題假設(shè)1、假設(shè)在后面所分成的兩組司機(jī)中他們只選擇時(shí)間最短的方針。并且兩組是同時(shí)進(jìn)行的；2、再行對(duì)應(yīng)的路上，在說(shuō)明時(shí)滿足用戶均衡原則，相對(duì)于流量等因素。以及滿足一定的對(duì)稱性。3、在一定的時(shí)間內(nèi)整個(gè)路網(wǎng)和局部道路網(wǎng)絡(luò)內(nèi)車流量不發(fā)生顯著變化，即可認(rèn)為不發(fā)生改變。4、天氣道路質(zhì)量、擁擠程度和綜合路阻等這些可測(cè)因素都在后面的延時(shí)參數(shù)中體現(xiàn)。不再考慮這樣的問(wèn)題；5、司機(jī)對(duì)道路是熟悉的，不存在迷路繞遠(yuǎn)問(wèn)題，并且能自行選擇最短路徑。6、谷歌地圖中的路況四種顏色反應(yīng)為道路上的車距，并認(rèn)為車距平均分布，不考慮道路的車道數(shù)量。車長(zhǎng)假設(shè)為5米，不考

11、慮公交車與小轎車的不同，認(rèn)為所有車都是5米。7、道路的自由通行時(shí)間認(rèn)為汽車達(dá)到法律規(guī)定的本路段最大限速值。二、模型分析與建立交通網(wǎng)絡(luò)中各路段的容量直接影響到交通流在網(wǎng)絡(luò)上的分布格局。而B(niǎo)raess 悖論是由于司機(jī)從個(gè)人利益出發(fā),選擇出行成本最小的路徑,致使系統(tǒng)達(dá)到均衡狀態(tài)時(shí)的總出行成本增加。1952 年Wardrop 通過(guò)對(duì)交通現(xiàn)象的分析提出了關(guān)于交通網(wǎng)絡(luò)流量分布的用戶均衡原理5：在所有實(shí)際使用的路徑上,出行成本相等,且小于任何未使用路徑上的出行成本。所有合作博弈的解都具有這樣的性質(zhì):在均衡點(diǎn)處，任何用戶收益的增加都必將導(dǎo)致其他用戶收益的降低,網(wǎng)絡(luò)所能調(diào)整的全部合作對(duì)策解的集合構(gòu)成了Paret

12、o邊界。從博弈論角度來(lái)看,Braess悖論實(shí)質(zhì)上是非合作網(wǎng)絡(luò)中Nash平衡點(diǎn)不滿足Pareto最優(yōu)性時(shí)出現(xiàn)的詭異現(xiàn)象。如圖1 所示的路網(wǎng), 路段出行時(shí)間（a）4個(gè)路段組成的路網(wǎng)（b）5個(gè)路段組成的路網(wǎng)圖1路網(wǎng)結(jié)構(gòu)圖其中，為用戶在路段上的出行時(shí)間；為自由流情況下，路段上的出行時(shí)間；為路段的延遲參數(shù)，即路段上，每增加單位流量時(shí)，所增加的出行時(shí)間；為路段上的車流量。假設(shè)該問(wèn)題滿足對(duì)稱條件進(jìn)一步假定路網(wǎng)中的瓶頸路段和很短，因此自由流情況下的出行時(shí)間近似為，即假定新增路段的延遲參數(shù)與路段和相等，即設(shè)，則各路段出行時(shí)間可表示成，。路網(wǎng)（）由4個(gè)路段構(gòu)成，從至有兩條路線：路線1（），路線2（），其出行時(shí)間為

13、令，并取，則，。做出和的函數(shù)曲線分別如圖2路網(wǎng)（）中實(shí)線和星號(hào)線所示。圖中兩條線的交點(diǎn)為用戶均衡解，偏離這一平衡必然導(dǎo)致一個(gè)目標(biāo)數(shù)值減小時(shí)另一個(gè)目標(biāo)函數(shù)值增加。此時(shí)用戶均衡解在Pareto邊界上，因此，盡管用戶之間是非合作關(guān)系，其結(jié)果任滿足Pareto最優(yōu)性，不存在可以同時(shí)提高雙方性能的解。路網(wǎng)（）中除了線路1、2以外，增加了路線3（）。設(shè)為分配道路線1上交通流，根據(jù)路網(wǎng)對(duì)稱性，分配到路線2上的交通就也是，因此，分配到路線3上的交通流為。取與路網(wǎng)（）相同的參數(shù)并另，做出和的函數(shù)曲線如圖2路網(wǎng)（）所示。出行時(shí)間，min用戶均衡解路線3路線1、2Pareto 最優(yōu)解流量路網(wǎng)（b）流量路網(wǎng)（a）出行

14、時(shí)間，min用戶均衡解路線1路線2此時(shí)只有一個(gè)Pareto最優(yōu)解，路線3上沒(méi)有車流；而用戶均衡解為，。顯然用戶均衡解不在Pateto邊界上，此時(shí)出現(xiàn)Braess悖論：在路網(wǎng)（）中增加一條通路反而增加了所有用戶的出行時(shí)間。實(shí)際路網(wǎng)中圖1所示的結(jié)構(gòu)并不常見(jiàn)，北京路網(wǎng)中經(jīng)常見(jiàn)到的結(jié)構(gòu)如圖3所示。圖3 路網(wǎng)結(jié)構(gòu)及路段出行時(shí)間描述從到有3條路線，。設(shè)交通需求為，分配到3條路線上的交通流分別為、和。當(dāng)時(shí)，則該問(wèn)題存在Pareto最優(yōu)解，并且與用戶均衡解不一致，發(fā)生Braess悖論。二、模型求解分析北京市二環(huán)路以內(nèi)的某區(qū)域路網(wǎng)。首先，根據(jù)路段上一個(gè)月的車速()和流量（）數(shù)據(jù)以及路段長(zhǎng)度()，估計(jì)路段的自由流

15、出行時(shí)間和延遲參數(shù)。路段出行時(shí)間，因此根據(jù)車速和流量的數(shù)據(jù)，可以擬合出關(guān)系曲線，從而估計(jì)和的值。而對(duì)于某一路段的車流量的獲取，我們根據(jù)該路段的堵塞程度的情況，由圖中各種顏色的比例求得其總流量。假設(shè):車長(zhǎng) ：車距 ：路長(zhǎng)車流量表示：車速假設(shè)，車距根據(jù)4種堵塞程度來(lái)確定。方法如下：從左到右車距依次為：、選取5段路網(wǎng)分析計(jì)算得由關(guān)系曲線估計(jì)出和的值如表14（備注：路段編號(hào)和圖3模型中一樣按順時(shí)針編排）圖4 鼓樓橋路段編號(hào)流量flow（輛）路長(zhǎng)L (m)自由出行時(shí)間(s)延遲參數(shù)1199153068.920.019823262500112.610.0198310070031.530.043742501

16、80081.080.0185514070031.530.012963542400108.110.03367260180081.080.0178此路網(wǎng)驗(yàn)證存在悖論。圖5 西便門橋路段編號(hào)流量flow（輛）路長(zhǎng)L (m)自由出行時(shí)間(s)延遲參數(shù)1179120054.050.0173212990040.540.0180313390040.540.03354183120054.050.0169514394042.340.0169614283037.390.01507171110049.550.0166此路網(wǎng)驗(yàn)證不存在悖論。圖6 東直門北橋路段編號(hào)流量flow（輛）路長(zhǎng)L (m)自由出行時(shí)間(s)延遲

17、參數(shù)118890040.540.0123210077034.680.01983195150067.570.0381413590040.540.01725377150067.570.0102618870031.530.0232712895042.790.0198此路網(wǎng)驗(yàn)證存在悖論。圖7 廣渠門橋 路段編號(hào)流量flow（輛）路長(zhǎng)L (m)自由出行時(shí)間(s)延遲參數(shù)1211120054.050.0147213790040.540.0169312580036.040.03174163110049.550.0174510960027.030.01426202120054.050.015371861300

18、58.560.0180此路網(wǎng)不存在悖論。圖8 建國(guó)門橋路段編號(hào)流量flow（輛）路長(zhǎng)L (m)自由出行時(shí)間(s)延遲參數(shù)110080036.040.0206210376034.230.0190310378035.140.0375413080036.040.0158512778035.140.0158610070031.530.0180711480036.040.0180此路網(wǎng)不存在悖論。根據(jù)對(duì)以上路網(wǎng)的分析可知，在北京市二環(huán)路以內(nèi)，某些路網(wǎng)中（包括二環(huán)路）存在Braess悖論。三、模型評(píng)價(jià)1.論文中關(guān)于出行時(shí)間 的假設(shè)是比較合理的，出行時(shí)間包括自由出行時(shí)間和延遲時(shí)間。2.針對(duì)北京市二環(huán)路以內(nèi)的

19、路網(wǎng)中（包括二環(huán)路），本論文沒(méi)有對(duì)其中的每個(gè)路網(wǎng)做計(jì)算，而是抽取了其中5個(gè)比較典型的“日”字形網(wǎng)絡(luò)進(jìn)行分析。數(shù)據(jù)估算難免存在誤差，有些路段上的堵塞情況沒(méi)有考慮到，這是本論文的缺陷之處，但我們的結(jié)果也基本解決了題目中的要求。3.對(duì)于某一路段車流量的估算，本論文采取的是flow=L/(s1+s2)的方法。道路越堵塞，則車流密度越大，車距越短；道路越串通，則車流密度越小，車距越長(zhǎng)。這種假設(shè)大致符合實(shí)際情況。4.通過(guò)對(duì)悖論的驗(yàn)證，知道要使城市道路網(wǎng)絡(luò)變成一個(gè)高效的城市交通網(wǎng)絡(luò)，就必須根據(jù)整個(gè)城市的交通量及其出行分布來(lái)合理劃分車道。當(dāng)要在城市道路網(wǎng)絡(luò)中添加一條道路，需要通合理設(shè)計(jì)路網(wǎng)結(jié)構(gòu)和確定路段參數(shù)，

20、盡量避免Braess悖論出現(xiàn)。（2）一 問(wèn)題假設(shè)1、假設(shè)GPS導(dǎo)航系統(tǒng)只對(duì)擁堵情況做出判斷提供給用戶，沒(méi)有其他方面的提供，比如天氣，路況等。也就是司機(jī)只通過(guò)擁堵?tīng)顩r選擇路徑。2、GPS導(dǎo)航系統(tǒng)對(duì)道路一定未來(lái)時(shí)間有預(yù)測(cè)能力。3、司機(jī)沒(méi)有個(gè)人愛(ài)好選擇，只是根據(jù)導(dǎo)航系統(tǒng)所提供的所花時(shí)間最短的道路來(lái)行使。4、同上題一樣，所有司機(jī)，無(wú)論是否用導(dǎo)航系統(tǒng)，司機(jī)都對(duì)道路非常熟悉，并且所假設(shè)的司機(jī)如果沒(méi)有導(dǎo)航系統(tǒng)都會(huì)選擇距離最短那條路。5實(shí)際情況中部分車輛，如公交車不根據(jù)GPS路況改變路線，在此假設(shè)不存在這種情況。二、模型分析與建立第二問(wèn)是能否緩解減緩交通堵塞，若能縮短一部分出行者出行時(shí)間，同時(shí)也不會(huì)增加其他出行者的出行時(shí)間，系統(tǒng)的總體性能會(huì)有所提高就可以緩解該狀況。出行者之間不了解其他出行者所能選擇的道路策略，但知道其他出行者做出選擇后的道路狀況，并且出行者選擇路徑是從個(gè)人角度出發(fā)，使得自己出行時(shí)間最短做出的選擇，每個(gè)出行者選擇路徑不是同時(shí)進(jìn)行，所以出行者之間為動(dòng)態(tài)博弈關(guān)系，并且信息不完全，為不完全信息動(dòng)態(tài)博弈。在實(shí)際情況中，因?yàn)槌鲂姓吆芏?，策略空間也很大，博弈分為很多周期，并且即使每個(gè)出行者都其他出行者每個(gè)周期結(jié)束時(shí)的行動(dòng)，由于難以確定對(duì)方所屬類型，我們不能檢驗(yàn)后續(xù)策略是否為Nash均衡。局中人屬于何種類型被假設(shè)為由“自然”賦予的概率而