基于时间满意度与服务效用的改进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