Loca ing Two T ans e Poin s on a Ne wo k wi h a T ip
Co e ing C i e ion and Mixed Dis ances
M.C. L´opez-de-los-Mozos ∗Juan A. Mesa †Ani a Sch¨obel ‡
Abs ac
In his pape we conside a se o o igin-des ina ion pai s in a mixed model in which a
ne wo k embedded in he plane ep esen s an al e na i e high-speed anspo a ion sys em,
and s udy a ip co e ing p oblem which consis s on loca ing wo poin s in he ne wo k
which maximize he numbe o co e ed pai s, ha is, he numbe o pai s which use he
ne wo k by acceding and exi ing h ough such poin s. To deal wi h he absence o con exi y
o his mixed dis ance unc ion we p opose a decomposi ion me hod based on o mula ing
a collec ion o subp oblems and sol ing each o hem ia disc e iza ion o he solu ion se .
Keywo ds: Loca ion; Ne wo k; Co e ing P oblem; Mixed Dis ances
1 In oduc ion
In a p e ious pape [5], a loca ion p oblem on a mixed plana -ne wo k space was ackled. In
he p oblem deal wi h in ha pape , he e a e exis ing acili ies in he Euclidean plane whe eas
new acili ies a e o be loca ed in a s aigh -line segmen o in a ee ne wo k. Ins ead o co e ing
acili ies he objec i e aims a co e ing ips be ween each pai o exis ing acili ies. These ips
can be done ei he by using he plane wi h he Euclidean dis ance o by a combina ion plane-
ne wo k in which he sec ion on he ne wo k is supposed o be a e sed as e han hose
on he plane. The e o e, he e is a compe i ion be ween he mode ha only uses he plana
dis ance and he combined one. Each pai o exis ing acili ies has an associa ed demand and
he objec i e is o maximize he numbe o ips o which he combined mode is p e e able
o he plana one. In his pape we ex end he app oach applied in [5] o he case o gene al
ne wo ks by aking in o accoun he loss o con exi y o he dis ance unc ion be ween pai s o
poin s h ough he ne wo k.
The p oblem o loca ing s a ions in a ailway ne wo k was indi ec ly ackled in [13], in which
hey conside ed he p oblem o op imal in e s a ion spacing in a commu e line. The objec i e
o his p oblem was o minimize he o al ime o passenge s going o a ci y cen e along a
ailway line. A commu e line compe ing wi h a eeway was conside ed in [14] in o de o
maximize he numbe o passenge s on he basis i he sho es a el ime. The aim was also
o de e mine he op imal in e s a ion space be ween pai s o adjacen s a ions. Apa om
he pape s [6, 7] in which he easible solu ion space o loca ing s a ions was disc e e, and
he objec i e was o maximize he passenge s and ip co e age, espec i ely, se e al objec i e
unc ions ha e been conside ed in hose in which s a ions can be loca ed along he edges o he
ailway ne wo k ([2, 10, 11, 8]).
In o de o a oid duplica ions he eade is e e ed o he In oduc ion o he pape [5] o
an o e iew o o he ela ed pape s.
∗Dp o. Ma em´a ica Aplicada I. Uni e sidad de Se illa, Spain. [email p o ec ed]
†Dp o. Ma em´a ica Aplicada II. Uni e sidad de Se illa, Spain. j[email p o ec ed]
‡Ins i u ¨u Nume ische and Angewand e Ma hema ik. Uni e si ¨a G¨o ingen, Ge many.
schoeb[email p o ec ed]goe ingen.de
1
The case o loca ing only one acili y ega ding ans e acili ies al eady loca ed in he
ne wo k is a pa icula case o ha deal wi h in his pape and can be ca ego ized as a
condi ional loca ion p oblem. Thus, adding he ex a demand cap u ed by bo h pai s consis ing
o a new acili y and an al eady loca ed one, and hose consis ing o wo new acili ies, he global
con ibu ion o he wo new ans e poin s is compu ed.
The pape is o ganized as ollows. A e his in oduc ion he p oblem is o mula ed in
Sec ion 2. The necessa y de ini ions and esul s on he dis ance on ne wo ks a e summa ized in
Sec ion 3. Sec ion 4 is de o ed o sol e he wo cases a isen om he p ope ies o he dis ance.
The pape ends wi h some conclusions and u he esea ch.
2 The p oblem
He eina e we will use he no a ion in oduced by [5]. Le A={Ai= (ai, bi), i =
1,...,n} ⊂ IR2be a se o exis ing acili ies on he plane. We assume ha a el ime dis-
ances be ween wo poin s in he plane can be es ima ed by he Euclidean me ic.
Le T= ( ij )∈IRn×nbe an o igin-des ina ion (O/D) ma ix in which ip pa e ns a e
codi ied, i.e., ij is he weigh o he o de ed pai (Ai, Aj) (o (i, j), i he e is no con usion).
This ma ix is known a p io i: o example, in a anspo a ion con ex each ij can be iewed
as he numbe o ips om an o igin Ai o a des ina ion Aj, and in a elecommunica ion se ing
i could ep esen he amoun o da a ans e ed om se e i o se e j.
In o de o o mula e he p oblem wi h a mixed mode o anspo a ion, we conside an
embedded ne wo k N(V, E) ep esen ing a high-speed sys em, wi h |V| e ices and |E|edges.
Each e ex ∈V ep esen s a junc ion o a node, and we assume ha each undi ec ed edge
e∈Ehas a leng h leand i can be modeled as a s aigh -line segmen . The embedding o N
in he Euclidean plane as well as he coo dina es o he nodes in Nwill allow us o compu e
he a el dis ances be ween each pai o poin s. Le Nbe he con inuum se o poin s on
he edges. The edge leng hs induce a dis ance unc ion don N, such ha o any wo poin s
x, y ∈ N,d(x, y) is he leng h o any sho es pa h connec ing xand y. Mo eo e , i xand y
a e on he same edge, d(x, y) = ||x−y||.
Fo any wo poin s x, y ∈ N, le us de ine he high-speed dis ance dN(x, y) = αd(x, y), wi h
α∈(0,1). Pa ame e αis a speed ac o . I is s aigh o wa d o see ha (N, dN) is a me ic
space.
Gi en an O/D pai (i, j), he anspo a ion ime by using he ne wo k is ob ained by
selec ing wo poin s X1∈ N and X2∈ N (o a 2- acili y poin (X1, X2)∈ N2) such ha he
anspo a ion pa h om i o jen e s he ne wo k a one o such poin s and exi s he ne wo k
a he o he one. I X1is he access poin om Aiand X2 he exi poin owa ds Aj, he leng h
o he a el-pa h (Ai, X1, X2, Aj) is gi en by:
hij (X1, X2) = ||Ai−X1||2+dN(X1, X2) + ||X2−Aj||2
Mo eo e , i X2is he access poin om Aiand X1 he exi poin owa ds Aj, he leng h o he
a el-pa h (Ai, X2, X1, Aj) is
hij (X2, X1) = ||Ai−X2||2+dN(X2, X1) + ||X1−Aj||2
Al hough algeb aically hij(X1, X2) = hji(X2, X1) and hij (X2, X1) = hji(X1, X2), in his con-
ex he subindex ij indica es he o igin/des ina ion pai (i, j), which is di e en om he O/D
pai (j, i). Fo his eason, wi h each O/D pai (i, j) we only associa e he subindex ij.
The dis ance be ween he O/D pai (Ai, Aj) by using he ansi poin s X1, X2∈ N is:
ij (X1, X2) = min{hij(X1, X2), hij (X2, X1)}= ij(X2, X1)
Le D= (dij )∈IRn×nbe a symme ic ma ix, wi h 0 ≤dij <||Ai−Aj||2. The alues o D
ep esen he accep ance le els o using he ne wo k, meaning ha he O/D pai (i, j) chooses
2
he high-speed ne wo k i and only i he a eling ime by using i is less han o equal o dij .
In o he wo ds, he O/D pai s always choose he as e op ion.
De ini ion 1 The O/D pai (i, j) is co e ed by (X1, X2)∈ N2i and only i ij(X1, X2)≤dij.
Le C(X1, X2) be he se o O/D pai s co e ed by (X1, X2), ha is:
C(X1, X2) = {(Ai, Aj)∈ A×A : ij(X1, X2)≤dij }
Symme y o he accep ance le el ma ix and bo h he Euclidean and he ne wo k dis ances
implies ha (i, j)∈C(X1, X2) i and only i (j, i)∈C(X1, X2).
The objec i e unc ion measu es he amoun o ip pa e ns cap u ed by each 2- acili y-
poin (X1, X2)∈ N2, and i is gi en by he ip-sum unc ion:
F(X1, X2) = X
(i,j)∈C(X1,X2)
ij
Finally, he O/D-pai 2-loca ion p oblem is o ind a poin (X1, X2)∈ N2such ha he sum
o ip pa e ns o all O/D pai s co e ed by such a poin is maximized:
max F(X1, X2) := X
(i,j)∈C(X1,X2)
ij
s. . (X1, X2)∈ N2
(1)
The p oblem (1) has been i s sol ed o he pa icula case whe e Nis a segmen o a
s aigh line, and la e he me hod was ex ended o he case whe e Nis a ee ne wo k T(see
[5]). Howe e , he app oach applied o he ee ne wo k case canno be di ec ly ex ended o a
gene al ne wo k Ndue o he absence o con exi y o dis ance unc ions on a cyclic ne wo k.
I o de o sol e he p oblem, we nex summa ize some concep s on he beha io o dis ance
on ne wo ks.
3 P e ious esul s on dis ances on ne wo ks
Le e= [u, w]∈Ebe an edge o he ne wo k No leng h le=l(u, w), and le Pbe a
poin on e. Le x=l(u, P) be he leng h o he subedge om he le e ex u o P, and
l(w, P) = le−xbe he leng h o subedge [P, w]. I is well known ha o any node i∈V, he
dis ance d( i, P) = di(x) = min{d( i, u) + x, d( i, w) + le−x}is conca e and piecewise linea
on x∈[0, le], wi h a mos wo pieces wi h slopes 1 and −1. I l(u, w)≤ |d( i, u)−d( i, w)|,
hen he dis ance unc ion d( i, P) on [u, w] is linea . The ollowing concep s and de ini ions
can be ound in [3] and e e ences he ein.
De ini ion 2 Gi en a poin Q∈ N and an edge [u, w], he poin P∈[u, w] a which d(Q, P)
is maximized is called an ipodal o Qin [u, w].
No e ha i Pis an ipodal o Qdoes no imply ha Qis an ipodal o P; i i is Pand Q
a e an ipodal o each o he .
De ini ion 3 A poin ¯ i∈[u, w], o he han a node, is called an a c bo leneck poin i he e is
a e ex i o which ¯ iis an ipodal o i. In his case, d( i, u) + l(u, ¯ i) = d( i, w) + l(w, ¯ i).
Clea ly, [u, w] con ains a mos |V|a c bo leneck poin s (since each e ex ide ines a
mos one a c bo leneck poin ¯ ion he edge). Such a poin ¯ ican be iden i ied by he leng h
o he suba c [u, ¯ i] gi en by: l(u, ¯ i) = d( i, w)−d( i, u) + l(u, w)
2.
3
De ini ion 4 Le Bebe he se o a c bo leneck poin s o edge e= [u, w], and le ¯ i, ¯ jbe wo
adjacen poin s o Be∪{u, w}. Then Li= [¯ i,¯ j], he closed subedge limi ed by such poin s, is
called a linea a c segmen (o a eelike segmen [3]).
On each linea a c segmen he dis ance d( i, P) is linea . I Be=∅ he en i e edge [u, w]
(including nodes) is a linea a c segmen . The se o all linea a c segmen s o an edge eis
deno ed by L(e).
Le [up, wp] and [uq, wq] be wo edges o he ne wo k N, and le [ ¯wp,¯up]⊆[uq, wq], [ ¯wq,¯uq]⊆
[up, wp] be he subedges o which he ex eme poin s a e an ipodal poin s as ollows: ¯up,¯wp
a e he an ipodal poin s o up, wp espec i ely, and ¯uq,¯wqa e he an ipodal poin s o uq, wq,
espec i ely (see Figu e 1(a)). F om p e ious de ini ions we ha e l( ¯wq,¯uq) = l( ¯wp,¯up) and
d( ¯wq,¯wp) = d(¯uq,¯up) (see [3] o a mo e de ailed explana ion).
uq
upwp
wq
uq
wq
up
wp
u ww u
d(u, w)< l(u, w)
(a) (b)
Figu e 1. An ipodal poin s on: (a) di e en edges, (b) he same edge
De ini ion 5 Le Lp,Lqbe wo linea a c segmen s o di e en edges [up, wp] and [uq, wq],
espec i ely, and le [ ¯wq,¯uq]⊆[up, wp] and [ ¯wp,¯up]⊆[uq, wq] be he subedges o which ¯up,¯wp
a e he an ipodal poin s o up, wp espec i ely, and ¯uq,¯wqa e he an ipodal poin s o uq, wq,
espec i ely. I Lp⊆[ ¯wq,¯uq] and Lq⊆[ ¯wp,¯up], hen Lp,Lqa e called an ipodal segmen s o
each o he .
(This de ini ion includes he case [ ¯wq,¯uq] = [up, wp] and [ ¯wp,¯up] = [uq, wq]). The ollowing
esul summa izes he beha io o dis ance d(P, Q) on linea a c segmen s o di e en edges
(see Hooke , Ga inkel and Chen [3]).
Lemma 6 Le Pbe es ic ed o linea a c segmen Lpo edge [up, wp]and Q o linea a c
segmen Lqo edge [uq, wq], wi h [up, wp]6= [uq, wq].
1. I Lp, Lqa e an ipodal segmen s o each o he , d(P, Q)is conca e.
2. O he wise, d(P, Q)is linea .
In case 1, he dis ance be ween a poin Pon he segmen [ ¯wq,¯uq] and a poin Qon he
segmen [ ¯wp,¯up] beha es like he dis ance on he pa allelog am in Figu e 1(a), and i is conca e.
Dis ance on any o he pai o segmen s beha es like dis ance on a line segmen and is he e o e
linea .
By deno ing x=l(up, P), wi h x∈[0, l(up, wp)] and y=l(uq, Q), wi h y∈[0, l(uq, wq)], we
can compu e he dis ance d(P, Q) o he cases conside ed in his lemma.
d(P, Q) =









