考慮救援點(diǎn)資源分布的救援車輛路徑優(yōu)化

韓亞娟,楊宇航,彭運(yùn)芳

(上海大學(xué)管理學(xué)院,上海200444)

應(yīng)急物資調(diào)度是應(yīng)急保障體系中的重要一環(huán).當(dāng)大規(guī)模突發(fā)事件爆發(fā)后,應(yīng)急物資必須在盡可能短的時(shí)間內(nèi)運(yùn)達(dá)各受災(zāi)點(diǎn).近年來,國(guó)內(nèi)外對(duì)應(yīng)急物資調(diào)度問題的研究逐漸深入,并取得了較為豐富的研究成果.Wang等[1]研究了確定需求下應(yīng)急物流的開放式車輛路徑問題.Ceselli等[2]研究了藥品配送中的選址和車輛路徑問題.Wohlgemuth等[3]研究了確定需求條件下應(yīng)急救援車輛動(dòng)態(tài)路徑問題.Lei等[4]對(duì)隨機(jī)需求環(huán)境下的車輛路徑問題進(jìn)行了研究.上述研究多建立在車輛物資足夠多的情況下,較少地考慮資源有限性.程碧榮等[5]針對(duì)救援期內(nèi)物資供應(yīng)可能不足的特點(diǎn),考慮隨機(jī)需求并建立了應(yīng)急救援車輛路徑模型.石彪等[6]針對(duì)大規(guī)模突發(fā)事件爆發(fā)后應(yīng)急物資運(yùn)輸車輛不足的情況,建立了兩階段應(yīng)急物資配送模型,有效提升了應(yīng)急物資運(yùn)輸車輛的使用效率.馬祖軍等[7]和代穎等[8-9]綜合考慮應(yīng)急物資需求的模糊性、限制期和多次往返配送,研究了一類多目標(biāo)開放式定位路徑問題.另外,劉長(zhǎng)石等[10]以應(yīng)急物資運(yùn)達(dá)時(shí)間最短和總成本最優(yōu)為目標(biāo)函數(shù),構(gòu)建了多目標(biāo)模糊優(yōu)化模型,重點(diǎn)考慮了受災(zāi)點(diǎn)的情況.廖成等[11]設(shè)計(jì)了一種多模式分層網(wǎng)絡(luò),并利用延期費(fèi)用和劃分時(shí)段的方法構(gòu)建了應(yīng)急物資車輛路徑的多目標(biāo)數(shù)學(xué)規(guī)劃模型.何正文等[12]考慮了交通網(wǎng)絡(luò)的道路和節(jié)點(diǎn)帶有禁止時(shí)間窗的情況,以減少應(yīng)急物資的調(diào)運(yùn)時(shí)間為目標(biāo)構(gòu)建了整數(shù)規(guī)劃模型.基于上述分析可知,目前對(duì)于應(yīng)急救援車輛路徑優(yōu)化的研究,多是直接定位于受災(zāi)點(diǎn)的具體情況,而較少考慮救援點(diǎn)的特殊情形.如果災(zāi)害發(fā)生初期物資總量有限,且各個(gè)救援點(diǎn)的物資量與車輛運(yùn)輸能力比值有顯著差別,那么某些救援點(diǎn)的物資輸出效率則會(huì)成為瓶頸,無法使總體救援時(shí)間最短.因此,本工作考慮在救援系統(tǒng)中構(gòu)建一個(gè)物資集散區(qū)以協(xié)調(diào)救援系統(tǒng)內(nèi)各個(gè)救援點(diǎn)的資源,從而達(dá)到優(yōu)化救援效率的目的.

1 問題描述

重大災(zāi)害爆發(fā)后,需在盡可能短的時(shí)間內(nèi)將應(yīng)急物資配送到各個(gè)受災(zāi)點(diǎn).本工作假設(shè)有多個(gè)地理位置已知的受災(zāi)點(diǎn)和救援點(diǎn),這些救援點(diǎn)的物資總量略多于受災(zāi)點(diǎn)物資總需求量,且救援點(diǎn)的物資量與車輛運(yùn)輸能力比值不平衡,各個(gè)救援點(diǎn)的救援車輛無權(quán)限前往其他救援點(diǎn).在上述特定情形下,本工作考慮在救援系統(tǒng)內(nèi)部構(gòu)建一個(gè)物資集散區(qū)來平衡各個(gè)救援點(diǎn)的物資量與車輛運(yùn)輸能力.基于此,救援車輛分為兩類:第一類車輛負(fù)責(zé)將物資從救援點(diǎn)運(yùn)達(dá)物資集散區(qū),第二類車輛直接參與救援,若救援物資不足,則救援車輛從物資集散區(qū)處獲取物資以完成剩余任務(wù).決策問題是確定每個(gè)救援車輛的路徑,使所有受災(zāi)點(diǎn)都得到救援的時(shí)間最短.

