劉長(zhǎng)鶴 邵清亮 李明沂 曹云淏 余冬

摘 要：隨著公路建設(shè)規(guī)模的不斷擴(kuò)大和交通量的不斷增加，汽車碰撞、追尾等交通事故的發(fā)生頻率也隨之增加。因此，在發(fā)生各種事故后，運(yùn)輸部門應(yīng)及時(shí)進(jìn)行任務(wù)分配和應(yīng)急物資運(yùn)輸路線規(guī)劃。針對(duì)蟻群算法在傳統(tǒng)調(diào)度系統(tǒng)中的不足，本文提出的系統(tǒng)通過適當(dāng)改變信息素?fù)]發(fā)因子，加快收斂到染色體最優(yōu)解的速度，建立了蟻群自適應(yīng)優(yōu)化算法，利用優(yōu)化算法求解規(guī)劃模型。結(jié)果表明，該算法的收斂速度和優(yōu)化結(jié)果均優(yōu)于傳統(tǒng)的蟻群算法。

關(guān)鍵詞：智能交通系統(tǒng);蟻群算法;信息素因子;應(yīng)急管理

中圖分類號(hào)：X928 文獻(xiàn)標(biāo)識(shí)碼：A

0 引言

層出不窮的交通事件和不可抗力災(zāi)害是造成交通網(wǎng)絡(luò)各種擁堵的關(guān)鍵原因，將對(duì)城市乃至全國(guó)的經(jīng)濟(jì)建設(shè)和服務(wù)效率造成巨大損失。因此，科學(xué)地運(yùn)用蟻群算法對(duì)城市交通進(jìn)行引導(dǎo)和分類，是有效減少交通事故、災(zāi)害、資源運(yùn)輸?shù)仁录挠行Х椒ā?/p>

交通調(diào)度問題[1]（Traffic Scheduling Problem，TSP）是1959年由Dantzig和Ramser提出。TSP具有較高的實(shí)用性和廣泛的應(yīng)用。但是，TSP沒有使用大規(guī)模的鄰域搜索技術(shù)，對(duì)于多目標(biāo)車輛計(jì)數(shù)調(diào)度，響應(yīng)速度慢，調(diào)度周期長(zhǎng)，容易受到一系列條件的限制。其蟻群算法與動(dòng)態(tài)搜索算法無關(guān)，不具備將動(dòng)態(tài)車輛調(diào)度問題轉(zhuǎn)化為一系列靜態(tài)車輛調(diào)度問題的能力，也不足以達(dá)到有效的收斂速度。本文提出的自適應(yīng)蟻群優(yōu)化算法動(dòng)態(tài)調(diào)整調(diào)度路徑中散發(fā)的信息素，適當(dāng)增大隨機(jī)選擇的概率，進(jìn)一步完善搜索解空間，克服了傳統(tǒng)蟻群算法的缺點(diǎn)，加快了收斂速度。避免給國(guó)民經(jīng)濟(jì)建設(shè)和服務(wù)效率造成巨大損失。因此，科學(xué)地運(yùn)用蟻群算法對(duì)城市交通進(jìn)行引導(dǎo)和分類，是有效減少交通事故、災(zāi)害、資源運(yùn)輸?shù)仁录挠行Х椒ā?/p>

1 傳統(tǒng)蟻群算法

傳統(tǒng)蟻群算法[2]是一種模擬自然界螞蟻搜索路徑的啟發(fā)式算法。該算法不受限于特定的數(shù)學(xué)描述。該算法擁有全局優(yōu)化、高并行性、強(qiáng)魯棒性、短求解時(shí)間、便于計(jì)算機(jī)仿真等優(yōu)點(diǎn)。它包含蟻群算法、最優(yōu)排序蟻群算法、極大值蟻群算法、自適應(yīng)蟻群算法等。

1.1 解空間[3]的構(gòu)建及信息素的初始化和更新

，表示立體網(wǎng)絡(luò)結(jié)構(gòu)中的節(jié)點(diǎn)，表示緊急物資從出發(fā)點(diǎn)輸送到終點(diǎn)的完整路徑。

信息素為，表示螞蟻位于網(wǎng)絡(luò)節(jié)點(diǎn)[4]時(shí)，選擇節(jié)點(diǎn)出發(fā)的第j條路線的期望程度。執(zhí)行迭代前，各路徑信息素初始值，其中為與節(jié)點(diǎn)相連的邊的總數(shù)。設(shè)為信息素的揮發(fā)系數(shù)，0<<1，n為迭代次數(shù)，為本次迭代后的信息素增量，每次迭代后，各條路徑上更新后的信息素更新為：

（1）

目標(biāo)函數(shù)，作為蟻群算法的評(píng)價(jià)函數(shù)，測(cè)定螞蟻構(gòu)建出的解的質(zhì)量，信息素增量，基于下式確定：

（2）

其他 （3）

1.2 選擇策略

螞蟻k從節(jié)點(diǎn)選擇路徑e（i，j）向節(jié)點(diǎn)轉(zhuǎn)移的概率基于下式確定：

（4）

其他 （5）