min{x+d(up, uq) + y, l(up, wp)−x+d(wp, wq) + l(uq, wq)−y}, Lp, Lqan ipodal
x+d(up, uq) + y, Lp⊆[up,¯wq], Lq⊆[uq,¯wp] o Lq⊆[ ¯wp,¯up]
x+d(up, wq) + l(uq, wq)−y, Lp⊆[up,¯wq], Lq⊆[¯up, wq]
4
No e ha in he case Lp, Lqan ipodal segmen s, wi h up6= ¯wq, ¯uq6=wpand simila ly uq6=
¯wp, ¯up6=wq, he dis ance d(P, Q) can also be compu ed by min{x+d(up, wq) + l(uq, wq)−
y, l(up, wp)−x+d(wp, uq)+y}. Finally, he emaining cases ob ained by combining Lp, Lqcan
be educed o one o hese by symme y ( o example, o he case Lp⊆[up,¯wq], Lq⊆[¯up, wq]
he dis ance can also be equi alen ly ob ained as l(up, wp)−x+d(wp, uq) + y).
We now s udy he case in which P, Q lie on he same edge [u, w], wi h d(u, w)≤l(u, w). Le
¯u, ¯wbe he an ipodal poin s o u, w espec i ely. The sequence {u, ¯w, ¯u, w}induces a pa i ion
o [u, w] in (a mos ) h ee consecu i e subedges: [u, ¯w], [ ¯w, ¯u] and [¯u, w] (Figu e 1(b)).
Lemma 7 Le Lp,Lqbe wo linea a c segmen s o [u, w]such ha Pis es ic ed o Lpand
Qis es ic ed o Lq.
1. I Lp=Lq he dis ance d(P, Q)is con ex.
2. I Lp6=Lq, and Lp,Lqlie espec i ely in non-adjacen subedges o he pa i ion, d(P, Q)
is conca e.
3. O he wise, d(P, Q)is linea .
Clea ly, i Lp=Lq he dis ance d(P, Q) is con ex because he a c segmen be ween Pand Q
is he sho es pa h be ween hem, and i is conca e i Lp⊆[u, ¯w], Lq⊆[¯u, w] (o ice- e sa),
wi h ¯w6= ¯u(which a ises when d(u, w)< l(u, w), ha is, when he edge [u, w] is no he sho es
pa h be ween u, w, as in Figu e 1(b)). As abo e, by deno ing x=l(u, P) and y=l(u, Q), we
ha e:
d(P, Q) =









