殷代君

【摘要】結(jié)合時(shí)間與服務(wù)效用，研究有容量限制的擁塞設(shè)施選址問(wèn)題。從被服務(wù)者角度考察制約設(shè)施點(diǎn)覆蓋水平的各種因素，由到達(dá)設(shè)施的時(shí)間給出時(shí)間滿(mǎn)意度函數(shù)，由損失概率和平均等待時(shí)間給出服務(wù)效用函數(shù)，在綜合考慮時(shí)間滿(mǎn)意度與服務(wù)效用雙重因素影響下建立改進(jìn)的廣義最大覆蓋選址模型，并與基于時(shí)間滿(mǎn)意的最大覆蓋問(wèn)題比較，考察對(duì)選址決策的影響與改進(jìn)。

【關(guān)鍵詞】時(shí)間滿(mǎn)意度；服務(wù)效用；IGMCLP；擁塞設(shè)施選址

一、引 言

自Church和Revelle等于1974年提出了MCLP(Maximal Covering Location Problem)模型后，最大覆蓋模型（MCLP）已被證明為是最有用的選址模型之一。但是MCLP存在一個(gè)缺陷——覆蓋度的二元化假設(shè)，即任一節(jié)點(diǎn)i要么被完全覆蓋，要么完全不被覆蓋，這一假設(shè)通常會(huì)導(dǎo)致某些需求點(diǎn)被決策者放棄，但這往往是不合理的。Berman和Krass［1］于2002年提出的廣義最大覆蓋模型（GMCLP）彌補(bǔ)了這一缺陷，將覆蓋度多元化，即定義為一個(gè)［0,1］之間的非增分段函數(shù)，在完全覆蓋與不被覆蓋之間提出了“部分覆蓋”的觀點(diǎn)，目標(biāo)依然是使被覆蓋節(jié)點(diǎn)的總權(quán)重達(dá)到最大。

近年來(lái)，國(guó)際上對(duì)擁塞設(shè)施選址問(wèn)題的研究引起了廣泛關(guān)注。目前，針對(duì)擁塞設(shè)施選址研究主要有兩類(lèi)模型，分別為覆蓋模型和中位模型，已有文獻(xiàn)多是利用MCLP或綜合考慮其他因素的改進(jìn)MCLP進(jìn)行建模，還沒(méi)有利用GMCLP進(jìn)行建模。

另一方面，用傳統(tǒng)的最大覆蓋問(wèn)題解決擁塞設(shè)施選址問(wèn)題時(shí)，通常都只從決策者（提供服務(wù)者）的角度去考慮，沒(méi)有考慮被服務(wù)者的選擇條件與選擇偏好。如有的服務(wù)設(shè)施建立在人口密度非常大的市中心，雖然覆蓋的人口數(shù)很大，但是顧客在到達(dá)設(shè)施點(diǎn)的過(guò)程中經(jīng)常會(huì)遇到擁堵，進(jìn)入設(shè)施后又會(huì)出現(xiàn)排隊(duì)等待，這些都是影響顧客是否選擇該設(shè)施點(diǎn)的因素，很可能會(huì)導(dǎo)致部分顧客因設(shè)施擁塞而改選其他位置稍遠(yuǎn)但交通便利、顧客較少的設(shè)施點(diǎn)。服務(wù)設(shè)施的實(shí)際有效覆蓋度并沒(méi)有預(yù)期的大。

本文基于M/M/1/k排隊(duì)系統(tǒng)，研究有容量限制的擁塞設(shè)施選址問(wèn)題，從被服務(wù)者角度考察制約設(shè)施點(diǎn)覆蓋水平的各種因素，由到達(dá)設(shè)施的時(shí)間給出時(shí)間滿(mǎn)意度函數(shù)，由設(shè)施因擁塞而導(dǎo)致?lián)p失的概率和等待時(shí)間給出服務(wù)效用函數(shù)，在綜合考慮時(shí)間滿(mǎn)意度與服務(wù)效用雙重因素影響下建立改進(jìn)的廣義最大覆蓋選址模型（Improve Generalized Maximal Covering Location Problem—IGMCLP），目標(biāo)是使設(shè)施的有效覆蓋度達(dá)到最大。

