# Queueing Maximal Covering Location-Allocation Problem: An Extension withM/G/1 Queueing Systems

Authors: Foroogh Moeen Moghadas; Hossein Taghizadeh Kakhki
Journal: Advances in Decision Sciences
 (2011)

---

## Abstract

We consider the queueing maximal covering location-allocation problem (QM-CLAP) with anM/G/1 queueing system. We first formulate the problem as a binary quadratic programming problem and then propose a new solution procedure based on decomposition of the problem into smaller binary quadratic sub-problems. The heuristic procedure GRASP is used to solve the sub-problems, as well as the entire model. Some computational results are also presented.


---

## Body

## 1. Introduction

An extensively studied and widely used model in location theory is the maximal covering location problem (MCLP). It can be stated as follows. Given a set ofmdemand points and a set of n potential new facility locations in the plane, find the location of p
(
<
n
) new facilities such that the demands covered are maximized. A demand point iis said to be covered by a facilityj if the distance (or time) between i andj is no more than a given fixed value,R. In this simple form, the problem is attributed to Church and ReVelle [1] who have modeled it as a binary integer program. Extensions and applications of this model have been discussed by many including ReVelle [2], Schilling et al. [3], Marianov and ReVelle [4], Brotcorne et al. [5], Marianov and Serra [6], and Goldberg [7]. A bibliography for some discrete location problems, including maximal covering location problem, can also be found in ReVelle et al. [8]. Erkut et al. [9] present a computational comparison for five maximal covering models.A variant of this problem, usually called location in congested systems, takes into account the stochastic nature of demand and response times. Berman et al. [10] are among the first to incorporate such systems into location models. They extend Hakimi’s 1-median problem by assuming that demands at nodes follow a Poisson process, and the service time has a general distribution, hence, a network with an M/G/1 queueing system. They propose an algorithm to find the optimal location of a server on such networks. Berman and Mandowsky [11] present a location-allocation model for districting a region with congestion. Berman et al. [12] consider the problem of locating a single facility with M/G/k queueing system. Batta and Berman [13] consider locating a single facility on a network with an M/G/k queue. Batta [14] considers the problem of locating a single server on a network operating as an M/G/1 with nonpreemptive priority queue. Marianov and ReVelle [15] consider the queueing probabilistic location set covering problem with M/G/s/s queueing system. They [4], also use an M/G/s/s queueing system for siting emergency facilities. Marianov and Serra [16] consider probabilistic maximal covering models with constraints on waiting time and for queue length. Jamil et al. [17] consider the problem of locating a single facility with a “center-type” objective in an M/G/1 queueing environment. Silva and Serra [18] consider the MCLP with an M/M/1 queueing system and with different priority levels. They consider both a “directed choice environment” model, where a demand point may be allocated to one center for one priority and to another center for a different priority, and a “user choice environment,” where it is assumed that the customer always chooses the closest center. They propose a heuristic procedure to solve this problem. Moghadas and Kakhki [19] consider the QM-CLAP with M/M/k system and side constraints. In this model, k is unknown and some constraints on the number of servers at each center, as well as constraints on the total costs of establishing a center and locating servers, are imposed. Berman and Krass [20] is a thorough review of the models with stochastic demands and congestion at facilities.In this paper, we consider the maximal covering location problem in a congested system. A single mobile server resides at each center, and demands for service occur in time as a Poisson process. If the server is available, it is immediately dispatched to the demand point. After providing the service, the server returns to its base. If the server is busy, the customer waits in a queue with anM/G/1 system. The objective is to choose the location of at most pservice centers and to allocate demand points to those centers so that the population covered is maximized. Each demand point should be serviced by at most one established service center, and the average waiting time at each service center must not exceed a given threshold. We first formulate the problem as a binary quadratic programming problem with linear and quadratic constrains. Then we propose two solution procedures. The first procedure is based on a decomposition of the problem into smaller binary quadratic knapsack-type subproblems. The second method is the metaheuristic procedure GRASP. Finally some computational results are presented.


## 2. Problem Formulation

