應(yīng)急車(chē)輛分配與應(yīng)急物資配送的集成決策

王莉，周鮮成，趙志學(xué)，劉利枚，余伶俐

?

應(yīng)急車(chē)輛分配與應(yīng)急物資配送的集成決策

王莉1，周鮮成2，趙志學(xué)1，劉利枚1，余伶俐3

(1. 湖南商學(xué)院 計(jì)算機(jī)與信息工程學(xué)院，湖南 長(zhǎng)沙，410025；2. 湖南商學(xué)院 湖南省移動(dòng)電子商務(wù)協(xié)同創(chuàng)新中心，湖南 長(zhǎng)沙，410025；3. 中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙，410083)

針對(duì)應(yīng)急物資配送中各受災(zāi)點(diǎn)應(yīng)急車(chē)輛分配的公平性與應(yīng)急物資配送的及時(shí)性難以平衡的問(wèn)題，以各受災(zāi)點(diǎn)車(chē)輛分配的相對(duì)剝奪感(公平性)與配送時(shí)間(及時(shí)性)為目標(biāo)函數(shù)，構(gòu)建基于車(chē)輛分配公平性與應(yīng)急物資配送及時(shí)性的多目標(biāo)協(xié)調(diào)優(yōu)化模型。為求解該模型，設(shè)計(jì)一種基于啟發(fā)式算法、局部搜索算法和遺傳算法的混合智能算法。研究結(jié)果表明：當(dāng)配送中心車(chē)輛數(shù)不足時(shí)，公平性和及時(shí)性之間存在關(guān)聯(lián)；該混合智能算法能快速、有效地找到滿意解；目標(biāo)權(quán)重對(duì)算法的穩(wěn)定性和快速性有一定影響；該模型和算法在大規(guī)模地震實(shí)例中能有效實(shí)現(xiàn)公平性與及時(shí)性的協(xié)調(diào)優(yōu)化。

應(yīng)急物資配送；相對(duì)剝奪感；公平性；及時(shí)性；協(xié)調(diào)優(yōu)化

