不確定性條件下的最優(yōu)路徑問題

不確定性條件下的最優(yōu)路徑問題摘要本文針對現(xiàn)實生活中的交通網(wǎng)絡(luò)，綜合各種影響因素，建立不確定條件下的最優(yōu)路徑選擇模型。首先，本文改變傳統(tǒng)路徑最短算法的思路，以尋求行駛時間最短為目標(biāo)，綜合考慮不確定因素，通過線性回歸分析，建立了基本的各路段行駛時間與路段平均行駛時間、行程時間標(biāo)準(zhǔn)差、行程緊急程度、動態(tài)交通變化量之間的模型。得出不確定條件下車輛從起點到終點最優(yōu)路徑的定義和數(shù)學(xué)表達(dá)式，并將此模型運用于第一問示例，得出結(jié)論。。。。其次，在已知每條路徑行駛時間均值與標(biāo)準(zhǔn)差的條件下，借助蟻群算法在實際交通網(wǎng)絡(luò)中尋找最優(yōu)路徑。接著，考慮到道路擁擠情況，利用道路阻抗排隊論的結(jié)論在原有模型基礎(chǔ)上進(jìn)行改進(jìn)，建立新的模型并應(yīng)用于交通網(wǎng)絡(luò)最優(yōu)路徑的搜索。最后，對現(xiàn)實網(wǎng)絡(luò)的重新分析，綜合其他不確定因素完善現(xiàn)有模型。關(guān)鍵詞：回歸分析蟻群算法排隊論一、問題重述目前，交通擁擠和事故正越來越嚴(yán)重的困擾著城市交通。隨著我國交通運輸事業(yè)的迅速發(fā)展，交通“擁塞”已經(jīng)成為很多城市的“痼疾”。在復(fù)雜的交通環(huán)境下，如何尋找一條可靠、快速、安全的最優(yōu)路徑，已經(jīng)成為所有駕駛員的共識。傳統(tǒng)的最優(yōu)路徑問題的研究大多數(shù)是基于“理想”的交通狀況下分析的，即:假設(shè)每條路段上的行駛時間是確定的。在這種情況下，最優(yōu)路徑就是行駛時間最短的路徑，可以用經(jīng)典的最短路徑算法來搜索（例如Dijkstra最短路徑算法）。目前的車輛路徑導(dǎo)航系統(tǒng)也大都是基于這種理想的狀況下的最優(yōu)路徑算法，尋找行駛時間最短的路徑。事實上，由于在現(xiàn)實生活中，會受到很多不確定性因素的影響，例如：交通事故、惡劣天氣、突發(fā)事件等，車輛的行駛時間存在著不確定性。第一問：如圖1所示的交通網(wǎng)絡(luò)，起點：中國礦業(yè)大學(xué)，終點：XX火車站。假設(shè)車輛的行駛時間是隨機(jī)變量。如果走繞城快速路，平均33分鐘到達(dá)，雖然路程遠(yuǎn)，但是很少發(fā)生堵車，所以行駛時間的波動很小，標(biāo)準(zhǔn)差只有1分鐘；如果走市區(qū)道路，平均30分鐘到達(dá)，雖然路程近，但是市區(qū)經(jīng)常發(fā)生堵車，所以行駛時間的波動很大，標(biāo)準(zhǔn)差高達(dá)15分鐘。如果用傳統(tǒng)的最優(yōu)路徑算法，應(yīng)該選市區(qū)道路，因為平均時間短。在現(xiàn)實中，為了準(zhǔn)時到達(dá)目的地，駕駛員通常會選擇路程稍遠(yuǎn)的繞城快速路。繞城快速路對于一般的交通網(wǎng)絡(luò)，假設(shè)已知每條路段行駛時間的均值和標(biāo)準(zhǔn)差，請建立數(shù)學(xué)模型，定量的分析車輛行駛時間的不確定性，然后給出在不確定性條件下車輛從起點到終點的最優(yōu)路徑的定義和數(shù)學(xué)表達(dá)式，將此模型應(yīng)用到圖1的例子中會選擇哪條道路。提示：（1）傳統(tǒng)的最優(yōu)路徑可以看成是平均行駛時間最短的路徑，本題中的最優(yōu)路徑不僅要考慮平均行駛時間，而且還要考慮不確定性條件下車輛準(zhǔn)時到達(dá)終點的可靠性等因素；⑵假設(shè)車輛在每條路段上的行駛時間是隨機(jī)變量，這里的“路段”相當(dāng)于網(wǎng)絡(luò)圖中的“邊”。第二問：根據(jù)第一問的定義，假設(shè)已知每條路段行駛時間的均值和標(biāo)準(zhǔn)差，設(shè)計算法搜索最優(yōu)路徑，并將該算法應(yīng)用到具體的交通網(wǎng)絡(luò)中，用計算結(jié)果驗證算法的有效性。如果可能的話，從理論上分析算法的收斂性、復(fù)雜性等性質(zhì)。第三問：在現(xiàn)實的交通網(wǎng)絡(luò)中，某個路段發(fā)生了交通擁堵，對上游或者下游路段的交通狀況有很大的影響，從而導(dǎo)致了交通路段之間的行駛時間有一定的相關(guān)性，這種相關(guān)性情況很復(fù)雜，其中一個典型的例子如下：下游路段發(fā)生交通擁堵使車輛減速或者排隊，導(dǎo)致上游路段發(fā)生擁堵。請建立數(shù)學(xué)模型描述這種交通路段之間行駛時間的相關(guān)性，并將這種相關(guān)性應(yīng)用到第一問和第二問的最優(yōu)路徑搜索問題中，并設(shè)計算法解決考慮相關(guān)性的最優(yōu)路徑搜索問題，給出算例驗證算法的有效性。如果可能的話，從理論上分析算法的收斂性、復(fù)雜性等性質(zhì)。提示：這里的相關(guān)性，可以從空間和時間的兩個方面考慮。空間相關(guān)性：同一個時間段（例如7:00-8:00之間），路段@和路段匕的相關(guān)性。時間相關(guān)性：對于路段@,不同時間段的相關(guān)性，例如7:00-8:00和8:00-9:00之間的相關(guān)性。當(dāng)然，也可以兩種相關(guān)性同時考慮。第四問：從不確定性條件下交通網(wǎng)絡(luò)的實際情況出發(fā)，在合理假設(shè)下，進(jìn)一步完善前三問的數(shù)學(xué)模型和相關(guān)算法。或者，提出一種或多種與前三問不同的最優(yōu)路徑的定義方法，建立相關(guān)的數(shù)學(xué)模型并設(shè)計算法，應(yīng)用數(shù)值算例驗證算法的有效性。如果可能的話，從理論上分析算法的收斂性、復(fù)雜性等性質(zhì)。說明：本題中的所涉及的算例最好能采用真實的交通網(wǎng)絡(luò)數(shù)據(jù)，也可以使用自己假設(shè)的數(shù)據(jù)，交通網(wǎng)絡(luò)的規(guī)模越大越好。二、問題背景隨著智能交通系統(tǒng)（訂$）的發(fā)展，對出行者路徑選擇行為的研究也成為各國學(xué)者關(guān)注的熱點問題之一。路徑選擇主要解決的問題是：以智能交通系統(tǒng)實時提供的路況信息和駕駛者交通需求為輸入，在一定優(yōu)化目標(biāo)下，為駕駛者提供最合理的出行路徑。在傳統(tǒng)路徑選擇方法中，一般是以Dijkstra最短路徑算法為典型，此類算法雖然降低了模型的復(fù)雜度，但是忽略了駕駛者的個性化需求，誘導(dǎo)系統(tǒng)為不同的人群提供相同的方案，這必然會在網(wǎng)絡(luò)中產(chǎn)生集聚效應(yīng)，產(chǎn)生擁擠漂移現(xiàn)象，使網(wǎng)絡(luò)交通流量處于失衡狀態(tài)。所以，有必要在多不確定屬性條件下，對路徑選擇綜合分析。三、基本假設(shè)與符號說明3.1基本假設(shè).交通網(wǎng)絡(luò)中的各路段行駛時間均值與標(biāo)準(zhǔn)差已知。.本文收集的數(shù)據(jù)真實可靠。.忽略駕駛者主觀導(dǎo)致行駛時間變化的因素。3.2符號說明四、問題分析與思路流程4.1問題分析首先對于綜合評估不確定性因素的建模，我們不止考慮到時間最短以及時間的波動性（也就是標(biāo)準(zhǔn)差）這兩個因素，還有另外一些不確定性因素，例如，安全性、舒適性、擁擠程度、車道數(shù)、道路質(zhì)量等級、行人及非機(jī)動車數(shù)量、交通事故率、行程費用、沿途景觀等。這些都將作為影響最終時間的主要因素，注意這些因素是不確定的。從駕駛?cè)说慕嵌瓤紤]，理想最優(yōu)路徑的確定過程應(yīng)綜合考慮各主要出行影響因素并充分體現(xiàn)駕駛?cè)说闹鲃有浴Ｋ跃C合面向駕駛者的個性化需求構(gòu)建可行路徑的屬性集即路徑綜合評價指標(biāo)體系。利用回歸分析建立行程時間模型。其次，當(dāng)我們面對一個具體的復(fù)雜網(wǎng)絡(luò)時，解答：此次建模不止考慮到時間最短以及時間的波動性（也就是標(biāo)準(zhǔn)差）這兩個因素，還有另外一些不確定性因素，例如，安全性，舒適性，擁擠程度，車道數(shù)，道路質(zhì)量等級，行人及非機(jī)動車數(shù)量，交通事故率，行程費用，沿途景觀等。這些都將作為影響最終時間的主要因素，注意這些因素是不確定的。從駕駛?cè)说慕嵌瓤紤]，理想最優(yōu)路徑的確定過程應(yīng)綜合考慮各主要出行影響因素并充分體現(xiàn)駕駛?cè)说闹鲃有?。本文綜合面向駕駛?cè)说膫€性化需求，構(gòu)建可行路徑的屬性集即路徑綜合評價指標(biāo)體系如下：X={xj'j=1，2,⑻⑴式中x為行程平均時間，注意此行程平均時間僅僅是在不考慮人的主觀性所得出的平均值，以時間最短為主要目標(biāo)；x為行程時間標(biāo)準(zhǔn)差，衡量在沒有其他因素影響下的偏離行程平均時間2的程度；x為當(dāng)前行程目標(biāo)緊急程度評價項用以衡量駕駛?cè)说木o急程度；X為動態(tài)路段交通變化量用以衡量較理想平均路段交通的偏離程度，例4如突然發(fā)生較大堵塞等狀況。X為行程距離；X為行程舒適度,是考慮可行路徑各路段的擁擠程度,車5道數(shù)，道路質(zhì)量6等級,行人及非機(jī)動車數(shù)量等因素

而所得的綜合評價值；X為安全度，是考慮可行路徑各路段交通事故率的綜合評價值；X8為彳行程費用，主要考慮路段收費和油耗?？梢娚鲜鯴,X,X,X皆是影響最終行程時間的相關(guān)因素，只是各因素在所占1權(quán)重2上會3不一4樣。而另外的因素是影響駕駛員主觀原則的因素?？傊?以上因素皆是評價最短路徑的主要因素。由以上說明可知，最終行程時間X=X（x,X,X,工）,假設(shè)最終行程時間函數(shù)是關(guān)于四個主要變量的線性函數(shù)1,另2外根3據(jù)以4上分析我們知道在不考慮除X以外的因素時，x=X，如此我們利用基準(zhǔn)值丁=X的增量形要求*=必工，X,X,%）的表達(dá)式，也就是*=口1+九X*+九X*+九X*）,我們可以將1X*我們可以將1X*2X*X*3X,X,X22 33 44叫做偏差量，相應(yīng)的九叫做相應(yīng)比重。具體分析計算如下：234對于X*，由于它是由標(biāo)準(zhǔn)差引起的，也就說與平均值之間的偏差，假設(shè)行程時間變量服從正態(tài)分布，那么我們理所當(dāng)然的認(rèn)為X*服從標(biāo)準(zhǔn)2正態(tài)分布，所以可以將X*當(dāng)做一個區(qū)間數(shù)，由概率論的相關(guān)知識，我2們可以只考慮偏差概率大的部分，即X*e[-11]；22’2對于X”由于它是由x即當(dāng)前行程目標(biāo)緊急程度評價項用以衡量駕駛?cè)说木o3急程度所決定,3我們可以用離散值來標(biāo)定相應(yīng)緊急程度,當(dāng)然程度越急，相應(yīng)時間也就會減得越少。如此我們可以用：X*e{-101},3 22其中駕駛員很急，則對應(yīng)-1,駕駛員一點都不急對應(yīng)1,在這之間2 2對應(yīng)0。為了簡便分析,我們只分這三種等級,很明顯的可以看出這種取值是符合實際的。對于x*,X為動態(tài)路段交通變化量用以衡量較理想平均路段交通的偏44離程度，我們仿照X*來規(guī)定取值，X*e{-1,0,1}，其中-1對應(yīng)較我們3 4 2 2 2所建立的理想時間時的路段交通堵塞狀況要輕得多，1則對應(yīng)較之重2的情形了,在這之間是0,也就是相差不多的情況。對于小仆仆則依實際而定。

