The pa h- a iance p oblem on ee ne wo ks
Te esa C%ace esa, M. C uz L%opez- de- los- Mozos
a, Juan A. Mesab
aDepa amen o de Ma ema ica Aplicada I, E.T.S. de Ingenie a In o ma ica, A da. Reina Me cedes, s/n, Se illa 410 12, Spain
bDepa amen o de Ma ema ica Aplicada II, Uni e sidad de Se illa, E.T.S. de Ingenie a In o ma ica, A da. Reina Me cedes, s/n, Se illa
410 12, Spain
Abs ac
Ex ensi e acili y loca ion models on g aphs deal wi h he loca ion o a special ype o subg aphs such as pa hs, ees
o cycles and can be conside ed as ex ensions o classical poin loca ion models. Va iance is one o he measu es applied
in models in which some equali y equi emen is imposed. In his pape he p oblem o loca ing a minimum a iance pa h
in a ee ne wo k is add essed, and an O(n2 log n) ime algo i hm is p oposed.
Keywo ds: Loca ion on ne wo ks; Equali y; Ex ensi e acili es
1. In oduc ion
Du ing he las wo decades he e has been inc easing a en ion paid o he applica ion o balancing o equali y objec i es
in loca ion analysis. Pape s on equali y loca ion models can be oughly classi;ed in o wo g oups: Fi s , hose dealing
wi h gene al aspec s such as how o measu e equali y, how o de;ne and wha p ope ies should ha e equali y measu es
([2,3,10]), and secondly, hose o ien ed o design e@cien algo i hms o sol ing he co esponding p oblems ([5,8,9]).
On he o he hand, when he acili y o be loca ed is oo la ge o be modelled as a poin , ex ensi e acili y loca ion
models a ise. Se e al pape s ha e in es iga ed he p oblem o loca ing, on a ne wo k, a pa h, ee o o he ypes o
acili ies which may no be conside ed as poin s (see [11,7] o a su ey o his li e a u e). Examples o p oblems in
which s uc u es ins ead o poin s a e equi ed include he loca ion o pipelines, e acua ion ou es, mass ansi ou es o
ou ing a highway h ough a oad ne wo k. Fo he op imal selec ion o a si e in which o loca e an ex ensi e acili y he
c i e ia used a e, in almos all cases, he minimax c i e ion, he minisum c i e ion o a co e ing model, (see [6,12–16]). In
addi ion, al hough mos o hese p oblems can be sol ed in polynomial ime in ee ne wo ks, hey a e NP-ha d in cyclic
ne wo ks (see [4] o an analysis o he complexi y o hese p oblems). Fo his eason he main eDo has been o ien a ed
o design e@cien algo i hms o sol e he a o emen ioned p oblems in ee ne wo ks. In pa icula he pa h-cen e and he
pa h-median (o co e) o a ee (which a ise om he applica ion o he minimax c i e ion and he minisum c i e ion,
espec i ely) can be ound by means o linea ime algo i hms (see [15,13]).
The abo e discussion shows ha he equi y (as sui able objec i e) has no been conside ed in he c i e ia used hi he o
in he loca ion o ex ensi e acili ies. Howe e , in ce ain public sec o p oblems, an equi y c i e ion is needed o gene a e
accep able decisions. The a iance o dis ance a elled by all cus ome s o he acili y has been an equi y c i e ia widely
s udied in poin loca ion p oblems. The pu pose o his wo k is o apply his c i e ion o loca ing a pa h-shaped acili y in
a ee ne wo k. This p oblem, which will be called he Pa h-Va iance P oblem, will be s udied in he con inuous e sion
in which pa ial edges a e allowed, ha is, when he ex eme poin s o he pa h can be in e io poin s o an edge. In
gene al hese ex eme poin s will belong o diDe en edges. Howe e , he case in which bo h poin s a e in he same edge
will be analyzed sepa a ely, since his gi es ise o he pa icula case in which he pa h degene a es o a single poin .
The emainde o he pape is o ganized as ollows. In he nex sec ion he o mula ion o he p oblem is in oduced and
p ope ies o he objec i e unc ion when he ex eme poin s belong o diDe en edges a e s udied. Sec ion 3is de o ed
o he case in which he ex eme poin s o he pa h belong o he same edge. In o de o design he algo i hm o he
p oblem, a da a s uc u e o desc ibe he ee is inco po a ed a he beginning o Sec ion 4. In ha sec ion he algo i hm
is also p oposed, and i s complexi y is discussed.
2. The pa h- a iance p oblem on die en edges
Le T=(V; E) be an undi ec ed ee ne wo k wi h e ex se V={ 1;:::;
n}, edge se E, and edge leng hs {lj:ej∈E}.
Deno e by T he se o poin s in Twhich comp ises bo h se Vand he se o all he poin s on edges. We will conside
pa hs no only con aining comple e edges bu also pa ial edges, and hey will be deno ed as P(x1;x
2) in which x1;x
2∈T
a e he end poin s o he pa h. I P(x1;x
2)⊂Tis a pa h, hen d(x; P) = miny∈Pd(x; y), whe e d(x; y):x; y ∈T,is he
dis ance be ween poin s gi en by he leng h o he only pa h joining xand y, which makes Ta me ic space.
We suppose ha demand o igina es a he e ices o he ee, and we associa e a posi i e weigh wiwi h each e ex
i∈V. Wi hou loss o gene ali y we may assume ha n
i=1 wi= 1 and in e p e each wias he ac ion o demand
o igina ed a i. Fo a subse o e ices V⊂Vle W(V)= i∈Vwibe he weigh o V, and le W(V)= i∈V V
wi=1−W(V) be he weigh o he complemen o Vin V.
Fo any poin x∈T, he median unc ion (dis ancesum) o xo e V⊂Vis gi en by zm(x; V )= i∈Vwid( i;x).
Simila ly he median unc ion o a pa h P(x1;x
2)inV⊆Vis gi en by zm(P(x1;x
2);V)= i∈Vwid( i;P(x1;x
2)). Fo
simplici y, when V=Vwe will use zm(x) and zm(P(x1;x
2)) ins ead o zm(x; V ) and zm(P(x1;x
2);V), espec i ely.
The a iance unc ion o a pa h P(x1;x
2) is de;ned as
zs(P(x1;x
2)) =
n