自進(jìn)入21世紀(jì)以來(lái)，全球自然災(zāi)害頻發(fā)，給人民群眾造成了巨大的生命財(cái)產(chǎn)損失。由于各個(gè)受災(zāi)點(diǎn)的受災(zāi)情況和地理位置不同，受災(zāi)群眾對(duì)救援物資的需求以及物資運(yùn)達(dá)時(shí)間的期望也不同。為了第一時(shí)間滿足受災(zāi)群眾的基本物資需要，安撫各受災(zāi)點(diǎn)群眾，制定出科學(xué)、合理的方案，以提高車(chē)輛分配的公平性與物資配送的及時(shí)性是非常必要的。目前，國(guó)內(nèi)外關(guān)于應(yīng)急物資配送的公平性研究主要針對(duì)物資分配，追求的是物資需求滿足的最大化或者公平損失的最小化。馬衛(wèi)峰等[1]建立了以物資分配量最大和最小滿意度的多目標(biāo)數(shù)學(xué)模型，實(shí)現(xiàn)救災(zāi)物資在災(zāi)區(qū)的合理、公平分配。CHANTA等[2]以基尼系數(shù)公平性指標(biāo)建立了多目標(biāo)規(guī)劃模型，采用鄰域搜索算法求解。馮春等[3]以各周期懲罰成本最小化建立了多周期應(yīng)急物資配送的公平性模型，采用混合整數(shù)線性規(guī)劃算法求解。張錦等[4]建立了基于變權(quán)的資源分配公平性模型，以效率損失和公平損失最小為目標(biāo)，分析了變權(quán)參數(shù)對(duì)公平的影響。BEHESHTI等[5]建立了以顧客滿意度最大化為優(yōu)化目標(biāo)的數(shù)學(xué)模型，并采用量子進(jìn)化算法進(jìn)行求解。胡志華等[6]基于相對(duì)剝奪理論對(duì)應(yīng)急物資車(chē)輛分配的公平性進(jìn)行建模，利用橫向和縱向相對(duì)剝奪感評(píng)價(jià)車(chē)輛分配的公平性，并采用啟發(fā)式算法求解。在應(yīng)急物資配送及時(shí)性研究方面，國(guó)內(nèi)外學(xué)者以配送時(shí)間最小或延遲懲罰最小為目標(biāo)，建立了規(guī)劃模型或優(yōu)化模型，并采用不同的算法求解。王海軍等[7]建立了混合整數(shù)規(guī)劃模型，并采用基于非支配解排序的遺傳算法求解。劉長(zhǎng)石等[8]構(gòu)建了1個(gè)基于機(jī)會(huì)約束規(guī)劃的多目標(biāo)模糊LRP優(yōu)化模型，并采用混合免疫遺傳算法求解。ZHOU等[9]建立了多目標(biāo)優(yōu)化模型，采用基于分解的進(jìn)化算法求解。OTHMAN等[10]建立了單一供應(yīng)商多客戶模式的應(yīng)急物資調(diào)度決策系統(tǒng)，采用分支定界算法求解。目前，國(guó)內(nèi)外關(guān)于應(yīng)急物資配送公平性與及時(shí)性的協(xié)調(diào)優(yōu)化也進(jìn)行了研究，如BEHESHTI等[5]提出了1個(gè)基于時(shí)間最短以及公平性最大的多目標(biāo)優(yōu)化模型，并運(yùn)用多目標(biāo)量子遺傳算法求解。鄭斌等[11]建立了應(yīng)急物資配送雙層優(yōu)化模型，上層以物資配送時(shí)間最短、下層以物資分配公平性最大為目標(biāo)，并采用混合遺傳算法求解。在此基礎(chǔ)上，鄭斌等[12]考慮物資最低滿足率限制等其他約束條件，建立了雙層規(guī)劃動(dòng)態(tài)模型。陳瑩珍等[13]建立了1個(gè)雙目標(biāo)優(yōu)化模型，其目標(biāo)函數(shù)是最大化地區(qū)的物資滿足量以及最小化最大配送時(shí)間，采用差分進(jìn)化算法求解。國(guó)內(nèi)外學(xué)者關(guān)于應(yīng)急物資配送中的公平性、及時(shí)性以及兩者的協(xié)調(diào)優(yōu)化方面進(jìn)行了研究，取得了一些成果，但還存在以下幾個(gè)問(wèn)題：1) 大多數(shù)研究了物資需求是否得到滿足問(wèn)題，很少討論配送車(chē)輛的分配是否公平問(wèn)題。實(shí)際上，車(chē)輛分配的公平性會(huì)直接影響物資需求的滿意度，前者是因，后者是果，若車(chē)輛分配不公平，則滿意度也會(huì)大大降低。2) 公平性模型中大多通過(guò)改變公平性指標(biāo)或者權(quán)重尋求公平性的最大化，這不符合實(shí)際情況。當(dāng)災(zāi)情發(fā)生后，各受災(zāi)點(diǎn)的受災(zāi)情況相對(duì)確定，因此，公平性指標(biāo)或權(quán)重變化都較小，不太可能出現(xiàn)較大波動(dòng)。3) 研究中假設(shè)各應(yīng)急物資配送中心車(chē)輛充足，但在實(shí)際救援中有可能出現(xiàn)車(chē)輛不足或車(chē)輛閑置等情況，因此，當(dāng)出現(xiàn)車(chē)輛不足時(shí)需要進(jìn)行調(diào)撥。為此，針對(duì)上述問(wèn)題，本文作者提出物資配送中車(chē)輛分配公平性和配送及時(shí)性的協(xié)調(diào)優(yōu)化模型，并采用基于啟發(fā)式算法、局部搜索算法和遺傳算法的混合智能算法進(jìn)行求解，解決多配送中心、多受災(zāi)點(diǎn)、多品種物資的車(chē)輛分配和物資配送問(wèn)題。

1 問(wèn)題描述與變量定義

1.1 問(wèn)題描述與基本假設(shè)

研究的問(wèn)題可描述為：在不斷變化救災(zāi)環(huán)境中，在有限的時(shí)間和車(chē)輛資源條件下，通過(guò)科學(xué)合理的車(chē)輛分配方案，將有限的多品種物資在較短時(shí)間內(nèi)從不同配送中心配送至各個(gè)受災(zāi)點(diǎn)，同時(shí)實(shí)現(xiàn)車(chē)輛分配公平性的最大化。圖1所示為配送系統(tǒng)示意圖。

圖1 應(yīng)急物流配送系統(tǒng)示意圖

本文中定義模型的假設(shè)條件如下：

1) 配送中心車(chē)輛充足，且車(chē)型相同；

2) 每輛車(chē)只執(zhí)行1次配送任務(wù)，即從某配送中心出發(fā)，到達(dá)受災(zāi)點(diǎn)完成配送任務(wù)；

3) 當(dāng)其中1個(gè)配送中心車(chē)輛數(shù)不足時(shí)，可以從其他配送中心閑置車(chē)輛中調(diào)撥；

4) 配送中心與配送中心、配送中心與受災(zāi)點(diǎn)的距離已知，且車(chē)輛的行駛速度不變；

5) 問(wèn)題考慮的時(shí)間為運(yùn)輸時(shí)間，物資裝卸載時(shí)間不予以考慮。

1.2 變量定義

4) 目標(biāo)函數(shù)：1為受災(zāi)地區(qū)的總相對(duì)剝奪感，作為公平性目標(biāo)；2為受災(zāi)地區(qū)的總配送時(shí)間，作為及時(shí)性目標(biāo)。

2 模型構(gòu)建

2.1 車(chē)輛分配的公平性模型

對(duì)于所有物資，受災(zāi)點(diǎn)產(chǎn)生的總剝奪感為

