Sol ing he median p oblem wi h con inuous demand on a
ne wo k∗
Ra ael Blanque o and Emilio Ca izosa,
Uni e sidad de Se illa, Spain
{ blanque o,eca izosa}@us.es
No embe 5, 2012
Abs ac
Whe e o loca e one o se e al acili ies on a ne wo k so as o minimize he expec ed
use s-closes acili y anspo a ion cos is a p oblem well s udied in he OR li e a u e unde
he name o median p oblem.
In he median p oblem use s a e usually iden i ied wi h nodes o he ne wo k. In many
si ua ions, howe e , such assump ion is un ealis ic, since use s should be be e conside ed o
be dis ibu ed also along he edges o he anspo a ion ne wo k. In his pape we add ess
he median p oblem wi h demand dis ibu ed along edges and nodes. This leads o a global-
op imiza ion p oblem, which can be sol ed o op imali y by means o a b anch-and-bound
wi h DC bounds. Ou compu a ional expe ience shows ha he p oblem is sol ed in sho
ime e en o la ge ins ances.
Keywo ds: Ne wo k Loca ion, Median P oblem, Con inuous Demand, DC Func ions, Global
Op imiza ion
1 In oduc ion
Loca ion p oblems on ne wo ks ha e a ac ed he in e es o esea che s and p ac i ione s since
he 60s o las cen u y. Unde he usual assump ion, he demand is concen a ed a he nodes
o he ne wo k, and he acili ies can be loca ed ei he a he nodes o along he edges o he
anspo a ion ne wo k.
Assuming ha he demand is concen a ed a he nodes is no ealis ic when modeling so-
called ne wo ks spa ial phenomena, e.g. [18], ha is, phenomena which do happen in poin s
along edges o he ne wo k, such as, o ins ance, a ic acciden s, o close o such edges, as
happens in u ban se ings, whe e edges model he ci y s ee s, close o he buildings whe e
demand happens. See [18, 19] o u he discussion on he ad an ages on con inuous ne wo k
models agains adi ional app oaches (disc e e o plana loca ion models).
∗Resea ch suppo ed by g an s om he Spanish Minis y o Educa ion, Cul u e and Spo MTM2009-14039-
C06-06, Jun a de Andaluc´ıa TIC-6064, FQM-329, in pa inanced by he Eu opean Regional De elopmen
Fund (ERDF).
1
Fo his eason, se e al esea che s ha e add essed loca ion p oblems on ne wo ks unde he
assump ion ha demand is no only concen a ed on nodes, bu also is (con inuously) dis ibu ed
along he edges o he ne wo k.
Mos pape s conside he case in which, o each edge o he ne wo k, demand is uni o mly
dis ibu ed. [17] add esses he p oblem o minimizing he expec ed dis ance om he use s o
one acili y, [6, 8] conside he wo- acili y case on e y pa icula ne wo k opologies ( ees),
whe eas [15] add esses he minimiza ion o he a iance o dis ances om he use s o he acili y.
Assuming uni o m demands on edges should be seen as a i s s ep owa ds gaining ealism o he
model, while main aining ac abili y. Indeed, he esul ing objec i e unc ions admi s a a he
simple o m, as a piecewise polynomial unc ion in one a iable, whose op imiza ion is educed
o inspec ing all c i ical poin s, namely, ex eme poin s and poin s a which he de i a i e o
he polynomial unc ion anishes.
Assuming mo e gene al dis ibu ions o he demand has been ad oca ed by se e al au ho s.
[18] sugges s he use o gene al densi y dis ibu ions, om which andom samples a e gene a ed,
yielding a disc e e app oxima ion o he p oblem, which is he one which is la e analyzed.
S a is ical ke nel me hods ha e also been ecen ly p oposed o model he demand, [20, 23],
hough, as a as he au ho s know, no op imiza ion has been ca ied ou , excep ing, as said
abo e, disc e iza ion ia simula ion.
In his pape we conside a single- acili y loca ion p oblem, namely, he 1-median p oblem:
he poin minimizing he expec ed dis ance om he use s is sough . Wi h espec o he
s a e-o - he-a , we gi e a u he s ep owa ds ealism, by assuming a bi a y dis ibu ions o
he demand along edges. Con a y o he plana 1-median p oblem, known o be con ex, [7],
he 1-median p oblem on ne wo ks wi h con inuous demand poses non i ial challenges: we
ha e no longe a simple exp ession o he objec i e, and i s op imiza ion calls o he use o
global-op imiza ion echniques. In pa icula , i is shown ha he objec i e unc ion is DC,
[10, 11, 21, 22] i.e., i can be w i en as he di e ence o wo con ex unc ions, and hus i s
op imiza ion can be add essed ia b anch-and-bound me hods cus omized o DC unc ions,
[1, 4, 5].
The emainde o he pape is o ganized as ollows. In Sec ion 2 he 1-median p oblem wi h
demand dis ibu ed on edges and on nodes o he ne wo k is o mally in oduced. P ope ies
o he objec i e unc ion a e discussed in Sec ion 3, whe e i is shown, in pa icula , how he
unc ion can be exp essed as he di e ence o wo con ex unc ions on each edge o he ne wo k.
These p ope ies will be he co ne s one o a b anch-and-bound algo i hm, as desc ibed in
Sec ion 4. Ou nume ical expe ience is epo ed in Sec ion 5, showing ha ou algo i hm
enables us o sol e p oblems on la ge ne wo ks in easonable ime.
2 P oblem o mula ion
Le N= (A, E) be a connec ed and undi ec ed ne wo k, wi h node se A={a1, . . . , an}and
edge se E, wi h |E|=m. Le us deno e by lij he leng h o each edge eij = [ai, aj]∈Eand
le d(x, y) be he dis ance be ween wo poin s x, y ∈N, ob ained as he sho es pa h om x o
y. In pa icula , he dis ance dij =d(ai, aj) be ween each pai o nodes {ai, aj}can be wo ked
ou by using s anda d algo i hms, [2]. No e ha o e e y pai o nodes ai, ajwi h [ai, aj]∈E,
i ollows ha dij ≤lij ,and equali y holds i and only i he edge [ai, aj] is he sho es pa h
joining aiand aj.
2
Gi en a node ak∈Aand a poin x∈[ai, aj], ob ained a e co e ing a dis ance lxon he
edge [ai, aj], he dis ance d(x, ak) om ak o xis, as a unc ion o x, a piecewise linea conca e
unc ion gi en by:
d(x, ak) = min{ k
ij(x), sk
ij(x)}(1)
whe e
k
ij(x) = d(ai, ak) + lxsk
ij(x) = d(aj, ak)+(lij −lx) (2)
We assume ha he demand no only occu s a nodes bu also along he edges o he ne wo k.
Mo e p ecisely, he demand o a node a∈Awill be deno ed by ωa≥0, he o al demand o a
gi en edge e∈Eis pe≥0,and i is dis ibu ed along eacco ding o a andom a iable wi h
cumula i e dis ibu ion unc ion (cd ) Fe.
Unde he p e ious assump ions, he median p oblem wi h con inuous demand can be w i en
as ollows:
min
x∈NH(x) := X
a∈A
wad(x, a) + X
e∈E
peZy∈e
d(x, y)dFe(y) (3)
Obse e ha we a e making no assump ion on he ype o dis ibu ion ollowed o he
demand. In case he demand on he edges is con inuously dis ibu ed along e, i.e., when he cd
Fehas a pd e,(3) can be ew i en as
min
x∈NH(x) := X
a∈A
wad(x, a) + X
e∈E
peZy∈e
d(x, y) e(y)dy. (4)
3 P ope ies
I has been no iced in [12] ha he objec i e unc ion o (3) is nei he con ex no conca e as
a ule. Indeed, he objec i e unc ion can exhibi local op ima which a e no globally op imal,
as he ollowing example shows. So he use o global op imiza ion echniques is equi ed i one
seeks he op imal solu ion.
Example 1 Le us conside he ne wo k N= (A, E)wi h A={a1, a2, a3}and E={[a1, a2],[a1, a3],[a2, a3]}.
A c leng hs, node demands and a c demands a e he ollowing:
l12 = 1 l13 = 1 l23 = 1
w1= 0 w2= 0 w3= 0
p12 = 0.35 p13 = 0.30 p23 = 0.35
We also assume ha he demand along each a c eis dis ibu ed acco ding o a be a dis ibu-
ion, i.e., he p obabili y densi y unc ion ehas he o m
e(x) = Γ(αe+βe)
Γ(αe)Γ(βe)xαe−1(1 −x)βe−1x∈[0,1].
The pa ame e s αe, βeo hese p obabili y dis ibu ions in he h ee edges a e as ollows:
A c e αeβe
[a1, a2] 0.6 0.5
[a1, a3] 0.4 0.8
[a2, a3] 0.5 0.5
3
Unde hese assump ions, he objec i e unc ion o P oblem (3) es ic ed o he edge [a1, a2]
akes he o m
H12(x)=0.35 Z1
0
|x−y| 12(y)dy+0.30 Z1
0
min{x+y, 3−x−y} 13(y)dy+0.35 Z1
0
min{2+x−y, 1−x+y} 23(y)dy.
(5)
Mul imodali y o he unc ion is clea ly seen in Figu e 1.
0.685
0.69
0.695
0.7
0.705
0.71
0 0.2 0.4 0.6 0.8 1
Figu e 1: Objec i e unc ion H12(x) in Example 1
The special s uc u e o he objec i e unc ion o P oblem (3) will be exploi ed in o de o
design a de e minis ic global op imiza ion algo i hm ha allows us o ind an op imal solu ion
o he p oblem. Mo e p ecisely, we will show ha H(x) in (3) belongs o he b oad class o
DC unc ions, [11, 10, 21]. This key p ope y will allow us o sol e P oblem (3) by b anch-and-
bound algo i hms, as he one desc ibed in Sec ion 4, since lowe and uppe bounds can easily
be ob ained o DC unc ions as soon as a DC decomposi ion is a ailable.
De ini ion 2 Le Ω⊂Rnbe a con ex se . A unc ion h: Ω →Ris called DC in Ωi he e
exis wo con ex unc ions h+: Ω →R,h−: Ω →Rsuch ha
h(x) = h+(x)−h−(x)∀x∈Ω (6)
A pai (h+, h−)sa is ying (6) is called a DC decomposi ion o hin Ω.
An in e es ing p ope y o he class o DC unc ions is ha i is closed unde he mos com-
mon ope a ions in op imiza ion, [3, 10, 11, 21, 22]. In pa icula , i h1, . . . , h a e DC unc ions
and λi∈R, i = 1, . . . , , hen P
i=1 λihi, maxi=1,..., hi, mini=1,..., hiand k(h1, . . . , h )ka e
also DC and hei DC decomposi ions can be easily ob ained om he DC decomposi ions o
hi, i = 1, . . . , .
The ollowing esul shows ha he objec i e unc ion H(x) in (3) is DC on each a c o he
ne wo k.
4
P oposi ion 3 Gi en ¯e∈E, he unc ion H¯e: ¯e7→ Rde ined as
H¯e(x) := X
a∈A
wad(x, a) + X
e∈E
peZy∈e
d(x, y)dFe(y)
is DC. A DC decomposi ion o H¯eon ¯eis gi en by he pai (H+
¯e, H−
¯e),wi h
H+
¯e(x) = p¯eZy∈¯e
|x−y|dF¯e(y)
H−
¯e(x) = H+
¯e(x)−H¯e(x)
(7)
P oo . Le us ew i e H¯e(x) as H¯e(x) = h1(x) + h2(x) + h3(x) whe e
h1(x) = X
a∈A
wad(x, a) (8)
h2(x) = X
e∈E,e6=¯e
peZy∈e
d(x, y)dFe(y) (9)
h3(x) = p¯eZy∈¯e
d(x, y)dF¯e(y) (10)
The unc ion h1is piecewise linea and conca e (see [13] o ins ance), and h2is also conca e,
see [12]. In wha ollows i is shown ha h3is DC, and a DC decomposi ion is gi en. Gi en
x, y ∈¯e= [ai, aj], he dis ance d(x, y) be ween xand yis ob ained as he minimum o he
leng hs o he ollowing pa hs:
1. he subedge o ¯ewi h x, y as end poin s,
2. he subedge o ¯ejoining xand ai, he sho es pa h joining aiand aj,and hen he subedge
o ¯ejoining ajand y,
3. he subedge o ¯ejoining xand aj, he sho es pa h joining ajand ai,and hen he subedge
o ¯ejoining aiand y.
In o he wo ds d(x, y) can be exp essed as
d(x, y) = min {|x−y|, x +dij + (lij −y),(lij −x) + dij +y}(11)
= min {|x−y|, lij +dij − |x−y|} (12)
=|x−y| − max {0,2|x−y| − (lij +dij)}.(13)
Obse e ha he las exp ession gi es a DC decomposi ion o don ¯e. Hence, h3can be w i en
as
h3(x) = p¯eZy∈¯e
|x−y|dF¯e(y)−p¯eZy∈¯e
max {0,2|x−y| − (lij +dij)}dF¯e(y),(14)
which yields a DC decomposi ion o h3.Taking in o accoun ha H¯e=h1+h2+h3,wi h h1, h2
conca e and h3decomposed as a di e ence o con ex unc ions in (14), i ollows ha (7) gi es
a DC decomposi ion o H¯e,as asse ed. 2
We end his sec ion wi h u he p ope ies o he objec i e unc ion Heunde some assump-
ion on he edge e. These esul s ex end p e ious well-known esul s o pa icula opologies,
e.g. o ne wo ks which a e chains o ees.
5