In order to formulate the problem, we use the following notations and variables:–I:
the set of all existing demand points (incident locations) (|
I
|
=
m),
–J:
the set of all possible locations of new facilities (centers)(
|
J
|
=
n
),
–a
i:
population at pointi,
–N
i:
the set of points in a pre-specified neighborhood ofi; that is, N
i
=
{
j
∈
J
:
d
(
i
,
j
)
≤
R
}, Ris the covering radius, and d
(
i
,
j
) is the distance between node i and candidate center j,
–p:
the maximum number of new facilities (centers)(
p
<
n
),
–W
j:
average waiting time at facility (center)j,
–τ
j:
maximum allowable waiting time at centerj,
(2.1)
x
i
j
=
{
1
,
if
a
call
from
point
i
is
answered
by
facility
(
center
)
j
,
0
,
otherwise
,
y
j
=
{
1
,
if
a
new
facility
is
located
at
site
j
∈
J
,
0
,
otherwise
.
The queueing maximal covering location-allocation problem (QM-CLAP), with average waiting time at a center constrained to be less than a given time, is modeled as follows (Marianov and Serra [16]):(P)
Max
⁡
∑
i
∈
I
∑
j
∈
N
i
a
i
x
i
j
,
(2.2)
s
.
t
.
∑
j
∈
N
i
x
i
j
≤
1
,
∀
i
∈
I
,
(2.3)
x
i
j
≤
y
j
,
∀
i
∈
I
,
j
∈
J
,
(2.4)
∑
j
∈
J
y
j
≤
p
,
(2.5)
W
j
≤
τ
j
,
∀
j
∈
J
,
(2.6)
x
i
j
,
y
j
∈
{
0,1
}
,
∀
i
∈
I
,
j
∈
J
.
Constraints (2.2) guarantee that each point iis allocated to at most one service center j. Constraints (2.3) ensure that a point is being served only by an established facility at j, Constraint (2.4) establishes at mostpnew centers, and (2.5) ensures that the average waiting time at each center j does not exceed a predetermined amountτ
j. The objective maximizes the population covered.Marianov and Serra [16] considered this problem for the M/M/1 and M/M/m queueing systems and proposed heuristic methods to solve them. Corrêa and Lorena [21] proposed a constructive genetic algorithm, and Corrêa et al. [22] proposed a clustering search procedure to solve this problem. Corrêa et al. [23] convert the problem into a covering graph problem and propose a decomposition approach to solve it. Silva and Serra [18] considered the priority queueing covering location problem (PQCLP) for an M/M/1 system and proposed a GRASP heuristic procedure to solve their problem.In this paper, we consider a problem in which requests for services at each demand point occur with a Poisson process. If the server is available at the time of a call, it travels to the demand point to provide on-scene and perhaps off-scene services. A service is completed only when the server returns home. If the server is unavailable, the customer is entered into a queue with anM/G/1 system, with an infinite queue length and a FIFO discipline. If we assume that the arriving calls from a demand point ihave a Poisson distribution with intensityf
i, then the requests for service at center j is a Poisson process with an intensityλ
j,λ
j
=
∑
i
∈
I
:
j
∈
N
i
f
i
x
i
j (see e.g., Marianov and Serra [16]). i
′
∈
I
:
j
∈
N
i
′  denotes the set of all demand points i which are in a neighborhood of candidate center j.For anM/G/1 queueing system, the waiting time is given by the Pollaczek-Khintchine formula (Kleinrock [24]):(2.7)
W
j
=
{
λ
j
S
𝚥
2
̅
/
2
1
-
λ
j
S
𝚥
̅
,
if
1
-
λ
j
S
𝚥
̅
>
0
,
+
∞
,
otherwise
,
where S
𝚥
̅ and S
𝚥
2
̅ are the first and the second moments of the service time at center j, respectively. Hence, if the stability condition (
1
-
λ
j
S
𝚥
̅
>
0
) holds, then constraints (2.5) can be written as(2.8)
λ
j
(
1
2
S
𝚥
2
̅
+
τ
j
S
𝚥
̅
)
≤
τ
j
.
Now, if we define T
ı
𝚥
̅ and T
ı
𝚥
2
̅ as the first and second moments of service times for the customer i at center j, then we have (see, e.g., Jamil et al. [17])
(2.9)
S
𝚥
̅
=
∑
i
∈
I
:
j
∈
N
i
h
i
T
ı
𝚥
̅
x
i
j
,
S
ı
𝚥
2
̅
=
∑
i
∈
I
:
j
∈
N
i
h
i
T
ı
𝚥
2
̅
x
i
j
,
where h
i is the fraction of calls originating from demand point i which is defined as h
i
=
f
i
/
∑
t
∈
I
f
t. Then,
(2.10)
(
2.8
)
⟹
(
∑
t
∈
I
:
j
∈
N
t
f
t
x
t
j
)
(
1
2
∑
i
∈
I
:
j
∈
N
i
h
i
T
ı
𝚥
2
̅
x
i
j
+
τ
j
∑
i
∈
I
:
j
∈
N
i
h
i
T
ı
𝚥
̅
x
i
j
)
≤
τ
j
⟹
(
∑
t
∈
I
:
j
∈
N
t
f
t
x
t
j
)
(
∑
i
∈
I
:
j
∈
N
i
h
i
(
1
2
T
ı
𝚥
2
̅
+
τ
j
T
ı
𝚥
̅
)
x
i
j
)
≤
τ
j
⟹
∑
i
∈
I
:
j
∈
N
i
∑
t
∈
I
:
j
∈
N
t
[
f
t
h
i
(
1
2
T
ı
𝚥
2
̅
+
τ
j
T
ı
𝚥
̅
)
x
t
j
x
i
j
]
≤
τ
j
.Therefore, the problem with anM/G/1 queue can be written as (2.11)
Max
⁡
∑
i
∈
I
∑
j
∈
N
i
a
i
x
i
j
,
s
.
t
.
(
2.2
)
–
(
2.4
)
,
(
2.10
)
and
(
2.6
)
.
To determine T
ı
𝚥
̅ and T
ı
𝚥
2
̅, we use the same assumptions as in Berman et al. [10]; that is, the average service time for demand point ifrom service center j consists of travel time to the scene, on the scene service time, travel time back to the center j, and possibly additional off-scene time. T
ı
𝚥
̅ and T
ı
𝚥
2
̅ are defined as(2.12)
T
ı
𝚥
̅
=
β
d
(
i
,
j
)
v
+
Z
ı
̅
,
T
ı
𝚥
2
̅
=
(
β
d
(
i
,
j
)
v
)
2
+
2
(
β
d
(
i
,
j
)
v
)
(
Z
ı
̅
)
+
Z
ı
2
̅
,
where the parameter β is greater than or equal to one, d
(
i
,
j
) is the distance between demand point i and center at j, v is the speed, and Z
ı
̅ is the average on-scene plus off-scene (“non-travel related”) service time associated with node i.This problem is NP-hard, and, in general, as the problem is a nonconvex programming problem, even small instances cannot be solved with the existing commercial softwares. A semidefinite programming relaxation for the problem is recently presented by Kakhki and Moghadas [25]. In Section 3 we discuss an approach for decomposing the problem into smaller subproblems and present some solution procedures.


## 3. A Solution Approach for ProblemP

The basic idea for our proposed algorithm is to decompose the problem into smaller subproblems which is inspired by the solution methods suggested in the literature for the capacitated p-median problem (see, e.g., Baldacci et al. [26] and Lorena and Senne [27]).Suppose that we have determined the location ofk
-
1
(
k
≤
p
) centers and want to determine the location of the k
th center from among the n
-
k
+
1  remaining candidate centers. If we remove the demand points assigned to the previous k
-
1 centers, then constraints (2.2) would be satisfied for any customer. In addition we consider the constraints (2.3) and (2.4) implicitly. Therefore, the problem can be decomposed into smaller binary quadratic subproblems (BQSP) as follows:(Pj)
v
j
=
Max
⁡
∑
i
∈
I
̅
:
j
∈
N
i
a
i
x
i
j
,
s
.
t
.
∑
i
∈
I
̅
:
j
∈
N
i
∑
t
∈
I
̅
:
j
∈
N
t
[
f
t
h
i
(
1
2
T
ı
𝚥
2
̅
+
τ
j
T
ı
𝚥
̅
)
x
t
j
x
i
j
]
≤
τ
j
,
x
i
j
∈
{
0,1
}
,
∀
i
∈
I
̅
,
j
∈
J
,
where I
̅  is the set of remaining demand points, not assigned to the k
-
1 previous centers.Now starting withk
=
1, we can solve n
-
k
+
1 binary quadratic subproblems P
j for all j  not in the set of selected centers,J
*. We then find the optimal solution,j
*, delete all the demand points assigned to j
* from I
̅, and add j
* toJ
*. The procedure is continued until k
≥
p, or all the nodes are covered (
I
̅
=
ϕ
). This procedure is outlined in Algorithm 1, below.Algorithm 1:Heuristic algorithm for solving P.
algorithm  Heuristic procedure
begin
Setk
=
1
,
J
*
=
ϕ
,
I
̅
=
I
;
While  k
≤
p & I
̅
≠
ϕ  do
begin
For all j
∉
J
*
do
(
v
j
,
I
j
*
)
=
S
o
l
v
e
(
P
j
,
I
̅
)
;
end;
j
*
=
Arg
(
Max
{
v
j
:
j
∉
J
*
}
)
;
LetJ
*
=
J
*
∪
{
j
*
} and U
p
d
a
t
e
(
I
̅
)
;
k
=
k
+
1;
end;
end;S
o
l
v
e
(
P
j
,
I
̅
)  solves the binary quadratic subproblem P
j for a candidate center j. If a demand point i
(
i
∈
I
̅
) is assigned toj, then i is added to I
j
*. U
p
d
a
t
e
(
I
̅
)removes all demand points assigned to j
* from I
̅.This procedure can be easily extended to solve the more general case of fixed charge facilities; that is, when the objective isMax
∑
i
∈
I
:
j
∈
N
i
a
i
x
i
j
-
∑
j
∈
J
c
j
y
j, where c
j is the cost of establishing a center at site  j. Notice that problem P is nonlinear and can be decomposed into smaller binary quadratic subproblems. Treating the quadratic terms x
i
j
x
t
j’s as a single variable and using linearization methods, such as that of Sherali and Adams [28] will considerably increase the dimension of the problem. Instead we propose to solve the subproblem P
j using GRASP. In the next section, we discuss this procedure in more detail.


## 4. Solving SubproblemP
j with GRASP

GRASP (Greedy Randomized Adaptive Search Procedure) has been developed in late 1980s by Feo and Resende [29, 30]. Since then, it has been successfully applied to many problems, including the maximal covering location problem (Resende [31]). A bibliography of different applications is compiled by Festa and Resende [32, 33]. GRASP consists of two main phases: construction and local search. In the construction phase, a solution is built using a greedy function and randomization. In the local search, an optimal solution in the neighborhood of the solution found in the construction phase is obtained. Here we describe the details of the procedure for solving subproblems P
j with GRASP. Algorithm 2 shows the GRASP algorithm for solving BQSPP
j.Algorithm 2:
GRASP procedure for solving BQSP P
j.
algorithm
G
R
A
S
P
-
B
Q
S
P
(
I
̅
,
j
)
begin
preprocess;
While  k
≤
Max
i
tr & k
e
y
=
=
1
do
begin
C
G
R
S
-
L
S
(
I
̅
,
I
j
*
,
B
e
s
t
S
o
l
u
t
i
o
n
);
k
=
k
+
1;
end;
I
j
*
=
B
e
s
t
S
o
l
u
t
i
o
n
,
v
j
=
W
(
B
e
s
t
S
o
l
u
t
i
o
n
);
return  I
j
*
,
v
j;
end;Algorithm3 shows the details of the  preprocess  and CGRS-LS procedures. Here W
(
I
j
*
) is defined as W
(
I
j
*
)
=
∑
i
∈
I
j
*
a
i. The procedure starts withk
=
1
,
k
e
y
=
1. The best solution is stored inB
e
s
t
S
o
l
u
t
i
o
n. The steps of the algorithm are repeated for M
a
x
i
t
r iterations. If a new solution is constructed in the construction phase, then k
e
y is set equal to one, the  local search  is performed, and the best solution is updated.Algorithm 3:
Preprocess and CGRS-LS procedures.
procedure  preprocess
begin
Setk
=
1, k
e
y
=
1
,
I
j
*
=
ϕ;
B
e
s
t
S
o
l
u
t
i
o
n
=
ϕ,  W
(
B
e
s
t
S
o
l
u
t
i
o
n
)
=
0;
end;
procedure  C
G
R
S
-
L
S
(
I
̅
,
I
j
*
,
B
e
s
t
S
o
l
u
t
i
o
n
)
begin
C
o
n
s
t
r
u
c
t
G
r
e
e
d
y
R
a
n
d
o
m
S
o
l
u
t
i
o
n
_
B
Q
S
P
(
I
̅
,
I
j
*
);
If
k
e
y
=
=
1  then
L
o
c
a
l
S
e
a
r
c
h
_
B
Q
S
P
(
I
j
*
);
If  W
(
I
j
*
)
>
W
(
B
e
s
t
S
o
l
u
t
i
o
n
)  then
B
e
s
t
S
o
l
u
t
i
o
n
=
I
j
*;
end;
end;
return
I
̅
,
I
j
*
,
B
e
s
t
S
o
l
u
t
i
o
n;
end;Therestricted candidate list (RCL) for our problem includes all demand points that can improve the objective while maintaining the waiting time constraint. If this list is empty, then k
e
y is set equal to zero and no local search is performed; otherwise, a candidate point is randomly selected and k
e
y is set to one, the local search is performed, and the best solution is updated.Algorithm4 shows the procedure for constructing the restricted candidate list. In this procedure, the so-called candidate parameter
α ranges from zero to one. α
=
0 indicates that the points are randomly selected, while α
=
1 yields the greedy selection. S
1 and R
i
t
j are defined as(4.1)
S
1
=
∑
i
∈
I
j
*
∑
t
∈
I
j
*
f
i
h
t
(
1
2
T
ı
𝚥
2
̅
+
τ
j
T
ı
𝚥
̅
)
,
R
i
t
j
=
f
i
h
t
(
1
2
T
ı
𝚥
2
̅
+
τ
j
T
ı
𝚥
̅
)
.Algorithm 4:
MakeRCL_BQSPprocedure.
procedure
M
a
k
e
R
C
L
_
B
Q
S
P
(
I
̅
,
I
j
*
)
begin
SetR
C
L
=
ϕ;
a
max
=
max
{
a
i
:
i
∈
I
̅
∖
I
j
*
,
S
1
+
R
i
i
j
+
∑
t
∈
I
j
*
(
R
i
t
j
+
R
t
i
j
)
≤
τ
j
,
s
t
a
b
i
l
t
y
c
o
n
d
i
t
i
o
n
i
s
m
a
i
n
t
a
i
n
e
d
};
For  i
∈
I
̅
∖
I
j
*  do
If  a
i
≥
α
×
a
max
&
S
1
+
R
i
i
j
+
∑
t
∈
I
j
*
(
R
i
t
j
+
R
t
i
j
)
≤
τ
j
then
R
C
L
=
R
C
L
∪
{
i
}
end;
end;
return
R
C
L;
end;In this algorithmS
1is actually the left hand side of (2.10). If demand point i (i
∈
I
̅
∖
I
j
*) is added to I
j
*, then the left hand side of this equation is increased by R
i
i
j
+
∑
t
∈
I
j
*
(
R
i
t
j
+
R
t
i
j
), so S
1
+
R
i
i
j
+
∑
t
∈
I
j
*
(
R
i
t
j
+
R
t
i
j
)  must be less than τ
j.In thelocal search, we use the 2-exchange neighborhood structure. The exchange between two demand points i
∈
I
j
* and s
∈
I
̅
∖
I
j
*is only possible ifa
s
>
a
i, and, in addition, adding s to I
j
* and deleting i from I
j
* would not violate the constraints. The procedure for local search is shown in Algorithm 5.Algorithm 5:
LocalSearch_BQSPprocedure.
procedure  L
o
c
a
l
S
e
a
r
c
h
_
B
Q
S
P
(
I
j
*
)
begin
Setk
e
y
=
1;
While  k
e
y
=
=
1  do
begin
k
e
y
=
0;
For all i
∈
I
j
*
do
s
max
=
i
,
a
max
=
a
i;
For all s
∈
I
̅
∖
I
j
*
do
If   (
S
1
-
(
R
i
i
j
+
∑
t
∈
I
j
*
,
t
≠
i
(
R
i
t
j
+
R
t
i
j
)
)
+
(
R
s
s
j
+
∑
t
∈
I
j
*
(
R
t
s
j
+
R
s
t
j
)
)
≤
τ
j
)
&
(
a
s
>
a
i
)
&
s
t
a
b
i
l
i
t
y
c
o
n
d
i
t
i
o
n
i
s
m
a
i
n
t
a
i
n
e
d
then
If
a
s
>
a
max  then
a
max
=
a
s
,
s
max
=
s;
end;
end;
end;
If
s
max
≠
i  then
r
=
s
max
,
k
e
y
=
1;
S
1
=
S
1
-
(
R
i
i
j
+
∑
t
∈
I
j
*
,
t
≠
i
(
R
i
t
j
+
R
t
i
j
)
)
+
(
R
r
r
j
+
∑
t
∈
I
j
*
(
R
t
r
j
+
R
r
t
j
)
);
I
j
*
=
I
j
*
∪
{
r
}
∖
{
i
}
,
I
̅
=
I
̅
∪
{
i
}
∖
{
r
};
end;
end;
end;
return  I
j
*;
end;Ifs
∈
I
̅
∖
I
j
*is added to and i
∈
I
j
* is deleted from I
j
*, then S
1 is increased by R
s
s
j
+
∑
t
∈
I
j
*
(
R
t
s
j
+
R
s
t
j
) and decreased by R
i
i
j
+
∑
t
∈
I
j
*
,
t
≠
i
(
R
i
t
j
+
R
t
i
j
). In the above procedure, i
∈
I
j
* is replaced by a demand point r(r
∈
I
̅
∖
I
j
*) which has maximum population and would not violate the constraints.Finally, in construction and local search phases, addingi
∈
I
̅ to I
j
* is possible only if the stability condition is not violated.


## 5. GRASP for ProblemP

Our procedure for solvingP is similar to that proposed for the maximal covering problem by Resende [31]). The main difference is in selection of the greedy function for construction of the restricted candidate list. The construction of the restricted candidate list is illustrated in Algorithm 6.Algorithm 6:
MackRCL‒ MainProblemprocedure.
procedure
MackRCL‒ MainProblem
(
J
*
,
I
̅
)
begin
setR
C
L
_
M
P
=
ϕ;
For all j
∈
J
∖
J
*  do
[
I
j
*
,
v
j
]
←
G
R
A
S
P
_
B
Q
S
P
(
I
̅
,
j
);
end;
v
max
=
ma
x
{
v
j
:
j
∈
J
∖
J
*
};
R
C
L
_
M
P
=
{
j
∣
j
∈
J
∖
J
*
,
v
j
≥
α
×
v
max
};
return  R
C
L
_
M
P;
end;We use the GRASP procedure to solve the subproblemP
j for any candidate facilityj
(
j
∈
J
∖
J
*
), as indicated in line 5.There are few differences between our implementation of GRASP and that of Silva and Serra [18] for the M/M/1 case with priorities. In Silva and Serra [18], the allocation is based on a set D
i
j which is constructed for each candidate center j. D
i
j contains the indices of all demand points i for which d
(
i
,
j
) is less thanR. Entries in D
i
j are ordered according to their distances from j. Demand points from D
i
j are assigned to j as long as the waiting time constraint is not violated. Another difference is in the selection of the greedy function. In Silva and Serra [18], the greedy function is the total costumer arrival rate, while ours is the amount of increase in the objective function. Finally their local search is a comprehensive search over all feasible solutions which improves the objective, while we use a 2-exchange neighborhood search.


## 6. Computational Results

The queueing maximal covering location-allocation problem with anM/G/1 is considerably more difficult to solve than the one with an M/M/1 system, since the waiting time (quality of service) constraints are quadratic with possibly indefinite coefficient matrices. Hence, even small-sized problems cannot be solved with the state-of-the-art software packages of today. Here we have tried to solve some randomly generated test problems by the proposed algorithms. We first considered the solution of problems with heuristic algorithm where subproblems P
j were solved with GRASP. Then we used the GRASP to solve the entire model P. All calculations were performed on a Pentium IV processor with 2.80 GHz and 2.50 GB of RAM.The number of points in the instances ranged from 20 to 200. In these instances, the number of candidate locations,n, was taken to be equal to the number of points, m. We assume that each demand point is also a potential server location, and the distances are considered to be Euclidean.f
i and τ
j, namely, the daily call rate and the average time limit, were taken to be 0.005 times the population and 12.75 minutes for each candidate center. The covering radius, R, was taken to be 1.5 miles. Parameters α and β  were set to 0.85 and 2; respectively, and v was set to 5 (miles/hour). Z
ı
̅ is assumed to be the same for all demand points and was taken to be 0.5 (hour). The maximum number of iterations was set to 20. Each problem was run 5 times. Percent of coverage listed are the averages. Tables 1 and 2 show the results for instances solved with the suggested heuristic and with the GRASP procedure, respectively.Table 1
Computational results for test problems solved with the heuristic procedure.
Number ofdemand points
Percent of population covered
Least number of
Average CPU
p
=
1
p
=
3
p
=
5
p
=
10
p
=
15
facilities needed
time for 100%
for 100% pop.   coverage
pop.  coverage     (seconds)
20
77.05
98.10
—
—
—
4
0.79
30
70.74
95.24
100
—
—
5
2.30
50
47.33
72.57
85.52
—
—
9
6.58
100
34.22
58.90
74.22
94.18
100
15
55.97
150
26.23
48.34
66.34
89.77
98.46
18
192.85
200
22.37
43.46
60.64
86.36
95.74
22
468.40Table 2
Computational results for test problems solved with GRASP.
Number ofdemand points
Percent of population covered
Least number of
Average CPU
p
=
1
p
=
3
p
=
5
p
=
10
p
=
15
facilities needed
time for 100%
for 100% pop.   coverage
pop.  coverage     (seconds)
20
77.05
100
—
—
—
3
24.36
30
70.74
98.09
100
—
—
5
63.45
50
47.33
74.85
87.08
—
—
9
194.24
100
34.22
60.05
75.20
95.77
100
15
1270.66
150
26.23
51.37
68.13
91.16
98.79
18
4205.43
200
22.37
45.38
62.17
87.31
96.61
21
9905.76Comparison of the results for the two approaches reveals that solving the subproblems with GRASP takes far less time than does solving the entire model. The CPU time increases dramatically for the second algorithm as the number of points increases, while the coverage does not improve substantially. For example, as indicated in Tables1 and 2, for the 200 point test problem, the first approach provides a solution with 100% coverage by selecting p
=
22 in 468.40 seconds, while the second approach gives a solution with 100% coverage with p
=
21 in 9905.76 seconds.Finally, in order to have some idea about our solution methods, we tried to solve some small instances by enumerating all possible outcomes. The results for 5 and 10 points with 1 and 2 centers are shown in Table3.Table 3
Comparison of the results for enumerative method with the heuristic procedure and GRASP.
m
=
n
=
5, p
=
1
m
=
n
=
10, p
=
1
m
=
n
=
10, p
=
2
Enumeration method
Percent of population covered
100
90.47
100
Population covered
2630
3230
3570
Selected center(s)
1 or 2 or 4 or 5
2
2,5
Heuristic   procedure
Percent of population covered
100
90.47
100
Population covered
2630
3230
3570
Selected center(s)
1 or 2 or 4 or 5
2
2,1
GRASP
Percent of population covered
100
90.47
100
Population covered
2630
3230
3570
Selected center(s)
1 or 2 or 4 or 5
2
5,10For these limited instances, there were no discrepancies between the solutions. However, this of course is no proof that the algorithm always obtains an optimal solution, but we hope and expect it to at least obtain a rather good solution.


## 7. Conclusion

In this paper we considered the queueing maximal covering problem with anM/G/1 queueing system. A quadratically constrained integer programming model was presented for the problem. To solve the problem, we first considered a heuristic algorithm based on decomposing the problem into smaller knapsack-type subproblems. Then we solved the binary quadratic subproblems with GRASP. We also used GRASP to solve the entire model. Our limited computational results showed that using the proposed heuristic algorithm provide better solutions.



---

*Source: 605629-2012-01-29.xml*