應急物資儲備點選址多目標優化模型及算法研究*

馮艦銳，蓋文妹

(中國地質大學(北京) 工程技術學院，北京 100083)

0 引言

隨著城市的不斷發展，建筑物、各類網絡系統工程密集程度增加。地震、洪水、颶風等自然災害以及火災、爆炸、泄漏等事故災難一旦發生，城市內部的公眾安全將面臨極大威脅，救援工作難度加大[1]。在城市中各類防救災設施(消防機構，避難場所，物資場所等)的設置均有規劃標準[2-3]，選擇合適的地址對緊急情況下的人力物力的節約有重要意義。建立應急資源儲備點來滿足物流的配送要求，就必須考慮儲備點的位置及其優化問題。

選址的優化問題近年來已成為一個研究熱點，陳國華等[4]基于博弈論的思想，從安全性、可達性、適宜性3 個方面構建化工園區應急避難點選址評估指標體系，并結合AHP和熵值法的組合賦權法，對指標權重進行賦權；吳坷等[5]基于弗洛伊德最短路徑算法模型，以時間成本作為目標函數值，確定應急資源儲備點的個數以及位置分布的最優方案；吳健宏等[6]開發了基于GIS和多目標規劃模型的決策支持系統，對選址優化問題進行研究；田書冰等[7]采用云模型，對水域風險評價體系進行評價，采用自適應差分進化算法，對構建的加權距離最小為目標的溢油應急設備點選址模型進行求解；朱建明[8]以時效性、均衡性和魯棒性3個方面構建應急選址多目標優化模型，利用理想點目標擾動最小化模型和遺傳算法說明了模型和算法的有效性；陳志宗等[9]在建立模型的過程中，綜合考慮了其公平性和效率性，同時結合最大覆蓋模型來驗證模型的正確性；姜濤等[10]利用魯棒優化的方法，建立不確定性應急選址模型，并給出模型正確性分析；韓強[11]將應急選址優化問題與模擬退火算法結合，通過仿真驗證多目標優化問題的有效性。綜合以上現有研究發現，在選址方面進行多目標優化時，大多沒有對改變各個目標的權重對結果的影響進行探究。因此，本文綜合考慮總路程最短、成本最小2個方面，基于智能算法[12-13]和運籌學中求解多目標優化問題[14-17]的理論和方法，通過引入并改變權重[18]探究不同權重下路程和成本對應急資源儲備點的選址影響，改進并設計提出求解權重的算法，并以此為基礎拓展到3個及3個以上的情況，以及其他領域選址問題。具體模擬分析過程中，為了簡化問題，通過使用鄰接矩陣表示交通網絡，并使用0-1管轄矩陣描述儲備點與受災地點之間約束關系，以此為基礎建立多目標與多約束模型，得到儲備點的最佳選址。

1 應急物資儲備點選址多目標優化模型

1.1 問題提出

正常環境下的企業運輸調度通常考慮的是經濟性，但是出現災害情況下的救援物資運輸調度與前者不同，它考慮更多的是時效性[19]。第一，緊急情況下時間是最寶貴的資源，縮短救援時間就能拯救更多的生命，減少財產損失，所以在任何緊急情況下，時間是不可忽視的決策屬性之一；第二，合理的救援物資儲備點選址方案可以減小救援物資的周轉量，降低運輸費用，節約能源，為緊急狀態下的緩解運量大、運輸時間集中以及各個儲備點的工作量差異的問題提供解決方案。

綜上，影響應急資源儲備點服務范圍的主要因素是到達時間和經濟性。在遇到緊急情況下，應急物資儲備點的選址，可以要求從救援物資儲備點到受災地點的運輸線路的時效性和經濟性2個目標進行優化。

1.2 模型建立

應急救援物資儲備點的選址問題本質上屬于多目標問題，同時也是在緊急條件下的物資調度問題。它是要求滿足物資周轉時間最短的情況下，提高經濟性，在時效性和經濟性2個目標約束下，選擇合適的儲備點。

對于此類雙目標決策問題，本文通過計算受災地點與應急資源儲備點的最短路徑，進而為受災地點分配距離最近的應急資源儲備點。在滿足不超過一定時間到達受災地點的條件下，考慮整個物資周轉的經濟性，降低運輸費用，得到更加合理的服務分配方案。

