孫 萍，盧俊杰，陳友榮，，趙克華，3

(1. 浙江樹人大學信息科技學院，浙江 杭州 310015； 2. 常州大學計算機與人工智能學院&阿里云大數(shù)據(jù)學院，江蘇 常州 213164；3. 浙江禹貢信息科技有限公司，浙江 杭州310015)

1 引言

我國地域遼闊，降水局部集中，時間與空間分布不均，且與人口、耕地等分布不相匹配，因而歷來水災(zāi)頻發(fā)。據(jù)國家水利部發(fā)表預測未來我國氣象水文年景總體偏差，極端事件增多，澇重于旱，突發(fā)洪澇災(zāi)害事件隨時可能發(fā)生[1]。一旦發(fā)生災(zāi)害，需要保證防洪搶險救災(zāi)工作的正常快速運轉(zhuǎn)。其中，防汛物資的快速調(diào)度是防汛搶險救災(zāi)工作的重要一個環(huán)節(jié)。一旦搶險救災(zāi)工作啟動，需要保證防汛物資調(diào)得出、運得走、及時到位。因此需要一種防汛物資的車輛運輸調(diào)度方法，解決防汛物資運得走問題。

目前國內(nèi)外學者在車輛調(diào)度優(yōu)化領(lǐng)域已取得一定成果。部分學者側(cè)重于以到達時間短，車輛行駛距離和運輸費用最小等作為模型優(yōu)化目標，研究多目標調(diào)度優(yōu)化問題，如文獻[2]建立了綜合多周期、多物流中心和需求點時間約束的車輛調(diào)度模型，提出了一種具有適應(yīng)性差異控制的混合遺傳求解算法。文獻[3]以總配送費用最小為目標，提出單次運輸?shù)穆窂揭?guī)劃模型，優(yōu)化軍事應(yīng)急物流運輸。文獻[4]構(gòu)建應(yīng)急物資調(diào)運系統(tǒng)的高效、及時、低成本的動態(tài)調(diào)度模型，通過弗洛伊德算法對其進行最短路徑求解。但是文獻[2-4]沒有考慮道路受損擁擠和分配公平原則，所建模型較簡單。因此部分學者側(cè)重于研究道路受損或擁擠下的車輛調(diào)度方法。如文獻[5-7]都考慮了對禁行路段和必經(jīng)路段道路受損的通行時間阻抗，分別提出了等待風險最小和通信時間最短的車輛調(diào)度算法和一種帶精英策略的混合進化算法。文獻[8]考慮路徑規(guī)劃和不確定通行能力等約束，建立不確定信息環(huán)境下車輛調(diào)度優(yōu)化模型，并提出基于逆向搜索最短路徑和正向反推安全路徑的求解算法。文獻[9-10]分別構(gòu)建基于運輸時間最短、資源調(diào)度最少的多目標應(yīng)急物資調(diào)度計算模型，都采用加權(quán)排序法將多目標問題轉(zhuǎn)化為單目標問題，并利用遺傳算法進行求解。部分學者側(cè)重于研究分配公平原則下的車輛運輸調(diào)度算法，如文獻[11]建立需求未滿足率、交貨時間和運輸成本的最小化模型，提出基于多目標遺傳算法求解配送路徑。文獻[12]采取加權(quán)方法構(gòu)建權(quán)衡多個目標的車輛調(diào)度模型，并提出基于親密函數(shù)概念的聚類遺傳算法求解。但是文獻[8-12]沒有同時考慮道路受損擁擠和分配公平原則，且只是采用理想狀態(tài)建模，沒有考慮防汛物資運輸?shù)恼鎸崍鼍啊?/p>