第一類車輛把物資從救援點(diǎn)運(yùn)往物資集散區(qū),每次載運(yùn)物資量為車輛容量.若到達(dá)救援點(diǎn)時(shí)救援過程未完成且救援點(diǎn)物資量不足,則該類車輛載運(yùn)量為其所屬救援點(diǎn)的剩余物資量.第二類車輛在初始階段滿載離開救援點(diǎn)并直接參與受災(zāi)點(diǎn)的救援,其路徑規(guī)則如下:開始階段車輛從其所屬救援點(diǎn)出發(fā)到達(dá)救援任務(wù)的第一個(gè)受災(zāi)點(diǎn),然后按照救援順序繼續(xù)救援下一個(gè)受災(zāi)點(diǎn);若到達(dá)某受災(zāi)點(diǎn)時(shí)無法滿足該受災(zāi)點(diǎn)物資需求,則車輛從該受災(zāi)點(diǎn)出發(fā)到物資集散區(qū)獲取物資并原路返回繼續(xù)救援.第二類救援車輛每次從物資集散區(qū)獲取的物資量規(guī)則如下:若救援車輛非最后一次去物資集散區(qū),則獲取物資量為車輛容量;若救援車輛最后一次去物資集散區(qū),則該次從物資集散區(qū)獲取的物資量只需滿足救援任務(wù)中后續(xù)受災(zāi)點(diǎn)的物資需求即可.救援車輛在物資集散區(qū)的排隊(duì)規(guī)則如下:先到車輛的物資需求量必須被滿足的情況下,后到車輛才能獲取物資.另外為便于建立模型,假設(shè)任意兩輛車不會(huì)同時(shí)到達(dá)物資集散區(qū).

基于上述路徑規(guī)則,本工作中救援車輛的路徑模式如圖1表示.假設(shè)存在3個(gè)受災(zāi)點(diǎn)和2個(gè)救援點(diǎn),其中救援點(diǎn)S1擁有車輛1和車輛2,救援點(diǎn)S2擁有車輛3和車輛4.救援點(diǎn)S1的車輛2去物資集散區(qū)B1,而車輛1先到受災(zāi)點(diǎn)P1,再到受災(zāi)點(diǎn)P2.在到達(dá)受災(zāi)點(diǎn)P2時(shí)發(fā)現(xiàn)物資不足,則前往物資集散區(qū)B1獲取物資并原路返回.救援點(diǎn)S2的車輛3去物資集散區(qū)B1,而車輛4先到受災(zāi)點(diǎn)P3,發(fā)現(xiàn)物資不足,接著去物資集散區(qū)B1獲取物資并原路返回.在本例中,救援點(diǎn)S1的車輛1和救援點(diǎn)S2的車輛4屬于第二類車輛,而救援點(diǎn)S1的車輛2和救援點(diǎn)S2的車輛3屬于第一類車輛.

圖1 救援車輛的路徑模式Fig.1 Path pattern of rescue vehicle

2 數(shù)學(xué)模型

2.1 參數(shù)與變量

為便于描述,定義如下參數(shù):V為車輛集合,v為救援車輛,vmax為車輛總數(shù),D為受災(zāi)點(diǎn)集合,d為受災(zāi)點(diǎn),S為救援點(diǎn)集合,s為救援點(diǎn);td為受災(zāi)點(diǎn)d到物資集散區(qū)的時(shí)間,ts為救援點(diǎn)s到物資集散區(qū)的時(shí)間,tsd為救援點(diǎn)s到受災(zāi)點(diǎn)d的時(shí)間,td′d為受災(zāi)點(diǎn)到受災(zāi)點(diǎn)d的時(shí)間;rs為救援點(diǎn)s的物資擁有量,rd為受災(zāi)點(diǎn)d的物資需求量,rv為車輛v的容量;

