超立方體排隊均衡的衛(wèi)星消防站選址調(diào)度優(yōu)化

劉 晗，王 健，安 實，崔 娜

(哈爾濱工業(yè)大學(xué)交通科學(xué)與工程學(xué)院交通安全特種材料與智能化控制技術(shù)交通行業(yè)重點實驗室，哈爾濱150090)

0 引言

城市消防站的選址問題是關(guān)系城市安全的重要戰(zhàn)略問題.消防站選址是否科學(xué)，直接影響到消防車輛的救援效率和城市需求點的覆蓋水平[1].《城市消防站建設(shè)標(biāo)準(zhǔn)(建標(biāo)152-2011)》規(guī)定，消防站的布局一般應(yīng)以接到出動指令后5 min內(nèi)消防隊可以到達轄區(qū)邊緣為原則確定.然而，隨著城市經(jīng)濟的快速發(fā)展，城市建筑分布與城市交通狀況發(fā)生顯著變化，一些城市的現(xiàn)有消防站已不能滿足5 min內(nèi)到達火災(zāi)點的要求.尤其是在一些老舊城區(qū)，一方面，人員密集，道路擁堵，如果發(fā)生火災(zāi)，外部消防車輛行駛時間可能由于道路擁堵而延長；另一方面，老舊城區(qū)一般建筑密集，可用于建設(shè)標(biāo)準(zhǔn)消防站的大型空地數(shù)量有限，且土地昂貴、民居拆遷難度很大，政府財政預(yù)算有限，建造標(biāo)準(zhǔn)消防站規(guī)模大，投資大，周期長.城市原消防基礎(chǔ)薄弱的現(xiàn)狀與當(dāng)前城市發(fā)展速度不相適應(yīng)，嚴(yán)重制約了城市消防救援服務(wù)的效率，加劇了火災(zāi)造成的生命財產(chǎn)損失.

面對以上難題，國內(nèi)一些城市已開始借鑒國外發(fā)達國家消防站站小、點密的經(jīng)驗，以建設(shè)“衛(wèi)星消防站”的模式來解決傳統(tǒng)消防站建設(shè)的諸多難題.衛(wèi)星消防站，即以現(xiàn)有的標(biāo)準(zhǔn)消防站(主站)為依托，并以其為中心，向周邊輻射建立的小型消防站(副站).相對于標(biāo)準(zhǔn)消防站，小型消防站占地面積小，建設(shè)成本低，能夠布置于人口密集的老舊城區(qū)，為標(biāo)準(zhǔn)消防站滅火力量提供援助.但因其占地面積較小，消防車輛較少，沒有能力撲救大型火災(zāi)，只能撲救小型火災(zāi).當(dāng)小型消防站升級為某一標(biāo)準(zhǔn)消防站的衛(wèi)星副站后，可撲救中型火災(zāi).衛(wèi)星消防站建設(shè)，是國內(nèi)消防部門專業(yè)人員根據(jù)中國城市消防工作的實際情況，并借鑒國外成功經(jīng)驗確定的發(fā)展模式[2].尤其對于大中型城市，建設(shè)衛(wèi)星消防站成為有效化解制約高效實施滅火救援瓶頸性問題的有效途徑.

