交通事故約束下車輛通行最優(yōu)調(diào)度模型仿真

顧 洵，戴 帥

(中國(guó)人民公安大學(xué)交通管理學(xué)院，北京 100038)

1 引言

城市路網(wǎng)多事故應(yīng)急救援中，因交通擁堵造成應(yīng)急車輛滯留現(xiàn)象時(shí)常發(fā)生，嚴(yán)重影響道路交通事故救援效率，尤其近年來，物資運(yùn)輸行業(yè)逐漸壯大，城市中貨物運(yùn)輸車輛逐漸增多。交通事故發(fā)生時(shí)，會(huì)延長(zhǎng)貨物運(yùn)輸時(shí)長(zhǎng)。車輛調(diào)度優(yōu)化由Ramser和Dantzig共同提出，一經(jīng)提出便成為組合優(yōu)化領(lǐng)域和運(yùn)籌學(xué)領(lǐng)域的熱點(diǎn)問題?？茖W(xué)合理的車輛通行調(diào)度不僅能夠降低運(yùn)輸成本，而且可以提升客戶的認(rèn)可度，目前車輛通行調(diào)度模型已經(jīng)被廣泛地應(yīng)用于交通線路規(guī)劃、貨物運(yùn)輸以及客戶配送等多個(gè)領(lǐng)域之中。

盧錦川等人首先結(jié)合車輛運(yùn)輸相關(guān)參數(shù)構(gòu)建車輛通行調(diào)度模型，然后采用非線性擾動(dòng)因子改進(jìn)粒子群算法，提高算法全局和局部尋優(yōu)能力，求解車輛通行調(diào)度最優(yōu)模型。陳友榮等人構(gòu)建車輛通行調(diào)度模型后采用最近鄰原則初始化車輛集合，設(shè)定車輛通行距離范圍，建立二分圖并轉(zhuǎn)換矩陣為低維度矩陣，結(jié)合實(shí)際需求執(zhí)行KM算法直到生成最優(yōu)調(diào)度模型。馬艷芳等人結(jié)合模糊需求建立車輛通行調(diào)度模型，采用自然數(shù)編碼構(gòu)建適應(yīng)度函數(shù)，以兩元素優(yōu)化法作為差分算法變異機(jī)制，聯(lián)合二項(xiàng)交叉算子和貪婪選擇算子實(shí)現(xiàn)最優(yōu)調(diào)度模型獲取。以上方法在構(gòu)建車輛通行調(diào)度模型時(shí)沒有考慮駕駛員自身特征差異，導(dǎo)致生成的最優(yōu)調(diào)度路徑總距離較長(zhǎng)，生成最優(yōu)調(diào)度路徑所用迭代次數(shù)和運(yùn)行時(shí)間較多的問題。

雖然以上研究已經(jīng)取得了較好的應(yīng)用效果，但是交通事故發(fā)生時(shí)，車輛堵塞的問題較為嚴(yán)重，且運(yùn)輸貨物車輛體型更大，通行難度也更大。為了解決上述方法中存在的問題，提出交通事故約束下車輛通行最優(yōu)調(diào)度模型研究。

2 車輛通行調(diào)度模型構(gòu)建

(1)

交通事故下的車輛通行調(diào)度問題不僅受外界環(huán)境因素影響，同時(shí)也與駕駛員自身特征息息相關(guān)，通過駕駛速度差異描述駕駛員駕駛經(jīng)驗(yàn)、風(fēng)險(xiǎn)偏好、道路熟悉程度等個(gè)體差異，為使結(jié)果具有可比性，將其它外界因素均視為相同，以車輛通行時(shí)間最短及通行成本最低為目標(biāo)分別構(gòu)建車輛通行調(diào)度模型。

(2)

用表示車輛初始位置，表示駕駛員初始位置，為保證駕駛員初始位置與車輛初始位置相同，設(shè)定函數(shù)，約束條件如下所示

(3)

其中，(，)=1表示車輛初始位置與駕駛員初始位置相同，反之為0。

(4)

