顧 洵，戴 帥

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

1 引言

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

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

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

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

(1)

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

(2)

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

(3)

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

(4)

機械臂要完成相應(yīng)的抓取工作，必須由步進電機來進行驅(qū)動，步進電機的作用是將電脈沖信號轉(zhuǎn)換為相應(yīng)的角位移或直線位移的設(shè)備，它利用電脈沖信號進行控制，當步進電機接收到一個電脈沖控制信號后，就轉(zhuǎ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)能力更好的模擬退火算法對其優(yōu)化。

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

(8)

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

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

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

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

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

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

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

4 實驗與結(jié)果

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

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

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

表1 車輛目的地位置坐標

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

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

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

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

圖4 不同方法調(diào)度過程耗時對比測試

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

5 結(jié)束語

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