Co olla y 4 Le ¯e∈Ebe an edge such ha p¯e= 0.Then H¯eis conca e on ¯e.
P oo . I p¯e= 0, hen, by P oposi ion 3, (0,−H¯e) is a alid DC decomposi ion o H¯e.2
P oposi ion 5 Le ¯e∈Ebe an edge such ha E {¯e}is a disconnec ed ne wo k. Then H¯eis
con ex on ¯e.
4 The algo i hm
P oblem (3) will be sol ed by using a s anda d b anch and bound me hod [14, 16] which will
ind ou he op imal solu ion wi hin a ela i e accu acy o ε > 0. The bounds o he objec i e
unc ion equi ed o applying he algo i hm will be wo ked ou by aking in o accoun i s DC
s uc u e. A b ie desc ip ion o such an algo i hm is shown nex .
•Phase 1: Ini ializa ion
1. Fix he equi ed accu acy ε > 0.
2. Se UB = +∞(uppe bound ini ializa ion).
3. Compu e he all-pai s dis ance ma ix.
4. Se he lis Λ o emaining segmen s as emp y.
5. Fo each edge e∈Edo:
(a) Conside eas a segmen wi h i s nodes as he segmen e ices.
(b) E alua e he objec i e unc ion a he segmen midpoin . I his alue is lowe
han UB, hen upda e UB and s o e in xUB he midpoin as incumben .
(c) Calcula e a lowe bound o he segmen e,LB(e).
(d) I LB(e)< UB/(1 + ε), hen inse ein o Λ.
•Phase 2: B anch and Bound p ocess
Repea as long as no s op was eached:
1. Selec om Λ he minimum lowe bound segmen emin and emo e i om Λ.
2. I LB(emin)≥UB/(1 + ε), hen s op he algo i hm wi h xUB as op imal solu ion
and UB as op imal objec i e alue.
3. Spli emin by i s midpoin in o wo smalle segmen s, e1
min and e2
min.
4. E alua e he objec i e unc ion a he midpoin o he wo small segmen s. I any o
hese alues is lowe han UB, hen upda e UB.
5. Compu e a lowe bound o he objec i e unc ion on each small segmen .
6. I LB(ei
min)< UB/(1 + ε) o i= 1 o i= 2, hen inse ei
min in o Λ.
7. I UB has been upda ed in his i e a ion, hen disca d all segmen s om Λ whose
lowe bound is g ea e han UB.
6
The algo i hm uses a da a s uc u e Λ whe e all he segmen s (bi s o edge) ha can con ain
an op imal solu ion a e s o ed. The loop in Phase 1 es ablishes he ini ial composi ion o he
da a s uc u e by selec ing he edges whose lowe bound is no g ea e ha he global uppe
bound o he op imal objec i e alue. A he same ime, ha uppe bound is imp o ed by
e alua ing each edge a i s middle poin and eplacing he bound wi h he objec i e alue when
his is smalle .
Phase 2 o he algo i hm consis s o an unde ined loop whe e he segmen wi h he wo s
lowe bound is p ocessed; he algo i hm inishes when he di e ence be ween ha lowe bound
and he global uppe bound is smalle han he ole ance εchosen in Phase 1. I he s opping
ule is no ul illed, he selec ed segmen is spli in o wo equal segmen s which a e p ocessed
in he same way ha he edges in Phase 1. E en ually, i a change in he uppe bound ook
place du ing an i e a ion, all he segmen s in he da a s uc u e ha canno con ain an op imal
solu ion a e emo ed.
The compu a ion o he objec i e unc ion’s lowe bound on each segmen equi es mo e
a en ion and is going o be de ailed nex .
4.1 Cons uc ing lowe bounds
Gi en an edge ¯e= [ai, aj]∈E, P oposi ion 3 p o ides a DC decomposi ion o H¯e– he e-
s ic ion o he objec i e H o e– and his ac can be exploi ed in o de o ob ain he lowe
bounds equi ed in he p e ious algo i hm. S a ing om he DC ep esen a ion (7), a conca e
unde es ima e L¯e(x) o H¯eis ob ained by eplacing H+
¯ewi h an a ine unde es ima e buil in
he usual way,
L¯e(x) = H+
¯e(x0) + ξ(x−x0)−H−
¯e(x)
whe e ξis any poin in ∂H+
¯e(x0), he subdi e en ial o H+
¯ea x0∈¯e. Since
∂H+
¯e(x0) = Z(0,x0)
dF¯e(y)+[−1,1] Z{x0}
dF¯e(y)−Z(x0,l¯e)
dF¯e(y),
one has
2F¯e(x0)−1∈∂H+
¯e(x0),
and hus, a conca e unde es ima e L¯e(x) is gi en by
L¯e(x) = H+
¯e(x0) + (2F¯e(x0)−1)(x−x0)−H−
¯e(x)
Due o he conca i y o L¯e, i is enough o e alua e his unc ion a he ex eme poin s o ¯e o
ob ain i s minimum on he segmen , which is also a lowe bound o H+
¯e. Hence,
LB(¯e) = min{L¯e(ai), L¯e(aj)}
5 Compu a ional esul s
The e ec i eness o he p oposed algo i hm was in es iga ed wi h he aid o nume ical cases.
The algo i hm desc ibed in Sec ion 4 was coded in Fo an and compiled using In el c
Fo an
Compile XE 12.0. Execu ions we e ca ied ou on an In el Co e i7 compu e wi h 8.00 Gb o
7
RAM memo y a 2.8 Ghz, unning Windows 7. The solu ions we e ound o a ela i e accu acy
o 10−3and he in eg als we e calcula ed by means o he unc ions qdags and qdagp a ailable
a he IMSL Fo an Nume ical Lib a y.
We expe imen ed wi h a se o 43 es ne wo ks ob ained om [9, 24]. The numbe o nodes
o hese es p oblems anges om 150 o 1000, and he numbe o edges om 296 o 3083.
Each p oblem was sol ed 10 imes o e each ne wo k using andomly gene a ed pa ame e s: he
demands o nodes we e ob ained om a Uni o m dis ibu ion on [0,1], as i is also he case o
he o e all demand o each edge. Rega ding he demand along each edge, i was assumed o be
dis ibu ed ollowing a Be a dis ibu ion wi h pa ame e s andomly gene a ed on he in e al
[0.1,5], which p o ides a wide ange o densi y unc ions wi h e y di e en shapes.
A e he esolu ion o each se o 10 ins ances, some s a is ical measu es (minimum, maxi-
mum, a e age and s anda d de ia ion) we e calcula ed o he ollowing indica o s o he algo-
i hm pe o mance:
•Numbe o i e a ions o he Phase 2 o he algo i hm.
•Maximum size o he da a s uc u e used o s o age eached du ing he algo i hm execu-
ion.
•CPU ime.
Table 1 shows he compu a ional esul s, whe e he numbe o nodes |A|and edges |E|o
he g aphs a e epo ed as well as he abo e-men ioned compu a ional measu es.
The numbe o i e a ions and he maximum size o he b anch-and-bound lis emain low in
all he execu ions. Howe e , he CPU ime esul s a e qui e high mainly due o he compu a ion
o he in eg als in Phase 1 (s eps 5-b and 5-c) and Phase 2 (s eps 4 and 5). One can see ha
he CPU ime equi ed o sol e di e en ins ances o he same p oblem shows a g ea s abili y.
We summa ize he indings o his pape . We ha e add essed he p oblem o loca ing one
acili y on a ne wo k wi h demand dis ibu ed on nodes and edges, ollowing a bi a y dis i-
bu ions. The p oblem is shown o be mul imodal, calling o he use o global op imiza ion
echniques. The objec i e unc ion on each edge has been shown o be DC, and a DC decom-
posi ion is gi en. This enables us o ob ain conca e unde es ima es o he objec i e, which a e
used in a b anch and bound p ocedu e. Ou nume ical es s show ha p oblems o la ge size
a e sol ed a he quickly. Ex ensions o ou echniques o he mul i acili y case a e now unde
s udy.
Re e ences
[1] L. Bello, R. Blanque o, E. Ca izosa, “On minimax- eg e Hu loca ion models”. Compu e s
& Ope a ions Resea ch 38 (2011) 90–97.
[2] D.P. Be sekas, Ne wo k Op imiza ion: Con inuous and Disc e e Models. A henas Scien i ic,
Belmon , Mass. (1998).
[3] R. Blanque o, E. Ca izosa, “Op imiza ion o he no m o a ec o - alued DC unc ion and
applica ions”. Jou nal o Op imiza ion Theo y and Applica ions 107 (2000) 245–260.
8
Ne wo k |A| |E|i e a ions B&B lis ime
min max mean±s d min max mean±s d min max mean±s d
KROB200G 200 386 6 18 11.60±4.03 11 18 13.60±2.46 27.89 32.76 30.14±1.63
KROB150G 150 296 13 21 17.20±2.70 4 4 4.00±0.00 17.61 20.89 19.19±1.17
KROA200G 200 392 11 17 13.70±1.89 8 13 9.60±1.58 30.58 34.60 32.15±1.37
UR137 980 1744 10 16 12.20±2.04 11 11 11.00±0.00 494.23 543.32 511.20±13.80
KROA150G 150 297 11 22 16.90±4.09 6 16 13.20±3.16 17.46 20.01 18.55±0.80
PR152G 152 296 2 7 4.00±1.56 5 6 5.10±0.32 14.77 18.47 16.34±1.03
RAT195G 195 336 4 11 8.10±2.18 3 6 3.30±0.95 17.89 20.31 18.67±0.89
TS225G 225 306 9 15 12.10±1.73 9 11 9.40±0.70 8.94 10.30 9.85±0.46
UR532 298 597 4 44 12.00±13.26 3 28 10.10±7.78 69.69 82.91 73.39±4.14
UR542 343 862 9 17 13.90±2.77 8 18 11.90±3.48 169.28 182.12 175.00±3.98
UR552 388 1135 15 30 22.90±4.72 14 14 14.00±0.00 333.14 347.49 339.86±5.33
UR562 416 1403 23 37 28.20±3.97 27 30 28.60±0.84 532.68 569.67 551.77±12.75
UR732 452 915 1 15 7.90±5.00 6 11 8.00±2.21 164.72 179.26 171.37±4.72
UR535 458 812 0 4 1.60±1.78 3 3 3.00±0.00 102.79 121.29 113.57±5.78
UR545 476 1104 7 20 14.00±3.80 15 24 19.60±2.67 264.00 285.97 275.21±9.58
UR555 490 1305 8 22 16.20±4.59 25 30 26.90±1.79 401.20 429.67 415.26±10.39
UR537 493 868 8 14 11.00±2.05 10 13 12.10±1.45 118.01 134.64 124.53±5.49
UR565 496 1513 15 27 21.90±3.60 23 28 26.30±1.64 573.02 631.32 604.81±19.32
UR547 498 1112 11 19 15.00±2.62 9 14 11.40±1.35 259.46 278.79 269.54±6.59
UR557 498 1310 9 21 16.30±4.16 10 17 11.50±2.42 404.76 425.90 413.57±7.60
UR567 499 1426 13 20 16.10±2.02 5 9 6.80±1.99 510.09 540.01 519.53±8.27
UR742 538 1325 9 20 15.10±4.09 15 18 16.90±0.74 393.67 425.37 406.78±10.22
UR752 580 1735 30 54 43.20±6.68 25 42 29.50±5.60 787.07 825.64 799.86±12.27
UR762 593 2089 31 47 39.40±5.13 21 22 21.80±0.42 1179.76 1271.95 1229.23±26.58
UR132 605 1122 12 27 21.40±3.92 8 8 8.00±0.00 224.33 239.21 233.02±5.58
UR735 662 1200 10 15 12.00±1.56 8 11 10.50±1.08 234.36 255.16 247.08±6.57
UR142 709 1815 5 12 8.40±2.32 4 4 4.00±0.00 748.35 805.64 779.01±17.74
UR745 713 1616 6 16 10.80±3.74 13 14 13.60±0.52 536.82 591.37 561.00±15.58
UR755 724 1966 12 21 15.70±3.27 19 23 20.50±1.84 926.85 972.39 945.26±13.39
UR765 741 2278 6 18 11.90±3.93 13 18 14.20±1.40 1316.04 1366.79 1341.44±16.73
UR737 744 1315 6 14 10.90±2.42 4 4 4.00±0.00 273.45 320.83 290.30±12.75
UR747 745 1659 9 20 14.10±3.31 11 13 11.90±0.57 574.32 609.25 586.98±12.07
UR757 748 1969 12 23 16.70±3.30 19 21 19.90±0.74 891.87 967.30 929.94±21.33
UR767 749 2314 14 22 17.00±2.58 24 53 36.60±9.81 1369.49 1427.39 1390.21±17.92
UR152 766 2390 17 33 24.70±4.74 16 18 17.10±0.88 1455.80 1564.55 1491.42±30.88
UR162 802 2897 30 47 37.80±5.33 23 34 31.00±2.98 2321.47 2419.84 2366.32±32.81
UR135 892 1619 0 7 3.40±2.50 4 6 5.50±0.85 430.73 465.54 447.52±11.17
UR145 929 2117 12 25 20.40±4.03 16 36 28.90±5.72 953.42 1011.92 975.20±18.78
UR155 975 2680 8 22 14.90±3.78 10 10 10.00±0.00 1701.16 1816.37 1755.81±32.00
UR165 980 3068 12 18 15.10±1.97 20 29 24.10±2.47 2368.22 2453.96 2425.75±27.64
UR147 996 2254 10 21 14.60±3.20 5 9 6.90±1.66 1037.24 1113.22 1081.61±23.26
UR157 1000 2690 11 26 18.80±5.35 34 38 36.70±1.42 1671.54 1779.63 1726.31±30.29
UR167 1000 3083 14 25 18.20±3.26 17 34 25.70±7.15 2408.45 2495.42 2451.24±31.00
Table 1: Compu a ional esul s
[4] R. Blanque o, E. Ca izosa, “Con inuous loca ion p oblems and Big T iangle Small T iangle:
Cons uc ing be e bounds”. Jou nal o Global Op imiza ion 45 (2009) 389–402.
[5] R. Blanque o, E. Ca izosa, P. Hansen, “Loca ing objec s in he plane using Global Op i-
miza ion echniques”. Ma hema ics o Ope a ions Resea ch 34 (2009) 837–858.
[6] M.L. B andeau, S.S. Chiu, R. Ba a, “Loca ing he wo-median o a ee ne wo k wi h
con inuous link demands”. Annals o Ope a ions Resea ch 6(1986) 223–253.
[7] E. Ca izosa, E. Conde. M. Mu˜noz-M´a quez, J. Pue o, “The gene alized Webe p oblem
wi h expec ed dis ances”. RAIRO. Reche che op´e a ionnelle 29 (1995) 35–57.
[8] T.M. Ca alie , T.M., H.D. She ali, “Ne wo k loca ion p oblem wi h con inuous link de-
mands: p-medians on a chain and 2-medians on a ee”. Eu opean Jou nal o Ope a ional
Resea ch 23 (1986) 246–255.
[9] A. Co be ´an, J.M. Sanchis, “A b anch & cu algo i hm o he windy gene al ou ing
p oblem and special cases”. Ne wo ks,49 (2007) 245–257.
[10] R. Ho s , N.V. Thoai, “DC p og amming: O e iew”. Jou nal o Op imiza ion Theo y and
Applica ions 103 (1999) 1–43.
9