交通應急調(diào)度系統(tǒng)的蟻群算法優(yōu)化設計

1、 交通應急調(diào)度系統(tǒng)的蟻群算法優(yōu)化設計 劉長鶴 邵清亮 李明沂 曹云淏 余冬摘 要：隨著公路建設規(guī)模的不斷擴大和交通量的不斷增加，汽車碰撞、追尾等交通事故的發(fā)生頻率也隨之增加。因此，在發(fā)生各種事故后，運輸部門應及時進行任務分配和應急物資運輸路線規(guī)劃。針對蟻群算法在傳統(tǒng)調(diào)度系統(tǒng)中的不足，本文提出的系統(tǒng)通過適當改變信息素揮發(fā)因子，加快收斂到染色體最優(yōu)解的速度，建立了蟻群自適應優(yōu)化算法，利用優(yōu)化算法求解規(guī)劃模型。結(jié)果表明，該算法的收斂速度和優(yōu)化結(jié)果均優(yōu)于傳統(tǒng)的蟻群算法。Key：智能交通系統(tǒng);蟻群算法;信息素因子;應急管理：X928 ：A0 引言層出不窮的交通事件和不可抗力災害是造成交通網(wǎng)絡各種擁堵的關

2、鍵原因，將對城市乃至全國的經(jīng)濟建設和服務效率造成巨大損失。因此，科學地運用蟻群算法對城市交通進行引導和分類，是有效減少交通事故、災害、資源運輸?shù)仁录挠行Х椒?。交通調(diào)度問題1（Traffic Scheduling Problem，TSP）是1959年由Dantzig和Ramser提出。TSP具有較高的實用性和廣泛的應用。但是，TSP沒有使用大規(guī)模的鄰域搜索技術，對于多目標車輛計數(shù)調(diào)度，響應速度慢，調(diào)度周期長，容易受到一系列條件的限制。其蟻群算法與動態(tài)搜索算法無關，不具備將動態(tài)車輛調(diào)度問題轉(zhuǎn)化為一系列靜態(tài)車輛調(diào)度問題的能力，也不足以達到有效的收斂速度。本文提出的自適應蟻群優(yōu)化算法動態(tài)調(diào)整調(diào)度路徑

3、中散發(fā)的信息素，適當增大隨機選擇的概率，進一步完善搜索解空間，克服了傳統(tǒng)蟻群算法的缺點，加快了收斂速度。避免給國民經(jīng)濟建設和服務效率造成巨大損失。因此，科學地運用蟻群算法對城市交通進行引導和分類，是有效減少交通事故、災害、資源運輸?shù)仁录挠行Х椒ā? 傳統(tǒng)蟻群算法傳統(tǒng)蟻群算法2是一種模擬自然界螞蟻搜索路徑的啟發(fā)式算法。該算法不受限于特定的數(shù)學描述。該算法擁有全局優(yōu)化、高并行性、強魯棒性、短求解時間、便于計算機仿真等優(yōu)點。它包含蟻群算法、最優(yōu)排序蟻群算法、極大值蟻群算法、自適應蟻群算法等。1.1 解空間3的構(gòu)建及信息素的初始化和更新，表示立體網(wǎng)絡結(jié)構(gòu)中的節(jié)點，表示緊急物資從出發(fā)點輸送到終點的完整

4、路徑。信息素為，表示螞蟻位于網(wǎng)絡節(jié)點4時，選擇節(jié)點出發(fā)的第j條路線的期望程度。執(zhí)行迭代前，各路徑信息素初始值，其中為與節(jié)點相連的邊的總數(shù)。設為信息素的揮發(fā)系數(shù)，01，n為迭代次數(shù)，為本次迭代后的信息素增量，每次迭代后，各條路徑上更新后的信息素更新為：（1）目標函數(shù)，作為蟻群算法的評價函數(shù)，測定螞蟻構(gòu)建出的解的質(zhì)量，信息素增量，基于下式確定：（2）其他 （3）1.2 選擇策略螞蟻k從節(jié)點選擇路徑e（i，j）向節(jié)點轉(zhuǎn)移的概率基于下式確定：（4）其他 （5）其中，為螞蟻k下一步允許選擇的城市集合，為啟發(fā)式信息，基于下式確定：（6）傳統(tǒng)蟻群算法雖然在整體脈絡上非常清晰，但是收斂速率仍具有較大的提升空間

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

6、，j） （7）2.1 構(gòu)造狀態(tài)轉(zhuǎn)移規(guī)則結(jié)合確定性進行選擇，使用隨機性的策略適當?shù)卦黾与S機選擇概率。更優(yōu)的、更全面的對解空間進行搜索，攻克了傳統(tǒng)蟻群算法的缺點?；诜匠蹋?）（5）確定螞蟻k由i移動到j的狀態(tài)轉(zhuǎn)移概率。q是隨機數(shù)0，1，是參數(shù)，0，1，一般在0.80到0.90中取值。螞蟻將選擇下一個結(jié)點前，根據(jù)上文，由式（8）來選最好的方向，否則按照式（7）來選一個方向，對求得的各個結(jié)點的轉(zhuǎn)移概率進行疊加，并與生成的隨機數(shù)進行比較，直到滿足要求，螞蟻才可移動到下一個結(jié)點。搜索概率 （8）2.2 信息素更新（1）保持最佳的解決方案。每次循環(huán)后保持最好的解。（2）自適應性變化。雖然它可以提高算法的全

