1、2014美賽A題建模與求解,講解人：王永麗,2014年8月11日,提綱,問題描述,求解方案,1、問題分析與模型建立,2、模型求解與計(jì)算機(jī)仿真,模型優(yōu)缺點(diǎn)分析與改進(jìn),問題描述,題目：除非超車否則靠右行駛的交通規(guī)則,問題：在一些汽車靠右行駛的國(guó)家（比如美國(guó)，中國(guó)等），多車道的高速公路常常遵循以下原則：司機(jī)必須在最右側(cè)駕駛，除非他們正在超車，超車時(shí)必須先移到左側(cè)車道，超車然后再返回右車道。 建立數(shù)學(xué)模型來分析這條規(guī)則在低負(fù)荷和高負(fù)荷狀態(tài)下的交通路況的表現(xiàn)。,不妨考察一下流量和安全的權(quán)衡問題，車速過高過低的限制，或者這個(gè)問題陳述中可能出現(xiàn)的其他因素。這條規(guī)則在提升車流量方面是否有效？如果無效，提出能夠

2、提升車流量、安全系數(shù)或其他因素的替代品（包括完全沒有這種規(guī)則）并加以分析。 在一些國(guó)家，汽車靠左行駛是常態(tài)，探討你的解決方案是否稍作修改即可適用，或者需要一些額外的需要。 最后，以上規(guī)則依賴于人的判斷，如果相同規(guī)則的交通運(yùn)輸完全在智能系統(tǒng)的控制下，無論是部分網(wǎng)絡(luò)還是嵌入使用的車輛設(shè)計(jì)，在何種程度上會(huì)修改你前面的結(jié)果？,問題分析與模型建立,2、是否存在更好的交通規(guī)則，如果存在，如何說明其更好。,1、在交通暢通與交通擁擠情形下，“右行左超車”交通規(guī)則的表現(xiàn)如何，選取什么樣的評(píng)價(jià)參數(shù)來衡量。由此來確定該規(guī)則是否需要改進(jìn)以及如何改進(jìn)。,3、新規(guī)則是否適合靠左行駛的國(guó)家，是否需要考慮其他因素。,4、在智

3、能系統(tǒng)的控制下，上述規(guī)則表現(xiàn)如何，結(jié)果有何變化。,需要解決的問題,注：對(duì)該問題的研究可以歸結(jié)為“右行左超車”規(guī)則下的交通 流模型的研究。,模型建立-元胞自動(dòng)機(jī)模型,對(duì)于交通問題的研究中最經(jīng)典的模型有跟車模型、流體力學(xué)模型和元胞自動(dòng)機(jī)模型。,跟車模型將交通流處理為分散的粒子, 以單個(gè)車輛作為描述對(duì)象, 通過研究車輛之間的相互作用來描述交通流的特性。由于這種研究側(cè)重于車輛間相互作用的精細(xì)刻畫，屬于微觀模型,因此往往難以進(jìn)行大規(guī)模的交通系統(tǒng)仿真。,流體力學(xué)模型以密度、速度和流量等宏觀量來描繪車輛的平均作用行為，可以描述“交通激波”現(xiàn)象, 但是該模型建立在速度和密度平衡的條件之上, 不適用于描述本質(zhì)上

4、處于非平衡狀態(tài)的交通現(xiàn)象, 例如“幽靈式”交通阻塞、交通遲滯等。,交通流元胞自動(dòng)機(jī)模型(Cellular Automaton，簡(jiǎn)稱 CA模型) 是一種時(shí)空離散的局部動(dòng)力學(xué)模型，特別適合于空間復(fù)雜系統(tǒng)的時(shí)空動(dòng)態(tài)模擬研究。交通流元胞自動(dòng)機(jī)的研究主要通過計(jì)算機(jī)仿真來模擬真實(shí)交通流,可以很好地反映交通流的宏觀現(xiàn)象。,CA-184模型是采用一維格點(diǎn)鏈上的粒子來模擬公路上的車輛。在CA-184模型中,一條道路可以看作由一系列元胞組成,用元胞狀態(tài)表示道路上某個(gè)位置（有無車輛）的狀態(tài)，每個(gè)元胞左右各有一個(gè)元胞作為該元胞的鄰居，根據(jù)t時(shí)刻自身和鄰居的狀態(tài)決定t+1時(shí)刻該元胞的狀態(tài)。通過動(dòng)態(tài)仿真模擬交通流的變化。

