Applied Mathematics, 2011, 2, 947-952
doi:10.4236/am.2011.28130 Published Online August 2011 (http://www.SciRP.org/journal/am)
The Capacitated Location-Allocation Problem in the
Presence of k Connections
Saber Shiripour, Mehdi Amiri-Aref, Iraj Mahdavi
Department of In d ust ri al Engineering, Mazandaran University of Science & Technology, Babol, Iran
Received June 13, 2011; revised July 2, 2011; accepted July 9, 2011
Abstract
We consider a capacitated location-allocation problem in the presence of k connections on the horizontal line
barrier. The objective is to locate a set of new facilities among a set of existing facilities and to allocate an
optimal number of existing facilities to each new facility in order to satisfy their demands such that the
summation of the weighted rectilinear barrier distances from new facilities to existing facilities is minimized.
The proposed problem is designed as a mixed-integer nonlinear programming model. To show the efficiency
of the model, a numerical example is provided. It is worth noting that the global optimal solution is obtained.
Keywords: Capacitated Location-Allocation Problem, Line Barrier, Mixed Integer Nonlinear Programming
1. Introduction
Facility location problems have been extensively inves-
tigated in operations research (OR) and theoretical com-
puter science literature (Cornu ejols et al. [1] and Shmoys
[2]). For the first time, facility location problem is intro-
duced by Weber [3]. He introduced a classical Weber
problem in which locating a warehouse is considered so
that the distance traveled between the warehouse and its
customers is minimized. The American Mathematical
Society (AMS) even generated specific codes for loca-
tion problems (90B80 for discrete location and assign-
ment, and 90B85 for continuous location). Location area
can be divided into three branches: location problems,
allocation problems and location-allocation problems.
We used location-allocation problems in this work. Lo-
cation-allocation (LA) problem is to locate a set of new
facilities such that the total transportation cost from fa-
cilities to customers is minimized and an op timal number
of customers have to be allocated in an area of interest in
order to satisfy the customer demands. Generally, there
are some aspects affecting formulation this problem such
as: either each customer is serviced by only one new
facility or more, demand of customers are deterministic
or stochastic and facilities are capacitated or uncapaci-
tated. The models available for this problem are divided
into two main sections: the general models (Cooper [4])
and developed models (Zhou and Liu [5]).
In many of location problems, we have to consider
some restrictions in finding locations of new facilities so
that these restrictions refuse establishment of new facili-
ties in some specified regions. In general, the restricted
planar location problems are categorized in three catego-
ries. The first category is called forbidden regions,
namely, in these regions the locating of facility is not
permitted but passing through is allowed (e.g., rods or
forests). In Hamacher and Nickel [6] an extensive over-
view of the location problems with forbidden regions is
provided. The second category is consist of regions
where placement of a facility is prohibited but travelling
through is possible with a penalty cost (e.g., lakes that
can be crossed only using a jolly boat). These regions are
called congested regions. The third group considers bar-
rier regions, for which both placement a facility and
passing through are forbidden (e.g., lakes, big machines
and conveyor belts in a plant). Note that, in some cases
travelling on the barrier regions boundaries is allowed.
The special case of almost linear barriers in the plane
that have only a finite number of passages is frequently
encountered in practice. Line barriers with passages
may be used urban design for rivers, border lines,
highways, mountain ranges, or, on a smaller scale, con-
veyer belts in industrial plants. In all these examples
trespassing is allowed only through a finite number of
passag es .
Barrier regions were first specified to location model-
ing by Katz and Cooper [7], who consider Weber prob-
lems with the Euclidean distance and a circular barrier.

948 S. SHIRIPOUR ET AL.
Consideration of all barrier sets as polyhedral permits
construction of a visibility graph that can be applied to
efficiently compute barrier distances. They showed that
the objective function of the problem was non-convex
and suggested a heuristic algorithm for solving this pro-
blem that is based on a sequential unconstrained mini-
mization technique (SUMT) for nonlinear programming
problems. This heuristic algorithm did not guarantee
achievement of a global optimum solution. The problem
was further investigated in Klamroth [8] and it was de-
picted that in the case of a single circular barrier, the
feasible set can be subd ivided into a polynomial nu mber,
O(N2), of sub-regions, on every convex subset of which
the Weber objective function is convex. N is the number
of existing facilities on the plane so that, when N in-
creases, construction of these convex subsets becomes
cumbersome and hence is not desired. To overcome this
difficulty, Bischoff and Klamroth [9] suggested a genetic
algorithm (GA) and Weiszfeld technique-based solution
to the problem.
In the case of line barriers, Klamroth [10] considered a
limited number of passages with any distance measure,
separated the plane into two sub-planes and showed that
an optimal solution of the non-convex barrier problem
can be attained by solving a polynomial number of re-
lated unconstrained sub-problems. Klamroth and Wiecek
[11] generalized this result to multi-criteria problems.
Huang et al. [12] find the optimal location of k connec-
tions in the plane for uncapacitated and capacitated loca-
tion problems. Huang et al. [13] considered the same
problem and find the optimum capacity of each connec-
tion. Huang et al. [14] discussed the same problem sub-
ject to congestion.
Recently, Canbolat and Wesolowsky [15] presented a
single facility location problem in the presence of a line
barrier that is distributed randomly on a given horizontal
route on the plane. The goal is to locate a new facility
such that the sum of the expected rectilinear distances
from the facility to the demand points is minimized.
They proposed a solution algorithm in which the feasible
region is divided into two half-planes and to obtain a
global optimum solution.
For the first time, location-allocation problem is pre-
sented by Cooper [4] who introduced a general model of
location-allocation with two new facilities and seven
demand points. He showed that the objective function is
neither concave nor convex and may attain several local
minima. Later on, Badri [16] provided network loca-
tion-allocation problem and many models for this prob-
lem. In a study Brady and Rosenthal [17] provided in-
teractive graphics to solve facility location problems with
a center objective function involving single as well as
multiple new facilities in the presence of forbidden re-
gion having any arbitrary configuration. Batta and Leifer
[18] discussed multi-facility Weber problems with Man-
hattan metric and give lower and upper bounds as well as
the relative accuracy of solutions for problems with and
without barriers. A network location problem where de-
mand produced at a node is distance-dependent is ana-
lyzed by Berman and Drezner [19]. The objective is to
find a given number of facilities on network so that the
facilities can serve no more than a given number of cus-
tomers. Berman et al. [20] studied the problem of locat-
ing a set of service facilities on a network while the de-
mand for service is stochastic and congestion may occur
at the facilities while considering two potential sources
of lost demand like increasing long queues and travel
distance. In this context, several integer programming
formulations and heuristic approaches are investigated
by them. For the same work, Berman et al. [21] proposed
heuristic-based solution procedures to maximize the ex-
pected number of captured demand when customer de-
mands are stochastic and congestion exists at facilities.
Also, Zhou and Liu [22] presented models for capaci-
tated location—allocation problem with fuzzy demands.
Recently, a multi-dimensional mixed-integer optimiza-
tion problem for the location-allocation problem with the
Euclidean distance in the presence of polyhedral barriers
is presented by Bischoff et al. [23]. They introduced two
different alternate location and allocation heuristics and
used genetic algorithm in the location step of both algo-
rithms. Iyigun and Ben-Israel [24] proposed an iterative
method for the K facilities location problem. This me-
thod relaxes the problem applying probabilistic assign-
ments, depending on the distances to the facilities, so that
the probabilities together with the facility locations are
updated at each iteration.
In this paper we focus on the capacitated location-al-
location problem in the presence of k connections in the
rectangular space (p = 1) and present an MINLP model
for the problem. In this problem, it is assumed that new
facilities are capacitated, there is no relationship between
the new facilities, the solution space is continues and
each the existing facility can be serviced by only one
new facility. So, in addition to finding optimum locatio ns
for the new facilities, the optimum assignments of exist-
ing facilities to any new facility should be searched.
The rest of this work is organized as follows. In next
section, the problem structure and definitions are inves-
tigated. In Section 3, we introduce a mathematical pro-
gramming model for the capacitated location-allocation
problem in the presence of k connection with the rectan-
gular distance. Section 4 contains the computational re-
sults where we evaluate the performance of the proposed
model. Conclusions and scope for future studies are pro-
vided in the last section.

S. SHIRIPOUR ET AL.
949

I

2. Problem Description
Let be set of existing facilities in the
feasible region. Suppose

1, ,i 

,
iii
X
ab

1, 
be the ith exist-
ing facility coordinates. Let be set of
new facility in the feasible region. Suppose

J,j


,
j
jj
X
xy
be the jth new facility coordinates in the plane, (see Fig-
ure 1). Let wi be the demand of the ith point and Cj be
the maximum capacity the jth new facility. The feasible
region is defined as the union of the two closed 
Figure 1. Demand points wi th 2 conne ctions.
X are located in the same half-plane we have


,
pij
dXX ,
half-planes and on both sides. Let
1
2 


,
B
L
p
ij
dXX without any restrictions. Else the shortest traveled dis-
tance through K connections should be considered. Al-
though, distance metric lp, p=[1,) is applicable, the
rectilinear distance, p = 1, is considered for this problem.
be the p-norm barrier distance between Xi and Xj in the
presence of a horizontal line barrier which trespassing
through
L

1, ,k
is allowed only at the K connections (i.e.,
Pk, ), where K


,
kkk
Prs
,
k
s
is the coordinates
of the connections. Since the connections are located on
a horizontal line, we set


If Xi and 1,,.k
The p-norm shortest path from each new facility to the
existing facilities through the connections is as follo ws.
K



 

''
,,
,min ,,,,,
1, ,;1, ,;1,...,2
mm
Piji j
Lmmm
pijPikPkj ijij
kmm mm
dXXX X
dXX dXPdPXXXXX
iIjJm
m










 



(1)
It means that while both i
X
and
j
X
are located in the
same half-plane, the p-norm distance is computed and
while i
X
and
j
X
are located in the opposite half-
plane, the shortest path should be calculated. In this
case, the shortest permitted path should be considered
from the new facility to the existing facilities through
all passages. So, considering p = 1 (i.e., rectilinear dis-
tance), we have:


''
1
,
,min,, ,
1, ,;1, ,;1, ,2
mm
ji jiij
Lmmm
ij ikik jj ijij
kmm mm
xa ybXX
dXX arbrxyXXXX
iIjJm



m


 





 


 
   



(2)
3. Proposed Mathematical Model
In this section, we introduce a nonlinear mathematical
model for capacitated location-allocation problem in the
presence of k connections on the line barrier. Generally,
for the capacitated location-allocation problem with bar-
rier, the problem of locating a set of J new facilities, Xj,
, with respect to a finite set of I existing facili-
ties, to minimize the total weighted barrier distances can
be stated as follows:
1, ,jJ
I
1
1,1, ,
J
ij
j
zi


 
 (3)
1
,1,,
I
iij j
i
wz CjJ






0,1,1, ,,1, ,
ij
ziIjJ

   (4)
,
j
X
j


where


1,
Bij
dXX is the rectilinear barrier distance
between the i-th demand point and the j-th new facility
and the binary variables stand for the allocation of if
existing facility i to new facility j, i.e.,
ij
z

1
11
min ,
IJ LB
iiji j
ij
wz dXX



1,ifexisting facilityis assignedto newfacility,1, ,,1, ,.
0, otherwise,
ij
ij
zi

  

IjJ

S. SHIRIPOUR ET AL.
950
In this model, constraints (3) assure that each demand
point can be served only by one new facility. Constraints
(4) guarantee that the each new facility cannot serve
more than their correspondence capacity.
Here, three binary variables and a binary parameter are
introduced. Let if the existing facility i and the
new facility j are located in different half-planes and else
, if the existing facility i be served to the
new facility j through passage k else
1
ij
t
0
ij
t1
ijk
u0
ijk
u

and
if the y-coordinate of the j-th new facility is
greater than
1
j
g

(j y

), otherwise . Assume
if
0
j
g
1
i
qi b

, else . 0
i
q
Now, with respect to the parameter and variables in-
troduced, the capacitated location-allocation problem in
the presence of k connections on the line barrier can be
written as follows:

11 1
min
1
IJ K
iiji kikj
ij k
jijk ijijijij
wza rbrx
yut axbyt


 











 
 



  (5)
Subject to:
1
1,1, ,
J
ij
j
zi

 
I
,
J
1
,1,
I
iij j
i
wz CjJ



1
1,1,,,1, ,
K
ijk
k
uiIj

  
 (6)
2
jjj j
ygg y

 (7)
,1,,; 1,,
iji j
tqgi IjJ (8)

,,,0,1,1,,;1,,,1,,
j ijijijk
g
tzui Ij JkK
(9)
,
jj
xy0 (10)
The objective function (5) consists of two parts. The
first part of the objective function considers the shortest
path from each existing facility to each the new facility
through the passages if they are located in the different
halfplanes. The second part of the objective function
considers the regular rectilinear metric while the existing
and new facilities are located in the one halfplane. This
expression minimizes the total weighted traveled barrier
distance from each new facility to the allocated existing
facilities. Constraints (6) assure that the each new facility
can serve every existing facility through only one con-
nection. Constraints (7) determine that whether the new
facility j is located in the upper-plane or not. Constraints
(8) determine that whether the existing facility and the
new facility, both are located in the same half-planes or
not. Constraints (9) and constraints (10), respectively,
show the binary and non-negative variables. Because of
the complexity of the proposed mathematical program-
ming model in large size problems, a numerical example
in small size is presented.
4. Numerical Example
In this section we assess the performance of the proposed
model by providing a numerical example. In this exam-
ple, we will find the optimum locations for establishment
of two new facilities and the optimum assignments of
existing facilities to these new facilities in the presence
of a line barrier with two connections. This example
consists of 8 existing facilities on the plane. The x and y
coordinates of existing facilities are provided according
to the sample data by Canbolat and Wesolowsky [15].
However, they considered the problem in the presence of
a probabilistic line barrier. The coordinates of the exist-
ing facilities and values of demands of the existing fa-
cilities, ,1,,8
i
wi

 are showed in Table 1. These
values are chosen in the range [1-10]. The coordinates of
the connections are provided in Table 2. The proposed
model has been implemented in the LINGO 9.0 software
package using global solver.
To achieve a better understanding of the proposed
model, the optimum locations found for two new facili-
ties in two cases of without and with barrier are reported
in Table 3. The capacities of new facilities 1 and 2 are
considered 16 and 30 respectively. The obtained results
state that the presence of line barrier with connections
was effective on the optimum locations of both new fa-
cilities 1 and 2. Also the value of objective function in
case of with barrier is more than the case of without bar-
rier, as we expected. This addition cost is due to the fact
that the presence of line barrier can be effective on
weighted rectilinear distances of mutual points on the
Table 1. Existing facility locations and their demands.
Existing
facilitie Coordinates wi
1 (4,2) 10
2 (12,2) 3
3 (5,4) 7
4 (10,4.5) 2
5 (7,8) 5
6 (4,9) 2
7 (12,9.5) 8
8 (7,11) 7
Table 2. Coordinates of the connections
Connections Coordinates
1 (6,6)
2 (10,6)

S. SHIRIPOUR ET AL.
951
Table 3. New facility locations.
Facility 1 Facility 2
*
1
x
*
1
y *
2
x
*
2
y
Objective
value
without
barrier 12 9.5 5 4 155.5
with
barrier 4 2 7 9.5
158.5
plane and so on the optimum locations of the new facili-
ties and optimum allocations of existing facilities to new
facilities. It is worth noting that LINGO software re-
ceived to the global optimum solutions. It is obvious that
by increasing number of new facilities, the objective
values of problem will be decreased. For the case of 8
new facilities (I = J = 8) the objective function value will
be zero because in this case every existing facility will be
allocated to unique new facility. So, summation of the
weighted rectilinear barrier distances of between the new
facilities and existing facilities will be zero.
In Figure 2 the example problem together with the
optimum locations and corresponding allocation clusters
in the case of two new facilities for two situations of
without and with barrier (cases (a) and (b)) are depicted.
It can be observed that in case (a), the new facility 1 ser-
vices the existing facilities 7 and 8 whereas in case b this
facility services the existing facilities 1, 2 and 4. Also,
new facility 2 in case a, services the existing facilities 1
to 6 whereas in case b services the existing facilities 3, 5,
6, 7 and 8. So, in the mentioned location-allocation prob-
lem, the presence of the barrier not only can be effect on
the total cost but can be effect on the optimum locations
of some new facilities and the relevant optimum alloca-
tions.
In this example, when n = 1 and 8, two special cases
occur. In the first case (n = 1), every existing facility will
be allocated to the same new facility and in the second
case (n = 8), every existing facility will be allocated to a
different one and so the objective value will be zero.
5. Conclusions
We proposed a mixed-integer nonlinear programming
model for the location-allocation problem in the pres-
ence of a line barrier with K connections. Our aim was to
find the optimal locations of a given set of new facilities
and the optimal allocations of existing facilities to these
new facilities for minimizing the total weighted traveled
rectilinear barrier distances from the new facilities to the
existing. To show validation of the proposed model, a
numerical example was provided. We solved the exam-
ple problem using LINGO 9.0 software that led to the
global optimum solutions. The results illustrated that the
presence of a line barrier with two connections on the
line barrier not only affected on the objective value of
the problem, but also affected on the optimum locations
and allocations of the new facilities in compared with
case of without barrier.
For future research, the other distance functions such
as the Euclidean distance function can be considered.
Megiddo and Supowit [25] demonstrated the multi We-
ber problems are NP-hard and also Bischoff et al. [23]
stated that the multi-Weber problems with barrier which
reduces to the multi-Weber problems if no barriers are
present is also NP-hard. So, designing some heuristic or
meta-heuristic methods to solve the proposed model in
the large scales are another extension for this problem.
(a) (b)
Figure 2. The optimum locations and the corresponding allocation clusters for two new facilities. (a): Without barrier; (b):
With barrier.

S. SHIRIPOUR ET AL.
952
6. References
[1] G. Cornuejols, G. L. Nemhauser and L. A. Wolsey, “The
Uncapacitated Facility Location Problem,” In: P. Mir-
chandani and R. Francis, Eds., Discrete Location Theory,
John Wiley and Sons, New York, 1990, pp. 119-171.
[2] D. Shmoys, “Approximation Algorithms for Facility Lo-
cation Problems,” Proceedings of 3rd International
Workshop of Approximation Algorithms for Combinato-
rial Optimization, Vol. 1913, No. 1, 2000, pp. 27-33.
[3] A. Weber, “Über den Standort der Industrien,” Tübingen
Theory of the Location of Industries, University of Chi-
cago Press, 1909.
[4] L. Cooper, “Location-Allocation Problems,” Operations
Research, Vol. 11, No. 3, 1963, pp. 331-343.
doi:10.1287/opre.11.3.331
[5] J. Zhou and B. Liu, “New Stochastic Models for Capaci-
tated Location-Allocation Problem,” Computers & In-
dustrial Engineering, Vol. 45, No. 1, 2003, pp. 111-125.
doi:10.1016/S0360-8352(03)00021-4
[6] H. W. Hamacher and S. Nickel, “Restricted Planar Loca-
tion-Problems and Applications,” Naval Research Logis-
tics, Vol. 42, No. 6, 1995, pp. 967-992.
doi:10.1002/1520-6750(199509)42:6<967::AID-NAV322
0420608>3.0.CO;2-X
[7] I. N. Katz and L. Cooper, “Formulation and the Case of
Euclidean Distance with One Forbidden Circle,” Euro-
pean Journal of Operational Research, Vol. 6, No. 1,
1981, pp. 166-173. doi:10.1016/0377-2217(81)90203-4
[8] K. Klamroth, “Algebraic Properties of Location Problems
with One Circular Barrier,” European Journal of Opera-
tional Research,” Vol. 154, No. 1, 2004, pp. 20-35.
doi:10.1016/S0377-2217(02)00800-7
[9] M. Bischoff and K. Klamroth, “An Efficient Solution
Method for Weber Problems with Barriers Based on Ge-
netic Algorithms,” European Journal of Operational Re-
search, Vol. 177, No. 1, 2007, pp. 22-41.
doi:10.1016/j.ejor.2005.10.061
[10] K. Klamroth, “Planar Weber Location Problems with
Line Barriers,” Optimization, Vol. 49, No. 5-6, 2001, pp.
517-527. doi:10.1080/02331930108844547
[11] K. Klamroth and M. M. Wiecek, “A Bi-Objective Median
Location Problem with a Line Barrier,” Operations Re-
search, Vol. 50, No. 4, 2002, pp. 670-679.
doi:10.1287/opre.50.4.670.2857
[12] S. Huang, R. Batta, K. Klamroth and R. Nagi, “The K-
Connection Location Problem in a Plane,” Annals of Op-
erations Research, Vol. 136, No. 1, 2005, pp. 193-209.
doi:10.1007/s10479-005-2045-1
[13] S. Huang, R. Batta and R. Nagi, “Variable Capacity Siz-
ing and Selection of Connections in a Facility Layout,”
IIE Transactions, Vol. 35, No. 1, 2003, pp. 49-59.
doi:10.1080/07408170304434
[14] S. Huang, R. Batta and R. Nagi, “Distribution Network
Design: Selection and Sizing of Congested Connections,”
Naval Research Logistics, Vol. 52, No. 8, 2005, pp. 701-
712. doi:10.1002/nav.20106
[15] M. S. Canbolat and G. O. Wesolowsky, “The Rectilinear
Distance Weber Problem in the Presence of a Probabilis-
tic Line Barrier,” European Journal of Operational Re-
search, Vol. 202, No. 1, 2010, pp. 114-121.
doi:10.1016/j.ejor.2009.04.023
[16] M. A. Badri, “Combining the Analytic Hierarchy Process
and Goal Programming for Global Facility Location-Al-
location Problem,” International Journal of Production
Economic, Vol. 62, No. 1, 1999, pp. 237-248.
doi:10.1016/S0925-5273(98)00249-7
[17] S. D. Brady and R. E. Rosenthal, “Interactive Graphical
Solutions of Constrained Minimax Location Problems,”
IIE Transactions, Vol. 12, No, 1, 1980, pp. 241-248.
doi:10.1080/05695558008974512
[18] R. Batta and L. A. Leifer, “On the Accuracy of Demand
Point Solutions to the Planar, Manhattan Metric, p-Me-
dian Problem, with and without Barrier to Travel,” Com-
puters and Operations Research, Vol. 15, No. 1, 1988, pp.
253-262. doi:10.1016/0305-0548(88)90038-X
[19] O. Berman and Z. Drezner, “Location of Congested Ca-
pacitated Facilities with Distance-Sensitive Demand,” IIE
Transactions, Vol. 38, No. 3, 2006, pp. 213-221.
doi:10.1080/07408170500288190
[20] O. Berman, D. Krass and J. Wang, “Locating Service
Facilities to Reduce Lost Demand,” IIE Transactions,
Vol. 38, No. 11, 2006, pp. 933-946.
doi:10.1080/07408170600856722
[21] O. Berman, R. Huang, S. Kim and B. C. Menezes, “Lo-
cating Capacitated Facilities to Maximize Captured De-
mand,” IIE Transactions, Vol. 39, No. 11, 2007, pp.
1015-1029. doi:10.1080/07408170601142650
[22] J. Zhou and B. Liu, “Modeling Capacitated Location-
Allocation Problem with Fuzzy Demands,” Computers &
Industrial Engineering, Vol. 53, No. 3, 2007, pp. 454-468.
doi:10.1016/j.cie.2006.06.019
[23] M. Bischoff, T. Fleischmann and K. Klamroth, “The
Multi-Facility Location-Allocation Problem with Polyhe-
dral Barriers,” Computers and Operations Research, Vol.
36, No. 5, 2009, pp. 1376-1392.
doi:10.1016/j.cor.2008.02.014
[24] C. Iyigun and A. Ben-Israel, “A Generalized Weiszfeld
method for the Multi-Facility Location Problem,” Opera-
tions Research Letters, Vol. 38, No. 1, 2010, pp. 207-214.
doi:10.1016/j.orl.2009.11.005
[25] N. Megiddo and K. J. Supowit, “On the Complexity of
Some Common Geometric Location Problems,” SIAM
Journal on Computing, Vol. 13, No. 1, 1984, pp. 182-196.
doi:10.1137/0213014