定義V1為直接參與救援的車輛集合,vn為車輛v救助受災(zāi)點(diǎn)的個(gè)數(shù),dvi為車輛v第i次救助的受災(zāi)點(diǎn),cvi為救援車輛v第i次對(duì)受災(zāi)點(diǎn)救援時(shí)需要去物資集散區(qū)的次數(shù);為救援車輛v第i次對(duì)受災(zāi)點(diǎn)救援時(shí)第c次到達(dá)物資集散區(qū)的時(shí)間;為救援車輛v第i次對(duì)受災(zāi)點(diǎn)救援時(shí)第c次離開物資集散區(qū)的時(shí)間,為救援車輛v第i次對(duì)受災(zāi)點(diǎn)救援時(shí)第c次需要從物資集散區(qū)獲取的物資量,lvi為救援車輛v從第i次救援的受災(zāi)點(diǎn)離開時(shí)所攜帶的剩余物資量;fs(x)為救援點(diǎn)s到達(dá)物資集散區(qū)的物資量函數(shù);

決策變量如下:

2.2 函數(shù)定義

為便于建立模型,定義兩個(gè)函數(shù).

定義1 若函數(shù)f(x)滿足對(duì)任意的x1＜x2,有f(x1)≤f(x2),則定義函數(shù)

函數(shù)y的含義為:若存在a使得f(a)≥θ,且對(duì)于任意滿足f(b)≥θ的b都有a≤b,則y=a.

定義2 假設(shè)任何兩輛車不會(huì)同時(shí)到達(dá)物資集散區(qū),故以每輛車每次到達(dá)物資集散區(qū)的時(shí)間為自變量,以該車該次需要從物資集散區(qū)獲取的物資量為因變量,構(gòu)造函數(shù)

由函數(shù)(2),可根據(jù)每輛車每次到達(dá)物資集散區(qū)的時(shí)間對(duì)應(yīng)得出該車該次需要從物資集散區(qū)獲取的物資量.

2.3 模型構(gòu)建

所有受災(zāi)點(diǎn)都得到救援的時(shí)間一共包含4部分.

(1)救援車輛從起始救援點(diǎn)出發(fā)到第一個(gè)受災(zāi)點(diǎn)的時(shí)間

(2)受災(zāi)點(diǎn)之間的運(yùn)輸時(shí)間

(3)從受災(zāi)點(diǎn)到物資集散區(qū)的往返時(shí)間

(4)救援車輛在物資集散區(qū)的等待時(shí)間)

總的目標(biāo)函數(shù)和約束條件如下:

式(7)表示模型的優(yōu)化目標(biāo)為救援時(shí)間最短.式(8)和(9)表示同一輛車只能參與一個(gè)任務(wù).式(10)表示一個(gè)受災(zāi)點(diǎn)只能被一輛車救援.式(11)表示車輛的路徑分配必須使救援點(diǎn)能夠滿足受災(zāi)點(diǎn)的物資需求.式(12)表示所有車輛在救援第一個(gè)受災(zāi)點(diǎn)時(shí)需要去物資集散區(qū)的次數(shù)約束.式(13)表示所有車輛在救援非第一個(gè)受災(zāi)點(diǎn)時(shí)需要去物資集散區(qū)的次數(shù)約束.式(14)表示救援車輛每次從物資集散區(qū)獲取的物資量約束.式(15)表示救援車輛到達(dá)物資集散區(qū)的時(shí)間約束.式(16)表示救援車輛離開物資集散區(qū)的時(shí)間約束.式(17)表示救援車輛從受災(zāi)點(diǎn)離開時(shí)所攜帶的剩余物資量約束.

3 模擬退火算法設(shè)計(jì)

