基于時間滿意度與服務效用的改進GMCLP研究

殷代君

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

【關鍵詞】時間滿意度；服務效用；IGMCLP；擁塞設施選址

一、引 言

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

近年來，國際上對擁塞設施選址問題的研究引起了廣泛關注。目前，針對擁塞設施選址研究主要有兩類模型，分別為覆蓋模型和中位模型，已有文獻多是利用MCLP或綜合考慮其他因素的改進MCLP進行建模，還沒有利用GMCLP進行建模。

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

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

二、模型的建立

1筆奔瀆意度函數

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

2被于M/M/1/k排隊系統的服務效用函數

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

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

3盜GMCLP模型的建立

假設一個服務網絡G=(I,E)，I是節點集合(|I|=n)，E是邊集合，并設J為候選設施點集合(|J|=m）。每個節點i∈N都對應一個權重wi，可以是人口密度，也可以是呼叫服務頻數。

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

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

對每個需求點i而言，在不考慮其他因素的情況下，每個設施對它產生的時間滿意度值和服務效用值是唯一的，因此對它產生的覆蓋度也是唯一的，ali與某一aij相對應，一旦j確定，l即唯一，因此，決策變量可以直接寫成yij。進一步，由于wi是常數，對于確定的j，ali也是常數，所以定義常量cij=wiali，i∈I，j∈J。那么，模型可以表達為（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)

目標是使有效覆蓋的需求點的總權重達到最大。式(3)是應急設施數約束，式(4)表明應首先在j點建立設施才能為需求點i提供服務，式(5)說明需求點i只被分配給其中一個設施，最后是變量的0-1約束。

三、模型的求解

當問題規模較小時，可以采用整數規劃的分支定界法，即先求解原問題的線性松弛問題，對解向量中的非整數部分再進行分支定界。分支定界法的關鍵技術在于各結點權值如何估計，可以說一個分支定界求解方法的效率基本上由值界方法決定，若界估計不好，在極端情況下將與窮舉搜索沒多大區別。

當問題規模較大時，分支定界法無能為力了，因為GMCLP是NP-hard問題，只能依靠啟發式或近似算法來求解。目前，在選址問題中解整數規劃模型的常見啟發式算法如貪婪(Gr)算法、拉格朗日松弛（Lagrangian Relaxation）算法。針對覆蓋問題，拉格朗日松弛算法在許多選址模型中都有應用，其基本原理是，利用拉格朗日乘子松弛掉原問題中難以處理的約束，從而將問題變為較易解決的拉格朗日問題，并通過求取拉格朗日對偶問題而逐步逼近獲取原問題的最優解，具體迭代過程見文獻［2］。

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

四、計算實驗

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

1崩用基于時間滿意的MCLP求解

Global optimal solution found。

objective value: 4。075445

Extended solver steps： 0

Total solver iterations: 0