整個(gè)受災(zāi)地區(qū)的總剝奪感為

當(dāng)1越小時(shí)，車(chē)輛分配的總剝奪感越小，感知的公平程度越高；反之，則公平程度越低。

2.2 物資配送的及時(shí)性模型

當(dāng)2越小時(shí)，物資配送的時(shí)間越短，及時(shí)程度越高；反之，則及時(shí)程度越低。

2.3 車(chē)輛分配的公平性與物資配送及時(shí)性協(xié)調(diào)優(yōu)化模型

在考慮多物資種類、多配送中心、多受災(zāi)點(diǎn)等情況下，構(gòu)建應(yīng)急物資配送的多目標(biāo)優(yōu)化模型。該模型以車(chē)輛分配的公平性最大(相對(duì)剝奪感最小)和物資配送的及時(shí)性最好(配送時(shí)間最小)為目標(biāo)，即

s.t.

式(5)為公平性與及時(shí)性協(xié)調(diào)優(yōu)化模型，其中1為車(chē)輛分配公平性目標(biāo)函數(shù)，2為物資配送及時(shí)性目標(biāo)函數(shù)。式(6)中左邊第1部分為受災(zāi)點(diǎn)和受災(zāi)點(diǎn)的配送物資的車(chē)輛數(shù)滿足率之差，第2部分為受災(zāi)點(diǎn)和受災(zāi)點(diǎn)的物資系數(shù)之差，不等式大于等于0，故這2部分必須同時(shí)大于等于0或者小于等于0，意味著物資系數(shù)越大的受災(zāi)點(diǎn)，車(chē)輛滿足率應(yīng)當(dāng)越大；式(7)表示受災(zāi)點(diǎn)之間不存在車(chē)輛配送；式(8)表示1輛車(chē)只能對(duì)1個(gè)受災(zāi)點(diǎn)進(jìn)行配送服務(wù)且僅服務(wù)1次；式(9)表示1輛車(chē)只能對(duì)1個(gè)配送中心進(jìn)行車(chē)輛調(diào)撥服務(wù)且僅服務(wù)1次；式(10)~(11)為車(chē)輛數(shù)約束；式(12)~(13)為0?1約束。

3 模型求解

本文研究的協(xié)調(diào)優(yōu)化問(wèn)題是1個(gè)多目標(biāo)整數(shù)規(guī)劃問(wèn)題(MILP)，屬于NP-hard問(wèn)題，不僅包括多受災(zāi)區(qū)多品種物資的配送，而且包括配送中心的選擇，同時(shí)還要考慮配送中心擁有的車(chē)輛數(shù)限制、物資系數(shù)限制等約束條件。因此，該問(wèn)題模型變量及約束條件眾多，求解困難。為解決此問(wèn)題，采用基于啟發(fā)式算法、2?Opt局部搜索算法和遺傳算法的混合智能算法[14?20]進(jìn)行求解。

3.1 歸一化處理

對(duì)于多目標(biāo)優(yōu)化問(wèn)題，通常要轉(zhuǎn)化為單目標(biāo)進(jìn)行求解，方法有優(yōu)選法、線性加權(quán)法、平方加權(quán)法、乘除法和分層序列法等。本文采用加權(quán)法，首先對(duì)多目標(biāo)協(xié)調(diào)優(yōu)化模型進(jìn)行歸一化處理。

3.2 混合智能算法

將遺傳算法和啟發(fā)式算法、2?Opt局部搜索算法結(jié)合起來(lái)，構(gòu)造求解應(yīng)急車(chē)輛配送的公平性與及時(shí)性協(xié)調(diào)優(yōu)化問(wèn)題的混合智能算法(hybrid intelligent algorithm，HIA)。HIA的基本思想為：根據(jù)啟發(fā)式算法對(duì)種群結(jié)構(gòu)進(jìn)行調(diào)整，使種群中所有染色體合法化；采用2?Opt局部搜索算法來(lái)修正染色體中的車(chē)輛數(shù)，使車(chē)輛滿意率排序與其對(duì)應(yīng)的物資系數(shù)排序一致；通過(guò)遺傳算法求解最優(yōu)染色體和最優(yōu)解，輸出最優(yōu)車(chē)輛配送情況。

3.2.1 編碼

種群中每一條染色體包含若干個(gè)子串，每個(gè)子串表示對(duì)應(yīng)配送中心的車(chē)輛配送情況，采用自然數(shù)編碼。配送中心編號(hào)用1，…，表示，受災(zāi)點(diǎn)編號(hào)用+1，…，表示，物資編號(hào)用1，…，表示。圖2所示為染色體編碼結(jié)構(gòu)。

圖2 染色體結(jié)構(gòu)

以子串sub為例。子串包含個(gè)基因段，=1, 2, …,?；蚨?為始發(fā)配送中心編號(hào)，長(zhǎng)度為1。其他基因段為每個(gè)受災(zāi)點(diǎn)所需配送物資的車(chē)輛數(shù)，長(zhǎng)度均為D，基因位=1, 2, …,D。圖3所示為具體 編碼。

