基于拉格朗日松弛算法的應急物流配送車輛調(diào)度模型優(yōu)化研究

張文暉

(廣東省珠海市交通運輸局， 廣東 珠海 519003)

各種緊急情況和事故會嚴重影響公共安全及人員和財產(chǎn)安全。重大災難性事故發(fā)生后，往往需要啟動緊急救援，包括醫(yī)療物資、防護裝備、安置及生活保障物資運輸?shù)?。應急物流下的車輛調(diào)度問題(Vehicle Rooting Problem，VRP)是積極應對各種緊急突發(fā)事件的關鍵因素。VRP基于具有已知裝載點(供應點)、卸載點(事故點)和已知可用路線的運輸網(wǎng)絡，在滿足其他外部約束條件(如對不同物資的需求、車輛類型和容量、時間窗要求等)的情況下，選擇最合適的行駛路線以達到預期目標要求(如路程或時間最短、保證時間前提下費用最少等)。 有關VRP的文獻資料很多，由于其復雜性，多數(shù)著重于以最小化運輸費用或最小化運輸時間作為目標函數(shù)來構建模型。如文獻[1-5]根據(jù)不同條件下的要求，構建了以運輸費用最小化為優(yōu)化目標的VRP模型；文獻[6]提出同時考慮送貨和提貨的車輛路徑問題，并采用并行變鄰域搜索算法進行求解；文獻[7]提出帶有軟時間窗的VRP模型，并采用禁忌搜索算法進行求解；文獻[8-9]根據(jù)模糊理論，采用兩階段變鄰域禁忌搜索算法解決模糊需求下車輛路徑選擇問題；文獻[11-13]針對各種應急條件下物流車輛路徑問題開展模型構建，并分別采用免疫算法、PSO 算法等進行求解。為提高對大型突發(fā)事件應急物流的響應能力，該文在相關研究的基礎上，綜合考慮應急物流需求的急迫性、多部門及市場主體參與性、弱經(jīng)濟性等內(nèi)在特點，將VRP問題轉化為多模式的分層網(wǎng)絡問題，構建多目標數(shù)學優(yōu)化調(diào)度模型并采取拉格朗日松弛算法進行求解。

1 問題描述及模型建立

1.1 多模式分層網(wǎng)絡設計

針對各類突發(fā)事件進行應急貨物運輸車輛調(diào)度時，由于事件發(fā)生點的隨機性，通常會出現(xiàn)多個可能的需求點與供應點，且需轉換2種以上運輸方式。為滿足應急物流需求，依據(jù)需求特點，展開不同運輸方式的多模式網(wǎng)絡分層設計。該模式網(wǎng)絡通常有四類頂點和三類弧(見圖1)。四類頂點分別為中轉點、映像點、供應點、需求點，其中：中轉點表示該節(jié)點僅為各種運輸方式轉換的場所，且不承擔貨物存儲任務；映像點表示該節(jié)點為各運輸方式下實際發(fā)貨(供應)或接收貨物(需求)的點；供應點表示該節(jié)點為應急貨物的提供場所，它通過各模式網(wǎng)絡層上的供應映像點發(fā)運貨物；需求點表示該節(jié)點為應急貨物的需求場所，它通過各模式網(wǎng)絡層上的需求映像點接收貨物。三類弧分別為載重弧、轉換弧、映像弧，其中：載重弧表示貨運通路，連接所有映像點和中轉點，與載重弧相關的成本為運輸成本；轉換弧表示將不同模式網(wǎng)絡層中的運輸方式進行連接的通道，轉換過程將產(chǎn)生相關轉運成本；映像弧僅表示映像點與需求或供應點之間的聯(lián)系，其相互間發(fā)生的供需運量關系、相關費用和時間消耗等均忽略不計。

圖1 多模式分層網(wǎng)絡結構示意圖

