A gene al app oach o he loca ion o ans e poin s on a
ne wo k wi h a ip co e ing c i e ion and mixed dis ances
M. C. López-de-los-Mozos
a,
Juan A. Mesa
b, Ani a Schöbel
c
a
Depa amen o de Ma emá ica Aplicada I, E.T.S. de Ingenie ía In o má ica, A da. Reina Me cedes, s/n, 41012, Uni e sidad de Se illa, Spain
b
Depa amen o de Ma emá ica Aplicada II, E.T.S. de Ingenie ía, Camino de los Descub imien os, s/n, 41092, Uni e sidad de Se illa, Spain
c
Ins i u ü Nume ische and Angewand e Ma hema ik. Uni e si ä Gö ingen, Ge many
Keywo ds:
Loca ion
Ne wo ks
Co e ing p oblems
Mixed dis ances
a b s a c
In his pape we conside a ip co e ing loca ion model in a mixed plana -ne wo k space. An embed-
ded ne wo k in he plane ep esen s an al e na i e anspo a ion sys em in which a eling is as e
han a eling wi hin he plane. We assume ha he demand o be co e ed is gi en by a se o o igin-
des ina ion pai s in he plane, wi h some affic be ween hem. An o igin-des ina ion pai is co e ed by
wo acili y poin s on he ne wo k (o ans e poin s), i he a el ime om he o igin o des ina ion
by using he ne wo k h ough such poin s is no highe han a gi en accep ance le el ela ed o he a el
ime wi hou using he ne wo k. The acili y loca ion p oblems s udied in his wo k consis o loca ing
one o wo ans e poin s on he ne wo k such ha , unde se e al objec i e unc ions, he affic h ough
he ne wo k is maximized. Due o he con inuous na u e o hese p oblems, a gene al app oach is p o-
posed o disc e izing hem. Since he non-con exi y o he dis ance unc ion on cyclic ne wo ks also
implies he absence o con exi y o he mixed dis ance unc ion, such an app oach is based on a decom-
posi ion p ocess which leads o a collec ion o subp oblems whose solu ion se can be ound by adap ing
he gene al s a egy o each p oblem conside ed.
1. In oduc ion
Gi en a eal o i ual unde lying ne wo k, he gene al
ne wo k design p oblem consis s o wo in e wined p oblems
( Con e as & Fe nández, 2012 ): o selec om he ne wo k a
numbe o poin s o si ing acili ies, and o in e connec hese
poin s by choosing
links o he unde lying ne wo k. In ou p oblem we ha e a ne -
wo k embedded in he plane and a se o demand poin s in he
plane. The demand o affic be ween demand poin s is gi en by
an OD-ma ix (O igin-Des ina ion ma ix) which is assumed o be
s a ic, and i is sa isfied by a eling om one o he o he poin
o each pai . We wan o selec poin s on he ne wo k o access/
exi o/ om i . These acili y poin s a e used o ans e om he
plane o he embedded gi en ne wo k, hus allowing he
connec ion o he pai s o demand poin s by using he ne wo k. A
subp oblem o he gene al ne wo k design p oblem a ises in he
design o a ailway ne wo k ( Lapo e & Mesa, 2015; Lapo e,
Mesa, & O ega, 20 0 0) ha consis s in loca ing a numbe o
s a ions and he acks o connec he s a ion- acili ies.
The p oblem o loca ing s a ions in a ailway ne wo k was in-
di ec ly ackled in Vuchic and Newell (1968) , in which he op imal
in e s a ion spacing p oblem in a commu e line was esea ched.
The objec i e o his p oblem is o minimize he o al ime o pas-
senge 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 Vuchic (1969) in
o de o maximize he numbe o passenge s on he basis o sho -
es a el imes. 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 ( Lapo e, Mesa, & O ega, 2002; Lapo e, Mesa, O ega, &
Se illano, 2005; Repolho, An unes, & Chu ch, 2013 ) in which he
easible solu ion space o loca ing s a ions was disc e e and he
objec i es we e o maximize he passenge co e age, ip co e -
age and sa ings in a el cos , espec i ely, se e al objec i e unc-
ions ha e been conside ed in hose models in which s a ions can
be loca ed along he edges o he ailway ne wo k: sa ing in pas-
senge a el ime ( Hamache , Liebe s, Schöbel, Wagne , & Wag-
ne , 2001 ), co e age/numbe o new s a ions ( Schöbel, 2005 ), ad-
di ional a el ime ( Schöbel, Hamache , Liebe s, & Wagne , 2009 ),
and o al a el ime ( Ca izosa, Ha be ing, & Schöbel, 2016 ). The
maximal co e ing loca ion p oblem was in oduced in Chu ch and
ReVelle (1974) in which a numbe o acili ies a e o be loca ed
on a ne wo k so ha he popula ion wi hin a se ice dis ance is
maximized. In Mu awski and Chu ch (2009) ime o access he a-
cili ies is imp o ed by upg ading edges o he anspo a ion ne -
wo k. The objec i e unc ion consis s in maximizing he numbe
o people who a e co e ed by upg ading some pa s o he ne -
wo k. In o de o loca e in e changes poin s in a highway ne wo k
a cos -benefi objec i e unc ion is conside ed in Repolho, Chu ch,
and An unes (2010) ha akes in o accoun a ou e choice model.
In he p oblem deal wi h in his pape , he e a e exis ing de-
mand poin s in he Euclidean plane whe eas new acili ies a e o
be loca ed in a 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 Eu-
clidean dis ance o by a plane-ne wo k combina ion 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 compe i ion be ween he
mode ha only uses he plana dis ance and he combined one. I
he ime spen by he ip in he combined mode is lowe han
ha o he plana mode hen he OD-pai is said o be co e ed
by he ans e poin s used o access/exi he ne wo k. 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 assume he decision space is he se o poin s
on he edges o he ne wo k. The na u e o he decision space
when loca ing new ans e poin s in long and medium dis ance
ailway ne wo ks as well as in unde g ound u ban/subu ban apid
ansi sys ems is con inuous. As was poin ed ou in Lapo e, Mesa,
and Pe ea (2014) 30% o he s a ions o he Spanish high-speed
ne wo k a e si ua ed ou side ci ies in he coun yside, hus al-
lowing a con inuous decision space. Fu he mo e, he con inuous
se ing o he decision space allows he use o con inuous op i-
miza ion me hods hus p o iding insigh in o he beha io o he
objec i e unc ion and he p oblem i sel . Mo eo e , new de el-
opmen a eas, conges ion o en i onmen al and ene gy consump-
ion a e easons o cons uc ing new s a ions. An example is he
use o a sec ion o he ailway line Se ille-Huel a as a new com-
mu e line (Line 5) o he me opoli an a ea o Se ille ( Lapo e
e al., 2014 ). Fo his line new s a ions we e buil , some o hem
be ween owns. Ano he example is he cons uc ion o a new s a-
ion in he high-speed line Mad id-Se ille be ween Có doba and
Pue ollano s a ions. The new s a ion: Villanue a de Có doba-Los
Ped oches co e s an a ea o he no h o he p o ince o Có doba.
Since he a eling demand is gi en by pai s o exis ing poin s i
is cohe en o conside he loca ion o pai s o ans e poin s ac -
ing as access/exi poin s on he ne wo k. Unde he assump ion o
a ne wo k wi h a se o exis ing node-s a ions, he e a e wo p ob-
lems pa icula ly ele an om an applied poin o iew, which
deal wi h loca ing one, o wo, ans e poin s in o de o maxi-
mize he amoun o OD-pai s addi ionally co e ed, ha is, hose
OD-pai s which canno be co e ed by he exis ing s a ions. In he
fi s p oblem only one ans e poin is loca ed since his poin in
combina ion wi h each s a ion wo ks as an access/exi poin . In
he second p oblem, which seeks o loca e wo ans e poin s, he
addi ional co e age e e s he OD-pai s co e ed ei he by he wo
ans e poin s o by a combina ion o each poin wi h some s a-
ion, bu no ye co e ed by pai s o e ices. Bo h p oblems also
exclude he OD-pai s p e iously co e ed by he exis ing s a ions.
Mo eo e , he second p oblem p esen s a mo e gene al o mula-
ion o he model, in he way ha i inco po a es he addi ional
co e age p o ided bo h by he wo poin s and by each poin sepa-
a ely.
Fo sol ing hese addi ional co e ing p oblems, his pape p o-
poses a me hodology which is based on conside ing a key p oblem,
whose solu ion p ocedu e p o ides a gene al app oach which can
be adap ed o he emaining p oblems. This key p oblem does no
equi e any hypo hesis on he ne wo k (i is possible ha he e
is no al eady loca ed s a ion), since i seeks o loca e wo ans-
e poin s maximizing he amoun o OD-pai s co e ed. The ele-
ance o his p oblem de i es om i allowing he de elopmen o
a heo e ical amewo k which is sha ed by he abo e one o wo
ans e addi ional co e ing p oblems, as well as by o he ela ed
p oblems.
Summa izing, he main con ibu ion o his pape is, in he fi s
place, o p opose a comp ehensi e app oach o sol ing se e al
p oblems dealing wi h loca ing ans e poin s on cyclic anspo a-
ion ne wo ks unde se e al objec i e unc ions, all o hem o-
cused on co e ing OD-pai s ins ead o single demand poin s. Mo e-
o e , he p oposed app oach o sol e he p oblem o maximizing
he co e age ob ained by 2- ans e poin s is used o he mo e
eal p oblems o loca ing one o wo ans e poin s so ha he
addi ional co e age (in p esence o al eady unc ioning s a ions)
will be maximized. The p oblems s udied deal wi h a con inuous
model, whose analysis enla ges he knowledge on bo h he geo-
me ic s uc u e o he p oblems and he beha io and p ope ies
o he objec i e unc ions. On he o he hand, such an app oach de-
sc ibes a flexible me hodology which, by inco po a ing sligh mod-
ifica ions, allows o disc e ize he solu ion se o all p oblems con-
side ed.
In a p e ious pape ( Kö ne , Mesa, Pe ea, Schöbel, & Scholz,
2014 ) he key p oblem was sol ed when he new acili ies a e o
be loca ed in segmen s and ee ne wo ks. In his pape we ex end
he app oach applied in Kö ne e al. (2014) 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
main aim o his esea ch is o sol e ha complex con inuous lo-
ca ion p oblem by educing he candida e se o a fini e one om
which an op imal solu ion is selec ed by means o a polynomial
ime algo i hm.
The pape is o ganized as ollows: a e his in oduc ion he
elemen s o he model a e p esen ed in Sec ion 2 . The necessa y
defini ions and esul s on he dis ance on ne wo ks a e summa-
ized in Sec ion 3 . Sec ion 4 p o ides a decomposi ion o he fi s
p oblem in o wo ypes o subp oblems, such ha o each sub-
p oblem a solu ion me hod is p oposed in Sec ions 5 . Sec ions 6
and 7 s udy espec i ely wo new p oblems, bo h ela ed o he
p e ious one, in which one and wo ans e poin s a e loca ed un-
de di e en objec i e unc ions, and Sec ion 8 is de o ed o p e-
sen ing he co esponding algo i hms and discussing i s compu a-
ional complexi y. The pape ends wi h some conclusions and u -
he esea ch.
2. Elemen s o he model
In o de o o mula e he p oblems wi h a mixed mode o ans-
po a ion, we conside a connec ed ne wo k N (V, E) ep esen ing a
high-speed sys em, wi h | V | nodes and | E | edges (whe e | ·| deno es
ca dinali y). We assume ha he ne wo k is embedded in he Eu-
clidean plane and ha each undi ec ed edge e ∈ E 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 N will allow us
o compu e he dis ances along he ne wo k. Mo e p ecisely, he
leng h l(u, ) o an edge (o a subedge) [ u, ] is he Euclidean dis-
ance || u − || be ween i s endpoin s, and by using sho es pa h
algo i hms we can mo eo e compu e he dis ance be ween each
pai o nodes. Mo eo e , he iangle inequali y holds in his model.
Le N be he con inuum se o poin s o he edges. The edge
leng hs induce a dis ance unc ion d such ha , o any wo poin s
x, y ∈ N , d ( x , y ) is he leng h o any sho es pa h in N (V, E) con-
nec ing x and y . I x and y a e on he same edge, hen d ( x , y ) coin-
cides wi h he leng h o he subedge [ x , y ].
Fo x, y ∈ N , he a el dis ance be ween bo h poin s is gi en by
αd ( x , y ), wi h α∈ (0, 1). Pa ame e αis a speed ac o , such ha
Ai
Aj
X1
X2
Ai
Aj
X1
X2
Fig. 1. T a el pa hs o : h
+
ij
(X
1
, X
2
) (le ), and h
−
ij
(X
1
, X
2
) ( igh ).
αd ( x , y ) ep esen s he a eling ime be ween x , y by using he
high-speed ne wo k. I can immedia ely be seen ha , wi h hese
dis ance, N is a me ic space.
•Le A = { A
i
= (a
i
, b
i
) , i = 1 , . . . , n } ⊂IR
2 be a se o exis ing de-
mand poin s on he plane. We assume ha dis ances be ween
wo poin s in he plane can be es ima ed by he Euclidean me -
ic.
•Le T = (
ij
) ∈ IR
n ×n be an o igin-des ina ion ma ix in which
ip pa e ns a e codified, i.e.,
ij
is he weigh o he o de ed
pai ( i , j ). This ma ix is known a p io i: o example, in a ans-
po a ion con ex each
ij
can be iewed as he numbe o ips
om an o igin A
i
o a des ina ion A
j
, and in a elecommunica-
ion se ing i could ep esen he amoun o da a ans e ed
om se e A
i
o se e A
j
.
•Gi en an OD-pai ( i , j ), he a el dis ance by using he ne wo k
h ough he poin s X
1
, X
2
∈ N (o he 2- acili y poin ( X
1
, X
2
))
is ob ained om he wo possible a el pa hs: ( A
i
, X
1
, X
2
, A
j
),
and ( A
i
, X
2
, X
1
, A
j
), linking o igin and des ina ion (see Fig. 1 ).
Fo each o hem, he a el dis ance is gi en by
h+
ij(X
1
, X
2
) = || A
i
−X
1
|| + αd(X
1
, X
2
) + || X
2
−A
j
||
h−
ij(X
1
, X
2
) = || A
i
−X
2
|| + αd(X
2
, X
1
) + || X
1
−A
j
|| .
The mixed a el dis ance be ween A
i
and A
j
by using he high-
speed ne wo k h ough he ans e poin s X
1
, X
2
∈ N is gi en
by he sho es a el dis ance ob ained om bo h a el pa hs,
and i is w i en as:
ij
(X
1
, X
2
) = min { h+
ij
(X1
,X2
),h−
ij
(X
1
, X
2
) } .
Symme y o such pa hs implies h
+
ij
(X
1
, X
2
) = h
−
ji
(X
1
, X
2
) ,
h−
ij
(X1
,X2
)=h+
ji
(X
1
, X
2
) , and he e o e
ij
(X
1
, X
2
) =
ji
(X
1
, X
2
) .
•Le 
D = (

d
ij
) ∈ IR
n ×n be a symme ic ma ix, wi h 0 ≤
d
ij
<
|| A
i
−A
j
|| , o i  = j , and 
d
ii
= 0 , i = 1 , . . . , n . The alues o 
D
ep esen he accep ance le els o using he ne wo k, meaning
ha he OD-pai ( i , j ) chooses he high-speed ne wo k i and
only i he mixed a el dis ance by using i is less han o equal
o 
d
ij
. In o he wo ds, he OD-pai s always choose he as e op-
ion. In he ollowing, we assume ha i  = j o a oid he i ial
case.
Defini ion 1. The OD-pai ( i , j ) is co e ed by X
1
, X
2
∈ N i
ij
(X
1
, X
2
) ≤
d
ij
.
Le C ( X
1
, X
2
) be he se o O/D pai s co e ed by X
1
, X
2
, gi en
by
C(X
1
, X
2
) = { (i, j) , i  = j, 1 ≤i, j ≤n :
ij
(X
1
, X
2
) ≤
d
ij
} .
F om symme y bo h o he accep ance le el ma ix 
D and he
mixed a el dis ance we ha e
(i, j) ∈ C(X
1
, X
2
) i and only i (j, i ) ∈ C(X
1
, X
2
) .
As i has been poin ed ou in he p e ious sec ion, in he fi s
place we o mula e he key p oblem, which p esen s s uc u al
p ope ies sha ed by he emaining p oblems, and whose solu ion
p ocedu e p o ides a gene al me hodology o analyzing and sol -
ing he one and wo addi ional co e ing p oblems, which a e o -
mula ed subsequen ly.
Ai
Aj
X1
X2
Ak
Fig. 2. Gi en he nonnega i e accep ance le els 
d
ij
<
|| A
i
−A
j
|| , 
d
ik
<
|| A
i
−A
k
|| ,