如此最終行程時間函數(shù)模型建立。之后是關(guān)于最短路徑的評價標(biāo)準(zhǔn)，兼顧x,X5,x6,x7,x8等因素來做相應(yīng)的綜合評價。在不確定性條件下車輛從起點到終點的最優(yōu)路徑的定義如下，關(guān)于綜合評價的最小值所對應(yīng)的路徑即為最優(yōu)路徑。以下是關(guān)于綜合評價的模型：建模所需要的理論模型是不確定型多屬性決策方法模型：多屬性決策是決策理論研究的重要內(nèi)容,現(xiàn)已被廣泛應(yīng)用于項目評估、方案優(yōu)選、效益綜合評價等諸多領(lǐng)域。對于智能交通系統(tǒng)研究中的路徑選擇問題，交通路網(wǎng)信息本身就存在較大的動態(tài)性和隨機(jī)性，諸多路徑評價指標(biāo)只能通過測算、建模來給出當(dāng)前交通狀態(tài)下的估計值，與真實值相比存在誤差，簡單將其忽略有可能導(dǎo)致路徑選擇結(jié)果的不合理性，同時駕駛?cè)俗鳛閱我粋€體，由于其性格、愛好、駕駛熟練程度的不同，對路徑選擇具有一定的偏好性。而且這種偏好本身具有模糊性，難以量化，因此本文基于不確定型多屬性決策方法研究動態(tài)路徑選擇問題，具有較強(qiáng)的實際應(yīng)用背景。對于不確定型多屬性決策問題，設(shè)可行方案集為y={y|i=1,2,,M},屬性集為X1j\j=1,2, ,N},各屬性對應(yīng)的權(quán)重向量為W={wj|j=1,2, ,N},屬性權(quán)重滿足泮w廣1，且對于任意的w/有TOC\o"1-5"\h\z... j=1W>0。???設(shè)ar[adown,a.]為可行方案yi關(guān)于屬性wj的取值區(qū)間，則決策矩陣為:(2)a a(2)A=11 1 na： a：n1 ..: nn考慮到屬性類型有效益型（屬性值越大越好型）和成本型（屬性值越小越好型），為了消除不同物理量綱對決策結(jié)果的影響，需要將決策矩陣人化為規(guī)*化矩陣a。根據(jù)區(qū)間數(shù)的運算法則，對于效益型和成本型，轉(zhuǎn)換公式分別為式（3），（4）：