二、模型的建立

1筆奔瀆意度函數(shù)

設(shè)tij表示從需求點(diǎn)i到設(shè)施點(diǎn)j所用時(shí)間，tij的大小受路況、出行時(shí)間的影響，往往不是一個(gè)固定值，令Dj表示在道路最擁堵情況下，到達(dá)設(shè)施j的時(shí)間上限，Lj表示最暢通情況下到達(dá)設(shè)施j的時(shí)間下限，Lj≤Dj，f(tij)為顧客對(duì)到達(dá)時(shí)間的滿(mǎn)意度水平，它是一個(gè)［0,1］之間的非增函數(shù)。當(dāng)tijDj時(shí),滿(mǎn)意度水平降為0；當(dāng)Lj≤tij≤Dj時(shí)，f(tij)可以有多種定義形式，最常用的形式是凹凸分布曲線(xiàn)，即f(tij)=1-tij-LjDj-Ljα,(α>0)（2。1。1），α是正的時(shí)間敏感系數(shù)。敏感系數(shù)的大小受個(gè)人偏好的影響，所以確定α的取值應(yīng)根據(jù)所面向的服務(wù)對(duì)象而定。

2被于M/M/1/k排隊(duì)系統(tǒng)的服務(wù)效用函數(shù)

在這里假設(shè)每個(gè)設(shè)施j是一個(gè)服務(wù)臺(tái)，有容量限制kj，即每個(gè)設(shè)施都可看成M/M/1/kj排隊(duì)系統(tǒng)。顧客流是參數(shù)為λ的Poisson流，λ為單位時(shí)間內(nèi)平均到達(dá)的顧客數(shù)；在任意時(shí)刻t，系統(tǒng)中的顧客數(shù)N(t)服從泊松分布；1μ為每個(gè)顧客的平均服務(wù)時(shí)間，ρ=λμ為系統(tǒng)的服務(wù)強(qiáng)度。

因?yàn)橛腥萘肯拗疲栽O(shè)施j中的顧客數(shù)量達(dá)到kj時(shí)，下一個(gè)到來(lái)的顧客將自動(dòng)離開(kāi)，稱(chēng)Pjkj為“損失概率”。如果設(shè)施j正處于忙期，顧客i在選擇設(shè)施j后將進(jìn)入排隊(duì)等待狀態(tài)，服務(wù)時(shí)間包括等待時(shí)間和服務(wù)進(jìn)行時(shí)間。設(shè)服務(wù)時(shí)間為Fij，等待時(shí)間為Wij，服務(wù)進(jìn)行時(shí)間為sij，則上述關(guān)系可以表示為Fij=Wij+Sij。系統(tǒng)的平均服務(wù)時(shí)間為Fj=Wj+Sj=Wj+1μ，則顧客i選擇設(shè)施j后所產(chǎn)生的消耗為(1-pjkj)Fj，同時(shí)也會(huì)產(chǎn)生一個(gè)效用值，該效用值與消耗成反比。為把效用值控制在［0,1］范圍內(nèi)，采用降對(duì)數(shù)Sigmoid函數(shù)形式定義服務(wù)效用函數(shù)，即Uj=11+eβ(1-pjkj)Fj，j∈J（2。2。1），β為正的服務(wù)效用敏感系數(shù)，當(dāng)β較小時(shí)，效用值隨消耗的增加而下降的幅度不大；反之，則下降幅度較大。服務(wù)設(shè)施j一經(jīng)建立后，設(shè)施容量即可確定，平均等待時(shí)間由平均隊(duì)長(zhǎng)決定，它恰好體現(xiàn)了設(shè)施的擁塞程度，也決定著設(shè)施的服務(wù)質(zhì)量。