i=1
wi[d( i;P(x1;x
2)) −zm(P(x1;x
2)]2:
The Con inuous Pa h-Va iance P oblem (CPVP) consis s o ;nding poin s x1;x
2such ha he pa h joining hese poin s
minimises he unc ion zson all he pa hs P⊂T.
Gi en a pai o edges ej;e
k he Con inuous Pa h-Va iance P oblem Res ic ed o (ej;e
k), (CPVP)jk , is ha o min-
imising he es ic ed unc ion zs(P(x1;x
2)), whe e x1∈ej,x2∈ek, whose domain is [0;l
j]×[0;l
k]. Consequen ly a solu ion
o he p oblem (CPVP)jk is a pai (x∗
1;x
∗
2)∈[0;l
j]×[0;l
k] such ha
zs(P(x∗
1;x
∗
2)) 6zs(P(x1;x
2));∀(x1;x
2)∈[0;l
j]×[0;l
k]:
As usual when an edge ejis ;xed, any eal numbe x∈[0;l
j] will deno e he poin on he edge whose exac loca ion
is de e mined by i s dis ance (along he edge) om a p esc ibed endpoin o he edge. In o de o a oid a decomposi ion
in o wo cases, and he e o e he subsequen case analysis, he e e ence e ices o measu e dis ances be ween any wo
poin s x1∈ej=(uj;
j) and x2∈ek=(uk;
k) will be he a hes e ices among hose o bo h edges. We will suppose
ha ujand ka e hese a hes e ices, consequen ly x1∈ejmeans he leng h o subedge (uj;x
1) and x2∈ekmeans he
leng h o subedge ( k;x
2).
Fo a e ex uo edges ej;e
k, le Vudeno e he e ex se o he sub ee Tu oo ed a uwhich does no con ain he
edge ejno ekwhich is inciden o u.W(Vu)= i∈V
uwiis he o al weigh o Vuand W(Vu)=1−W(Vu) is he weigh
o he complemen a y e ex se . In acco dance wi h his no a ion, Tujand T kwill ep esen he sub ees oo ed a he
a hes e ices ujand k espec i ely, and do no con ain he edges ejand ek(and he e o e nei he do hey con ain he
pa h P(x1;x
2)).
Likewise we deno e by V(P(x1;x
2)) he e ex se o he pa h P(x1;x
2) and by T1;T
2;:::;T
he connec ed componen s
(sub ees) ha esul om he dele ion o V(P(x1;x
2)) and he co esponding inciden edges om he ee T (Tuj∪T k).
Then he median unc ion o he pa h P(x1;x
2)is
zm(P(x1;x
2)) = 
i∈V
wid( i;P(x1;x
2)) = 
i∈V
uj
wi[d( i;u
j)+x1]
+

h=1 

i∈V
h
wid( i;P(x1;x
2))
+
i∈V
k
wi[d( i;
k)+x2]
=zm(P(uj;
k)) + W(Vuj)x1+W(V k)x2:
In he ollowing we will deno e by zm(P) he alue zm(P(uj;
k)).
The a iance o he pa h P(x1;x
2) can be decomposed in he ollowing manne :
zs(P(x1;x
2)) = 
i∈V
uj
wi[(d( i;u
j)−zm(P))2+(W(Vuj))2x2
1
+(W(V k))2x2
2+2(d( i;u
j)−zm(P))W(Vuj)x1
−2(d( i;u
j)−zm(P))W(V k)x2−2W(Vuj)W(V k)x1x2]
+

h=1 

i∈V
h
wi[(d( i;P)−zm(P))2+(W(Vuj))2x2
1+(W(V k))2x2
2
−2(d( i;P)−zm(P))W(Vuj)x1−2(d( i;P)−zm(P))W(V k)x2
+2W(Vuj)W(V k)x1x2]
+
i∈V
k
wi[(d( i;
k)−zm(P))2+(W(Vuj))2x2
1+(W(V k))2x2
2
+2(d( i;
k)−zm(P))W(V k)x2−2(d( i;
k)−zm(P))W(Vuj)x1
−2W(V k)W(Vuj)x1x2]:
By associa ing e ms wi h equal deg ee,
zs(P(x1;x
2)) = W(Vuj)W(Vuj)x2
1+W(V k)W(V k)x2
2
−2W(Vuj)W(V k)x1x2
+2(zm(uj;V
uj)−W(Vuj)zm(P))x1
+2(zm( k;V
k)−W(V k)zm(P))x2+zs(P):(1)
By imposing he necessa y condi ions o s a iona y poin s he ollowing sys em esul s:
W(Vuj)W(Vuj)x1−W(Vuj)W(V k)x2+(zm(uj;V
uj)−W(Vuj)zm(P))=0;
W(Vuk)W(Vuk)x2−W(Vuj)W(V k)x1+(zm( k;V
k)−W(V k)zm(P))=0:
Le W(P)= i∈V(P(x1;x2)) wibe he weigh o he e ex se o he pa h P(x1;x
2). Clea ly W(P)¿0 since he se
V(P(x1;x
2)) is no emp y when he ex eme poin s x1;x
2o he pa h belong o diDe en edges. By simpli ying he unique
solu ion o he las sys em, we ob ain
x1=1
W(P)zm(P)−zm( k;V
k)−zm(uj;V
uj)W(V k)
W(Vuj)
x2=1
W(P)zm(P)−zm(uj;V
uj)−zm( k;V
k)W(Vuj)
W(V k):(2)
Fu he mo e, 0 6x16ljand 0 6x26lkmus hold.
The Hessian ma ix is
H=2W(Vuj)W(Vuj)−W(Vuj)W(V k)
−W(Vuj)W(V k)2W(V k)W(V k):
Since W(Vuj)=W(P)+W(Vuk) and W(Vuk)=W(P)+W(Vuj), hen
|H|=W(Vuj)W(V k)(4W(Vuj)W(V k)−W(Vuj)W(V k)) ¿0
and also 2W(Vuj)W(Vuj)¿0.
The e o e, he Hessian ma ix is de;ni e posi i e, which gua an ees ha he a iance unc ion is s ic ly con ex on he
compac se [0;l
j]×[0;l
k] and he s a iona y poin gi en by (2) is he minimum, which implies ha i is he solu ion
(x∗
1;x
∗
2) o he es ic ed p oblem (CPVP)jk .
When he minimum (x1;x
2) does no belong o he abo e compac se hen he op imum is eached in he bounda y.
The e a e se e al cases.
(1) I x160 and 0 6x26lk hen he minimum (x∗
1;x
∗
2) o he es ic ed p oblem is eached a he poin
0;W(V k)zm(P)−zm( k;V
k)
W(V k)W(V k):
(2) I x1¿ljand 0 6x26lk hen he op imum is
lj;W(V k)(zm(P)+W(Vuj)lj)−zm( k;V
k)
W(V k)W(V k):
(3) I x260 and 0 6x16lj hen he minimum is gi en by
W(Vuj)zm(P)−zm(uj;V
uj)
W(Vuj)W(Vuj);0:
(4) I x2¿lkand 0 6x16lj hen
W(Vuj)(W(V k)lk+zm(P)) −zm(uj;V
uj)
W(Vuj)W(Vuj);l
k:
(5) Finally,
(x∗
1;x
∗
2)=












(lj;0) i x1¿ljand x260;
(0;0) i x160 and x260;
(lj;l
k)i x1¿ljand x2¿lk;
(0;l
k)i x160 and x2¿lk:
3. The pa h- a iance p oblem on an edge
In his sec ion he pa h loca ion p oblem, in which he wo ends o he pa h a e in he same edge, is conside ed.
We a e looking o he pa h ha minimises he a iance unc ion zs(P(x1;x
2)) among hose pa hs P(x1;x
2) such ha
x1;x
2∈ej=(uj;
j). Following he no a ion in oduced in he p e ious sec ion, ujand ja e now he a hes e ices.
Consequen ly x1,x2 ep esen he leng hs o he subedges (uj;x
1) and ( j;x
2), espec i ely, and i Vuj,V ja e he e ex
se s o he sub ees Tuj,T j oo ed a uj, j, espec i ely, which do no con ain he edge ej, hen hey a e complemen a y
e ex se s, i.e. Vuj∪V j=V. This implies ha W(P) = 0, which jus i;es a sepa a e s udy o his case.
The exp ession o he median unc ion is he same as in he p e ious case, zm(P(x1;x
2))=zm(P(uj;
j))+W(Vuj)x1+
W(V j)x2. By using he simpli;ed no a ion zm(P) and zs(P) ins ead o zm(P(uj;
j)) and zs(P(uj;
j)), espec i ely, and
aking in o accoun ha Vuj=V j, he a iance unc ion can be w i en as ollows:
zs(P(x1;x
2)) = W(Vuj)W(V j)x2
1+W(Vuj)W(V j)x2
2
−2W(Vuj)W(V j)x1x2+2{zm(uj;V
uj)−W(Vuj)zm(P)}x1
+2{zm( j;V
j)−W(V j)zm(P)}x2+zs(P)=W(Vuj)W(V j)[x1−x2]2
+2{zm(uj;V
uj)W(V j)−zm( j;V
j)W(Vuj)}[x1−x2]+zs(P):
Fig. 1.
I can be seen ha when x1=x2(i.e. he pa h degene a es o he medium poin o he edge), hen he alue zs(P(x1;x
2))
coincides wi h he a iance zs(P) o he comple e edge. Mo eo e , he edge a iance also coincides wi h he a iance o
any pa h cen e ed a he medium poin and con ained in he edge. The necessa y condi ions o s a iona y poin s gi e ise
o he ollowing sys em:
W(Vuj)W(V j)(x1−x2)+(zm(uj;V
uj)−W(Vuj)zm(P))=0;
W(Vuj)W(V j)(x2−x1)+(zm( j;V
j)−W(V j)zm(P))=0;
in which zm(uj;V
uj)−W(Vuj)zm(P)=W(V j)zm(P)−zm( j;V
j), since zm(P)=zm(uj;V
uj)+zm( j;V
j) and W(Vuj)+W(V j)=1.
This implies ha he sys em is unde e mined compa ible, and i p o ides he only condi ion gi en by
x1−x2=zm(P)
W(V j)−zm(uj;V
uj)
W(Vuj)W(V j)
o equi alen ly
x1−x2=zm( j;V
j)
W(V j)−zm(uj;V
uj)
W(Vuj)=K; (3)
wi h 0 6x16lj,06x26lj, and 0 6x1+x26lj.
Since he Hessian ma ix is also de;ni e posi i e he s a iona y poin s a e minima. In acco dance wi h hese exp essions,
he ollowing cases can be conside ed (see Fig. 1).
Case 1: I −lj¡K¡l
j hen any pa h o which
x1−x2=K; 0¡x
1+x2¡l
j;0¡x
16x2¡l
j
is a pa h o minimum a iance whose a iance alue is:
zs(P(x1;x
2)) = zs(P)+K2W(Vuj)W(V j)
+2K{W(V j)zm(uj;V
uj)−W(Vuj)zm( j;V
j)}
=zs(P)−[zm( j;V
j)W(Vuj)−zm(uj;V
uj)W(V j)]2
W(Vuj)W(V j)
=zs(P)−K2W(Vuj)W(V j):
Le us no e ha he poin (x1;x
2)∈[0;l
j]×[0;l
j] such ha
x1+x2=lj;x
1−x2=K
is he poin o minimum a iance o his edge.
Case 2: I K¿lj hen he pa h degene a es o he poin j, which co esponds o he pai (lj;0), and also is he poin
o minimum a iance o he edge.
Case 3: I K6−lj hen he pa h educes o he poin o minimum a iance o he edge, uj.

Fig. 2.
4. Algo i hm and complexi y
Fo each pai o edges ej,ek, he de e mina ion o he local op imum x1;x
2ei he by (2) and subsequen exp essions
(i j=k)o by(3) and subsequen exp essions (i j=k), equi es he p e ious compu a ion o a se o auxilia y alues
associa ed o each e ex uas well as he e alua ion o he unc ion zmon he pa h joining he a hes e ices o he
edges ejand ek. In o de o ob ain all hese alues he ecu si e p ocedu e designed by Maimon [9] will be applied.
Le be he oo wi h sons 1;:::;
s,(s¿0), (i.e. he e exis s an edge ( i;
)∈E o each i=1;:::;s). A pos o de
a e sal o Tis de;ned ecu si ely as ollows:
(1) Visi in pos o de he sub ees wi h oo s 1;:::;
sin ha o de .
(2) Visi he oo .
The pos o de de;ned in Tinduces he ollowing o de o edges o E:
(u1;
(1));(u2;
(2));:::;(un−1;
);
whe e each (i)is he a he o uiin he pos o de , and o each wo edges ej=(uj;
(j)) and ek=(uk;
(k)), k¿j means
ha (k)can be (no necessa ily) a common ances o o he emaining h ee e ices.
This ac p o ides an iden i;ca ion o he a hes e ices o pai ej=(uj;
(j));e
k=(uk;
(k)) (wi h k¿j) as ollows
(see Fig. 2).
Case (i): I (j)is a descendan o uk( ha is, (j)∈Vukin he de;ned pos o de ), hen uj;
(k)a e he a hes e ices.
In his case, he e ices belonging o P=P(uj;
(k)) can be ound by successi ely adding he e ex a he o each e ex
son (s a ing wi h he ; s son uj, and ending wi h he las a he (k)).
Case (ii): O he wise, he a hes e ices a e uj;u
k. In his case, uj;u
kha e a common ances o ∗, which can be ei he
one o he a he s (j);
(k)(o bo h, i hey coincide), o a e ex no in ej;e
k. In his las case, he pa h Pjoining
uj;u
kcan be ound by a bina y sea ch among he a he s o he e ices uj;u
kas ollows: s a ing wi h ujand uk, he
successi e a he s a e es ed (and added o pa h P=P(uj;u
k)) un il a common a he ∗is ound).
I kdeno es he a hes e ex om uj(whe e as we ha e al eady seen, kcan be ei he (k)o uk), he poin x2in
he edge ekis iden i;ed by i s dis ance om k. No e ha in case (i) he iden i;ca ion o he second poin when using
he pos o de can be ob ained om ha used in Sec ion 2, by applying he simple change x
2=lk−x2. Howe e , he poin
x1in he edge ejis always iden i;ed by i s dis ance om he lowe e ex ujo he edge.
I Tu=(Vu;E
u) deno es (in he pos o de ) he sub ee oo ed in each u∈V, he necessa y e ex in o ma ion o
compu ing he local op imum (x∗
1;x
∗
2) can be de e mined in a p ep ocessing phase, in which he ee is wice a e sed
ollowing he pos o de ( owa d he oo o he ee and con e sely). By applying he ecu si e ela ionships o Maimon
[9], a he end o his phase he a o emen ioned e ex in o ma ion is a ailable. This in o ma ion (accumula ed in a ec o
o auxilia y alues associa ed o each e ex) is:
W(Vu);z
m(u; Vu);z
m(u);z(2)
m(u; Vu);z(2)
m(u);
whe e z(2)
m(u; Vu)= i∈V
uwid( i;u)2, and z(2)
m(u)=z(2)
m(u; V ). I is easy o see ha o a pa h P
zs(P)=
i∈V
wid( i;P)2−
i∈V
wid( i;P)2
=z(2)
m(P)−(zm(P))2:
The e o e he a o emen ioned auxilia y alues will be necessa y o compu ing zs(P).
I Vu=V Vu, and Suis he se o sons o uand i s a he , he se C(u)=Su∪{ }con ains all he nea es
e ices ( om u) in he connec ed componen s ob ained by dele ing uand he inciden edges. The p ep ocessing phase
also p o ides he alues associa ed o he connec ed componen s whose nea es e ices belong o Su:
{W(Vui);z
m(ui;V
ui);z(2)
m(ui;V
ui)∀ui∈Su}
as well as he alues associa ed o he connec ed componen a he :
W(Vu)=1−W(Vu);
zm( ; V u)=zm(u)−zm(u; Vu)−lu (1 −W(Vu));
z(2)
m( ; V u)=z(2)
m(u)−z(2)
m(u; Vu)−l2
u W(Vu)−2lu zm( ; V u):
The knowledge o hese auxilia y alues allows us o ob ain zm(P) and z(2)
m(P) by means o a p og essi e p ocedu e.
Le P=P(uj;
k) be he pa h joining he a hes e ices in he pai o edges {ej;e
k};k¿j, le V(P) be he e ex
se o he pa h Pand le C(uj)={uj1;:::;u
js};C( k)={ k1;:::;
k }be he espec i e nea es e ices in he connec ed
componen s associa ed o uj;
k. Ini ially
zm(P)=zm(uj)−
uji∈C(uj)∩V(P)
zm(uj;T
uji)+zm( k)−
ki∈C( k)∩V(P)
zm( i;T
kj):
When a e ex is added o Pacco ding o he a o emen ioned desc ibed cases (i) o (ii), he alues o zm(P) and
z(2)
m(P) a e successi ely upda ed by adding he co esponding auxilia y alues o in he connec ed componen s whose
nea es e ices a e no in P:
zm(P)←zm(P)+zm( )−