5、,一維交通流元胞自動(dòng)機(jī)-CA-184模型,單車道元胞自動(dòng)機(jī)NS模型與FI模型,1992年,德國(guó)學(xué)者Nagel和Schreckenberg提出了單車道的NS模型,該模型考慮了汽車的加速和隨機(jī)慢化的可能性,同時(shí)在模型中引入了高速車，即單位時(shí)步的行進(jìn)格點(diǎn)數(shù)大于l 。,1996年,日本學(xué)者Fukui和Ishibashi在NS模型基礎(chǔ)上提出了單車道FI模型,認(rèn)為車輛的加速不僅限于一個(gè)格點(diǎn),而是以最高車速為加速目標(biāo),即可以直接加速到最大速度。,1998年，K.Nagel 等人在單車道NS模型的基礎(chǔ)上提出了雙車道元胞自動(dòng)機(jī)交通流NS模型，與單車道NS模型相比, 多車道NS模型主要是增加了車輛換道規(guī)則，要求在

6、各條車道上行駛的車輛要遵守NS規(guī)則, 在進(jìn)行車道變換時(shí)還要滿足車輛換道規(guī)則。,多車道元胞自動(dòng)機(jī)NS模型與FI模型,多車道FI模型則是在單車道FI模型的基礎(chǔ)上增加了車輛換道規(guī)則，要求在各條車道上行駛的車輛要遵守FI規(guī)則, 在進(jìn)行車道變換時(shí)遵循車輛換道規(guī)則。,用CA模型描述交通流，主要是通過對(duì)駕駛員駕車行為的分析，建立駕駛員或車輛的行為輸出規(guī)則，從而建立元胞自動(dòng)機(jī)的運(yùn)行規(guī)則，然后仿真實(shí)際交通背景，模擬整體元胞群的動(dòng)態(tài)過程，從中得到解決交通問題的方法或信息。這類模型考慮的主要問題包括：如何用微觀規(guī)則的建模來描述元胞的運(yùn)動(dòng)過程；如何用宏觀規(guī)則的建模來描述高速公路運(yùn)行車輛的隨機(jī)性，這是交通現(xiàn)象的重要特征

7、。,本賽題要求評(píng)價(jià)“右行左超車”的交通規(guī)則對(duì)高速公路的通行能力和安全性的影響。通過對(duì)CA模型建模和仿真一般方法的理解，需要研究以下四個(gè)方面的問題：首先要選取合適的評(píng)價(jià)指標(biāo)，這些指標(biāo)不僅能用于超車規(guī)則對(duì)高速公路的通行能力和安全性的評(píng)價(jià)，而且還必須便于在元胞自動(dòng)機(jī)仿真過程中提?。黄浯?，建立高速公路上車輛的運(yùn)行狀態(tài)隨時(shí)間變化的微觀規(guī)則模型，特別是“右行左超車”的規(guī)則模型；第三是運(yùn)行車輛的不同運(yùn)行狀態(tài)改變的宏觀概率分布，這是由交通問題的隨機(jī)性決定的, 而隨機(jī)性是交通問題的一個(gè)特別重要的特性；最后是設(shè)計(jì)元胞自動(dòng)機(jī)的仿真對(duì)比試驗(yàn)，特別是元胞群空間、初始元胞群密度、分布與狀態(tài)等。,“右行左超車”交通規(guī)則下的

