趙燕偉 丁鋆杰 冷龍龍 張景玲 余孟凡

(*浙江工業(yè)大學(xué)特種裝備制造與先進加工技術(shù)教育部重點實驗室 杭州 310023)

(**浙江工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院 杭州 310023)

0 引言

中國是世界上自然災(zāi)害最為嚴(yán)重的國家之一。災(zāi)害種類多、發(fā)生頻率高、分布地域廣、造成損失重,這就導(dǎo)致了在進行應(yīng)急救援時,難度急劇增大。由于自然災(zāi)害的不確定性,當(dāng)?shù)貎涞膽?yīng)急救援物資往往會出現(xiàn)供不應(yīng)求的情況。因此,在災(zāi)后第一時間需要根據(jù)應(yīng)急物資的需求和供應(yīng)關(guān)系以及災(zāi)區(qū)的受損程度進行優(yōu)化調(diào)度決策,才能最大限度地減少損失。在應(yīng)急物流系統(tǒng)中,配送中心的選址非常重要,它決定了應(yīng)急系統(tǒng)能否對突發(fā)事件作出快速反應(yīng)。因此,應(yīng)急倉庫的選址和物資分配問題近年來受到了廣泛的關(guān)注。Wang 等人[1]提出了一種在不確定條件下基于時間成本的應(yīng)急倉庫選址與配送的混合整數(shù)規(guī)劃模型,解決了應(yīng)急倉庫選址與配送問題。Geng 等人[2]將受害者的疼痛感知成本引入模型,提出了一個以應(yīng)急系統(tǒng)總成本最小為目標(biāo)的選址—配送模型。Paul 等人[3]考慮到地震場景下的不確定性,提出了一個以總的社會成本最小為目標(biāo)的選址—配送模型。Ghasemi 等人[4]針對地震反應(yīng)階段,提出了一個多商品、多車輛的多目標(biāo)選址—配送問題混合整數(shù)數(shù)學(xué)規(guī)劃模型,目標(biāo)分別是最小化總成本和最小化救災(zāi)物資短缺的數(shù)量。Gutjahr 等人[5]提出了一種人道主義物流中救援配送中心選址的雙目標(biāo)雙層優(yōu)化模型,并以最小化配送中心運營成本和最小化未被滿足的數(shù)量為目標(biāo)進行優(yōu)化。Baharmand 等人[6]將受影響地區(qū)的地形劃分為多個層次,考慮受限的設(shè)施和車隊的數(shù)量和能力,并提供解決方案以便決策者在響應(yīng)時間和物流成本之間進行權(quán)衡。郭鵬輝等人[7]考慮到災(zāi)后的物資供應(yīng)不足的情況,提出了一個以救援及時性、物資配送的公平性等為目標(biāo)的選址—路徑—配送模型。此外,學(xué)者將其與不同的應(yīng)用場景結(jié)合,又衍生出了一些不同的問題。Gulzari 等人[8]將選址—配送問題與遠(yuǎn)程醫(yī)療應(yīng)用場景結(jié)合,考慮到病人的需要得到救治的緊急程度,以最小化未被滿足的醫(yī)療需求為目標(biāo)進行優(yōu)化。Zhao 等人[9]將選址—配送問題與地震避難所的選擇場景結(jié)合,提出了一個以最小化總疏散時間和最小化庇護所面積為目標(biāo)的兩階段模型。然而,現(xiàn)有的關(guān)于應(yīng)急物資選址—配送問題的研究,大多只關(guān)注時間成本,而忽略了其他的一些成本,在考慮災(zāi)區(qū)人民的滿意程度時,也沒有考慮災(zāi)區(qū)的緊急程度。因此本文提出了一個考慮各種成本,并以時間成本為主導(dǎo),且根據(jù)災(zāi)區(qū)緊急程度來進行配送的雙目標(biāo)選址—配送模型。