圖1中，a、b為需求點，c、d為供貨點，e、f為中轉點。該多模式分層網(wǎng)絡由3種運輸方式組成，故對應3種模式層。如c供貨點可通過模式層一、二中c′、c″的不同運輸方式映像點向各需求點運送貨物；f中轉點可在轉換弧上通過f″和f?2個不同運輸方式中轉點為模式層二、三的車輛進行轉換等。車輛可在不同模式層上被調(diào)度循環(huán)使用，從而形成循環(huán)車輛流。

在應急物流的車輛調(diào)度中，通常需設置某些特殊的約束條件：1) 車輛可在網(wǎng)絡上任意一個點被調(diào)用；2) 沒有固定停車場，因為車輛完成運輸任務后通常不必返回原始位置，而是停在原地；3) 車輛流只能流過載重?。?) 不同模式層上最大車輛流不能超出載重弧的最大容量限定，同時貨物流量不能超出貨運車輛的最大額定量。

盡量縮短貨物在途運輸時間是應急物流車輛調(diào)度的主要目標，故時間參數(shù)是調(diào)度中需考慮的首要因素。引入時間參數(shù)后，要解決的問題就轉化為四維空間優(yōu)化問題。為方便起見，將貨運調(diào)度方案總體所需時間周期劃分成若干等長的單位時間段，在車輛調(diào)度優(yōu)化模型中設置的時間參數(shù)均以時段數(shù)來表示時間維度值。這樣可使各供需節(jié)點的供貨量或需求量與應急救援所規(guī)定的不同時間要求更加匹配，因為以一個預定的時間周期來進行調(diào)度計劃安排，可能會導致車輛在完成任務后出現(xiàn)不必要的閑置時間，而采用時間段可更靈活地根據(jù)需求進行調(diào)度安排。需注意的是，時段長度的取值不能過大，也不能過小，過大可能導致車輛在完成任務后出現(xiàn)不必要的閑置時間，過小則會導致車輛路徑長度呈指數(shù)增長。引入時間維度后，多模式分層網(wǎng)絡便轉換成了時空網(wǎng)絡(見圖2)，該時空網(wǎng)絡由圖1中第二模式層抽象而來，其中每兩點間的車輛行駛路線用虛線連接。車輛的起始點在c與d點，車輛可根據(jù)需要在時空網(wǎng)絡的單向可行路線中按照調(diào)度指令選擇完成配送任務的路線。

圖2 模式層二的時空網(wǎng)絡結構示意圖

應急物流VRP是一個多目標(減少運輸時間、降低運輸費用)規(guī)劃問題，其中運輸費用的產(chǎn)生主要體現(xiàn)在載重弧上車輛行駛費用和車輛在各中轉點進行運輸方式換載時發(fā)生的費用。在構建運輸時間最小化目標函數(shù)模型時，可設置車輛未按時到達的罰函數(shù)參數(shù)，通過車輛延期到達的罰函數(shù)系數(shù)來反映不同需求點對應急物資的時間需求程度。該罰函數(shù)系數(shù)可由未滿足時間要求而順延一個時間段對目標函數(shù)所造成的單位增量來定義。

該方法的優(yōu)點在于適用性較靈活，如需要以最小時間為目標函數(shù)，可將貨運費用參數(shù)值設置為零；而當救援行動持續(xù)一段時間，應急情況相對緩解后，需考慮救援貨物運輸費用最小化時，可將模型中時間參數(shù)延期的罰函數(shù)系數(shù)賦值為零。

1.2 模型構建

1.2.1 假設條件

(1) 在應急救災過程中運行的貨運車輛均為額定滿載。

(2) 載重弧上運行的貨運車輛均以單位時段數(shù)來計量運輸時間，運行時間小于1單位時段的按1單位計量。

(3) 車輛在轉換弧上耗費的時間均按1單位時間段數(shù)計量。

(4) 車輛運行過程中所有相關費用函數(shù)都成線性關系。

(5) 各供應點和需求點上的貨物可供量與需求量已知。

(6) 不同模式層下同一種運輸方式的車輛規(guī)格相同。