機(jī)械臂要完成相應(yīng)的抓取工作，必須由步進(jìn)電機(jī)來進(jìn)行驅(qū)動(dòng)，步進(jìn)電機(jī)的作用是將電脈沖信號(hào)轉(zhuǎn)換為相應(yīng)的角位移或直線位移的設(shè)備，它利用電脈沖信號(hào)進(jìn)行控制，當(dāng)步進(jìn)電機(jī)接收到一個(gè)電脈沖控制信號(hào)后，就轉(zhuǎn)動(dòng)一個(gè)固定角度或前進(jìn)一段固定位移。

(5)

(6)

3 基于自適應(yīng)模擬退火遺傳算法的模型求解

在得到交通事故約束下的車輛通行調(diào)度模型后，采用自適應(yīng)模擬退火遺傳算法求解車輛通行最優(yōu)調(diào)度模型。

(7)

自適應(yīng)遺傳算法具有優(yōu)異的全局尋優(yōu)能力，但其局部尋優(yōu)能力無法滿足尋優(yōu)需求，因此引入局部尋優(yōu)能力更好的模擬退火算法對(duì)其優(yōu)化。

模擬退火算法是根據(jù)固體退火原理而來的隨機(jī)算法，在局部尋優(yōu)中具有優(yōu)異的表現(xiàn)。引入指數(shù)降溫法控制溫度改變，用表示初始溫度，表示溫度下降系數(shù)，則當(dāng)前控制溫度=()-1，在模擬退火過程中，新解在當(dāng)前解鄰域范圍內(nèi)生成，用和′表示當(dāng)前解和新解，兩者均為種群個(gè)體，()表示擾動(dòng)值，當(dāng)為時(shí)，()≤1，()能夠確?！湓诩s束范圍內(nèi)，當(dāng)→0時(shí)，()→0，從而保證算法收斂性，表示(0，1)內(nèi)隨機(jī)數(shù)。用(′)和()表示和′的適應(yīng)度值，依據(jù)準(zhǔn)則計(jì)算由變?yōu)椤涞慕邮芨怕?，如下所?/p>

(8)

通過自適應(yīng)模擬退火遺傳算法求解車輛通行調(diào)度最優(yōu)模型的主要流程如下所示

①初始化最小新解接收次數(shù)、最大內(nèi)循環(huán)次數(shù)、軌道離散參數(shù)以及、、、，隨機(jī)生成初始群體；

②計(jì)算全部個(gè)體適應(yīng)度值并記錄其中最優(yōu)適應(yīng)度個(gè)體，拉伸適應(yīng)度值得到拉伸結(jié)果′=exp[-(-)]，引入輪盤賭法選擇個(gè)體并實(shí)行交叉和變異操作；

③設(shè)置內(nèi)循環(huán)次數(shù)=0，新解接受次數(shù)=0，計(jì)算自適應(yīng)遺傳算法處理后的個(gè)體適應(yīng)度值，對(duì)適應(yīng)度值最高的前個(gè)個(gè)體模擬退火，計(jì)算()并判定新解接受概率是否符合作為當(dāng)前解的要求，若符合，則=+1，反之保持不變。若<且<，則=+1，返回步驟①，反之跳出循環(huán)，采用適應(yīng)度值最小的個(gè)個(gè)體替代退火后個(gè)體，開始步驟④；

④采用步驟②記錄最優(yōu)適應(yīng)度值對(duì)應(yīng)個(gè)體替換子代種群中任意一個(gè)個(gè)體；

⑤若<，則計(jì)算當(dāng)前降溫后溫度，令=+1，返回步驟②，反之流程結(jié)束。

采用以上自適應(yīng)模擬退火遺傳算法能夠提升車輛通行調(diào)度模型求解能力，從而獲取車輛最優(yōu)調(diào)度結(jié)果。

4 實(shí)驗(yàn)與結(jié)果

為了驗(yàn)證交通事故約束下車輛通行最優(yōu)調(diào)度模型仿真的整體有效性，需要設(shè)計(jì)一次測(cè)試實(shí)驗(yàn)。調(diào)取某市早高峰交通事故的監(jiān)控錄像，如圖1所示，隨機(jī)選取事故現(xiàn)場(chǎng)正在通行的運(yùn)輸貨物車輛20臺(tái)，將運(yùn)輸貨物車輛的目的地設(shè)置為本次實(shí)驗(yàn)的通行調(diào)度目的地，經(jīng)查看監(jiān)控可知這20臺(tái)車輛的目的地分布在20km×20km的區(qū)域內(nèi)。

