基于多目標(biāo)優(yōu)化的應(yīng)急設(shè)施選址配送模型

吉 康，劉 倩

(1. 南京市城市與交通規(guī)劃設(shè)計(jì)研究院股份有限公司，南京 210018；2. 常州工學(xué)院 經(jīng)濟(jì)與管理學(xué)院，常州 213001)

隨著人類社會(huì)不斷發(fā)展，自然環(huán)境遭受的破壞加重，社會(huì)矛盾逐漸突出，各類突發(fā)事件頻發(fā)。面對(duì)突發(fā)事件，科學(xué)合理的應(yīng)急設(shè)施選址與配送路徑規(guī)劃，對(duì)開展應(yīng)急救援工作、減少突發(fā)事件損失具有極為重要的意義。

傳統(tǒng)的應(yīng)急設(shè)施選址模型，如P-中值模型、P-中心模型和覆蓋模型等，已有較為成熟的研究應(yīng)用。孫華麗等[1]基于P-中值模型進(jìn)行不確定信息下的應(yīng)急設(shè)施選址方案魯棒優(yōu)化，確保應(yīng)急物流系統(tǒng)的風(fēng)險(xiǎn)應(yīng)對(duì)能力。郗蒙浩等[2]以各個(gè)應(yīng)急救援需求點(diǎn)到應(yīng)急設(shè)施的加權(quán)距離和最小為優(yōu)化目標(biāo)，提出了一種考慮區(qū)域自然災(zāi)害風(fēng)險(xiǎn)區(qū)劃的改進(jìn)P-中值模型，并采用變鄰域算法進(jìn)行求解，可同步獲得最優(yōu)應(yīng)急設(shè)施選址與分配方案。

應(yīng)急設(shè)施選址是一個(gè)具有社會(huì)性、時(shí)效性和經(jīng)濟(jì)性的綜合問題，部分研究在模型構(gòu)建中以約束條件或目標(biāo)函數(shù)的形式增加了對(duì)相關(guān)影響因素的考慮[3]。陳剛等[4]構(gòu)建了一種考慮居民選擇行為的應(yīng)急避難所選址模型，基于競(jìng)爭(zhēng)效用理論評(píng)價(jià)居民的避難所選擇行為，并分別采用非線性整數(shù)規(guī)劃與模擬退火算法進(jìn)行求解。汪文文等[5]構(gòu)建了一種多目標(biāo)動(dòng)態(tài)選址模型，分別以物資效用、災(zāi)區(qū)滿意度和配送中心數(shù)量反映選址方案的時(shí)效性、公平性和均衡性，并基于NSGA-Ⅱ獲取模型的局部最優(yōu)解。Feng等[6]同時(shí)以最小化總旅行距離和最小化總運(yùn)輸成本為優(yōu)化目標(biāo)，進(jìn)行城市應(yīng)急設(shè)施選址，并設(shè)計(jì)了一種變權(quán)算法，采用不同的權(quán)重因子構(gòu)建輔助函數(shù)對(duì)模型進(jìn)行求解。

在配送路徑規(guī)劃方面，現(xiàn)有研究多基于帶約束的車輛路徑問題[7]。呂偉等[8]構(gòu)建了一種考慮受災(zāi)點(diǎn)需求時(shí)間窗的應(yīng)急物資配送模型，基于時(shí)間懲罰成本與物資滿足狀況設(shè)置軟、硬兩種時(shí)間窗約束，以確保路徑規(guī)劃方案的有效性。康斌等[9]建立了一種多目標(biāo)應(yīng)急救援物資配送路徑規(guī)劃模型，以最小化配送完成時(shí)間提高物資配送效率，以最小化需求未滿足率保證配送公平性，進(jìn)行物資配送方案制定。Li和Chung[10]探討了需求不確定條件下的應(yīng)急物資配送路徑規(guī)劃問題，并提出了一種混合啟發(fā)式算法對(duì)問題進(jìn)行求解。

應(yīng)急設(shè)施選址與配送路徑規(guī)劃具有緊密的聯(lián)系，應(yīng)急設(shè)施選址決定了配送路徑規(guī)劃的輸入條件，配送路徑規(guī)劃則是評(píng)價(jià)應(yīng)急設(shè)施選址方案有效性最直接的指標(biāo)。因此，將應(yīng)急設(shè)施選址和配送路徑規(guī)劃聯(lián)合考慮，具有重要意義。