其中，為螞蟻k下一步允許選擇的城市集合，為啟發(fā)式信息，基于下式確定：

（6）

傳統(tǒng)蟻群算法雖然在整體脈絡(luò)上非常清晰，但是收斂速率仍具有較大的提升空間，我們應(yīng)該做的是改變傳統(tǒng)蟻群算法的信息素的更迭模式。

2 改進(jìn)蟻群算法

在此，我們將改進(jìn)上述傳統(tǒng)的蟻群算法。螞蟻k在運(yùn)動(dòng)過程中，其移動(dòng)方向是由各路徑的信息素分布情況決定的，其中是螞蟻k下一步可選擇的城市;是能見度因數(shù)，常取。反映了螞蟻在運(yùn)動(dòng)過程中信息素的積累，反映了啟發(fā)信息在選擇路徑中的相對(duì)重要程度，為信息啟發(fā)式因子，為期望啟發(fā)式因子。是信息素?fù)]發(fā)因子，（0，1），（t）表示本次循環(huán)中信息素增量，表示第k只螞蟻在這次循環(huán)中存在的信息素。Q表示信息素水平，收斂速度會(huì)受算法的影響，過高會(huì)使局部收斂，過低會(huì)影響收斂速度。表示在本次循環(huán)中路徑的長(zhǎng)度。

，螞蟻k經(jīng)過路徑（i，j）;

=0，螞蟻k不經(jīng)過路徑（i，j） （7）

2.1 構(gòu)造狀態(tài)轉(zhuǎn)移規(guī)則

結(jié)合確定性進(jìn)行選擇，使用隨機(jī)性的策略適當(dāng)?shù)卦黾与S機(jī)選擇概率。更優(yōu)的、更全面的對(duì)解空間進(jìn)行搜索，攻克了傳統(tǒng)蟻群算法的缺點(diǎn)?；诜匠蹋?）（5）確定螞蟻k由i移動(dòng)到j(luò)的狀態(tài)轉(zhuǎn)移概率。q是隨機(jī)數(shù)[0，1]，是參數(shù)，[0，1]，一般在0.80到0.90中取值。螞蟻將選擇下一個(gè)結(jié)點(diǎn)前，根據(jù)上文，由式（8）來選最好的方向，否則按照式（7）來選一個(gè)方向，對(duì)求得的各個(gè)結(jié)點(diǎn)的轉(zhuǎn)移概率進(jìn)行疊加，并與生成的隨機(jī)數(shù)進(jìn)行比較，直到滿足要求，螞蟻才可移動(dòng)到下一個(gè)結(jié)點(diǎn)。

搜索概率 （8）

2.2 信息素更新

（1）保持最佳的解決方案。每次循環(huán)后保持最好的解。

（2）自適應(yīng)性變化。雖然它可以提高算法的全局搜索能力[5]，但也會(huì)降低算法的收斂速度，因此需要對(duì)其進(jìn)行自適應(yīng)的改變。的初始值，當(dāng)該算法得到的最優(yōu)值沒有顯著提高N周期，將如方程（9）所示?？梢苑乐顾惴ǖ氖諗克俣仍黾佑捎谥堤《鴾p少。

（9）

2.3 自適應(yīng)蟻群優(yōu)化算法求解步驟

（1）混沌搜索，生成初始種群，設(shè)計(jì)自適應(yīng)蟻群算法的參數(shù)。

（2）構(gòu)建狀態(tài)轉(zhuǎn)移規(guī)則。

（3）以螞蟻?zhàn)罴崖窂奖闅v所有增加信息素的點(diǎn)。

（4）更新信息素。

（5）滿足條件后，達(dá)到最大迭代次數(shù)或多次生成相同解，以結(jié)束。否則，轉(zhuǎn)到3。

3 多智能體調(diào)度

3.1 多智能體和跨區(qū)域調(diào)度的概念

（1）多智能體是由一系列具有分布性、自主性和協(xié)調(diào)性的相互作用的智能體組成的。內(nèi)部智能體通過相互交流、幫助和競(jìng)賽來完成個(gè)別智能體無法完成的工作，由此可以做到將復(fù)雜問題完成簡(jiǎn)化分解?；诙嘀悄荏w協(xié)作規(guī)則，得到適合系統(tǒng)的應(yīng)急物資調(diào)度任務(wù)。

（2）跨區(qū)域綜合交通應(yīng)急調(diào)度是在突發(fā)事件發(fā)生時(shí)，通過不同區(qū)域、不同部門之間的相互協(xié)調(diào)，提高應(yīng)急資源配置的一種救援策略。有效配置各區(qū)域資源，確?？鐓^(qū)域合作行動(dòng)的快速響應(yīng)，控制事件發(fā)展，減少災(zāi)害損失，對(duì)于促進(jìn)交通資源信息共享，促進(jìn)交通資源的合理配置具有重要意義。