圖1 事故現(xiàn)場(chǎng)示意圖

以文獻(xiàn)[4]提出的基于改進(jìn)粒子群算法的車輛調(diào)度方法和文獻(xiàn)[5]提出的基于最近鄰原則的車輛調(diào)度優(yōu)化方法為對(duì)照方法，測(cè)試提出方法的車輛通行最優(yōu)調(diào)度的生成策略的合理性。設(shè)定車輛調(diào)度中心坐標(biāo)為(11.0km，15.5km)，目的地相關(guān)參數(shù)如表1所示。

表1 車輛目的地位置坐標(biāo)

由于不同車輛通往目的地的路線較多，因此不對(duì)生成的調(diào)度路徑做具體列舉。將實(shí)驗(yàn)測(cè)試過程迭代次數(shù)設(shè)置為1000次，以所提方法、文獻(xiàn)[4]提出的基于改進(jìn)粒子群算法的車輛調(diào)度方法和文獻(xiàn)[5]提出的基于最近鄰原則的車輛調(diào)度優(yōu)化方法生成的最優(yōu)調(diào)度路徑總距離、生成最優(yōu)調(diào)度路徑迭代次數(shù)和生成最優(yōu)調(diào)度路徑運(yùn)行時(shí)間為指標(biāo)檢驗(yàn)三種方法性能，結(jié)果如圖2～圖4所示。

圖2 不同方法調(diào)度下車輛總距離對(duì)比

由圖2可以看出，在實(shí)現(xiàn)相同運(yùn)輸目標(biāo)時(shí)，所提方法規(guī)劃的交通事故約束下車輛通行最優(yōu)調(diào)度模型總距離始終小于文獻(xiàn)[4]提出的基于改進(jìn)粒子群算法的車輛調(diào)度方法和文獻(xiàn)[5]提出的基于最近鄰原則的車輛調(diào)度優(yōu)化方法，此實(shí)驗(yàn)結(jié)果表明所研究模型應(yīng)用下車輛能夠以最短距離到達(dá)目的地。因?yàn)樗岱椒ㄔ谝?guī)劃車輛通行最優(yōu)調(diào)度模型時(shí)不僅考慮外界環(huán)境因素的影響，還結(jié)合了駕駛員自身特征，以外界干擾和駕駛速度差異共同構(gòu)建交通事故約束下車輛通行調(diào)度模型從而獲取最優(yōu)路徑。

圖3 不同方法生成最優(yōu)調(diào)度路徑時(shí)迭代次數(shù)對(duì)比測(cè)試

圖4 不同方法調(diào)度過程耗時(shí)對(duì)比測(cè)試

由圖3和圖4可以看出，所提方法在生成總距離短于基于改進(jìn)粒子群算法的車輛調(diào)度方法和基于最近鄰原則的車輛調(diào)度優(yōu)化方法的同時(shí)迭代次數(shù)和運(yùn)行時(shí)間均短于文獻(xiàn)方法，說明所提方法獲取最優(yōu)調(diào)度路徑時(shí)的效率最高，更適合用于實(shí)際車輛運(yùn)行調(diào)度最優(yōu)路徑規(guī)劃之中。

5 結(jié)束語

為了解決目前存在生成的最優(yōu)調(diào)度路徑總距離較長(zhǎng)，生成最優(yōu)調(diào)度路徑所用迭代次數(shù)和運(yùn)行時(shí)間較多問題，提出交通事故約束下車輛通行最優(yōu)調(diào)度模型仿真，結(jié)合交通事故和駕駛速度差異構(gòu)建車輛通行調(diào)度模型，采用自適應(yīng)模擬退火遺傳算法求解最優(yōu)模型。該方法能夠有效地縮短生成的最優(yōu)調(diào)度路徑總距離，降低生成最優(yōu)調(diào)度路徑所用迭代次數(shù)和運(yùn)行時(shí)間，為交通事故影響時(shí)的車輛通行調(diào)度規(guī)劃奠定基礎(chǔ)。