WSEAS TRANS. on INFORMATION SCIENCE & APPLICATIONS Issue 4. Volume 3 Ap il 2006 ISSN: 1790-0832 737
Planning a Ring-T ee Ne wo k o p o ide Telecommunica ion Se ices
a Cen es o Ru al Popula ion
PABLO CORTES*, JESUS MUNUZURI, JOSE GUADIX, NICOLAS IBANEZ
Depa men Ingenie ia de O ganizaci6n
Uni e si y o Se ille
c/ Camino de los Descub imien os sin, 41092 -Se ille
SPAIN
*[email p o ec ed] h p://io.us.es/Componen es/P.Co es/
Abs ac : -Nowadays ce ain cen es o u al popula ion a e expe imen ing di icul ies o access high-speed
elecommunica ion ne wo ks. This phenomenon a oids he possibili y o accessing o he digi al e olu ion o
such a eas. The p i a e companies a e ocusing hei in es men e o s in o he mo e p o i able a eas. In such
condi ions, he go e nmen s ha e o p omo e al e na i es o b idge he digi al di ide be ween u al and u ban
a eas. We p esen how ing- ee opologies can be used as an adequa e a chi ec u e o inco po a e such less
a ou ed a eas in he In o ma ion Socie y. We p esen a case s udy o Andalucia (a wide egion in he sou h o
Spain) whe e a decision suppo sys em based on a gene ic algo i hm is implemen ed p o iding cos e ec i e
solu ions. We make use o eal li e da a om he elecommunica ion indus y and p esen di e en solu ions
sepa a ed by co e age as well as a sensi i i y analysis based on he main ac o s o he cos unc ion.
Key-Wo ds: - ing- ee ne wo k, digi al di ide, u al pop ila ion, gene ic algo i hms, ibe op ic, case s udy
1 In oduc ion
Nowadays ce ain cen es o u al popula ion a e
expe imen ing di icul ies o access high-speed
elecommunica ion ne wo ks. I supposes a g ea
ba ie o i s de elopmen embedded in o he
modem digi al socie y. Ce ainly, he access o
in o ma ion and communica ion echnologies can .
launch small and medium-sized inns di ec ly in o
he hea o egional, na ional and global ma ke s.
Also, elemedicine can p o ide access o up- o
da e heal h and medical in o ma ion o e en he
mos emo e communi ies. These echnologies
will acili a e low-cos dis ance lea ning. And
hey can empowe ci il socie y, s eng hen
democ a ic ins i u ions and make go e nmen s
mo e anspa en and accoun able, [lJ.
The e a e no many scien i ic e e ences
dealing wi h his p oblem. Al hough, [2] shows
how he use o new in o ma ion echnologies can
imp o e he compe i i eness in u al small
businesses. Howe e he p oposals a e in e ms o
business solu ions, bu no in e ms o
communica ion in as uc u e.
Un o una ely, hose communi ies ha mos
need he boos ha he echnologies o he
in o ma ion and communica ion can p o ide a e
leas able o ake ad an age o i . Because, he
In o ma ion Socie y e olu ion is suppo ed
h ough he elecommunica ion ne wo ks
deploymen . The high cos o such in as uc u es
o ces he companies o ocus hei e o s in he
p o i able communi ies. To gi e a solu ion o i ,
he go e nmen s ha e o p omo e al e na i es o
b idge he digi al di ide be ween u al and u ban
a eas. And in many cases hese ac ions mus
include he unding o new elecommunica ion
in as uc u es.
As in o he pa s o he wo ld, in Spain, he
p i a e companies ha e ocused hei ne wo k
ex ension and mode nisa ion s a egic plans on he
mo e p o i able communi ies. I is he case o he
big ci ies o he coun y. Recen ly, he Andalusian
Regional Go e nmen has been leading a se ies o
ini ia i es aimed a p omo ing he de elopmen o
ibe op ic ne wo ks a ound he egion. And i s
plan ies o p omo e he de elopmen o such
ne wo ks, especially, o he less a ou ed a eas.
This objec i e is he s a ing poin o ou wo k.
The Gene al Di ec o a e o he In o ma ion
Socie y o he Jun a de Andalucia asked us o a
ool capable o e alua ing he in es men olume
equi ed o se up a ibe op ic ne wo k. This
ne wo k would ha e o a i e up o he less
a ou ed a eas o Andalucia and o connec hem
o he bigge ci ies. So ou objec i e was he
gene a ion o a ool capable o designing a cos -
738 WSEAS TRANS. on INFORMATION SCIENCE & APPLICATIONS Issue 4, Volume 3, Ap il 2006 ISSN: 1790-0832
e icien backbone ne wo k allowing b idging he
digi al di ide and ge ing access o he less
a ou ed u al zones.
The es o his pape deals wi h he
iden i ica ion o he digi al di ide in Andalucia,
and he desc ip ion o he echnological
backg ound ( espec i ely in sec ion 2 and 3).
Subsequen ly, we p esen he model conside ed o
design he ne wo k in sec ion 4, and he decision
suppo sys em based on a gene ic algo i hm in
sec ion 5. The main esul s a e showed in sec ion
6. Finally we inish ou pape wi h he mo e
ele an conclusions.
2 The digi al di ide in Andalu�ia
In Eu ope, he digi al di ide is a phenomenon ha
is p oduced due o he disconnec ion be ween he
u al and u ban communi ies. I is because he
u al a eas and i s municipali ies end o be non
p o i able o he p i a e companies. So he
elecommunica ion ne wo ks do no each hose
zones.
Recen ly, he EU Conunission S a wo king
pape , [3], has s a ed he guidelines on c i e ia and
modali ies o implemen a ion o s uc u al unds
in suppo o elec onic communica ions. The
wo king pape shows how he demand
agg ega ion o b oadband se ices should be
encou aged in o de o ensu e c i ical mass o
use s in public adminis a ions whils a oiding
dependence on one single ope a o . Fu he mo e
he s imula ion o demand o ypes o 'clus e s'
o SMEs allows inc easing awa eness and use o
JCT. The ac ua ions ha he wo king pape s a es,
mus be use ul o inance con en , including e
go e nmen , in pa icula local and egional
se ices in o de o boos demand o b oadband
on a su icien ly ocused basis o de elop supply.
Also he Commission s a es ha he Public
au ho i ies, and pa icula ly he Regional
au ho i ies (as he case o he Jun a de Andalucia
is) and local au ho i ies, ha e a key ole o play in
he de elopmen o he in o ma ion socie y by (1)
using in o ma ion socie y applica ions and
se ices in he p ocess o mode nisa ion o
se ices p o ided o ci izens and companies, (2)
p omo ing he in o ma ion socie y in he egion
and (3) moni o ing he e olu ion o he
communica ions ne wo ks and se ices p o ision
on he egion in o de o a oid exclusion and
con ibu e o he balanced de elopmen o
egional ac i i ies.
In o de o a end o hese guidelines, we
di ided Andalucia in h ee se s. Fi s ly, we
conside as ype A municipali ies hose whe e
exis al e na i e in as uc u e. So, hey a e ci ies
whe e a comme cial compe i ion is p oduced
(basically be ween ADSL and coaxial cable).
Secondly, we s a e ype B municipali ies as hose
whe e only exis ADSL bu hey could ha e
enough se ice demand o suppo ano he
elecommunica ion ope a o . Finally, ype C
municipali ies a e hose which has no ADSL
in as uc u e due o a s ong lack o demand.
2.1 Classi ica ion o municipali ies
The e a e 18 ype A municipali ies: Alme ia,
Algeci as, Cadiz, Chiclana de la F on e a, Je ez de
la F on e a, La Linea de la Concepcion, El Pue o
de San a Ma ia, Ro a, San Fe nando, Sanluca de
Ba ameda, Co doba, G anada, Huel a, Jaen,
Malaga, Alcala de Guadai a, Dos He manas and
Se ille. I supposes 43% o he Andalucia en i e
popula ion (3,164,329 inhabi an s).
The popula ion li ing in ype B municipali ies
is equal o 45% (3,292,609 inhabi an s). The e a e
262 ype B municipali ies. Fu he mo e, we di ide
he ype B municipali ies be ween B 1 and B2.
Type BI municipali ies a e hose whe e he
exis ence o ano he elecommunica ion ope a o
would be p o i able; and B2 municipali ies hose
non-p o i able. The sepa a ion be ween B 1 and B2
was done conside ing he expec ed Payback
pe iod, he Ne P esen Value (NPV) and he
In e nal Ra e o Re u n (IRR) o each ype B
municipali y. See [4] o an in dep h discussion. In
o de o ealize he analysis we conside ed he
ini ial in es men as a unc ion o he municipali y
size. Basically, we conside ed he DSLAM cos
(including a ixed pa and ano he a iable
depending on he numbe o use s). As incomes,
Cl ENCE & APPLJCATIO S Issue 4, Volume 3. Ap il 2006 ISS 1790-0832 739
we conside ed he mon hly a i mul iplied by he
expec ed demand. The demand was calcula ed by
using di e en s a is ical app oxima ion me hods
(mo ing a e age, exponen ial smoo hing, Hol ,
linea eg ession and quad a ic eg ession) and
minimising he his o ical e o obse ed by a
pa ame ic composi ion o hem. [ 4] discusses in
dep h abou he demand es ima ion. As cos s, we
conside ed he ope a ion and main enance cos s as
a 10% o he incomes ( ollowing habi ual alues
om he Indus y). He e he possible enla gemen
o he DSLAM capaci ies was also included.
Finally, o di e ence be ween ype B 1 and
ype B2 we selec ed an IRR uppe han 120% and
a NPV uppe han 3 millions o eu os o a 10
yea s ho izon. The esul was 43 ype B 1
municipali ies and 219 ype B2. The analysis
leads o a s anda d Bl own wi h 32,500
inhabi an s and a s anda d B2 own wi h 8,600
inhabi an s. The es o he owns we e conside ed
ype C. So we manage 490 municipali ies ha
ep esen he 12% o he en i e popula ion o
Andalucia, i.e. 883,637 inhabi an s.
Figu e 1 ep esen s he main cha ac e is ics o
he municipali ies ( he demand is exp essed as he
expec ed numbe o "equi alen ADSL lines" o
he inal pe iod o he ho izon). Each "equi alen
ADSL line" is conside ed wi h a capaci y o 256
Kb/s. So, inal use s wi h capaci ies uppe han
256 Kb/s a e con e ed in he co esponden
numbe o "equi alen ADSL lines".
Amoun o Popula ion
Numbe o munlclpall les
Demand olume
Figu e 1. Municipali y classi ica ion
The numbe o municipali ies in he bad pa o
he digi al di ide is 709. I is a popula ion equal o
2,780,327 inhabi an s, and mos o hem a e li ing
in u al a eas. I ep esen s a g ea olume o he
Andalusian popula ion ha will su e s ong
di icul ies o access o he In o ma ion Socie y
and i s bene i s. Figu e 2 de ails he main
cha ac e is ics o he digi al di ide.
Numbe o munlclpall les
C
....
Popula ion
(.,,.
.MI.HO·,
.. �
Nl.1)1:
12�
Demand and Popula ion
Figu e 2. Main cha ac e is ics o he digi al di ide
3 Technological backg ound
The e a e a wide ange o echnological
al e na i es o allow he deploymen o high-speed
elecommunica ion ne wo ks. The i s di ision
ha we ha e o unde ake is be ween he access
ne wo k (u ban ne wo k) and he backbone
ne wo k (in e -u ban ne wo k). Nex igu e 3
depic s he di e en al e na i es o be conside ed.
,....,.,
, . .,
'•C
Topological { : ���,��!,101
al e na i es � R,ng. Mul iple S o
•Ring· R:ing
Backbone
Access
Ne wo k
. :�
!i ;�
.::; ·,
-�·
)' ./� '
lechnological
al e na i es { • Swi ched ne wo,k· PSTH l0SN, x0Sl)
• Coble; HFC
• Fixed eellulo : Wll·LMOS
• MobMa ce l kl · GSM. UMTS
• So ellil•. DVB
Figu e 3. Access ne wo k and backbone
The mos signi ican cos in he access ne wo k
is he local loop. The access ne wo k p esen s a
g ea echnological he e ogenei y. The physical
media can be ibe op ic, coaxial cables, coppe
cables cellula adio o e en sa elli e. And he
echnology can include adi ional public swi ched
elephone ne wo ks, PSTN, IDSN o xDSL, as
well as cable elecommunica ion ne wo ks (HFC),
ixed cellula ne wo ks (WLL-LMDS) o mobile
ne wo ks (GSM, UMTS) in addi ion o he
sa elli e mul icas (DVB). Figu e 4 shows se e al
o hese al e na i es.
I :::·
·
..
1111
=-��
Figu e 4. Technological al e na i es o access
ne wo ks
ISS 1790-0832
Bu he mos impo an pa o he deploymen
cos o a uni e sal elecommunica ion ne wo ks is
he cos o he backbone ne wo k. The backbone
p esen s ce ain homogenei y due o he eno mous
ad an ages o he ibe op ic (using SDH o WDM
s anda ds).
Se e al al e na i es can be used o he
ex ension o unk links in he backbone. They
depend on he ansmission capaci y and he
leng h o he link:
•Fibe op ic o high quali y wi hou
egene a o s. They achie e op ical
ampli ica ion each 100 kilome es. High
quali y monomode ibe is necessa y, as well
as e bium-doped ibe ampli ie s. This sys em
need no elec o-op ic con e sion, and when i
1s combined wi h wa eleng h di ision
mul iplexe (WDM/DWDM) can each
capaci ies up o 100 Gb/s.
•Fibe op ic wi h egene a o s. This op ion
does no equi e so e icien and also
expensi e equipmen . Lowe quali y ibe can
be used bu i equi es he ins alla ion o
egene a o s each ce ain dis ance ( ypically
40-50 kilome es). I is adequa e o capaci ies
up o 2.4 Gb/s and dis ances sho e han 150
kilome es.
•Digi al adio communica ion. I is limi ed o
capaci ies up o 34 Mb/s. Fu he mo e he
land o og aphy mus be aken in o accoun .
Nex sec ion 4 p esen s he design model. In i ,
we ocus he p oblem in he backbone design, bu
conside ing he necessa y e minal in es men
( he local loop). So he las mile co esponding o
he selec ion among he echnological al e na i es
is no conside ed he e and i will depend on he
inal decision o he p i a e company. The
objec i e o he wo k is o se up an exis ing
in as uc u e capable o eaching he non
p o i able poin s o he u al Andalusian egion.
In o de o concep ualise he p oblem we make
use o G aph Theo y oge he wi h bio-inspi ed
algo i hms o sol e i . The p ocess desc ibed in
his pape shows he concep ualisa ion o a model
ha ep esen s easonably a elecommunica ion
ne wo k, as well as he p ocess ollowed in o de
o achie e a cos -e ec i e ne wo k deploymen
o a egional-size geog aphic a ea.
4 Model
The Theo y o G aph de ines a g aph gi en by a
se o nodes and a cs: G=(N,A). The nodes can
ep esen municipali ies (M) o simple
in e sec ions (S) in he unde lying anspo
ne wo k whe e he elecommunica ions ne wo k is
o be placed. So, hey will be ac i e nodes
(municipali ies) o passi e ones ( ypically
in e sec ions o he g aph no supplying o
ecei ing in o ma ion). A cs ep esen oads
linking wo di e en nodes.
We used he oad ne wo k o Andalucia ha
allows he deploymen o ibe op ic cables. This
ini ial g aph was supplied by he Ins i u o de
Ca og a ia de Andalucia (ICA) in A c/In o
o ma . The g aph is shown in igu e 5.
Figu e 5. Ini ial g aph
4.1 P e ious hypo hesis
P e iously o he design o he ne wo k, he Jun a
de Andalucia s a ed some s a egic decisions ha
had o be aken:
1. The ansmission media would be ibe op ic.
Tha allows o ensu e a ansmission wi h
quali y and capaci y (speed in he o de o
hund ed o Gbi /s).
2. The opology should pe mi he e ou ing o
he lows among he main municipali ies in
case o ails. So, he selec ion o a ing- ee
opology was selec ed because i allowed his
conce n. The ing o such ne wo k would
include all he ype A mu ucipali ies.
Ce ainly, he bi-di ec ional sel -healing ing
has been he mos used opology in he case o
74 1
adi ional public ope a o s due o i s e ilien
wide co e age.
3. The ing should ollow al e na i e ibe op ic
ings being cu en ly p ope y o ope a o s
di e en om he dominan ope a o . Thi is
he case o he a ailable ibe op ic in he
ailway and elec ical ne wo ks. This decision
will make possible a as e deploymen o he
ne wo k in he less a ou ed a eas ca ying
ou he ing deploymen in he las s age. Thi
decision ixes he ing opology o he igu e 6
case.
,
.. .
.. ·. ·. ·"
Figu e 6. Resilien sel -healing ing in he backbone
The ing has wo special cha ac e is ics. One o
hem is he di ec connec ion be ween Se ille
and Huel a. This is o a oid he Do iana
Na u al Pa k, one o he la ges p o ec ed
biosphe e ese es in Eu ope. The o he one is
he di ec connec ion O gi a-Alme ia. This is
due o special di icul ies in he oad ne wo k.
Bo h p oblems a e sol ed by deploying a
pa allel double ibe op ic cable.
4. The ing conside s he da a accumula ion
nodes o In e ne connec ion loca ed in
Se ille and Malaga.
4.2 Cos model
The in as uc u e cos s a e classi ied n ou
ca ego ies:
1. Node cos s:
a. Fixed cos associa ed o he exjs ence
o he node, F; Vi EM. I co esponds
o he e minal cable oom adap a ion

742 WSEAS TRANS. on INFORMATION SCIENCE & APPLICATIONS Issue 4 Volume 3 Ap il 2006 ISSN: 1790-0832
o connec he ibe s in o he
DSLAM.
b. Cos depending on he capaci y
managed by he node. G;(C;), ' lieM.
I co esponds o he modula
equipmen , whe e he ansmi e s and
ecei e s a e placed.
2. A c cos s:
a. Cos depending on he a c leng h,
L;/Di ), l(iJ)eA. I co esponds o he
di ches and condui s.
b. Cos depending on he a c leng h and
i s suppo ed capaci y, C/DiJ,Cmax),
V(i,j)eA. I co esponds o he ibe
op ic links including ansmi e s,
ecei e s and egene a o s o op ical
ampli ie s when needed.
The node cos s (pa 1 ), as well as he a c cos s
depending only on he leng h (pa 2.a) a e
de ailed in appendix 1. On he o he hand, wo
di e en echnological al e na i es a e conside ed
o calcula e he 2.b cos pa .
The i s op ion co esponds o high quali y
ibe op ic link (wi hou egene a o s). I can be
es ima ed as ( 1).
(1)
The second op ion co esponds o lowe
quali y ibe op ic link (wi h egene a o s) ha can
be es ima ed as (2).
C (D C )= /'SDH,i + l'soHd +P ·D
+C - 11+2C ·lc-J
u IJ' .... n� n, > J .., D.,.. DWDl>I c,OGb
Whe e:
(2)
• PsDHo and PsDHd a e he o igin and des ina ion
SDH mul iplexe cos s.
•n0 and nd a e he numbe o links in he SDH
equipmen placed in node. Each SDH
mul iplexe can se e di e se digi al links.
•D/G is he a c dis ance. I is co e ed wi hou
egene a o s.
•D,i is he a c dis ance. I can be co e ed wi h
egene a o s.
•P1
/G is he linea cos o a high quali y cable
o 24 monomode ibe s plus he cos o
connec ing i .
•P1
0 is he linea cos o a s anda d cable o 24
monomode ibe s plus he cos o connec ing
i .
•Coam is he cos o an op ical ampli ica ion
sys em.
•C eg is he cos o a egene a o .
•Dmax is he ampli ica ion maximum dis ance.
Typically 140 kilome es o op ion 1 and 40
kilome es o op ion 2.
•C, is he cos o DWDM in e ace ca d
( ansmi e / ecei e ) wi h capaci y up o 10
Gb/s.
•Cmax is he capaci y ha mus be equipped.
Appendix I de ails he nume ical alues o
bo h op ions.
4.3 Topological model
As sec ion 4.1 s a ed a ing- ee opology was
selec ed. This opology consis s o a hie a chical
s uc u e gi en by nodes o le el I and nodes o
le el 2. Th goal o such a chi ec u e is o simpli y
he subsequen ne wo k managemen .
The le el 1 nodes a e he en la ge ci ies o
Andalusia: Alme ia, Algeci as, Cadiz, Je ez de la
F on e a, Co doba, G anada, Huel a, Jaen,
Malaga and Se ille plus O gi a (a small
municipali y selec ed as pa o he ing due o i s
s a egic geog aphic loca ion) ..
These nodes depic he ing o he backbone
( igu e 6). The es o nodes a e connec ed a one
o hese le el 1 nodes by a ee s uc u e. Howe e
he es o nodes could be loca ed in o he ing
s uc u e o ou o he ing. In he i s case, he
basic in as uc u e has no o be cons uc ed.
The e al eady exis he di ch and condui , so we
only ha e o conside he cos 2.b. In he o he
case ( ou o he ing) we would ha e o conside
he cos s o ci il · in as uc u e (2.a) and
ansmission link (2.b). See igu e 7.
WSEAS TRA S. on JNFORMATIO
all Nodes o ln•I 1
eHodes o le¥el 2 in IM ,ng
QNodu o lenl 2 ou o he ing
Flows be wHn nodu
-- Di ec link be wHn nodes o le el 1 ( ing)
Supa •b anch. Link be wHn nodH o
-- le el 1 and l el 2 h ough lhe ing
B anch. L.ink b wHn nodes o le el 2
and le el 2 ou o he ing
0 ln u n,c u e. Condui and di ch
0 0
Figu e 7. Topological s uc u e
5 Decision Suppo Sys em based on
a gene ic algo i hm
The decision suppo sys em (DSS) is based on a
gene ic algo i hm engine. Gene ic algo i hms ha e
ecen ly been conside ed o deal wi h di e en
kinds o elecommunica ion p oblems. Mos o
hem a e in he scope o heo e ical applica ions.
A wide-scope on gene ic algo i hm was p esen ed
by [5] o design ne wo k ings, and mo e ecen ly
[6] and [7]. [8] p esen ed Gen0Sys ha is a
opology planning ool based on a gene ic
algo i hm o design ee ne wo k in as uc u es.
In his scope, [9] de eloped a gene ic algo i hm
o he design o opologies in op ical ne wo ks. I
is case simila o [ 1 O]. Also, gene ic algo i hms
ha e been used o dynamic packing, [11].
Finally, a eal li e implemen a ion can be ound a
[ 12].
5.1 Decision suppo sys em s uc u e
The DSS inpu s a e he ca og aphy supplied by
he ICA and he socio economic da a wa ehouse
da abase p o ided by he Ins i u e Es adis ico de
Andalucia (IEA).
A e p ocessing he ca og aphy and
conside ing he echnological model and he
s a egic decisions, we ge he opological model,
in e ms o a g aph. The esul was a g aph wi h
Issue 4. Volume 3. Ap il 2006 IS N 1790-0832 743
2 796 a cs and 1 920 nodes. 770 o hose nodes
' '
a e municipali ies, he es a e simple
in e sec ions.
Jn he o he side, he socio economic da a o
he municipali ies o Andalusia plus he his o ical
demand da a a e used o es ima e he
elecommunica ion demand o each o he
municipali ies. The demand alues plus he
inancial analysis o each u ban node allows us o
classi y he municipali ies be ween p o i able and
non-p o i able. This allows iden i ying he digi al
di ide.
These h ee componen s ( he opological
model he cos model and he classi ica ion o
'
municipali ies) a e in oduced in he algo i hm
ha p o ides he solu ion. See igu e 8.
� IEA(SIMA}
� Sooo--eoonom,c da abNe
Digi al di ide
lden l l�a lon n
��� ymg anspo
ne wo <
A c/In o co e ages
EJ
n
!T� modol !llmagic -1.lona
Figu e 8. Decision Suppo Sys em s uc u e
5.2 The gene ic algo i hm
The dimensioning o he ne wo k, as well as he
mul iple opological al e na i es o deploy such
ne wo k makes he compu a ionally complex
p oblem. In ac , he p oblem can be p o ed as
NP-Ha d by simple educ ion o he S eine
p oblem. Fu he mo e, gi en a easible solu ion is
easy o compu e i s e alua ion (i can be done in
polynomial ime), so he p oblem is NP-Comple e
oo. Fo his ype o p oblems me aheu is ics
app oaches ha e been p o ed o be sui able. And
ou p oposal is based on a gene ic algo i hm.
The u iliza ion o gene ic algo i hms allows
ob aining good solu ions in p oblems wi h a high
744 WSEAS TRANS. on INFORMATION SCIENCE & APPLICATIONS Issue 4, Volume 3, Ap il 2006 ISSN: 1790-0832
numbe o complex cons ain s wi h a di icul
ma hema ical o mula ion, as his one is.
The s a egy consis s o gene a ing di e se
easible solu ions (wi h easy e alua ion) and
ecombining hem wi hou losing easibili y. No e
how each easible solu ion o ou p oblem mus
include he p ede ined ing plus he ee (supe 
b anches and b anches, see igu e 7).
The p ocedu e ollows he nex h ee s eps:
1. Cons uc ing a sup a-node co esponding o
he ing. The ing is concep ualised in one
only node composed by all he nodes in he
ing (including municipali ies and passi e
nodes) and wi h so many inciden a cs as each
node o he ing has.
2. Cons uc ing a ee ha con ains he sup a
node and all he municipali ies. The passi e
nodes (in e sec ion o he anspo ne wo k)
can be con enien ly used i necessa y. The
gene ic algo i hm gene a es he ne wo k
p oposal.
3. Dimensioning he capaci y o he ing.
5.2.1 Cha ac e is ics o he gene ic algo i hm
We p oposed a gene ic algo i hm wi h an
encoding o he indi iduals genome as shown in
igu e 9. The encoding consis s o an a ay wi h so
many egis e s as a cs exis in he g aph. I he
egis e is se o one hen he a c will be included
in he solu ion, o he wise he a c will no be in he
solu ion. Addi ionally, he genome mus ensu e
he easibili y o he solu ion. So non- easible
solu ions a e no accep ed.
A e es ing wi h di e en sizes, we ha e
conside ed an ini ial popula ion o 20 indi iduals.
To gene a e hem we ha e use he K uskal
algo i hm o sol e he minimum spanning ee
p oblem -MST. No e ha we a e conside ing he
ing as a sup a-node. So, gi en 20 di e en se s
wi h a c ic i ious cos , we can sol e he
co esponden MSTs and a e wa ds he solu ions
a e cleaned by e asing he passi e nodes loca ed
in a e minal posi ion.
The popula ion size is a majo ac o in he
e ec i eness o gene ic algo i hms. I has been
p o ed ha ela i ely small popula ions allow
eaching success ul solu ions wi h li le
compu a ion e o , [13]. Ou expe imen s show
ha inc easing he popula ion size beyond 20,
al hough inc easing he compu a ional e o , is
no ewa ded by a co esponding inc ease o
pe o mance.
We ha e implemen ed wo di e en gene ic
ope a o s (see igu e 9): c osso e and mu a ion
ope a o s. The pa en selec ion mechanism is
andom in o de o en ich he gene ic a ie y. I
includes a mechanism o inces p e en ion o
a oid he c osso e o gene ically simila pa en s.
•Un i o m c osso e ope a o . I he genome o
bo h pa en s includes he a c in hei solu ion
(i.e. i has he same egis e se o 1, o se o
0), hen he a c is main ained in he o sp ing.
O he wise (only one pa en has he a c) he
a c is main ained wi h a p obabili y equal o
0.5.
•Mu a ion ope a o . The ope a o changes a
egis e om 1 o 0, o ice e sa. Tha is,
once one egis e has been andomly selec ed,
i he a c belongs o he solu ion, hen he a c
is e ased. O he wise, i he a c does no
belong o he solu ion, hen he a c is
included.
The applica ion o he gene ic ope a o s can
lead o un easible solu ions. The possible
in easibili ies a e he ollowing:
•A e applying a c osso e ope a o wo ees
a e connec ed. This si ua ion gene a es a new
g aph and cycles appea . The cycles a e
b oken by e asing a andomly selec ed a c o .
each cycle.
•A e applying a mu a ion ope a o wo
si ua ions can appea :
oI an a c is included in he solu ion, a
cycle can appea . Then, he cycle is
b oken by e asing a andomly
selec ed a c o he cycle.
oI an a c is e ased in he solu ion, he
ee is disconnec ed. Then, he ee is
econnec ed by means o he sho es
pa h algo i hm.
W EAS TRANS. on INFORMATION SCIENCE & APPLICATIONS Issue 4, Volume 3, Ap il 2006 ISSN 1790-0832 745
Genome encoding
l1lol1!olojol1joj1j1j
A, A1 A, A,. A.,.
C osso e ope a o
Pa en 1
Mu a ion ope a o
Figu e 9. Genome encoding and gene ic ope a o s
Tes s we e ca ied ou wi h di e en
p obabili ies o c osso e and mu a ion ope a o s.
Va ying he c osso e p obabili y om 50% o
100% had li le e ec on pe o mance, wi h a
alue o 80-90% being ma ginally op imal o he
es s ca ied ou . A alue o 80% is used in he
main uns. Fo mu a ion, alues be ween 5% and
20% we e seen o be gi ing be e esul s han
ypically smalle alues. A alue o 20% is used
in he main uns in o de o en ich he gene ic
a ie y o he popula ion. Howe e , i is o be
no ed ha he gene ic algo i hm is obus . Tha is,
he es p oblems' solu ions we e achie ed on he
whole wi h a wide ange o pa ame e alues, and
wi h no ine- uning equi ed o achie e e iciency.
The subs i u ion o new indi iduals (o sp ing)
by he old indi iduals (in p e ious popula ion) is
made by a anking based eplacemen . We
p opose he use o hype geome ic unc ions
allowing mo e p obabili y o eplacemen o
indi iduals wi h wo se i ness and less p obabili y
o eplacemen o indi iduals wi h be e i ness.
So he indi idual in anking posi ion-i, ha e a
e�lacemen p obabili y equal o q•( 1-q i, whe e q
is he eplacemen p obabili y o he wo s
indi idual. The alue o he pa ame e q is
p og essi e. I s a s wi h a low alue o q in o de
o explo e he easibili y egion and hen he alue
is p og essi ely inc eased o exploi he niche
quali y.
Addi ionally, we inco po a ed an indi idual
duplici y con ol in he popula ion gene a ion.
The numbe o gene a ions o he gene ic
algo i hm can be a c i ical pa ame e when we y
o each e iciency o he solu ion and sho ime
execu ion. Gene ic algo i hms a e i e a i e, and,
he e o e, hey can ake e y much ime o
execu ion. Howe e he ad an age o gene ic
algo i hms is ha hey can be s opped a any ime
ha ing he be e solu ion a he momen . A e
se e al es s, we selec ed a numbe o 50
i e a ions. The lea ning cu e o he algo i hm is
depic ed in igu e 10.
400,00 -1I
I 295,00 ,h---���---.--,-----.-..-----.-------�
� � m � � N � � � � ; � �
I e a ion
Figu e 10. Leaming cu e
I
Nex Table 1 summa izes he alue o
pa ame e s selec ed.
Table 1. Gene ic al o i hm a ame e s
Po ula ion size, N 20
C osso e ope a o p obabili y (mu a ion 0,8 (0,2)
0,2/0,4/0,6/0,8a
a P og essi e inc ease o q each en gene a ions.
The algo i hm pseudocode is desc ibed in he
appendix 2.
5.2.2 Final dimensioning o he ing capaci y
We p oposed a bi-di ec ional sel -healing ing.
This allows e ou ing he demand lows in case o
ail. The p oblem is o de e mine he capaci y o
he ing ha allows e ou ing all he lows in case
o ail. As he ing capaci y is di ec ly ela ed o
he ing cos , we minimize he capaci y capable o
gua an eeing he demand lows.