超啟發(fā)算法(hyper-heuristics,HH),作為一種高效、通用的智能算法,已經(jīng)被廣泛的應(yīng)用于各類優(yōu)化問題,例如教育時間表問題[10]、旅行商問題[11]、車輛路徑問題[12]、選址路徑問題[13]和生產(chǎn)調(diào)度問題[14]等。最初的超啟發(fā)算法主要用來求解單目標(biāo)問題,隨著研究的深入,越來越多的學(xué)者將其用于多目標(biāo)問題,并取得了不錯的效果。Leng 等人[15]提出了一種新的超啟發(fā)式方法來處理雙目標(biāo)區(qū)域低碳選址—路徑問題,并使用量子策略來選擇算子。Wang等人[16]提出了一個多目標(biāo)的超啟發(fā)算法來求解冷鏈物流,比傳統(tǒng)的多目標(biāo)算法取得了更好的效果。Yao 等人[17]提出了智能城市步行路線規(guī)劃的超啟發(fā)算法框架,并使用了強化學(xué)習(xí)機制來選擇算子。Castro 等人[18]將超啟發(fā)算法整合到多目標(biāo)粒子群算法(multiple objective particle swarm optimization,MOPSO)中,并設(shè)計了4 種選擇策略進行對比。Zhang 等人[19]提出一種新的基于多種多樣性機制的選擇超啟發(fā)式操作,并在3～10 個目標(biāo)的MaOP 測試集上驗證了算法的性能。在求解多目標(biāo)問題的時候,學(xué)者們也提出了很多優(yōu)秀的高層接受準(zhǔn)則,包括全接受[20]、只接受改進解[21]、大洪水[22]以及蒙特卡洛[23]等,保證了算法的有效性。然而,尚未有學(xué)者將超啟發(fā)算法應(yīng)用在選址—配送問題中,因此缺乏相應(yīng)的底層算子與高層算法設(shè)計。

鑒于超啟發(fā)算法優(yōu)秀的搜索能力,本文也針對模型設(shè)計了一個多目標(biāo)超啟發(fā)式(multi-objective hyper-heuristic,MOHH)算法框架,并通過對比選擇出最優(yōu)的高層策略組合,并在不同規(guī)模的實例問題中與其他多目標(biāo)算法進行比較,驗證了所提算法的性能。

1 多目標(biāo)優(yōu)化調(diào)度模型

1.1 問題描述

本文研究了災(zāi)害發(fā)生初期應(yīng)急物資配送的問題。由于事發(fā)突然,在救援初期,一般會出現(xiàn)2 種情況,一是物資準(zhǔn)備不足,二是運力有限。此時在進行物資分配時,就需要考慮到配送的公平性,進行合理的物資分配,實現(xiàn)效益最大化。本文基于此類情況,考慮不同受災(zāi)點的緊急情況,提出了一個既能控制配送成本,又能保證配送公平性的多目標(biāo)應(yīng)急物資配送模型。

設(shè)某地區(qū)突發(fā)災(zāi)害后,受應(yīng)急物流協(xié)調(diào)指揮中心指示,物資儲備庫迅速向物資臨時配送中心分配物資,周邊共有m個臨時物資配送中心,所有點的集合為A,A={A1,A2,…,Am},其中,每個物資配送中心都有相應(yīng)的運行成本,同時由于車輛數(shù)量有限,存在運力上限,也就是配送中心車輛提供的最大運力。此外,共有n個受災(zāi)點,所有點的集合為B,B={B1,B2,…,Bn}。同時,需要提供K種物資,所有物資的集合為C,C={C1,C2,…,CK}。其配送關(guān)系如圖1 所示,其中,x0mk表示從物資儲備庫向物資配送中心m運送的第k種物資的量,xmnk表示從m到n配送的第k種物資的量(k=1,2,…,K)。此外,每個災(zāi)區(qū)的受災(zāi)程度不同,不同的受災(zāi)程度則對應(yīng)了不同的需求緊迫度。當(dāng)受災(zāi)越嚴(yán)重時,需求緊迫度越高,此時則需要越符合需求的救援物資送達(dá),至于具體的緊迫度,可由受災(zāi)地區(qū)上報受災(zāi)情況后進行認(rèn)定。要求通過合理的選擇物資配送中心,以運輸過程中的運輸總成本、時間成本和物資配送中心的開設(shè)成本最少、同時以配送公平性最高為目標(biāo),給出一個優(yōu)化調(diào)度結(jié)果。

圖1 3 級應(yīng)急物資選址—配送網(wǎng)絡(luò)示意圖

1.2 條件假設(shè)

假設(shè)1車輛始終以恒定速度行駛,不考慮出發(fā)與到達(dá)的速度變化,所有車輛速度一致。

假設(shè)2物資配送中心的配送車輛有限。

