The Capacitated Location-Allocation Problem in the Presence of <i>k</i> Connections

doi:10.4236/am.2011.28130

Paper Menu >>

Journal Menu >>

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

E-mail: s_saber2004@yahoo.co m, m.a.aref @ u stmb.ac.ir, [email protected]

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





2. Problem Description

Let be set of existing facilities in the

feasible region. Suppose



1, ,i 



iii

ab



1, 

be the ith exist-

ing facility coordinates. Let be set of

new facility in the feasible region. Suppose



J,j





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

2







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



1, ,k

is allowed only at the K connections (i.e.,

Pk, ), where K





kkk

Prs

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

Piji j

Lmmm

pijPikPkj ijij

kmm mm

dXXX X

dXX dXPdPXXXXX

iIjJm



















 







(1)

It means that while both i

and

are located in the

same half-plane, the p-norm distance is computed and

while i

and

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:





,min,, ,

1, ,;1, ,;1, ,2

ji jiij

Lmmm

ij ikik jj ijij

kmm mm

xa ybXX

dXX arbrxyXXXX

iIjJm











 









 



 

   







(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

1,1, ,



 

 (3)

,1,,

iij j

wz CjJ













0,1,1, ,,1, ,

ziIjJ



   (4)





where





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.,



min ,

IJ LB

iiji j

wz dXX







1,ifexisting facilityis assignedto newfacility,1, ,,1, ,.

0, otherwise,



  



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

t

t1

ijk

u0

ijk



and

if the y-coordinate of the j-th new facility is

greater than

g



), otherwise . Assume

0

qi



, else . 0

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

IJ K

iiji kikj

ij k

jijk ijijijij

wza rbrx

yut axbyt



 





















 

 





  (5)

Subject to:

1,1, ,



 

I

,

,1,

iij j

wz CjJ







1,1,,,1, ,

ijk

uiIj



  

 (6)

jjj j

ygg y





(7)

,1,,; 1,,

iji j

tqgi IjJ (8)



,,,0,1,1,,;1,,,1,,

j ijijijk

tzui Ij JkK

(9)

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



 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

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