基于排隊模型的β可靠性最大覆蓋應(yīng)急服務(wù)車輛選址：模型與算法

喬聯(lián)寶，朱華桂

（南京大學(xué) 工程管理學(xué)院，南京 210093）

在現(xiàn)實生活中，應(yīng)急服務(wù)設(shè)施的選址具有廣泛的應(yīng)用，如警察巡邏車、消防站救護(hù)車輛以及醫(yī)院急救車輛的選址問題.早期的應(yīng)急服務(wù)設(shè)施主要應(yīng)用覆蓋模型來確定應(yīng)急服務(wù)設(shè)施點的位置，即只要在給定的時間（或者距離）范圍內(nèi)，服務(wù)點能夠?qū)π枨簏c提供服務(wù)即可.如Toregas等［1］較早對應(yīng)急服務(wù)設(shè)施的集合覆蓋問題進(jìn)行了研究，Current和Morton［2］考察了兩種類型警報器的集合覆蓋問題.集合覆蓋選址在應(yīng)用中存在一定的局限性，它所產(chǎn)生的設(shè)施點數(shù)量一般較多，往往超出了可能的預(yù)算約束.所以后來又出現(xiàn)了最大覆蓋模型，最大覆蓋并不要求覆蓋所有的需求點，而是要在給定的資源限制下覆蓋盡可能多的需求量，Church和ReVelle［3］較早地提出了最大覆蓋模型.

在某些情況下，需求點與其周圍最近的設(shè)施點之間的距離在給定的服務(wù)半徑內(nèi)，按照覆蓋模型的規(guī)定，該需求點應(yīng)該被設(shè)施點所覆蓋.但是，并沒有考慮這樣一種情形：當(dāng)需求點向其最近的服務(wù)設(shè)施點請求服務(wù)時，該服務(wù)單位恰好處于繁忙狀態(tài)，比如正在為其服務(wù)范圍內(nèi)的另一個客戶提供服務(wù).那么在這種情況下，新產(chǎn)生的需求要么進(jìn)行排隊等候，要么損失了，或者轉(zhuǎn)向其他的服務(wù)設(shè)施點等.在這種情況下，無論需求點進(jìn)行排隊等候還是損失了，它都不在一般覆蓋模型的考慮范圍之內(nèi).

鑒于服務(wù)器因處于繁忙狀態(tài)而不能夠?qū)ζ渌枨筇峁┓?wù)，Daskin［4］提出了最大期望覆蓋選址問題（Maximum Expected Covering Location Problem，MEXCLP），最大化能夠得到服務(wù)的需求量的期望值.ReVelle和Hogan［5，6］提出了有服務(wù)水平保證的最大覆蓋選址模型，要求被覆蓋的需求點能夠得到服務(wù)的概率不小于給定的值α.同確定性覆蓋模型假定所有被覆蓋的需求點都可以及時得到服務(wù)相比，概率覆蓋模型在假設(shè)條件上有很大的進(jìn)步.但是，以上等人所建立的概率覆蓋模型要求服務(wù)器的繁忙率必須事先已知，而且相互獨(dú)立，顯然這些假定仍然過于嚴(yán)格.

對于服務(wù)器經(jīng)常處于繁忙狀態(tài)的設(shè)施選址問題，使用排隊論模型來研究此類問題能夠更準(zhǔn)確地反應(yīng)現(xiàn)實系統(tǒng)的運(yùn)行情況.在模型假設(shè)條件上也不需要假定服務(wù)器是否繁忙是相互獨(dú)立的.Larson［7，8］提出了超立方排隊模型來直接計算車輛的繁忙比率，但是超立方排隊模型需要設(shè)施點的位置已知，并且該模型是非線性的，精確方法計算量也非常大，它常常同其他方法結(jié)合起來使用.后來一些文獻(xiàn)直接應(yīng)用排隊論模型來研究服務(wù)設(shè)施經(jīng)常處于繁忙狀態(tài)的覆蓋選址問題［9，10］，本文將從另一個角度建立有服務(wù)水平保證、基于排隊論的最大覆蓋選址模型.

