何 靜，朱雙凱，任 曄

（1. 昆明理工大學(xué)交通工程學(xué)院，昆明 650500；2. 昆明地鐵運(yùn)營(yíng)有限公司，昆明 650500）

1 研究背景

近年來(lái)，我國(guó)對(duì)地鐵突發(fā)事件應(yīng)急處置的要求越來(lái)越高，因地鐵運(yùn)營(yíng)具有客流集中、空間封閉等特點(diǎn)，一旦發(fā)生突發(fā)事件，社會(huì)影響巨大，有可能造成嚴(yán)重的生命財(cái)產(chǎn)損失[1]。由于突發(fā)事件通常無(wú)法提前預(yù)見(jiàn)，發(fā)生災(zāi)害的位置事先無(wú)法確定，物資需求數(shù)量、救援時(shí)間也不確定，因此極可能導(dǎo)致突發(fā)事件在第一時(shí)間內(nèi)不能得到妥善處理，貽誤了救援最佳時(shí)機(jī)，造成不必要的損失。目前，我國(guó)許多城市地鐵應(yīng)急儲(chǔ)備點(diǎn)布局不合理，應(yīng)急資源配置不均衡，這給地鐵網(wǎng)絡(luò)化運(yùn)營(yíng)以及應(yīng)急處理等帶來(lái)諸多挑戰(zhàn)。其中，正確合理的地鐵應(yīng)急儲(chǔ)備點(diǎn)選址布局是保證應(yīng)急救援及時(shí)有效的重要前提，對(duì)于提高地鐵應(yīng)急處置水平具有重要意義。

目前學(xué)者們?cè)谠擃I(lǐng)域的研究多集中于應(yīng)急物資儲(chǔ)備點(diǎn)優(yōu)化配置的問(wèn)題，且較多是基于確定模型展開(kāi)的[2-4]，而考慮不確定因素的研究相對(duì)較少。在考慮突發(fā)事件發(fā)生后多種不確定性下的LRP模型時(shí)，Rajali針對(duì)災(zāi)難發(fā)生后定位的不確定性，開(kāi)發(fā)了一種用于救濟(jì)物資供應(yīng)和分配的多目標(biāo)位置分配模型[5]；Chawis在考慮洪水不確定的情況下，探討以救援距離和避難風(fēng)險(xiǎn)指數(shù)為目標(biāo)的避難所選址問(wèn)題，提出了隨機(jī)線性混合整數(shù)規(guī)劃模型[6]；孫華麗等針對(duì)需求點(diǎn)物資需求量和車輛運(yùn)輸時(shí)間的不確定，通過(guò)魯棒優(yōu)化方法，建立了以物資送達(dá)需求點(diǎn)救援時(shí)間之和最小為目標(biāo)的應(yīng)急設(shè)施選址-路徑模型[7]；李建光等通過(guò)離散場(chǎng)景來(lái)表達(dá)避難需求的不確定性，以建設(shè)總成本為目標(biāo)，提出魯棒隨機(jī)規(guī)劃模型，分析不同期望情形與最壞情形下的應(yīng)急避難場(chǎng)所選址[8]；在不確定條件模型處理方式上，Ye等運(yùn)用改進(jìn)的遺傳算法和禁忌搜索算法，求解應(yīng)急車輛定位模型和路網(wǎng)任意點(diǎn)的需求模型[9]。高飛針對(duì)不確定因素下的配送路徑選擇，設(shè)計(jì)了基于證據(jù)推理的不確定多因素路徑選擇方法，利用基于禁忌搜索的混合模擬退火算法來(lái)求解[10]。

綜上所述，已有的研究基本集中在搶修物資不確定這一因素上，對(duì)應(yīng)急儲(chǔ)備點(diǎn)不確定這一因素展開(kāi)的研究很少。此外，大多數(shù)研究缺乏系統(tǒng)性、整體性，基本都是將應(yīng)急儲(chǔ)備點(diǎn)選址和物資配送的路徑分開(kāi)研究，在求解算法上也將其分為兩個(gè)問(wèn)題單獨(dú)求解?；谝陨戏治?，本研究進(jìn)行建模與求解算法的設(shè)計(jì)。考慮了應(yīng)急救援需求點(diǎn)具有一定的時(shí)間窗，構(gòu)建基于相關(guān)機(jī)會(huì)目標(biāo)規(guī)劃理論的地鐵應(yīng)急物資儲(chǔ)備點(diǎn)帶有時(shí)間窗的選址-路徑模型，以應(yīng)急物流總成本最小化和救援時(shí)間最短化為目標(biāo)，并設(shè)計(jì)遺傳算法(GA)對(duì)模型求解，以期為地鐵應(yīng)急物資儲(chǔ)備點(diǎn)的選址決策提供借鑒。

