考慮時(shí)效性與公平性的應(yīng)急物資選址配送問題及算法研究①

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

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

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

0 引言

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

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

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

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

1.1 問題描述

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

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

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

1.2 條件假設(shè)

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

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

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

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

1.3 模型建立

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

其中,c0i表示物資儲(chǔ)備庫到i的單位運(yùn)輸成本,表示從物資儲(chǔ)備庫到點(diǎn)i運(yùn)送的第k種物資的量,t0i表示物資儲(chǔ)備庫到點(diǎn)i的行駛時(shí)間,ei表示分配中心i的運(yùn)行成本,cij表示從點(diǎn)i到點(diǎn)j的單位運(yùn)輸成本表示從點(diǎn)i到點(diǎn)j運(yùn)送的第k種物資的量,tij表示點(diǎn)i到點(diǎn)j的行駛時(shí)間。

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

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

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

服從以下約束:

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

2 算法設(shè)計(jì)

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

2.1 初始化個(gè)體策略

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟4合并父子種群。

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

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

步驟8生成Pareto 前沿。

3 實(shí)驗(yàn)與分析

3.1 實(shí)例驗(yàn)證

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

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

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

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

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

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

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

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

3.3 性能指標(biāo)

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

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

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

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

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

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

3.4 模型分析

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

圖3 不同的ω 取值對(duì)時(shí)間成本以及其他成本的影響

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

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

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

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

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

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

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

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

3.6 算法比較

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

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

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

針對(duì)10 個(gè)不同規(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 求出的解的值都會(huì)優(yōu)于其余算法,其中有2個(gè)案例,MOPSO 求出的解的值會(huì)略優(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 求得的解無論是在均勻性上還是非支配性上都會(huì)更強(qiáng)。因此,在求解本文提出的模型時(shí),MOHH 求出的解在所提指標(biāo)上會(huì)優(yōu)于NSGA-II 和MOPSO 求出的解。

4 結(jié)論

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

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

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