例如有3個(gè)配送中心、3個(gè)受災(zāi)點(diǎn)、3種物資，表1所示為車(chē)輛配送情況。本例中3個(gè)配送中心編號(hào)為1號(hào)、2號(hào)和3號(hào)，3個(gè)災(zāi)點(diǎn)的編號(hào)為4號(hào)、5號(hào)和6號(hào)。染色體由3個(gè)子串組成，這些子串定義為sub1，sub2和sub3。sub1為1242000704，sub2為2000533403，sub3為3065309075。

圖3 子串subn編碼示意圖

表1 車(chē)輛分配表

3.2.2 種群初始化及種群結(jié)構(gòu)調(diào)整

根據(jù)染色體編碼規(guī)則隨機(jī)生成規(guī)模為popsize的初始種群。

由于隨機(jī)產(chǎn)生的染色體可能會(huì)發(fā)生配送車(chē)輛數(shù)超過(guò)配送中心車(chē)輛數(shù)，或者車(chē)輛滿意率不符合物資系數(shù)排序的情況，從而產(chǎn)生非法解。為了減少或者避免這些情況的發(fā)生，就需要對(duì)種群結(jié)構(gòu)進(jìn)行調(diào)整。首先要對(duì)每條染色體的車(chē)輛數(shù)進(jìn)行評(píng)估，然后通過(guò)啟發(fā)式算法進(jìn)行調(diào)整。具體的過(guò)程如下。

Step 1 計(jì)算每條染色體中的配送車(chē)輛數(shù)，并記錄。

Step 2對(duì)于配送車(chē)輛數(shù)超過(guò)配送中心車(chē)輛數(shù)的染色體，從中找出若干物資系數(shù)較小的受災(zāi)點(diǎn)，將其車(chē)輛數(shù)清零，使該染色體合法化。同時(shí)將配送中心及這些受災(zāi)點(diǎn)放入待選列表中。

Step 3根據(jù)啟發(fā)式算法中的最鄰近法和節(jié)約法，在保證配送車(chē)輛數(shù)可行的前提下，將待選列表的配送中心及受災(zāi)點(diǎn)更新到已有染色體中。

Step 4 判斷待選列表是否所有配送中心和受災(zāi)點(diǎn)都遍歷到，若列表中還有未遍歷的，則繼續(xù)進(jìn)行Step 3，否則，則轉(zhuǎn)向Step 5。

Step 5 根據(jù)物資系數(shù)的排序，采用2?Opt局部搜索算法修正受災(zāi)點(diǎn)的配送車(chē)輛數(shù)。

3.2.3 適應(yīng)度計(jì)算

為評(píng)價(jià)模型種群中個(gè)體優(yōu)劣，對(duì)每個(gè)染色體的適應(yīng)度進(jìn)行計(jì)算，從而獲得更優(yōu)的染色體。將式(14)作為適應(yīng)度函數(shù)，適應(yīng)度最大的染色體為最優(yōu)染色體。確定適應(yīng)度函數(shù)為

3.2.4 遺傳操作

1) 選擇操作。本文采用輪盤(pán)賭選擇策略，這樣既能保證目標(biāo)函數(shù)值隨代數(shù)變得越來(lái)越小，又能使較好的個(gè)體以更大的概率保存。

2) 交叉操作。為了不破壞優(yōu)良的子串，本文提出一種新的交叉算子，圖4所示為交叉操作示意圖。首先，隨機(jī)選擇2個(gè)父?jìng)€(gè)體A和B，將其中一個(gè)父?jìng)€(gè)體中物資系數(shù)最大的1條子串移到另一個(gè)父?jìng)€(gè)體的臨時(shí)串首位；然后，刪除該父?jìng)€(gè)體中與臨時(shí)串相同的基因；最后，將剩余的基因隨機(jī)全排列合并到臨時(shí)串中。

3) 變異操作。本文依據(jù)變異概率m，采用位移變異算子進(jìn)行變異操作。方法是隨機(jī)選擇父?jìng)€(gè)體A中2個(gè)非0編碼，交換其位置，從而產(chǎn)生新個(gè)體B。圖5所示為變異操作示意圖。

3.2.5 算法流程

根據(jù)HIA算法設(shè)計(jì)的基本思想，設(shè)計(jì)算法的具體步驟如下。

1) 種群的初始化。設(shè)定種群規(guī)模、最大迭代次數(shù)、權(quán)重系數(shù)，對(duì)染色體進(jìn)行初始化。

2) 種群結(jié)構(gòu)的調(diào)整。

3) 計(jì)算適應(yīng)度。根據(jù)式(15)計(jì)算每條染色體的適應(yīng)度。

4) 對(duì)每條染色體進(jìn)行選擇、交叉和變異操作，更新子代種群。