國內(nèi)外學(xué)者在應(yīng)急設(shè)施選址領(lǐng)域，取得了大量成果.他們主要以位置集合覆蓋模型和最大覆蓋模型為基礎(chǔ)，針對不同背景問題提出了各種覆蓋模型.在合作設(shè)施選址方面，Gendreau提出了雙層標(biāo)準(zhǔn)覆蓋模型[3].Doerner等在此基礎(chǔ)上加入懲罰因子，使設(shè)施工作量更加均衡[4].Berman等提出了合作條件下的位置集合覆蓋模型和最大覆蓋模型[5].但以上模型均為無容量設(shè)施選址模型，沒有對設(shè)施內(nèi)可調(diào)派的車輛數(shù)量進行優(yōu)化.Drezner提出了設(shè)施點對需求點的隨機漸進覆蓋模型[6].但模型并未考慮合作服務(wù)條件下的漸進覆蓋情況.方磊等研究了應(yīng)急限制期下城市應(yīng)急系統(tǒng)優(yōu)化選址決策問題[7].Leknes等針對不同應(yīng)急需求和多重車輛調(diào)派特點，提出了應(yīng)急車輛選址戰(zhàn)略優(yōu)化模型[8].Van Barneveld等將線性瓶頸分配問題引入應(yīng)急選址模型[9].Jagtenberg等提出了應(yīng)急車輛在線調(diào)度算法[10].王健等提出了應(yīng)急設(shè)施合作漸進覆蓋模型[11].劉晗等提出了基于合作機制的超立方體排隊論優(yōu)化模型[12]和基于超立方體排隊均衡，服務(wù)者合作機制與不可靠因素的應(yīng)急車輛出動模型[13].Ansari等應(yīng)用超立方體排隊論模型構(gòu)建了多級響應(yīng)模型[14].

雖然已有文獻針對應(yīng)急領(lǐng)域覆蓋問題提出了各種覆蓋模型，但目前尚未對適應(yīng)中國城市情況的衛(wèi)星消防站選址覆蓋問題進行深入研究.本文研究的衛(wèi)星消防站選址覆蓋問題，考慮了超立方體排隊均衡和主消防站對附屬衛(wèi)星消防站的數(shù)量約束和距離約束，并根據(jù)城市大、中、小型火災(zāi)隱患點的分布情況對不同成本與功能的可用消防資源進行優(yōu)化配置，確定哪些小型消防站應(yīng)升級為某一標(biāo)準(zhǔn)消防站的衛(wèi)星消防站，并對站內(nèi)消防車輛進行合理調(diào)派，用最低的財政預(yù)算提供最優(yōu)消防服務(wù)水平.針對現(xiàn)有研究不足，本文通過構(gòu)建衛(wèi)星合作關(guān)系條件下有容量消防站選址調(diào)度優(yōu)化模型，解決了以下問題：①考慮了基于排隊論的超立方體均衡，精細(xì)化特定覆蓋水平下車輛調(diào)派方案；②構(gòu)建不同等級設(shè)施點之間的協(xié)作水平漸進衰減函數(shù)；③構(gòu)建了存在衛(wèi)星協(xié)作關(guān)系的需求點服務(wù)水平目標(biāo)函數(shù).從工程實踐角度講，科學(xué)構(gòu)建衛(wèi)星消防站模式下選址覆蓋模型能夠為大中型城市政府消防規(guī)劃政策和消防資源優(yōu)化配置提供更為有效的指導(dǎo).需要說明的是，此模型在其他領(lǐng)域(如醫(yī)療救護點選址，治安派出所選址等)的相似背景下也具有適用性.

本文提出了衛(wèi)星消防站模式下的選址覆蓋模型，其目標(biāo)是最大化城市消防服務(wù)水平.由于此優(yōu)化模型為非線性規(guī)劃問題，很難在可接受時間內(nèi)得到大規(guī)模問題的最優(yōu)解，因此用GAMS對模型進行編程，采用局部搜索算法并利用線性求解器ILOG CPLEX和非線性求解器MINOS對模型進行求解，在較短時間內(nèi)得到了問題的滿意解.隨后，對哈爾濱市主城區(qū)衛(wèi)星消防站布局進行了實例優(yōu)化，并分析了不同財政預(yù)算下消防車數(shù)量與消防服務(wù)水平的變化趨勢.最后對衛(wèi)星消防站關(guān)聯(lián)成本進行了敏感度分析，為消防預(yù)算投入提供了更為準(zhǔn)確的參考.

1 基于排隊均衡的衛(wèi)星消防站選址調(diào)度模型

1.1 問題描述