1 相關(guān)文獻(xiàn)綜述

在設(shè)施選址模型中，Church和ReVelle［3］提出的最大覆蓋模型是其中的一個重要類型，它在實踐中已被成功的應(yīng)用，并被廣泛應(yīng)用到應(yīng)急服務(wù)設(shè)施的選址問題中.在基本的覆蓋模型基礎(chǔ)上，后來產(chǎn)生了各種不同的變化形式.早期Schilling等［11］按照集合覆蓋和最大覆蓋這兩種類型對覆蓋選址問題進(jìn)行了綜述；Farahani等［12］對Schilling等綜述以后的近20年間與覆蓋選址相關(guān)的文獻(xiàn)做了全面而廣泛的綜述.以上兩篇綜述性文章涵蓋了覆蓋選址問題的大部分方面，相關(guān)問題可以參考上述文獻(xiàn).

早期的選址文獻(xiàn)在模型參數(shù)方面都是確定性的.當(dāng)考慮不確定因素時，Snyder［13］研究了在不確定環(huán)境下的選址問題，包括不確定環(huán)境下的決策制定.Boffey等［14］對服務(wù)臺不可移動且有容量約束的排隊情形下的選址問題做了相關(guān)綜述，他們以確定性的p－Median問題為基本模型，通過對參數(shù)和約束的擴(kuò)展逐漸將其演變?yōu)槠渌谴_定類型的選址問題.

在最大覆蓋選址問題中最早引入不確定性因素的是Daskin［4］，同樣他也做了很多有助于簡化問題的一些假設(shè)，比如服務(wù)器的繁忙率事先可以確定，服務(wù)器的繁忙率不依賴于最終的位置和工作量等.后來，ReVelle和Hogan［6］提出了有可靠性水平保證的，最大化車輛可獲得性條件下的覆蓋選址問題，并分別使用系統(tǒng)層次和區(qū)域?qū)哟蔚能囕v繁忙率對實例城市進(jìn)行了研究.

考慮到系統(tǒng)可能存在的擁堵情形，直接運(yùn)用排隊模型來研究應(yīng)急車輛選址問題的有Marianov和ReVelle［9，10］，他們都通過運(yùn)用排隊論模型來進(jìn)一步放松“各個服務(wù)臺是否繁忙是相互獨(dú)立的”這一假設(shè)條件，最大化有可靠性水平保證的需求數(shù)量.

Berman和Drezner［15］考慮了需求和服務(wù)時間都是隨機(jī)的網(wǎng)絡(luò)選址問題，需求點和設(shè)施點只位于網(wǎng)絡(luò)的節(jié)點上，目標(biāo)函數(shù)是最小化服務(wù)器到達(dá)需求點的運(yùn)行時間和在服務(wù)器的平均等待時間之和，因此屬于有排隊系統(tǒng)的中值選址問題.Aboolian等［16］建立了與Berman和Drezner類似的排隊選址模型，同時他們允許在一個站點設(shè)立多個服務(wù)臺，并且目標(biāo)函數(shù)最小化最大運(yùn)行時間和等待時間之和，因此屬于中心排隊選址問題.Baron等［17］研究了需求隨機(jī)、有等待時間約束的更一般條件下的隨機(jī)選址問題，在他們的模型中，需求和服務(wù)過程都服從一般的分布，設(shè)施的潛在位置未知且有容量約束，同時對最大的到達(dá)時間和服務(wù)水平有一定要求，最后構(gòu)造了求解問題的分解算法.

