Solving the median problem with continuous demand on a network

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