3盜GMCLP模型的建立

假設(shè)一個(gè)服務(wù)網(wǎng)絡(luò)G=(I,E)，I是節(jié)點(diǎn)集合(|I|=n)，E是邊集合，并設(shè)J為候選設(shè)施點(diǎn)集合(|J|=m）。每個(gè)節(jié)點(diǎn)i∈N都對(duì)應(yīng)一個(gè)權(quán)重wi，可以是人口密度，也可以是呼叫服務(wù)頻數(shù)。

在該網(wǎng)絡(luò)中，對(duì)每個(gè)需求點(diǎn)i，不同的設(shè)施點(diǎn)j對(duì)應(yīng)不同的到達(dá)時(shí)間。如果按照到達(dá)時(shí)間的升序排列，每個(gè)點(diǎn)i對(duì)應(yīng)一個(gè)多重時(shí)間集合：0…>f(tijm)≥0。又由于每個(gè)設(shè)施點(diǎn)j的容量規(guī)模和面向的顧客類(lèi)型、密度不同，所以每個(gè)設(shè)施j所提供的服務(wù)質(zhì)量有所不同。由不同的服務(wù)質(zhì)量產(chǎn)生了不同的服務(wù)效用值，如果按照效用值的降序排列，每個(gè)需求點(diǎn)i又對(duì)應(yīng)一個(gè)多重效用值集合：1≥Uij′ 1>Uij′ 2>…>Uij′ m≥0。顯然，序列j1,j2,…,jm與序列j′ 1,j′ 2,…,j′ m有可能完全不同。因此，本文綜合考慮到達(dá)時(shí)間與服務(wù)效用獲得兩個(gè)方面的因素來(lái)定義覆蓋度，目標(biāo)是使有效覆蓋度達(dá)到最大。

對(duì)衖∈I，每一j∈J對(duì)i產(chǎn)生兩個(gè)函數(shù)值，即f(tij)與Uij，因此j對(duì)i的覆蓋水平定義為線(xiàn)性加權(quán)組合aij=θ1f(tij)+θ2Uij,θ1,θ2>0，θ1+θ2=1（2。3。1），θ1,θ2是權(quán)重系數(shù)，aij∈［0,1］。θ1,θ2剛好體現(xiàn)了顧客的選擇偏好，若θ1>θ2，則認(rèn)為到達(dá)時(shí)間比服務(wù)質(zhì)量重要；反之，則認(rèn)為服務(wù)效用的獲得更重要。對(duì)某一需求點(diǎn)i，所有j∈J對(duì)i產(chǎn)生一個(gè)覆蓋水平序列：1≥aij1>aij2>…>aijm≥0，我們將序列j1,j2,…,jm分別對(duì)應(yīng)于覆蓋級(jí)別1,2,…,m，進(jìn)而得到覆蓋級(jí)別序列：1≥a1i>a2i>…>ami≥0。

對(duì)每個(gè)需求點(diǎn)i而言，在不考慮其他因素的情況下，每個(gè)設(shè)施對(duì)它產(chǎn)生的時(shí)間滿(mǎn)意度值和服務(wù)效用值是唯一的，因此對(duì)它產(chǎn)生的覆蓋度也是唯一的，ali與某一aij相對(duì)應(yīng)，一旦j確定，l即唯一，因此，決策變量可以直接寫(xiě)成yij。進(jìn)一步，由于wi是常數(shù)，對(duì)于確定的j，ali也是常數(shù)，所以定義常量cij=wiali，i∈I，j∈J。那么，模型可以表達(dá)為（IP1）：

max∑ni=1∑mj=1cijyij。

(1)

s。t。cij=wiali。

(2)

∑j∈JXj=P。

(3)

yij≤Xj,衖∈I,j∈J。

(4)

∑j∈Jyij≤1,衖∈I。

(5)

Xj,yij∈{0,1}。

(6)

目標(biāo)是使有效覆蓋的需求點(diǎn)的總權(quán)重達(dá)到最大。式(3)是應(yīng)急設(shè)施數(shù)約束，式(4)表明應(yīng)首先在j點(diǎn)建立設(shè)施才能為需求點(diǎn)i提供服務(wù)，式(5)說(shuō)明需求點(diǎn)i只被分配給其中一個(gè)設(shè)施，最后是變量的0-1約束。

三、模型的求解

當(dāng)問(wèn)題規(guī)模較小時(shí)，可以采用整數(shù)規(guī)劃的分支定界法，即先求解原問(wèn)題的線(xiàn)性松弛問(wèn)題，對(duì)解向量中的非整數(shù)部分再進(jìn)行分支定界。分支定界法的關(guān)鍵技術(shù)在于各結(jié)點(diǎn)權(quán)值如何估計(jì)，可以說(shuō)一個(gè)分支定界求解方法的效率基本上由值界方法決定，若界估計(jì)不好，在極端情況下將與窮舉搜索沒(méi)多大區(qū)別。

當(dāng)問(wèn)題規(guī)模較大時(shí)，分支定界法無(wú)能為力了，因?yàn)镚MCLP是NP-hard問(wèn)題，只能依靠啟發(fā)式或近似算法來(lái)求解。目前，在選址問(wèn)題中解整數(shù)規(guī)劃模型的常見(jiàn)啟發(fā)式算法如貪婪(Gr)算法、拉格朗日松弛（Lagrangian Relaxation）算法。針對(duì)覆蓋問(wèn)題，拉格朗日松弛算法在許多選址模型中都有應(yīng)用，其基本原理是，利用拉格朗日乘子松弛掉原問(wèn)題中難以處理的約束，從而將問(wèn)題變?yōu)檩^易解決的拉格朗日問(wèn)題，并通過(guò)求取拉格朗日對(duì)偶問(wèn)題而逐步逼近獲取原問(wèn)題的最優(yōu)解，具體迭代過(guò)程見(jiàn)文獻(xiàn)［2］。

