基于雙層規(guī)劃的應(yīng)急救援車輛調(diào)度模型

夏紅云 江億平 趙林度

(東南大學(xué)系統(tǒng)工程研究所，南京210096)

近年來，大規(guī)模災(zāi)難性事件頻發(fā)，給人類造成了巨大的生命與財(cái)產(chǎn)損失.2013年的雅安地震造成196人死亡，11 470人受傷.在地震發(fā)生后的短時(shí)間內(nèi)，各災(zāi)區(qū)醫(yī)療資源極度匱乏，全國(guó)各地對(duì)雅安災(zāi)區(qū)迅速實(shí)施了醫(yī)療資源支援.由此發(fā)現(xiàn)，大規(guī)模災(zāi)難性事件會(huì)產(chǎn)生對(duì)應(yīng)急醫(yī)療資源突發(fā)的、迫切的、大量的需求，而現(xiàn)實(shí)背景下醫(yī)療資源供應(yīng)點(diǎn)的可用物資量與物資配送車輛受應(yīng)急準(zhǔn)備限制，在災(zāi)害發(fā)生后的短時(shí)間內(nèi)通常會(huì)供不應(yīng)求，運(yùn)輸車輛也必須承擔(dān)多次、分階段的調(diào)度任務(wù).因此，如何在特定時(shí)間域內(nèi)，通過多階段車輛調(diào)度將應(yīng)急醫(yī)療資源從多個(gè)供應(yīng)點(diǎn)配送到多個(gè)需求點(diǎn)，以最大化災(zāi)區(qū)需求滿足量是應(yīng)急救援中亟待解決的關(guān)鍵問題.

應(yīng)急物資車輛調(diào)度是傳統(tǒng)車輛路徑問題(vehicle routing problem)在應(yīng)急情境下的一種演化.傳統(tǒng)車輛路徑問題用以解決最小化運(yùn)輸成本目標(biāo)下將m個(gè)供應(yīng)點(diǎn)的物資運(yùn)送到n個(gè)需求點(diǎn)的車輛路徑規(guī)劃.自1959年Dantzing等[1]提出車輛路徑問題以來，該基本問題已有各種各樣的變化與拓展.基于車輛路徑問題中各參數(shù)的特征，可將拓展類型簡(jiǎn)單歸納為以下幾種:多路徑(multi-trip)車輛調(diào)度、分批到達(dá)(split delivery)車輛調(diào)度、帶取送的(pickup and delivery)車輛調(diào)度、多階段車輛調(diào)度(multi-period)等[2-7].上述問題多以最小化總成本為目標(biāo)，而應(yīng)急情境下必須以時(shí)效性為第一準(zhǔn)則，弱化調(diào)度過程中的經(jīng)濟(jì)性.

關(guān)于應(yīng)急救援車輛調(diào)度，Yuan等[8]考慮車輛受災(zāi)害影響的速度，構(gòu)建了應(yīng)急物流管理路徑選擇模型.Wohlgemuth等[9]在物資擁有量小于車容量的假設(shè)下，建立了災(zāi)害救援中的動(dòng)態(tài)車輛調(diào)度模型.應(yīng)急救援車輛調(diào)度問題受時(shí)間域的限制，會(huì)產(chǎn)生多次、多階段的調(diào)度任務(wù).關(guān)于多階段車輛調(diào)度，石彪等[10]建立了基于車輛緊缺假設(shè)的兩階段應(yīng)急物資運(yùn)輸車輛調(diào)度模型.Wen等[7]針對(duì)動(dòng)態(tài)多階段車輛調(diào)度問題，建立了混合整數(shù)線性規(guī)劃模型.文獻(xiàn)所提的多階段車輛調(diào)度中，每一階段車輛的可用數(shù)量基本上是已知的，而應(yīng)急背景下的實(shí)時(shí)調(diào)度中，每階段可用車輛數(shù)量隨時(shí)間及上一階段的決策而動(dòng)態(tài)變化.

本文考慮在大規(guī)模突發(fā)事件爆發(fā)后的有限時(shí)間域內(nèi)，針對(duì)應(yīng)急救援車輛不足，需要多次、分階段將應(yīng)急醫(yī)療資源從多個(gè)供應(yīng)點(diǎn)配送到多個(gè)需求點(diǎn)的情形，以最大化需求點(diǎn)收益、最小化延遲成本為目標(biāo)，采用網(wǎng)絡(luò)流理論及雙層規(guī)劃建模方法，構(gòu)建了含時(shí)間窗的應(yīng)急救援車輛多階段調(diào)度模型，并應(yīng)用基于動(dòng)態(tài)規(guī)劃的兩階段啟發(fā)式算法進(jìn)行求解.算例結(jié)果驗(yàn)證了該算法的可行性，上下層相互制約與合作推動(dòng)了全局最優(yōu)的實(shí)現(xiàn).