5) 若未達(dá)到最大迭代次數(shù)，則返回2)。

6) 輸出最優(yōu)染色體和最優(yōu)解。

圖4 交叉操作示意圖

圖5 變異操作示意圖

4 仿真實(shí)驗(yàn)分析

本文的算例分析分為3個(gè)部分：第1部分以Solomon測(cè)試數(shù)據(jù)庫(kù)中的算例數(shù)據(jù)，驗(yàn)證本文提出的模型和算法的有效性；第2部分通過(guò)3個(gè)不同的實(shí)驗(yàn)，將實(shí)驗(yàn)結(jié)果與原算例中的結(jié)果進(jìn)行分析對(duì)比，進(jìn)一步驗(yàn)證本文提出模型和算法的有效性；第3部分對(duì)雅安地震中應(yīng)急物資配送進(jìn)行仿真，驗(yàn)證本文提出的模型和算法在實(shí)際應(yīng)用中的效果。本文所有算例采用Matlab R2014a編程，在AMD四核A8-4500 M 1.90 GHz APU、內(nèi)存為4 G的微機(jī)上進(jìn)行求解。

4.1 算例仿真

為了驗(yàn)證本文提出的模型和方法的有效性，將以Solomon測(cè)試數(shù)據(jù)庫(kù)中的RC201算例數(shù)據(jù)為基礎(chǔ)，并補(bǔ)充物資系數(shù)等相關(guān)數(shù)據(jù)，產(chǎn)生測(cè)試算例。具體方法如下：從RC201數(shù)據(jù)中隨機(jī)抽取13個(gè)坐標(biāo)數(shù)據(jù)，其中3個(gè)作為配送中心，10個(gè)作為受災(zāi)點(diǎn)，各點(diǎn)之間的距離采用直線距離表示，然后，隨機(jī)產(chǎn)生10個(gè)受災(zāi)點(diǎn)的物資系數(shù)及車(chē)輛需求數(shù)。選擇的3個(gè)配送中心坐標(biāo)為(2，45)，(8，56)和(45，65)，并分別命名為1號(hào)、2號(hào)和3號(hào)。假設(shè)每個(gè)配送中心初始配有30輛車(chē)。表2所示為各受災(zāi)點(diǎn)物資系數(shù)及車(chē)輛需求數(shù)。

表2 原算例中各受災(zāi)點(diǎn)初始數(shù)據(jù)

注：括號(hào)中數(shù)據(jù)為本著中心至受災(zāi)點(diǎn)的車(chē)輛數(shù)

4.2 對(duì)比分析實(shí)驗(yàn)

為了進(jìn)一步驗(yàn)證本文模型和算法的有效性，對(duì)如下3個(gè)問(wèn)題進(jìn)行比較分析：1) 配送中心車(chē)輛數(shù)不足時(shí)的物資配送問(wèn)題；2) 目標(biāo)函數(shù)的權(quán)重系數(shù)對(duì)HIA算法性能的影響；3) HIA算法和PSO算法求解結(jié)果的分析對(duì)比。

4.2.1 配送中心車(chē)輛數(shù)不足時(shí)的物資配送實(shí)驗(yàn)

將原算例中1號(hào)、2號(hào)和3號(hào)配送中心的車(chē)輛數(shù)均減少為25輛，其他條件不變。圖7所示為車(chē)輛數(shù)不足時(shí)的配送示意圖。由于可配送車(chē)輛的總數(shù)為75輛，而受災(zāi)點(diǎn)對(duì)于車(chē)輛的總需求數(shù)為87輛，因此，離震中較遠(yuǎn)的、物資系數(shù)較小的受災(zāi)點(diǎn)6、受災(zāi)點(diǎn)8和受災(zāi)點(diǎn)9不會(huì)分配車(chē)輛。而受災(zāi)點(diǎn)1和受災(zāi)點(diǎn)7由于離震中較近，物資系數(shù)較大，所需的配送車(chē)輛也較多，需要2個(gè)配送中心同時(shí)進(jìn)行配送，以滿足它們的車(chē)輛需求。實(shí)驗(yàn)可得到平均總配送距離為1 660.25 km，平均總配送時(shí)間為23.72 h。與原算例進(jìn)行比較可以發(fā)現(xiàn)：當(dāng)配送中心車(chē)輛數(shù)充足時(shí)，配送距離和配送時(shí)間的變化不會(huì)引起總剝奪感的變化；當(dāng)配送中心車(chē)輛數(shù)不足時(shí)，物資配送距離和配送時(shí)間會(huì)減小，但總剝奪感會(huì)大幅度上升。