假設(shè)某區(qū)域總共有I個火災(zāi)隱患點，其中I1、I2、I3分別為大、中、小型火災(zāi)隱患點集合.θi,1為二元變量，當(dāng)且僅當(dāng)i∈I1時，θi,1=1；否則，θi,1=0.θi,2和θi,3的物理意義與θi,1相似.di為需求點i的權(quán)重；r表示覆蓋條件下需求點與設(shè)施點的距離上限；Wi表示能夠覆蓋需求點i的設(shè)施點集合，即，tij表示需求點i到設(shè)施點j的最短行駛距離.隨著行駛距離的增加，火災(zāi)產(chǎn)生的損失逐漸增大，消防服務(wù)水平漸進損失.因此，模型考慮了漸進覆蓋特點，加入了服務(wù)水平漸進損失函數(shù)(Citij)，使覆蓋模型水平更加貼近實際，(Citij)為tij的遞減函數(shù).

pj為消防站j的容量，實際布設(shè)的消防車數(shù)量分別為xj，實際派遣至需求點i的消防車數(shù)量為yij，xj和yij均為整數(shù)變量；標(biāo)準(zhǔn)消防站和小型消防站的候選點集合分別為jm∈Jm和jv∈Jv；sjmjv為二元變量，表示小型消防站jv是否可以升級為標(biāo)準(zhǔn)消防站jm的衛(wèi)星消防副站，如果jv和jm存在衛(wèi)星關(guān)系，則sjmjv=1，否則；zj為二元變量，表示是否在相應(yīng)候選點建設(shè)消防站.對于任意標(biāo)準(zhǔn)消防站jm∈Jm，有能力撲救各個級別火災(zāi)(i∈I)；對于任意小型消防站jv∈Jv，有能力撲救任意小型火災(zāi)(i∈I3)，當(dāng)且僅當(dāng)其升級為某一標(biāo)準(zhǔn)消防站j∈J的衛(wèi)星消防站時(即sjmjv=1時)可撲救中型火災(zāi)(i∈I2)，但沒有能力撲救大型火災(zāi)(i∈I1).

為了精細(xì)化特定覆蓋水平下車輛調(diào)派方案，本文采用超立方體排隊論(Hypercube Queuing Theory)模型[15].超立方體排隊論基于空間排隊論與馬爾科夫近似過程，是描述應(yīng)急服務(wù)系統(tǒng)車輛調(diào)派狀態(tài)的有效方法.模型中，pt為超立方體總數(shù)量；k表示超立方體順序；為第k個超立方體的忙碌率，其中λ為需求發(fā)生率，服從泊松分布，μk為第k個超立方體的服務(wù)率，服務(wù)時間服從指數(shù)分布；α為需求點的被覆蓋可靠度；Q為超立方體修正函數(shù)[16].

設(shè)r'為衛(wèi)星關(guān)聯(lián)條件下消防站主站與副站的距離上限；Ujv表示能夠關(guān)聯(lián)主站jm的副站選址點集合，即類似的，Ujm表示能夠關(guān)聯(lián)副站jv的主站選址點集合，即，其中tjmjv表示衛(wèi)星消防站副站至主站的最短行駛距離.隨著主站與副站距離的增大，主站對副站保障難度增加，在通信技術(shù)、物資供給及人力資源等方面的投入逐漸增加，使協(xié)作成本相應(yīng)增大.因此，模型考慮了漸進關(guān)聯(lián)特點，加入了主站與副站關(guān)聯(lián)成本隨距離變大的遞增函數(shù)假設(shè)Ms為衛(wèi)星消防站單位關(guān)聯(lián)成本，則漸進關(guān)聯(lián)成本為為消防站j的建設(shè)成本，M為用于消防站建設(shè)的總預(yù)算.

