2/22不確定性條件下的最優(yōu)路徑問(wèn)題摘要本文針對(duì)現(xiàn)實(shí)生活中的交通網(wǎng)絡(luò)，綜合各種影響因素，建立不確定條件下的最優(yōu)路徑選擇模型。首先，本文改變傳統(tǒng)路徑最短算法的思路，以尋求行駛時(shí)間最短為目標(biāo)，綜合考慮不確定因素，通過(guò)線性回歸分析，建立了基本的各路段行駛時(shí)間與路段平均行駛時(shí)間、行程時(shí)間標(biāo)準(zhǔn)差、行程緊急程度、動(dòng)態(tài)交通變化量之間的模型。得出不確定條件下車輛從起點(diǎn)到終點(diǎn)最優(yōu)路徑的定義和數(shù)學(xué)表達(dá)式，并將此模型運(yùn)用于第一問(wèn)示例，得出結(jié)論。。。。其次，在已知每條路徑行駛時(shí)間均值與標(biāo)準(zhǔn)差的條件下，借助蟻群算法在實(shí)際交通網(wǎng)絡(luò)中尋找最優(yōu)路徑。接著，考慮到道路擁擠情況，利用道路阻抗排隊(duì)論的結(jié)論在原有模型基礎(chǔ)上進(jìn)行改進(jìn)，建立新的模型并應(yīng)用于交通網(wǎng)絡(luò)最優(yōu)路徑的搜索。最后，對(duì)現(xiàn)實(shí)網(wǎng)絡(luò)的重新分析，綜合其他不確定因素完善現(xiàn)有模型。關(guān)鍵詞：回歸分析蟻群算法排隊(duì)論一、問(wèn)題重述目前，交通擁擠和事故正越來(lái)越嚴(yán)重的困擾著城市交通。隨著我國(guó)交通運(yùn)輸事業(yè)的迅速發(fā)展，交通“擁塞”已經(jīng)成為很多城市的“痼疾”。在復(fù)雜的交通環(huán)境下，如何尋找一條可靠、快速、安全的最優(yōu)路徑，已經(jīng)成為所有駕駛員的共識(shí)。傳統(tǒng)的最優(yōu)路徑問(wèn)題的研究大多數(shù)是基于“理想”的交通狀況下分析的，即：假設(shè)每條路段上的行駛時(shí)間是確定的。在這種情況下，最優(yōu)路徑就是行駛時(shí)間最短的路徑，可以用經(jīng)典的最短路徑算法來(lái)搜索(例如Dijkstra最短路徑算法)。目前的車輛路徑導(dǎo)航系統(tǒng)也大都是基于這種理想的狀況下的最優(yōu)路徑算法，尋找行駛時(shí)間最短的路徑。事實(shí)上，由于在現(xiàn)實(shí)生活中，會(huì)受到很多不確定性因素的影響，例如：交通事故、惡劣天氣、突發(fā)事件等，車輛的行駛時(shí)間存在著不確定性。第一問(wèn)：如圖1所示的交通網(wǎng)絡(luò)，起點(diǎn)：中國(guó)礦業(yè)大學(xué)，終點(diǎn)：徐州火車站。假設(shè)車輛的行駛時(shí)間是隨機(jī)變量。如果走繞城快速路，平均33分鐘到達(dá)，雖然路程遠(yuǎn)，但是很少發(fā)生堵車，所以行駛時(shí)間的波動(dòng)很小，標(biāo)準(zhǔn)差只有1分鐘；如果走市區(qū)道路，平均30分鐘到達(dá)，雖然路程近，但是市區(qū)經(jīng)常發(fā)生堵車，所以行駛時(shí)間的波動(dòng)很大，標(biāo)準(zhǔn)差高達(dá)15分鐘。如果用傳統(tǒng)的最優(yōu)路徑算法，應(yīng)該選市區(qū)道路，因?yàn)槠骄鶗r(shí)間短。在現(xiàn)實(shí)中，為了準(zhǔn)時(shí)到達(dá)目的地，駕駛員通常會(huì)選擇路程稍遠(yuǎn)的繞城快速路。起點(diǎn)起點(diǎn)終點(diǎn)市區(qū)道路均值30分鐘，標(biāo)準(zhǔn)差15分鐘中國(guó)礦業(yè)大學(xué)徐州火車站繞城快速路均值33分鐘，標(biāo)準(zhǔn)差1分鐘圖1.示例交通網(wǎng)絡(luò)對(duì)于一般的交通網(wǎng)絡(luò)，假設(shè)已知每條路段行駛時(shí)間的均值和標(biāo)準(zhǔn)差，請(qǐng)建立數(shù)學(xué)模型，定量的分析車輛行駛時(shí)間的不確定性，然后給出在不確定性條件下車輛從起點(diǎn)到終點(diǎn)的最優(yōu)路徑的定義和數(shù)學(xué)表達(dá)式，將此模型應(yīng)用到圖1的例子中會(huì)選擇哪條道路。提示：(1)傳統(tǒng)的最優(yōu)路徑可以看成是平均行駛時(shí)間最短的路徑，本題中的最優(yōu)路徑不僅要考慮平均行駛時(shí)間，而且還要考慮不確定性條件下車輛準(zhǔn)時(shí)到達(dá)終點(diǎn)的可靠性等因素;(2)假設(shè)車輛在每條路段上的行駛時(shí)間是隨機(jī)變量，這里的“路段”相當(dāng)于網(wǎng)絡(luò)圖中的“邊”。第二問(wèn)：根據(jù)第一問(wèn)的定義，假設(shè)已知每條路段行駛時(shí)間的均值和標(biāo)準(zhǔn)差，設(shè)計(jì)算法搜索最優(yōu)路徑，并將該算法應(yīng)用到具體的交通網(wǎng)絡(luò)中，用計(jì)算結(jié)果驗(yàn)證算法的有效性。如果可能的話，從理論上分析算法的收斂性、復(fù)雜性等性質(zhì)。第三問(wèn)：在現(xiàn)實(shí)的交通網(wǎng)絡(luò)中，某個(gè)路段發(fā)生了交通擁堵，對(duì)上游或者下游路段的交通狀況有很大的影響，從而導(dǎo)致了交通路段之間的行駛時(shí)間有一定的相關(guān)性，這種相關(guān)性情況很復(fù)雜，其中一個(gè)典型的例子如下：下游路段發(fā)生交通擁堵使車輛減速或者排隊(duì)，導(dǎo)致上游路段發(fā)生擁堵。請(qǐng)建立數(shù)學(xué)模型描述這種交通路段之間行駛時(shí)間的相關(guān)性，并將這種相關(guān)性應(yīng)用到第一問(wèn)和第二問(wèn)的最優(yōu)路徑搜索問(wèn)題中，并設(shè)計(jì)算法解決考慮相關(guān)性的最優(yōu)路徑搜索問(wèn)題，給出算例驗(yàn)證算法的有效性。如果可能的話，從理論上分析算法的收斂性、復(fù)雜性等性質(zhì)。提示：這里的相關(guān)性，可以從空間和時(shí)間的兩個(gè)方面考慮。空間相關(guān)性：同一個(gè)時(shí)間段(例如7:00-8:00之間)，路段a和路段b的相關(guān)性。時(shí)間相關(guān)性：對(duì)于路段a，不同時(shí)間段的相關(guān)性，例如7:00-8:00和8:00-9:00之間的相關(guān)性。當(dāng)然，也可以兩種相關(guān)性同時(shí)考慮。第四問(wèn)：從不確定性條件下交通網(wǎng)絡(luò)的實(shí)際情況出發(fā)，在合理假設(shè)下，進(jìn)一步完善前三問(wèn)的數(shù)學(xué)模型和相關(guān)算法?；蛘?，提出一種或多種與前三問(wèn)不同的最優(yōu)路徑的定義方法，建立相關(guān)的數(shù)學(xué)模型并設(shè)計(jì)算法，應(yīng)用數(shù)值算例驗(yàn)證算法的有效性。如果可能的話，從理論上分析算法的收斂性、復(fù)雜性等性質(zhì)。說(shuō)明：本題中的所涉及的算例最好能采用真實(shí)的交通網(wǎng)絡(luò)數(shù)據(jù)，也可以使用自己假設(shè)的數(shù)據(jù)，交通網(wǎng)絡(luò)的規(guī)模越大越好。二、問(wèn)題背景隨著智能交通系統(tǒng)（ITS）的發(fā)展，對(duì)出行者路徑選擇行為的研究也成為各國(guó)學(xué)者關(guān)注的熱點(diǎn)問(wèn)題之一。路徑選擇主要解決的問(wèn)題是：以智能交通系統(tǒng)實(shí)時(shí)提供的路況信息和駕駛者交通需求為輸入，在一定優(yōu)化目標(biāo)下，為駕駛者提供最合理的出行路徑。在傳統(tǒng)路徑選擇方法中，一般是以Dijkstra最短路徑算法為典型，此類算法雖然降低了模型的復(fù)雜度，但是忽略了駕駛者的個(gè)性化需求，誘導(dǎo)系統(tǒng)為不同的人群提供相同的方案，這必然會(huì)在網(wǎng)絡(luò)中產(chǎn)生集聚效應(yīng)，產(chǎn)生擁擠漂移現(xiàn)象，使網(wǎng)絡(luò)交通流量處于失衡狀態(tài)。所以，有必要在多不確定屬性條件下，對(duì)路徑選擇綜合分析。三、基本假設(shè)與符號(hào)說(shuō)明3.1基本假設(shè)1.交通網(wǎng)絡(luò)中的各路段行駛時(shí)間均值與標(biāo)準(zhǔn)差已知。2.本文收集的數(shù)據(jù)真實(shí)可靠。3.忽略駕駛者主觀導(dǎo)致行駛時(shí)間變化的因素。3.2符號(hào)說(shuō)明四、問(wèn)題分析與思路流程4.1問(wèn)題分析首先對(duì)于綜合評(píng)估不確定性因素的建模，我們不止考慮到時(shí)間最短以及時(shí)間的波動(dòng)性（也就是標(biāo)準(zhǔn)差）這兩個(gè)因素，還有另外一些不確定性因素，例如，安全性、舒適性、擁擠程度、車道數(shù)、道路質(zhì)量等級(jí)、行人及非機(jī)動(dòng)車數(shù)量、交通事故率、行程費(fèi)用、沿途景觀等。這些都將作為影響最終時(shí)間的主要因素，注意這些因素是不確定的。從駕駛?cè)说慕嵌瓤紤]，理想最優(yōu)路徑的確定過(guò)程應(yīng)綜合考慮各主要出行影響因素并充分體現(xiàn)駕駛?cè)说闹鲃?dòng)性。所以綜合面向駕駛者的個(gè)性化需求構(gòu)建可行路徑的屬性集即路徑綜合評(píng)價(jià)指標(biāo)體系。利用回歸分析建立行程時(shí)間模型。其次，當(dāng)我們面對(duì)一個(gè)具體的復(fù)雜網(wǎng)絡(luò)時(shí)，解答：此次建模不止考慮到時(shí)間最短以及時(shí)間的波動(dòng)性（也就是標(biāo)準(zhǔn)差）這兩個(gè)因素，還有另外一些不確定性因素，例如，安全性，舒適性，擁擠程度，車道數(shù)，道路質(zhì)量等級(jí)，行人及非機(jī)動(dòng)車數(shù)量，交通事故率，行程費(fèi)用，沿途景觀等。這些都將作為影響最終時(shí)間的主要因素，注意這些因素是不確定的。從駕駛?cè)说慕嵌瓤紤]，理想最優(yōu)路徑的確定過(guò)程應(yīng)綜合考慮各主要出行影響因素并充分體現(xiàn)駕駛?cè)说闹鲃?dòng)性。本文綜合面向駕駛?cè)说膫€(gè)性化需求，構(gòu)建可行路徑的屬性集即路徑綜合評(píng)價(jià)指標(biāo)體系如下：（1）式中為行程平均時(shí)間，注意此行程平均時(shí)間僅僅是在不考慮人的主觀性所得出的平均值，以時(shí)間最短為主要目標(biāo);為行程時(shí)間標(biāo)準(zhǔn)差，衡量在沒(méi)有其他因素影響下的偏離行程平均時(shí)間的程度；為當(dāng)前行程目標(biāo)緊急程度評(píng)價(jià)項(xiàng)用以衡量駕駛?cè)说木o急程度；為動(dòng)態(tài)路段交通變化量用以衡量較理想平均路段交通的偏離程度，例如突然發(fā)生較大堵塞等狀況。為行程距離;為行程舒適度,是考慮可行路徑各路段的擁擠程度,車道數(shù)，道路質(zhì)量等級(jí),行人及非機(jī)動(dòng)車數(shù)量等因素而所得的綜合評(píng)價(jià)值;為安全度,是考慮可行路徑各路段交通事故率的綜合評(píng)價(jià)值;為行程費(fèi)用，主要考慮路段收費(fèi)和油耗?？梢?jiàn)上述，，，皆是影響最終行程時(shí)間的相關(guān)因素，只是各因素在所占權(quán)重上會(huì)不一樣。而另外的因素是影響駕駛員主觀原則的因素。總之，以上因素皆是評(píng)價(jià)最短路徑的主要因素。由以上說(shuō)明可知，最終行程時(shí)間x=x(，，，),假設(shè)最終行程時(shí)間函數(shù)是關(guān)于四個(gè)主要變量的線性函數(shù)，另外根據(jù)以上分析我們知道在不考慮除以外的因素時(shí)，x=,如此我們利用基準(zhǔn)值T=的增量形式來(lái)表達(dá)關(guān)于最終時(shí)間函數(shù)的表達(dá)式。要求x=x(，，，)的表達(dá)式，也就是x=T（1+），我們可以將叫做偏差量，相應(yīng)的叫做相應(yīng)比重。具體分析計(jì)算如下：對(duì)于，由于它是由標(biāo)準(zhǔn)差引起的，也就說(shuō)與平均值之間的偏差，假設(shè)行程時(shí)間變量服從正態(tài)分布，那么我們理所當(dāng)然的認(rèn)為服從標(biāo)準(zhǔn)正態(tài)分布，所以可以將當(dāng)做一個(gè)區(qū)間數(shù)，由概率論的相關(guān)知識(shí)，我們可以只考慮偏差概率大的部分，即；對(duì)于，由于它是由即當(dāng)前行程目標(biāo)緊急程度評(píng)價(jià)項(xiàng)用以衡量駕駛?cè)说木o急程度所決定，我們可以用離散值來(lái)標(biāo)定相應(yīng)緊急程度，當(dāng)然程度越急，相應(yīng)時(shí)間也就會(huì)減得越少。如此我們可以用：，其中駕駛員很急，則對(duì)應(yīng)，駕駛員一點(diǎn)都不急對(duì)應(yīng)，在這之間對(duì)應(yīng)0。為了簡(jiǎn)便分析，我們只分這三種等級(jí)，很明顯的可以看出這種取值是符合實(shí)際的。對(duì)于，為動(dòng)態(tài)路段交通變化量用以衡量較理想平均路段交通的偏離程度，我們仿照來(lái)規(guī)定取值，，其中對(duì)應(yīng)較我們所建立的理想時(shí)間時(shí)的路段交通堵塞狀況要輕得多，則對(duì)應(yīng)較之重的情形了，在這之間是0，也就是相差不多的情況。對(duì)于，則依實(shí)際而定。如此最終行程時(shí)間函數(shù)模型建立。之后是關(guān)于最短路徑的評(píng)價(jià)標(biāo)準(zhǔn)，兼顧x,等因素來(lái)做相應(yīng)的綜合評(píng)價(jià)。在不確定性條件下車輛從起點(diǎn)到終點(diǎn)的最優(yōu)路徑的定義如下，關(guān)于綜合評(píng)價(jià)的最小值所對(duì)應(yīng)的路徑即為最優(yōu)路徑。以下是關(guān)于綜合評(píng)價(jià)的模型：建模所需要的理論模型是不確定型多屬性決策方法模型：多屬性決策是決策理論研究的重要內(nèi)容,現(xiàn)已被廣泛應(yīng)用于項(xiàng)目評(píng)估、方案優(yōu)選、效益綜合評(píng)價(jià)等諸多領(lǐng)域。對(duì)于智能交通系統(tǒng)研究中的路徑選擇問(wèn)題，交通路網(wǎng)信息本身就存在較大的動(dòng)態(tài)性和隨機(jī)性，諸多路徑評(píng)價(jià)指標(biāo)只能通過(guò)測(cè)算、建模來(lái)給出當(dāng)前交通狀態(tài)下的估計(jì)值，與真實(shí)值相比存在誤差，簡(jiǎn)單將其忽略有可能導(dǎo)致路徑選擇結(jié)果的不合理性，同時(shí)駕駛?cè)俗鳛閱我粋€(gè)體，由于其性格、愛(ài)好、駕駛熟練程度的不同，對(duì)路徑選擇具有一定的偏好性。而且這種偏好本身具有模糊性，難以量化，因此本文基于不確定型多屬性決策方法研究動(dòng)態(tài)路徑選擇問(wèn)題，具有較強(qiáng)的實(shí)際應(yīng)用背景。對(duì)于不確定型多屬性決策問(wèn)題，設(shè)可行方案集為，屬性集為,各屬性對(duì)應(yīng)的權(quán)重向量為，屬性權(quán)重滿足，且對(duì)于任意的，有。設(shè)為可行方案關(guān)于屬性的取值區(qū)間，則決策矩陣為：A=(2)考慮到屬性類型有效益型(屬性值越大越好型)和成本型（屬性值越小越好型），為了消除不同物理量綱對(duì)決策結(jié)果的影響，需要將決策矩陣A化為規(guī)范化矩陣。根據(jù)區(qū)間數(shù)的運(yùn)算法則，對(duì)于效益型和成本型，轉(zhuǎn)換公式分別為式（3），（4）：（3）（4）由于多屬性決策的本質(zhì)是對(duì)各方案綜合屬性值的排序比較，針對(duì)規(guī)范化決策矩陣，假定各屬性的權(quán)重向量W已確定，則方案的綜合屬性值為：（5）由于仍是區(qū)間數(shù)，為了能對(duì)方案進(jìn)行排序，需定義區(qū)間數(shù)之間兩兩比較的可能度概念。以下是相關(guān)可能度概念的定義：當(dāng)a和b之間至少有一個(gè)是區(qū)間數(shù)時(shí)，設(shè)，，記，，則稱為的可能度，且（6）基于各方案之間的可能度，令,建立各方案的可能度互補(bǔ)矩陣P,對(duì)于互補(bǔ)判斷矩陣，相關(guān)文獻(xiàn)里給出了互補(bǔ)判斷矩陣的排序向量的一個(gè)計(jì)算公式：(7)按其分量大小對(duì)方案進(jìn)行排序即可得到最優(yōu)方案。以上是關(guān)于我們建立綜合評(píng)價(jià)體系所要用到的理論模型，之后將它與我們所要解決的實(shí)際問(wèn)題結(jié)合起來(lái)?；氐浇獯饎傞_(kāi)始的地方，我們建立了8個(gè)主要因素，其中前4個(gè)主要因素導(dǎo)出了行程時(shí)間這個(gè)主要因素，所以最終我們建立了5個(gè)主要因素。按照理論模型中對(duì)應(yīng)的說(shuō)法是我們建立了5個(gè)屬性，即：令，如此我們就建立了相應(yīng)的屬性集。需要說(shuō)明的是，為綜合評(píng)價(jià)的方便，需將不同物理意義的各種評(píng)價(jià)指標(biāo)轉(zhuǎn)換為[0,1]區(qū)間的量綱為1的滿意度評(píng)價(jià)指標(biāo)，本文同意將其轉(zhuǎn)化為成本型（設(shè)計(jì)指標(biāo)越小越好型）；同時(shí)，由于在實(shí)際中客觀交通路況的動(dòng)態(tài)變化和主觀個(gè)性票號(hào)的改變，路徑評(píng)價(jià)指標(biāo)值具有一定的隨機(jī)性，可以表示為區(qū)間數(shù)形式，即：以下是關(guān)于一開(kāi)始所說(shuō)的指標(biāo)權(quán)重的確定：在一般情況下，出行者會(huì)根據(jù)個(gè)人經(jīng)驗(yàn)喜好或習(xí)慣去選擇路徑，對(duì)指標(biāo)權(quán)重的確定反映了駕駛?cè)说膫€(gè)性化需求，但個(gè)性化偏好往往具有復(fù)雜性和模糊性，用模糊數(shù)表示判斷的結(jié)果能夠更好反映事物的客觀本質(zhì)。因此，本文將駕駛?cè)说膫€(gè)性化需求引入指標(biāo)權(quán)重確定過(guò)程，基于模糊數(shù)學(xué)理論進(jìn)行指標(biāo)權(quán)重的個(gè)性化確定，相比一般方法，模糊分析法簡(jiǎn)化了駕駛?cè)伺袛嗦窂皆u(píng)價(jià)指標(biāo)相對(duì)重要性的復(fù)雜程度，解決了可行路徑優(yōu)化排序過(guò)程中的一致性問(wèn)題。模糊分析法的基本過(guò)程是以矩陣形式表達(dá)各路徑評(píng)價(jià)指標(biāo)對(duì)駕駛?cè)说南鄬?duì)重要性，從而建立相應(yīng)的模糊矩陣。（8）評(píng)價(jià)指標(biāo)比相對(duì)重要評(píng)價(jià)指標(biāo)比同樣重要（9）評(píng)價(jià)指標(biāo)比相對(duì)重要