為了進(jìn)一步探討當(dāng)配送中心車(chē)輛數(shù)不足時(shí)公平性與及時(shí)性的關(guān)聯(lián)關(guān)系，本實(shí)驗(yàn)通過(guò)5種不同車(chē)輛分配方案分析總剝奪感與總配送時(shí)間，結(jié)果如圖8所示。從圖8可以看出：當(dāng)配送中心車(chē)輛數(shù)不足時(shí)，總配送時(shí)間和總剝奪感不能同時(shí)實(shí)現(xiàn)最小，提高公平性的同時(shí)會(huì)引起及時(shí)性降低，反之亦然。

注：括號(hào)中數(shù)據(jù)為本著中心至受災(zāi)點(diǎn)的車(chē)輛數(shù)

1—總配送時(shí)間；2—總剝壓感。

4.2.2 目標(biāo)函數(shù)權(quán)重系數(shù)對(duì)HIA算法性能的影響

4.2.3 算法比較

為了更好地檢驗(yàn)本文提出的HIA算法的性能，將該算法與微粒群PSO算法進(jìn)行對(duì)比分析，分別對(duì)原算例進(jìn)行10次求解，表3所示為計(jì)算時(shí)間數(shù)值實(shí)驗(yàn)計(jì)算結(jié)果。從表3可知：隨著最大迭代次數(shù)增大，程序運(yùn)行時(shí)間會(huì)有所增加，但HIA的計(jì)算時(shí)間總體上稍低于PSO的計(jì)算時(shí)間，其平均時(shí)間比PSO算法最大減少3.07%。基于模型最優(yōu)解，在相同迭代次數(shù)下，HIA算法與PSO算法相比最大減幅達(dá)2.48%，減幅明顯，最優(yōu)解也更優(yōu)。

表3 不同算法計(jì)算時(shí)間比較

4.3 大規(guī)模算例分析

為了驗(yàn)證本文提出的模型和算法在實(shí)際應(yīng)用的效果，以2013?04四川雅安地區(qū)的7.0級(jí)強(qiáng)震為例進(jìn)行分析。在這次地震中，雅安市區(qū)、龍門(mén)鄉(xiāng)、寶盛鄉(xiāng)、太平鎮(zhèn)、寶興縣、天全縣、名山區(qū)、滎經(jīng)縣、漢源縣和石棉縣等地都不同程度受到影響，其中雅安市區(qū)、龍門(mén)鄉(xiāng)、天全縣等地受災(zāi)嚴(yán)重，急需藥品、食品、帳篷等物資。已知雅安市區(qū)及周邊有3個(gè)應(yīng)急配送中心，車(chē)型均為中型載貨汽車(chē)，每個(gè)配送中心均擁有100輛車(chē)，總數(shù)為300輛。表4所示為各受災(zāi)點(diǎn)的物資系數(shù)及需求量，部分?jǐn)?shù)據(jù)來(lái)源于文獻(xiàn)[6]。表5所示為車(chē)輛分配結(jié)果，圖10所示為配送示意圖。

由表5可知：在車(chē)輛充足的情況下，所有受災(zāi)點(diǎn)的車(chē)輛需求都能得到滿足，滿足率達(dá)到100%，總剝奪感為0，實(shí)現(xiàn)了車(chē)輛分配的最大公平性。同時(shí)，計(jì)算得到總配送距離為6 628.8 km，總配送時(shí)間為94.7 h，表明在較短的時(shí)間內(nèi)完成了大規(guī)模的應(yīng)急物資配送任務(wù)。

表4 大規(guī)模算例中各受災(zāi)點(diǎn)初始數(shù)據(jù)

表5 車(chē)輛分配結(jié)果

圖10 配送示意圖

5 結(jié)論

1) 針對(duì)應(yīng)急救援中物資配送車(chē)輛分配的公平性與及時(shí)性問(wèn)題進(jìn)行分析，構(gòu)建了協(xié)調(diào)優(yōu)化模型，設(shè)計(jì)了一種基于啟發(fā)式算法、2?Opt算法和遺傳算法的混合智能算法對(duì)模型進(jìn)行求解。

2) 設(shè)計(jì)了標(biāo)準(zhǔn)算例庫(kù)和四川雅安地震2個(gè)算例，共進(jìn)行了5次數(shù)值實(shí)驗(yàn)，都取得了比較理想的結(jié)果。該混合智能算法能快速有效地找到滿意解；當(dāng)配送中心車(chē)輛數(shù)不足時(shí)，公平性與及時(shí)性存在關(guān)聯(lián)；目標(biāo)權(quán)重對(duì)算法的穩(wěn)定性和快速性有一定影響；該模型和算法在大規(guī)模地震實(shí)例中有效實(shí)現(xiàn)了公平性與及時(shí)性的協(xié)調(diào)優(yōu)化。

3) 本文構(gòu)建的模型主要有以下適用條件：在震后應(yīng)急救援初期，配送中心車(chē)輛有限情況下藥品、食品和帳篷3種應(yīng)急物資的配送，且需求已知；不適合于物資需求不確定的情況，因此，對(duì)需求不確定情況下的車(chē)輛分配問(wèn)題有待進(jìn)一步研究。