求解基于概率模型的覆蓋選址問題所面臨的一個重要難點是服務(wù)器繁忙率的確定.為了保證達(dá)到事先給定的服務(wù)水平約束，必須要求服務(wù)器繁忙率已知，而各個服務(wù)器繁忙的具體情況又依賴于設(shè)施點所處的位置.所以，文獻(xiàn)要么假定所有服務(wù)器的繁忙率事先已知［4］，要么基于系統(tǒng)層次或區(qū)域?qū)哟螌Σ煌恢玫姆泵β蔬M(jìn)行估計［5，6，9，10］，也有的文獻(xiàn)通過迭代或其他改進(jìn)方法來近似估計服務(wù)器的繁忙率［18］等.Larson［7］從理論上描述了如何精確計算服務(wù)器繁忙率及服務(wù)系統(tǒng)其他重要參數(shù)的方法，由于該方法很難應(yīng)用于大規(guī)模問題，所以出現(xiàn)了Larson［8］的簡化版，簡化方法所求得的解同精確解的誤差隨著服務(wù)器的數(shù)目增加而減少，并不超過2%，但是該方法需要設(shè)施點位置已知.

基于上述原因，下面將建立有服務(wù)水平β保證、基于排隊模型的應(yīng)急服務(wù)車輛最大覆蓋選址模型.由于引入了排隊論模型，因此不用假定設(shè)施點的服務(wù)器繁忙與否是相互獨(dú)立的.在服務(wù)器繁忙率的選擇上，使用基于設(shè)施點區(qū)域水平的值.但是與以往文獻(xiàn)不同的是模型建立的角度，本文從覆蓋量的角度給出服務(wù)水平約束條件.模型M1的建立十分自然，由于是非線性規(guī)劃模型，它求解起來較為困難.模型M2是整數(shù)線性規(guī)劃問題，同M1相比較容易求解.但是對于求解大規(guī)模的問題，在時間上可能不可行.當(dāng)需求可以分散服務(wù)，并且設(shè)施點允許安排的服務(wù)器數(shù)量無上限時，根據(jù)排隊論的性質(zhì)設(shè)計了相應(yīng)的快速求解算法.在以下的章節(jié)中，將不再區(qū)分服務(wù)器和應(yīng)急服務(wù)車輛這兩個概念.

2 模型建立

從假定系統(tǒng)內(nèi)所有服務(wù)器具有相等的繁忙率到假設(shè)不同的區(qū)域有不同的繁忙率，這在假設(shè)條件上有很大的改善，所以以下模型選擇區(qū)域水平的服務(wù)器繁忙率.以往研究有服務(wù)水平保證的覆蓋模型大多是直接以機(jī)會約束的形式給出服務(wù)水平約束條件，本文從覆蓋量的角度來規(guī)定這一約束.

變量含義如下：

xij＝需求點i分派到設(shè)施點j的需求量；

M是一個充分大的數(shù)，其余符號如上文所述.

（2）式和（3）式表明需求點的需求量只能分派到服務(wù)半徑內(nèi)的設(shè)施點；（4）式要求只有在設(shè)施點至少安排了k－1臺服務(wù)器時，它才有可能至少安排了k臺服務(wù)器；（5）式是服務(wù)器數(shù)量關(guān)系；（6）式是允許安排的總服務(wù)器的數(shù)量；（7）式表明只有設(shè)施點建立了，它才能對其他需求點提供服務(wù)；（8）式保證只有服務(wù)站點能夠?qū)χ車男枨筇峁┮?guī)定水平的服務(wù)時，此部分需求才被計入目標(biāo)函數(shù)中；（9）式和（10）式是相應(yīng)的變量取值范圍約束.

觀察目標(biāo)函數(shù)（1）式和約束（8）式，可以發(fā)現(xiàn)這是一個非線性規(guī)劃模型，同時（8）式中變量出現(xiàn)在下標(biāo)和求和符號中，所以該模型不能通過一般的數(shù)學(xué)優(yōu)化方法或者規(guī)劃軟件進(jìn)行求解.雖然M1模型求解起來很困難，但是它提供了直接針對服務(wù)器繁忙率建模的描述性模型.在目標(biāo)函數(shù)（1）式和約束條件（8）式中，如果令β＝0，則所有zj＝1滿足約束條件（8）式，因此該問題等價于不考慮服務(wù)器是否繁忙的最大覆蓋問題.當(dāng)β≠0時，只有滿足約束1－Pyj≥β的設(shè)施點j的覆蓋量才被計入目標(biāo)函數(shù).所以，為了使目標(biāo)函數(shù)達(dá)到最大，既要盡可能多的覆蓋，同時還要使覆蓋這些需求的服務(wù)器繁忙水平不超過1－β（使得盡可能多的zj＝1）.基于上述分析，如果可以保證分派到某個設(shè)施點的需求不會使得該設(shè)施點的服務(wù)器繁忙率超過1－β，那么這種分派方法所得到的需求都會被計入目標(biāo)函數(shù)中.