|x−y|, Lp=Lq
min{y−x, x +d(u, w) + l(u, w)−y}, Lp⊆[u, ¯w], Lq⊆[¯u, w],¯w6= ¯u
|y−x|,o he wise
No e ha in he hi d case, he dis ance |y−x|becomes linea , acco ding wi h he o de in
which Lpand Lqa e placed. I d(u, w) = l(u, w), hen u= ¯wand ¯u=w, he e o e he dis ance
d(P, Q) is con ex (i Lp=Lq), o linea (i Lp6=Lq).
4 Sol ing he p oblem on a ne wo k
The solu ion me hod is based on decomposing he p oblem (1) in a collec ion o subp oblems
independen o each o he , and sol ing each o hem ia disc e iza ion o he solu ion se . To his
end and wi h pu poses o eadabili y, we will desc ibe he p ocess in h ee phases: he i s one
is de o ed o bo h decomposing he p oblem (1) and iden i ying he wo ype o subp oblems,
he second one deals wi h he subp oblems o ype 1, and inally in he las s ep we will s udy
he subp oblems o ype 2. Nex i will be desc ibed bo h ype o subp oblems.
4.1 Decomposing he p oblem
To decompose he p oblem we i s need he ma ix ∆ = (d( i, j))i,j o sho es dis ances
be ween all pai s o nodes o he ne wo k N. This ma ix can be calcula ed in O(|V||E|)
unning ime. Then, o each edge e∈Ewe compu e, and so , he a c bo leneck poin s o
he se Be(in O(|V|log |V|) ime). A he end o his p ocess we ha e, o each edge eo he
ne wo k, he o de ed sequence L(e) o all linea a c segmen s o he edge. Besides, gi en a pai
o di e en edges ep= [up, wp] and eq= [uq, wq] we know i wo linea a c segmen s Lp∈ L(ep)
and Lq∈ L(eq) a e, o no , an ipodal o each o he . I epand eqa e he same edge e= [u, w]
(which is he case o Lemma 7), we also know he loca ion o he linea a c segmen s on he
subedges o he pa i ion induced by {u, ¯w, ¯u, w}.
5