8、元胞自動(dòng)機(jī)模型,評(píng)價(jià)參數(shù)的確定,1）車流密度（ ）：一個(gè)車道單位長(zhǎng)度內(nèi)某一瞬時(shí)存在的車輛數(shù)，以輛/千米表示，即 （1）,注：車流密度主要用來表征交通擁擠（Heavy Traffic）與交通暢通（Light Traffic）的狀態(tài)。車流密度越大，說明交通越擁擠，否則就越暢通。,2）平均車速（ ）：,在固定路段內(nèi)不同車道上所有車輛的平均時(shí)速的平均值， 其定義如下：,（2）,3）交通流量（Q）：?jiǎn)挝粫r(shí)間內(nèi)通過某一固定點(diǎn)的車輛數(shù)。 根據(jù)交通流的理論,交通流量可定義為車流密度與平均車速 的乘積，即：,（3）,4）車道改變率（ ）：,給定路段上，單位時(shí)間內(nèi)的平均變道次數(shù)占總車輛數(shù)的比例，等于給定路段上某個(gè)

9、時(shí)間段內(nèi)的車輛變道總數(shù)除以時(shí)間與車輛總數(shù)的乘積，即,（4）,5）連續(xù)剎車率（ ）：,給定路段上，單位時(shí)間內(nèi)車輛連續(xù)減速改變的次數(shù)超過,兩次（包含兩次）的計(jì)數(shù)。,注：考慮到車道改變會(huì)增加事故發(fā)生的可能性，而連續(xù)剎車則可以理解成為避免發(fā)生事故而采取的措施，這些可以看作安全性隱患，故可用整個(gè)路段上的車道改變數(shù)及連續(xù)剎車計(jì)數(shù)來衡量交通規(guī)則的安全性。,仿真參數(shù)設(shè)定,1）加速概率（ ）：,對(duì)整個(gè)模擬路段上所有滿足加速規(guī)則的車輛，讓其以,的概率隨機(jī)加速。,2）隨機(jī)慢化概率（ ）,對(duì)所有以恒速行駛的車輛將以一個(gè)很小的概率 隨機(jī)減速，,該指標(biāo)主要用于描述駕駛員的駕駛行為輸出。,3）超車概率( ）,對(duì)整個(gè)仿真路段

10、上滿足向左（向右）變道規(guī)則的車輛，,注：由于高速公路上大多數(shù)駕駛員都有高速行駛的欲望，因此，,而由快車道向慢車道變道的概率則較小。,對(duì)于超車欲望值為1的車輛，其變道概率設(shè)為1。,本模型中假設(shè)左車道為快車道，右車道為慢車道。,1、只討論高速公路上“右行左超車”規(guī)則的作用與影響。,基本假設(shè),2、假設(shè)沒有任何停止信號(hào)或交叉打斷當(dāng)前的交通流，沒有其他的入口與出口，沒有急轉(zhuǎn)彎，且路上僅有一種類型的車輛，但車道有快慢車道之分，即在不同車道上最低與最高限速不同。不考慮車輛在運(yùn)行道路上停車的情況。,3、在仿真實(shí)驗(yàn)中，假設(shè)每個(gè)元胞只被1輛車占據(jù)。車輛的換道不考慮車輛加減速的中間過程，當(dāng)車輛滿足變道條件時(shí)，將直接

11、調(diào)整到合適的車道。,4、考慮到不同駕駛員的駕駛行為有所差異，車輛狀態(tài)的改變具有一定的隨機(jī)性，因此，假設(shè)在行車過程中，所有車輛狀態(tài)的改變都按一定的概率發(fā)生。,5、在仿真過程中，通過在一個(gè)預(yù)先設(shè)定的區(qū)域，用定量的汽車采用循環(huán)的方式來模擬整個(gè)高速交通情況。仿真路段內(nèi)汽車數(shù)量即車輛密度是常數(shù)，但是將對(duì)不同的密度進(jìn)行仿真。,元胞自動(dòng)機(jī)的微觀規(guī)則設(shè)計(jì),首先研究高速路一個(gè)方向兩車道的超車問題。假設(shè)每一 車道分為1000個(gè)元胞，則2條車道劃分為 的元胞矩陣,定義每個(gè)元胞長(zhǎng)度為5.5米，則模擬的實(shí)際道路長(zhǎng)度為5.5km。,仿真的時(shí)間步設(shè)為1秒。一個(gè)元胞的全部狀態(tài)用一個(gè)5元組 表示： （ ）,）,5個(gè)狀態(tài)參數(shù)分別

12、為：第i輛車在t時(shí)刻的速度，所處元胞的位置，超車欲望值，所處車道及其與前車的間距。,，,車速離散化為元胞長(zhǎng)度的整數(shù)倍。,1元胞/秒=19.8公里/小時(shí)。,車輛前行規(guī)則設(shè)計(jì),在假設(shè)車輛按照周期循環(huán)的方式來模擬的條件下，向前行駛的車輛在每一個(gè)離散的t到t+1時(shí)間步，每一車道上的車輛狀態(tài)按下列規(guī)則同步更新：,1） 加速規(guī)則 如果當(dāng)前車輛與同一車道上前車間距大于安全 距離且車速?zèng)]有達(dá)到最大速度，則以概率 加速。即,2）減速規(guī)則 如果當(dāng)前車輛與前車的間距小于安全間距， 但大于等于當(dāng)前道路最大限速與最小限速的差，則速度減1 或減速至最小速度，若當(dāng)前車輛與前車的間距小于最大限速 與最小限速的差，則減速至最小