由于Pyj是所有yj臺服務(wù)器全部繁忙的概率，因此也是系統(tǒng)的呼叫損失率，為了使1－Pyj≥β，也即Pyj≤1－β，一方面可以增加服務(wù)器的數(shù)量；另一方面也可以減少服務(wù)的需求量.由于需求可以部分滿足，所以對于任意正整數(shù)k臺服務(wù)器，總可以找到與之對應(yīng)的惟一最大需求量使得恰好Pk＝1－β，這也是在k臺服務(wù)器時能夠保證服務(wù)水平的最大可處理需求量.如果記MAXk為使得Pk＝1－β成立的最大需求量，同時要最大化單位時間內(nèi)能夠得到服務(wù)水平保證的需求量，則可以得到第二個模型M2：

符號含義如下：MAXk＝k臺服務(wù)器在滿足服務(wù)水平約束時能夠處理的最大需求量.

各變量含義如下：其他符號如前文所述，應(yīng)當(dāng)注意，此處的Yjk和模型M1中的yjk含義并不相同.

（12）式和（13）規(guī)定了需求分派的方式和范圍；（14）式限制了每個設(shè)施點能夠服務(wù)的最大需求量；（15）式要求只有設(shè)施點j建立了，才可能夠向該設(shè)施點分派服務(wù)器，并且只能有一種分派方式；（16）式要求各個設(shè)施點服務(wù)器的總和不應(yīng)超過可得到的服務(wù)器數(shù)量；（17）式和（18）式是相應(yīng)的變量范圍約束.由于（14）式保證了每個設(shè)施點服務(wù)的需求都不低于給定的服務(wù)水平，所以目標(biāo)函數(shù)（11）式簡化為最大化這種可行的需求分派量.

模型M2是一個混合整數(shù)線性規(guī)劃問題，比起M1模型，它求解起來要相對容易，可以通過已知的覆蓋選址算法進(jìn)行求解，也可以直接利用優(yōu)化軟件進(jìn)行求解.在下面的部分，本文將根據(jù)排隊論的性質(zhì)設(shè)計出在設(shè)施點的服務(wù)器數(shù)量無限制時所對應(yīng)的貪婪算法.

3 算法設(shè)計與求解

3.1 算法設(shè)計

首先考慮這樣一種情況，對于固定的某一覆蓋量，如果存在兩種（或幾種）不同的覆蓋方法，為了達(dá)到特定的服務(wù)水平，其中的一種方法所需要的服務(wù)器數(shù)目較少，或者使用相同數(shù)量的服務(wù)器，它能提供更高的服務(wù)水平，那么這種方法所達(dá)到的覆蓋量一定要更接近最優(yōu)值.由于Pyj是所有yj臺服務(wù)器全部繁忙的概率，因此也是系統(tǒng)的呼叫損失率，合理的想法就是找到這樣一種覆蓋方法：在同等的覆蓋量或者資源條件下，它的呼叫損失較小，從而這部分覆蓋量更可能被計入目標(biāo)函數(shù).下面給出基于M／M／k／k排隊系統(tǒng)的一個性質(zhì).

性質(zhì)1 如果到達(dá)率為λ，單臺服務(wù)器的服務(wù)率為μ，服務(wù)器數(shù)量為k（k≥2），則k臺服務(wù)器集中服務(wù)的M／M／k／k系統(tǒng)要比k個分散服務(wù)的M／M／1／1系統(tǒng)具有較小的呼叫損失率.