綜上所述，目前車輛調(diào)度算法仍存在以下問題，不能適應(yīng)于防汛物資的車輛運輸問題：①車輛調(diào)度模型沒有同時考慮道路受損擁擠和分配公平原則，建模較理想化。②主要考慮運輸車輛實現(xiàn)每一個物資儲備倉庫的物資運輸問題，較少考慮物資儲備倉庫需要的運輸車輛調(diào)配問題。因此在上述文獻的基礎(chǔ)上，考慮救災(zāi)緊迫性、公平性和道路受損擁擠等情況，提出一種基于儲備倉庫多目標多約束的運輸車輛調(diào)度算法(transportation vehicle scheduling algorithm based on multi-objective and multi-constraint of reserve warehouse，TVSA)，根據(jù)各個儲備倉庫所需車輛數(shù)量，物流中心位置和擁有車輛數(shù)量等信息，提出車輛平均調(diào)度預測時間，離規(guī)定救援時間的偏離度和平均偏離度方差等數(shù)學公式，建立每一個儲備倉庫的車輛調(diào)度優(yōu)化模型。采用基于Pareto支配策略的多目標遺傳算法，即通過非支配等級和精英解保留，提高算法的收斂性，通過擁擠度計算和非支配排序進行交叉和變異操作，保證算法的全局尋優(yōu)能力，最終可獲得一組趨于均勻分布的非支配解集和可權(quán)衡調(diào)度預測時間和偏離度的車輛運輸調(diào)度方案，從而降低車輛平均調(diào)度預測時間，離規(guī)定救援時間的偏離度和偏離度方差，提高算法收斂速度。

2 模型建立

問題表述：每一個城市內(nèi)存在1個以上防汛物資的儲備倉庫和指定的1個以上車輛物流中心。每個物流中心存在若干輛防汛物資的運輸車輛，一輛運輸車輛同一個時刻只可前往一個儲備倉庫。當發(fā)生災(zāi)難需要進行防汛物資調(diào)度時，則接收到儲備倉庫的運輸請求后，物資運輸車輛根據(jù)車輛調(diào)度時間最小和配送公平原則進行調(diào)度運輸，并盡可能多的滿足各個儲備倉庫對車輛需求。

如圖1所示，一個地區(qū)存在多級物資儲備倉庫(省級、市級和區(qū)級)和多個車輛物流中心。當災(zāi)難發(fā)生后啟動搶險工作時，物流中心接收到各級儲備倉庫的物資運輸指令后進行車輛調(diào)配。首先根據(jù)開源平臺API計算兩點間各路段車流情況，估算預測總體完成運輸時間，以盡可能快速的對車輛進行調(diào)度。其次引入運輸時間偏離度和車輛數(shù)量偏離度概念，盡可能保證其救援公平性。目前算法需要解決以下二個問題：一是如何考慮多個儲備倉庫之間的競爭，建立儲備倉庫多目標多約束下的運輸車輛調(diào)度模型；二是如何求解上述模型，獲得最優(yōu)方案，從而降低車輛到達儲備倉庫的時間以及離規(guī)定運輸?shù)诌_時間的偏離度。具體模型建立如下。

(1)

圖1 運輸車輛調(diào)度示意圖

(2)

依據(jù)浙江省水利防汛物資管理辦法規(guī)定，在制定水利防汛物資應(yīng)急調(diào)度方案中應(yīng)當考慮交通道路情況。因此結(jié)合開源平臺API計算儲備倉庫與物流中心之間的各段道路行駛規(guī)劃組合，將物流中心及水利平臺上報的損毀道路以及禁止通行路段從組合中剔除，再綜合考慮道路擁擠情況對車輛的總體運輸行駛時間進行預測估算。為了預測道路的總體通暢情況，引入一個道路擁擠因子(Road congestion factor，RCF)作為主要影響因素。令某個物流中心j至某個儲備倉庫k的總路程劃分為n個路段，第i個路段長度為Li，以交通指數(shù)計算最小時間單位C(15分鐘)為時間段間隔，計算當前時間段和上一時間段該路段的平均通行速度S對比，得到當前路段行駛組合實際通行時間比值Tp。

(3)

根據(jù)式(3)計算所得的行程時間比值，通過對比同一路段的相鄰兩個時間段車輛通行速度預測路段是否處于擁堵減輕或加重，獲得當前路段組合的擁擠因子RCF。

(4)

考慮防汛救災(zāi)的緊迫性，以所有物資運輸車輛平均行駛預測時間最小為首要優(yōu)化目標。令Tk表示所有運輸車輛到達儲備倉庫k的總預測抵達時間為

(5)

