Ann Ope Res (2014) 222:175–195
DOI 10.1007/s10479-013-1445-x
Single- acili y hu loca ion p oblems on ne wo ks
Ra ael Blanque o ·Emilio Ca izosa ·
Amaya Nogales-Gómez ·F ank Plas ia
Published online: 17 Sep embe 2013
© Sp inge Science+Business Media New Yo k 2013
Abs ac Hu loca ion p oblems ha e been ex ensi ely analyzed wi hin he ield o com-
pe i i e con inuous loca ion.
In his wo k, wo Hu loca ion models on ne wo ks a e add essed, by conside ing ha
use s go di ec ly o he acili y o hey isi he acili y in hei way o a des ina ion.
Since he p oblems a e mul imodal, a b anch and bound algo i hm is p oposed, in which
wo di e en bounding s a egies, based on In e al Analysis and DC op imiza ion, a e used
and compa ed. Compu a ional esul s a e gi en o he wo bounding p ocedu es, showing
ha p oblems o a he ealis ic size can be sol ed in easonable ime.
Keywo ds Hu loca ion models ·Loca ion on ne wo ks ·DC op imiza ion ·In e al
analysis
1 In oduc ion
In his pape we add ess wo compe i i e loca ion models (Blanque o and Ca izosa 2009a;
D ezne and D ezne 2004; Fe nández e al. 2007;Hu 1964,1966;Plas ia2001)ona
This wo k has been pa ially suppo ed by IMUS (Ma hema ics Ins i u e o Uni e si y o Se ille) and by
p ojec s MTM2012-36163, Minis e io de Economía y Compe i i idad, Spain, P11FQM7603,
P10TIC6064 and FQM-329, Jun a de Andalucía, Spain, all wi h EU ERF Funds.
R. Blanque o ·E. Ca izosa ·A. Nogales-Gómez (B)
Depa amen o de Es adís ica e In es igación Ope a i a Facul ad de Ma emá icas,
Uni e sidad de Se illa, Se ille, Spain
e-mail: [email p o ec ed]
R. Blanque o
e-mail: [email p o ec ed]
E. Ca izosa
e-mail: [email p o ec ed]
F. Plas ia
MOSI, V ije Uni e si ei B ussel, B ussels, Belgium
e-mail: ank.plas ia@ ub.ac.be
176 Ann Ope Res (2014) 222:175–195
ne wo k (Dea ing and Shie 1983; Labbé e al. 1995). Le N=(V,E) beane wo k,wi h
node se Vand edge se E. The leng h o he edge e∈Eis gi en, and i is deno ed by le.The
dis ance be ween wo nodes ai,ajis calcula ed as he sho es pa h (Labbé e al. 1995) om
ai o aj. Fo each e∈E, wi h end nodes ai,aj, we iden i y each x∈[0,le]wi h he poin
in he edge ea dis ance x om aiand dis ance le−x om aj. This way, we ob ain ha ,
o any e ex ak∈V, he dis ance d(x,ak) om x o akis, as a unc ion o x,aconca e
piecewise linea unc ion, gi en by:
d(x, ak)=min iak(x), jak(x)
iak(x) =x+d(ai,ak)
jak(x) =(le−x)+d(aj,ak)
(1)
We e e he eade o Labbé e al. (1995) o a comp ehensi e in oduc ion o loca ion
models on ne wo ks.
The emainde o his pape is s uc u ed as ollows. Two di e en loca ion models on
ne wo ks a e conside ed. The i s model (Sec . 2) is he classic Hu loca ion model, as
add essedinBe mane al.(2011), in which cus ome s pe cei e he acili y a ac i eness in
e ms o hei dis ance o he acili y, while he second model (Sec . 3) is new, called he Hu
o igin-des ina ion (OD) ip model. In he OD ip model he acili y a ac ion is a unc ion
o he leng h o he sho es pa h om he o igin o he des ina ion h ough he acili y. In
Sec . 4a b anch and bound algo i hm is designed o sol e bo h p oblems and wo di e en
p ocedu es o ob ain bounds a e p esen ed.
Compu a ional esul s a e gi en in Sec . 5, compa ing he wo bounding s a egies imple-
men ed. Some concluding ema ks a e p esen ed in Sec . 6.
2 Hu loca ion model
In his model, he ini e se Vo e ices o he ne wo k ep esen s use s, asking o a ce ain
se ice. Each use a∈Vhas demand ωa≥0. Such demand is being pa onized by di e en
exis ing acili ies, loca ed a poin s x1,...,x on he ne wo k, so ha he demand cap u ed
by acili y a xi om use ais in e sely p opo ional o a posi i e nondec easing unc ion
o he dis ance d(a,xi) om he use a a o he acili y a xi. In o he wo ds, he demand
cap u ed by he acili y a xi om he use a ais gi en by
ωa
1/ϕa(d(a, xi))