downaijadownupaijaup1/aup downaijadownupaijaup1/aup ij—dowmaijupaij/（1/adown）2ji=11/adown由于多屬性決策的本質(zhì)是對各方案綜合屬性值的排序比較，針對規(guī)X化決策矩陣A，假定各屬性的權(quán)重向量0已確定，則方案的綜合屬性值為：?N(5)z=￡(w^j)?j=1?由于一仍是區(qū)間數(shù)，為了能對方案進(jìn)行排序，需定義區(qū)間數(shù)之間兩兩i比較的可能度概念。以下是相關(guān)可能度概念的定義：當(dāng)2和b之間至少有一個是區(qū)間數(shù)時，設(shè)a=[adown,aup]，b=[bdown,bup]，記L(a)=aup—adown,L(b)=bup—bdown,則稱P(a>b)為a>b的可能度，且P(a>b)=max{0,L(a)+L(b)-max(bup—bdown,0)}/[L(a)+L(b)](6)基于各方案之間的可能度，令p=P(zt>Zj)屣立各方案的可能度互補矩陣P,對于互補判斷矩陣，相關(guān)文獻(xiàn)里給出了互補判斷矩陣的排序向量8={①Ii=1,2,,M}的一個計算公式：zp+M/—1ij①二j1 i M(M—1)按其分量大小對方案進(jìn)行排序即可得到最優(yōu)方案。以上是關(guān)于我們建立綜合評價體系所要用到的理論模型，之后將它與我們所要解決的實際問題結(jié)合起來?；氐浇獯饎傞_始的地方，我們建立了8個主要因素，其中前4個主要因素導(dǎo)出了行程時間這個主要因素，所以最終我們建立了5個主要因素。按照理論模型中對應(yīng)的說法是我們建立了5個屬性，即：令a二x,a二x,a二x,a=x,a=x，如此我們就建立了相應(yīng)的屬性集1。 25364758需要說明的是，為綜合評價的方便，需將不同物理意義的各種評價指標(biāo)轉(zhuǎn)換為[0,1]區(qū)間的量綱為1的滿意度評價指標(biāo)，本文同意將其轉(zhuǎn)化為成本型(設(shè)計指標(biāo)越小越好型)；同時，由于在實際中客觀交通路況的動態(tài)變化和主觀個性票號的改變，路徑評價指標(biāo)值具有一定的隨機(jī)性，可以表示為區(qū)間數(shù)形式，即：ai=[adown,aup](i=1,2,3,4,5)以下是關(guān)于一開始所說的指標(biāo)權(quán)重的確定：在一般情況下，出行者會根據(jù)個人經(jīng)驗喜好或習(xí)慣去選擇路徑，對指標(biāo)權(quán)重的確定反映了駕駛?cè)说膫€性化需求，但個性化偏好往往具有復(fù)雜性和模糊性，用模糊數(shù)表示判斷的結(jié)果能夠更好反映事物的客觀本質(zhì)。因此，本文將駕駛?cè)说膫€性化需求引入指標(biāo)權(quán)重確定過程，基于模糊數(shù)學(xué)理論進(jìn)行指標(biāo)權(quán)重的個性化確定，相比一般方法，模糊分析法簡化了駕駛?cè)伺袛嗦窂皆u價指標(biāo)相對重要性的復(fù)雜程度，解決了可行路徑優(yōu)化排序過程中的一致性問題。模糊分析法的基本過程是以矩陣形式表達(dá)各路徑評價指標(biāo)對駕駛?cè)说南鄬χ匾?，從而建立相?yīng)的模糊矩陣。F=（QNxN（8）評價指標(biāo)a比、相對重要評價指標(biāo)a比a同樣重要（9）評價指標(biāo)a?比aj相對重要對模糊矩陣F進(jìn)行一致化處理，構(gòu)成模糊一致矩陣口，即R=（rr）其中：r=r^r1-+05r=/f（10）ij 2N 1i1=1然后基于模糊一致矩陣進(jìn)行指標(biāo)權(quán)重的確定，即得：10.5（ii）1=1按下式進(jìn)行歸一化：w=（,W={w,w,,w}（12）i寸l 1 2Nii=1???從而可得到路徑指標(biāo)權(quán)重向量亞。至此最優(yōu)路徑模型建立完畢。第二問：根據(jù)第一問的定義，假設(shè)已知每條路段行駛時間的均值和標(biāo)準(zhǔn)差，設(shè)計算法搜索最優(yōu)路徑，并將該算法應(yīng)用到具體的交通網(wǎng)絡(luò)中,用計算結(jié)果驗證算法的有效性。如果可能的話，從理論上分析算法的收斂性、復(fù)雜性等性質(zhì)。答：我們針對現(xiàn)實生活中的路網(wǎng)信息不確定性，利用多屬性的決策方法對所有可行路徑進(jìn)行綜合評估排序，以求得最優(yōu)路徑。我們根據(jù)第一問的結(jié)論，現(xiàn)在將一個復(fù)雜的交通網(wǎng)絡(luò)分為若干段，基于蟻群算法進(jìn)行動態(tài)路徑選擇。1蟻群算法原理生物世界中的螞蟻在覓食時可以在沒有任何可見提示的情況下找出蟻穴到食物源最短路徑，并且隨環(huán)境變化及時搜索新的最短路徑。研究發(fā)現(xiàn)，這是因為螞蟻能夠在其走過的路徑上分泌一種稱作信息素的揮發(fā)性化學(xué)物質(zhì)，通過這種方式形成信息素軌跡。螞蟻在尋徑時能感知信息素的存在及其強(qiáng)度，并以此直到自己的運動方向。信息素的強(qiáng)度越高，螞蟻選擇該方向的概率越大。假設(shè)存在4、8兩條路徑，在不考慮信息素?fù)]發(fā)的情況下，當(dāng)口只螞蟻經(jīng)過兩條路后，第印+1只螞蟻選擇人路徑概率為P(m)=T-~~Sm+27、，a(A+k)h+(B+k)h選擇8路徑的概率為P(m)=1-P(m)。式中?？诤?m分別為經(jīng)過4、8路徑的螞蟻數(shù)，A+8二m山和卜為匹配參數(shù),根據(jù)6。55等人的雙橋?qū)嶒?h。2,k-20omm對于一條路徑來說,選擇它的螞蟻越多,則該路徑上的信息素強(qiáng)度就越大,從而吸引更多的螞蟻,形成一種正反饋。螞蟻正是通過這種正反饋最終發(fā)現(xiàn)最短路徑的。受螞蟻集體覓食行為的啟發(fā)，意大利學(xué)者口。例。于1991年首次提出了蟻群算法。目前該算法已經(jīng)廣泛應(yīng)用于各個領(lǐng)域,并取得了較好的效果。本文將著重探討蟻群算法在動態(tài)誘導(dǎo)方面的具體應(yīng)用。2基于螞蟻尋徑原理的路網(wǎng)模型將經(jīng)濟(jì)圈公路網(wǎng)中的公路交匯處和樞紐抽象為節(jié)點,公路(包括高速公路、國道、省道等等)抽象為路徑,公路網(wǎng)中的車輛駕駛員對應(yīng)成一只只螞蟻,就可以將經(jīng)濟(jì)圈公路網(wǎng)中的動態(tài)路徑選擇問題和螞蟻尋徑問題聯(lián)系起來。那么駕駛員卜在節(jié)點i選擇相鄰節(jié)點j的轉(zhuǎn)移概率為pG.)_[兀0j*x[M；j邛x[“i,j外 ⑴上前d*x[M；d邛豆山,d不dgL(i)式中：n(i,j)為路段(i,j)的“信息素”；L(i)為與節(jié)點i相鄰的所有節(jié)點的集合；人j)=1,C(i,j)為路段(i,j)的路機(jī)可以取C(i,j)作路段長度,也可取作行駛費用成本，還可取作行駛時間；武i,j)為路段(i,j)上的車輛平均速度,反映了路段的飽和度,即已有交通量和設(shè)計交通量的比值，路段飽和度越高，車輛的平均速度就越小?？梢姡范蔚穆窓?quán)大小、飽和度與駕駛員選擇該路段的概率成反比。。、6和口為啟發(fā)式因子，分別反應(yīng)信息素、路段權(quán)重和路段飽和度在路徑選擇時的相對重要程匣可根據(jù)具體情況確定。另外需要為每個駕駛員設(shè)計一個禁忌表，記錄駕駛員k已走過的節(jié)點，不允許駕駛員在單次行程中重復(fù)經(jīng)過這些節(jié)點。信息素",j)的刷新規(guī)則有局部刷新規(guī)則和全局刷新規(guī)-則兩種。局部刷新規(guī)則是指每一個駕駛員每經(jīng)過一個路段便及時更新該路段的信息素強(qiáng)度。當(dāng)駕駛員k經(jīng)過路段(i,j)后，該路段(i,j)的信息素強(qiáng)度刷新公式為兀(i,j)—(1—p)兀(i,j)+OAkk(i,j) (2)式中：「為信息素?fù)]發(fā)度,在。1口圍內(nèi)取值；0為可調(diào)參數(shù),根據(jù)取值路段的交通狀況特征,如高峰時間和非高峰時間、公路的等級而有所不同。在公式A兀k(i,j)=1中一(i,j)為路段的行程時間。當(dāng)行程時t(i,j)間t(i,j紜 0『、、時潞段(i,j)的信息素則完全處于揮發(fā)狀態(tài),此時px兀(i,j)信息素不再增加,而是隨/(i,j)的增加而減小。全局刷新規(guī)則是指駕駛員到達(dá)目的節(jié)點時,再更新公路網(wǎng)中所有路段的信息素強(qiáng)度。設(shè)駕駛員k從源節(jié)點到目的節(jié)點經(jīng)過的路徑為5,則可將所有路段的信息素強(qiáng)度公式刷新為(3)(1—p)兀(i,j)+OAkk(i,j),(i,j)es(3)(1—p)兀(i,j),(i,j)免s式中：A兀k(i,j)=^Vminl,V為路徑$上的瓶頸路段平均車速,即Lmin路徑5上所有路段平均車速的最小值，VV],les；L為路徑$的全長;0為可調(diào)參數(shù),取決于路段的交通狀■特征；。為瓶頸路段車速對信息素強(qiáng)度的影響程度。全局刷新公式中引入了瓶頸路段平均車速作為參考指標(biāo),這樣可以為瓶頸車流速大的路徑分配較強(qiáng)的信息素,從而誘導(dǎo)駕駛員在通暢的路徑上通行。另外模擬信息素的揮發(fā)也使得選擇次數(shù)多的路徑要比較少選擇的路徑信息素要強(qiáng)。兩種刷新規(guī)則的不同在于反饋信息類型的不同,全局刷新規(guī)則使用的是全局信息,刷新時迭加的信息素大小取決于生成解的優(yōu)劣程度,駕駛員選擇的路徑越短、瓶頸路段平均速度越快,那么這條路徑上所貢獻(xiàn)的信息素量就越多。而局部刷新規(guī)則使用的是局部信息,在搜索過程中不受解的優(yōu)劣度影響，其啟發(fā)信息n(i,j)只是Hi,j)的增強(qiáng),而在全局刷新規(guī)則中兀(i,j)代表了一個與Mi,j)完全不同的信息類型。由此可見全局刷新規(guī)則明顯優(yōu)于局部刷新規(guī)則,不僅可以更精確地尋求最優(yōu)路徑,更能大大減少迭代次數(shù)。參數(shù)取值蟻群算法與其它模擬進(jìn)化算法一樣,存在著收斂速度慢、易陷入局部最優(yōu)等缺陷。而模型中各參數(shù)的取值更直接關(guān)系到算法的收斂速度和全局搜索能力。信息素?fù)]發(fā)度「是算法最關(guān)鍵的參數(shù)之一，若「過大,在處理較大的交通網(wǎng)絡(luò)問題時,一些未被選擇的路徑信息素含量可能很快就會降低到趨近于0,而有被選擇的路徑則被選擇的可能性會增大很多，因而降低了算法的全局搜索能力；若「過小，雖然算法的全局搜索能力提高了,但是算法的收斂速度將會降低,算法的迭代次數(shù)會大大增加。通過計算機(jī)的仿真實驗分析ant-cyclesystem模型,將啟發(fā)式因子和路段信息素初始值均取為1,運算停止條件為相鄰的兩次循環(huán)搜索中最優(yōu)解的差別小于。001。由實驗結(jié)果可知「值在0.3~0.5X圍內(nèi)時,算法的搜索效率和收斂速度會比較好。針對動態(tài)路徑選擇問題的實際要求,應(yīng)該首先考慮算法的穩(wěn)定性和最優(yōu)解的全局性,其次才是其收斂速度,因此,「取0.3為宜。啟發(fā)式因子。反映了駕駛員在運動過程中殘留信息量在路徑選擇中的相對重要程度抱的大小反映了路徑選擇時隨機(jī)性因素作用的強(qiáng)度,其值越大,駕駛員選擇曾經(jīng)走過的路徑的可能性也就越大,搜索的隨機(jī)性減弱,可見a值過大容易使路徑搜索過早限于局部最優(yōu)。啟發(fā)式因子口反映了路段的權(quán)重(距離、費用、行駛時間等)在路徑選擇中的相對重要程度加的大小反映了路徑選擇時確定性因素作用的強(qiáng)度,其值越大,駕駛員在某個局部點上選擇局部最短路徑的可能性越大,盡管搜索的收斂速度加快,但隨機(jī)性減弱,也很容易陷入局部最優(yōu)解。啟發(fā)式因子口反映了路段實時飽和度在路徑選擇中相對重要程度小的大小反映了實時性因素作用的強(qiáng)度，其值越大,駕駛員選擇服務(wù)水平高的路段的可能性就越大,搜索的實時變動性加大，增加了全局最優(yōu)解的不確定性,可見口值過大會使算法的收斂性能大大降低。3個啟發(fā)式因子既相關(guān)又矛盾,對算法性能的影響很大。通過對上述路網(wǎng)模型的仿真實驗,當(dāng)取「=0.3時，實驗結(jié)果表明。的最優(yōu)值在1左右,而6和口在2~5之間最優(yōu)。動態(tài)路徑選擇的步驟描述假設(shè)經(jīng)濟(jì)圈公路網(wǎng)中的每個節(jié)點都安設(shè)有一臺專門的交通信息服務(wù)器,并配有刷新保存該節(jié)點相鄰各路段的信息素表。當(dāng)駕駛員在節(jié)點s發(fā)出一個目的節(jié)點6為路徑選擇申請(該申請有可能附帶車速、行程時間、費用等限制條件)時,首先使用初始化的信息素值來初始化公路網(wǎng)中每個節(jié)點的信息素表。然后開始按以下步驟進(jìn)行動態(tài)路徑選擇。第一步:選取!^位駕駛員，設(shè)其起始節(jié)點為5,目的節(jié)點為6,將從節(jié)點s周期性啟程的駕駛員進(jìn)行分組,并設(shè)啟程的時間周期遠(yuǎn)遠(yuǎn)小于行程時間。第二步:設(shè)第卜位駕駛員到達(dá)了節(jié)點i,iNe。則根據(jù)節(jié)點》的信息素表中的最大概率值來選擇下一個節(jié)點j,pk(i,j)=maxPk(i,j),jeL(i),P&j)計算公式見公式⑴,依次提取,從而得到路徑5※…※t。第三步:利用全局刷新公式