當僅出現(xiàn)單個物流中心對單個儲備倉庫進行車輛調(diào)度時，其解決方案較為簡單，隨著數(shù)量規(guī)模的增加，其難度呈指數(shù)性增加?？紤]發(fā)生大規(guī)模災(zāi)害時需要大量的車輛，且在實際過程中，大型儲備倉庫往往與某些物流中心事先簽訂協(xié)議要求救災(zāi)過程中必須保證其運輸車輛需要在一定的時間內(nèi)達到，即每一輛車輛完成調(diào)度任務(wù)的行駛時間距離規(guī)定的運輸車輛抵達時間的偏離程度應(yīng)盡可能小，則離規(guī)定抵達時間的偏離度定義為

(6)

(7)

其中，ωk表示運輸車輛抵達儲備倉庫k的時間總偏離度，ωjk表示從物流中心j到儲備倉庫k的調(diào)度預測時間的偏離值，tjk表示車輛兩點間的調(diào)度行駛預測時間，μ表示規(guī)定車輛到達儲備倉庫的最大運輸時間。

考慮到每個儲備倉庫都希望其調(diào)度方案盡可能的滿足自身需求，則可建立每一個儲備倉庫的調(diào)度優(yōu)化模型：

min(Tk×(1+ωk))

(8)

s.t.：式(1)-(7)

在運輸過程中，每一個儲備倉庫都需要自身防汛物資能快速運輸出去，則儲備倉庫相互競爭運輸車輛資源，是一個多目標優(yōu)化問題。

3 模型求解

車輛資源調(diào)度問題是一種組合優(yōu)化的NP難問題，目前研究主要通過精確算法和啟發(fā)式算法求解。精確算法比較適合規(guī)模較小模型求解。啟發(fā)式算法適用于規(guī)模較大模型求解。而遺傳算法等元啟發(fā)式算法是啟發(fā)式算法的改進，是隨機算法與局部搜索算法相結(jié)合的產(chǎn)物，能更加有效地發(fā)現(xiàn)近似最優(yōu)解。在多目標求解問題上，考慮到遺傳算法具有較高的魯棒性和較強的搜索能力等特性，更適合求解較為復雜的調(diào)度優(yōu)化問題。因此選擇基于Pareto支配策略的多目標遺傳算法求解儲備倉庫競爭的多目標問題(8)，具體求解過程如下。

3.1 染色體編碼設(shè)計

令一個有效的調(diào)度方案為染色體，采用一維實數(shù)矩陣編碼，在運輸車輛調(diào)度中，擬定一個地區(qū)有J個物流中心，有K個儲備倉庫，編寫矩陣維度為J×K的染色體。如下圖2所示，染色體中的基因數(shù)值代表某個物流中心派往某個倉庫點的運輸車輛數(shù)量。例如第一行第三列基因值代表由1號物流中心派遣4輛運輸車至3號儲備倉庫。依次循環(huán)類推，可形成對所有物流中心和倉庫點的運輸車輛數(shù)量的調(diào)配指令。

圖2 編碼結(jié)構(gòu)圖

3.2 種群初始化

種群的初始化就是依據(jù)編碼規(guī)則給出種群的初始解。按照約束條件進行隨機數(shù)值生成，得到一定數(shù)量的初始解集。其染色體初始化的具體程序流程如下：

3.3 染色體適應(yīng)度評價

針對物資運輸車輛調(diào)度的緊急性，每個儲備倉庫都希望盡可能滿足自身需求，因此計算單個儲備倉庫的個體適應(yīng)度Fk，即

Fk=Tk×(1+ωk)

(9)

而調(diào)度最優(yōu)解應(yīng)權(quán)衡所有儲備倉庫的運輸時間、偏離度和公平方差，則令染色體的總體適應(yīng)度評價函數(shù)為

Fitness=Tave×(1+ωave)×(1+Rat)

(10)

其中，Tave表示所有車輛調(diào)度的平均時間，ωave表示所有車輛運輸?shù)诌_時間的平均偏離度，Rat表示平均偏離度的方差，可定義為

(11)

若該染色體適應(yīng)度評價值越小，則該調(diào)度方案效果越好，反之越差。

3.4 Pareto非支配計算和選擇操作