i∈C( )∩V(P)
zm( ;T

i):
No e ha he ca dinali y o he se C( )∩V(P) is bounded by 2 (since he e exis s a mos wo e ices in Pwhich a e
adjacen s o ). Likewise, z(2)
m(P) is ob ained by he same p ocedu e by conside ing z(2)
mins ead o zm.
Finally, be o e desc ibing he pseudocode o he algo i hm, i is necessa y o make some obse a ions wi h espec o
he alue W(V k) which appea s in he exp ession (2). Fo a gi en pai o edges ej=(uj;
(j));e
k=(uk;
(k)) whose
a hes e ices a e uj;
k, o he case (ii) W(V k) coincides wi h he auxilia y alue p o ided by he pos o de , ha
is : W(V k)=1−W(V k). Howe e , in he case (i) such a alue ep esen s he weigh o he connec ed componen
associa ed o kwhose nea es e ex is uk, ha is, uk∈C( k)∩V(P). The e o e, in he case (i), W(V k)=W(V(Tuk)),
and W(V k)=1−W(V k). Thus, he pseudocode o he algo i hm is as ollows:
Inpu : A ee ne wo k gi en by a pos o de a e sal.
P ep ocessing phase
Fo (u∈V)do
Compu e he auxilia y alues.
end o
Le Zbe a sui able la ge numbe .
Main s ep
Fo (j=1 o n−1) do
Fo (k=j o n−1) do
I (k¿j) hen
By a bina y sea ch de e mine he e ex se o
P=P(uj;
k) and simul aneously compu e
zm(P) and z(2)
m(P).
Compu e zs(P)=z(2)
m(P)−(zm(P))2.
Compu e he poin (x∗
1;x
∗
2) (by applying (2) and
subsequen ela ionships).
O he wise (k=j) hen
Compu e (x∗
1;x
∗
2) (by applying (3) and
subsequen ela ionships).
endi
Compu e zs=zs(P(x∗
1;x
∗
2)).
I (zs¡Z) hen
P∗←P(x∗
1;x
∗
2), Z←zs.
endi
end o
end o
Ou pu : The pa h P∗=P(x∗
1;x
∗
2) ha minimises he a iance and Z=zs(P∗).
Fo each conside ed pa h, ob aining he op imum equi es iden i ying and adding a se o auxilia y alues associa ed
o he co esponding nodes o he pa h. By using he pos o de s uc u e, such nodes (and hei auxilia y alues) a e
added by means o a bina y sea ch p ocess o e he se o a he s. Since he complexi y o he bina y sea ch is O(log n)
(see [1]) and n2pa hs a e es ed, he o e all complexi y o he algo i hm is O(n2log n) ime.
Acknowledgemen s
The au ho s a e pa ially suppo ed by P ojec : MCyT BFM2000-1052-C02-01.
Re e ences
[1] A. Aho, J. Hopc o , J. Ullman, Da a S uc u es and Algo i hms, Addison-Wesley, Reading, MA, 1983.
[2] H.A. Eisel , G. Lapo e, Objec i es in loca ion p oblems, in: Z i D ezne (Ed.), Facili y Loca ion: A Su ey o Applica ions and
Me hods, Sp inge Se ies in Ope a ions Resea ch, Sp inge , New Yo k, 1995, pp. 151–180.
[3] E. E ku , Inequali y measu es o loca ion p oblems, Loca ion Sci. 1 (1993) 199–217.
[4] S.L. Hakimi, E.F. Schmeichel, M. Labb%e, On loca ing pa h o ee-shaped acili ies on ne wo ks, Ne wo ks 23 (1993) 543–555.
[5] P. Hansen, M. Zheng, An algo i hm o he minimum a iance poin o a ne wo k, RAIRO Ope a ions Resea ch/Reche che
Op%e a ionnelle 25 (1991) 119–126.
[6] R.K. Kincaid, T.J. Lowe, T.L. Mo in, The loca ion o cen al s uc u es in ees, Compu . Ope . Res. 15 (1988) 103–113.
[7] M. Labb%e, G. Lapo e, I. Rod %
Qguez-Ma %
Qn, Pa h, ee and cycle loca ion, in: T.G. C ainic, G. Lapo e (Eds.), Flee Managemen
and Logis ics, Kluwe , Bos on, 1998, pp. 187–204.
[8] M.C. L%opez de los Mozos, J.A. Mesa, The a iance loca ion p oblem on a ne wo k wi h con inuously dis ibu ed demand, RAIRO
Ope a ions Resea ch/Reche che Op%e a ionnelle 34 (2000) 155–181.
[9] O. Maimon, The a iance equi y measu e in loca ional decision heo y, Ann. Ope . Res. 6 (1986) 147–160.
[10] M.T. Ma sh, D.A. Schilling, Equi y measu emen in acili y loca ion analysis: A e iew and amewo k, Eu opean J. Ope . Res. 74
(1994) 1–17.
[11] J.A. Mesa, T.B. BoDey, A e iew o ex ensi e acili y loca ion in ne wo ks, Eu opean J. Ope . Res. 95 (1996) 592–603.
[12] E. Minieka, The op imal loca ion o a pa h o ee in a ee ne wo k, Ne wo ks 15 (1985) 309–321.
[13] C.A. Mo gan, P.J. Sla e , A linea algo i hm o a co e o a ee, J. Algo i hms 1 (1980) 247–248.
[14] S. Peng, A.B. S ephens, Y. Yesha, Algo i hms o a co e and k- ee co e o a ee, J. Algo i hms 15 (1993) 143–159.
[15] P.J. Sla e , Loca ing cen al pa hs in a g aph, T anspo a ion Sci. 16 (1982) 1–18.
[16] P.J. Sla e , Some de;ni ions o cen al s uc u es, Lec u e No es in Ma hema ics, Vol. 1073, Sp inge , Be lin, 1984, pp. 169–178.