證 M／M／s／s損失系統(tǒng)：假定顧客到達(dá)率服從參數(shù)為λ的泊松分布，每臺服務(wù)器的服務(wù)時間服從參數(shù)為μ的指數(shù)分布，服務(wù)器個數(shù)為s，系統(tǒng)容量為s.記pk為系統(tǒng)有k臺服務(wù)器處于繁忙狀態(tài)，則根據(jù)系統(tǒng)平衡狀態(tài)的轉(zhuǎn)移方程可以得到：

如果令α＝λ／μ，通過迭代求解式可以解得

因此對于M／M／1／1系統(tǒng)有

現(xiàn)在假如將s臺服務(wù)器分開單獨(dú)服務(wù)，則平均每臺服務(wù)器所對應(yīng)的顧客到達(dá)率和它處于繁忙狀態(tài)的概率為

令Δs＝p1－ps，現(xiàn)在證明對于任意的α＞0，s≥2有Δs＞0.

故對任意α＞0，s≥2有p1＞ps.

由上述性質(zhì)可知，對于同樣的需求量，應(yīng)盡可能將所有的需求集中起來服務(wù)，這樣可以保證較小的呼叫損失率（從而1－Pk更大）.根據(jù)上述性質(zhì)，同等條件下集中服務(wù)能夠提高服務(wù)水平，下面將根據(jù)性質(zhì)1設(shè)計求解問題的貪婪算法.算法假定單個設(shè)施點允許安排的服務(wù)器數(shù)量無限制，當(dāng)單個設(shè)施點允許安排的服務(wù)器數(shù)量相對較大時，該假設(shè)是合理的.

下面為了敘述方便，先提出以下幾個概念.

最大分派覆蓋量：設(shè)施點的最大分派覆蓋量是所有在該設(shè)施點的覆蓋半徑內(nèi)，且還未被分派的需求點的需求之和，記為MACQ；

實際覆蓋量：設(shè)施點的實際覆蓋量是在其覆蓋半徑內(nèi)，實際分派給該設(shè)施點的所有需求之和，記為ACQ；

冗余覆蓋量：設(shè)施點的冗余覆蓋量等于最大分派覆蓋量減去實際覆蓋量，即RCQ＝MACQ－ACQ；

邊際貢獻(xiàn)量：設(shè)施點的最后一臺服務(wù)器的邊際貢獻(xiàn)量是該設(shè)施點的實際覆蓋量與其當(dāng)前服務(wù)器數(shù)量減少1臺時所能覆蓋的最大量之差，如果記設(shè)施點的服務(wù)器數(shù)量為N，則MCQ＝ACQ－MAXN－1；

增加上限：設(shè)施點的增加上限是當(dāng)前數(shù)量臺服務(wù)器所能覆蓋的最大量與實際覆蓋量之差，即AUB＝MAXN－ACQ，N是設(shè)施點的服務(wù)器數(shù)量.

冗余覆蓋量反映了能夠覆蓋但未被覆蓋的需求量，這部分需求量是當(dāng)服務(wù)器數(shù)量增加時可以進(jìn)一步覆蓋的量；增加上限是設(shè)施點在當(dāng)前給定數(shù)量服務(wù)器條件下，所能夠進(jìn)一步覆蓋的最大需求量，它反映了設(shè)施點剩余的覆蓋能力.

下面給出算法的具體實現(xiàn)步驟：

Init：初始化潛在設(shè)施點的相關(guān)參數(shù)，包括最大分派覆蓋量、實際覆蓋量、冗余覆蓋量、邊際貢獻(xiàn)量以及增加上限.

Phase1：

Step1：判斷當(dāng)前可以使用的服務(wù)器數(shù)量是否為零，或者潛在設(shè)施點能夠覆蓋的需求是否為零，如果是則Stop；

Step2：計算所有未建立的潛在設(shè)施點的最大分派覆蓋量，并選擇其中的最大者Fk，其最大分派覆蓋量為MACQk；

