陳則輝,劉誠,呂品,劉葉飆
(1.南昌工學(xué)院經(jīng)濟(jì)管理學(xué)院,江西南昌330108;2.中南大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,湖南長沙410075)
近年來,重大自然災(zāi)害事件頻發(fā),相關(guān)應(yīng)急決策問題受到越來越多的關(guān)注[1-2]。應(yīng)急物資配送作為應(yīng)急救援過程中的一個重要環(huán)節(jié),成為應(yīng)急物流研究的重要課題。Gendreau等[3]考慮了受災(zāi)點(diǎn)位置不確定及受災(zāi)點(diǎn)的需求量是隨機(jī)數(shù)的車輛路徑問題,給出了求解該模型的禁忌搜索算法;Salmeron等[4]將多目標(biāo)規(guī)劃與隨機(jī)規(guī)劃結(jié)合運(yùn)用到解決人道主義物流設(shè)施擴(kuò)建、物資配送問題中;Changa等[5]研究了一個基于遺傳算法的多目標(biāo)應(yīng)急物資調(diào)度模型的貪婪算法,該算法可根據(jù)需求點(diǎn)的需求動態(tài)調(diào)整配送計(jì)劃,以減少資源浪費(fèi),縮短交付時間和降低運(yùn)輸成本;Novoa等[6]建立了隨機(jī)需求下車輛路徑模型,利用蒙特卡羅隨機(jī)模擬算法將隨機(jī)需求量轉(zhuǎn)化為確定性需求量,并給出了該模型的近似動態(tài)規(guī)劃算法;ZHANG[7]在不確定環(huán)境下建立了車輛路徑問題的模型;楊菊花等[8]運(yùn)用多式聯(lián)運(yùn)和路網(wǎng)的脆弱性理論,建立了應(yīng)急物資全程調(diào)拔時運(yùn)輸方式和路徑選擇問題的綜合模型;佟常青等[9]研究了城市交通背景下的軍隊(duì)?wèi)?yīng)急物資配送路徑優(yōu)化選擇問題,以軍隊(duì)?wèi)?yīng)急物資配送的時效性和安全性特征作為評價(jià)指標(biāo),建立了評價(jià)備選路徑的多目標(biāo)決策模型;YANG等[10]針對應(yīng)急車輛線路規(guī)劃,建立了多目標(biāo)數(shù)學(xué)規(guī)劃模型,并給出了合理有效的求解算法;蔡鑒明等[11]將時效性和可靠性作為應(yīng)急物流運(yùn)輸路徑選擇主要評價(jià)指標(biāo),構(gòu)建了預(yù)測和評價(jià)應(yīng)急物流運(yùn)輸路徑的多目標(biāo)決策模型;詹沙磊等[12]考慮了災(zāi)害預(yù)測準(zhǔn)確性和物流成本效率之間的悖反關(guān)系,從多目標(biāo)規(guī)劃和隨機(jī)規(guī)劃的角度,建立了應(yīng)急物資配送的多目標(biāo)隨機(jī)規(guī)劃模型;陳森等[13]利用時延要素和物資要素之間的轉(zhuǎn)換,同時考慮搶修毀損路段和車輛配送,實(shí)施路網(wǎng)結(jié)構(gòu)、車輛路徑聯(lián)合優(yōu)化,并求得了符合決策者意愿的配送體系,建立了該問題的聯(lián)合優(yōu)化模型;Ren等[14]在路網(wǎng)連通的不確定性條件下,建立了多種應(yīng)急物資配送的多周期動態(tài)運(yùn)輸模型。以上文獻(xiàn)大部分只是針對某一層面去考慮應(yīng)急物資配送問題,如文獻(xiàn)[6]只在需求為隨機(jī)數(shù)的條件下考慮VRP,文獻(xiàn)[14]只在路網(wǎng)不確定的條件下研究了應(yīng)急物資配送問題。而在以往的應(yīng)急物資配送問題研究中,對多個參數(shù)同為不確定數(shù)且同時以總時間滿意度最大及系統(tǒng)運(yùn)輸總成本最低為目標(biāo)的應(yīng)急物資配送問題的研究比較少。本文針對受災(zāi)點(diǎn)的需求量、車輛從配送中心到受災(zāi)點(diǎn)的運(yùn)行時間及單位運(yùn)輸成本為三角模糊數(shù),建立了總的時間懲罰成本最小和系統(tǒng)總運(yùn)輸費(fèi)用最省的雙目標(biāo)規(guī)劃模型,給出了模型的有效解法。
設(shè)有一個應(yīng)急配送中心O,擁有容量為q的車輛K輛,現(xiàn)有N個受災(zāi)地區(qū)向配送中心請求救災(zāi)物資配送,以1,2,…,N表示。本文將配送中心編號為0,各受災(zāi)點(diǎn)編號為1,2,…,N,受災(zāi)點(diǎn)及配送中心均已點(diǎn)i(i=1,2,…,N)表示,將這些點(diǎn)集記為:V={0,1,2,…,N}。已知第i個受災(zāi)點(diǎn)對于物資的需求量為(三角模糊數(shù)),且<q,否則對這個受災(zāi)點(diǎn)先進(jìn)行整車配送,直到剩余的需求量小于車輛的最大容量;RTi表示車輛到達(dá)受災(zāi)點(diǎn)i的時刻,STi表示車輛在受災(zāi)地i的卸貨時間;(三角模糊數(shù))表示車輛由地點(diǎn)i行駛到地點(diǎn)j的時間;(三角模糊數(shù))表示車輛從地點(diǎn)i行駛到地點(diǎn) j的單位費(fèi)用;dij(i,j∈V,且 i≠j)為地點(diǎn)i直接到達(dá)地點(diǎn)j的距離,且應(yīng)急配送中心與受災(zāi)點(diǎn)及受災(zāi)點(diǎn)與受災(zāi)點(diǎn)之間都有線路相通,即為完全網(wǎng)絡(luò),車輛從配送中心出發(fā),經(jīng)過一系列受災(zāi)點(diǎn)后返回配送中心;ETi為受災(zāi)點(diǎn)i感覺到滿意時所能接受的最長等待時間,LTi為受災(zāi)點(diǎn)i感覺到不滿意時的最短等待時間,即應(yīng)急物資在ETi之前送達(dá)受災(zāi)點(diǎn)i,受災(zāi)點(diǎn)i會感覺到滿意;應(yīng)急物資在(ETi,LTi]時間段內(nèi)送達(dá)受災(zāi)點(diǎn)i,受災(zāi)點(diǎn)i感覺到的滿意程度會逐漸降低;應(yīng)急物資在LTi之后送達(dá)受災(zāi)點(diǎn)i,對受災(zāi)點(diǎn)i來說沒有任何救援意義,其中ETi<LTi。為建立物資配送模型,定義如下變量:
時間在應(yīng)急物流活動中的至關(guān)重要,為此,針對應(yīng)急物流配送設(shè)定了2個救援時間分界點(diǎn)ETi和LTi,并針對時間分界點(diǎn)給出了符合應(yīng)急物流活動的時間懲罰成本的函數(shù):
式中:βi是時間敏感系數(shù),決策者可根據(jù)受災(zāi)點(diǎn)i對時間要求的嚴(yán)格程度給出適當(dāng)?shù)闹怠?/p>
根據(jù)以上描述,問題是如何選擇車輛運(yùn)行路線使得總的時間懲罰成本最小和系統(tǒng)運(yùn)輸總費(fèi)用最小。因此,建立以下模型:
模型(Ⅰ)
其中:目標(biāo)函數(shù)(1)表示所有受災(zāi)點(diǎn)時間滿意度之和;目標(biāo)函數(shù)(2)表示運(yùn)輸總費(fèi)用;約束條件(3)表示車輛的任務(wù)量必須小于車輛的容量;約束條件(4)表示應(yīng)急配送中心車輛總數(shù);約束條件(5)表示每一個受災(zāi)點(diǎn)的任務(wù)只能由1輛車完成;約束條件(6)和(7)表示到達(dá)和離開某一個受災(zāi)點(diǎn)的車輛有且只有1輛;約束條件(8)為支線消去約束,為了避免出現(xiàn)孤立圈;約束條件(9)表示每輛車從配送中心出發(fā)又回到配送中心;約束條件(10)表示到達(dá)受災(zāi)點(diǎn)j的時間要不早于到達(dá)受災(zāi)點(diǎn)i,為受災(zāi)點(diǎn)i的服務(wù)時間與受災(zāi)點(diǎn)i到受災(zāi)點(diǎn)j的行駛時間之和;約束條件(11)為0-1約束。
模型(Ι)是一個模糊規(guī)劃模型,為了求解該模型,需要將其轉(zhuǎn)化為確定性模型。
(1)將模型(Ι)中三角模糊參數(shù)轉(zhuǎn)化為確定性參 數(shù),由 Pishvaee[15],定 義 三 角 模 糊 數(shù)的隸屬函數(shù):
(2)結(jié)合三角模糊數(shù)的性質(zhì),給出以下隨機(jī)模擬算法:
Step3:重復(fù)step1和step2 M次(M為一個較大的正整數(shù)),取σ的平均值即可等價(jià)于模糊數(shù)。
模型(Ⅱ)
其他約束條件與模型(Ι)相同。
模型(Ⅱ)是一個NP-難問題,首先將模型轉(zhuǎn)化為單目標(biāo)規(guī)劃模型。由于2個目標(biāo)函數(shù)的量綱相同,可將雙目標(biāo)進(jìn)行線性加權(quán)轉(zhuǎn)化為單目標(biāo),于是模型(Ⅱ)中雙目標(biāo)函數(shù)可轉(zhuǎn)化為:
在以上基礎(chǔ)上,給出以下C-W節(jié)約算法:
Step 1:求配送中心到各受災(zāi)點(diǎn)、受災(zāi)點(diǎn)到受災(zāi)點(diǎn)的最短距離;
Step 2:根據(jù)節(jié)約量公式 s1(i,j)=c0id0i+cj0dj0-cijdij,計(jì)算連接點(diǎn)對后運(yùn)輸成本節(jié)約量值,令M1={s1(i,j)}。本文模型考慮車輛最后是空載回到配送中心的情況,所以運(yùn)輸成本不是對稱成本,s1(j,i)≠s1(i,j)在計(jì)算節(jié)約量時還要算 s1(j,i)=c0jd0j+ci0di0-cjidij;
Step 3:將配送中心到各受災(zāi)點(diǎn)的模糊運(yùn)行時間轉(zhuǎn)化為時間平均數(shù),根據(jù)時間懲罰成本函數(shù),計(jì)算出
Step 4:計(jì)算時間成本節(jié)約量,連接受災(zāi)點(diǎn)i和j后,車輛到達(dá)受災(zāi)點(diǎn)j的時間為STi,計(jì)算Pi,從而根據(jù)節(jié)約量的計(jì)算公式可得:s2(i,j)=P0i+Poj- P0i- Pj=Poj- Pj,通過此式可以計(jì)算出受災(zāi)點(diǎn)對連接后的時間滿意度懲罰成本節(jié)約量;
Step 5:根據(jù)公式 s(i,j)= ωs1(i,j)+(1 -ω)s2(i,j),計(jì)算總的節(jié)約量 s(i,j),記M={s(i,j)|s(i,j)≥ 0};
Step 6:在M中按照s(i,j)從大到小進(jìn)行排序,逐項(xiàng)檢查對應(yīng)的受災(zāi)點(diǎn)之間的連接,在M中取s(i,j)最大的受災(zāi)點(diǎn)對,判斷這2個受災(zāi)點(diǎn)所需貨物之和是否超過車輛的最大載重量,若超過,則這2個受災(zāi)點(diǎn)不能在同一條配送線路上;若不超過,則連接i和j,形成線路0→i→j→0,并在M中刪除以i為前的受災(zāi)點(diǎn)對(i,*)和以j為后的受災(zāi)點(diǎn)對(*,j);
Step 7:在M的剩余受災(zāi)點(diǎn)對中取s(i,j)最大的受災(zāi)點(diǎn)對:
(1)如果該點(diǎn)對中的受災(zāi)點(diǎn)均不在已構(gòu)成的線路上,則重復(fù)Step7的操作;
(2)如果該點(diǎn)對中的前外受災(zāi)點(diǎn)是已構(gòu)成的線路上的后外受災(zāi)點(diǎn),即出現(xiàn)受災(zāi)點(diǎn)對(j,k)時,則形成線路0→i→j→k→0,判斷該線路中車輛是否超載,若超載則受災(zāi)點(diǎn)j和k不予連接,并在M中刪除s(j,k),若沒有超載,準(zhǔn)予連接受災(zāi)點(diǎn)j和k;
(3)如果該受災(zāi)點(diǎn)對中的后外點(diǎn)是已構(gòu)成的線路上的后外受災(zāi)點(diǎn),即出現(xiàn)點(diǎn)對(u,i)時,則形成線路0→u→i→j→0,判斷該線路中車輛是否超載,若超載則受災(zāi)點(diǎn)u和受災(zāi)點(diǎn)i不予連接,并在M中刪除s(u,i),若沒有超載,準(zhǔn)予連接受災(zāi)點(diǎn)u和受災(zāi)點(diǎn)i;
Step 8:在M中剩下的受災(zāi)點(diǎn)對中選擇節(jié)約量最大的受災(zāi)點(diǎn)對,重復(fù)Step 6-Step 7,當(dāng)產(chǎn)生出一條線路時,在M中刪除所有與該線路上受災(zāi)點(diǎn)的相關(guān)連接;直至M為空集。
假設(shè)某次自然災(zāi)害中,某個配送中心需向8個受災(zāi)點(diǎn)運(yùn)送應(yīng)急救災(zāi)物資,具體數(shù)據(jù)見表1~表5(三角模糊數(shù)和已根據(jù)隨機(jī)模擬算法轉(zhuǎn)化為確定數(shù)和)。
表1 受災(zāi)點(diǎn)的相關(guān)數(shù)據(jù)Table 1 Relevant data of each disaster area
表2 配送中心到受災(zāi)點(diǎn)、受災(zāi)點(diǎn)到受災(zāi)點(diǎn)的運(yùn)行時間Table 2 Running time from distribution center to each disaster area and the running time from disaster area to disaster area
表3 時間敏感系數(shù)Table 3 Time sensitive coefficient
表4 配送中心到受災(zāi)點(diǎn)、受災(zāi)點(diǎn)到受災(zāi)點(diǎn)的運(yùn)費(fèi)Table 4 Transportation cost from distribution center to each disaster area and transportation cost from disaster area to disaster area
表5 配送中心到受災(zāi)點(diǎn)、受災(zāi)點(diǎn)到受災(zāi)點(diǎn)的最短距離Table 5 Minimum distance from distribution center to each disaster area and minimum distance from disaster area to disaster area
由于本文考慮的是應(yīng)急物資配送問題,故時間滿意度應(yīng)重點(diǎn)考慮,故取ω=0.8,另取P=10,K=4,q=12,用隨機(jī)模擬算法將以上模糊數(shù)轉(zhuǎn)化為確定數(shù),再運(yùn)用以上C-W算法可得如下結(jié)果:
(1)受災(zāi)點(diǎn)對連接的距離成本節(jié)約量s1(i,j)按從大到小順序排列如表6所示。
表6 運(yùn)輸成本節(jié)約量Table 6 Savings of transportation cost
(2)受災(zāi)點(diǎn)對連接的時間懲罰成本節(jié)約量s2(i,j)按從大到小順序排列如表7所示。
表7 時間懲罰成本節(jié)約量Table 7 Savings of time penalty cost
(3)當(dāng)ω=0.8時,受災(zāi)點(diǎn)對連接的加權(quán)后總成本節(jié)約量s(i,j)按從大到小順序排列如表8所示。
(4)由表8可得以下車輛路徑,見圖1。
圖1 車輛路徑運(yùn)行圖Fig.1 Vehicles running diagram
此時節(jié)約總量為351.685千元。
由于決策者的偏好或者具體情況的不同,當(dāng)ω取值不同時,決策方案也不同,以下列舉出幾種ω的值,所得出的結(jié)果圖2所示。
圖2 不同權(quán)重ω所對應(yīng)的節(jié)約量Fig.2 Savings corresponding to different weights ω
由圖2可知:隨著權(quán)重值ω的增加,物流配送系統(tǒng)的總節(jié)約量總體趨勢是越來越小,故決策者應(yīng)根據(jù)實(shí)際災(zāi)情,選擇合適的權(quán)重值,在保證合理時間滿意度的前提下,適當(dāng)降低物流系統(tǒng)成本。
(1)假定受災(zāi)點(diǎn)的需求量、車輛從配送中心到受災(zāi)點(diǎn)的運(yùn)行時間及單位成本為三角模糊數(shù)的應(yīng)急物資配送問題,建立了系統(tǒng)總費(fèi)用最小和總的時間懲罰成本最小的雙目標(biāo)規(guī)劃模型。
(2)通過算法和算例分析表明,最優(yōu)的車輛路徑的決策方案與權(quán)重值ω關(guān)系密切,故決策者在決策時應(yīng)根據(jù)實(shí)際情況選擇合適的權(quán)重值ω,這對應(yīng)急物流配送問題有一定的借鑒意義。
(3)本文只考慮了單個配送中心、單物資配送問題以及將不確定因素定位在三角模糊數(shù),而在現(xiàn)實(shí)的應(yīng)急物流配送中往往是多配送中心、多種應(yīng)急物資以及多種不確定數(shù)(模糊數(shù)、隨機(jī)數(shù)等),這將是應(yīng)急物資配送下一步的研究內(nèi)容。
[1]Sheu J B.Dynamic material-demand management for emergency logistics operations under large-scale disasters[J].Transportation Research Part E,2010,46(1):1 -17.
[2]HU Zhihua.A container multimodal transportation scheduling approach based on immune affinity model for emergency material[J].Expert Systems with Applications,2011,38(3):2632 -2639.
[3]Salmeron J,Apte A.Stochastic optimization for natural disaster asset prepositioning[J].Production and Operations Management,2010,19(5):561 - 574.
[4]Genderau M,Gilbert L.A tabu search heuristic for the vehicle routing problem with stochastic demands and customers[J].Operations Research,1996,4(23):469 -477.
[5]Changa F S,Wua J S,Leea C N,et al.Greedy-search-based multi-objective genetic algorithm for emergency logistics scheduling[J].Expert Systems with Applications,2014,41(6):2947 -2956.
[6]Novoa C,Robert S.An approximate dynamic programming approach for the vehicle routing problem with stochastic demands[J].European Journal of Operational Research,2009,196(2):509-515.
[7]ZHANG Jing.Control of the supply chain optimization with vehicle scheduling of logistics under uncertain systems[J].Procedia Environmental Sciences,2012,12(Part B):1440-1445.
[8]楊菊花,朱昌鋒,田志強(qiáng).基于蟻群算法的應(yīng)急物資運(yùn)輸路徑優(yōu)化[J].鐵道科學(xué)與工程學(xué)報(bào),2012,9(6):90-94.
YANG Juhua,ZHU Changfeng,TIAN Zhiqiang.Trans-port path optimization for emergency material based on ant colony algorithm[J].Journal of Railway Science and Engineering,2012,9(6):90 -94.
[9]佟常青,王景國,陳博文.軍隊(duì)?wèi)?yīng)急物資配送備選路徑優(yōu)化多目標(biāo)規(guī)劃模型研究[J].物流技術(shù),2010,29(2):206-208.
TONG Changqing,WANG Jingguo,CHEN Bowen.A multi-objective programming model of routing optimization for military emergency material distribution[J].Logistics Technology,2010,29(2):206 -208.
[10]LIU Yang,YUN Meiping,PENG Guoxiong.A multiobjective programming model of route choice of emergency vehicles before travel[J].Journal of Highway and Transportation Research and Development,2009,26(8):135-139.
[11]蔡鑒明,李夏苗,楊光華.基于時變性和可靠性的地震災(zāi)害應(yīng)急物流運(yùn)輸路徑選擇[J].鐵道科學(xué)與工程學(xué)報(bào),2011,8(5):101 -106.
CAI Jianming,LI Xiamiao,YANG Guanghua.The routing problem for emergency logistics considering the reliability and time-varying in the earthquake disasters[J].Journal of Railway Science and Engineering,2011,8(5):101 -106.
[12]詹沙磊,劉南.基于災(zāi)情信息更新的應(yīng)急物資配送多目標(biāo)隨機(jī)規(guī)劃模型[J].系統(tǒng)工程理論與實(shí)踐,2013,33(1):159-166.
ZHAN Shalei,LIU Nan.Multi - objective stochastic programming model for material allocation based on disaster scenario information updates[J].Systems Engineering-Theory& Practice,2013,33(1):159-166.
[13]陳森,姜江,陳英武.未定路網(wǎng)結(jié)構(gòu)情況下應(yīng)急物資車輛配送問題模型與應(yīng)用[J].系統(tǒng)工程理論與實(shí)踐,2011,31(5):907 -913.
CHEN Sen,JIANG Jiang,CHEN Yingwu.Emergency logistics distribution problem model under uncertain roadway network structure and its application[J].Systems Engineering-Theory& Practice,2011,31(5):907-913.
[14]Ren Xide,Zhu Jianming,Huang Jun.Multi- period dynamic model for emergency resource dispatching problem in uncertain traffic network systems[J].Engineering Procedia,2012,22(5):37 -42.
[15]Pishvaee M S,Torabi S A.A possibilistic programming approach for closed-loop supply chain network design under uncertainty[J].Fuzzy Sets and Systems,2010,161(20):2668-2683.