假設(shè)3所有點之間有且僅有一條最短路徑。且道路均可以到達(dá)。

假設(shè)4物資儲備庫的第k物資儲存量總和不超過n個受災(zāi)點的第k種物資需求量總和。

1.3 模型建立

本文提出了一個雙目標(biāo)模型,一個目標(biāo)是總成本最少,另一個目標(biāo)是物資短缺數(shù)最小?？偝杀景ㄟ\輸成本、時間成本以及配送點的運行成本。在計算運輸成本時,引入了單位運輸成本的概念,也就是運送單位物資的成本,故運輸成本為單位運輸成本與運送物資量的乘積,時間成本就是在兩點之間所花費的時間的累加和。為了突出應(yīng)急配送的時效性,參考文獻(xiàn)[24],引入時間成本系數(shù)ω,這樣可以使得時間成本的權(quán)重更大,所以總的成本為

其中,c0i表示物資儲備庫到i的單位運輸成本,表示從物資儲備庫到點i運送的第k種物資的量,t0i表示物資儲備庫到點i的行駛時間,ei表示分配中心i的運行成本,cij表示從點i到點j的單位運輸成本表示從點i到點j運送的第k種物資的量,tij表示點i到點j的行駛時間。

對于物資短缺數(shù)最小這一目標(biāo),本文以災(zāi)區(qū)的需求緊迫度為評價基準(zhǔn),將需求緊迫度與欠缺的物資量相乘,將這個值當(dāng)成公平性的評價標(biāo)準(zhǔn)。當(dāng)這個值最小時,說明配送結(jié)果兼顧到了災(zāi)區(qū)的受災(zāi)程度與災(zāi)民需求,實現(xiàn)了公平。災(zāi)區(qū)物資短缺數(shù)量可由下式進行計算。

其中,f2 為災(zāi)區(qū)需求的未被滿足程度,μj表示災(zāi)區(qū)j的需求緊迫度,djk表示災(zāi)區(qū)j實際需要的物資k的數(shù)量。

所以綜上所述,該問題的模型為

服從以下約束:

其中,式(3)本次優(yōu)化的目標(biāo),表示最小化總成本,以及最小化物資短缺數(shù);式(4)表示運送到需求點的各類物資的數(shù)量不超過其實際需求量;式(5)表示配送中心收到的物資數(shù)量不可超過運力上限,Di表示臨時配送中心i的運力上限;式(6)表示在供不應(yīng)求的情況下,物資儲備點的所有物資都應(yīng)該分發(fā)出去,其中ck表示物資儲備庫第k種物資的存量;式(7)是計算兩點間的行駛時間,其中,rij表示點i和點j之間的距離,v是行駛速度;式(8)是配送中心配送到災(zāi)區(qū)的的物資都是非負(fù)整數(shù)約束,式(9)～(11)為決策變量。

2 算法設(shè)計

本文提出的問題是一個混合整數(shù)非線性模型。它不僅包括臨時配送點的選址以及多個配送點與多個受災(zāi)點之間的多種物資的配送,還考慮到了現(xiàn)實中的受災(zāi)程度。同時,考慮的問題也是一個NP(non-deterministic polynomial)難題。因此,本文的目標(biāo)是設(shè)計一個有效的超啟發(fā)式算法來獲得最優(yōu)或者接近最優(yōu)的Pareto 解。

2.1 初始化個體策略

在產(chǎn)生初始個體時,對于每個個體采用了3 層的編碼。

第1 層采用的是二進制編碼,表示為配送中心的開通情況。第1 層的長度與配送中心個數(shù)相同。如果配送中心被選擇,則相應(yīng)的編碼為1,否則為0。在初始化產(chǎn)生第1 層時,先隨機產(chǎn)生0 -1 字符串,再判斷被選擇的配送中心是否滿足配送要求,若滿足,則該字符串合法,否則在未選擇的配送中心中隨機選擇一個開設(shè),直到滿足配送要求。