本算法考慮儲備倉庫之間的競爭，根據(jù)儲備倉庫數(shù)量將種群劃分成對應(yīng)數(shù)量的子類種群，盡可能使每個子類種群其對應(yīng)的適應(yīng)度越優(yōu)，從而實現(xiàn)儲備倉庫的多目標求解，具體步驟如下：

步驟1：通過式(9)計算所有染色體中每個儲備倉庫k的適應(yīng)度值，得到一個長度為K的個體適應(yīng)度矩陣Fm。對矩陣Fm中每一列數(shù)據(jù)進行排序，獲得矩陣Fm中每一個元素的鄰居個體i+1和i-1，計算擁擠度，即通過染色體i對染色體i+1以及染色體i-1的歐式距離值，計算擁擠度d，即計算每一個個體適應(yīng)度值Fk的差值之和。擁有最大和最小值的解被指定為無窮大距離的值，即邊界解d1=dy=∞。

(12)

步驟2：由于解集合中會出現(xiàn)部分解集中在某個區(qū)域，部分區(qū)域中解分布稀疏的情況，因此根據(jù)染色體的擁擠度，進行降序排序，獲得與周圍鄰居染色體的空間度量，通過式(11)計算染色體被選擇概率。

(13)

步驟3：基于非支配排序劃分非支配等級。循環(huán)比較任意的兩個染色體的個體適應(yīng)度值Fk。若其中一個染色體的個體適應(yīng)度值均大于或等于另一個染色體，則表示該染色體支配另一個染色體，因此可以獲得一組不被其它解支配的非支配解集合Q1，并將之從種群中暫時除去。繼續(xù)兩兩比較染色體適應(yīng)度值Fk得到新的一組非支配解集合Q2。以此循環(huán)，直至將雙倍初始規(guī)模大小的新種群劃分為若干個等級。

步驟4：遍歷計算父代種群中所有染色體的適應(yīng)度值，將總適應(yīng)度最優(yōu)的染色體直接存入下一代新種群。保留非支配解集合Q1，若Q1中解數(shù)量小于初始種群規(guī)模，按照步驟3中的非支配等級，逐級進行擇優(yōu)填充，其擇優(yōu)準則為總體適應(yīng)度Fitness最小，直至種群規(guī)?；謴椭脸跏即笮　?/p>

3.5 交叉操作

根據(jù)2.4節(jié)確定每個染色體被選中的概率，選擇兩個父代染色體，采用均勻交叉算子產(chǎn)生下一代染色體，即每個基因都存在一定的概率進行交換，從而形成兩個新個體。具體方法為：在[0，1]范圍內(nèi)隨機生成一組維度為J×K的浮點數(shù)組，若存在數(shù)值小于預定交叉概率則進行交換。

3.6 變異操作

采用了移位擾動變異操作，改善遺傳算法的局部搜索能力，維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。具體方法如下：隨機生成一個[0，1]范圍內(nèi)的浮點數(shù)，若該值小于預定的變異概率則隨機選擇某一列k，從該列中選擇兩個基因?qū)M行位置交換。由于在進行交叉變異后其種群中會產(chǎn)生不滿足約束條件(1)-(2)的解，因此采用2.2節(jié)種群初始化中的修正操作(步驟2-3)，使其染色體滿足約束條件(1)-(2)。

4 算法的實現(xiàn)

如圖3所示，本文模型主要使用帶Pareto支配策略的多目標遺傳算法進行求解，其具體步驟如下所示：

步驟1：獲知所有物流中心的坐標位置以及所屬的運輸車輛數(shù)量，獲得儲備倉庫申報的車輛需求數(shù)量；

步驟2：根據(jù)開源地圖獲取物流中心與儲備倉庫兩者之間的若干條路線集合。獲取路線中各個路段的暢通情況，預測車輛行駛的最短通行時間；

步驟3：初始化種群規(guī)模大小M，設(shè)定交叉概率，變異概率，迭代終止次數(shù)等參數(shù)，依據(jù)約束條件進行隨機組合，得到初始解集；

步驟4：通過式(9)-(10)分別計算針對儲備倉庫的個體適應(yīng)度值Fk和總體評價最優(yōu)值Fitness；

步驟5：根據(jù)式(12)計算染色體之間擁擠度，從而確定各個染色體的選擇概率；其次對整個種群進行非支配排序，將整個種群劃分為若干個等級，獲得各級非支配解集合；