d
jk
<
|| A
j
−A
k
|| , and a sui able speed ac o α∈ (0, 1), we ha e ( i , j ), ( i , k ) ∈
C ( X
1
, X
2
). Howe e ( j , k ) ∈ C ( X
1
, X
2
). The objec i e alue a ( X
1
, X
2
) is: F
(X
1
, X
2
) =
ij
+
ji
+
ik
+
ki
. The e may be se e al poin s ( X
1
, X
2
) wi h he same objec i e
alue.
1. The fi s objec i e unc ion measu es he o al weigh o OD-
pai s cap u ed by each pai o ans e poin s X
1
, X
2
∈ N , and
i is gi en by:
F (X
1
, X
2
) = 
(i,j) ∈ C(X
1
,X
2
)
ij
.
In his unc ion whe he he node se V con ains al eady lo-
ca ed s a ions o no is no ele an , since i seeks o com-
pu e he weigh o pai s co e ed by he wo ans e poin s
when hey assume he symme ic ole o access/exi poin s
(see Fig. 2 ).
The key p oblem, b iefly he 2- ans e co e ing p oblem (2-
TC), is o find wo ans e poin s X
1
, X
2
∈ N such ha he
sum o weigh s o all OD-pai s co e ed by such poin s is
maximized:
max
X
1
,X
2
∈N
F (X
1
, X
2
) := 
(i,j) ∈ C(X
1
,X
2
)
ij (2-TC)
2. Con a y o he abo e model, his p oblem and he ollow-
ing one deal wi h addi ional co e age, and hey equi e he
hypo hesis o ha ing a se o s a ions al eady loca ed, hese
la e ones selec ed om he node se .
Wi hou loss o gene ali y we can assume ha all nodes o
V a e al eady loca ed ans e poin s. F om Defini ion 1 , he
OD-pai ( i , j ) is co e ed by any X ∈ N i he e exis s ∈ V
such ha
ij
(X, ) ≤
d
ij
. Thus, he se C ( X ) con aining he
OD-pai s co e ed by X is
C(X ) = { (i, j) , i  = j, 1 ≤i, j ≤n :
ij
(X, ) ≤
d
ij
o some ∈ V }
Simila ly, he se C
V
o OD-pai s al eady co e ed by he
nodes o V is gi en by
C
V = { (i, j) , i  = j, 1 ≤i, j ≤n :
ij
(w, ) ≤
d
ij
o some w, ∈ V }
Thus, he second objec i e unc ion can be s a ed as
F
V
(X ) := 
(i,j) ∈ C(X) C
V
ij
And he 1- ans e addi ional co e ing p oblem (1-TAC) is:
max
X∈NF
V
(X ) := 
(i,j) ∈ C(X)
ij (1-TAC)
Finally, in his case wo ans e poin s ( X
1
, X
2
) a e lo-
ca ed by add essing he addi ional co e age. As abo e, we
assume ha all nodes a e s a ions, and also he se C
V
is ex-
cluded. The objec i e unc ion in eg a es he abo e o mu-
la ions since i akes in o accoun bo h he amoun o OD-
pai s co e ed by ( X
1
, X
2
) and he OD-pai s co e ed by each
poin in combina ion wi h he s a ions al eady loca ed a
nodes, as ollows:
F
A
(X
1
, X
2
) := 
(i,j) ∈
C(X
1
,X
2
) ∪ C(X
1
) ∪ C(X
2
)
 C