對(duì)模糊矩陣F進(jìn)行一致化處理，構(gòu)成模糊一致矩陣R，即其中：（10）然后基于模糊一致矩陣進(jìn)行指標(biāo)權(quán)重的確定，即得：（11）按下式進(jìn)行歸一化：（12）從而可得到路徑指標(biāo)權(quán)重向量W。至此最優(yōu)路徑模型建立完畢。第二問(wèn)：根據(jù)第一問(wèn)的定義，假設(shè)已知每條路段行駛時(shí)間的均值和標(biāo)準(zhǔn)差，設(shè)計(jì)算法搜索最優(yōu)路徑，并將該算法應(yīng)用到具體的交通網(wǎng)絡(luò)中，用計(jì)算結(jié)果驗(yàn)證算法的有效性。如果可能的話，從理論上分析算法的收斂性、復(fù)雜性等性質(zhì)。答：我們針對(duì)現(xiàn)實(shí)生活中的路網(wǎng)信息不確定性，利用多屬性的決策方法對(duì)所有可行路徑進(jìn)行綜合評(píng)估排序，以求得最優(yōu)路徑。我們根據(jù)第一問(wèn)的結(jié)論，現(xiàn)在將一個(gè)復(fù)雜的交通網(wǎng)絡(luò)分為若干段，基于蟻群算法進(jìn)行動(dòng)態(tài)路徑選擇。蟻群算法原理生物世界中的螞蟻在覓食時(shí)可以在沒(méi)有任何可見(jiàn)提示的情況下找出蟻穴到食物源最短路徑，并且隨環(huán)境變化及時(shí)搜索新的最短路徑。研究發(fā)現(xiàn)，這是因?yàn)槲浵伳軌蛟谄渥哌^(guò)的路徑上分泌一種稱作信息素的揮發(fā)性化學(xué)物質(zhì)，通過(guò)這種方式形成信息素軌跡。螞蟻在尋徑時(shí)能感知信息素的存在及其強(qiáng)度，并以此直到自己的運(yùn)動(dòng)方向。信息素的強(qiáng)度越高，螞蟻選擇該方向的概率越大。假設(shè)存在A、B兩條路徑，在不考慮信息素?fù)]發(fā)的情況下，當(dāng)m只螞蟻經(jīng)過(guò)兩條路后，第m+1只螞蟻選擇A路徑概率為，選擇B路徑的概率為。式中:Am和Bm分別為經(jīng)過(guò)A、B路徑的螞蟻數(shù),;h和k為匹配參數(shù),根據(jù)Goss等人的雙橋?qū)嶒?yàn),h≈2,k≈20。對(duì)于一條路徑來(lái)說(shuō),選擇它的螞蟻越多,則該路徑上的信息素強(qiáng)度就越大,從而吸引更多的螞蟻,形成一種正反饋。螞蟻正是通過(guò)這種正反饋?zhàn)罱K發(fā)現(xiàn)最短路徑的。受螞蟻集體覓食行為的啟發(fā),意大利學(xué)者Dorigo于1991年首次提出了蟻群算法。目前該算法已經(jīng)廣泛應(yīng)用于各個(gè)領(lǐng)域,并取得了較好的效果。本文將著重探討蟻群算法在動(dòng)態(tài)誘導(dǎo)方面的具體應(yīng)用?；谖浵亴皆淼穆肪W(wǎng)模型將經(jīng)濟(jì)圈公路網(wǎng)中的公路交匯處和樞紐抽象為節(jié)點(diǎn),公路(包括高速公路、國(guó)道、省道等等)抽象為路徑,公路網(wǎng)中的車輛駕駛員對(duì)應(yīng)成一只只螞蟻,就可以將經(jīng)濟(jì)圈公路網(wǎng)中的動(dòng)態(tài)路徑選擇問(wèn)題和螞蟻尋徑問(wèn)題聯(lián)系起來(lái)。那么駕駛員k在節(jié)點(diǎn)i選擇相鄰節(jié)點(diǎn)j的轉(zhuǎn)移概率為(1)式中:為路段的“信息素”;為與節(jié)點(diǎn)i相鄰的所有節(jié)點(diǎn)的集合;,為路段的路權(quán),可以取作路段長(zhǎng)度,也可取作行駛費(fèi)用成本,還可取作行駛時(shí)間;為路段上的車輛平均速度,反映了路段的飽和度,即已有交通量和設(shè)計(jì)交通量的比值,路段飽和度越高,車輛的平均速度就越小?？梢?jiàn),路段的路權(quán)大小、飽和度與駕駛員選擇該路段的概率成反比。α、β和η為啟發(fā)式因子,分別反應(yīng)信息素、路段權(quán)重和路段飽和度在路徑選擇時(shí)的相對(duì)重要程度,可根據(jù)具體情況確定。另外需要為每個(gè)駕駛員設(shè)計(jì)一個(gè)禁忌表,記錄駕駛員k已走過(guò)的節(jié)點(diǎn),不允許駕駛員在單次行程中重復(fù)經(jīng)過(guò)這些節(jié)點(diǎn)。信息素的刷新規(guī)則有局部刷新規(guī)則和全局刷新規(guī)-則兩種。局部刷新規(guī)則是指每一個(gè)駕駛員每經(jīng)過(guò)一個(gè)路段便及時(shí)更新該路段的信息素強(qiáng)度。當(dāng)駕駛員k經(jīng)過(guò)路段后,該路段的信息素強(qiáng)度刷新公式為(2)式中:ρ為信息素?fù)]發(fā)度,在(0,1)范圍內(nèi)取值;θ為可調(diào)參數(shù),根據(jù)取值路段的交通狀況特征,如高峰時(shí)間和非高峰時(shí)間、公路的等級(jí)而有所不同。在公式中,為路段的行程時(shí)間。當(dāng)行程時(shí)間時(shí),路段的信息素則完全處于揮發(fā)狀態(tài),此時(shí)信息素不再增加,而是隨的增加而減小。全局刷新規(guī)則是指駕駛員到達(dá)目的節(jié)點(diǎn)時(shí),再更新公路網(wǎng)中所有路段的信息素強(qiáng)度。設(shè)駕駛員k從源節(jié)點(diǎn)到目的節(jié)點(diǎn)經(jīng)過(guò)的路徑為s,則可將所有路段的信息素強(qiáng)度公式刷新為(3)式中:,為路徑s上的瓶頸路段平均車速,即路徑s上所有路段平均車速的最小值,,;為路徑s的全長(zhǎng);θ為可調(diào)參數(shù),取決于路段的交通狀況特征;σ為瓶頸路段車速對(duì)信息素強(qiáng)度的影響程度。全局刷新公式中引入了瓶頸路段平均車速作為參考指標(biāo),這樣可以為瓶頸車流速大的路徑分配較強(qiáng)的信息素,從而誘導(dǎo)駕駛員在通暢的路徑上通行。另外模擬信息素的揮發(fā)也使得選擇次數(shù)多的路徑要比較少選擇的路徑信息素要強(qiáng)。兩種刷新規(guī)則的不同在于反饋信息類型的不同,全局刷新規(guī)則使用的是全局信息,刷新時(shí)迭加的信息素大小取決于生成解的優(yōu)劣程度,駕駛員選擇的路徑越短、瓶頸路段平均速度越快,那么這條路徑上所貢獻(xiàn)的信息素量就越多。而局部刷新規(guī)則使用的是局部信息,在搜索過(guò)程中不受解的優(yōu)劣度影響,其啟發(fā)信息只是的增強(qiáng),而在全局刷新規(guī)則中代表了一個(gè)與完全不同的信息類型。由此可見(jiàn)全局刷新規(guī)則明顯優(yōu)于局部刷新規(guī)則,不僅可以更精確地尋求最優(yōu)路徑,更能大大減少迭代次數(shù)。3參數(shù)取值蟻群算法與其它模擬進(jìn)化算法一樣,存在著收斂速度慢、易陷入局部最優(yōu)等缺陷。而模型中各參數(shù)的取值更直接關(guān)系到算法的收斂速度和全局搜索能力。信息素?fù)]發(fā)度ρ是算法最關(guān)鍵的參數(shù)之一,若ρ過(guò)大,在處理較大的交通網(wǎng)絡(luò)問(wèn)題時(shí),一些未被選擇的路徑信息素含量可能很快就會(huì)降低到趨近于0,而有被選擇的路徑則被選擇的可能性會(huì)增大很多,因而降低了算法的全局搜索能力;若ρ過(guò)小,雖然算法的全局搜索能力提高了,但是算法的收斂速度將會(huì)降低,算法的迭代次數(shù)會(huì)大大增加。通過(guò)計(jì)算機(jī)的仿真實(shí)驗(yàn)分析ant-cyclesystem模型,將啟發(fā)式因子和路段信息素初始值均取為1,運(yùn)算停止條件為相鄰的兩次循環(huán)搜索中最優(yōu)解的差別小于0.001。由實(shí)驗(yàn)結(jié)果可知ρ值在0.3～0.5范圍內(nèi)時(shí),算法的搜索效率和收斂速度會(huì)比較好。針對(duì)動(dòng)態(tài)路徑選擇問(wèn)題的實(shí)際要求,應(yīng)該首先考慮算法的穩(wěn)定性和最優(yōu)解的全局性,其次才是其收斂速度,因此,ρ取0.3為宜。啟發(fā)式因子α反映了駕駛員在運(yùn)動(dòng)過(guò)程中殘留信息量在路徑選擇中的相對(duì)重要程度,a的大小反映了路徑選擇時(shí)隨機(jī)性因素作用的強(qiáng)度,其值越大,駕駛員選擇曾經(jīng)走過(guò)的路徑的可能性也就越大,搜索的隨機(jī)性減弱,可見(jiàn)α值過(guò)大容易使路徑搜索過(guò)早限于局部最優(yōu)。啟發(fā)式因子β反映了路段的權(quán)重(距離、費(fèi)用、行駛時(shí)間等)在路徑選擇中的相對(duì)重要程度,β的大小反映了路徑選擇時(shí)確定性因素作用的強(qiáng)度,其值越大,駕駛員在某個(gè)局部點(diǎn)上選擇局部最短路徑的可能性越大,盡管搜索的收斂速度加快,但隨機(jī)性減弱,也很容易陷入局部最優(yōu)解。啟發(fā)式因子η反映了路段實(shí)時(shí)飽和度在路徑選擇中相對(duì)重要程度,η的大小反映了實(shí)時(shí)性因素作用的強(qiáng)度,其值越大,駕駛員選擇服務(wù)水平高的路段的可能性就越大,搜索的實(shí)時(shí)變動(dòng)性加大,增加了全局最優(yōu)解的不確定性,可見(jiàn)η值過(guò)大會(huì)使算法的收斂性能大大降低。3個(gè)啟發(fā)式因子既相關(guān)又矛盾,對(duì)算法性能的影響很大。通過(guò)對(duì)上述路網(wǎng)模型的仿真實(shí)驗(yàn),當(dāng)取ρ=0.3時(shí),實(shí)驗(yàn)結(jié)果表明α的最優(yōu)值在1左右,而β和η在2～5之間最優(yōu)。4動(dòng)態(tài)路徑選擇的步驟描述假設(shè)經(jīng)濟(jì)圈公路網(wǎng)中的每個(gè)節(jié)點(diǎn)都安設(shè)有一臺(tái)專門(mén)的交通信息服務(wù)器,并配有刷新保存該節(jié)點(diǎn)相鄰各路段的信息素表。當(dāng)駕駛員在節(jié)點(diǎn)s發(fā)出一個(gè)目的節(jié)點(diǎn)e為路徑選擇申請(qǐng)(該申請(qǐng)有可能附帶車速、行程時(shí)間、費(fèi)用等限制條件)時(shí),首先使用初始化的信息素值來(lái)初始化公路網(wǎng)中每個(gè)節(jié)點(diǎn)的信息素表。然后開(kāi)始按以下步驟進(jìn)行動(dòng)態(tài)路徑選擇。第一步:選取m位駕駛員,設(shè)其