在初期的選址中，容易確定m個備選點，在m個備選點中選出最佳儲備點。為了使所述問題更方便用數學模型解決，假設接到預警后，應急資源儲備點立即展開配送行動，無延時。

為了便于描述，可以用T=(J，E)表示一個交通網絡圖，其中頂點集合J={j}中的元素，表示每個受災地點的編號；集合E={eja,jb}中的元素，表示相鄰受災地點ja到jb的路程，單位：km，ja與jb的位置坐標可用(xa，ya)與(xb，yb)表示；假設i為應急資源儲備點的編號；T中有N個節點、n個受災地點，可以得到：

1≤m,n≤N

1

另外，為了方便利用0-1規劃解決問題，可添加另一個0-1矩陣表示所有儲備點的服務范圍，其中的元素xij表示儲備點i是否管轄受災地點j，當取值為1時表示有服務關系；取值為0時表示沒有服務關系。如式(1)所示。

(1)

為應急資源儲備點分配管轄范圍以及配送時，為每個應急資源儲備點選擇合理路徑，需要獲得儲備點到所有受災地點間的最短路徑，按照最短路徑算法可以得到備選點到受災地點之間的距離，就可以定義為最短路程，如式(2)～(3)所示。

lij=xij·eij

(2)

(3)

式中：lij為儲備點i與受災地點j間的最短路程，單位：km；S為各條路徑的之和，即總路程，單位：km。

此外，還需要考慮經濟性目標，希望在物資運送過程中，能源消耗最低，這不僅與道路長度有關，而且還與道路的通行難易程度有關，比如上坡下坡、拐彎數量以及右轉交通燈占交通燈總數等。因此，可以計算出相應路段的經濟性權重，如式(4)所示。

cij=dij×xij

(4)

式中：dij表示儲備點i到受災地點j的經濟消耗水平，包括人力資源消耗與能源消耗等。

本文所研究的應急物資儲備點的雙優化目標可以表示為：

(5)

(6)

(7)

(8)

式中：約束(7)表示所有受災地點都至少需要1個儲備點來服務；約束(8)中，v為車輛的平均速度，表示物資配送時間在一個可以接受的范圍內，在實際應用過程中，可以改變a的值對目標進行限定，而a可以用來表示從儲備點到受災地點的時間，所以，約束(8)表示為滿足一定的應急決策需求。

2 模型求解

道路下最優方案未必是經濟成本的最優方案，考慮到算法未來的應用與拓展，同時降低計算的復雜度，減少緊急情況下的反應時間，借助加權法并應用變權的思想構造輔助決策函數。

2.1 模型轉化與輔助函數構建

為解決2個目標的優化問題，引用權重λ得到1個無量綱數wij。

wij=λlij+(1-λ)cij

(9)

借助加權法，就可以將式(5)～(6)轉化為單目標優化問題。

(10)

本文所建立的選址模型，實際上是求解滿足式(8)的最優方案P。但是加權系數λ的賦值是一個關鍵問題，為了解決這個問題，構造1個基于式(8)的決策函數，用fk表示一個關于權重λ與W的對應關系：

y=fk(λ),λ∈[0,1]，k∈{1,2,…,X}

令Pλ表示滿足約束條件的1個解，利用Pλ可構造另外2個輔助決策函數：

y=f1k(λ)=λlij(Pλ)，

y=f2k(λ)=(1-λ)cij(Pλ)

式中：λ∈[0，1]，k∈{1,2,…,X}；f1k(λ)表示權重與路程的對應關系；f2k(λ)表示權重與成本的對應關系，且fk(λ)=f1k(λ)+f2k(λ)。可證明輔助函數有如下性質成立。

性質：輔助函數y=f1k(λ)遞增時，y=f2k(λ)遞減，且分別在λ=0和λ=1時取得最小值，如圖1所示。

證明：對W(P)取關于λ的微分，可以得到：

顯然，W隨lij的增大而增大，隨cij的增大而減小。

圖1 輔助函數性質示意Fig.1 Auxiliary function of the schematic

2.2 算法設計