Step3：標(biāo)記設(shè)施點Fk已經(jīng)建立，如果剩余的服務(wù)器數(shù)量不足以覆蓋設(shè)施點Fk的最大分派覆蓋量，則分派所有的服務(wù)器到該設(shè)施點；否則，分派n臺服務(wù)器到該設(shè)施點，其中n滿足｛n｜MAXn－1＜MACQk，MAXn≥MACQk｝.設(shè)置Fk覆蓋半徑內(nèi)的所有需求量為零，更新可以使用的服務(wù)器數(shù)量及設(shè)施點的相關(guān)參數(shù)，返回Step1.

Phase2：

記F1，F(xiàn)2，…，F(xiàn)q為第一階段順序建立的設(shè)施點，q是建立的設(shè)施點個數(shù).

1.Demand Moving：

Step1：選擇Phase1生成的最后一個設(shè)施點Fq，判斷它的冗余覆蓋量是否為零，如果是則Stop；否則從前q－1個設(shè)施點中選擇邊際貢獻(xiàn)量最小的設(shè)施點Fi，令k＝1；

Step2：選擇Fi后面的第k個設(shè)施點Fi＋k，如果兩者的共同覆蓋區(qū)域有公共需求點并且可以轉(zhuǎn)移的最大需求量不為零，則轉(zhuǎn)移該部分需求，更新設(shè)施點的相關(guān)參數(shù)；

Step3：判斷設(shè)施點Fi的邊際貢獻(xiàn)量是否非正，或者Fi＋k是否等于Fq，如果是，轉(zhuǎn)Step4；否則令k＝k＋1，返回Step2；

Step4：如果設(shè)施點Fi的邊際貢獻(xiàn)量小于設(shè)施點Fq增加一臺服務(wù)器所產(chǎn)生的需求增加量，則將設(shè)施點Fi最后一臺服務(wù)器移動到Fq處，更新設(shè)施點的相關(guān)參數(shù)，返回Step1；否則Stop.

2.Server Moving：

Step 1：在未建立的潛在設(shè)施點中，選擇最大分派覆蓋量最大的設(shè)施點fk，其最大分派覆蓋量為MACQfk，如果MACQfk＜MAX1，Stop；否則，轉(zhuǎn)Step2；

Step2：令K＝argn｛MAXn≤MACQfk，MAXn＋1＞MACQfk｝，K＝min｛K，q｝；對已經(jīng)建立的設(shè)施點按照其最后一臺服務(wù)器的邊際貢獻(xiàn)量升序排序，排序后的設(shè)施點記為I1，I2，…，In；

Step3：令K＝argmaxn｛MAXn／n≥MCIn｝，如果K＝?，Stop，否則將設(shè)施點I1，I2，…，In的最后一臺服務(wù)器移動到設(shè)施點fk，標(biāo)記建立設(shè)施點fk并更新設(shè)施點的相關(guān)參數(shù)，Stop.

3.2 計算實例

為了驗證模型和算法的有效性，假定在平面上存在N個需求點，每一個需求點都可以作為潛在的設(shè)施點，并且每個需求點單位時間的需求參數(shù)λi由［1，10］之間的整數(shù)均勻分布產(chǎn)生，需求點的縱橫坐標(biāo)服從［1，100］之間的整數(shù)均勻分布.

假定服務(wù)器數(shù)量等于需求點的個數(shù)N，所有服務(wù)器具有相同的服務(wù)率μ＝θΛ／N，其中Λ為總需求，θ為參數(shù)分別取1.05和1.15（對應(yīng)的系統(tǒng)利用率大約分別為95%和85%）；服務(wù)半徑S分別?。害遥?、σ－10和σ－15，其中σ為所有需求點距離的標(biāo)準(zhǔn)差；給定的服務(wù)水平β分別取95%，80%.

以上算法和M2問題分別通過Matlab R2012a和Lingo11.0編程實現(xiàn)，并在個人電腦Lenovo－R400上運(yùn)行（CPU 2.40Ghz，內(nèi)存2G）.表1給出了在不同問題規(guī)模時，上述算法和Lingo程序的計算結(jié)果.其中最優(yōu)值列加星號的部分為Lingo程序運(yùn)行1h以上給出的可行解（在給定時間1h未求得最優(yōu)解），同時上界列是Lingo給出的最優(yōu)目標(biāo)函數(shù)值上界.誤差列是上述算法最優(yōu)解同Lingo程序最優(yōu)解（或可行解）之間的差異.CPU time列的Matlab子列為上述算法求解時間（取Matlab第二次運(yùn)行時間①），Lingo列為Lingo程序運(yùn)行時間②.