第2 層采用的是實數(shù)編碼,它是一個k×m的矩陣,其中,k為物資種類,m為配送中心數(shù)量,表示開通的配送中心分配到的每種物資的量。首先,給被選擇的配送中心k個不超過其運力上限的值,代表其被分到的每種物資的量。其次,對第2 層的編碼進行規(guī)范化調(diào)整,使其符合約束。調(diào)整規(guī)則如下:先調(diào)整編碼的列,計算每一列與運力上限的差值,若超出,則每一項按比例減少,并保證每一項都至少要大于1 t;再調(diào)整編碼的行,計算每一行與物資上限的差值,若大于物資上限,則從分配最多的配送中心開始依次減少,直到將多出來的物資全部減去,并保證每個配送中心至少有1 t 物資;若低于物資上限,則從距離配送中心運力上限最大的配送中心開始,依次加滿物資,直到所有配送物資全部分發(fā)出去。

第3 層依舊采用實數(shù)編碼,表示每一個配送中心給每一個災(zāi)區(qū)的每種物資的量,它的規(guī)模為m×n×k,其中n表示災(zāi)區(qū)數(shù)。假設(shè)第i個配送中心分到第k種物資為Uik,則配送中心i向第1 個災(zāi)區(qū)隨機配送第k種物資的量xi1k=rand×Uik,rand 為一個隨機數(shù);配送中心i向第2 個受災(zāi)點配送第k種物資量應(yīng)以該供應(yīng)點i的第k種物資剩余總量(Uik-xi1k) 為上邊界來隨機初始化xi2k;以此類推,若分到最后一個災(zāi)區(qū)還剩物資,則將物資全部配送給最后一個災(zāi)區(qū)。一個6 個配送中心、6 個災(zāi)區(qū)的小規(guī)模問題實例如圖2 所示。

圖2 一個小規(guī)模問題個體的編碼

2.2 底層啟發(fā)式算子設(shè)計

根據(jù)本文問題編碼的特點,設(shè)計對應(yīng)的幾種底層啟發(fā)式算子(low-level heuristics,LLH),主要分為局部優(yōu)化算子(local research,LLH-L)、變異算子(mutation,LLH-M) 和破壞與重構(gòu)算子(locationbased radial ruin,LLH-R) 3 大類?？紤]到本文的問題有3 層編碼,并且每一層之間還有遞進的邏輯性,所以為了算子的有效性,本文將局部優(yōu)化算子作為第3 層編碼的操作,作用是通過改變物資的分配量,使其產(chǎn)生一個更好的解;變異算子為第2 層和第3層編碼的操作,目的是通過改變物資的分配量,使其跳出局部最優(yōu)解;而破壞與重構(gòu)算子,本文將其作為第1 層的操作。因為當(dāng)?shù)? 層改變時,2、3 層也會隨之改變,保證解的多樣性。同時,所有的算子進行操作以后都應(yīng)符合約束條件,保證解的可行性。在執(zhí)行算子操作時,本文引入了2 個參數(shù),一個是局部搜索率Ps,另一個是變異率Pm,用它們來決定每個算子操作的具體執(zhí)行次數(shù)。具體的設(shè)計如下。

LLH-L1:以一定的概率Ps挑選配送中心,采用遍歷的方式將其分給不同的2 個災(zāi)區(qū)的物資互換,并保證解的可行性,直到產(chǎn)生更好的解。

LLH-L2:以遍歷的方式挑選2 個災(zāi)區(qū),將所有配送中心分給災(zāi)區(qū)的物資互換,并保證解的可行性,直到產(chǎn)生更好的解。

LLH-L3:以一定的概率Ps挑選被選擇的配送中心,減少其分給某一個災(zāi)區(qū)的物資量,將它分給另外一個災(zāi)區(qū),并保證解的可行性,直到產(chǎn)生更好的解。

LLH-L4:以一定的概率Ps選取配送中心,將其分配給災(zāi)區(qū)A的物資分配給災(zāi)區(qū)B,同時縮減其余配送中心分配給B災(zāi)區(qū)的同等物資,將其分給災(zāi)區(qū)A,直到產(chǎn)生更好的解。

LLH-M1:以一定的概率Pm挑選配送中心,將其分給某災(zāi)區(qū)的物資分出一部分給另外一個災(zāi)區(qū),并保證解的可行性。

LLH-M2:以一定的概率Pm挑選配送中心,將其分給某災(zāi)區(qū)的物資分出一部分給另外2 個災(zāi)區(qū),并保證解的可行性。

LLH-M3:以一定的概率Pm挑選配送中心,將其分給不同的2 個災(zāi)區(qū)的物資互換,并保證解的可行性。