V
ij
The 2- ans e addi ional co e ing p oblem (2-TAC), seeks
he loca ion o wo ans e poin s maximizing he o al
weigh o OD-pai s addi ionally co e ed:
max
X
1
,X
2
∈N
F
A
(X
1
, X
2
) := 
(i,j) ∈
C(X
1
,X
2
) ∪ C(X
1
) ∪ C(X
2
)
 C
V
ij
(2-TAC)
Rema k 2. Each pai o associa ed p oblems ob ained by excluding,
o no , C
V
om he co esponding o mula ion a e equi alen , bu
no he same, in he ollowing way: hey sha e he same solu ion
se (which is a s aigh o wa d consequence om he ac ha C
V
is a cons an se ), al hough hei op imal solu ions could be di e -
en . Tha is, (2-TC) and max
X
1
,X
2
∈N
F (X
1
, X
2
) :=

(i,j) ∈ C(X
1
,X
2
) C
V
ij
a e equi alen , and so on.
Al hough p oblems (1-TAC) and (2-TAC) p esen special ele-
ance ega ding he applica ions, he p ocedu e o sol ing p ob-
lem (2-TC) p o ides a gene al me hodology which can be applied
o all p oblems p esen ed in his pape . In ac , he na u e o such
a me hodology allows he esolu ion o be ex ended o some gen-
e aliza ions o hese p oblems, as he p - ans e addi ional co e -
ing p oblem ( p > 2). This mo i a es ha p oblem (2-TC) is s udied
in he fi s place. The s a egy o sol ing his p oblem lies in de-
composing i in o a collec ion o subp oblems such ha , o each
o hem, a pa i ion o he easible solu ion se is cons uc ed, and
om such pa i ion, a fini e subse con aining some op imal solu-
ion is selec ed.
P oblem (2-TC) has been fi s sol ed o he pa icula case
whe e N is a segmen o a s aigh line, and subsequen ly he
me hod was ex ended o he case whe e N is a ee ne wo k T
(see Kö ne e al., 2014 ). Thus, hence o h we will conside ha N
con ains a leas one cycle. Unde his assump ion, he app oach
applied o he ee ne wo k case canno be di ec ly ex ended o
his case due o he absence o con exi y o he dis ance unc ion
on a cyclic ne wo k.
In o de o sol e his p oblem, we nex summa ize some con-
cep s and esul s on dis ances in ne wo ks.
3. P e ious esul s on dis ances on ne wo ks
Fo e alua ing he objec i e unc ion o p oblem (2-TC) , i is
fi s necessa y o ob ain an analy ical exp ession o he dis ance
be ween any wo poin s P , Q , o he ne wo k N . The a o emen-
ioned non-con exi y leads o he ac ha he exp ession o he
dis ance d ( P , Q ) could a y h ough he ne wo k. In his sec ion
we pa i ion he ne wo k in o a collec ion o subedges such ha
o each pai o subedges, he dis ance be ween hei poin s can
be compu ed. To his end, we fi s need o e iew some concep s
dealing wi h he dis ance on ne wo ks.
He eina e we assume a ne wo k N wi h a dis ance unc ion
d ( ·, ·) such ha he iangle inequali y holds. Le e = [ u, w ] ∈ Ebe
an edge o N wi h leng h l
e
, and le P be a poin on edge e . Le x =
l(u, P ) deno e he leng h o subedge [ u , P ], and le l(w, P ) = l
e
−x
deno e he leng h o subedge [ P, w ] . I is well known ha o any
node ∈ V, he dis ance d( , P ) = min { d( , u ) + x, d( , w ) + l
e
−x }
is conca e and piecewise linea on x ∈ [0, l
e
], wi h a mos wo
pieces wi h slopes 1 and −1 . F om he iangle inequali y we
ha e l
e
= d(u, w ) ≤| d( , u ) −d( , w ) | , he e o e he dis ance unc-
ion d( , P ) on [ u, w ] is linea . Fo he sake o comple eness we in-
clude he ollowing concep s and defini ions, al hough all o hem
uq
upwp
wq
uq
wq
wpup
Fig. 3. An ipodal poin s.
can be ound in Hooke , Ga finkel, and Chen. (1991) and e e ences
he ein.
Defini ion 3. 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 Q in
[ u, w ] .
Defini ion 4. A poin ¯
∈ [ u, w ] , o he han a node, is called an a c
bo leneck poin i he e is a node o which ¯
is an ipodal o .
In his case, we call i he a c bo leneck poin ¯
.
Clea ly, he edge e = [ u, w ] con ains a mos | V | a c bo leneck
poin s. I ¯
∈ [ u, w ] is an ipodal o we ha e d( , u ) + l(u,
¯
) =
d( , w ) + l(w,
¯
) , hence such a poin ¯
can be iden ified by he
leng h o he subedge [ u,
¯
] , gi en by: l(u,
¯
) =
d ( ,w ) −d ( ,u )+ l
e
2
.
Defini ion 5. Le B
e be he se o a c bo leneck poin s o edge
e = [ u, w ] , and le ¯
, ¯
 be wo adjacen poin s o B