1 問題描述

從網(wǎng)絡(luò)流的角度來看車輛調(diào)度問題，假設(shè)整個(gè)有向圖為G=(I∪J，A)，其中I為供應(yīng)點(diǎn)的集合，J為需求點(diǎn)的集合，A為弧的集合.假定離散有限決策時(shí)間域?yàn)榧蟵0，1，…，T}.時(shí)間域T內(nèi)，每個(gè)供應(yīng)點(diǎn)的醫(yī)療物資存儲(chǔ)量為固定量si，每個(gè)供應(yīng)點(diǎn)i的車輛擁有量為ki，所有車的車載量均為Q，車輛集合為K.各需求點(diǎn)的需求量為dj，根據(jù)災(zāi)情給定的收益權(quán)重為βj，每個(gè)需求點(diǎn)的物資保障最低標(biāo)準(zhǔn)為αj.需求點(diǎn)j的最低標(biāo)準(zhǔn)保障量應(yīng)在bj時(shí)刻到達(dá)(設(shè)為bj整數(shù)時(shí)刻)，否則會(huì)產(chǎn)生延遲成本.每條弧a(i，j)∈A 的運(yùn)輸時(shí)間為 cij，其中 i∈I，i∈J.

本文構(gòu)建的應(yīng)急救援車輛調(diào)度模型基于如下基本假設(shè):

①每輛車一次只訪問一個(gè)需求點(diǎn);

②裝卸時(shí)間小于車輛運(yùn)輸行駛時(shí)間，暫不考慮;

③每輛車完成任務(wù)后立即返回原出發(fā)點(diǎn)待命;

④時(shí)間域T內(nèi)，除每個(gè)需求點(diǎn)最后一次運(yùn)輸或者供應(yīng)點(diǎn)物資匱乏外，每輛車都必須滿載.

2 雙層規(guī)劃模型

本文采用雙層規(guī)劃方法對(duì)問題進(jìn)行建模.上層規(guī)劃用以決策供應(yīng)點(diǎn)到需求點(diǎn)的最優(yōu)配送量，下層規(guī)劃用以決策在給定最優(yōu)配送量基礎(chǔ)上的各階段車輛調(diào)度方案.上層規(guī)劃與下層規(guī)劃的相互制約與合作推動(dòng)了整體優(yōu)化的實(shí)現(xiàn).

2.1 上層規(guī)劃

上層規(guī)劃的目標(biāo)函數(shù)為

式中，X為上層規(guī)劃中的上層決策解集;xij為上層決策變量，表示時(shí)間域T內(nèi)需要從供應(yīng)點(diǎn)i配送到需求點(diǎn)j的醫(yī)療資源總量;Y為上層規(guī)劃中的下層決策解集為下層決策變量，表示t時(shí)刻從供應(yīng)點(diǎn)i調(diào)配到需求點(diǎn)j的車流量;γ為權(quán)重系數(shù).

約束條件為

式中，τij為松弛變量，表示供應(yīng)點(diǎn)i到需求點(diǎn)j最后一次的運(yùn)輸量.

上層規(guī)劃中以最大化需求點(diǎn)收益、最小化時(shí)間域T的總時(shí)間成本為目標(biāo)，滿足式(2)和(3)的供應(yīng)約束條件與需求約束條件，即供應(yīng)點(diǎn)i配送的醫(yī)療資源總量不能超過其可供應(yīng)量，需求點(diǎn)j所獲得的總資源量不能超過其需求量.式(4)表明，供應(yīng)點(diǎn)i配送到j(luò)個(gè)需求點(diǎn)的醫(yī)療資源量不能超過供應(yīng)點(diǎn)i所擁有車輛能夠配送的數(shù)量上限.式(5)反映了與xij的關(guān)系，是下層規(guī)劃對(duì)上層規(guī)劃的反應(yīng)函數(shù).

2.2 下層規(guī)劃

下層規(guī)劃的目標(biāo)函數(shù)為

約束條件為

式中，Si(t)為t時(shí)刻供應(yīng)點(diǎn)i擁有的車輛數(shù).

下層規(guī)劃的目標(biāo)是在滿足上層規(guī)劃設(shè)定的物資量分配的基礎(chǔ)上最小化車輛延遲成本.本文的延遲懲罰函數(shù)是關(guān)于bj時(shí)刻需求點(diǎn)j所累積到達(dá)的物資量的線性函數(shù).由于t時(shí)刻從供應(yīng)點(diǎn)i調(diào)配到需求點(diǎn)j的輛車將在時(shí)刻到達(dá)需求點(diǎn)j，故可以得到式(6)的關(guān)于需求點(diǎn)j車輛的流量守恒公式.