LLH-M4:以一定的概率Pm挑選配送中心,將其分到的物資分出一部分給另外的配送中心,并保證解的可行性。

LLH-R1:改變開設(shè)的倉庫,并保證解的可行性。

2.3 高層選擇策略設(shè)計

(1)簡單隨機(simple random,SR)。在每次迭代中隨機選擇一個算子,通常用作與任何其他策略進行比較的參考。

(2)禁忌搜索(tabu search,TS)。該策略是禁止重復(fù)使用先前的算子。針對局部搜索算子容易陷入局部最優(yōu)點的缺陷,禁忌搜索構(gòu)造了一個禁忌列表,禁忌對象是底層啟發(fā)式算子。在下一次迭代中不搜索或選擇性地搜索禁忌列表中的元素,從而消除了局部最優(yōu)的陷阱,達(dá)到了全局優(yōu)化的目的。在進行優(yōu)化過程中,根據(jù)算子的優(yōu)化效果進行評分,從而選擇當(dāng)前迭代的算子。換言之,如果由于使用LLH 而產(chǎn)生的子解改進了父解,則將該LLH 的分?jǐn)?shù)相加,且加分分值隨著改進效果增加而增加,否則將被扣除,然后使用輪盤賭選擇算子。具體的加減分規(guī)則如下:

(3)選擇函數(shù)(choose function,CF)?；贑F的方法也是通過計算得分選擇低層啟發(fā)式算法,但計算分?jǐn)?shù)的方法與式(2)中的方法不同。本文基于3 個不同的度量來選擇LLH。

第1 個度量f1 用來評估算子之前的表現(xiàn)性能:

其中,In(LLHj) 表示第n次使用j算子的改進率,若不改進則取0。

第2 個度量f2 用來評估算子之間的聯(lián)系:

其中,In(LLHj,LLHk) 表示第n次使用k算子后再使用j算子的改進率,若不改進則取0。

第3 個度量則是為了提高算子使用的多樣性,使得那些使用次數(shù)少的算子有更大的幾率被選擇:

其中,N(LLHj) 表示目前為止j算子的使用次數(shù),初始值取1,β是一個常數(shù)。

所以,總的算子的得分為3 個度量相加,再對其進行排序,然后按照輪盤賭選擇算子。

2.4 高層接受準(zhǔn)則設(shè)計

(1)全部接受(all move,AM)。不管產(chǎn)生的解是否改進,都接受相應(yīng)的解。

(2)模擬退火(simulated annealing,SA)。設(shè)置相應(yīng)的初始溫度以及降溫速率,在迭代的過程中,以一定的概率接受差解。

(3)記錄更新(record update,RU)。設(shè)置一個Record和一個偏差系數(shù)γ,Record記錄當(dāng)前最優(yōu)解。如果當(dāng)前解的值優(yōu)于Record,則將Record的值設(shè)為當(dāng)前解,若當(dāng)前解變差并且當(dāng)前解的值小于Record×γ時,則接受該差解。

(4) 改進自適應(yīng)接受(adaptive acceptance,AA)。在開始只接受改進的解,如果在某一階段已連續(xù)多次沒有改進當(dāng)前解,則接受差解,避免徒勞的搜索。

2.5 超啟發(fā)式算法框架設(shè)計

針對提出的選址—配送模型,本文提出了一個多目標(biāo)超啟發(fā)算法,重點是選擇配送中心以及配送中心與災(zāi)區(qū)的物資分配。具體的算法步驟如下。

步驟1初始化參數(shù)。包括高層選擇策略的參數(shù),高層接受準(zhǔn)則的參數(shù)以及底層啟發(fā)式算子的參數(shù)。

步驟2初始化種群的參數(shù)。按照2.1 節(jié)的策略,產(chǎn)生與種群數(shù)量相同的個體,組合成初始化種群。

步驟3優(yōu)化種群。

隨著城鎮(zhèn)化進程的不斷發(fā)展，農(nóng)村中許多問題日益凸顯，其中以土地矛盾最為顯著，涉及到的村民群體利益日益嚴(yán)峻。如果不妥善處理這些利益沖突，勢必會激發(fā)更多的社會矛盾，不利于社會和諧。因此，明確農(nóng)村集體經(jīng)濟組織的法律主體地位就顯得至關(guān)重要和急迫，必須要引起足夠的重視。