e
∪ { u, w } . Then
he closed subedge L = [
¯
,
¯

] is called a linea a c segmen (o a
eelike segmen ( Hooke e al., 1991 )).
We ema k ha B
e has O (| V |) elemen s. On each linea a c
segmen he dis ance d( , ·) is linea . I B
e
= ∅ he en i e edge
e = [ u, w ] (including nodes) is a linea a c segmen . The se o all
linea a c segmen s o an edge e is deno ed by L (e ) .
Le [ u
p
, w
p
] and [ u
q
, w
q
] be wo edges o he ne wo k N ,
and le [
¯
w
p
,
¯
u
p
] ⊆[ u
q
, w
q
] , [
¯
w
q
,
¯
u
q
] ⊆[ u
p
, w
p
] be he subedges o
which he ex eme poin s a e an ipodal poin s as ollows: ¯
u
p
, ¯
w
p
a e he an ipodal poin s o u
p
, w
p
, espec i ely, and ¯
u
q
, ¯
w
q a e he
an ipodal poin s o u
q
, w
q
, espec i ely (see Fig. 3 ). F om p e ious
defini ions we ha e l(
¯
w
q
,
¯
u
q
) = l(
¯
w
p
,
¯
u
p
) and d(
¯
w
q
, ¯
w
p
) = d(
¯
u
q
,
¯
u
p
)
(see Hooke e al., 1991 o a mo e de ailed explana ion).
Defini ion 6. Le L
p
, L
q be wo linea a c segmen s o di e en
edges [ u
p
, w
p
] and [ u
q
, w
q
] , espec i ely, and le [
¯
w
q
,
¯
u
q
] ⊆[ u
p
, w
p
]
and [
¯
w
p
,
¯
u
p
] ⊆[ u
q
, w
q
] be he subedges o which ¯
u
p
, ¯
w
p a e he
an ipodal poin s o u
p
, w
p
, espec i ely, and ¯
u
q
, ¯
w
q a e he an ipo-
dal poin s o u
q
, w
q
, espec i ely. I L
p
⊆[
¯
w
q
,
¯
u
q
] and L
q
⊆[
¯
w
p
,
¯
u
p
] ,
hen L
p
, L
q a e called an ipodal segmen s o each o he .
(This defini ion includes he case [
¯
w
q
,
¯
u
q
] = [ u
p
, w
p
] and
[
¯
w
p
,
¯
u
p
] = [ u
q
, w
q
] ). 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 e al., 1991 ).
Lemma 7. Le P be es ic ed o linea a c segmen L
p o edge
[ u
p
, w
p
] and Q o linea a c segmen L
q o edge [ u
q
, w
q
] , wi h
[ u
p
, w
p
]  = [ u
q
, w
q
] .
1. I L
p
, L
q a e an ipodal segmen s o each o he , d ( P , Q ) is con-
ca e.
2. O he wise, d ( P , Q ) is linea .
In case 1, he dis ance be ween a poin P on he segmen
[
¯
w
q
,
¯
u
q
] and a poin Q on he segmen [
¯
w
p
,
¯
u
p
] beha es like he
dis ance on he pa allelog am in Fig. 3 (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(u
p
, P ) , wi h x ∈ [0 , l(u
p
, w
p
)] and y = l(u
q
, Q) ,
wi h y ∈ [0 , l(u
q
, w
q
)] , we can compu e he dis ance d ( P , Q ) o he
cases conside ed in his lemma.
d(P, Q) =
⎧
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎩
min { x + d(u
p
, u
q
) + y, l(u
p
, w
p
) −x + d(w
p
, w
q
)
+ l(u
q
, w
q
) −y } , L
p
, L
q
an ipodal
x + d (u
p
, u
q
) + y, L
p
⊆[ u
p
, ¯
w
q
] , L
q
⊆[ u
q
, ¯
w
p
]
o L
q
⊆[
¯
w
p
,
¯
u
p
]
x + d (u
p
, w
q
) + l(u
q
, w
q
) −y, L
p
⊆[ u
p
, ¯
w
q
] ,
L
q
⊆[
¯
u
p
, w
q
] .
No e ha i L
p
, L
q a e an ipodal segmen s, wi h u
p
 = ¯
w
q
, ¯
u
q
 = w
p
and simila ly u
q
 = ¯
w
p
, ¯
u
p
 = w
q
, hen he dis ance d ( P , Q ) can also
be compu ed by min { x + d(u
p
, w
q
) + l(u
q
, w
q
) −y, l(u
p
, w
p
) −x +
d(w
p
, u
q
) + y } . Finally, he emaining cases ob ained by combin-
ing L
p
, L
q can be educed o one o hese by symme y ( o exam-
ple, o he case L
p
⊆[ u
p
, ¯
w
q
] , L
q
⊆[
¯
u
p
, w
q
] he dis ance can also
be equi alen ly ob ained as l(u
p
, w
p
) −x + d(w
p
, u
q
) + y ).
We now commen he case in which P , Q lie on he same edge
e = [ u, w ] . Le L
p
, L
q be wo linea a c segmen s o e such ha P ∈
L
p
, Q ∈ L
q
. The iangle inequali y implies ha L
p and L
q a e no
an ipodal o each o he , consequen ly he dis ance d ( P , Q ) is ei he
con ex (i L
p
= L
q
), o linea (i L
p  = L
q
), and i is gi en by he
leng h o subedge [ P , Q ]. By using he abo e no a ion x = l(u, P )
and y = l(u, Q) , we ha e d(P, Q) = | x −y | .
4. Decomposing he 2- ans e co e ing p oblem
Summa izing he p e ious sec ion, o each pai o linea a c
segmen s he dis ance d ( P , Q ) be ween hei espec i e poin s is
ei he conca e o con ex, and i s analy ical exp ession can be com-
pu ed. Fo his eason, he solu ion me hod is based on decompos-
ing p oblem (2-TC) in o a collec ion o independen subp oblems
(whe e each subp oblem is he es ic ion o (2-TC) o a gi en pai
o linea a c segmen s), and sol ing each o hem ia disc e iza-
ion o he solu ion se . To his end and o he sake o eadabili y,
we will desc ibe he p ocess in h ee phases: he fi s one is de-
o ed o bo h decomposing he p oblem (2-TC) and g ouping he
subp oblems in o wo cases: he conca e and he con ex case. The
second phase deals wi h he subp oblems o he fi s case, and fi-
nally in he las s ep we will s udy he subp oblems o he second.
These wo cases will be desc ibed as ollows.
To decompose he p oblem we fi s compu e, in O (| V || E |) ime,
he dis ance ma ix be ween all pai s o nodes o he ne wo k.
Then, o each edge e ∈ E we ob ain, and so , he se B
e (in
O (| V |log | V |) ime). A he end o his p ocess we ha e, o each
edge e o 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
e
p
= [ u
p
, w
p
] and e
q
= [ u
q
, w
q
] we know whe he o no wo linea
a c segmen s L
p
∈ L (e
p
) and L
q
∈ L (e
q
) a e an ipodal.
Le L =

e ∈ E
L (e ) be he se o all linea a c segmen s o he
o e all ne wo k. Thus p oblem (2-TC) 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 L
p ×L
q
, wi h L
p
, L
q
∈ L . By imposing ha
X
1 ∈ L
p
, X
2 ∈ L
q we ob ain he es ic ed p oblem:
max
X
1
∈ L
p
, X
2
∈ L
q
F (X
1
, X
2
) := 
(i,j) ∈ C(X
1
,X
2
)
ij (2-TCR)
A solu ion o p oblem (2-TC) is ound by sol ing he collec-
ion o all O (|L|
2
) es ic ed p oblems (2-TCR) (in ac , |L| (|L|−1)
2
es ic ed p oblems by symme y), and hen selec ing he bes so-
lu ion.
The classifica ion o he es ic ed p oblem (2-TCR) is made ac-
co ding o he conca i y o he dis ance d ( X
1
, X
2
), which is ela ed
o he an ipodal cha ac e o L
p
, L
q
. Mo e specifically, p oblem (2-
TCR) is conca e i he ollowing condi ion holds:
Fig. 4. Ne wo k wi h V = {
i
, i = 1 , . . . , 4
} , and linea a c segmen s L
p
, p = 1 , . . . , 8 .
L
p
∈ L (e
p
) , L
q
∈ L (e
q
) , wi h e
p  = e
q
, and L
p
, L
q a e an ipodal o
each o he .
Fo he emaining cases, he p oblem (2-TCR) is classified as
con ex.
5. A p ocedu e o disc e izing he es ic ed p oblem (2-TCR)
This sec ion is de o ed o s udying he es ic ed p oblem
(2-TCR) o a gi en pai L
p
, L
q
∈ L . Hence o h, we w i e ( X
1
, X
2
)
∈ L
p ×L
q ins ead o X
1 ∈ L
p
, X
2 ∈ L
q
.
The s a egy o sol ing (2-TCR) is based on iden i ying a Fi-
ni e Domina ing Se (FDS), ha is, a fini e se o poin s ⊂L
p ×
L
q con aining an op imal solu ion. F om his se , (2-TCR) becomes
he p oblem max
(X
1
,X
2
) ∈ F (X
1
, X
2
) . In o de o desc ibe he p o-
cedu e o finding , he conca e and con ex cases a e analyzed
sepa a ely.
5.1. The conca e case
This p oblem can be o mula ed om (2-TCR) by adding he as-
sump ion “L
p
, L
q a e an ipodal o each o he ”, and i will be iden-
ified as (2-TCR) (1).
Each linea a c segmen is a ec ifiable subedge in which all dis-
ance unc ions d(
i
, P ) a e linea . On he o he hand, we ha e:
1. Fo each A
i
∈ A , he Euclidean dis ance || A
i
−X|| is con-
ex when X a ies in any linea a c segmen . In e ec , his
esul ollows s aigh o wa dly om con exi y heo y (see
Rocka elle , 1970 ), since 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.
2. When ( X
1
, X
2
) ∈ L
p ×L
q
, wi h L
p
, L
q an ipodal o each o he ,
he dis ance αd ( X
1
, X
2
) is conca e ( Lemma 7 ), whe e α∈ (0,
1) is he speed ac o .
The e o e bo h he unc ion h
+
ij
(X
1
, X
2
) and h−
ij
(X
1
, X
2
) a e no
con ex on L
p ×L
q
.
To illus a e some concep s and p ope ies associa ed wi h his
case, we will use he ne wo k wi h apezoidal shape shown in
Fig. 4 . The leng hs o he basis edges o he apezoid a e 7 and
5, espec i ely, and he nodes {
i
, i = 1 , . . . , 4 } a e indica ed in he
figu e wi h hei co esponding coo dina es. Likewise, each ¯
i
ep-
esen s he a c bo leneck poin opposi e o
i
, i = 1 , . . . , 4 . This
figu e also shows he pa i ion o he ne wo k o igina ed by he
se o linea a c segmen s L = { L
p
, p = 1 , . . . , 8 } . In his case, L
2
=
[
¯
3
,
¯
4
] and L
6
= [
4
,
3
] a e an ipodal o each o he .

Fig. 5. Su ace h
+
ij
(X
1
, X
2
) o α= 0 . 3 (le ), and se s H
+
ij
(η) o such a su ace ( igh ).
In o de o find an FDS o he p oblem, in he ollowing we in-
oduce he necessa y defini ions on he suble el se s, om which
he FDS is cons uc ed.
5.1.1. Cha ac e izing he suble el se s
When ( X
1
, X
2
) ∈ L
p ×L
q
, and { L
p
, L
q
} a e an ipodal o each
o he , he dis ance d ( X
1
, X
2
) is a conca e unc ion ob ained om
he lowe en elope o wo linea unc ions: d
a
( X
1
, X
2
) and d
b
( X
1
,
X
2
). Tha is, d(X
1
, X
2
) = min { d
a
(X
1
, X
2
) , d
b
(X
1
, X
2
) } , whe e his ex-
p ession is ob ained om Lemma 7 by eplacing P and Q by X
1
and
X
2
, espec i ely. Mo e specifically, i x = l(u
p
, X
1
) and y = l(u
q
, X
2
) ,
we ha e
d
a
(X
1
, X
2
) = x + d(u
p
, u
q
) + y, and d
b
(X
1
, X
2
)
= l(u
p
, w
p
) −x + d(w
p
, w
q
) + l(u
q
, w
q
) −y.
I he e is no con usion we will iden i y X
1
wi h x and X
2
wi h y .
The e o e, he a el dis ance h
+
ij
(X
1
, X
2
) o a el pa h ( A
i
, X
1
, X
2
,
A
j
) can be exp essed as
h
+
ij
(X
1
, X
2
) = || A
i
−X
1
|| + αmin { d
a
(X
1
, X
2
) , d
b
(X
1
, X
2
) } + || X
2
−A
j
||
and consequen ly,
h
+
ij
(X
1
, X
2
) = min { g
+ ,a
ij
(X
1
, X
2
) , g
+ ,b
ij
(X
1
, X
2
) } ,
whe e
g
+ ,a
ij
(X
1
, X
2
) = || A
i
−X
1
|| + αd
a
(X
1
, X
2
) + || X
2
−A
j
||
g
+ ,b
ij
(X
1
, X
2
) = || A
i
−X
1
|| + αd
b
(X
1
, X
2
) + || X
2
−A
j
|| .
Since d(X
2
, X
1
) = d(X
1
, X
2
) , in a simila manne we can define he
a el dis ance h
−
ij
(X
1
, X
2
) o a el pa h ( A
i
, X
2
, X
1
, A
j
):
h
−
ij
(X
1
, X
2
) = min { g
−,a
ij
(X
1
, X
2
) , g
−,b
ij
(X
1
, X
2
) } ,
wi h g
−,
ij (X
1
, X
2
) = || A
i
−X
2
|| + αd
(X
1
, X
2
) + || X
1
−A
j
|| , o ∈ { a ,
b }.
Fo example, when X
1 ∈ L
6
, X
2 ∈ L
2
, Fig. 5 (le ) shows he
unc ion h
+
ij
(X
1
, X
2
) on he ne wo k o Fig. 4 o α= 0 . 3 , A
i
(2.5, 6),
A
j
(1 , −4) . No e he pagoda oo -shape o he su ace.
Defini ion 8 (Suble el Se s) . Le { L
p
, L
q
} be wo linea a c seg-
men s an ipodal o each o he such ha ( X
1
, X
2
) ∈ L
p ×L
q
. Fo
η≥0, le us conside :
1. The ( η)-suble el se H
+
ij
(η) o unc ion h
+
ij
(X
1
, X
2
) , gi en
by:
H
+
ij
(η) = { (X
1
, X
2
) ∈ L
p
×L
q
: h
+
ij
(X
1
, X
2
) ≤η} .
Analogously, H
−
ij
(η) = { (X
1
, X
2
) ∈ L
p
×L
q
: h
−
ij
(X
1
, X
2
) ≤η} .
2. Fo ∈ { a , b }, he ( η)-suble el se s G
+ ,
ij
(η) and G
−,
ij (η) ,
o unc ions g
+ ,
ij
(X
1
, X
2
) and g
−,
ij
(X
1
, X
2
) , espec i ely, gi en
by:
G
+ ,
ij
(η) = { (X
1
, X
2
) ∈ L
p
×L
q
: g
+ ,
ij
(X
1
, X
2
) ≤η}
G
−,
ij
(η) = { (X
1
, X
2
) ∈ L
p
×L
q
: g
−,
ij
(X
1
, X
2
) ≤η} .
Fo se e al η- alues, Fig. 5 ( igh ) displays he co esponding
suble el se s H
+
ij
(η) o he su ace ep esen ed on he le -hand
side o he figu e.
Fo ∈ { a , b }, he unc ion g
+ ,
ij
(X
1
, X
2
) is he sum o he con ex
e m || A
i
−X
1
||
2
+ || A
j
−X
2
||
2 and he linea unc ion αd
( X
1
, X
2
).
Simila ly, g
−,
ij
(X
2
, X
1
) 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 G
+ ,
ij (η) and G
−,
ij (η) , o ∈
{ a , b }, is a s aigh o wa d consequence (see Boyd & Vande be ghe,
2004 ).
F om hese defini ions, and aking in o accoun ha i h =
min { , g} , he le el se o h is he union o he le el se s o and
g , we ha e:
Lemma 9. H
+
ij
(η) = G
+ ,a
ij
(η) ∪ G
+ ,b
ij
(η) , and H
−
ij
(η) = G
−,a
ij (η) ∪
G
−,b
ij (η)
Consequen ly, bo h H
+
ij
(η) and H
−
ij
(η) a e he union o wo con-
ex (bu possibili y no disjoin ) se s. The ollowing example shows
ha G
+ ,a
ij (η) ∩ G
+ ,b
ij
(η)  = ∅ , o some η- alues, wi h η< || A
i
−A
j
|| .
In Fig. 4 , we ha e || A
i
−A
j
|| =√
409
2 ≃ 10 . 11 . Fig. 6 (a) displays,
o α= 0 . 4 and η= 10 , he bounda ies o he suble el se s G
+ ,a
ij
(η)
and G
+ ,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 ≤η< || A
i
−A
j
|| , H+
ij
(η) ∩ H
−
ij
(η) = ∅ ,
i.e., i he e exis s a pa h om A
i
o A
j
wi h leng h sho e han he
Euclidean (plana ) a el dis ance, hen he o de in which X
1
and X
2
a e passed is uniquely de e mined.
ab c
Fig. 6. (a): Fo

d
ij
= 10 , cu es
G
+ ,a
ij
,
G
+ ,b
ij
, and se Q
+
(i, j) = G
+ ,a
ij ∩
G
+ ,b
ij
. (b): Se P((i, j) , (k, )) , o

d
k = 10 . 5 . (c): Ve ex
(X

1
, X

2
) in he bounda y o a egion R .
P oo . Le 0 < η<  A
i
−A
j
 and assume H
+
ij
(η) ∩ H
−
ij
(η)  = ∅ . Then
he e exis s ( X
1
, X
2
) such ha
 A
i
−X
1
 + αd(X
1
, X
2
) +  A
j
−X
2
 ≤η
 A
i
−X
2
 + αd(X
1
, X
2
) +  A
j
−X
1
 ≤η.
Summing up and using ha d ( X
1
, X
2
) ≥0 we ob ain ha
 A
i
−X
1
 +  A
j
−X
1
 +  A
i
−X
2
 +  A
j
−X
2
 ≤2 η.
Due o he iangle inequali y, we ha e ha  A
i
−A
j
 ≤ A
i
−
X
k
 +  A
j
−X
k
 o k = 1 , 2 . This gi es us
2  A
i
−A
j
 ≤ A
i
−X
1
 +  A
j
−X
1
 +  A
i
−X
2
 +  A
j
−X
2
 ≤2 η,
a con adic ion o he assump ion ha η<  A
i
−A
j
 . 
Le { L
p
, L
q
} be an ipodal o each o he . Fo a gi en poin ( X
1
, X
2
)
∈ L
p ×L
q
, he objec i e alue F (X
1
, X
2
) =

(i,j) ∈ C(X
1
,X
2
)
ij
quan i-
fies he amoun o weigh s o OD-pai s cap u ed by such a poin .
Taking in o accoun Defini ion 1 , le H
ij
be he se o poin s which
co e he OD-pai ( i , j ), gi en by
H
ij
= { (X
1
, X
2
) ∈ L
p
×L
q
:
ij
(X
1
, X
2
) ≤
d
ij
} .
The ollowing esul ollows di ec ly om he defini ion
Co olla y 11. ( X
1
, X
2
) ∈ H
ij
i and only i ( i , j ) ∈ C ( X
1
, X
2
) .
In o de o ob ain H
ij
om he abo e defined suble el se s, we
eplace he η- alues by he specific accep ance le el 
d
ij
associa ed
wi h each OD-pai ( i , j ).
Rema k 12 (No a ion) . Gi en an accep ance le el 0 ≤
d
ij
< || A
i
−
A
j
||
2
, o ∈ { a , b } le us deno e G
+ ,
ij
(

d
ij
) and G
−,
ij
(

d
ij
) by G
+ ,
ij
and G
−,
ij , espec i ely. This abb e ia ed no a ion is also applied o
he se s H
+
ij
(

d
ij
) and H
−
ij
(

d
ij
) , which will be iden ified by H
+
ij
and
H
−
ij, espec i ely.
Co olla y 13. Fo each OD-pai ( i , j ), H
ij
= H+
ij ∪ H
−
ij = G
+ ,a
ij ∪ G
+ ,b
ij ∪
G
−,a
ij ∪ G
−,b
ij .
P oo . Since
ij
(X
1
, X
2
) = min { h+
ij
(X
1
, X
2
) , h−
ij
(X
1
, X
2
) } =
ji
(X
1
, X
2
) ,
he esul ollows om Lemma 9 . 
5.1.2. Iden i ying a fini e domina ing se
We now b iefly commen on he ole o H
ij
in he cons uc-
ion o a Fini e Domina ing Se (FDS). Recall ha C(X
1
, X
2
) =
{ (i, j) , . . . , (k, ) } is he se o OD-pai s co e ed by ( X
1
, X
2
).
Co olla y 11 implies ha (X
1
, X
2
) ∈ H
ij
∩ . . . ∩ H
k
. Fo his eason,
we nex analyze he in e sec ions o hese se s, since such in e -
sec ions will p o ide he poin s o be inco po a ed in he FDS, as
we will see in he ollowing. In ac , due o he absence o con ex-
i y o bo h H
+
ij and H
−
ij, we will ocus he e o on selec ing poin s
om he bounda ies o all hese se s (as well as om hei in e -
sec ions), in o de o gua an ee ha he selec ed poin s belong o
all se s in ol ed in he in e sec ion.
Hence o h we will use he no a ion G (o H ), o iden i y he
bounda y o le el cu e o a se G (o H ). Tha is, o ∈ { a , b }, we
ha e
G
+ ,
ij = { (X
1
, X
2
) ∈ L
p
×L
q
: g
+ ,
ij
(X
1
, X
2
) = 
d
ij
}
H
+
ij = { (X
1
, X
2
) ∈ L
p
, L
q
: h+
ij
(X
1
, X
2
) = 
d
ij
} ,
and analogously o G
−,
ij and H
−
ij
. Clea ly, o τ∈ { + , −} , H
τ
ij ⊆
G
τ,a
ij ∪ G
τ,b
ij
, and H
τ
ij = G
τ,a
ij ∪ G
τ,b
ij
i he se G
τ,a
ij ∩ G
τ,b
ij con ains a
mos one poin . Likewise
H
ij
= { (X
1
, X
2
) ∈ L
p
×L
q
:
ij
(X
1
, X
2
) = 
d
ij
} .
Since om P oposi ion 10 , H
+
ij ∩ H
−
ij = ∅ , we i ially conclude
Co olla y 14. H
ij
= H
+
ij
∪ H
−
ij
.
As we ha e al eady seen, in o de o cons uc he FDS o p ob-
lem (2-TCR) (1), we will successi ely selec se e al easible poin s
om hese le el cu es and hei in e sec ions.
Lemma 15. Gi en wo di e en OD-pai s ( i , j ), ( k , ), le
P((i, j) , (k, )) ⊂L
p
×L
q be he se o in e sec ion poin s defined as
ollows:
P((i, j) , (k, )) =

( G
τ,
ij ∩ G
τ
,

k
) , τ, τ
∈ { + , −} , ,

∈ { a, b}.
Then, H
ij
∩ H
k
⊆P((i, j) , (k, )) .
P oo . H
ij
= H
+
ij
∪ H
−
ij
⊆( G
+ ,a
ij ∪ G
+ ,b
ij
) ∪ ( G
−,a
ij ∪ G
−,b
ij
) , and a simi-
la inclusion can be ob ained o H
k
. The e o e we can w i e
H
ij ∩ H
k
⊆G
+ ,a
ij ∪ G
+ ,b
ij ∪ G
−,a
ij ∪ G
−,b
ij 

G
+ ,a
k ∪ G
+ ,b
k ∪ G
−,a
k ∪ G
−,b
k .
Clea ly, P((i, j) , (k, )) is he igh -hand side o his exp ession
since P((i, j) , (k, )) is ob ained by in e sec ing each se o he
fi s g oup wi h each se o he second g oup. This concludes he
p oo . 
Defini ion 16. Fo each OD-pai ( i , j ), le Q (i, j) = Q
+
(i, j) ∪
Q
−(i, j) be a se o easible poin s o H
ij
= H
+
ij
∪ H
−
ij
, whe e o
each τ∈ { + , −} :
Q
τ(i, j) =
⎧
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎩
G
τ,a
ij ∩ G
τ,b
ij
,i his in e sec ion con ains a leas
one easible poin .
{ X
a
, X
b
} , o he wise, whe e he poin s X
a and
X
b a e a bi a ily selec ed om
G
τ,a
ij , G
τ,b
ij
, espec i ely.
Clea ly Q
τ(i, j) ⊂H
τ
ij
, o τ∈ { + , −} .
Fig. 6 (a) and (b) shows some o hese se s.
Fig. 6 is based on he ne wo k o Fig. 4 , wi h α= 0 . 4 . We ha e
conside ed he poin s A
i
(2.5, 6), A
j
(1 , −4) , A
k
(−2 , −4 . 5) and A
(3,
5.5). Fo 
d
ij
= 10 and 
d
k
= 10 . 5 , Fig. 6 (a) shows he cu es G
+ ,a
ij
and G
+ ,b
ij
, as well as he co esponding se Q (i, j) = G
+ ,a
ij ∩ G
+ ,b
ij
con aining wo in e sec ion poin s (in his case H
−
ij = ∅ ). Likewise,
Fig. 6 (b) displays he se o in e sec ion poin s P((i, j) , (k, )) con-
aining h ee poin s. In his figu e only a b anch o he cu e G
−,a
k
is inside he easible domain.
Theo em 17. Fo he conca e es ic ed p oblem (2-TCR) (1), le Q and
Pbe he se s defined as ollows
Q =

(i,j)
Q (i, j) , P = 
(i,j)  =(k, )
P((i, j) , (k, ))
Then, o any a bi a y poin X
pq
∈ L
p
×L
q
, he se = Q ∪ P ∪ { X
pq
}
is an FDS o he p oblem (2-TCR) (1)
P oo . Le G =

(i,j)
{ G
τ,
ij
, τ∈ { + , −} , ∈ { a, b}} ⊂L
p
×L
q be he
collec ion o all le el cu es o he es ic ed p oblem (2-TCR) (1).
F om bo h Defini ion 8 and subsequen esul s, he collec ion Gin-
duces a pa i ion o he easible domain L
p ×L
q in o a se o
egions { R
s
, s ∈ I } (whe e I is an index se ), such ha bo h F ( X
1
,
X
2
) and C ( X
1
, X
2
) a e cons an in he in e io poin s o each egion
(see Fig. 6 (c)). The possible changes in he objec i e unc ion may
only occu a he poin s on he bounda y o each egion. The e-
o e an FDS o p oblem (2-TCR) (1) can be cons uc ed by selec ing
poin s om he se o bounda ies { R
s
, s ∈ I} .
Gi en a egion R ∈ , we analyze he cases R = L
p
×L
q and
R ⊂L
p ×L
q
.
1. I R = L
p
×L
q
, hen G = ∅ . Hence, F ( X
1
, X
2
), C ( X
1
, X
2
) a e
cons an , o all ( X
1
, X
2
) ∈ L
p ×L
q
. Equi alen ly, any poin
X
pq
= (X
1
, X
2
) ∈ L
p
×L
q is op imal.
2. O he wise, R ⊂L
p ×L
q
, and i s bounda y R con ains a se
o edges: pieces o le el cu es, and possibly some e ex
which is a poin sha ed by (a leas ) wo di e en le el
cu es ( Fig. 6 (c)). All poin s o an edge ob ained om he
le el cu e G
τ,
ij ∈ Gco e he OD-pai ( i , j ). The e o e, gi en
a se o edges inciden o a e ex, such a e ex co e s
all OD-pai s associa ed wi h hese edges. In o he wo ds: i
(X

1
, X

2
) is a e ex, hen F (X

1
, X

2
) ≥F (X
1
, X
2
) , o any poin
( X
1
, X
2
) o each edge inciden o (X

1
, X

2
) . F om his a gu-
men , all e ices o he pa i ion a e selec ed o be in-
co po a ed o he FDS. Addi ionally, i he e is some R
s wi h
none e ex, hen R
s con ains a single le el cu e, in which
case an a bi a y poin o such a cu e is also added o he
FDS.
In he ollowing we p o e ha he FDS hus cons uc ed is
he se . In e ec , a e ex (X

1
, X

2
) o R is he in e sec ion
poin o (a leas ) wo le el cu es, and hese cu es can be
ob ained ei he om a single OD-pai ( i , j ) o om (a leas )
wo OD-pai s ( i , j ), ( k , ).
(a) In he fi s case, Lemma 9 and P oposi ion 10 imply
ha (X

1
, X

2
) ∈ G
τ,a
ij ∩ G
τ,b
ij
. F om Defini ion 16 , his in-
e sec ion is he se Q
τ(i, j) .
(b) Le assume wo edges associa ed wi h he OD-pai s ( i ,
j ) and ( k , ) a e inciden o (X

1
, X

2
) . This means ha
(X

1
, X

2
) is ob ained om he in e sec ion G
τ,
ij ∩ G
τ
,
k
,
o some τ, τ
∈ { + , −} and ,

∈ { a , b }, which implies
ha i belongs o he se P((i, j) , (k, )) .
S eps (a) y (b) a e epea ed wi h each e ex o he pa i ion
. A he end o his p ocess, all e ices o he case (b) a e
he se P. On he o he hand, an a bi a y poin is selec ed
om each R
s wi hou e ices: hese a bi a y poin s, o-
ge he wi h all e ices o he case (a), a e he se Q . Finally,
he a bi a y poin X
pq
may be selec ed as one o poin s p e-
iously selec ed (in ac , X
pq is necessa y only i G = ∅ ). This
concludes he p oo . 
5.2. The con ex case
This p oblem, iden ified by (2-TCR) (2), is o mula ed by adding
he assump ion ha { L
p
, L
q
} a e no an ipodal o each o he o p ob-
lem (2-TCR) .
In his case, when ( X
1
, X
2
) ∈ L
p ×L
q
, om Lemma 7 and
he subsequen easoning, he dis ance d ( X
1
, X
2
) is con ex. Mo e
specifically, we ha e
d
a
((X
1
, X
2
) = d
b
(X
1
, X
2
) = d(X
1
, X
2
) .
Consequen ly, all esul s o he p e ious sec ion a e alid o (2-
TCR) (2) aking in o accoun ha we now ha e:
H
+
ij = G
+ ,a
ij = G
+ ,b
ij
, and H
−
ij = G
−,a
ij = G
−,b
ij
.
The e o e, om P oposi ion 10 and Co olla y 13 , bo h H
+
ij and H
−
ij
a e con ex and disjoin se s such ha H
ij
= H+
ij ∪ H
−
ij. Likewise,
o his p oblem he se Q (i, j) o Defini ion 16 becomes he se
Q (i, j) = { X
+
, X
−} , whe e X
+
= (X
+
1
, X
+
2
) and X
−= (X
−
1
, X
−
2
) a e
poin s a bi a ily selec ed om H
+
ij
and H
−
ij
, espec i ely. And o
each wo di e en OD-pai s ( i , j ), ( k , ), he se P((i, j) , (k, )) o
Lemma 15 is now gi en by
P((i, j) , (k, )) = 
(i,j)  =(k, )
( H
ij
∩ H
k
) = { H
+
ij
∩ H
+
k
} ∪ { H
+
ij
∩ H
−
k }
∪{ H
−
ij
∩ H
+
k
} ∪ { H
−
ij
∩ H
−
k
} .
Wi h hese se s, Theo em 17 emains alid and es ablishes ha
= Q ∪ P ∪ { X
pq
} is a FDS o his p oblem.
Finally, since C
V
is a cons an se , i ollows s aigh o wa dly:
Co olla y 18. Le us conside ha he e exis s a se o s a ions loca ed
on he nodes o he ne wo k. Then, is also a FDS o he p ob-
lem in which he se C
V
is excluded: max
(X
1
,X
2
) ∈ L
p
×L
q
F (X
1
, X
2
) :=

(i,j) ∈ C(X
1
,X
2
) C
V
ij
.
5.3. Example
This example, based on he ne wo k o Fig. 4 , illus a es he
abo e p ocedu e.
The exis ing demand is loca ed a he poin s: A
1
(2.5, 6),
A
2
(3, 5.5), A
3
(5 . 5 ,
√
6 / 10) , A
4
(2 , −4 . 5) , and A
5
(1 , −4) . The pa i-
ion o he ne wo k o igina ed by he se o linea a c segmen s
L = { L
p
, p = 1 , . . . , 8 } p o ides 36 di e en es ic ed p oblems
on he pai s {{ L
p
, L
q
}, p = 1 , . . . , 7 , q = p + 1 , . . . , 8 } ∪ {{ L
p
, L
p
} , p =
1 , . . . , 8 } , ( he pai s { L
p
, L
q
} and { L
q
, L
p
} gi e ise o symme ic e-
s ic ed p oblems wi h he same solu ion). Among all hese pai s,
{ L
2
, L
6
}, { L
1
, L
5
} and { L
3
, L
7
} a e an ipodal o each o he , and he
emaining pai s a e no .
Fig. 7. Le : Collec ion Gand pa i ion  o he conca e es ic ed p oblem on { L
2
, L
6
}, and poin s o he FDS
. Righ : FDS o he subp oblem (1) on { L
2
, V ( L
6
)}.
We conside α= 0 . 4 . The ma ices T = (
ij
) and 
D = (

d
ij
) con-
aining he weigh s and he accep ance le els o all OD-pai s, e-
spec i ely, a e gi en by
T =
⎛
⎜
⎜
⎝
0 30 15 28 14
16 0 32 45 23
40 25 0 20 20
28 45 26 0 30
14 20 23 30 0
⎞
⎟
⎟
⎠

D =⎛
⎜
⎜
⎝
0 0 . 5 6 10 . 2 10
0 . 5 0 5 9 . 2 8 . 5
6 5 0 5 . 5 5
10 . 2 9 . 2 5 . 5 0 1
10 8 . 5 5 1 0
⎞
⎟
⎟
⎠
Wi h his scena io we fi s ha e conside ed he conca e es ic ed
p oblem:
max
(X
1
,X
2
) ∈ L
2
×L
6
F (X
1
, X
2
) := 
(i,j) ∈ C(X
1
,X
2
)
ij
No e ha o ( X
1
, X
2
) ∈ L
2 ×L
6
, X
1
= (x
1
, 0) ∈ L
2 and X
2
=
(x
2
, 2
√
6 ) ∈ L
6
, he e o e each poin ( X
1
, X
2
) ∈ is iden ified as
x = (x
1
, x
2
) . Wi h his no a ion, x
k
= (x
k
1
, x
k
2
) deno es he k h local
solu ion (X
k
1
, X
k
2
) o his subp oblem (i any).
Fig. 7 (le ) shows he FDS , cons uc ed om all e ices o
he pa i ion . The local solu ion o his subp oblem is eached
a bo h x
1
= (4 . 556013 , 2 . 90379) and x
2
= (4 . 776812 , 2 . 950328) ,
wi h x
1
∈ P((2 , 3) , (2 , 4)) and x
2
∈ P((1 , 5) , (2 , 4)) . Fo hese
poin s, he pai s co e ed and he objec i e alue a e (1, 3), (1, 4),
(1, 5), (2, 3), (2, 4) and 286, espec i ely.
The ollowing objec i e alues (in dec easing o de ) a e ob-
ained om he con ex es ic ed p oblems on { L
3
, L
6
} and { L
1
,
L
6
}. Le F
∗
p,q
be he op imum objec i e alue o he es ic ed p ob-
lem (2-TCR) . Table 1 summa izes he esul s o he abo e h ee
subp oblems. The local solu ions o he emaining es ic ed p ob-
lems p o ide subs an ially lowe objec i e alues, and hey ha e
no been included in his able.
The solu ions ob ained om he es ic ed p oblem on { L
2
, L
6
}
a e also global solu ions o he 2- ans e p oblem on he o e -
Table 1
Bes op imum alues o he 2- ans e p oblem.
Res ic ed
p oblem
Local solu ions C ( X
1
, X
2
)F
∗
p,q
{ L
2
, L
6
}x
1
=
(4 . 556013 , 2 . 90379) (1, 3), (1, 4), (1, 5), (2, 3), (2, 4) 286
x
2
=
(4 . 776812 , 2 . 950328)
{ L
3
, L
6
}x
3
=
(5 . 1 , 3 . 075407) (1, 3), (1, 4), (2, 3), (2, 4) 258
{ L
1
, L
6
}x
4
=
(0 , 2 . 2126927) (1,4), (1,5), (2,4), (2,5) 217
x
5
=
(0 , 3 . 1439062)
all ne wo k. The global op imum is F
∗= F
∗
2 , 6
= F (X
∗
1
, X
∗
2
) = 286 , o
(X
∗
1
, X
∗
2
) ∈ { (X
k
1
, X
k
2
) , k = 1 , 2 } .
6. The case o loca ing a single ans e poin
The abo e p ocedu e also sol es he case o loca ing one ans-
e poin . In e ec , as we ha e a gued a he beginning o his
pape , he o mula ion o he 1- ans e addi ional co e ing p ob-
lem (1-TAC) is made unde he hypo hesis ha all nodes o V (o
a subse o hem) a e al eady loca ed ans e poin s. F om his as-
sump ion, p oblem (1-TAC) can also be sol ed by adap ing he p o-
cedu e desc ibed o he 2- ans e es ic ed p oblem (2-TCR) o
a se o subp oblems dealing wi h he es ic ion o p oblem (1-
TAC) o each linea a c segmen L
p
∈ L .
The 1- ans e p oblem (1-TAC) can be e o mula ed as ol-
lows:
max
L
p
∈L
max
X∈ L
p
F
V
(X ) := 
(i,j) ∈ C(X) C
V
ij
= 
(i,j) ∈
X
2
∈ V
C(X,X
2
)
 C
V
ij
whe e we ha e applied ha C(X) =

X
2
∈ V
C(X, X
2
) . The es ic ion
o (1-TAC) o L
p
∈ L is:
max
X∈ L
p
F
V
(X ) := 
(i,j) ∈
X
2
∈ V
C(X,X
2
)
 C
V
ij (1-TACR)