表1 計算結(jié)果Tab.1 Computational results

（續(xù)表）

由表1可以發(fā)現(xiàn)：在選址數(shù)量上，上述算法和Lingo程序給出的解基本一致，當(dāng)覆蓋半徑較小時，Lingo精確解趨向于建立較多的設(shè)施點，在覆蓋半徑較大時，情況則恰好相反，但兩者的選址數(shù)量之差最多不超過1.所以從選址數(shù)量上來看，最終結(jié)果表明：通過選擇較少的設(shè)施點把服務(wù)器集中起來服務(wù)，可以得到較好的選址結(jié)果，這同性質(zhì)1的結(jié)論是一致的.對同一規(guī)模的問題：當(dāng)服務(wù)器的服務(wù)半徑越大時，在同等條件下它所覆蓋的需求也越多，同時所需建立的設(shè)施點數(shù)量也較少，這同直觀感覺是一致的.

在解的質(zhì)量方面，上述算法同精確解（可行解）的誤差大多在3%以內(nèi)，其中僅有一例除外，誤差最大為3.48%.實際的計算結(jié)果表明：算法第二階段的Server Moving部分并不總是可以進(jìn)一步改進(jìn)目標(biāo)函數(shù)值，改進(jìn)的程度大約在1%左右.但是目標(biāo)函數(shù)改進(jìn)卻額外增加了一個新的設(shè)施點，當(dāng)設(shè)施點的固定建造成本較大時，結(jié)果可能并不理想.

最后，在程序運(yùn)行的時間方面，上述算法具有較大的優(yōu)勢.即使是在N＝120時，Matlab的求解時間也不到1s，然而通過Lingo程序求解混合整數(shù)線性規(guī)劃模型M2時，在N≥100時，大部分實例運(yùn)行1h以上仍然得不到最優(yōu)解.所以上述算法可以迅速地對大規(guī)模問題提供合理的下界估計.

為了分析可靠性水平β對總需求量覆蓋情況的影響，選擇需求點數(shù)量N＝80，θ＝1.05，覆蓋半徑R＝組的數(shù)據(jù)，考察β在85%～95%之間變動時（每間隔1%取值），需求覆蓋度（實際覆蓋的需求量／總需求量×100%）的變動情況，如圖1.可以發(fā)現(xiàn)：隨著可靠性水平的不斷提高，總的覆蓋度逐漸減少，但是這種關(guān)系并不是嚴(yán)格線性的；同時，本文算法求出的最優(yōu)解和Lingo給出的最優(yōu)解之間的差距非常小，這也說明了上述算法的有效性，Lingo仍有3組數(shù)據(jù)在1h之內(nèi)無法求得最優(yōu)解（β＝88%，93%，94%）.

圖2顯示了服務(wù)器數(shù)量和服務(wù)可靠性水平對需求覆蓋度的影響，其中實線標(biāo)記的部分為Lingo給出的最優(yōu)解，虛線部分是Matlab運(yùn)行本文算法得出的解.可以發(fā)現(xiàn)：在同一可靠性水平時，服務(wù)器數(shù)量越多，覆蓋的總需求也越多；在同一服務(wù)器數(shù)量時，可靠性水平越小，覆蓋的總需求越多.總體來看，本文算法同Lingo精確解之間的差異相對較小，當(dāng)服務(wù)器數(shù)量較多以及總的覆蓋率較大時，誤差相對增加，但最多不超過2%.

4 結(jié) 論