根據輔助函數的性質，為了得到滿足式(5)和式(6)的備選儲備點，可利用Dijkstra算法作為底層算法求解lij，由于2個輔助函數分別單調遞增和單調遞減，可以將區間[α，β]細分為N份，只要取中間點驗證是否滿足約束(8)，直到找到1個不滿足約束的點，改變搜索范圍，縮短搜索區間，更新區間位置。令λ取值為k(β-α)/N，迭代過程中每次增加(β-α)/N，當得到滿足約束(8)時，對α和β重新賦值以更新位置；當區間的長度小于精度ε時，就可以得到1個較小的近似區間[α，β]，輸出此時賦值后的λ=(α+β)/2，即為1個滿足條件的優化解。得到λ后，可以根據式(9)確定wij，此時，雙目標優化問題轉化為單目標優化問題，借助現有的Mat-lab優化工具箱即可得到關于xij的二維m×n矩陣，即應急救援物資儲備點和受災地點的對應關系。具體流程如圖2所示。

圖2 應急物資儲備點選址雙目標優化算法Fig.2 Algorithm of bi-objective optimum site selection

2.3 含3個及以上優化目標的最佳選址算法

在實際情況中，常常出現多種情況，應急救援物資儲備點的多目標優化搜索算法可以以雙目標優化算法為基礎，增加多個權重因子，可以使含3個及以上的優化目標的最佳選址問題的求解變得容易。假設一個優化問題含有X個目標，若X>2，可將多目標優化問題分解為X個單目標優化問題。求解一個任意單目標優化問題時，可以把區間[0，1]分為若干份，獲得一系列局部最優解Pi，其中i=1，2，…，N。由于多目標優化要使各個目標同時達到綜合的最優值，含有多個目標的優化結果可能存在多組解。令集合A=P1∩P2∩…∩PX，那么集合A中滿足目標及約束條件的解即為最優解，如果集合A為空集，則需要改變限定條件或精度ε重新迭代計算；如果這樣的集合A不止1個就可以稱為最優解集。

2.4 算法終止條件及優勢分析

為在有限時間里解決這一問題，不能單單追求數值上的最優解，由于實際多目標優化問題較為復雜，可能存在多組改進的解，這就需要為決策者提供幾種不同的方案，所以必須為該算法循環部分增加1個終止條件α-β<ε，使算法終止于決策者可接受的精度范圍；其次，選取合適的N值可以提高求解效率，減少迭代時間。因為若N值過大，會因為區間過多而使尋找和迭代的次數過多，使求解效率降低，并且可能存在多個相鄰點；如果N值過小，則可能丟失部分值并且同樣使尋找時間增加，N值的確定可以通過多次模擬得到。

本文提出的多目標變權優化選址算法在應急管理中優勢分析如下：

1)算法將緊急條件下的應急救援物資儲備點選址的多目標優化問題和物資車輛的調度優化結合，利用車輛調度的最優化來確定最優選址，并建立合理的選址多目標優化數學模型，從運輸路程和運輸成本2個方面進行分析。借助可變權重構造輔助函數，并在輔助函數構成的搜索區間上尋找最優解。

2)算法為了保持較高的求解效率，采用啟發式的思想，而不是在各個方向平均搜索，算法求解的區域相對普通多目標優化的算法小，區域縮小的速度快。

3)通過輔助函數的性質可知，令λ取值為k(β-α)/N，迭代過程中每次增加(β-α)/N，當得到滿足條件的區間時，對α和β重新賦值以更新位置。當β-α縮小到可以接受的范圍時，可根據模擬值繪制出輔助決策函數與參數λ的關系曲線。這樣可根據所建立的應急救援物資儲備點選址模型及算法，為決策者提供緊急情況下的選址優化方案，也可以通過加約束條件在可以接受的范圍內提前終止算法，輸出目前的局部最優解。在應急決策中，還可以根據實際情況改變目標和約束條件，形成適應于實際情況的應急救援物資儲備點選址的優化方法。

3 算例分析

為了驗證算法的正確性及優勢，求解效率、輔助函數性質的正確性，本次算例的模擬選擇某市的隨機路網作為測試網絡。受災點之間，以及和儲備點之間的距離可以通過GIS得到，獲取距離矩陣的數據可以選擇從.xls文件或者地理信息系統數據庫導入。利用Mat-lab的函數庫，直接調用Dijkskra算法獲取儲備點和受災點的最短路徑，再根據算法進行迭代，就可以得到W與λ的關系。

表1為1個具有30個受災點(編號1～30)和10個備選應急物資儲備點(編號A～J)的距離矩陣，假設受災時所有儲備點不受影響并且都可以使用，網絡中每2個點的距離eij可以用1個10×30的矩陣來表示，通行速度v暫取45 km/h，最長到達時間a取2 h。