本工作采用模擬退火算法[13-16]求解車輛的救援路徑.基于文獻(xiàn)[17],本工作設(shè)計(jì)了一種解的表示方法.假設(shè)受災(zāi)點(diǎn)有M個(gè),首先設(shè)置M個(gè)位點(diǎn),每個(gè)位點(diǎn)與每個(gè)受災(zāi)點(diǎn)對(duì)應(yīng).每個(gè)位點(diǎn)由兩個(gè)數(shù)字表示,第一個(gè)數(shù)字代表服務(wù)于該受災(zāi)點(diǎn)的車輛,第二個(gè)數(shù)字代表該車輛第幾步服務(wù)于該點(diǎn).結(jié)果會(huì)構(gòu)造長(zhǎng)度為2M的解,該解遵循兩個(gè)原則:①該解不能包含所有車輛,因?yàn)楸仨氂胁糠周囕v服務(wù)于物資集散區(qū);②若某車輛在初始解中出現(xiàn)過N次,則從1到N的N個(gè)整數(shù)必須分別出現(xiàn)在該車輛對(duì)應(yīng)位點(diǎn)的第二個(gè)數(shù)字中.例如,編號(hào)分別為1,2,3,4的4個(gè)受災(zāi)點(diǎn)需要救援,那么32222131代表的是3號(hào)車輛路徑為4-1,2號(hào)車輛路徑為3-2.

3.1 解的評(píng)價(jià)

求解組合優(yōu)化問題,需要對(duì)解進(jìn)行相關(guān)評(píng)價(jià),使算法在迭代過程中不斷搜索到質(zhì)量更優(yōu)的解.本工作中解的表示方式隱含能夠滿足一個(gè)受災(zāi)點(diǎn)只接受一個(gè)車輛的救援,但無法滿足受災(zāi)點(diǎn)的物資需求量約束.假設(shè)受災(zāi)點(diǎn)的總物資需求量為某條不可行路徑中救援點(diǎn)一共可以提供的物資量為若則該解為可行解;若則該解為不可行解.設(shè)該不可行解的目標(biāo)函數(shù)值為Z,且對(duì)每條不可行路徑的懲罰權(quán)重為Pλ,則該解的評(píng)價(jià)值為

3.2 鄰域操作

采用隨機(jī)替換的方法進(jìn)行鄰域操作,具體操作過程如下.

步驟1 在總車輛集合V中隨機(jī)挑選一輛救援車輛v1,在當(dāng)前解所包含車輛集合中隨機(jī)抽取一輛救援車輛v2,判斷v1=v2是否成立.是,重復(fù)此步驟;否則,轉(zhuǎn)步驟2.

步驟3 找出v2最后一次服務(wù)的受災(zāi)點(diǎn),把該受災(zāi)點(diǎn)的車輛替換為v1,轉(zhuǎn)步驟4.

步驟4判斷v1在該受災(zāi)點(diǎn)的服務(wù)次序.若則其次序?yàn)?;若且v1在中最大的服務(wù)次序?yàn)?則在新解中v1在該受災(zāi)點(diǎn)的服務(wù)次序?yàn)?/p>

上述步驟1是為避免產(chǎn)生相同解,步驟2保證至少有部分車輛為物資集散區(qū)提供物資.

3.3 實(shí)現(xiàn)過程

模擬退火算法的具體實(shí)現(xiàn)過程如下.

步驟1 按照解的表示方式構(gòu)造算法初始解.

步驟2 按照上述鄰域操作方法的步驟進(jìn)行.

步驟3 采用固定比率方式降溫,即tk+1=a·tk,其中a為降溫系數(shù).

步驟4 采用固定的迭代步長(zhǎng),步長(zhǎng)根據(jù)問題的規(guī)模確定.

步驟5 在溫度下降指定次數(shù)后終止運(yùn)算.

3.4 算法分析

模擬退火算法設(shè)計(jì)了較為直觀的解結(jié)構(gòu),能夠間接要求兩種救援任務(wù)必須都有車輛參與,有效分配相關(guān)任務(wù)給對(duì)應(yīng)車輛,以應(yīng)對(duì)救援系統(tǒng)中的救援點(diǎn)資源分布不平衡情況.在鄰域操作步驟中,迭代過程能夠保持解的結(jié)構(gòu)不變,且該過程可在時(shí)間復(fù)雜度不超過O(n2)的情形下完成運(yùn)算.

4 算例

4.1 仿真數(shù)據(jù)