步驟6：保留歷史最優(yōu)解，依據(jù)非支配等級保留Pareto最優(yōu)解，根據(jù)總體適應(yīng)度評價值大小擇優(yōu)保留；

步驟7：循環(huán)選擇M次，進行交叉和變異操作；

步驟8：驗證新產(chǎn)生的染色體是否滿足約束條件(1-2)，如果不滿足，進行修正操作；

步驟9：進化迭代次數(shù)是否等于迭代終止次數(shù)，若是，則輸出非支配解集，輸出總體評價最優(yōu)解，否則，進化迭代次數(shù)加1，跳到步驟4。

5 算法實驗分析

5.1 實驗參數(shù)

選擇由合作企業(yè)提供的杭州地區(qū)的實際儲備倉庫位置，選擇部分儲備倉庫指定的實際物流中心位置和其車輛數(shù)量，選擇杭州地區(qū)的部分物流中心位置和車輛數(shù)量，同時選擇以下參數(shù)進行仿真：儲備倉庫個數(shù)為11，物流中心個數(shù)為10，種群大小為50，模型的終止迭代次數(shù)均為80，交叉概率為0.8(經(jīng)驗值)，變異概率為0.01(經(jīng)驗值)，規(guī)定車輛到達儲備倉庫的最大運輸時間μ為30分鐘。針對某個需求總車輛數(shù)，隨機生成20組不同實驗場景。每組場景中的每個儲備倉庫所需的車輛數(shù)量在[0-40]區(qū)間范圍內(nèi)隨機生成，且其需求總車輛數(shù)相同。分析20個不同實驗場景下算法的車輛平均調(diào)度預測時間，離規(guī)定抵達時間的平均時間偏離度和平均偏離度方差，取其平均值作為仿真結(jié)果值。

5.2 算法參數(shù)和效果分析

現(xiàn)選擇4.1節(jié)中仿真參數(shù)，共生成11個儲備倉庫所需車輛總數(shù)409輛，隨機分布儲備倉庫所需車輛數(shù)量，獲得TVSA算法的算法非支配解分布圖4和收斂圖5。當儲備倉庫數(shù)量大于2時，各儲備倉庫之間形成相互競爭的態(tài)勢且各自希望自身的個體適應(yīng)度值盡可能達到最優(yōu)。由于儲備倉庫數(shù)量是11，其空間維數(shù)較多，為方便數(shù)據(jù)展示，將其分為2組，計算輸出非支配集合中各組的平均個體適應(yīng)度值。如圖4所示，由于車輛調(diào)度問題是離散問題，因此其Pareto非支配解集呈現(xiàn)離散點分布，但其總體趨勢仍然呈現(xiàn)Pareto曲線特點。根據(jù)圖5所示，進化迭代次數(shù)達到31時，算法完成收斂，這是因為針對多目標問題，TVSA算法采用Pareto支配策略、交叉操作、變異操作和精英保留策略等操作，能較快找到非支配解集，收斂速度較快。

圖4 算法非支配解分布圖

圖5 算法總適應(yīng)度Fitness收斂圖

5.3 算法性能比較

選擇SGA(標準遺傳算法)和MOPSO(多目標粒子群算法)作為對比算法，分析不同儲備倉庫所需車輛總數(shù)下各算法的車輛平均調(diào)度預測時間、平均時間偏離度和平均偏離度方差。其中，SGA算法采用加權(quán)法將多個儲備倉庫之間的3個目標優(yōu)化求解問題轉(zhuǎn)化為單目標總體尋優(yōu)問題，采用標準遺傳算法求解，從而獲得最優(yōu)解。MOPSO算法在粒子群算法的基礎(chǔ)上引入Parto支配策略，尋找目標向量的最優(yōu)解集。SGA算法仿真參數(shù)和TVSA算法仿真參數(shù)相同，MOPSO算法的仿真參數(shù)取常規(guī)經(jīng)驗值，如慣性因子0.8，局部速度因子0.1和全局速度因子0.1?，F(xiàn)選擇儲備倉庫所需車輛總數(shù)50，100，150，200，250，300，350，400，和4.1節(jié)中的其它仿真參數(shù)。同一儲備倉庫所需車輛總數(shù)下隨機產(chǎn)生20次不同車輛分布場景，計算不同場景下的TVSA，SGA和MOPSO算法的目標函數(shù)值，取其平均值作為仿真結(jié)果值。