[1] 馬衛(wèi)峰, 楊賽霓, 潘耀忠. 面向救災(zāi)物資需求特征的自然災(zāi)害應(yīng)急響應(yīng)[J]. 中國(guó)安全科學(xué)學(xué)報(bào), 2010, 20(10): 171?176. MA Weifeng, YANG Saini, PAN Yaozhong. Relief demand characteristic-oriented emergency response in natural disasters[J]. China Safety Science Journal, 2010, 20(10): 171?176.

[2] CHANTA S, MAYORGA M E, MCLAY L A. The minimum p-envy location problem: a new model for equitable distribution of emergency resources[J]. Lie Transactions on Healthcare Systems Engineering, 2011, 1(2): 101?115.

[3] 馮春, 向陽(yáng), 薛坤, 等. 多周期多品種應(yīng)急物資配送多目標(biāo)優(yōu)化模型[J]. 中國(guó)管理科學(xué), 2017, 25(4): 124?132. FENG Chun, XIANG Yang, XUE Kun, et al. Multi-objective optimization model of the emergency logistics distribution with multi-cycle and multi-item[J]. Chinese Journal of Management Science, 2017, 25(4): 124?132.

[4] 張錦, 曾倩, 陳義友. 基于變權(quán)的物流資源公平分配方法[J]. 西南交通大學(xué)學(xué)報(bào), 2017, 51(3): 563?570. ZHANG Jing, ZENG Qian, CHEN Yiyou. Equity allocation method of logistic resources based on variable weights[J]. Journal of Southwest Jiaotong University, 2017, 51(3): 563?570.

[5] BEHESHTI A K, HEJAZI S R, ALINAGHIAN M. The vehicle routing problem with multiple prioritized time windows: a case study[J]. Computers & Industrial Engineering, 2015, 90: 402?413.

[6] 胡志華, 董盼, 李清. 基于相對(duì)剝奪理論的救災(zāi)物資運(yùn)輸車(chē)輛分配公平性[J]. 上海海事大學(xué)學(xué)報(bào), 2015, 36(2): 36?42. HU Zhihua, DONG Pan, LI Qing. Fairness of vehicle allocation for disaster relief materials based on relative deprivation theory[J]. Journal of Shanghai Maritime University, 2015, 36(2): 36?42.

[7] 王海軍, 杜麗敬, 馬士華. 震后應(yīng)急物流系統(tǒng)中雙目標(biāo)開(kāi)放式選址：路徑問(wèn)題模型與算法研究[J]. 管理工程學(xué)報(bào), 2016, 30(2): 108?115. WANG Haijun, DU Lijing, MA Shihua. Model and algorithms for integrated open location and routing problem in emergency logistics under earthquake[J]. Journal of Industrial Engineering and Engineering Management, 2016, 30(2): 108?115.

[8] 劉長(zhǎng)石, 彭怡, 寇綱. 震后應(yīng)急物資配送的模糊定位?路徑問(wèn)題研究[J]. 中國(guó)管理科學(xué), 2016, 24(5): 111?118. LIU Changshi, PENG Yi, KOU Gang. Research on fuzzy location-routing problem in post earthquake delivery of relief materials[J]. Chinese Journal of Management Science, 2016, 24(5): 111?118.

[9] ZHOU Yawen, LIU Jing, ZHANG Yutong, et al. A multi-objective evolutionary algorithm for multi-period dynamic emergency resource scheduling problems[J]. Transportation Research Part E, 2017, 99: 77?95.

[10] OTHMAN S B, ZGAYA H, DOTOLI M, et al. An agent-based decision support system for resources' scheduling in emergency supply chains[J]. Control Engineering Practice, 2017, 59: 27?43.

[11] 鄭斌, 馬祖軍, 李雙琳. 基于雙層規(guī)劃的震后初期應(yīng)急物流系統(tǒng)優(yōu)化[J]. 系統(tǒng)工程學(xué)報(bào), 2014, 29(1): 113?125. ZHENG Bing, MA Zujun, LI Shuangling. Integrated optimization of emergency logistics systems for post-earthquake initial stage based on bi-level programming[J]. Journal of Systems Engineering, 2014, 29(1): 113?125.

[12] 鄭斌, 馬祖軍, 周愉峰. 震后應(yīng)急物流動(dòng)態(tài)選址聯(lián)運(yùn)問(wèn)題的雙層規(guī)劃模型[J]. 系統(tǒng)管理學(xué)報(bào), 2017, 26(2): 326?337. ZHENG Bing, MA Zujun, ZHOU Yufeng. Bi-level model for dynamic location transportation problem for post-earthquake relief distribution[J]. Journal of Systems & Management, 2017, 26(2): 326?337.

[13] 陳瑩珍, 趙秋紅. 基于公平原則的應(yīng)急物資分配模型與算法[J]. 系統(tǒng)工程理論與實(shí)踐, 2016, 51(3): 563?570. CHEN Yingzhen, ZHAO Qiuhong. The model and algorithm for emergency supplies distribution based on fairness[J]. Systems Engineering Theory & Practice, 2016, 51(3): 563?570.