本文構(gòu)建了一種基于多目標(biāo)優(yōu)化的應(yīng)急設(shè)施選址-配送模型，分別從時(shí)效、容量和成本的角度實(shí)現(xiàn)目標(biāo)優(yōu)化，以同步解決應(yīng)急設(shè)施的選址-配送問題，并采用NSGA-Ⅱ?qū)λ岢龅哪Ｐ瓦M(jìn)行求解，從而為系統(tǒng)性的應(yīng)急設(shè)施選址-配送方案的制定提供參考依據(jù)。

1 模型構(gòu)建

1.1 基本假設(shè)

模型構(gòu)建的基本假設(shè)主要包括：①道路網(wǎng)絡(luò)情況已知，可形成網(wǎng)絡(luò)任意兩節(jié)點(diǎn)間的有效連接；具備先進(jìn)的應(yīng)急調(diào)度系統(tǒng)，各個(gè)應(yīng)急設(shè)施服從系統(tǒng)聯(lián)合調(diào)配。②各個(gè)應(yīng)急設(shè)施的相應(yīng)資源能夠滿足所有集散點(diǎn)的總需求；各個(gè)集散點(diǎn)基于公平性原則進(jìn)行資源獲取[11]。

1.2 參數(shù)和變量

模型構(gòu)建參數(shù)如表1所示。變量如表2所示。

表1 模型構(gòu)建參數(shù)

表2 變量

1.3 目標(biāo)函數(shù)

模型目標(biāo)函數(shù)見式(1)～式(3)。

(1)

(2)

(3)

式中，f1為要求最小化總物資運(yùn)輸時(shí)間成本，包括所有車輛在網(wǎng)絡(luò)中進(jìn)行物資配送的運(yùn)輸時(shí)間，以確保選址-配送方案的時(shí)效性；f2為要求最大化應(yīng)急設(shè)施的設(shè)置容量，以確保應(yīng)急設(shè)施物資儲(chǔ)備；f3為要求最小化應(yīng)急設(shè)施的設(shè)置數(shù)量，以盡可能降低應(yīng)急設(shè)施設(shè)置成本。

1.4 約束條件

約束條件見式(4)～式(6)。

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

式(4)限制了變量的內(nèi)在約束關(guān)系，即進(jìn)行應(yīng)急設(shè)施選址的同時(shí)，完成集散點(diǎn)分配。應(yīng)急設(shè)施從網(wǎng)絡(luò)中的備選點(diǎn)進(jìn)行選擇，因此式(5)要求應(yīng)急設(shè)施設(shè)置數(shù)量不能超過網(wǎng)絡(luò)中的備選點(diǎn)數(shù)量。式(6)確保網(wǎng)絡(luò)中所有應(yīng)急設(shè)施的總物資容量必須超過全部集散點(diǎn)的總物資需求。式(7)確保單個(gè)應(yīng)急設(shè)施物資容量必須超過該應(yīng)急設(shè)施所服務(wù)的全部集散點(diǎn)的總物資需求。式(6)和式(7)要求選址-配送方案的物資儲(chǔ)存必須能夠滿足物資需求。式(8)確保所有集散點(diǎn)均分配應(yīng)急設(shè)施。式(9)確保每個(gè)集散點(diǎn)僅被分配1個(gè)應(yīng)急設(shè)施。即式(8)和式(9)要求集散點(diǎn)不遺漏、不重復(fù)地分配至應(yīng)急設(shè)施，從而構(gòu)成集散點(diǎn)全覆蓋約束。式(10)為車輛運(yùn)載容量約束，要求車輛在運(yùn)輸過程中的物資分發(fā)數(shù)量不得超過其最大裝載容量。式(11)確保集散點(diǎn)獲得物資數(shù)量不得超過其物資需求量。式(12)為網(wǎng)絡(luò)流量平衡約束，確保任意節(jié)點(diǎn)的車輛抵達(dá)次數(shù)等于該節(jié)點(diǎn)的車輛出發(fā)次數(shù)。

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