13、速度。即,其中，第2種情形的減速是為了避免撞車的可能性。,。,該規(guī)則用于描述駕駛員的駕駛行為，其減速行為不一定滿足減速條件，但所有車輛都有隨機(jī)減速的可能。,4）位置更新規(guī)則：,車輛換道規(guī)則設(shè)計(jì),“右行左超車”下的雙車道換道規(guī)則,由于高速路上車速相對(duì)較高，因此，考慮到安全性的因素，借鑒文獻(xiàn)【1】中的換道規(guī)則，提出如下雙車道換道規(guī)則：,1）車輛由右向左變道規(guī)則。如果當(dāng)前在右車道行駛的車輛 與前車的間距較小使得當(dāng)前車輛的前行受阻，而其與相鄰左 車道上的前車間距較大，同時(shí)與左車道上后方車輛的間距 大于安全距離，則車輛以概率 由右向左變道，即,表示右車道的最大限速，,表示左車道的最大限速。,2）車輛由左

14、向右變道規(guī)則。如果在左車道行駛的車輛與相鄰 右車道前方與后方車輛的間距都大于安全距離，則以概率 由左向右變道，即,超車規(guī)則設(shè)計(jì),1）超車欲望參數(shù),在兩車道模型中，只有位于右車道的車輛會(huì)產(chǎn)生超車欲望，且其超車欲望的產(chǎn)生與同車道前方車輛的狀態(tài)有關(guān)，故其超車欲望值的定義如下：,表示第i輛車的車速大于其前車的車速，,2）“右行左超車”下的超車規(guī)則,在兩車道模型中，考慮到實(shí)際駕駛中喜歡跟車的小概率駕駛行為，滿足超車條件的車輛不一定選擇超車，因此，其超車規(guī)則設(shè)計(jì)如下：,當(dāng)超車的車輛返回右道后，其超車欲望值 ,然后再判斷是否滿足超車條件，確定 的值，,重復(fù)此過程直至超車欲望值不再取1為止。,對(duì)于超車欲望值為

15、1的車輛若不滿足向左變道條件，則仍在當(dāng)前車道行駛，超車欲望值賦0，下一時(shí)刻再判斷其是否滿足超車條件。,兩車道元胞自動(dòng)機(jī)仿真步驟,步1.（初始化參數(shù)）輸入車道數(shù),步3.（狀態(tài)值計(jì)算） 對(duì)于每輛車，計(jì)算與前車的間距 ，,與前車的安全間距 ，,與相鄰車道前方車輛間距,步6. (加速、減速判別) 對(duì)每輛車進(jìn)行如下判斷:,步7. (由右向左換道判別),否則, 車輛仍在右車道行駛,同時(shí),步8. (由左向右換道判別),步9. (位置更新) 令,則自動(dòng)計(jì)數(shù)駛出系統(tǒng)的汽車數(shù)，然后以當(dāng)前狀態(tài)重新放入開放 車道的相應(yīng)元胞內(nèi)，重復(fù)上述過程直至,仿真過程說明,1）流量產(chǎn)生規(guī)則,在進(jìn)行仿真實(shí)驗(yàn)時(shí)，初始車流的產(chǎn)生采用隨機(jī)性