如圖6-7所示，不管儲備倉庫所需車輛數(shù)量如何變化，TVSA算法的車輛平均調(diào)度預測時間和離規(guī)定抵達時間的偏離度都小于SGA和MOPSO算法的車輛平均調(diào)度預測時間和離規(guī)定抵達時間的偏離度。這是因為：TVSA算法的種群適應(yīng)度值考慮平均調(diào)度預測時間和離規(guī)定抵達時間的偏離度，且在選擇階段加入精英保留，并根據(jù)支配等級和總體適應(yīng)度值大小對新種群進行填充，保證了算法收斂的高效性，同時根據(jù)擁擠度計算得到的選擇概率進行交叉變異操作，擴大算法的搜索效率，使其解在整個多維空間中分布更加均勻，最后基于式(11)計算得到權(quán)衡平均調(diào)度預測時間和偏離度的全局最優(yōu)解。而SGA算法僅僅依靠設(shè)置權(quán)重將多目標問題轉(zhuǎn)化為單目標問題，從而導致其解內(nèi)部的多目標值分布不均衡，不利于尋優(yōu)，并且隨著儲備倉庫數(shù)量增加，其目標維度增加，權(quán)重精確確定困難，從而求解效果下降。MOPSO算法在面對多目標問題時雖然引入了Pareto支配策略，但是隨著數(shù)據(jù)維度的增加，其計算量增大，計算精度變低，導致其尋優(yōu)能力減弱，容易陷入局部最優(yōu)。

圖6 車輛平均調(diào)度預測時間對比圖

圖7 離規(guī)定抵達時間的平均時間偏離度對比圖

如圖8所示，不管儲備倉庫所需的車輛總數(shù)如何變化，TVSA算法的平均偏離度方差小于SGA和MOPSO算法的平均偏離度方差。這是因為：針對11處儲備倉庫，SGA算法設(shè)置一組均勻分布的緊急性救援權(quán)重，并利用加權(quán)法計算最優(yōu)解，但是無法有效權(quán)衡各儲備倉庫之間的調(diào)度分配，無法保證其公平性，則其平均偏離度方差最大。MOPSO算法在搜索空間中其粒子速度無法動態(tài)調(diào)節(jié)，降低了精度和多樣性，對高維問題處理效果較差。TVSA算法能尋找到權(quán)衡各個儲備倉庫，體現(xiàn)出公平性原則，因此其平均偏離度方差最小。

圖8 平均偏離度方差對比圖

6 結(jié)束語

提出一種儲備倉庫多目標多約束的運輸車輛調(diào)度算法(TVSA)。首先，根據(jù)各個儲備倉庫所需車輛數(shù)量、地理坐標等信息，通過開源平臺API接口記錄各路段車輛平均通行時速預測擁堵情況，考慮車輛完成運輸?shù)念A測時間，時間偏離度和偏離度方差約束，建立運輸車輛調(diào)度優(yōu)化的多目標模型。其次，采用多目標遺傳算法求解該模型，即通過非支配排序?qū)⒄麄€種群分級并計算各個解之間的擁擠度，從而確定各個解被選中參與交叉變異的概率，使得整個解空間趨于均勻分布，避免陷入局部最優(yōu)，通過交叉操作、變異操作、精英保留策略等尋找最優(yōu)解，保證算法有效收斂。接著，分析TVSA算法的收斂性和非支配集合的解分布，比較TVSA、SGA和MOPSO算法的車輛平均調(diào)度預測時間、離規(guī)定抵達時間的偏離度和平均偏離度方差。

仿真結(jié)果表明：TVSA算法可獲得較優(yōu)車輛運輸調(diào)度方案，從而降低車輛平均調(diào)度預測時間，離規(guī)定救援時間的偏離度和偏離度方差，提高算法收斂速率，比SGA算法和MOPSO算法更優(yōu)。但是TVSA算法的時間復雜度較高，因此下一階段將研究低時間復雜度的求解算法，提高調(diào)度模型的求解速度。