對于算法的運算與驗證，在計算機上采用Matlab2016a和Lingo12共同完成， 根據本文提出的雙目標優化模型，借用Dijkstra算法得到各受災點到各應急救援物資儲備點的最短距離矩陣，調用算法得到權重λ與無量綱數W的關系，如圖3所示。其中，時效性和經濟性曲線的變化趨勢都與理論預測相同，在實際應用過程中，決策者要根據實際情況確定時間和經濟成本的上限，這樣就可以得到λ的取值范圍，在這個范圍內，可以有多種方案供決策者選擇。

圖3 λ與W、路程S、經濟成本C的關系Fig.3 Relationship between theλ and W, the distance S, and the economic cost C.

km

表2中列出當λ=0.5時，應急物資儲備點對應的受災點，以及每個儲備點的成本和路程，在10個備選點中選擇了8個。此時，對應的總成本為609.5，總路程為 1 294.2。

表2 應急物資儲備點與受災點對應關系及各點的成本和路程Table 2 Corresponding relationship between emergency material reserve points and disaster points and the total cost and total distance of each point

同時，分析表2中的數據可知：應急物資儲備點和受災點的對應關系并不是均勻的，也就是各個儲備點在災變條件下的工作量不同。基于本文的算法進行選址時，時效性和經濟性能得到較好地滿足，能使運輸路程和運輸成本降到可接受范圍，進而為決策者提供多組合適的儲備點備選位置。

4 結論

1)利用運籌學中求解多目標優化問題的理論和方法，建立應急救援物資儲備點選址數學模型。在此基礎上，借用智能算法中系統動態演化方法，利用可變權重因子構造輔助函數，改變權重因子并反復迭代，可以尋找到最優解的范圍，為決策者提供更多選擇。

2)在求解應急救援物資儲備點選址雙目標優化問題時，通過輔助函數的性質改進并設計雙目標優化和求解權重算法，并以此為基礎推廣到3個及以上優化目標的選址問題，不僅僅可以從時效性和經濟性2個方面進行考慮，還可以加入關于路況、儲備點的工作量以及道路安全性目標等。最后，通過算例驗證了算法的正確性及優勢，求解效率、輔助函數性質的正確性。

3)應急救援物資儲備點選址的多目標優化數學模型適用于災害條件下的應急資源儲備點選址優化問題，同時也可擴展應用到應急管理領域中其他優化與選址問題。

[1] 徐志勝, 馮凱, 白國強,等. 關于城市公共安全可持續發展理論的初步研究[J]. 中國安全科學學報, 2004, 14(1):1.

XU Zhisheng, FENG Kai, BAI Guoqiang, et al. Preliminary Study on Sustainable Development Theory of Urban Community Safety[J]. China Safety Science Journal,2004, 14(1):1.

[2] 馮凱, 徐志勝, 馮春瑩,等. 城市公共安全規劃與災害應急管理的集成研究[J]. 自然災害學報, 2005, 14(4):85-89.

FENG Kai, XU Zhisheng, FENG Chunying, et al. Comprehensive study on urban community safety plan and disaster emergency management[J]. Journal of Natural Disasters,2005, 14(4):85-89.

[3] Hernández J Z, SERRANO J M. Knowledge-based models for emergency management systems[J]. Expert Systems with Applications, 2001, 20(2):173-186.

[4] 陳國華, 夏浩, 高子文. 化工園區應急避難點選址評估模型應用研究[J]. 中國安全生產科學技術, 2017, 13(8):61-66.

CHEN Guohua,XIA Hao,GAO Ziwen.Research on application of evaluation model for emergency shelter location in chemical industrial park[J]. Journal of Safety Science and Technology,2017, 13(8):61-66.

[5] 吳坷, 宋英華, 呂偉. 城鎮應急資源儲備點選址與布局優化研究:考慮暴雨災害和路徑長度[J]. 中國安全科學學報, 2017, 27(9):170-174.

WU Ke,SONG Yinghua,LYU Wei.Research on siting of urban emergency resources depots and layout optimization considering rainstorm disaster and distribution route[J]. China Safety Science Journal, 2017，27(9):170-174.

[6] 吳健宏, 翁文國. 應急避難場所的選址決策支持系統[J]. 清華大學學報(自然科學版), 2011(5):632-636.