2 優(yōu)化配置模型

2.1 問(wèn)題描述

要從若干備選地鐵應(yīng)急物資儲(chǔ)備點(diǎn)中選出合適的應(yīng)急儲(chǔ)備點(diǎn)，在滿足需求點(diǎn)物資需求量的前提下，將應(yīng)急物資快速準(zhǔn)時(shí)地運(yùn)到需求點(diǎn)。應(yīng)急儲(chǔ)備點(diǎn)的設(shè)置是不確定的，而需求點(diǎn)救援帶有較高的時(shí)間限制。地鐵應(yīng)急物資儲(chǔ)備點(diǎn)的選址受許多因素影響，如時(shí)間、成本、物資需求、速度、損毀情況等，考慮到地鐵應(yīng)急需求點(diǎn)對(duì)物資需求的緊迫性，故將時(shí)間作為第一個(gè)要考慮約束條件；由于地鐵前期建設(shè)費(fèi)用較高，短期內(nèi)籌集到的資金有限，合理利用資金至關(guān)重要，故將成本作為第二個(gè)要考慮的約束條件。

2.2 模型假設(shè)

1) 有潛在的若干個(gè)應(yīng)急物資儲(chǔ)備候選點(diǎn)，容量有限，從中選取部分應(yīng)急物資儲(chǔ)備點(diǎn)發(fā)貨，要求每個(gè)應(yīng)急儲(chǔ)備點(diǎn)供應(yīng)量超過(guò)一個(gè)需求點(diǎn)的貨物；

2) 由于突發(fā)事件發(fā)生時(shí)道路情況不確定，所以車輛運(yùn)輸時(shí)間是隨機(jī)變量，服從正態(tài)分布；

3) 每輛車從應(yīng)急儲(chǔ)備點(diǎn)出發(fā)，在運(yùn)送完應(yīng)急物資后，應(yīng)回到該應(yīng)急儲(chǔ)備點(diǎn)；

4) 一個(gè)需求點(diǎn)僅由一個(gè)應(yīng)急儲(chǔ)備點(diǎn)供應(yīng)；

5) 每個(gè)需求站都會(huì)被覆蓋，且只能覆蓋一次；

6) 建設(shè)空間能夠滿足建設(shè)需求。

2.3 模型參數(shù)

模型中的參數(shù)定義如下：P1、P2表示優(yōu)先因子，表示各個(gè)目標(biāo)的相對(duì)重要性，滿足P1≥P2；di-和di+（i=1，2）表示目標(biāo)偏離目標(biāo)值的正偏差和負(fù)偏差；表示需求站集合；表示應(yīng)急物資儲(chǔ)備候選點(diǎn)集合表示應(yīng)急物流網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合；C表示單位距離車輛行駛成本；Cj表示應(yīng)急儲(chǔ)備點(diǎn)j的固定建設(shè)費(fèi)用；dij表示節(jié)點(diǎn)i到j(luò)的距離；qj表示應(yīng)急儲(chǔ)備點(diǎn)j的庫(kù)存容量；εi表示需求點(diǎn)i的隨機(jī)需求；tij表示配送車輛從i到j(luò)的行駛時(shí)間；α表示目標(biāo)約束的置信水平；Xj表示{0，1}，如果應(yīng)急儲(chǔ)備點(diǎn)建立在位置j則為1，否則為0；Yj表示{0，1}，如果需求點(diǎn)j由車輛配送則為1，否則為0；Zij表示{0，1}，如果車輛是從應(yīng)急儲(chǔ)備點(diǎn)j到需求點(diǎn)i則為1，否則為0。

2.4 構(gòu)建模型

機(jī)會(huì)目標(biāo)規(guī)劃理論的主要思想是：在不確定環(huán)境下，通過(guò)極大化事件成立的機(jī)會(huì)，從而給出最優(yōu)決策[11]。機(jī)會(huì)目標(biāo)規(guī)劃模型允許在優(yōu)化過(guò)程中決策不滿足約束條件，但必須保證約束條件成立的概率滿足置信水平要求?；谏鲜黾僭O(shè)條件，構(gòu)建不確定條件下的地鐵應(yīng)急物資儲(chǔ)備點(diǎn)選址數(shù)學(xué)模型。

目標(biāo)函數(shù)如下：

約束條件如下：

