基于多目標優化的應急設施選址配送模型

吉 康，劉 倩

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

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

傳統的應急設施選址模型，如P-中值模型、P-中心模型和覆蓋模型等，已有較為成熟的研究應用。孫華麗等[1]基于P-中值模型進行不確定信息下的應急設施選址方案魯棒優化，確保應急物流系統的風險應對能力。郗蒙浩等[2]以各個應急救援需求點到應急設施的加權距離和最小為優化目標，提出了一種考慮區域自然災害風險區劃的改進P-中值模型，并采用變鄰域算法進行求解，可同步獲得最優應急設施選址與分配方案。

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

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

應急設施選址與配送路徑規劃具有緊密的聯系，應急設施選址決定了配送路徑規劃的輸入條件，配送路徑規劃則是評價應急設施選址方案有效性最直接的指標。因此，將應急設施選址和配送路徑規劃聯合考慮，具有重要意義。

本文構建了一種基于多目標優化的應急設施選址-配送模型，分別從時效、容量和成本的角度實現目標優化，以同步解決應急設施的選址-配送問題，并采用NSGA-Ⅱ對所提出的模型進行求解，從而為系統性的應急設施選址-配送方案的制定提供參考依據。

1 模型構建

1.1 基本假設

模型構建的基本假設主要包括：①道路網絡情況已知，可形成網絡任意兩節點間的有效連接；具備先進的應急調度系統，各個應急設施服從系統聯合調配。②各個應急設施的相應資源能夠滿足所有集散點的總需求；各個集散點基于公平性原則進行資源獲取[11]。

1.2 參數和變量

模型構建參數如表1所示。變量如表2所示。

表1 模型構建參數

表2 變量

1.3 目標函數

模型目標函數見式(1)～式(3)。

(1)

(2)

(3)

式中，f1為要求最小化總物資運輸時間成本，包括所有車輛在網絡中進行物資配送的運輸時間，以確保選址-配送方案的時效性；f2為要求最大化應急設施的設置容量，以確保應急設施物資儲備；f3為要求最小化應急設施的設置數量，以盡可能降低應急設施設置成本。

1.4 約束條件

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

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

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

2 算法設計

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

圖1 算法流程

染色體編碼規則為：采用實數編碼，每個染色體由2個子串組成：子串1的基因數量為X，對應每一個集散點，基因值為1到nv的隨機整數，表示集散點與應急車輛之間的服務關系；子串2的基因數量為Y，對應每一輛車，基因值為1到ns的隨機整數，表示車輛與應急設施的歸屬關系。

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

步驟1：令n=0，生成初始種群。根據染色體編碼規則，在約束條件控制下，組合網絡中的備選節點、車輛與集散點，形成選址-配送方案，并計算方案目標函數值f1、f2和f3。在此基礎上，不斷生成方案個體并將其納入初始種群集合Pn中，直至初始種群中的個體數達到np。

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

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

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

步驟6：將種群Pn中全部序值為1的個體納入Pareto解集F1。基于Pareto解集F1，引入各個優化目標的權重，計算模型綜合目標函數，獲取模型最優解。

(1) 基于離差標準化公式，見式(13)，將模型的各優化目標f1、f2、f3進行標準化。

(13)

(2) 優化目標f1、f2、f3的權重值分別設置為μ1、μ2、μ3，μ1+μ2+μ3=1，模型綜合目標函數見式(14)。此時，對應最小F′(u)的解即為模型最優選址-配送方案。

(14)

3 案例分析

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

蘇爾福斯網絡如圖2所示，網絡中的各個節點與路段已進行編號。假設各路段均設有應急專用車道，應急車輛在各路段的通行時間如表3所示。

圖2 蘇爾福斯網絡

表3 應急車輛在各路段的通行時間

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

表4 集散點物資需求

表5 備選點庫容

經過算法求解，獲得應急設施選址-配送方案，如表6所示，應急設施選址為節點4、14、16，各個應急設施的庫容均超過所分配的集散點物資需求總量。該方案的模型綜合目標函數為0.62，總物資運輸時間成本為276 min，應急設施總庫容為500箱，應急設施設置為3個。

表6 應急設施選址-配送方案

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

表7 對照方案

4 結論

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