本文所構(gòu)建的應(yīng)急設(shè)施選址-配送模型為典型的多目標(biāo)優(yōu)化問題，通常難以使得各個(gè)優(yōu)化目標(biāo)同時(shí)達(dá)到最優(yōu)，因此可尋找其Pareto(帕累托)最優(yōu)解。遺傳算法是求解多目標(biāo)優(yōu)化問題的有效方法，具有適應(yīng)性強(qiáng)、搜索覆蓋面大的優(yōu)點(diǎn)[12-13]。根據(jù)趙星等[14]研究成果，本文結(jié)合快速非支配排序，設(shè)計(jì)了一種多目標(biāo)遺傳算法，以快速有效地獲取最優(yōu)選址-配送方案。算法流程如圖1所示。

圖1 算法流程

染色體編碼規(guī)則為：采用實(shí)數(shù)編碼，每個(gè)染色體由2個(gè)子串組成：子串1的基因數(shù)量為X，對(duì)應(yīng)每一個(gè)集散點(diǎn)，基因值為1到nv的隨機(jī)整數(shù)，表示集散點(diǎn)與應(yīng)急車輛之間的服務(wù)關(guān)系；子串2的基因數(shù)量為Y，對(duì)應(yīng)每一輛車，基因值為1到ns的隨機(jī)整數(shù)，表示車輛與應(yīng)急設(shè)施的歸屬關(guān)系。

步驟0：初始化。輸入最大迭代次數(shù)nmax、交叉概率pc和變異概率pe[13](交叉概率和變異概率取值范圍分別為0.1≤pc≤0.9和0

步驟1：令n=0，生成初始種群。根據(jù)染色體編碼規(guī)則，在約束條件控制下，組合網(wǎng)絡(luò)中的備選節(jié)點(diǎn)、車輛與集散點(diǎn)，形成選址-配送方案，并計(jì)算方案目標(biāo)函數(shù)值f1、f2和f3。在此基礎(chǔ)上，不斷生成方案?jìng)€(gè)體并將其納入初始種群集合Pn中，直至初始種群中的個(gè)體數(shù)達(dá)到np。

步驟2：生成子代種群。不斷從父代種群Pn中選擇父代個(gè)體，根據(jù)交叉概率pc與變異概率pe，采用輪盤賭規(guī)則執(zhí)行交叉和變異操作，生成子代個(gè)體，將滿足模型約束條件的子代個(gè)體納入子代種群中，得到子代種群Pg。

步驟4：修剪種群。根據(jù)序值將種群Pt中的所有個(gè)體進(jìn)行排序，選擇其中前np個(gè)個(gè)體形成新種群Pn，完成種群修剪。

步驟5：檢驗(yàn)迭代終止條件。若n≤nmax，則令n=n+1，并重新進(jìn)入步驟2；反之，進(jìn)入步驟6。

步驟6：將種群Pn中全部序值為1的個(gè)體納入Pareto解集F1?；赑areto解集F1，引入各個(gè)優(yōu)化目標(biāo)的權(quán)重，計(jì)算模型綜合目標(biāo)函數(shù)，獲取模型最優(yōu)解。

(1) 基于離差標(biāo)準(zhǔn)化公式，見式(13)，將模型的各優(yōu)化目標(biāo)f1、f2、f3進(jìn)行標(biāo)準(zhǔn)化。

(13)

(2) 優(yōu)化目標(biāo)f1、f2、f3的權(quán)重值分別設(shè)置為μ1、μ2、μ3，μ1+μ2+μ3=1，模型綜合目標(biāo)函數(shù)見式(14)。此時(shí)，對(duì)應(yīng)最小F′(u)的解即為模型最優(yōu)選址-配送方案。

(14)

3 案例分析

為了驗(yàn)證所提模型和求解算法的有效性，本試驗(yàn)基于蘇爾福斯網(wǎng)絡(luò)(Sioux Falls network)進(jìn)行了案例分析[15]。

蘇爾福斯網(wǎng)絡(luò)如圖2所示，網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)與路段已進(jìn)行編號(hào)。假設(shè)各路段均設(shè)有應(yīng)急專用車道，應(yīng)急車輛在各路段的通行時(shí)間如表3所示。

圖2 蘇爾福斯網(wǎng)絡(luò)

表3 應(yīng)急車輛在各路段的通行時(shí)間