16、的原則，即在仿真路段的不同車道上按一定車輛密度隨機(jī)撒入具有不同速度的車輛。此處，車輛密度是指車輛數(shù)占總元胞數(shù)的比例。,2）汽車循環(huán)規(guī)則,自動(dòng)計(jì)數(shù)駛出系統(tǒng)的汽車數(shù)，然后重新放入開放車道的相應(yīng)元胞內(nèi)，如果沒有開放車道則等下一步有開放車道再放入。,3）連續(xù)剎車計(jì)數(shù)規(guī)則,如果某輛車在某一固定的連續(xù)時(shí)間段內(nèi)車速減速改變的次數(shù)超過兩次（包含兩次），則記其為一次連續(xù)剎車。,4）超車成功計(jì)數(shù)規(guī)則,如果一輛車的超車欲望值由1變?yōu)?，則記超車成功1次。超車成功率即為在整個(gè)仿真時(shí)段內(nèi)超車欲望值由1變?yōu)?的車輛數(shù)占所有超車欲望值為1的車輛數(shù)的比率。,5）統(tǒng)計(jì)性原則,對(duì)每組參數(shù)，通過隨機(jī)重復(fù)n次然后取平均的方式得到最后

17、的實(shí)驗(yàn)結(jié)果。,仿真結(jié)果與分析,對(duì)兩車道模型，分別對(duì)“右行左超車”規(guī)則與無規(guī)則的交通流進(jìn)行仿真。這里所指的無規(guī)則是指車輛的超車與換道只是按一定的概率進(jìn)行,超車完成后也只是以一定的概率返回右道,與超車欲望值無關(guān)。在“右行左超車”規(guī)則情形下，超車欲望值為1的車輛超車完成后必須返回右道行駛。,在考慮快慢車道的情形下，通過選取不同的參數(shù)，進(jìn)行大量的仿真試驗(yàn)，最終確定仿真參數(shù)如下：,仿真時(shí)長(zhǎng)T=1200秒，隨機(jī)重復(fù)次數(shù)=20，,1）相同概率設(shè)置下有規(guī)則與無規(guī)則的對(duì)照,2）最大限速提高的對(duì)照,在智能系統(tǒng)的控制下有規(guī)則與無規(guī)則的對(duì)照,在智能系統(tǒng)的控制下，即不考慮人為的因素與駕駛員的駕駛行為，只要滿足相關(guān)條件，

18、就自動(dòng)按規(guī)則行駛。此時(shí)，除了概率值，其他參數(shù)都不變，而相關(guān)概率值的設(shè)置如下：,不分快慢車道情形下，有規(guī)則與無規(guī)則的對(duì)照,時(shí)空?qǐng)D分析,在第一組參數(shù)下，分別截取車流密度分別為0.1 與0.8時(shí)，兩個(gè)車道在“右行左超車”規(guī)則與無規(guī)則情形下的時(shí)空斑，如下圖所示：,結(jié)論：對(duì)兩車道模型，當(dāng)車流密度較低，交通暢通的情況下，無論是道路的通行能力還是安全性，無規(guī)則都要比有規(guī)則要好，而當(dāng)車流密度較大，使得交通比較擁擠時(shí)，有規(guī)則的安全性要好一些。從道路的利用率上講，有規(guī)則要好于無規(guī)則。無規(guī)則情形下兩個(gè)車道的利用率均勻，右道利用率相對(duì)較低。此外，無論是交通暢通還是交通擁擠，提高車道的最大與最小限速都將不僅提升道路的通行能力，而且也可以提高行車的安全性。但此時(shí)，當(dāng)車流密度較大時(shí)，無規(guī)則要比有規(guī)則的安全性高。,1）提出了超車欲望值的概念，對(duì)“右行左超車”規(guī)則進(jìn)行刻畫， 并以此對(duì)超車行為進(jìn)行