除啟發(fā)式算法外還有許多搜索能力強(qiáng)、收斂性較好的人工智能算法，如禁忌搜索（Tabu Search）算法、模擬退火（SA）算法、粒子群（PSO）算法等，這些算法各有優(yōu)劣。李彤于2005年提出一種以植物向光性機(jī)理為準(zhǔn)則的智能優(yōu)化算法，即模擬植物生長(zhǎng)（PGSA）算法，該算法在整數(shù)規(guī)劃、組合優(yōu)化及工程技術(shù)領(lǐng)域日益顯示出其突出的穩(wěn)定性、精確性和全局搜索能力，具有良好的應(yīng)用前景。

四、計(jì)算實(shí)驗(yàn)

假設(shè)有10個(gè)需求點(diǎn)，按正態(tài)分布N(0。5,22)隨機(jī)生成需求點(diǎn)的權(quán)重向量,有5個(gè)候選設(shè)施點(diǎn)，在此要建立3個(gè)服務(wù)設(shè)施。由于到達(dá)時(shí)間矩陣只在程序最初調(diào)用一次，所以可以按正態(tài)分布N(25,52)隨機(jī)生成，記為T(mén)，由時(shí)間矩陣T按照公式（2。1。1）生成滿(mǎn)意度矩陣F。在M/M/1/k排隊(duì)系統(tǒng)中，參數(shù)λ,μ可根據(jù)已建成的同類(lèi)型設(shè)施的服務(wù)情況來(lái)估計(jì)，容量kj由設(shè)施所選位置決定，因此服務(wù)效用矩陣可由公式（2。2。1）計(jì)算，并按公式（2。3。1）得到覆蓋度矩陣A。利用Lingo9。0編程計(jì)算。

1崩用基于時(shí)間滿(mǎn)意的MCLP求解

Global optimal solution found。

objective value: 4。075445

Extended solver steps： 0

Total solver iterations: 0