WU Jianhong,WENG Wenguo.Decision support system for urban shelter locations[J]. Journal of Tsinghua University(Sci & Tech),2011(5):632-636.

[7] 田書冰, 楊亞東, 田延飛,等. 長江干線中下游溢油應急設備點選址優化[J]. 安全與環境學報, 2017, 17(1):90-93.

TIAN Shubing, YANG Yadong,TIAN Yanfei, et al. On the optimized construction site choice for the oil spilling emergency point in the middle and lower reaches of Yangtze River[J]. Journal of Safety and Environment, 2017, 17(1):90-93.

[8] 朱建明. 損毀情景下應急設施選址的多目標決策方法[J]. 系統工程理論與實踐, 2015, 35(3):720-727.

ZHU Jianming.Methods of multi-objective decision-making for emergency facility location problem under failure scenario[J]. Systems Engineering-Theory&Practice, 2015, 35(3):720-727.

[9] 陳志宗, 尤建新. 重大突發事件應急救援設施選址的多目標決策模型[J]. 管理科學, 2006, 19(4):10-14.

CHEN Zhizong,YOU Jianxin. A Multi-objective Decision Model of Emergency Rescue Facility Location for Large-scale Emergency Incidents[J]. MANAGEMENT SCIENCES IN CHINA, 2006, 19(4):10-14.

[10] 姜濤, 朱金福. 應急設施魯棒優化選址模型及算法[J]. 交通運輸工程學報, 2007, 7(5):101-105.

JIANG Tao, ZHU Jinfu.Robust optimization model and algorithm of eanergency establishment[J]. Journal of Traffic and Transportation Engineering, 2007, 7(5):101-105.

[11] 韓強. 多目標應急設施選址問題的模擬退火算法[J]. 計算機工程與應用, 2007, 43(30):182-183.

HAN Qiang.Simulated anealing algorithm for multi-object emergency location problem[J]. Computer Engineering and Applications, 2007, 43(30):182-183.

[12] 焦巍, 劉光斌. 非線性模型預測控制的智能算法綜述[J]. 系統仿真學報, 2008(24):6581-6586.

JIAO Wei, LIU Guangbin. An overview of intelligent algorithms for predictive control of nonlinear models[J]. Journal of System Simulation, 2008(24):6581-6586.

[13] 余建平, 周新民, 陳明. 群體智能典型算法研究綜述[J]. 計算機工程與應用, 2010, 46(25):1-4.

YU Jianping, ZHOU Xingming, CHEN Ming. Research overview of group intelligent typical algorithms[J]. Computer Engineering and Applications, 2010, 46(25):1-4.

[14] 師立晨, 魏利軍, 吳宗之. 危險品道路運輸多目標路徑優化方法研究[J]. 中國安全生產科學技術, 2006, 2(5):59-63.

SHI Lichen, WEI Lijun, WU Zongzhi. Study on multi-objective path optimization for dangerous goods road transport[J]. Journal of Safety Science and Technology,2006, 2(5):59-63.

[15] KHALAFALLAH A, El-RAYES K. Automated multi-objective optimization system for airport site layouts[J]. Automation in Construction, 2011, 20(4):313-320.

[16] GASPAR-CUNHA A,COVAS J A. Robustness in multi-objective optimization using evolutionary algorithms[M]. Kluwer Academic Publishers, 2008.

[17] 蓋文妹, 蔣仲安, 鄧云峰,等. 應急救援物資車輛運輸路線多目標優化[J]. 北京科技大學學報, 2014(10):1384-1393.

GAI Wenmei,JIANG Zhongan, DENG Yunfeng, et al. Multi-objective route optimization of transporting emergency goods and materials for rescue[J]. Journal of University of Science and Technology Beijing, 2014(10):1384-1393.

[18] 任子暉, 王堅. 一種動態改變慣性權重的自適應粒子群算法[J]. 計算機科學, 2009, 36(2):227-229.

REN Zihui, WANG Jian. An adaptive particle swarm optimization algorithm for dynamic change of inertia weight[J]. Computer science, 2009, 36(2):227-229.

[19] 袁媛, 汪定偉. 災害擴散實時影響下的應急疏散路徑選擇模型[J]. 系統仿真學報, 2008, 20(6):1563-1566.

YUAN Yuan, WANG Dingwei. Route Selection Model in Emergency Evacuation under Real Time Effect of Disaster Extension[J]. Journal of System Simulation, 2008, 20(6):1563-1566.