j=11/ϕa(d(a, xj)).(2)
The usual choice o each ϕahas he o m ϕa(d) =dλa.Whenλa=2 o alla∈V,weha e
he so-called g a i a ional model.
A new i m is en e ing he ma ke , by loca ing one acili y a some poin on he ne wo k.
This pe u bs ma ke sha e, since he new acili y a xwill cap u e a demand om a∈V
equal o
ωa
1/ϕa(d(a, x))
1/ϕa(d(a, x)) +
j=11/ϕa(d(a, xj)).(3)
He e ϕais assumed o be non-nega i e, non-dec easing and wice con inuously di e en-
iable in R+. Exp ession (3) mus be ca e ully conside ed when ϕa(0)=0. Indeed, in such
case, i some xjexis s wi h xj=a∈V, hen he ull demand o awill be cap u ed by xj.
Ann Ope Res (2014) 222:175–195 177
Hence, such awill no be aken in o accoun , and hus we assume in wha ollows wi hou
loss o gene ali y ha xj/∈V,j=1,..., .
The goal o he en e ing i m is he maximiza ion o i s ma ke sha e. This is w i en as
he ollowing op imiza ion p oblem:
max
x∈[0,le],e∈E
a∈V
ωa
1/ϕa(d(a, x))
1/ϕa(d(a, x)) +
j=11/ϕa(d(a, xj)).(4)
De ining o each a∈V he posi i e cons an βa,
βa=

j=1
1
ϕa(d(a, xj)),(5)
i ollows ha p oblem (4) can be ew i en as
max
x∈[0,le],e∈EF(x) (6)
wi h Fde ined as
F(x)=
a∈V
ωa
1
1+βaϕa(d(a, x)).(7)
This p oblem has been add essed in Be man e al. (2011), in which a b anch and bound
algo i hm wi h in e al analysis bounds is p oposed.
3 Hu OD ip model
In his model, we ha e he se {{a,b},a ∈V,b ∈V}, o o igin-des ina ion pai s. The ip
om o igin a o des ina ion bwill imply a demand ωab >0.
Consume s in hei way om o igin a o des ina ion bwill s op a one acili y; hey
choose among he exis ing acili ies, x1,...,x , and he new acili y a xas in he model
desc ibed in Sec . 2: he demand om a use in his way om a o bcap u ed by each acili y
is in e sely p opo ional o a posi i e nondec easing unc ion o he leng h o he pa h om
he o igin o he des ina ion ia he acili y.
In o he wo ds, he demand cap u ed by x om use s in hei ip om o igin a o des i-
na ion bis gi en by
ωab
1/ϕab(d(a,x) +d(x,b))
1/ϕab(d(a,x) +d(x,b))+
j=11/ϕab(d(a,xj)+d(xj,b)).(8)
As in he o he model, he goal o he en e ing i m is he maximiza ion o i s ma ke
sha e. This is w i en as he ollowing op imiza ion p oblem:
max
x∈[0,le],e∈E
a,b∈V
ωab
1/ϕab(d(a,x) +d(x,b))
1/ϕab(d(a,x) +d(x,b))+
j=11/ϕab(d(a,xj)+d(xj,b)).(9)
De ining o each a,b ∈V he posi i e cons an βab,
βab =

j=1
1
ϕab(d(a, xj)+d(xj,b)),
178 Ann Ope Res (2014) 222:175–195
i ollows ha p oblem (9) can be ew i en as
max
x∈[0,le],e∈EF(x)
wi h Fde ined as
F(x)=
a,b∈V
ωab
1
1+βabϕab(d(a,x) +d(x,b)).(10)
We see ha bo h he loca ion and OD ip models yield an op imiza ion p oblem o he
same o m, namely, (6), wi h a a he simila unc ion F,asgi enby(7)and(10) espec-
i ely. Bo h unc ions Fcan be w i en in he o m
F(x)=
δ∈Δ
ωδ
1
1+βδϕδ(dδ(x)).(11)
whe e
Δ=Vand, o δ∈Δ, dδ(x) =d(a,x)
o he loca ion model, and
Δ={{a,b},a,b∈V}and, o δ∈Δ, dδ(x) =d(a,x)+d(x,b)
o he OD ip model.
4 Sol ing he models
4.1 Mul imodali y
The op imiza ion p oblems desc ibed in Sec . 2and 3a e, in gene al, mul imodal, and s an-
da d op imiza ion me hods ge s uck a local op ima. This can be seen in simple examples,
e en when he ne wo k is a segmen and is illus a ed in he ollowing examples o he Hu
loca ion p oblem in oduced in Sec . 2.
Fi s , da a o one p oblem wi h wo use s and =1 acili y on a segmen we e andomly
gene a ed. The objec i e unc ion Fo such ins ance is plo ed in Fig. 1(le ). One can see
ha he p oblem is bimodal. 100 uns o a local sea ch p ocedu e s a ing wi h a andom
poin we e pe o med.
In Fig. 1( igh ) one can see he his og am o he objec i e alues p o ided by he op i-
mize : below a 50 % o he uns yielded he global op imum, whe eas he emaining uns
s opped a he local no globally op imal solu ion.
Ano he ins ance, wi h 500 use and 100 acili ies was also gene a ed. In Fig. 2 he p ob-
lem is shown o be mul imodal, and jus below a 14 % o he uns sol ed wi h he op imize
yielded he global op imum.
In he igh pa o Figs. 1–2 he xaxis is no malized, so ha 1 co esponds o he bes
ound objec i e alue, z∗,andaba a x∈[0,1]indica es ha an objec i e alue x·z∗was
ound.
Since mul imodali y appea s e en in he simples cases, and local sea ch p ocedu es can
ge s uck a e y bad local op ima, global op imiza ion ools a e needed i he global op i-
mum is sough .
Ann Ope Res (2014) 222:175–195 179
Fig. 1 Use s =2, acili ies =1, λa=1∀a
Fig. 2 Use s =500, acili ies =100, λa=20 ∀a
4.2 Algo i hm
We will use a b anch and bound algo i hm (D ezne and Suzuki 2004;Hansene al.1985;
Plas ia 1992) o sol e he p oblems unde conside a ion. We i s ou line he algo i hm ha
inds an op imal solu ion wi hin a ela i e accu acy o ε, and la e gi e he de ails on he
bounding p ocess, which will exploi mono onici y p ope ies o he ac ha he objec i e
unc ion is DC on each edge (Blanque o and Ca izosa 2009b; Ho s and Thoai 1999;Tuy
1995; Tuy e al. 1995). We emind he eade ha a unc ion his DC i i can be w i en
as h=h+−h−,whe eh+,h−a e bo h con ex; he exp ession h+−h−is called a DC
decomposi ion o h. In he desc ip ion o he algo i hm, we ha e Δ=V o he Hu loca ion
model and Δ={{a,b},a,b∈V} o he Hu OD ip model.
Phase 1: Ini ializa ion
– Fix he equi ed accu acy ε>0.
–Se LB =0.
– Compu e he all-pai s dis ance ma ix.
– Calcula e βδ,∀δ∈Δ.