Le L=[
e∈EL(e) be he se o all linea a c segmen s o he o e all ne wo k. Thus p oblem
(1) is decomposed in o a se o subp oblems, whe e each o hem is ob ained by es ic ing he
easible space N × N o Lp×Lq, wi h Lp, Lq∈ L. By imposing ha X1∈Lp,X2∈Lqwe
ob ain he es ic ed p oblem:
max F(X1, X2) := X
(i,j)∈C(X1,X2)
ij
s. . (X1, X2)∈Lp×Lq, Lp, Lq∈ L
(2)
A solu ion o p oblem (1) is ound by sol ing he collec ion o all |L|2 es ic ed p oblems (2),
and hen selec ing he bes solu ion.
The classi ica ion o he es ic ed p oblem (2) is done acco ding o he conca i y o he
dis ance d(X1, X2). I d(X1, X2) is ei he linea o con ex, we classi y he es ic ed p oblem
as ype 2. O he wise, as ype 1. Mo e speci ically, conside he es ic ed p oblem o mula ed
in (2). Then he pai {Lp, Lq}is called o ype 1 i one o he ollowing wo condi ions holds:
(Lemma 6-1): Lp∈ L(ep), Lq∈ L(eq), wi h ep6=eq, and Lp,Lqa e an ipodal o each o he .
(Lemma 7-2): Lp, Lq∈ L(e), wi h e= [u, w] such ha d(u, w)< l(e), and Lp, Lqlie in no
adjacen subedges o pa i ion {u, ¯w, ¯u, w}.
Fo he emaining cases, he pai {Lp, Lq}is said o ype 2.
4.2 The conca e case: The es ic ed p oblem o ype 1
The p oblem can be o mula ed as ollows
max F(X1, X2) := X
(i,j)∈C(X1,X2)
ij
s. . (X1, X2)∈Lp×Lq
Lp, Lq∈ L,{Lp, Lq}o ype 1
(3)
Each linea a c segmen is a ec i iable subedge in which all dis ance unc ions d( i, P) a e
linea , and each e ex i∈Vlinks wi h all poin s o such subedge ia one o hei ex eme
poin s. On he o he hand, we ha e:
1. Fo each Ai∈ A, he Euclidean dis ance ||Ai−X||2is con ex when X a ies in any linea
a c segmen . In e ec , om con exi y heo y (see [1, 9]), i is a con ex unc ion in an
open se U hen he es ic ion o o any in e al (i.e., s aigh line segmen ) inside U
is con ex. Since e e y no m on IRnis con ex, he esul ollows s aigh o wa dly.
2. When (X1, X2)∈Lp×Lq, wi h {Lp, Lq}o ype 1, he dis ance d(X1, X2) is conca e
(Lemmas 6 and 7), and also is conca e dN(X1, X2) = α d(X1, X2) (whe e α∈(0,1) is he
speed ac o ).
The e o e he unc ion hij (X1, X2) = ||Ai−X1||2+dN(X1, X2) + ||X2−Aj||2is nei he
con ex no quasicon ex on Lp×Lq(and simila ly o hij (X2, X1)).
To illus a e some concep s and p ope ies associa ed o his case, we will use he small
ne wo k wi h apezoidal shape shown in Figu e 2. Leng h o basis o apezoid a e 7 and 5,
espec i ely, and he ou e ices up, wp, uqand wqo ne wo k a e he poin s (0,2√6), (5,2√6),
(−1,0) and (6,0), espec i ely. The only a c bo leneck poin s a e ¯wp= (0,0) and ¯up= (5,0)
opposi e o wpand up, espec i ely. By selec ing Lp= [up, wp] and Lq= [ ¯wp,¯up], hen Lp,
Lqa e an ipodal o each o he (no e ha in his example, Lpis he whole edge). Subsequen
6
examples on his ne wo k deal wi h he O/D pai (i, j), co esponding o poin s Ai(2.5,6) and
Aj(1,−4).
(−1,0)
uq
(6,0)
wq
(0,2√6)
up
(5,2√6)
5 5
wp
(0,0) (5,0)
Lp
Lq
wpup
Ai(2.5,6)
Aj(1,−4)
Figu e 2. An ipodal linea a c segmen s Lp= [ ¯wq,¯uq] = [up, wp] and Lq= [ ¯wp,¯up]
The s a egy o sol ing his p oblem is based on iden i ying a Fini e Domina ing Se (FDS)
such ha an op imal solu ion can be ound by selec ing he bes solu ion om he FDS. To
his end we i s in oduce some de ini ions and a collec ion o suble el se s which will be used
in he cons uc ion o such a se .
When (X1, X2)∈Lp×Lq, and {Lp, Lq}a e wo linea a c segmen s o ype 1, he dis-
ance d(X1, X2) is a conca e unc ion ob ained om he lowe en elope o wo linea unc ions:
da(X1, X2) and db(X1, X2). Tha is, d(X1, X2) = min{da(X1, X2), db(X1, X2)}, whe e his
exp ession is ob ained om Lemmas 6 and 7 (acco ding o whe he o no Lpand Lqlie in
di e en edges), by eplacing Pand Qby X1and X2, espec i ely. Mo e speci ically,
1. F om Lemma 6,
da(X1, X2) = x+d(up, uq) + y, and db(X1, X2) = l(up, wp)−x+d(wp, wq)+ l(uq, wq)−y
2. F om Lemma 7,
da(X1, X2) = y−x, and db(X1, X2) = x+d(u, ) + l(u, w)−y
Fo simplici y o no a ion, hence o h we will use (x, y) and (X1, X2) indis inc ly. In he
example o Figu e 2, deno ing by xand y he leng hs o subedges [up, X1] and [ ¯wp, X2], espec-
i ely, he dis ance d(X1, X2) is gi en by
d(X1, X2) = min{6 + x+y, 16 −x−y},wi h (x, y)∈[0,5] ×[0,5]
The e o e, he leng h hij (X1, X2) o a el pa h (Ai, X1, X2, Aj) can be exp essed as:
hij (X1, X2) = ||Ai−X1||2+αmin{da(X1, X2), db(X1, X2)}+||X2−Aj||2
and consequen ly
hij(X1, X2) = min{ga
ij(X1, X2), gb
ij (X1, X2)}
7
whe e ga
ij (X1, X2) = ||Ai−X1||2+α da(X1, X2) + ||X2−Aj||2
gb
ij (X1, X2) = ||Ai−X1||2+α db(X1, X2) + ||X2−Aj||2
Since d(X2, X1) = d(X1, X2), in a simila manne we can de ine he leng h hij(X2, X1) o a el
pa h (Ai, X2, X1, Aj):
hij(X2, X1) = min{ga
ij(X2, X1), gb
ij (X2, X1)}
wi h g
ij(X2, X1) = ||Ai−X2||2+α d (X1, X2) + ||X1−Aj||2, whe e he supe index ∈ {a, b}
e e s o he case de e mined by he o mula o d(X1, X2).
Fo example, when X1∈Lp,X2∈Lq, Figu e 3 (le ) shows he unc ion hij (X1, X2) o
ne wo k o Figu e 2 o α= 0.3. No e he pagoda oo -shape o he su ace.
Fo each O/D pai (i, j), he unc ions hij (X1, X2) and hij(X2, X1) indica e he leng h
o a el pa hs (Ai, X1, X2, Aj) and (Ai, X2, X1, Aj), espec i ely. The e o e, he ollowing
no a ion uses he supe index “12” o he i s pa h and “21” o he second pa h ( his no a ion
was also used in [5]).
De ini ion 8 [Suble el Se s] Le {Lp, Lq}be wo linea a c segmen s o ype 1 such ha
(X1, X2)∈Lp×Lq. Fo η≥0, le us conside :
1. The (η)-suble el se S12
ij (η) o unc ion hij(X1, X2), gi en by:
S12
ij (η) = {(X1, X2)∈Lp×Lq:hij(X1, X2)≤η}
Analogously, S21
ij (η) = {(X1, X2)∈Lp×Lq:hij (X2, X1)≤η}.
2. Fo ∈ {a, b}, he (η)-suble el se s G12( )
ij (η) and G21( )
ij (η), o unc ions g
ij(X1, X2) and
g
ij(X2, X1), espec i ely, gi en by:
G12( )
ij (η) = {(X1, X2)∈Lp×Lq:g
ij(X1, X2)≤η}
G21( )
ij (η) = {(X1, X2)∈Lp×Lq:g
ij(X2, X1)≤η}
Fo se e al η- alues, Figu e 3 ( igh ) displays he co esponding le el se s S12
ij (η) o he
su ace on he le o he igu e.
8
Figu e 3. Su ace hij (X1, X2) o α= 0.3 (le ), and se s S12
ij (η) o such a su ace ( igh )
Fo ∈ {a, b}, he unc ions g
ij(X1, X2) a e he sum o he con ex e m ||Ai−X1||2+||Aj−
X2||2and he linea unc ion α d (X1, X2). Simila ly, g
ij(X2, X1) is also he sum o a con ex
and a linea e m. The e o e, he con exi y o he se s G12( )
ij (η) and G21( )
ij (η), o ∈ {a, b}, is
a s aigh o wa d consequence (see [1]).
F om hese de ini ions, we ha e
Lemma 9 Sτ
ij(η) = Gτ(a)
ij (η)∪Gτ(b)
ij (η), o τ∈ {12,21}.
P oo : We p o e he lemma by double inclusion. Wi hou loss o gene ali y, we assume τ= 12.
Le (X1, X2)∈S12
ij (η) = {(X1, X2)∈Lp×Lq:hij(X1, X2)≤η}be such ha hij(X1, X2) =
min{ga
ij(X1, X2), gb
ij (X1, X2)}=g
ij(X1, X2), o some ∈ {a, b}. Since g
ij(X1, X2)≤η, hen
(X1, X2)∈G12( )
ij , which implies S12
ij (η)⊆G12(a)
ij (η)∪G12(b)
ij (η).
Con e sely, i (X1, X2)∈G12(a)
ij (η)∪G12(b)
ij (η), hen (X1, X2) belongs o (a leas ) one o such
se s, suppose (X1, X2)∈G12(a)
ij (η). I (X1, X2)/∈G12(b)
ij (η), hen gb
ij(X1, X2)> η, he e o e
hij(X1, X2) = ga
ij(X1, X2)≤ηwhich implies (X1, X2)∈S12
ij (η). I (X1, X2)∈G12(b)
ij (η), hen
hij(X1, X2)≤max{ga
ij(X1, X2), gb
ij(X1, X2)} ≤ η, consequen ly (X1, X2)∈S12
ij (η). In his case
we ha e ob ained he con e se inclusion G12(a)
ij (η)∪G12(b)
ij (η)⊆S12
ij (η), which concludes he
p oo . ⊗
F om his esul , bo h S12
ij (η) = G12(a)
ij (η)∪G12(b)
ij (η) and S21
ij (η) = G21(a)
ij (η)∪G21(b)
ij (η) a e
he union o wo con ex (bu possibili y no disjoin ) se s. The ollowing example shows ha
G12(a)
ij (η)∩G12(b)
ij (η)6=∅, o some η- alues, wi h η < ||Ai−Aj||2.
In Figu e 2, we ha e ||Ai−Aj||2=√409
2≃10.11. Figu e 4 (a) displays, o α= 0.4 and
η= 10, he bounda ies o he suble el se s G12(a)
ij (η) and G12(b)
ij (η). I can be obse ed ha he
in e sec ion o bo h se s is no emp y.
P oposi ion 10 Fo any 0≤η < ||Ai−Aj||2,S12
ij (η)∩S21
ij (η) = ∅.
P oo : Le ηbe any alue such ha 0 ≤η < ||Ai−Aj||2. To es ablish he esul i is su icien
o p o e ha , o ∈ {a, b},G12( )
ij (η)∩S21
ij (η) = ∅. Wi hou loss o gene ali y, we will p o e
G12(a)
ij (η)∩S21
ij (η) = ∅.
Assume (X1, X2)∈G12(a)
ij (η). Then
ga
ij(X1, X2) = ||Ai−X1||2+α da(X1, X2) + ||X2−Aj||2≤η < ||Ai−Aj||2
This implies ||Ai−X1||2+||X2−Aj||2<||Ai−Aj||2. By combining his inequali y wi h he
iangula p ope y, we can w i e
||Ai−Aj||2≤ ||Ai−X1||2+||X1−Aj||2<||Ai−Aj||2−||X2−Aj||2+||X1−Aj||2
By applying again he iangula p ope y ||Ai−Aj||2≤ ||Ai−X2||2+||X2−Aj||2 o he igh
hand side, we inally ob ain ||Ai−Aj||2<||Ai−X2||2+||X1−Aj||2. Consequen ly
η < ||Ai−Aj||2<||Ai−X2||2+||X1−Aj||2+αmin{da(X1, X2), db(X1, X2)}=hij (X2, X1)
Since η < hij (X2, X1) = min{ga
ij(X2, X1), gb
ij(X2, X1)}, hen (X1, X2)/∈G21(a)
ij (η)∪G21(b)
ij (η) =
S21
ij (η), which concludes he p oo . ⊗
9
Re e ences
[1] S.P. Boyd and L. Vande be ghe.Con ex Op imiza ion. Camb idge Uni e si y P ess,
2004.
[2] H. Hamache , A. Liebe s, A. Sch¨
obel, D. Wagne , F. Wagne .Loca ing new
s ops in a ailway ne wo k. Elec onic No es Theo e ical Compu e s Science 50 (2001),
1-11
[3] J.J. Hooke , R.S. Ga inkel, C.K. Chen.Fini e domina ing se s o ne wo k loca ion
p oblems. Ope a ions Resea ch 39 (1991), 100-118.
[4] F. Ki wan.Complex Algeb aic Cu es. Camb idge Uni e si y P ess, 1992.
[5] M-C. K¨
o ne , J.A. Mesa, F. Pe ea, A. Sch¨
obel, D. Scholz.A Maximum ip
co e ing loca ion p oblem wi h al e na i e mode o anspo a ion on ee ne wo ks and
segmen s. TOP (2012): DOI: 10.1007/s11750-012-0251-y.
[6] G. Lapo e, J.A. Mesa, F.A. O ega.Loca ing s a ions on apid ansi lines. Com-
pu e s & Ope a ions Resea ch 29 (2002), 741-759.
[7] G. Lapo e, J.A. Mesa, F.A. O ega, I. Se illano.Maximizing ip co e age in
he loca ion o a single apid ansi line alignmen . Annals o Ope a ions Resea ch 136
(2005), 49-61.
[8] H.M. Repolho, A.P. An unes, R.L. Chu ch.Op imal loca ion o ailway s a ions:
The Lisbon-Po o High-Speed ail Line. T anspo a ion Science 47 (2013), 330-343.
[9] R.T. Rocka elle .Con ex Analysis. P ince on Uni e si y P ess, 1970.
[10] A. Sch¨
obel.Loca ing s ops along bus o ailway lines. A bic i e ia p oblem. Annals o
Ope a ions Resea ch 136 (2005), 211-227.
[11] A. Sch¨
obel, H. Hamache , A. Liebe s, D. Wagne .The con inuous s op loca ion
p oblem in public anspo a ion ne wo ks. Asia-Paci ic Jou nal o Ope a ional Resea ch
26 (2009), 13-30.
[12] A. Sch¨
obel, D. Scholz.The Big Cube Small Cube Solu ion Me hod o Mul idimen-
sional Facili y Loca ion P oblems. Compu e s & Ope a ions Resea ch 37 (2010), 115-122.
[13] V.R. Vuchic, G.F. Newell.Rapid ansi in e s a ion spacing o minimum a el
ime. T anspo a ion Science 2(1968), 303-309.
[14] V.R. Vuchic.Rapid ansi in e s a ion spacings o maximum numbe o passenge s.
T anspo a ion Science 3(1969), 214-232.
16