步驟3.1以相同的概率隨機選擇2 個目標(biāo)中的一個;

步驟3.2根據(jù)算子的性能表現(xiàn),使用輪盤賭方法選擇算子,并進行優(yōu)化;

步驟3.3計算所選目標(biāo)的值;

步驟3.4根據(jù)接受準(zhǔn)則中的機制決定是否接納當(dāng)前解;

步驟3.5計算另一個目標(biāo)的值;

步驟3.6更新算子的性能指標(biāo)。

步驟4合并父子種群。

步驟6更新與高層選擇策略以及底層算子分?jǐn)?shù)相關(guān)的參數(shù)。

步驟7判斷是否滿足終止條件;如果是,則停止迭代并輸出最優(yōu)解集;否則,返回步驟3。

步驟8生成Pareto 前沿。

3 實驗與分析

3.1 實例驗證

假設(shè)在某地發(fā)生嚴(yán)重的地震災(zāi)害,收到上級的指示,某物資儲備庫將要把籌集的2 種物資緊急送往災(zāi)區(qū),其中包括1200 t 水和1200 t 食物。為了保證能夠更有效地分配物資和避免救災(zāi)物資在災(zāi)區(qū)積壓,儲備庫先將物資送往災(zāi)區(qū)附近的配送中心進行集散。其中配送中心共有6 個,每個配送中心的車輛運力配送上限如下表所示。其中,從供應(yīng)點到配送中心配送速度為v1=300 km/h,從配送中心到災(zāi)區(qū)的配送速度為v2=70 km/h。關(guān)于災(zāi)區(qū)的詳細(xì)信息如表1 所示。各配送中心與供應(yīng)點和災(zāi)區(qū)的距離、單位運輸成本等信息如表2～4 所示。

表1 災(zāi)區(qū)的詳細(xì)信息

表2 各配送中心與供應(yīng)點和災(zāi)區(qū)的距離/(km)

表3 各配送中心與供應(yīng)點和災(zāi)區(qū)的單位運輸成本/(元/t)

表4 配送中心的運營成本(元)與運力上限(t)

3.2 參數(shù)設(shè)置

本文的實驗采用MatlabR2019 a編程,在Inter(R)Core(TM)i7-6700K CPU @4.00 GHz 4.01 GHz和20 GB 內(nèi)存的計算機上運行。

參數(shù)設(shè)置如下,種群個體數(shù)量為100,最大的迭代次數(shù)設(shè)置為1000。文中存在幾個變量,分別是變異算子的變異概率Pm、局部搜索算子的搜索概率Ps、式(12)中提到的參數(shù)α、式(15)中提到的參數(shù)β以及記錄更新的偏差系數(shù)γ。本文給定了這些參數(shù)一個取值范圍:Pm={0.1,0.2,0.3,…,1.0};Ps={0.1,0.2,0.3,…,1.0};α={1,2,3,…,10};β={5,10,15,20,…,50};γ={0.03,0.06,0.09,…,0.30}。經(jīng)過初始化實驗,最終本文選定Pm=0.2,Ps=0.8,α=5,β=30,γ=0.15。此外,對于一些算法的參數(shù),也通過初始化實驗得出。在禁忌搜索中,局部優(yōu)化算子的初始得分為1000,變異算子與破壞重構(gòu)算子的得分為500,其中得分上限為3000,下限為300;在模擬退火的接受準(zhǔn)則中,初始溫度為1000,終止溫度為0.01,降溫速率為0.99。

3.3 性能指標(biāo)

為了驗證提議的MOHH 算法的性能,使用了以下3 個指標(biāo)。

(1)Pareto 解數(shù)(number of Pareto solution,NPS)。該指標(biāo)用于確定通過算法獲得的Pareto 解數(shù)。

(2)間距指標(biāo)(spacingmetric,SM)。計算每個解到其他解的最小距離的標(biāo)準(zhǔn)差,SM值越小,說明解集越均勻。

其中,n表示解的數(shù)量,di表示Pareto 解i到Pareto解集中最近點的歐氏距離,表示所有di的平均值。

(3)多樣性指標(biāo)(hypervolume,HV)。算法獲得的非支配解集與參照點圍成的目標(biāo)空間中區(qū)域的體積,HV值越大,說明算法的綜合性能越好。