為簡(jiǎn)化運(yùn)算,依據(jù)基本規(guī)則生成一個(gè)具有11個(gè)受災(zāi)點(diǎn)(P1～P11)、2個(gè)救援點(diǎn)(S1,S2)和2個(gè)候選物資集散區(qū)(B1,B2)的救援網(wǎng)絡(luò).A車型容量為9.0 t,B車型容量為7.2 t,C車型容量為6.3 t.救援點(diǎn)S1的A車型車輛編號(hào)分別為1,2,3,B車型車輛編號(hào)分別為4,5,C車型車輛編號(hào)為6.救援點(diǎn)S2的A車型車輛編號(hào)為7,C車型車輛編號(hào)分別為8,9.救援點(diǎn)的物資總量為111 t,受災(zāi)點(diǎn)的物資需求總量為99 t,可認(rèn)為救援點(diǎn)物資總量略多于受災(zāi)點(diǎn)物資需求總量.本實(shí)例其他相關(guān)數(shù)據(jù)如表1和表2所示.

表1 初始點(diǎn)坐標(biāo)及相關(guān)數(shù)據(jù)Table 1 Coordinates of each point and other related data

4.2 平衡性評(píng)價(jià)指標(biāo)

將救援點(diǎn)的物資量與車輛運(yùn)輸能力比值作為該救援點(diǎn)的資源平衡性評(píng)價(jià)指標(biāo),有

式中,rs為該救援點(diǎn)的物資所有量,為該救援點(diǎn)的車輛容量之和為該救援點(diǎn)到所有受災(zāi)點(diǎn)的時(shí)間之和.

表2 各點(diǎn)間的行程時(shí)間Table 2 Travel time between points min

為判斷兩個(gè)救援點(diǎn)S1與S2的資源分布平衡性差異,定義指標(biāo)

4.3 運(yùn)行結(jié)果

本工作取初始溫度260°C,降溫速率0.98,降溫次數(shù)200,每個(gè)溫度迭代80次.使用JAVA編程,隨機(jī)運(yùn)行20次,兩個(gè)物資集散區(qū)對(duì)應(yīng)的最優(yōu)解如表3和表4所示.

表 3 B1最優(yōu)解Table 3 Optimum solution of B1

表 4 B2最優(yōu)解Table 4 Optimum solution of B2

由表3和表4可知，在最優(yōu)解對(duì)應(yīng)的車輛路徑中,救援點(diǎn)S1中的車輛多作為第二類車輛參與受災(zāi)點(diǎn)的救援,而救援點(diǎn)S2中的車輛多作為第一類車輛把救援點(diǎn)的物資運(yùn)往物資集散區(qū).該算例表明,基于物資集散區(qū)的車輛路徑優(yōu)化方法適用于救援點(diǎn)資源分布不平衡的情況.通過物資集散區(qū)的協(xié)調(diào),一些物資量相對(duì)較大的救援點(diǎn)可以將物資配送到物資集散區(qū),供第一類車輛使用;而車輛運(yùn)輸能力強(qiáng)的救援點(diǎn)可以將其車輛作為第一類車輛使用.另外,物資集散區(qū)B1和物資集散區(qū)B2對(duì)應(yīng)的最優(yōu)解分別為154.8 min和126.0 min,說明選擇地理位置較好的物資集散區(qū)會(huì)改善救援效果.

5 結(jié)束語(yǔ)

在考慮物資集散區(qū)的基礎(chǔ)上,本工作將所有救援點(diǎn)車輛分為兩類:一類負(fù)責(zé)把物資從救援點(diǎn)運(yùn)到物資集散區(qū),另一類參與受災(zāi)點(diǎn)的救援.研究結(jié)果表明,本工作提出的車輛路徑優(yōu)化方法適用于資源分布不平衡的情形,能夠改善救援的效率.但是,在各個(gè)救援點(diǎn)的物資量與其車輛運(yùn)輸能力相對(duì)平衡時(shí),基于物資集散區(qū)的車輛路徑優(yōu)化方法效果不顯著.

本工作僅考慮了單個(gè)物資集散區(qū).當(dāng)存在多個(gè)物資集散區(qū)時(shí),部分救援點(diǎn)分需求的物資集散區(qū)如何分配才能達(dá)到最優(yōu)救援效率,是下一步的研究?jī)?nèi)容.另外,本工作中的排序規(guī)則僅考慮了救援車輛到達(dá)時(shí)間,并沒有考慮救援車輛獲取的物資量大小和其他具體因素,如何更改救援車輛在物資集散區(qū)的排序規(guī)則來改善救援效率也是需要進(jìn)一步研究的.