[14] GIANFRANCO F, SIMONA M, CLAUDIA P, et al. An emergency vehicles allocation model for major industrial disasters[J]. Transportation Research Procedia, 2017, 25: 1164?1179.

[15] AHMAD M, SAEED Y A. Bi-objective stochastic model for emergency medical services network design with backup services for disasters under disruptions: an earthquake case study[J]. International Journal of Disaster Risk Reduction, 2017, 23: 204?217.

[16] 胡飛虎, 田朝暉, 趙沐華, 等. 基于遺傳算法的應(yīng)急物資分層聯(lián)動(dòng)分配研究[J]. 計(jì)算機(jī)應(yīng)用研究, 2016, 33(2): 440?443. HU Feihu, TIAN Zhaohui, ZHAO Muhua, et al. Research on hierarchical linkage scheduling emergency supplies based on genetic algorithm[J]. Application Research of Computers, 2016, 33(2): 440?443.

[17] 劉家利, 郭秀萍. 存在產(chǎn)品互斥和車(chē)輛匹配的多中心開(kāi)環(huán)車(chē)輛路徑問(wèn)題[J]. 系統(tǒng)管理學(xué)報(bào), 2016, 25(1): 129?138. LIU Jiali, GUO Xiuping. Multi-depot open vehicle routing problem with exclusive products and heterogeneous vehicles[J]. Journal of Systems & Management, 2016, 25(1): 129?138.

[18] BARKAOUI M, BERGER J, BOUKHTOUTA A. Customer satisfaction in dynamic vehicle routing problem with time windows[J]. Applied Soft Computing, 2015, 35: 423?432.

[19] SASO K, VILI P. A survey of genetic algorithms for solving multi depot vehicle routing problem[J]. Applied Soft Computing, 2015, 27: 519?532.

[20] 許茂增, 余國(guó)印, 周翔, 等. 綜合成本最小的低碳車(chē)輛調(diào)度問(wèn)題及算法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2015, 21(7): 1906?1914. XU Maozeng, YU Guoying, ZHOU Xiang, et al. Low-carbon vehicle scheduling problem and algorithm with minimum- comprehensive-cost[J]. Computer Integrated Manufacturing Systems, 2015, 21(7): 1906?1914.

(編輯 陳燦華)

Integrated decision making of emergency vehicle allocation and emergency material distribution

WANG Li1, ZHOU Xiancheng2, ZHAO Zhixue1, LIU Limei1, YU Lingli3

(1. School of Computer and Information Engineering, Hunan University of Commerce, Changsha 410025, China; 2. Hunan Collaborative Innovation Center of Mobile E-commerce, Hunan University of Commerce, Changsha 410025, China; 3. School of Information Science and Engineering, Central South University, Changsha 410083, China)

In the delivery of relief aids to the disaster areas, it is usually difficult to balance the fairness of vehicle allocation and the timeliness of materials distribution. To solve the problem, a multi-objective coordination optimization model was presented. The objective was to minimize the relative deprivation of the vehicle allocation(fairness) and the delivery time(timeliness). To solve the model, a hybrid intelligent algorithm combining a heuristic algorithm, a local search algorithm and a genetic algorithm was designed. The results show that there is a close relationship between fairness and timeliness when the number of vehicles in distribution centers is insufficient. The proposed algorithm is fast and effective to find the satisfactory solutions. The target weight coefficients have influence on the stability and rapidity of the algorithm. The model and algorithm are also effective in large-scale earthquake instances.

emergency materials distribution; relative deprivation; fairness; timeliness; coordinative optimization

10.11817/j.issn.1672-7207.2018.11.018

TP 391.9

A

1672?7207(2018)11?2766?10

2017?12?26；

2018?03?06

國(guó)家自然科學(xué)基金資助項(xiàng)目(61403426)；商務(wù)智能湖南省重點(diǎn)實(shí)驗(yàn)室資助項(xiàng)目(2015TP1002)；教育部人文社科基金資助項(xiàng)目(14YJCZH099)；湖南省自然科學(xué)基金資助項(xiàng)目(2018JJ3261)；湖南省教育廳科研項(xiàng)目(15C770) (Project(61403426) supported by the National Natural Science Foundation of China; Project(2015TP1002) supported by Key Laboratory for Business Intelligence of Hunan Province; Project (14YJCZH099) supported by the Humanities and Social Sciences Planning Fund of Ministry of Education; Project(2018JJ3261) supported by the Natural Science Foundation of Hunan Province; Project(15C770) supported by the Scientific Research Fund of Department of Education of Hunan Province)

周鮮成，博士，教授，從事物流系統(tǒng)的建模與優(yōu)化以及管理信息處理研究；E-mail: zxc6501@126.com