根據(jù)文獻[11]，基于漸進覆蓋因素和消防車輛數(shù)量因素的i∈I消防服務(wù)水平為，其中，ai為漸進覆蓋條件下的實際到場車輛；bi為滅火預(yù)案規(guī)定的需求點所需消防車輛數(shù)量參數(shù).

1.2 模型構(gòu)建

綜上所述，本文的數(shù)學(xué)模型為

式(1)為模型目標(biāo)函數(shù)，將城市消防服務(wù)水平最大化.式(2)～式(13)為約束條件，式(2)確保在超立方體排隊論條件下每一個需求點的被覆蓋可靠度為α；式(3)表示不同等級需求點的實際到場的消防車輛數(shù)量；式(4)表示實際到場消防車輛數(shù)量不大于需求點需要的消防車輛數(shù)量；式(5)表示從候選點調(diào)派至需求點的消防車輛數(shù)量不大于布置在此候選點的消防車輛數(shù)量；式(6)表示如果在候選點布置消防車，則須在此候選點建設(shè)消防站；式(7)表示消防站建設(shè)成本與關(guān)聯(lián)成本之和控制在一定財政預(yù)算范圍內(nèi)；式(8)表示，對于任何一個小型消防站，最多只能有一個標(biāo)準(zhǔn)消防站作為其主站；式(9)表示與主站建立衛(wèi)星關(guān)系的副站數(shù)量不大于超立方體數(shù)量；式(10)表示只有在相應(yīng)的候選點建設(shè)了標(biāo)準(zhǔn)消防站和小型消防站，兩者之間才可能存在衛(wèi)星關(guān)系；式(11)～式(13)規(guī)定了各決策變量的類型.

1.3 模型求解

該問題為非線性混合整數(shù)規(guī)劃問題，精確算法很難在滿意時間內(nèi)得到問題最優(yōu)解.因此，用GAMS對模型進行編程，在處理器為Intel(R)Core(TM)i7-4590 CPU@3.30GHz計算機上采用局部搜索算法，利用線性求解器ILOG CPLEX和非線性求解器MINOS對模型進行求解，最大運行時間為332 s.

2 算例分析

2.1 算例數(shù)據(jù)

將模型應(yīng)用于黑龍江省哈爾濱市主城區(qū)消防服務(wù)系統(tǒng).根據(jù)滅火救援預(yù)案，將市區(qū)分為3 150個不同等級子區(qū)域，其中小、中、大型火災(zāi)隱患點數(shù)量分別為1 830、1 210、110.將需求點被覆蓋可靠度設(shè)為95%.市區(qū)內(nèi)現(xiàn)有標(biāo)準(zhǔn)消防站數(shù)量為11個.國土資源部門在人口密集區(qū)域推薦了20個小型消防站候選點.

根據(jù)消防部門滅火預(yù)案，對于3類不同需求點，bi取值分別為2，4，6.根據(jù)消防后勤部門統(tǒng)計數(shù)據(jù)，標(biāo)準(zhǔn)消防站平均建設(shè)成本約為5.0×107元，小型消防站平均建設(shè)成本估算為1.5×106元.衛(wèi)星消防站的關(guān)聯(lián)成本Ms估算為3×105元.兩類消防站的最大可容納車輛數(shù)目分別為6輛和3輛.由Dijkstra最短路算法計算主副衛(wèi)星消防站之間的最短行駛時間，得出tjmjv矩陣.由文獻[17]漸進覆蓋公式參數(shù)計算矩陣.

由1.3節(jié)所述模型求解算法對衛(wèi)星消防站模式下選址覆蓋模型進行求解.設(shè)現(xiàn)有的哈爾濱市主城區(qū)傳統(tǒng)消防站模式為模式A；優(yōu)化后的哈爾濱市主城區(qū)衛(wèi)星消防站模式為模式B.圖1顯示了模式A與模式B下，消防車數(shù)量與最佳服務(wù)水平隨財政預(yù)算增加的變化.