其中,v(i,P)表示Pareto 解集中第i個解與參考點P之間形成空間的超體積,即以第i個解和參考點P之間的連線作為對角線,構(gòu)建的超立方體的體積。

3.4 模型分析

由于本文考慮的是時效性與公平性,這也是本文的2 個優(yōu)化目標(biāo),所以本節(jié)主要分析了時間成本系數(shù)ω的取值與緊急程度的有無對目標(biāo)的影響。首先,先隨機選擇一組高層選擇策略與接受準(zhǔn)則進行實驗,本次實驗選擇的是選擇函數(shù)和模擬退火。關(guān)于時間成本的取值,本文首先列舉了不同的ω值(ω=10,50,100,200,500)。在不同的ω取值之下,得到不同的解,對于不同的解,通過對比所求得解的結(jié)果再進行確定。實驗結(jié)果如圖3 所示。

圖3 不同的ω 取值對時間成本以及其他成本的影響

由圖3 可以看出,隨著ω的取值不斷增大,時間成本所占的比重會越來越高,因此在優(yōu)化時,會得到實際時間成本更低的解,也就是更加及時的解。但是當(dāng)ω增大到一定程度時,起到的優(yōu)化效果就會受限。同時隨著ω的增大,相應(yīng)的其他成本所占的比重就會降低,因此,在優(yōu)化的過程中,其余成本的優(yōu)化效果會越來越差。綜合兩者進行考慮,在保證及時性的情況下,綜合考慮其他成本的優(yōu)化效果,所以選擇ω的取值為100。

同時,該模型還兼顧到了公平性。本文中,公平性主要體現(xiàn)的是在物資緊缺的情況下,優(yōu)先將物資送給緊急程度高的地區(qū),所以選取了物資短缺數(shù)最低的一個解,并將引入緊急程度的結(jié)果與沒有引入緊急程度的結(jié)果進行對比,在未引入緊急程度的情況下,本文將物資短缺數(shù)換成了物資短缺率進行優(yōu)化,結(jié)果如圖4 所示。

圖4 表示的是災(zāi)區(qū)獲得的每種物資的數(shù)量,兩者分別是2 種情況下物資短缺數(shù)最低的解。由圖中可以看出,當(dāng)引入緊迫度后,物資短缺數(shù)最低是通過優(yōu)先滿足緊迫度高的災(zāi)區(qū)的需求來得到,因為實驗得到的是一個Pareto 解集,所以決策者可以在此基礎(chǔ)上,犧牲一些物資短缺數(shù),將緊迫度中等災(zāi)區(qū)的物資分出一些給緊迫度低的災(zāi)區(qū),實現(xiàn)公平的最大化。而未引入緊迫度的結(jié)果中,物資會優(yōu)先滿足需求量少的災(zāi)區(qū),而對于一些受災(zāi)嚴(yán)重且需求量大的災(zāi)區(qū),無法做到及時配送,所以無法實現(xiàn)公平分配。

3.5 超啟發(fā)算法策略比較

為了更好地求解提出的選址—配送問題,本文選擇不同的高層選擇策略與接受準(zhǔn)則對其優(yōu)化,以便找到最好的組合。不同策略組合的實驗結(jié)果如圖5和表5 所示。

表5 不同策略組合在求解選址-配送問題時的結(jié)果

圖5 不同策略組合下的Pareto 解

表6 比較了不同策略組合得到的解的性能指標(biāo)。從表中可以看出,使用TS 和CF 策略時,HV 的取值會得到提高,說明這2 種選擇策略取得的解非支配性更強。在NPS 指標(biāo)上,使用AM、AA 和RU 策略會得到更多的Pareto 解,而SA 策略則效果平平。在SM 指標(biāo)上,使用AM 和AA 取得的值會更小,說明該策略取得的解更加均勻,而RU 策略取得的解,SM的值普遍偏大。在HV 指標(biāo)上,使用AA 和RU取得的值會普遍偏大。根據(jù)實驗結(jié)果,選擇對于NPS大于90 的值、對于SM小于13 的值以及對于HV大于3.01×106的值進行標(biāo)記。在表中可以看出,3 個指標(biāo)都被標(biāo)記的策略有SR +AA、TS +AM、TS+AA、CF+AA。綜合考慮3 個指標(biāo)的值可以看出,TS+AA 策略的組合在求解選址—配送問題時能起到比較好的效果。