1.2.2 目標函數(shù)與約束條件

目標函數(shù)為：

min(C1+C2+C3)

(1)

(2)

(3)

約束條件如下：

(i∈S,g∈G,t∈T)

(4)

(i∈R,g∈G,t∈T)

(5)

(i∈FE,t∈T,g∈G,m∈M,i′∈R∪S)

(6)

(7)

(8)

(i,j)∈CA)

(9)

(10)

(t∈T,m∈M,(i,j)∈CA)

(11)

模型中的開始時刻為貨運的最早發(fā)運時間，由車輛行駛成本、運輸方式轉換成本、車輛未按時到達所帶來的目標函數(shù)增加值構成目標函數(shù)。

約束條件由貨物流約束、車輛流約束、關聯(lián)約束構成，其中：貨物流約束對供應點向需求點運輸?shù)呢浳镞M行約束；車輛流約束是對車輛在各供應點和需求點之間流轉的約束；關聯(lián)約束將貨物流與車輛流集成為一個整體相互關聯(lián)約束。式(4)～(7)為貨物流約束，式(4)表示供應點庫存量與供應點向各需求點運輸貨物的量平衡關系，即i點通過其映像點運送的g貨物數(shù)量=i點在上一時間段已延期到本時間段尚未發(fā)貨的貨物量+需新增的供貨量-延期到下一時間段運送的貨物量；式(5)表示需求點接收的貨物量未滿足需求，仍需增加供貨量；式(4)、(5)反映供應點與需求點之間貨物量的供需平衡關系；式(6)等式兩邊分別為貨物流入量和流出量，反映中轉點或映像點進出貨物量間的平衡關系；式(7)是非負條件約束。式(8)為車輛流平衡約束式，為進入中轉點或映像點的車輛總數(shù)等于已完成貨運任務并離開該點的車輛數(shù)與仍需停留在該點待命的車輛數(shù)之和。式(9)表示在弧(i,j)上運行的車輛數(shù)不能超過弧(i,j)所限制的最大容量，為車輛流的上限約束。式(10)表示車輛流決策變量值非負且為整數(shù)。式(11)反映車輛流與貨物流之間的關系，為兩者間的關聯(lián)約束，即通過載重弧(i,j)上貨運車輛的貨物運載量不能大于車輛的額載量。

2 拉格朗日松弛算法在VRP中的應用

2.1 問題解的框架

根據(jù)上述對應急物流車輛調(diào)度VRP模型的分析，車輛運營成本、運輸方式轉換中產(chǎn)生的費用及貨運車輛延期需求懲罰費用共同構成該模型的目標函數(shù)，模型的約束條件由車輛流、貨物流及其兩者之間相互關聯(lián)約束構成。對于后者，如果能采用相應的方法松弛該關聯(lián)約束，使模型轉化為車輛調(diào)度與貨物運輸2個子問題，求解模型的難度將大大降低。根據(jù)該思路，采用拉格朗日松弛算法進行求解。

引入該算法后的目標函數(shù)為：

min(C1+C2+C3+C4+C5)

(12)

(13)

式中：Wmijt為拉氏乘子向量組，簡稱Lag(OP)。

兩者相互關聯(lián)約束松弛之后，可將拉式乘子問題的求解過程分為對貨物流Lag1(X)與車輛流Lag2(Y)的計算。Lag1(X)的目標函數(shù)由式(2)、式(3)、式(12)組成，其約束為式(4)～(7)。為避免關聯(lián)松弛造成車輛在載重弧上的貨物流超限，在Lag1(X)中加入車輛貨物流量上限約束式：

(t∈T,m∈M,i∈FE,j∈FE)

(14)

車輛流Lag2(Y)的目標函數(shù)由式(1)、式(13)組成，其約束集為式(8)～(10)。

求解Lag(OP)最優(yōu)解的步驟：