7、局搜索能力5，但也會降低算法的收斂速度，因此需要對其進行自適應的改變。的初始值，當該算法得到的最優(yōu)值沒有顯著提高N周期，將如方程（9）所示?？梢苑乐顾惴ǖ氖諗克俣仍黾佑捎谥堤《鴾p少。（9）2.3 自適應蟻群優(yōu)化算法求解步驟（1）混沌搜索，生成初始種群，設計自適應蟻群算法的參數(shù)。（2）構(gòu)建狀態(tài)轉(zhuǎn)移規(guī)則。（3）以螞蟻最佳路徑遍歷所有增加信息素的點。（4）更新信息素。（5）滿足條件后，達到最大迭代次數(shù)或多次生成相同解，以結(jié)束。否則，轉(zhuǎn)到3。3 多智能體調(diào)度3.1 多智能體和跨區(qū)域調(diào)度的概念（1）多智能體是由一系列具有分布性、自主性和協(xié)調(diào)性的相互作用的智能體組成的。內(nèi)部智能體通過相互交流、幫助和競賽

8、來完成個別智能體無法完成的工作，由此可以做到將復雜問題完成簡化分解?；诙嘀悄荏w協(xié)作規(guī)則，得到適合系統(tǒng)的應急物資調(diào)度任務。（2）跨區(qū)域綜合交通應急調(diào)度是在突發(fā)事件發(fā)生時，通過不同區(qū)域、不同部門之間的相互協(xié)調(diào)，提高應急資源配置的一種救援策略。有效配置各區(qū)域資源，確保跨區(qū)域合作行動的快速響應，控制事件發(fā)展，減少災害損失，對于促進交通資源信息共享，促進交通資源的合理配置具有重要意義。（3）在城市地區(qū)，由于城市規(guī)劃的問題和救援裝備的大型化特點，救援裝備一般不放置在人口密集的中心區(qū)域。同時，每個地區(qū)的材料儲存是有限的。一旦需要大量的救災物資，當?shù)氐奈镔Y將無法滿足需求。此時應考慮跨區(qū)域應急救援?？鐓^(qū)域綜合

9、交通應急調(diào)度的核心任務是跨區(qū)域任務的分配和應急物資運輸路徑的規(guī)劃。災難或事故后，有必要把材料從緊急材料儲備點廣泛分布在全國各地，充分利用各種運輸方式的運輸緊急材料的需求點，和任務需要澄清的類別，流動方向，流路徑，運輸方式的組合和所需的多式聯(lián)運作業(yè)點。3.2 多智能體的應急物資調(diào)度（1）災害發(fā)生后，在鄰近的多個災區(qū)形成一個大型物資配送中心，每個大型物資配送中心生成一個需求點智能體，統(tǒng)計災情和應急物資需求信息。救援點對應于一個個分布在全國各地的應急物資儲備點。（2）救援點智能體接收到需求點智能體發(fā)送的救援信息后，根據(jù)綜合路網(wǎng)規(guī)劃的運輸路徑，形成包括應急物資種類、應急物資數(shù)量、應急多式聯(lián)運路徑等信息

10、的救援方案。并將其發(fā)送給需求點智能體。需求點智能體同意救援點智能體提交的救援方案后，救援點智能體開始執(zhí)行任務。當任務因各種原因無法完成時，救援點智能體需要將信息反饋給需求點智能體進行動態(tài)調(diào)整。3.3 出救點智能體路徑規(guī)劃假設裝貨只在該區(qū)域進行，不同區(qū)域之間只進行物料運輸。構(gòu)建了包含3N+2個點的智能體運輸路徑網(wǎng)絡。G=（T，e）e是弧集，T是點集。N為沿途起點、終點及可能發(fā)生的應急物資轉(zhuǎn)運區(qū)域，A為虛擬原點;C表示虛擬接收器。A到出發(fā)地和C到目的地的時間和費用為0?；∈敲總€節(jié)點之間的連接線。弧組可分為運輸弧和過渡弧。運輸弧表示網(wǎng)絡結(jié)構(gòu)中的水平連接線;過渡弧表示網(wǎng)絡結(jié)構(gòu)中節(jié)點間的縱向連接。給出了該節(jié)點物料跨越運輸?shù)南嚓P指標，起到了非常重要的作用。4 結(jié)論本文對交通突發(fā)事件進行了調(diào)度，并在蟻群算法優(yōu)化領域進行了有益的探索和研究，為完善我國主要城市的交通突發(fā)事件管理系統(tǒng)提供了參考依據(jù)。對于傳統(tǒng)的蟻群算法，我們對其信息素代謝進行了更深入的分析。經(jīng)過改進，得到了一種自適應蟻群優(yōu)化算法。從多種途徑中選擇最短、最合理、最經(jīng)濟的路徑資源，可以達到安排交通應急措施的目的。Reference：1高學英.大規(guī)模應急救援資源布局與調(diào)度優(yōu)化方法研究D.吉林大學，2012.2吳啟迪.蟻群算法的研究現(xiàn)狀及應用A.中國控制與決策學術年會論文集C.2001（5）：3