2.5 模型求解

本研究所建立的不確定條件下的地鐵應(yīng)急儲(chǔ)備點(diǎn)選址模型為雙約束條件選址決策模型，遺傳算法可以將問(wèn)題參數(shù)編碼成染色體進(jìn)行優(yōu)化，不用針對(duì)參數(shù)本身，從而不受函數(shù)約束條件的限制，這樣可大大減少陷入局部最優(yōu)的可能性。具體求解步驟如下：

1) 步驟1，編碼及種群初始化。染色體將需求點(diǎn)以及應(yīng)急物資儲(chǔ)備候選點(diǎn)進(jìn)行編碼，采用3層編碼的方式，將編碼序列分為3個(gè)編碼段。第一段表示應(yīng)急物資儲(chǔ)備候選點(diǎn)編號(hào)，第二段表示需求點(diǎn)編號(hào)，第三段為應(yīng)急物資儲(chǔ)備候選點(diǎn)到需求點(diǎn)的配送路徑。

舉例說(shuō)明，種群個(gè)體編碼序列為1 2 4 | 1 1 2 2 4 2 1 4 |2 3 1 5 6 4 8 7，則第一段1 2 4表示應(yīng)急物資儲(chǔ)備候選點(diǎn)編號(hào)為1 2 4的3個(gè)點(diǎn)被選中。第二段1 1 2 2 4 2 1 4表示需求點(diǎn)1被應(yīng)急儲(chǔ)備點(diǎn)1負(fù)責(zé)配送，需求2被應(yīng)急儲(chǔ)備點(diǎn)1負(fù)責(zé)配送，需求3被應(yīng)急儲(chǔ)備點(diǎn)2負(fù)責(zé)配送，依次類推。第三段表示需求點(diǎn)被配送的順序?yàn)? 3 1 5 6 4 8 7，同一個(gè)中心負(fù)責(zé)的需求點(diǎn)按次序列從左至右的順序配送。采用隨機(jī)生成的方式產(chǎn)生初始種群。

2) 步驟2，適應(yīng)度函數(shù)。本研究所求解的目標(biāo)函數(shù)為最小值，所以適應(yīng)度函數(shù)應(yīng)最大化。函數(shù)值越小的個(gè)體，適應(yīng)度越大，個(gè)體越優(yōu)。

3) 步驟3，選擇操作。采用輪盤(pán)賭的方式，選擇優(yōu)秀的個(gè)體保留至下一代。具體操作如下：

① 計(jì)算出群體中每個(gè)個(gè)體的適應(yīng)度f(wàn)(i=1，2，…，m)，m為群體大小；

④ 從區(qū)間[0，1]隨機(jī)產(chǎn)生一個(gè)均勻分布數(shù)r，若r

⑤ 最后重復(fù)步驟4)共m次。

4) 步驟4，交叉操作。將染色體分為三部分進(jìn)行交叉。

① 假設(shè)交叉點(diǎn)為第二個(gè)隨機(jī)產(chǎn)生的基因位，p1=[1 2 |4]，p2=[1 3|4]，交叉后得到 1p′=[1 3|4]，p2′=[1 2|4]，如果存在重復(fù)則去掉，然后隨機(jī)補(bǔ)充，使得編碼序列滿足要求。

② 假設(shè)交叉點(diǎn)為第5個(gè)隨機(jī)產(chǎn)生的基因位，p1=[1 1 2 2 4|2 1 4]，p2=[1 4 1 2 4|2 1 2]，交叉后得到 1p′=[1 4 1 2 4|2 1 4]，p2′=[1 1 2 2 4|2 1 2]。

③ 隨機(jī)產(chǎn)生兩個(gè)不相等的交叉點(diǎn)，并將兩交叉點(diǎn)之間的基因進(jìn)行互換，從而產(chǎn)生新的序列，然后將新序列中多余的基因去掉，缺失的基因補(bǔ)充完整，便可形成兩個(gè)符合條件的新個(gè)體。

6) 步驟6，結(jié)果輸出。采用遺傳算法常用的終止判據(jù)，即當(dāng)?shù)螖?shù)到達(dá)人為規(guī)定的最大迭代次數(shù)時(shí)終止運(yùn)算。

遺傳算法流程如圖1所示。

圖1 遺傳算法流程Figure 1 Flow chart of genetic algorithm

3 實(shí)際案例分析

