張文暉

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

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

1 問題描述及模型建立

1.1 多模式分層網(wǎng)絡(luò)設(shè)計(jì)

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

圖1 多模式分層網(wǎng)絡(luò)結(jié)構(gòu)示意圖

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

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

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

圖2 模式層二的時(shí)空網(wǎng)絡(luò)結(jié)構(gòu)示意圖

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

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

1.2 模型構(gòu)建

1.2.1 假設(shè)條件

(1) 在應(yīng)急救災(zāi)過程中運(yùn)行的貨運(yùn)車輛均為額定滿載。

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

(3) 車輛在轉(zhuǎn)換弧上耗費(fèi)的時(shí)間均按1單位時(shí)間段數(shù)計(jì)量。

(4) 車輛運(yùn)行過程中所有相關(guān)費(fèi)用函數(shù)都成線性關(guān)系。

(5) 各供應(yīng)點(diǎn)和需求點(diǎn)上的貨物可供量與需求量已知。

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

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

目標(biāo)函數(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)

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

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

2 拉格朗日松弛算法在VRP中的應(yīng)用

2.1 問題解的框架

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

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

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

(12)

(13)

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

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

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

(14)

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

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

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

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

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

θk=λ·(OP-LB)/

(15)

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

(16)

2.2 子問題解法分析

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

3 算例分析

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

表1 算例測(cè)試結(jié)果檢驗(yàn)和比較

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

4 結(jié)語

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