3 算法與算例

3.1 算法

本文雙層規(guī)劃的求解類型是對(duì)上下兩層反復(fù)求線性規(guī)劃，在上層收斂時(shí)得到上層最優(yōu)解，從而引誘下層最優(yōu)解.對(duì)于上層線性規(guī)劃，本文利用Matlab軟件中線性規(guī)劃求解函數(shù)進(jìn)行求解;對(duì)于下層整數(shù)規(guī)劃，本文采用基于動(dòng)態(tài)規(guī)劃的兩階段啟發(fā)式算法求得整數(shù)最優(yōu)解.具體步驟如下.

1)設(shè)定初始解X0，令迭代次數(shù)r=0.

2)對(duì)于給定的Xr，找出由供應(yīng)點(diǎn)i覆蓋的Ni個(gè)需求點(diǎn)，將其分為2類:第1類是只由供應(yīng)點(diǎn)i覆蓋需求點(diǎn)j的需求;第2類是除了供應(yīng)點(diǎn)i還有其他供應(yīng)點(diǎn)覆蓋需求點(diǎn)j的需求.然后，分別按照bj的大小將需求點(diǎn)從小到大進(jìn)行排序，且第1類中需求點(diǎn)集體優(yōu)先.因此，下層最優(yōu)解分2個(gè)階段進(jìn)行:①將Ni個(gè)需求點(diǎn)的車輛調(diào)度分為Ni個(gè)有序階段進(jìn)行，令 ni=1，V(0)=0.如果 t≥bj，則停止迭代;否則，令在時(shí)間域T內(nèi)，以為需求點(diǎn)j每階段車流量分配的整數(shù)基準(zhǔn)，在其中a∈N+)的整數(shù)范圍內(nèi)設(shè)定)'，使得 V(ni)=，令.如果 ni=Ni，則停止迭代;否則，令ni=ni+1，繼續(xù)迭代.②將Ni個(gè)需求點(diǎn)的車輛調(diào)度分為Ni個(gè)有序階段進(jìn)行，令ni=1，V(0)=0，t=bj.如果t=T－1，則停止迭代;否則，令在時(shí)間域T內(nèi)，以每階段車流量分配為整數(shù)基準(zhǔn)，在整數(shù)范圍內(nèi)設(shè)定，令，使得需求點(diǎn)j的總到達(dá)物資滿足上層分配量.

3)根據(jù)式(5)計(jì)算τij，將關(guān)系式－)/Q+1代入上層目標(biāo)函數(shù)，求解上層問題，得到一組新的Xr+1值.

3.2 算例

為了更好地理解上述模型，本文考慮某地突發(fā)大規(guī)模災(zāi)害性事件，共計(jì)8個(gè)災(zāi)情嚴(yán)重的區(qū)域急需醫(yī)療資源，而此時(shí)只有3個(gè)資源供應(yīng)點(diǎn)存有有限的醫(yī)療物資與可調(diào)度車輛.通過算例描述并求解在災(zāi)害發(fā)生后的12個(gè)單位時(shí)間內(nèi)的救援車輛調(diào)度問題.表1～表3為各資源供應(yīng)點(diǎn)與需求點(diǎn)的參數(shù)現(xiàn)狀.

表1 供應(yīng)點(diǎn)參數(shù)

表2 需求點(diǎn)參數(shù)

表3 時(shí)間距離表

表4 上層最優(yōu)解

由表4可計(jì)算得上層最優(yōu)解的目標(biāo)函數(shù)值為F=177.12.根據(jù)上層最優(yōu)解可求得下層最優(yōu)解，結(jié)果見表5.在本算例中，鑒于下層目標(biāo)函數(shù)的特征，最優(yōu)解不唯一.

由表5可知，最優(yōu)解形成了集覆蓋調(diào)度方案，即供應(yīng)點(diǎn)1出發(fā)的車輛覆蓋需求點(diǎn)(1，3，7，8)，供應(yīng)點(diǎn)2出發(fā)的車輛覆蓋需求點(diǎn)(2，4，6)，供應(yīng)點(diǎn)3出發(fā)的車輛覆蓋需求點(diǎn)(1，5).由此可以計(jì)算出下層目標(biāo)函數(shù)最優(yōu)值為0，也即無延遲發(fā)生.總的來說，該算例體現(xiàn)了算法中以時(shí)間窗為重要衡量標(biāo)準(zhǔn)的指派特征.基于動(dòng)態(tài)規(guī)劃的兩階段啟發(fā)式算法，在第1階段以滿足時(shí)間窗為目標(biāo)，在第2階段以最快完成配送任務(wù)為目標(biāo)，算例結(jié)果驗(yàn)證了算法的可行性.從管理學(xué)角度來講，應(yīng)急管理部門先行決策各供應(yīng)點(diǎn)到需求點(diǎn)的最優(yōu)配送量，可以提高各階段車輛調(diào)度效率，戰(zhàn)術(shù)層決策依賴于戰(zhàn)略層的規(guī)劃部署.鑒于本算例的特殊性，故存在一些缺陷:① 上層目標(biāo)的最優(yōu)解沒有能夠驗(yàn)證算法的收斂性;②算例中車輛對(duì)于時(shí)間域來講相對(duì)充足，現(xiàn)實(shí)情境下車輛可能在時(shí)間域無法完成供應(yīng)點(diǎn)的配送任務(wù).