消防車數(shù)量變化趨勢：在財政預(yù)算由0元增至4億元的過程中，兩類模式下消防車數(shù)量均得到穩(wěn)步增長，在財政預(yù)算由4億元增至5億元的過程中，消防車數(shù)量實現(xiàn)最大幅度增長.在財政預(yù)算達到6億元以后，模式A下消防車數(shù)量趨于飽和，最終保持在66輛；模式B下消防車數(shù)量依然保持快速增長趨勢，由68輛增至85輛.

2.2 優(yōu)化結(jié)果分析

消防服務(wù)水平變化趨勢：隨著財政預(yù)算增加，兩類模式下的消防服務(wù)水平變化均在初始階段出現(xiàn)急速增長，隨后增長趨勢變緩.具體來看，在財政預(yù)算達到6億元以后，模式A下消防服務(wù)水平趨于飽和，達到88.8%；模式B下消防車數(shù)量依然保持小幅增長，由92.42%增至94.04%.

圖2顯示了不同財政預(yù)算下衛(wèi)星消防站模式的標(biāo)準(zhǔn)消防站、小型消防站分布圖，每一線段兩端的圓形圖標(biāo)和三角形圖標(biāo)分別表示存在衛(wèi)星關(guān)聯(lián)的主站和副站.

優(yōu)化結(jié)果表明，在衛(wèi)星消防站關(guān)聯(lián)成本Ms為3×105元時，模式B比模式A能夠布置更多數(shù)量的消防車，且能提供更高水平的服務(wù).因此，在預(yù)算允許的條件下，哈爾濱市消防部門應(yīng)采用模式B設(shè)置一定數(shù)量的小型消防站，并合理選擇部分小型消防站升級為衛(wèi)星副站，以達到更高的消防服務(wù)水平.

2.3 敏感度分析

考慮到衛(wèi)星消防站關(guān)聯(lián)成本Ms可能對衛(wèi)星消防站服務(wù)優(yōu)化水平產(chǎn)生影響，對Ms進行敏感度分析.圖3表示消防服務(wù)水平隨關(guān)聯(lián)成本和預(yù)算變化趨勢的三維圖.

圖1 模式A與模式B下消防車數(shù)量與最佳服務(wù)水平隨財政預(yù)算增加變化趨勢Fig.1 The trend of fire vehicle quantity and fire service level with different budgets under mode A and B

圖2 衛(wèi)星消防站模式下標(biāo)準(zhǔn)消防站和小型消防站分布圖Fig.2 Layout of standard fire station and small fire station under satellite fire station mode

由圖3可知，在一定預(yù)算條件下，消防服務(wù)水平隨衛(wèi)星消防站關(guān)聯(lián)成本的增長而下降.這是因為，關(guān)聯(lián)成本的增長使預(yù)算范圍內(nèi)可建消防站數(shù)量降低，導(dǎo)致覆蓋范圍下降；或小型消防站升級為衛(wèi)星副站的成本增加而導(dǎo)致中級火災(zāi)隱患點的被覆蓋比例減少，影響了總體服務(wù)水平.因此，消防部門應(yīng)合理控制衛(wèi)星消防站關(guān)聯(lián)成本，在預(yù)算范圍內(nèi)合理布局各類消防站的選址，達到最優(yōu)消防服務(wù)水平.

圖3 衛(wèi)星消防站關(guān)聯(lián)成本對衛(wèi)星消防站服務(wù)水平的敏感度Fig.3 Sensitivity to satellite fire station related cost with respect to the fire service level

3 結(jié)論

本文通過構(gòu)建衛(wèi)星消防站關(guān)聯(lián)機制，提出了超立方體排隊論條件下不同等級災(zāi)害的車輛選址與調(diào)派漸進覆蓋優(yōu)化模型.應(yīng)用GMAS和局部搜索算法求解此混合整數(shù)規(guī)劃模型，并對黑龍江省哈爾濱市主城區(qū)衛(wèi)星消防站布局進行了實例優(yōu)化.通過分析衛(wèi)星消防站關(guān)聯(lián)成本對消防服務(wù)水平的影響，為哈爾濱市消防規(guī)劃部門的預(yù)算投入提供了更為準(zhǔn)確的參考.