本文建立了有服務(wù)水平保證、基于排隊論的應(yīng)急服務(wù)車輛最大覆蓋選址模型.由于運(yùn)用了排隊論模型來研究應(yīng)急服務(wù)車輛的繁忙狀態(tài)，因此可以不用假定各個服務(wù)器繁忙與否是相互獨(dú)立的，而基于區(qū)域水平的服務(wù)器繁忙率也比系統(tǒng)水平的估計更準(zhǔn)確.與以往文獻(xiàn)不同的是，在處理服務(wù)水平約束時，它們多從機(jī)會約束的角度通過調(diào)整服務(wù)器的數(shù)量來滿足約束條件，而本文則從調(diào)整覆蓋量的角度給出了約束條件.模型M1提供了求解問題的描述性框架，而服務(wù)水平和排隊系統(tǒng)中的呼叫損失率之間的相互關(guān)系使得可以將M1模型轉(zhuǎn)化為較易求解的M2模型.排隊論中的一個重要性質(zhì)也為設(shè)計求解M2模型的算法提供了重要的依據(jù)，計算結(jié)果表明：在時間和效果上，該算法是有效的.

但是只設(shè)計了設(shè)施點服務(wù)器數(shù)量無限制時的算法，對于設(shè)施點服務(wù)器數(shù)量受到很大的限制時，性質(zhì)1的優(yōu)勢可能不再明顯.因此需求的分派方式也更接近于一般的最大覆蓋問題.另外，在本文中需求可以部分滿足，也沒有考慮工作量平衡問題，所以對于更一般的問題還要設(shè)計相應(yīng)的有效算法來求解.

［1］Toregas C，Swain R，ReVelle C，et al.The location of emergency services facilities［J］.Operations Research，1971，19：1363－1373.

［2］Current J，Morton O K.Locating emergency warning sirens［J］.Decision Sciences，1922，23：221－234.

［3］Church R，ReVelle C.The maximal covering location problem［J］.Papers of the Regional Science Association，1974，32：101－118.

［4］Daskin M S.A maximum expected covering location model：Formulation，properties and heuristic solution［J］.Transportation Science，1983，17：47－70.

［5］ReVelle C，Hogan K.A reliability－constrainted siting model with local estimates of busy factions［J］.Environment and Planning B：Planning and Design，1988，15：143－152.

［6］ReVelle C，Hogan K.The maximum availability location problem［J］.Transportation Science，1989，23（3）：192－200.

［7］Larson C R.A hypercube queuing model for facility location and redistricting in urban emergency services［J］.Computers and Operations Research，1974，1：67－95.

［8］Larson C R.Approximating the performance of urban emergency service systems［J］.Operations Research，1975，23：845－868.

［9］Marianov V，ReVelle C.The queuing probabilistic location set covering problem and some extensions［J］.Socio－Economic Planning Sciences，1994，28：167－178.

［10］Marianov V，ReVelle C.The queueing maximal availability location problem：A model for the siting of emergency vehicles［J］.European Journal of Operational Research，1996，93：110－120.

［11］Schilling D A，Jayaraman V，Barkhi R.A review of covering problem in facility location［J］.Location Science，1993，1（1）：25－55.

［12］Farahani R Z，Asgarin N，Herdari N，et al.Covering problems in facility location：A review［J］.Computers ＆Industrial Engineering，2012，62：368－407.

［13］Synder L.Facility location under uncertainty：A review［J］.IIE Transactions，2006，38：537－554.

［14］Boffey B，Galvao R，Espejo L.A review of congestion models in the location of facilities with immobile servers［J］.European Journal of Operational Research，2007，178：642－662.

［15］Berman O，Drezner Z.The multiple server location problem［J］.Journal of Operational Research Society，2007，58：91－99.

［16］Aboolian R，Berman O，Drezner Z.The multiple server center location problem［J］.Annals of Operations Research，2009，167：337－352.

［17］Baron O，Berman O，Krass D.Facility location with stochastic demand and constraints on waiting time［J］.Manufacturing Service Operation Management，2008，3：484－505.

［18］Borrás F，Pastor J.The ex－post evaluation of the minimum local reliability level：An enhanced probabilistic location set covering model［J］.Annals of Operations Research，2002，111：51－74.

［19］Narayan B U.An introduction to queueing theory－modeling and analysis in applications［M］.Berlin：Birkhauser，2007.