(2) 利用子梯度法計算Lag(OP)。將Lag(OP)轉換為2個子問題Lag1(X)、Lag1(Y)分別進行計算，求得最優(yōu)解Xk和Yk。再求出目標函數(shù)值Sk，判斷Sk和LB兩者的大小關系，若Sk>LB，則利用LB=Sk判斷2個最優(yōu)解是否滿足約束條件。若滿足，且目標函數(shù)值Sk小于OP*，則令OP*=Sk，執(zhí)行步驟3；否則轉入步驟4。

(3) 退出循環(huán)的條件。1) 最優(yōu)解Xk和Yk是否滿足關聯(lián)約束等式成立的條件；2) (OP*-LB)/OP*<α(α為收斂率)；3)k=TK(TK為限制循環(huán)的次數(shù))。若滿足條件1，則可得出最優(yōu)解為Sk并輸出。若條件2中OP*距離下限解LB的比率小于收斂率α，則OP*是可行解并輸出。滿足條件3時，循環(huán)便直接退出，輸出Lag(OP)的最優(yōu)解。若循環(huán)不滿足上述3個條件，則執(zhí)行步驟4。

(4) 按式(15)求解拉氏乘子步長θk。將Xk和Yk代入式(15)，得到步長θk。如果在循環(huán)時LB的值不增加，但目標函數(shù)值必須收斂，則將比例因子λ減少至原來的一半，即λ=λ/2，執(zhí)行步驟5。

θk=λ·(OP-LB)/

(15)

式中：λ為比例因子，其初始值為2。

(16)

2.2 子問題解法分析

Lag1(X)：貨物流子問題。根據(jù)上述對多模式分層網(wǎng)絡的分析，實際上Lag1(X)問題可看作多種貨物應急調(diào)運的最小費用流問題，可應用列生成算法得出最小費用流?；〉馁M用可采用貨物流目標函數(shù)中式(2)、式(12)直接表示和計算，而式(3)需先轉換為弧形式，再進行計算。如果應急救援貨運只考慮時間最短而不在乎費用多少，則可將式(2)去除，直接求解運輸時間最短路徑。

3 算例分析

在某災害發(fā)生地區(qū)，設應急供應點、需求點與中轉點總量為8～12個，任選供應點與需求點，并不受坐標的影響。設每相鄰點之間弧的貨運周期為1～10，貨運計劃的周期數(shù)為以網(wǎng)絡中最長弧的貨運周期數(shù)為基數(shù)與3種類型點數(shù)的乘積之和。采用2種不同運輸方式對該應急貨運調(diào)度算例進行分析。設在單位時段內(nèi)，2種運輸方式單位車輛的運輸費用分別為10和100單位。 計劃執(zhí)行之初，車輛可在任意點停留。每種貨物每單位需求延時懲罰80單位，在調(diào)度計劃中最多運輸3種貨物。為保持應急貨物供需平衡，設每類貨物的運輸量≤500單位，每類貨物的供應點不超過3個，且每個需求點的貨物需求量為0～100。設Lag(OP)最優(yōu)求解步驟3中的收斂率α=0，應用拉格朗日松弛算法、單純形法與分支定界法結合算法對算例進行求解，將2種算法得出的最優(yōu)結果進行檢驗和比較。共進行10個算例任務測試，結果見表1。

表1 算例測試結果檢驗和比較

由表1可知：除算例7外，其余測試算例2種算法求解結果的偏差都小于5%，且各測試結果的平均偏差小于3.5%；偏差值與貨運計劃的時段數(shù)成正相關關系。算例2和10，由于運輸計劃時段數(shù)相對較少，2種算法計算結果之間的偏差均小于1%。

4 結語

該文基于應急物流的特點構建應急物流車輛調(diào)度VRP問題的多目標組合數(shù)學模型，在運用拉格朗日松弛算法的基礎上，將拉式乘子問題簡化為車輛流和貨物流2個子問題，采用網(wǎng)絡流算法分別求解。算例測試結果表明，該方法具有較好的收斂性與有效性，可為應急救災指揮中心制訂車輛調(diào)度方案提供依據(jù)。