表5 車輛調(diào)度計(jì)劃

4 結(jié)語(yǔ)

本文考慮了應(yīng)急背景下車輛多次、分階段調(diào)度以實(shí)現(xiàn)資源優(yōu)化配置的問題.在針對(duì)多階段應(yīng)急車輛調(diào)度、車輛動(dòng)態(tài)決策的研究上，這種基于雙層規(guī)劃的應(yīng)急救援車輛調(diào)度模型表現(xiàn)出較大的創(chuàng)新性.與此同時(shí)，雙層規(guī)劃降低了整個(gè)問題求解的維度，算例較好地驗(yàn)證了雙層規(guī)劃算法實(shí)現(xiàn)全局最優(yōu)的可行性.總體來說，本文提出的應(yīng)急救援車輛調(diào)度優(yōu)化方案擬合了現(xiàn)實(shí)應(yīng)急情境，能夠?yàn)閼?yīng)急管理部門的車輛調(diào)度與應(yīng)急資源配置提供輔助決策.

應(yīng)急情景下各類信息往往是動(dòng)態(tài)的，需求的種類與數(shù)量會(huì)隨著時(shí)間的變化而變化，整個(gè)應(yīng)急物資配送的網(wǎng)絡(luò)應(yīng)該是一個(gè)動(dòng)態(tài)網(wǎng)絡(luò).本文設(shè)定的應(yīng)急需求與供應(yīng)都是常量，在未來的研究中可以考慮物資供應(yīng)是隨時(shí)間而變化的.本文假定車輛返回后必須返回原出發(fā)點(diǎn)，而在實(shí)踐中車輛可能返回任意資源供應(yīng)點(diǎn)，可能會(huì)產(chǎn)生更優(yōu)的解.此外，本文考慮的車輛返回是空返，為了加強(qiáng)應(yīng)急環(huán)境下車輛使用的有效性，在未來可以考慮車輛返回時(shí)能夠轉(zhuǎn)移受傷人群，將應(yīng)急資源配置與人群疏散結(jié)合起來.

References)

[1] Dantzing G，Ramser J.The truck dispatching problem[J].Management Science，1959，6(1):80-91.

[2] Brand?o J.A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem[J].Computers＆ Operations Research，2011，38(1):140-151.

[3] Belfiore P C，Yoshizaki H T Y.Scatter search for a reallife heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil[J].European Journal of Operational Research，2009，199(3):750-758.

[4] Bettinelli A，Ceselli A，Righini G.A branch-and-cutand-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows[J].Transportation Research Part C:Emerging Technologies，2011，19(5):723-740.

[5] Azi N，Gendreau M，Potvin J.An exact algorithm for a single-vehicle routing problem with time windows and multiple routes[J].European Journal of Operational Research，2007，178(3):755-766.

[6] Xu L Y.A heuristic algorithm for the multi-period vehicle routing problem with simultaneous pickup and delivery service[D].Hong Kong:Hong Kong University of Science and Technology，2010.

[7] Wen M，Cordeau J，Laporte G，et al.The dynamic multi-period vehicle routing problem[J].Computers＆Operations Research，2010，37(1):1615-1623.

[8] Yuan Y，Wang D W.Path selection model and algorithm for emergency logistics management[J].Computers ＆ Industrial Engineering，2009，56(3):1081-1094.

[9] Wohlgemuth S，Oloruntoba R，Clausen U.Dynamic vehicle routing with anticipation in disaster relief[J].Socio-Economic Planning Sciences，2012，46(4):261-271.

[10] 石彪，池宏，祁明亮，等.應(yīng)急物資運(yùn)輸?shù)膬呻A段車輛調(diào)度模型[J].系統(tǒng)工程，2012，30(7):105-111.Shi Biao，Chi Hong，Qi Mingliang，et al.A two-stage vehicle scheduling model of transportation of emergency resources[J].Systems Engineering，2012，30(7):105-111.(in Chinese)