以消毒液為例，假設(shè)集散點(diǎn)物資需求如表4所示，備選點(diǎn)庫(kù)容如表5所示，應(yīng)急車輛資源充足，最大裝載容量為50箱，要求在網(wǎng)絡(luò)所有備選點(diǎn)中進(jìn)行一級(jí)應(yīng)急設(shè)施選址，并獲取二級(jí)物資配送方案。在此基礎(chǔ)上，采用本試驗(yàn)方法對(duì)案例進(jìn)行求解，模型相應(yīng)參數(shù)設(shè)置如下：最大迭代次數(shù)nmax為100，交叉概率pc為0.9，變異概率pe為0.1，初始種群數(shù)量為10個(gè)。本案例中優(yōu)先考慮應(yīng)急設(shè)施設(shè)置成本(目標(biāo)函數(shù)f3)，其次考慮方案時(shí)效性(目標(biāo)函數(shù)f1)，再次考慮設(shè)施容量(目標(biāo)函數(shù)f2)，因此各優(yōu)化目標(biāo)的權(quán)重μ1、μ2、μ3分別設(shè)置為0.3、0.2、0.5(各優(yōu)化目標(biāo)權(quán)重可根據(jù)實(shí)際需求進(jìn)行調(diào)整)。

表4 集散點(diǎn)物資需求

表5 備選點(diǎn)庫(kù)容

經(jīng)過算法求解，獲得應(yīng)急設(shè)施選址-配送方案，如表6所示，應(yīng)急設(shè)施選址為節(jié)點(diǎn)4、14、16，各個(gè)應(yīng)急設(shè)施的庫(kù)容均超過所分配的集散點(diǎn)物資需求總量。該方案的模型綜合目標(biāo)函數(shù)為0.62，總物資運(yùn)輸時(shí)間成本為276 min，應(yīng)急設(shè)施總庫(kù)容為500箱，應(yīng)急設(shè)施設(shè)置為3個(gè)。

表6 應(yīng)急設(shè)施選址-配送方案

基于相同的應(yīng)急設(shè)施設(shè)置數(shù)量，本試驗(yàn)依據(jù)郗蒙浩等[2]研究結(jié)果，采用傳統(tǒng)P-中值模型進(jìn)行應(yīng)急設(shè)施選址，采用插入算法進(jìn)行配送方案設(shè)計(jì)，獲得對(duì)照方案，如表7所示。該對(duì)照方案的總物資運(yùn)輸時(shí)間成本為282 min，應(yīng)急設(shè)施總庫(kù)容為500箱。將兩種方案進(jìn)行對(duì)比可以發(fā)現(xiàn)：兩種方案均滿足模型所提出的全部約束條件；但是相比于對(duì)照方案，模型方案的總物資運(yùn)輸時(shí)間成本有所降低，并且模型方案可少調(diào)用1輛應(yīng)急車輛。結(jié)果表明，本試驗(yàn)所提出的模型與算法能夠同步解決應(yīng)急設(shè)施選址與配送路徑規(guī)劃問題，并且能夠有效協(xié)助決策應(yīng)急設(shè)施設(shè)置數(shù)量，相比于傳統(tǒng)方法具有優(yōu)越性。

表7 對(duì)照方案

4 結(jié)論

本文主要研究突發(fā)事件下的應(yīng)急設(shè)施選址-配送問題，構(gòu)建了一種基于多目標(biāo)優(yōu)化的應(yīng)急設(shè)施選址-配送模型，可實(shí)現(xiàn)應(yīng)急設(shè)施選址方案與配送路徑規(guī)劃方案的同步求解。從時(shí)效、容量、成本的角度提出了3個(gè)優(yōu)化目標(biāo)，分別要求最小化總物資運(yùn)輸時(shí)間成本、最大化應(yīng)急設(shè)施設(shè)置容量和最小化應(yīng)急設(shè)施設(shè)置數(shù)量。為了求解所提出的模型，結(jié)合快速非支配排序，設(shè)計(jì)了多目標(biāo)遺傳算法以獲取模型Pareto最優(yōu)解。通過基于蘇爾福斯網(wǎng)絡(luò)的案例測(cè)試，可以發(fā)現(xiàn)所提出的模型與算法能夠有效地解決應(yīng)急設(shè)施選址-配送問題，相比于傳統(tǒng)方法具有優(yōu)越性，可為相關(guān)的應(yīng)急管理提供參考與支撐。