3.6 算法比較

為了進一步說明超啟發(fā)算法在求解應(yīng)急救災(zāi)物資選址—配送問題上的有效性,本文選取超啟法算法最優(yōu)的組合策略,與NSGA-II[25](non-dominated sorting genetic algorithm II)、MOPSO[26]相比。對于實驗的案例,本文隨機產(chǎn)生了不同規(guī)模的選址—配送問題,且假設(shè)配送的救災(zāi)物資均為食物和水,但是配送中心與災(zāi)區(qū)的數(shù)量是不一致的。本文一共產(chǎn)生了10 個不同規(guī)模的例子,并比較了3 種不同方法產(chǎn)生的解。不同算法在求解不同規(guī)模問題時的結(jié)果如表7 所示。不同算法求得的解的性能指標(biāo)見表8。其中案例1-3-6-3-2 表示實例1 有3 個臨時配送中心、6 個受災(zāi)區(qū)域、3 個倉庫規(guī)模、2 種應(yīng)急資源類型,其他以此類推。

表7 不同算法在求解不同規(guī)模問題時的結(jié)果

表8 不同算法求得的解的性能指標(biāo)

針對10 個不同規(guī)模的選址—配送問題,本文提出的超啟發(fā)算法在大多數(shù)情況下都能起到更好的效果。就性能指標(biāo)而言,本文提出的MOHH 得到的平均NPS為91.9,NSGA-II 的平均NPS為87.1,MOPSO 的平均NPS為90.9,所以MOHH 在NPS 上略優(yōu)于其余算法。在SM 指標(biāo)上,大多數(shù)的案例之下,MOHH 求出的解的值都會優(yōu)于其余算法,其中有2個案例,MOPSO 求出的解的值會略優(yōu)于其余算法,其中,MOHH 求出的解的平均SM值為12.15,NSGA-II 求出的解的平均SM值為14.28,MOPSO 求出的解的平均SM值為13.50,所以本文提出的算法取得的解能夠得到更小的平均間距,也就是解的分布更加均勻。在HV 指標(biāo)上,本文提出的MOHH 能在所有案例上都能取得領(lǐng)先其余算法的結(jié)果,其中,MOHH 求出的解的平均HV值為2.637×106,NSGA-II 求出的解的平均HV值為2.560×106,MOPSO求出的解的平均HV值為2.576×106,說明本文提出的MOHH 求得的解無論是在均勻性上還是非支配性上都會更強。因此,在求解本文提出的模型時,MOHH 求出的解在所提指標(biāo)上會優(yōu)于NSGA-II 和MOPSO 求出的解。

4 結(jié)論

本文建立了應(yīng)急救災(zāi)物資選址—配送問題的雙目標(biāo)數(shù)學(xué)模型,并將其用于提高物資配送系統(tǒng)的時效性與公平性。所建立的多目標(biāo)模型的第1 個主要目標(biāo)是優(yōu)化物資配送成本,包括兩階段的運輸成本、時間成本和配送中心的運營成本;第2 個主要目標(biāo)是考慮災(zāi)區(qū)緊迫程度的同時,優(yōu)化災(zāi)區(qū)物資的短缺數(shù)量。為了解決這個問題,設(shè)計了一個MOHH 算法框架,并提出了3 種高層選擇策略和4 種接受準(zhǔn)則,分別組合進行求解。同時使用了3 個性能指標(biāo)來對產(chǎn)生的解進行評價,以便得出最佳的策略組合。

通過實驗,本文驗證了模型的有效性,它能夠在保證時效性的同時兼顧公平性。同時,根據(jù)超啟發(fā)算法的策略比較,得出TS-AA 是最佳高層啟發(fā)式策略組合。最后通過與經(jīng)典多目標(biāo)求解算法NSGA-II以及MOPSO 在不同規(guī)模的案例上進行比較,進一步驗證了本文所提的MOHH 的有效性。

下一步的研究重點會考慮在模型上進行深入,從本文的單供應(yīng)點到多供應(yīng)點,再到多供應(yīng)點與臨時配送中心之間的聯(lián)合配送,以提出更多符合實際情況的模型。同時在多目標(biāo)超啟發(fā)算法的框架中,提出更多有效的高層策略,以便獲得更好的優(yōu)化效果。