180 Ann Ope Res (2014) 222:175–195
– Se he lis Ho emaining segmen s as emp y.
Phase 2: P epa e he lis o segmen s
– Conside he edge eas segmen wi h i s nodes as he segmen e ices.
– The alue o he objec i e unc ion is e alua ed a he segmen midpoin . I he alue is
g ea e han LB, henLB is upda ed o such alue and he midpoin s o ed as incumben .
– Calcula e an uppe bound o he segmen e,UB(e).
– In case UB(e) ≥LB ·(1+ε) inse ein o H.
Phase 3: B anch and bound p ocess.
Repea as long as no s op is eached:
– Selec om H he highes uppe bound segmen , UBmax, wi h LB as ε-op imal alue and
he incumben as an ε-op imal solu ion.
I UBmax ≤LB ·(1+ε), s op he algo i hm wi h LB as he solu ion.
– The highes uppe bound segmen , UBmax, is selec ed o a spli a i s midpoin in o wo
smalle segmen s.
– The alue o he objec i e unc ion a he midpoin o he wo small segmen s is calcu-
la ed.
I any o hese alues is g ea e han LB, henLB is upda ed and all segmen s om H
whose uppe bound is lowe han LB a e disca ded.
– An uppe bound o each small segmen is calcula ed.
– All segmen s whose uppe bound is g ea e han LB ·(1+ε) a e added o H.
In he algo i hm abo e, he segmen midpoin yielding he bes uppe bound is gi en as
ε-op imal solu ion. Obse e ha he ull lis o segmen s in Hcon ain all ε-op imal solu-
ions, and can hus be used in a wo-phase p ocess, as sugges ed in he GBSSS algo i hm
(Plas ia 1992).
Le us de ail he algo i hm s eps p e iously ou lined. To calcula e he all-pai s dis ance
ma ix we use he Floyd algo i hm (Be sekas 1998), which uses he edge leng h ma ix o
build ecu si ely he dis ance ma ix.
The compu a ion o he bounds equi es mo e de ail. The algo i hm needs he calcula ion
o an uppe bound, UB(s), o each segmen s. We p esen wo p ocedu es, one based on
In e al Analysis, and he o he in p ope ies o DC unc ions.
4.3 In e al analysis bound
When he dis ance dδ(x) dec eases, he ma ke sha e as gi en by he objec i e unc ion (11)
inc eases. Hence we ob ain an uppe bound on he ma ke sha e F(x) o any loca ion xon
asegmen s=[x0,x1]⊂e∈Eby eplacing dδ(x) by he lowes possible o hese dis ances
on he segmen . De ining he e o e such lowes dis ance o he loca ion model as in Be man
e al. (2011)dδ(s) =min{d(a,x0), d(a, x1)} o δ=a, and o he OD ip model as dδ(s) =
min{d(a,x0)+d(b,x0), d(a, x1)+d(b,x1)} o δ={a,b}, we ob ain he In e al Analysis
bound
UBIA(s) =
δ∈Δ
ωδ
1
1+βδϕδ(dδ(s)) (12)
4.4 DC bound
An uppe bound ob ained making use o he ac ha he objec i e unc ion is DC on each
edge exploi s he ollowing p ope ies:
Ann Ope Res (2014) 222:175–195 181
P oposi ion 4.1 Le I⊂Rbe an in e al.Le d:I→Rbe a conca e unc ion on I,and le
g:R→Rbe DC,wi h a DC decomposi ion gi en by g(x) =g+(x) −g−(x),wi h bo h g+
and g−non-inc easing unc ions.Then, he unc ion :I→Rde ined as (x)=g(d(x))
is DC on Iand a DC decomposi ion is gi en by (x)= +(x) − −(x),whe e +(x) =
g+(d(x)) and −(x) =g−(d(x)).
P oo The p oo ollows di ec ly om he ac ha he composi ions g+(d(x)) and g−(d(x))
a e also con ex unc ions. 
Rema k 4.1 P oposi ion 4.1 makes use o a unc ion gwhich can be w i en as he di e ence
o wo con ex unc ions, g+and g−. Since such con ex unc ions a e also non-inc easing, i
u ns ou ha gbelongs o a subclass o DC unc ions, namely DCM unc ions, as in oduced
in Blanque o and Ca izosa (2009a), which a e hose unc ions exp essed as he di e ence
o wo con ex mono onic unc ions, as g+,g−a e. See Blanque o and Ca izosa (2009a) o
u he p ope ies.
We a e now in posi ion o gi e a bound o Fon an edge exploi ing he ac ha Fis DC.
Le dδ(x) be he conca e unc ion gi en in (1). Assuming ϕδ(d) =dλ
δ,(11) can be ew i en
as
F(x)=
δ∈Δ
ωδ
1
1+βδdλ
δ(x) (13)
Le us de ine a simple unc ion:
g( ) =1
1+β λ(14)
The ollowing DC decomposi ion is known o unc ion g(Bello e al. 2011):
c=λ−1
(λ +1)β 1/λ
g+( ) =g(c) +g(c)( −c) i ≤c
g( ) i >c
g−( ) =g(c) +g(c)( −c) −g( ) i ≤c
0i >c
Tha means ha
g( ) =g+( ) −g−( ).
Applying P oposi ion 4.1 we ha e ha a DC decomposi ion o Fas de ined in (13)is:
F+
δ(x) =ωδg+dδ(x)
F−
δ(x) =ωδg−dδ(x)
F(x)=
δ∈Δ
F+
δ(x) −
δ∈Δ
F−
δ(x) =
δ∈ΔF+
δ(x) −F−
δ(x)(15)
182 Ann Ope Res (2014) 222:175–195
To cons uc an uppe bound, UBDC, i s we ob ain a con ex mino an o F−
δ(x) as in
Blanque o and Ca izosa (2009a):
F−
δ(x) ≥F−
δ(x0)+ξδ(x −x0)
F(x)≤
δ∈ΔF+
δ(x) −F−
δ(x0)−ξδ(x −x0) o ξδ∈∂F−
δ(x0), (16)
whe e ∂F−
δ(x0)deno es he se o subg adien s o F−
δa x0(Tuy 1995).
De ine o each δ∈Δ he unc ion om (16):
U(x)=
δ∈ΔF+
δ(x) −F−
δ(x0)−ξδ(x −x0) o ξδ∈∂F−
δ(x0)(17)
An uppe bound o a segmen sis ob ained:
UBDC(s) =maxU( 1), U( 2)
1, 2being e ices o s.
5 Compu a ional esul s
The algo i hm desc ibed in Sec . 4was p og ammed in an In el Fo an Compile XE 12.0
and execu ed wi h an In el Co e i7 compu e wi h 8.00 Gb o RAM memo y a 2.8 Ghz. The
solu ions we e ound wi hin an accu acy o 10−10.
The Hu loca ion model was i s es ed on he 55-node and 134-edge Swain’s (1971)
ne wo k (Se a e al. 1999; Ma iano and Se a 2002), see he Appendix,Table6, wi h bo h
bounding s a egies.
Se e al ins ances o he p oblem we e gene a ed using di e en alues o he numbe
o exis ing acili ies, anging om low-sa u a ed ma ke s ( =10 % o he numbe o
edges o he ne wo k, |E|) o high-sa u a ed ma ke s ( ≤90 %|E|). Fo each alue o ,10
di e en p oblems we e sol ed. Each p oblem is ob ained by andomly and independen ly
gene a ing he demands (each e ex o he ne wo k is assumed o ha e a demand uni o mly
dis ibu ed in he in e al (0,1)) and he loca ion o he exis ing acili ies. To gene a e he
acili y loca ions, edges a e andomly chosen wi h eplacemen ; on each edge, he acili y
loca ion is gene a ed ollowing a uni o m dis ibu ion. The esul s a e shown in Table 1.
The pe cen age o exis ing acili ies is shown in he i s column. Then, i is epo ed
he minimum, maximum, mean and s anda d de ia ion (s d) o he numbe o i e a ions,
i.e., he numbe o execu ions o Phase 3, he b anch and bound (B& B) lis size and he
CPU ime. The b anch and bound lis size is he maximum size o he da a s uc u e used o
s o age eached du ing he algo i hm execu ion.
In all cases, he bes solu ion is ound in less han 0.02 seconds o DC bounds, and
0.75 seconds o In e al Analysis bounds. I is ema kable ha DC bounds lead o a e y
s able p ocedu e, as can be seen o all alues o in memo y equi emen s as well as
compu a ional ime. On he o he hand, when using In e al Analysis bounds one can see
e y ex eme cases. The e is always a huge di e ence be ween he minimum and maximum
o he numbe o i e a ions, b anch and bound lis size and ime. This means ha in he
en uns ha a e sol ed o each alue o , In e al Analysis bounds a e qui e e a ic o
p oblems o he same di icul y. The e o e, we ha e an algo i hm ha when using DC bounds
Ann Ope Res (2014) 222:175–195 183
Table 1 Resul s o he 55-node and 134-edge Swain’s ne wo k o he Hu loca ion model
(%|E|)I e a ions B&B lis size Time
min max mean±s d min max mean±s d min max mean±s d
DC 10 111 196 144.40±34.68 9 61 31.50±17.25 0.00 0.02 0.00±0.00
20 80 193 140.10±34.32 15 83 42.70±22.76 0.00 0.00 0.00±0.00
30 51 209 117.80±47.86 25 96 66.70±22.42 0.00 0.00 0.00±0.00
40 50 256 176.40±55.33 15 107 84.80±30.51 0.00 0.02 0.00±0.00
50 81 290 172.20±67.40 74 126 107.50±14.92 0.00 0.02 0.00±0.00
60 121 317 166.50±60.54 72 121 110.10±16.09 0.00 0.02 0.00±0.00
70 94 323 190.00±64.79 113 131 123.80±6.36 0.00 0.02 0.00±0.00
80 145 332 209.70±58.43 117 133 123.70±5.62 0.00 0.02 0.00±0.01
90 137 296 211.40±55.51 111 129 121.40±5.66 0.00 0.02 0.00±0.00
In e al 10 158 318 223.70±50.81 26 120 64.20±31.72 0.00 0.02 0.00±0.00
20 185 178915 18100.40±56504.50 29 58170 5890.10±18369.30 0.00 0.59 0.06±0.19
30 203 70911 17779.60±25278.44 75 25465 6219.20±8904.76 0.00 0.20 0.05±0.07
40 243 243922 24639.40±77048.06 96 84425 8551.40±26659.27 0.00 0.75 0.08±0.24
50 187 37594 9132.40±13971.49 118 13306 3143.50±4794.67 0.00 0.11 0.03±0.05
60 186 29111 7734.70±12130.03 118 9927 2703.30±4174.80 0.00 0.09 0.03±0.04
70 212 10748 3029.00±4148.73 138 3489 1038.00±1349.47 0.00 0.03 0.01±0.02
80 172 1950 866.60±677.23 127 648 310.10±192.99 0.00 0.02 0.00±0.00
90 224 22520 4243.00±7225.49 147 7248 1442.20±2338.18 0.00 0.09 0.02±0.03
190 Ann Ope Res (2014) 222:175–195
Table 4 (Con inued)
Ne wo k Nodes Edges DC bounds In e al analysis bounds
I e a ions B&B lis size Time I e a ions B&B lis size Time
mean±s d mean±s d mean±s d mean±s d mean±s d mean±s d
UR752 580 1735 232.10±33.86 160.20±11.69 17.04±0.79 330.80±70.44 160.20±11.69 16.15±1.04
UR762 593 2089 266.80±15.37 202.00±13.52 21.13±0.40 489.40±32.67 202.00±13.52 21.10±0.35
UR132 605 1122 120.50±54.90 24.60±2.17 11.48±1.48 186.00±28.42 24.60±2.17 10.93±0.41
UR735 662 1200 78.90±13.30 40.00±1.49 13.37±0.42 120.20±4.89 40.00±1.49 12.79±0.15
UR142 709 1815 115.00±16.57 94.70±13.98 23.59±0.65 179.30±30.44 94.70±13.98 22.73±0.62
UR745 713 1616 146.90±31.56 76.30±2.91 23.02±1.27 172.90±26.59 76.30±2.91 20.52±0.47
UR755 724 1966 213.60±28.51 252.60±24.49 30.11±1.20 290.40±53.88 252.60±24.49 27.37±1.11
UR765 741 2278 213.70±9.41 111.20±3.77 35.85±0.29 250.60±11.48 111.20±3.77 31.92±0.33
UR737 744 1315 107.60±17.78 49.40±7.18 20.64±0.81 137.70±8.43 49.40±7.18 19.15±0.22
UR747 745 1659 122.60±31.26 56.00±2.31 25.11±1.31 163.90±15.77 56.00±2.31 23.22±0.33
UR757 748 1969 155.90±28.57 165.10±16.54 30.83±1.30 256.00±22.63 165.10±16.54 29.70±0.50
UR767 749 2314 274.60±58.70 236.60±21.26 39.65±2.59 333.50±22.87 236.60±21.26 34.84±0.51
UR152 766 2390 208.30±39.61 155.40±11.81 39.98±1.88 268.30±16.64 155.40±11.81 36.43±0.38
UR162 802 2897 407.20±107.72 288.50±31.36 62.94±5.80 504.60±39.82 288.50±31.36 55.42±1.04
UR135 892 1619 49.80±9.35 33.00±0.82 34.40±0.69 132.50±16.64 33.00±0.82 36.79±0.61
UR145 929 2117 136.40±21.10 115.20±6.73 57.26±1.59 243.80±18.41 116.30±6.11 57.94±0.74
UR155 975 2680 174.70±31.59 195.80±21.34 83.70±2.69 242.80±25.37 195.80±21.34 85.42±4.06
UR137 980 1744 94.60±13.78 48.90±5.99 53.14±1.17 120.30±3.09 48.90±5.99 54.90±0.28
UR165 980 3068 155.10±26.17 181.40±18.46 93.71±2.34 236.00±37.40 181.40±18.46 98.32±1.94
UR147 996 2254 89.00±13.47 132.30±7.53 69.48±1.34 169.50±10.26 132.30±7.53 71.75±2.24
UR157 1000 2690 154.00±21.55 139.70±12.14 83.01±1.90 256.30±13.62 139.70±12.14 82.30±0.99
UR167 1000 3083 229.10±33.85 254.70±24.43 100.38±3.03 313.70±42.59 254.70±24.43 98.70±2.65