（3）在城市地區(qū)，由于城市規(guī)劃的問題和救援裝備的大型化特點(diǎn)，救援裝備一般不放置在人口密集的中心區(qū)域。同時(shí)，每個(gè)地區(qū)的材料儲(chǔ)存是有限的。一旦需要大量的救災(zāi)物資，當(dāng)?shù)氐奈镔Y將無法滿足需求。此時(shí)應(yīng)考慮跨區(qū)域應(yīng)急救援?？鐓^(qū)域綜合交通應(yīng)急調(diào)度的核心任務(wù)是跨區(qū)域任務(wù)的分配和應(yīng)急物資運(yùn)輸路徑的規(guī)劃。災(zāi)難或事故后，有必要把材料從緊急材料儲(chǔ)備點(diǎn)廣泛分布在全國(guó)各地，充分利用各種運(yùn)輸方式的運(yùn)輸緊急材料的需求點(diǎn)，和任務(wù)需要澄清的類別，流動(dòng)方向，流路徑，運(yùn)輸方式的組合和所需的多式聯(lián)運(yùn)作業(yè)點(diǎn)。

3.2 多智能體的應(yīng)急物資調(diào)度

（1）災(zāi)害發(fā)生后，在鄰近的多個(gè)災(zāi)區(qū)形成一個(gè)大型物資配送中心，每個(gè)大型物資配送中心生成一個(gè)需求點(diǎn)智能體，統(tǒng)計(jì)災(zāi)情和應(yīng)急物資需求信息。救援點(diǎn)對(duì)應(yīng)于一個(gè)個(gè)分布在全國(guó)各地的應(yīng)急物資儲(chǔ)備點(diǎn)。

（2）救援點(diǎn)智能體接收到需求點(diǎn)智能體發(fā)送的救援信息后，根據(jù)綜合路網(wǎng)規(guī)劃的運(yùn)輸路徑，形成包括應(yīng)急物資種類、應(yīng)急物資數(shù)量、應(yīng)急多式聯(lián)運(yùn)路徑等信息的救援方案。并將其發(fā)送給需求點(diǎn)智能體。需求點(diǎn)智能體同意救援點(diǎn)智能體提交的救援方案后，救援點(diǎn)智能體開始執(zhí)行任務(wù)。當(dāng)任務(wù)因各種原因無法完成時(shí)，救援點(diǎn)智能體需要將信息反饋給需求點(diǎn)智能體進(jìn)行動(dòng)態(tài)調(diào)整。

3.3 出救點(diǎn)智能體路徑規(guī)劃

假設(shè)裝貨只在該區(qū)域進(jìn)行，不同區(qū)域之間只進(jìn)行物料運(yùn)輸。構(gòu)建了包含3N+2個(gè)點(diǎn)的智能體運(yùn)輸路徑網(wǎng)絡(luò)。G=（T，e）e是弧集，T是點(diǎn)集。N為沿途起點(diǎn)、終點(diǎn)及可能發(fā)生的應(yīng)急物資轉(zhuǎn)運(yùn)區(qū)域，A為虛擬原點(diǎn);C表示虛擬接收器。A到出發(fā)地和C到目的地的時(shí)間和費(fèi)用為0?；∈敲總€(gè)節(jié)點(diǎn)之間的連接線。弧組可分為運(yùn)輸弧和過渡弧。運(yùn)輸弧表示網(wǎng)絡(luò)結(jié)構(gòu)中的水平連接線;過渡弧表示網(wǎng)絡(luò)結(jié)構(gòu)中節(jié)點(diǎn)間的縱向連接。給出了該節(jié)點(diǎn)物料跨越運(yùn)輸?shù)南嚓P(guān)指標(biāo)，起到了非常重要的作用。

4 結(jié)論

本文對(duì)交通突發(fā)事件進(jìn)行了調(diào)度，并在蟻群算法優(yōu)化領(lǐng)域進(jìn)行了有益的探索和研究，為完善我國(guó)主要城市的交通突發(fā)事件管理系統(tǒng)提供了參考依據(jù)。對(duì)于傳統(tǒng)的蟻群算法，我們對(duì)其信息素代謝進(jìn)行了更深入的分析。經(jīng)過改進(jìn)，得到了一種自適應(yīng)蟻群優(yōu)化算法。從多種途徑中選擇最短、最合理、最經(jīng)濟(jì)的路徑資源，可以達(dá)到安排交通應(yīng)急措施的目的。

參考文獻(xiàn)：

[1]高學(xué)英.大規(guī)模應(yīng)急救援資源布局與調(diào)度優(yōu)化方法研究[D].吉林大學(xué)，2012.

[2]吳啟迪.蟻群算法的研究現(xiàn)狀及應(yīng)用[A].中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集[C].2001（5）：340-344.

[3]張紀(jì)會(huì)，徐心和，胡勇.一種新型模擬進(jìn)化算法—蟻群算法[J].系統(tǒng)工程理論與實(shí)踐，1999（3）：84-87.

[4]劉志碩.基于自適應(yīng)蟻群算法的車輛路徑研究[J].控制與決策，2005（5）：562-566.

[5]李妍峰，李軍，趙達(dá).基于迭代局域搜索的智能優(yōu)化算法求解車輛調(diào)度問題研究[J].系統(tǒng)工程理論與實(shí)踐，2007（5）：75-81.