地鐵應(yīng)急物資儲(chǔ)備點(diǎn)的選址范圍可在地鐵車站或附近區(qū)域內(nèi)選擇?？紤]到昆明地鐵線路的實(shí)際管理情況和快速救援等要求，將選址范圍確定為同屬于昆明地鐵運(yùn)營(yíng)有限公司的1、2號(hào)線首期工程、3號(hào)線和6號(hào)線一期工程上的53個(gè)地鐵車站。

在選擇應(yīng)急物資配送候選點(diǎn)時(shí)，主要考慮以下約束條件：

1) 選擇換乘站。換乘站不僅承擔(dān)一般車站乘客的進(jìn)出站和上下車功能，還要具備乘客的中轉(zhuǎn)換乘等功能，因此可實(shí)現(xiàn)3線換乘的東風(fēng)廣場(chǎng)站應(yīng)給予考慮。

2) 對(duì)于毗鄰汽車站、鐵路車站等大型客流集散點(diǎn)的地鐵站點(diǎn)，客流多且復(fù)雜，是應(yīng)急搶修點(diǎn)的重點(diǎn)區(qū)域，應(yīng)當(dāng)予以考慮[12]，如昆明地鐵1號(hào)線的昆明火車站、南部汽車站等。

3) 線路車輛段綜合維修基地物資配備比較齊全，因此也應(yīng)考慮將其當(dāng)作一個(gè)應(yīng)急物資儲(chǔ)備候選點(diǎn)。

基于上述約束條件，初步確定了16個(gè)應(yīng)急物資儲(chǔ)備候選點(diǎn)。

3.1 基礎(chǔ)數(shù)據(jù)情況

根據(jù)目前昆明地鐵的應(yīng)急物資安全庫(kù)存現(xiàn)狀以及應(yīng)急響應(yīng)的要求，結(jié)合綜合代價(jià)值最小的原則，擬建立10個(gè)應(yīng)急物資儲(chǔ)備點(diǎn)，使其覆蓋現(xiàn)有53個(gè)已運(yùn)營(yíng)的車站，如圖2所示。

圖2 地鐵線網(wǎng)及站點(diǎn)情況Figure 2 Metro network and site information

本案例中的53個(gè)車站已經(jīng)全部投入載客運(yùn)營(yíng)。這些車站的建設(shè)時(shí)序不同，初期的拆遷成本和建設(shè)成本各不相同，而設(shè)置應(yīng)急儲(chǔ)備點(diǎn)主要考慮充分利用現(xiàn)有車站的剩余空間，因此計(jì)算中僅考慮重新裝修成本，不考慮拆遷成本以及建設(shè)成本。為了計(jì)算的簡(jiǎn)化，將每個(gè)固定搶修點(diǎn)的實(shí)施建設(shè)成本簡(jiǎn)化為5.0萬(wàn)～6.0萬(wàn)元/個(gè)，可供使用的面積為30～50 m2。每個(gè)應(yīng)急物資儲(chǔ)備候選點(diǎn)的固定建設(shè)成本Cj={5.0，5.5，6.0}萬(wàn)元，應(yīng)急物資儲(chǔ)備候選站容量qj={350，400，450}件，車輛單位運(yùn)輸成本為7元/km，置信目標(biāo)α=95%，應(yīng)急候選點(diǎn)的坐標(biāo)和建設(shè)成本信息如表1所示，需求點(diǎn)的坐標(biāo)和需求量信息如表2所示，其中各車站的救援時(shí)間窗為[0，15]min，各個(gè)站點(diǎn)之間的運(yùn)輸時(shí)間是在不同時(shí)間段內(nèi)多次測(cè)試得到的。

表1 應(yīng)急物資儲(chǔ)備候選點(diǎn)信息Table 1 Candidate point information for emergency supplies

表2 需求點(diǎn)信息Table 2 Information about demand point

3.2 選址-路徑優(yōu)化

使用Matlab軟件編程，對(duì)該模型進(jìn)行求解，遺傳算法中交叉概率的選擇范圍為0.5～1，變異概率的選擇范圍為0～0.2，初始染色體的數(shù)目無(wú)限制。本研究設(shè)置染色體數(shù)目為100，交叉概率為0.85，變異概率為0.15，對(duì)算例進(jìn)行計(jì)算30次，得到的結(jié)果比較穩(wěn)定?；贕A確定的應(yīng)急儲(chǔ)備點(diǎn)的最優(yōu)選址位置和路徑分配如表3所示，算法經(jīng)過(guò)500次迭代，模型目標(biāo)收斂如圖3所示。

圖3 目標(biāo)收斂Figure 3 Target convergence graph

表3 應(yīng)急儲(chǔ)備點(diǎn)選址結(jié)果Table 3 Site selection results of emergency reserve points