Ann Ope Res (2014) 222:175–195 191
Table 5 Resul s o es ins ances o he Hu OD ip model wi h 90 %|E| acili ies
Ne wo k Nodes Edges DC bounds In e al analysis bounds
I e a ions B&B lis size Time I e a ions B&B lis size Time
mean±s d mean±s d mean±s d mean±s d mean±s d mean±s d
KROB150G 150 296 88.50±3.66 62.70±4.30 0.22±0.00 137.80±3.71 62.70±4.30 0.21±0.01
KROA150G 150 297 92.70±19.97 41.70±6.00 0.22±0.02 167.20±10.12 41.70±6.00 0.22±0.01
PR152G 152 296 71.90±3.00 58.50±9.69 0.20±0.00 122.60±2.01 58.50±9.69 0.20±0.01
RAT195G 195 336 55.90±4.82 93.90±6.42 0.36±0.01 119.10±11.12 93.90±6.42 0.38±0.02
KROB200G 200 386 90.90±22.34 34.10±3.96 0.47±0.04 144.90±5.63 34.10±3.96 0.45±0.01
KROA200G 200 392 78.60±3.27 37.30±1.89 0.45±0.01 129.60±2.17 37.30±1.89 0.44±0.01
TS225G 225 306 65.80±2.49 57.10±3.28 0.46±0.02 120.20±0.42 57.10±3.28 0.46±0.01
UR532 298 597 97.40±4.01 59.10±5.22 1.53±0.02 155.60±4.38 59.10±5.22 1.41±0.01
UR542 343 862 161.40±8.77 150.30±6.55 3.11±0.04 240.00±14.00 150.30±6.55 2.83±0.05
UR552 388 1135 113.80±4.32 99.40±4.48 4.74±0.06 211.60±3.75 99.40±4.48 4.60±0.03
UR562 416 1403 204.00±10.14 195.20±8.47 7.69±0.09 356.40±13.94 199.10±12.56 7.29±0.09
UR732 452 915 79.90±3.38 45.10±2.42 5.44±0.08 130.20±2.15 45.10±2.42 5.22±0.04
UR535 458 812 81.60±4.53 44.40±4.62 5.19±0.08 137.80±9.73 44.40±4.62 4.98±0.09
UR545 476 1104 86.80±14.46 91.40±4.35 7.42±0.23 148.20±8.11 91.40±4.35 7.21±0.10
UR555 490 1305 156.00±29.30 133.00±23.67 10.30±0.48 223.20±18.90 133.00±23.67 9.49±0.17
UR537 493 868 66.60±2.63 39.10±6.40 6.44±0.15 127.20±3.33 39.10±6.40 6.25±0.03
UR565 496 1513 153.50±9.62 128.70±2.98 11.96±0.19 281.70±28.41 136.30±5.58 11.43±0.24
UR547 498 1112 79.40±3.50 77.50±3.92 8.31±0.09 139.90±4.36 77.50±3.92 7.90±0.04
UR557 498 1310 132.10±10.12 122.90±13.92 10.40±0.18 270.80±18.26 122.90±13.92 10.26±0.17
UR567 499 1426 112.00±2.67 95.10±2.77 10.84±0.03 187.50±5.25 95.10±2.77 10.26±0.04
UR742 538 1325 162.20±13.79 162.30±9.13 13.17±0.29 246.00±16.07 162.30±9.13 12.39±0.21
192 Ann Ope Res (2014) 222:175–195
Table 5 (Con inued)
Ne wo k Nodes Edges DC bounds In e al analysis bounds
I e a ions B&B lis size Time I e a ions B&B lis size Time
mean±s d mean±s d mean±s d mean±s d mean±s d mean±s d
UR752 580 1735 194.70±11.72 160.10±7.37 20.15±0.36 361.80±73.69 160.10±7.37 19.55±0.96
UR762 593 2089 303.80±77.63 191.50±15.41 27.38±2.02 445.70±38.44 191.50±15.41 24.96±0.57
UR132 605 1122 73.50±13.33 26.10±0.32 12.95±0.37 185.20±28.54 26.10±0.32 13.41±0.60
UR735 662 1200 72.80±3.55 43.60±1.51 16.70±0.15 123.50±4.17 43.60±1.51 16.46±0.81
UR142 709 1815 105.50±3.89 94.60±6.74 29.68±0.23 157.00±6.02 94.60±6.74 27.89±0.32
UR745 713 1616 127.60±44.94 81.50±2.59 28.40±1.88 188.00±4.69 81.50±2.59 25.80±0.18
UR755 724 1966 211.70±16.17 259.10±6.17 38.18±0.69 308.20±28.83 259.10±6.17 34.46±0.62
UR765 741 2278 135.80±4.73 111.90±3.96 41.83±0.35 258.40±15.54 111.90±3.96 40.24±0.58
UR737 744 1315 69.50±2.22 54.00±2.67 24.32±0.25 142.20±2.57 54.00±2.67 24.75±0.48
UR747 745 1659 86.50±8.45 56.90±2.08 30.30±0.31 162.50±14.03 56.90±2.08 29.43±1.03
UR757 748 1969 145.80±8.12 172.90±4.18 38.24±0.35 288.10±35.09 172.90±4.18 37.58±1.21
UR767 749 2314 195.00±13.23 241.50±10.74 46.02±0.75 327.40±22.74 241.50±10.74 44.82±1.23
UR152 766 2390 178.80±26.39 160.30±3.50 49.72±1.31 267.00±5.29 160.30±3.50 46.27±1.14
UR162 802 2897 328.10±22.26 324.70±14.35 74.00±1.49 550.80±38.55 324.70±14.35 68.54±1.19
UR135 892 1619 50.50±10.22 33.50±0.53 42.73±1.64 136.60±10.36 33.50±0.53 45.95±0.72
UR145 929 2117 133.10±5.65 127.50±3.69 67.30±0.42 266.10±24.08 127.50±3.69 71.57±1.10
UR155 975 2680 171.90±7.31 204.00±16.49 99.39±0.66 266.40±15.06 204.00±16.49 98.18±0.90
UR137 980 1744 72.80±3.22 51.00±4.08 61.46±0.28 124.60±4.20 51.00±4.08 62.38±0.52
UR165 980 3068 161.20±8.42 199.10±7.92 111.06±0.75 235.40±4.81 199.10±7.92 111.63±0.68
UR147 996 2254 91.40±7.89 135.60±4.48 82.76±0.73 171.10±3.21 135.60±4.48 86.18±0.51
UR157 1000 2690 136.50±4.28 136.10±2.18 98.28±0.41 247.50±7.53 136.10±2.18 99.93±0.80
UR167 1000 3083 216.80±7.25 262.90±9.26 118.59±0.77 327.70±19.31 262.90±9.26 116.10±1.34
Ann Ope Res (2014) 222:175–195 193
The compu a ional expe ience epo ed shows ha la ge ne wo ks can be success ully
handled wi h bo h bounding p ocedu es whe e he DC p ocedu e seems o be mo e s able in
bo h ime and memo y equi emen s.
Ex ensions o hese p oblems o he mul i acili y case dese e u he s udy.
Appendix
Table 6 The Swain da a se (Ma iano and Se a 2002; Se a e al. 1999)
Ini ial
node
Final
node
Edge
leng h
Ini ial
node
Final
node
Edge
leng h
Ini ial
node
Final
node
Edge
leng h
123.1623 13 47 4.4721 25 49 7.0000
152.0000 14 16 10.2956 26 36 8.6023
184.4721 14 22 12.0416 27 38 9.2195
113 2.2361 14 27 9.8489 27 54 7.2111
14310.0000 15 18 6.4031 29 31 3.6056
144 4.1231 15 25 7.2801 30 33 4.0000
234.4721 15 31 7.0000 30 45 5.0000
243.0000 15 36 6.7082 32 33 5.0000
283.1623 15 41 6.3246 32 38 4.4721
242 2.8284 15 42 6.3246 32 45 4.0000
374.2426 16 22 6.7082 34 43 6.0828
383.1623 16 27 6.4031 34 45 3.0000
319 6.4031 16 32 6.3246 35 36 7.6158
330 5.0000 16 33 6.7082 35 48 7.6158
331 6.0828 16 38 7.2111 36 48 6.0000
334 5.3852 17 22 5.0990 37 47 10.0499
453.0000 17 23 5.3852 37 50 10.4403
492.0000 17 28 7.0000 37 53 7.8102
442 2.2361 18 23 9.0000 38 43 8.2462
511 1.4142 18 26 7.0711 38 45 7.2111
513 2.2361 18 29 5.3852 38 54 6.4031
693.6056 18 31 4.4721 38 55 7.8102
610 5.0000 18 36 8.2462 39 40 11.7047
615 5.8310 19 22 8.2462 39 54 6.0828
641 4.2426 19 23 5.3852 39 55 9.8489
642 5.0990 19 29 3.6056 40 46 8.9443
715 5.8310 19 30 5.0990 40 55 8.2462
731 3.6056 19 31 5.0990 43 44 7.2801
742 4.2426 20 21 4.4721 43 45 6.3246
834 3.6056 20 25 9.2195 43 46 5.0000
910 6.0000 20 41 8.2462 43 55 5.0000
911 4.1231 20 49 6.0000 44 46 7.2111
942 3.6056 20 51 9.2195 44 47 6.0000
10 20 8.0623 21 37 7.2111 46 47 11.6619
194 Ann Ope Res (2014) 222:175–195
Table 6 (Con inued)
Ini ial
node
Final
node
Edge
leng h
Ini ial
node
Final
node
Edge
leng h
Ini ial
node
Final
node
Edge
leng h
10 21 9.0000 21 51 7.2801 46 52 15.6205
10 37 7.8102 22 33 4.2426 46 55 6.0000
10 41 6.0828 23 26 12.2066 47 52 16.1245
10 47 8.6023 23 28 7.0711 47 53 5.6569
11 13 2.2361 23 29 4.4721 48 49 6.4031
11 47 3.6056 24 26 7.2111 49 51 12.0416
12 14 10.6301 24 35 4.4721 50 52 8.6023
12 17 6.3246 24 36 9.0554 50 53 5.8310
12 22 8.6023 25 36 5.6569 52 53 12.1655
12 28 7.8102 25 41 4.1231 54 55 10.1980
13 44 2.8284 25 48 4.4721
Re e ences
Bello, L., Blanque o, R., & Ca izosa, E. (2011). On minimax- eg e Hu loca ion models. Compu e s and
Ope a ions Resea ch,38, 90–97.
Be man, O., D ezne , Z., & K ass, D. (2011). Big segmen small segmen global op imiza ion algo i hm on
ne wo ks. Ne wo ks,58(1), 1–11.
Be sekas, D. P. (1998). Ne wo k op imiza ion: con inuous and disc e e models. Belmon : A henas Scien i ic.
Blanque o, R., & Ca izosa, E. (2009a). Con inuous loca ion p oblems and big iangle small iangle: con-
s uc ing be e bounds. Jou nal o Global Op imiza ion,45, 389–402.
Blanque o, R., & Ca izosa, E. (2009b). On co e ing me hods o d.c. op imiza ion. Jou nal o Global Op i-
miza ion,18, 265–274.
Co be án, A., & Sanchis, J. M. (2007). A b anch & cu algo i hm o he windy gene al ou ing p oblem and
special cases. Ne wo ks,49, 245–257.
Dea ing, P. M., & Shie , D. R. (1983). Op imal loca ions o a class o nonlinea single- acili y loca ion
p oblems on a ne wo k. Ope a ions Resea ch,31(2), 292–303.
D ezne , T., & D ezne , Z. (2004). Finding he op imal solu ion o he Hu compe i i e loca ion model.
Compu a ional Managemen Science,1, 193–208.
D ezne , Z., & Suzuki, A. (2004). The big iangle small iangle me hod o he solu ion o non-con ex
acili y loca ion p oblems. Ope a ions Resea ch,52, 128–135.
Fe nández, J., Peleg ín, B., Plas ia, F., & Tó h, B. (2007). Sol ing a Hu -like compe i i e loca ion and
design model o p o i maximiza ion in he plane. Eu opean Jou nal o Ope a ional Resea ch,170,
1274–1287.
Hansen, P., Pee e s, D., Richa d, D., & Thisse, J. F. (1985). The minisum and minimax loca ion p oblems
e isi ed. Ope a ions Resea ch,33(6), 1251–1265.
Ho s , R., & Thoai, N. V. (1999). Dc p og amming: o e iew. Jou nal o Op imiza ion Theo y and Applica-
ions,103, 1–43.
Hu , D. L. (1964). De ining and es ima ing a ading a ea. Jou nal o Ma ke ing,8, 28–34.
Hu , D. L. (1966). A p og ammed solu ion o app oxima ing an op imum e ail loca ion. Land Economics,
8(42), 293–303.
Labbé, M., Pee e s, D., & Thisse, J. F. (1995). Loca ion on ne wo ks. In M. O. Ball e al. (Eds.), Handbooks
in ope a ions esea ch and managemen science (Vol. 8, pp. 551–624). Ams e dam: Else ie .
Ma iano , V., & Se a, D. (2002). Loca ion-alloca ion o mul iple-se e se ice cen e s wi h cons ained
queues o wai ing imes. Annals o Ope a ions Resea ch,111, 35–50.
Plas ia, F. (1992). GBSSS: he gene alized big squa e small squa e me hod o plana single- acili y loca ion.
Eu opean Jou nal o Ope a ional Resea ch,62(2), 163–174.
Plas ia, F. (2001). S a ic compe i i e acili y loca ion: an o e iew o op imisa ion app oaches. Eu opean
Jou nal o Ope a ional Resea ch,129(3), 461–470.
Reinel , G. (1991). Tsplib—a a eling salesman p oblem lib a y. ORSA Jou nal on Compu ing,3(4), 376–
384.
Ann Ope Res (2014) 222:175–195 195
Se a, D., ReVelle, C., & Rosing, K. (1999). Su i ing in a compe i i e spa ial ma ke : he h eshold cap u e
model. Jou nal o Regional Science,39(4), 637–652.
Tuy, H. (1995). DC op imiza ion: heo y, me hods and algo i hms, handbook o global op imiza ion.Do -
d ech : Kluwe Academic.
Tuy, H., Al-Khayyal, F., & Zhou, F. (1995). A d.c. op imiza ion me hod o single acili y loca ion p oblems.
Jou nal o Global Op imiza ion,7, 209–227.