下一步研究可考慮應(yīng)急車輛不可靠性或超立方體排隊均衡特點，構(gòu)建衛(wèi)星消防站的動態(tài)選址覆蓋模型，使優(yōu)化模型更加準(zhǔn)確.

參考文獻:

[1]LI X P,ZHAO Z X,ZHU X Y,et al.Covering models and optimization techniques for emergency response facility location and planning:A review[J].Math.Meth.Res.,2011(74):281-310.

[2]央廣網(wǎng).全國城鄉(xiāng)消防規(guī)劃編修和小型消防站建設(shè)經(jīng)驗交流會召開[OL].(2017-08-10)[2017-11-11].http://news.cnr.cn/native/city/20170810/t20170810_523894922.shtml.[CNR.The conference of national urban and rural fire protection plan revision and small fire station construction experience washeld[OL].(2017-08-10)[2017-11-11].http://news.cnr.cn/native/city/20170810/t20170810_523894922.shtml.]

[3]GENDREAU M,LAPORTE G,SEMET F.Solving an ambulance location model by Tabu search[J].Location Science,1997(5):75-88.

[4]DOERNER K F,HARTL R F.Health care logistics,emergency preparedness,and disasterrelief:New challenges for routing problems with a focus on the austrian situation,In:The vehicle rounting problem:Lastest advances and new challenges[M].USA:Springer,2008.

[5]BERMAN O,DREZNER Z,KRASS D.Cooperative cover location problems:The planar case[J].IIE Trans.,2010(42):232-246.

[6]BERMAN O,KRASS D,DREZNER Z.The gradual coveringdecaylocation problem on anetwork[J].European Journal of Operational Research,2003(151):474-80.

[7]方磊,何建敏.城市應(yīng)急系統(tǒng)優(yōu)化選址決策模型和算法[J].管理科學(xué)學(xué)報,2005,8(1):12.[FANG L,HE J M.Urban emergency system location optimization model and algorithm[J].Management Science,2005,8(1):12.]

[8]LEKNES H,AARTUN E S,ANDERSSON H,et al.Strategic ambulance location for heterogeneous regions[J].European Journal of Operational Research,2017,260(1):122-133.

[9]VAN BARNEVELD T C,BHULAI S,VAN DER MEI R D.The effectofambulance relocations on the performance of ambulance service providers[J].European Journal of Operational Research,2016,252(1):257-269.

[10]JAGTENBERG C J,BERG P L,MEIR D.Benchmarking online dispatch algorithms for emergency medical services[J].European Journal of Operational Research,2017,258(2):715-725.

[11]WANG J,LIU H,AN S,et al.A new partial coverage locating model for cooperative fire services[J].Information Sciences,2016(373):527-538.

[12]LIU H,WANG J.Cooperative hypercube queuing model and its configuration optimization for emergency service system[C].Transportation Research Board 96th Annual Meeting,2017.

[13]LIU H,WANG J,OUYANG Y.Responder planning underhypercube queuing equilibrium,cooperation and disruptions[C].INFORMS Annual Meeting,2017.

[14]ANSARI S,YOON S,ALBERT L A.An approximate hypercube model for public service systems with colocated servers and multiple response[J].Transportation Research Part E:Logistics and Transportation Review,2017(103):143-157.

[15]LARSON R C.Hypercube queuing model for facility location and redistricting in urban emergency services[J].Computers and Operations Research,1974(1):67-95.

[16]LARSON R C.Approximating the performance of urban emergency service systems[J].Operations Research,1975,23(5):845-868.

[17]KARASAKAL O,KARASAKAL E K.A maximal covering location model in the presence of partial coverage[J].Comput.Oper.Res.,2004(31):1515-1526.