由上述計(jì)算結(jié)果得出，昆明地鐵需建立的10個(gè)應(yīng)急物資儲(chǔ)備點(diǎn)的站號(hào)依次為：1、6、9、14、23、24、28、32、41、48，滿足需求站點(diǎn)均被選出的應(yīng)急物資儲(chǔ)備站點(diǎn)覆蓋的要求。分析表3中的數(shù)據(jù)可知：以成本和時(shí)間作為約束條件，各應(yīng)急儲(chǔ)備點(diǎn)的容量也會(huì)存在差異，應(yīng)急儲(chǔ)備點(diǎn)對(duì)應(yīng)的需求點(diǎn)是不均勻的，配送路線也就不同。依據(jù)時(shí)序性原則，結(jié)合潛在昆明地鐵應(yīng)急儲(chǔ)備點(diǎn)在路上的實(shí)際位置，對(duì)實(shí)際配送路線進(jìn)行微調(diào)。換言之，各個(gè)應(yīng)急儲(chǔ)備點(diǎn)在不確定條件下的工作量不同。例如，應(yīng)急儲(chǔ)備點(diǎn)41覆蓋了2條線路10個(gè)站，而應(yīng)急儲(chǔ)備點(diǎn)1覆蓋了同一條線路的2個(gè)站點(diǎn)。

3.3 現(xiàn)狀結(jié)果討論

由于種種原因，我國(guó)地鐵既有線大多在規(guī)劃設(shè)計(jì)階段沒(méi)有考慮應(yīng)急儲(chǔ)備點(diǎn)的選址規(guī)劃。隨著線路的增加，車站的性質(zhì)會(huì)有所改變，中間站變成換乘站；進(jìn)入到網(wǎng)絡(luò)化階段，應(yīng)急搶險(xiǎn)的要求會(huì)變高。在此情況下，其應(yīng)急設(shè)施的設(shè)置也需要進(jìn)行相應(yīng)改變，故可考慮以新建應(yīng)急設(shè)施的建設(shè)成本與已設(shè)應(yīng)急設(shè)施的改造成本之和最小為目標(biāo)，以規(guī)定的救援時(shí)間最小、已有應(yīng)急設(shè)施和覆蓋所有的需求站點(diǎn)等為約束條件，建立動(dòng)態(tài)發(fā)展的選址模型。對(duì)于既有線新增應(yīng)急物資儲(chǔ)備點(diǎn)共有3種方法：一是根據(jù)應(yīng)急物資的類型不同，改造車站預(yù)留空間，達(dá)到儲(chǔ)備部分物資的目的；二是對(duì)于大中型應(yīng)急物資，可以依靠設(shè)備供應(yīng)商的場(chǎng)地，解決大型應(yīng)急設(shè)備的供應(yīng)問(wèn)題；三是最理想的狀態(tài)，應(yīng)該是在線路建設(shè)階段甚至是在規(guī)劃設(shè)計(jì)階段，就預(yù)留應(yīng)急物資儲(chǔ)備點(diǎn)，待到時(shí)機(jī)成熟再行建設(shè)。

4 結(jié)語(yǔ)

本研究針對(duì)地鐵應(yīng)急儲(chǔ)備點(diǎn)選址優(yōu)化存在的不確定性，在應(yīng)急救援存在嚴(yán)格的時(shí)間限制下，以應(yīng)急成本和救援時(shí)間作為約束條件，基于機(jī)會(huì)目標(biāo)規(guī)劃方法，建立地鐵應(yīng)急物資儲(chǔ)備點(diǎn)選址模型，通過(guò)設(shè)計(jì)遺傳算法對(duì)模型進(jìn)行求解，并以昆明市地鐵部分線路為例，對(duì)模型和算法進(jìn)行了驗(yàn)證。結(jié)果表明，該模型能夠解決昆明地鐵決策和物資路徑分配需求的問(wèn)題，能夠?yàn)槌鞘熊壍澜煌☉?yīng)急物資儲(chǔ)備點(diǎn)選址研究提供新的依據(jù)和思路，同時(shí)也證明了遺傳算法能夠有效地解決函數(shù)約束條件限制下的選址問(wèn)題，避免了僅針對(duì)參數(shù)本身減少陷入局部最優(yōu)的可能性。未來(lái)的改善研究可以考慮多層級(jí)地鐵應(yīng)急物資配送點(diǎn)選址模型，以解決多重不確定條件下的應(yīng)急配送點(diǎn)選址問(wèn)題。