Reducing Vehicle Emissions and Fuel Consump ion in he Ci y by
Using Pa icle Swa m Op imiza ion
A. Ca olina Oli e a 1,∗
Depa amen o de Ciencias e Ingenie ´ıa de la Compu aci´on, Uni e sidad Nacional del Su ,
A . Alem 1253, 8000, Bah´ıa Blanca, A gen ina
J. Ga c´ıa-Nie o, E. Alba
Dep . de Lenguajes y Ciencias de la Compu aci´on, Uni e si y o Malaga,
ETSI In o m´a ica, Campus de Tea inos, Malaga - 29071, Spain
Abs ac
Nowadays in cu en ci ies he inc easing le els o pollu ion emissions and uel consump ion de i ed om he oad
affic di ec ly affec o he ai quali y, he economy, and specially he heal h o ci izens. The e o e, imp o ing
he affic flow is a manda o y ask in o de o mi iga e such c i ical p oblems. In his wo k, we p opose a Swa m
In elligence app oach o op imizing signal ligh iming p og ams in me opoli an a eas. In his way, we can
imp o e he affic flow o ehicles wi h he global a ge o educing hei uel consump ion and gas emissions (CO
and NOx). In his a icle we op imize he iming p og ams o signal ligh s and analyze hei effec in pollu ion
by ollowing he s anda d HBEFA as affic emission model. In conc e e, we a e ocused he e on wo la ge and
he e ogeneous u ban ins ances loca ed in he ci ies o Malaga and Se ille (in Spain). In compa ison wi h iming
p og ams o signal ligh s p edefined by expe s (close o eal ones), ou p oposal ob ains significan educ ions in
e ms o he emission a e and he o al uel consump ion.
Key wo ds: T affic Signal Timing, Pa icle Swa m Op imiza ion, SUMO Mic oscopic Simula o o U ban MObili y,
HBEFA T affic Emission Model.
∗Co esponding au ho .
Email add esses: [email p o ec ed],
{jnie o,ea }@lcc.uma.es (J. Ga c´ıa-Nie o, E. Alba).
1Au ho s acknowledge unds om he CICE o
he Jun a de Andalucia, unde con ac P07-TIC-
03044 (DIRICOM h p://di icom.lcc.uma.es) and Span-
ish Minis y o Sciences and Inno a ion (MICINN)
and FEDER unde con ac s TIN2011-28194 (RoadMe
h p:// oadme.lcc.uma.es) and TIN2008-06491-C04-01
(M* h p://ms a .lcc.uma.es). Jos´e Ga c´ıa-Nie o is sup-
po ed by g an BES-2009-018767 om he MICINN. Ana
1. In oduc ion
In cu en me opoli an a eas, he inc easing
le els o ai con amina ion and uel consump ion
de i ed om he u ban oad affic ha e become
highly se ious p oblems ha di ec ly affec o he
C. Oli e a acknowledges CONICET, he ANPCyT o
G an PICT 2011 Ca ego y I-B and SeCyT (UNS) o
G an PGI 24/N026.
P ep in submi ed o Else ie Science July 2, 2012
ai quali y, he economy, he building/s uc u e
main enance, and especially o he heal h o ci -
izens. Imp o ing he affic flow o ehicles is a
manda o y ask in o de o mi iga e such c i ical
issues. T adi ionally, affic conges ion has been
deal wi h changes in u ban in as uc u es (e.g.
sense o affic in s ee s o oundabou s), al hough
his is usually no possible and always expensi e.
Recen ly, a numbe o wo ks in he li e a u e
p oposed he op imiza ion o iming p og ams o
signal ligh s as one o he mos influen me hods
o imp o e he flow o ehicles [20,22,23,28].
In his sense, he use o au oma ic in elligen
me hods ha e demons a ed hei use ulness o
he op imiza ion o iming p og ams o affic
ligh s [3,23]. Howe e , au ho s in gene al ha e
add essed specific cases o s udy wi h ew in e -
sec ions and small numbe o signal ligh s [5],
and mos o hem apply ad-hoc algo i hms de-
signed only o one specific ins ance [3,23]. The
use o a ificial in elligen echniques o la ge and
he e ogeneous u ban a eas is s ill an open issue.
Mo eo e , he op imiza ion o iming p og ams
om he pe spec i e o he educ ion o gas emis-
sion and hyd oca bons consump ion ha e no e e
been deal , o he bes o ou knowledge.
All his mo i a ed us o p opose in his wo k an
op imiza ion s a egy, based in a Pa icle Swa m
Op imiza ion (PSO) algo i hm [16], o find suc-
cess ul signal ligh iming p og ams wi h ega ds
o wo main ac o s: emissions o CO and NOx,
plus he global amoun o uel consumed by ehi-
cles. Se e al ea u es led us o use PSO ins ead o
o he e olu iona y me hods:
– Fi s o all, using a Fi ness Cloud p elimina y
analysis [31], we es ed ha PSO is able o
ackle he signal ligh iming p oblem (SLTP)
efficien ly. A desc ip ion o his analysis is gi en
in Sec ion 5.3.
– Second, he PSO is a well-known algo i hm
shown o pe o m a as con e ge o quasi-
op imal solu ions [8]. This is a highly desi able
ea u e o he op imal iming p og am o affic
ligh s, whe e new adap i e (and au oma ically
compu ed) schedules should be equi ed o ace
upda ing e en s in affic scena ios.
– Thi d, he S anda d PSO is easy o implemen ,
and equi es ew uning pa ame e s [8,16].
– Fou h, PSO is a kind o Swa m In elligence al-
go i hm ha can in o m us on u u e issues o
deal wi h his p oblem by using independen
agen s o online adap a ion (a p omising line o
esea ch).
Coupled wi h PSO, we use in ou op imiza ion
s a egy he mic oscopic simula o SUMO (Simu-
la o o U ban Mobili y) [4] o he e alua ion o
op imized iming p og ams codified as ec o so-
lu ions. Such iming p og ams a e used in signal
ligh s ha con ol he flow o ehicles h ough a
gi en scena io (u ban ins ance). As done in o he
simila ini ia i es [13,14,21], we use a affic simu-
la o since i p o ides an immedia e and con inu-
ous sou ce o in o ma ion abou he ehicles flow.
In he case o SUMO, we can also wo k wi h he
affic emission model HBEFA (HandBook Emis-
sion FAc o s) [15] o oad anspo in o de o ec-
ollec in o ma ion abou he emission a es and he
uel consump ion. This in o ma ion is used by PSO
o e alua e he iming p og ams o signal ligh s.
As main con ibu ions o his wo k, we can men-
ion he ollowing ones:
– We p opose an op imiza ion s a egy o he e-
duc ion o emissions in la ge and he e ogeneous
u ban a eas wi h hund eds o ehicles and signal
ligh s (high dimensionali y and complexi y).
– We use eal in o ma ion: we ha e modeled wo
u ban scena ios loca ed in he ci ies o Se ille
and Malaga, in Spain. Ou op imiza ion s a egy
has been hen e alua ed on ealis ic ins ances.
– In compa ison wi h p edefined (by expe s) im-
ing p og ams close o eal ones, ou PSO will be
shown o ob ain quan i a i e imp o emen s in
e ms o he wo main objec i es: educing he
emission a es and he global uel consump ion.
– We conside o he fi s ime he use o a swa m
in elligen app oach coupled wi h he affic
emission model HBEFA [9], o he educ ion o
pollu ion and uel consump ion in u ban a eas.
The s uc u e o his a icle is as ollows. In Sec-
ion 2, a e iew o ela ed wo ks in he li e a u e
is p esen ed. Sec ion 3 explains he SUMO simula-
ion ool and he HBEFA emission model. Then in
Sec ion 4, ou op imiza ion app oach is desc ibed.
Expe imen s and analysis o esul s a e de ailed in
Sec ion 5. Finally, concluding ema ks and u u e
wo k a e gi en in Sec ion 6.
2
2. S a e o he A
In he las decade, a numbe o wo ks can be
ound in he ela ed li e a u e ha deal wi h he
affic conges ion p oblem by means o accu a e
signal ligh s iming p og ams [6,18,23,24,26,29]. In
all hese app oaches, global ip imes and wai -
ing imes o ehicles in affic ligh s a e op imized,
al hough none o hem conside ed he influence
o solu ions on emissions and uel consump ion
ac o s. On he con a y, a ew o wo ks can be
ound ha inco po a ed emission/consuming ac-
o s in o he affic con ol s a egies by enhancing
he affic flow [11,20] wi h diffe en esul s. In [11],
jus o one in e sec ion (c oss oad), he imp o e-
men o affic ligh s iming p og ams and hei
impac on he final emission a es we e examined.
In [20], he au ho s p oposed a signal ime model
ha educe he ehicles’ delays, he uel consump-
ion, and he gas emissions by conside ing he cy-
cle leng h and he g een ime o affic ligh s in
one in e sec ion in Nanking ci y (China). In [7],
a mic oscopic simula o was used o he e alua-
ion o affic con ol s a egies in a sub-ne wo k
selec ed om he Haidian dis ic o Beijing. This
las wo k was ocused on analyzing he ela ion be-
ween ehicles’ emissions and hei ins an aneous
speeds/accele a ions, al hough affic signal op i-
miza ion was no conside ed and only wo con ol
s a egies we e s udied.
A he same ime, ad anced algo i hms ha e
eme ged as accu a e echniques o sol ing a -
fic ligh s scheduling and affic con ol p ob-
lems [23,26]. Howe e , he en i onmen al impac
o he affic flow is igno ed o pa ially conside ed.
An example o his can be ound in [32] whe e
a Gene ic Algo i hm (GA) was used o he ai
pollu ion educ ion conside ing he op imiza ion
o affic signals in one in e sec ion. In [33], he
au ho s showed how he cycle p og ams o affic
ligh s affec he gas concen a ions on a gi en oad
in e sec ion by using Neu al Ne wo ks.
Conce ning Swa m In elligence app oaches, ew
o hem can also be ound o he schedule o
affic ligh s. One o he mos ep esen a i e was
p oposed in [6], whe e he au ho s applied a PSO
o aining a uzzy logic con olle loca ed in each
in e sec ion by de e mining he effec i e ime o
g een o each phase o he affic ligh s. Peng
e al. [25] p esen ed a PSO wi h isola ion niches
o he schedule o affic ligh s. In ha wo k, a
pu ely academic small ins ance wi h a es ic i e
one-way oad wi h wo in e sec ions was used o
es he PSO. Mo e ecen ly, an An Colony Op-
imiza ion (ACO) [12] has been p oposed o he
signal ligh iming. In his wo k, wo in e es ing
unce ain y and con e gence analysis we e pe -
o med, al hough in he scope o one simple affic
in e sec ion. In hese las wo ks, en i onmen ac-
o s we e no conside ed a all, and only academic
ins ances we e s udied.
All hese app oaches ocused on diffe en aspec s
o he affic ligh scheduling. As a summa y, ou
limi a ions can be ound in gene al:
– They ackled limi ed ehicula ne wo ks wi h
e y ew affic ligh s and a small numbe o
o he elemen s ( oads, in e sec ions, di ec ions,
e c.). In con as , ou PSO can find op imized
iming p og ams o la ge scena ios wi h hun-
d eds o affic ligh s, ehicles, and o he ci y el-
emen s.
– They we e designed o only one specific sce-
na io. Some o hem s udied he influence o
he affic densi y. Ou app oach can be eas-
ily adap ed o diffe en scena io opologies and
ci ies.
– In mos o he cases, exis ing wo ks we e no
compa ed agains o he echniques. Ou PSO is
compa ed he e agains wo diffe en app oaches:
a Random Sea ch algo i hm ( o show ha i
is in elligen ), and he cycle p og am gene a-
o p o ided by SUMO ( ha uses human expe
knowledge).
– P e ious wo ks did no conside he op imiza-
ion o en i onmen al ac o s. Ou app oach con-
side s a se ies o ac o s (CO,NOx, and uel con-
sump ion) ha , coupled wi h pu e affic flow in-
dica o s ( ehicles a i ing a des ina ions, global
ip imes, e c.), p o ide he expe wi h op i-
mized signal ligh iming p og ams: a small s ep
o he u u e sma ci y.
3
… … … … … … 40 5 40 10 36 6 22 … … … … … … …
in e sec ion id=“i+1” in e sec ion id=“i”
phasedu a ion=“36” Solu ion:a pa icle
posi ion o he PSO
algo i hm
Cu en s a e o in e sec ion
i=“ GG GG ”
Figu e 1. Timing p og am (phase du a ion) o signal ligh s wi hin in e sec ions. In ege codifica ion inside a PSO solu ion
3. SLTP: Timing and Emission Models
A u ban affic scena io is basically composed
by: in e sec ions, affic ligh s, oads, di ec ions,
and ehicles mo ing h ough hei own diffe en
ou es. The affic ligh s a e loca ed in in e sec-
ions and con ol he flow o ehicles by ollowing
hei p og ams o colo s a es, and iming cycles o
phase du a ions. In his con ex , all affic ligh s
loca ed in he same in e sec ion a e go e ned by a
common p og am, since hey ha e o be necessa -
ily synch onized o affic secu i y. In addi ion, o
all he affic ligh s in an in e sec ion, he combina-
ion o colo s a es du ing a cycle pe iod is always
kep alid [19] and i mus ollow he specific affic
ules o in e sec ions, in o de o a oid ehicle col-
lisions and acciden s. In his sense, we wo k only
wi h alid combina ions o colo s a es o each in-
e sec ion, which a e kep easible du ing he op i-
miza ion p ocess. This a oids in alid combina ions
o colo s a es and es ic s he op imiza ion ap-
p oach o wo k only wi h easible s a es.
F om an en i onmen al poin o iew, since di -
e en iming p og ams lead o diffe en flow o e-
hicles, hei unde lying speeds, accele a ions, and
decele a ions po en ially esul in diffe en le els
o emissions [33]. In sho , decele a ions occu be-
o e ed ligh s, whe eas g een ligh s cause he ac-
cele a ion o ehicles. The e o e, affic emissions
a e likely influenced by iming p og am o a -
fic ligh s [7]. In his con ex , iming and emission
models a e de ailed in he ollowing subsec ions.
3.1. Timing Model
Ou main objec i e is o find op imized iming
p og ams (TP) o all he signal ligh s loca ed in a
gi en u ban a ea wi h he aim o educing he emis-
sions and he uel consump ion o ehicles. Specifi-
cally, iming p og ams a e e e eed o he ime span
ha a se o signal ligh s (in a junc ion) keep hei
colo s a es. A he same ime, hese p og ams ha e
o coo dina e signal ligh s in adjacen in e sec ions
wi h he aim o imp o ing he global flow o ehi-
cles ci cula ing acco ding o affic egula ions.
Fo his eason, we ha e ocused on a mic oscopic
iew o he managemen o affic agen s bu , a he
same ime, we wan o e alua e he beha io o all
he ehicles in he comple e u ban scena io du ing
a gi en ime in e al (mac oscopic analysis).
An example o his mechanism can be obse ed
in Figu e 1, whe e he in e sec ion wi h id="i"
con ains se en phases wi h du a ions 40, 5, 40, 10,
36, 6, and 22 seconds (simula ion s eps). In hese
phases, he s a es ha e wel e signals (colo s), co -
esponding each one o hem o one o he wel e
signal ligh s loca ed in he s udied in e sec ion.
These s a es a e he alid ones gene a ed by SUMO
(Simula ion o U ban Mobili y) [4] a ending o
eal affic ules. In his ins ance, he fi h phase
con ains he s a e “G GG G GG” meaning
ha six affic ligh s a e in g een (G), and he six
o he s a e in ed ( ) du ing 36 seconds. The ol-
lowing phase changes he s a e o he ou a -
fic ligh s o o he alid combina ion, o example,
4
“yGGG yGGG ” (ymeans yellow) du ing 6
seconds, and so on. The las phase is ollowed by
he fi s one, and his cycle ( iming) is epea ed
du ing all he analysis ime. All he in e sec ions in
he comple e scena io pe o m hei own iming cy-
cles o phases a he same ime, hence con o ming
he global schedule o signal ligh s. As commen ed
be o e, compu ing TP consis s in op imizing he
combina ion o phase du a ions o all affic ligh s
(in all in e sec ions) wi h he aim o imp o ing he
global flow o ehicles.
A final indica ion in his sense conce ns he be-
ha io o he ehicles in ol ed in a SUMO simu-
la ion, ha depends on bo h oad di ec ions and
speed. SUMO employs a space-disc e e ex ended
model as in oduced by K auß e al. [17]. In his
model, he s ee s a e di ided in o cells and he e-
hicles ci cula ing h ough he s ee s go om one
cell o ano he i bo h, he sense and he di ec-
ion a e allowed. The speed o each ehicle depends
on i s dis ance o he ehicle in on o i , wi h
a p ees ablished maximum speed ypical o u ban
a eas (50 km/h in ou s udy).
3.2. HBEFA: Road T affic Emission Model
Many esea ch effo s ha e a emp ed o de elop
emission o oad anspo a ion models. Due o
hei simplici y, a mac oscopic poin o iew has
become e y popula [2] in his sense. This kind o
model compu es uel consump ion (FC) and emis-
sions ac o (EF) based on a e age link speeds in a
global way. Tha is, changes o ehicle’s speed and
accele a ions le els a e compu ed as mean alues
o he whole ne wo k. Fo his eason, many mic o-
scopic models ha e been p oposed. In pa icula ,
HBEFA (Handbook o Emission Fac o s o Road
T anspo ) p o ides emission ac o s o all cu en
ehicle ca ego ies: PC (Passenge Ca ), LDV (ligh
deli e y ehicles), HDV (hea y du y ehicles), u -
ban buses, mo o cycles, and o a wide a ie y o
affic si ua ions. The HBEFA allows expe s o se-
lec diffe en ypes o emission ac o s (EFs). These
EFs depend on many a iables o ehicles such as:
size, ype, cylinde capaci y, uel mode o he ehi-
cle (gasoline o diesel), ype o exhaus echnology
(wi h/wi hou ca aly ic con e e ), d i ing s yle
(accele a ion and speed), oad g adien , and he
main enance [9].
SUMO e sion 0.12.0 [4] allows us o simula e
ehicula en i onmen al ac o s based on HBEFA.
The e o e, i is possible o define ehicles wi h in-
o ma ion abou accele a ion, decele a ion imes,
maximum eloci y, and e en hei HBEFA-based
emission class (PC, LDV, HDV, e c). Then, a e
a simula ion p ocedu e wi h SUMO, we can ob-
ain in o ma ion abou CO,NOx, uel consump-
ion, and o he pollu an agen s o e alua e he
ob ained iming p og ams by ou PSO. Fo his
s udy, we e ie e he in o ma ion abou CO and
NOxemissions, and uel consump ion.
4. Op imiza ion S a egy
This sec ion desc ibes ou op imiza ion ap-
p oach o compu e he op imal iming p og ams
o affic ligh s. I de ails he solu ion encoding,
he fi ness unc ion, and finally he global op i-
miza ion p ocedu e.
4.1. Solu ion Encoding
In ou app oach, he op imal TP is encoded by
means o a ec o o in ege s (see Figu e 1) ollow-
ing he SUMO s uc u e o p og amming cycles
( iming), whe e each elemen ep esen s a phase
du a ion o one s a e o he signal ligh s in ol ed
in a gi en in e sec ion.
In spi e o i s simplici y, his solu ion ep esen-
a ion allows ou PSO o ake in o accoun he de-
pendency o a iables (epis asis), no only be ween
phase du a ions o a s a e o affic ligh s in an in-
e sec ion, bu also be ween affic ligh s in adja-
cen ones.
4.2. Fi ness Func ion
In o de o e alua e each iming p og am solu-
ion (s) gene a ed by ou PSO, he ollowing fi ness
unc ion is minimized, which conside s he in o -
ma ion ob ained om he e en s happening du ing
he affic flow analyzed:
5

F p(s) = (CO+NOx+F u)(s)+ω·(G (s)+(C(s)×S )
V2(s) + P)
(1)
The main objec i e is o maximize he numbe
o ehicles ha each hei des ina ions (V) and
minimize bo h, emission le els (CO and NOx) and
uel consump ion (Fu), du ing he simula ion ime
(S ). The global ip ime o all he ehicles (G )
has o be also minimized. The numbe o ehicles
ha a i e o hei des ina ions is squa ed (V2(s))
in o de o p io i ize i o e he o he e ms and
ac o s. Ob iously, he numbe o ehicles ha do
no each hei des ina ions and emain ci cula -
ing C(s) a e he simula ion has o be minimized.
The global ip ime conce ns an agg ega ion o he
ip ime o ehicles ha each hei des ina ions
du ing he simula ion p ocess. On he con a y, e-
hicles wi h uncomple ed a els C(s) consume all
he simula ion ime S and hen, an addi ional pe-
naliza ion is induced by mul iplying hese wo ac-
o s. I is wo h men ioning ha e ms in Equa-
ion 1 a e in he ange o alues [1e+ 0 · · · 5e+ 2]
and he e o e, addi ional weigh ing alues we e no
conside ed in his o mula ion. Only he alue ω
which is se o 0.5 is conside ed in o de o en-
hancing en i onmen al e ms in he o e all fi ness
compu a ion.
Finally, he balanced p opo ion o colo s in he
phase du a ion o he s a es should p omo e hose
s a es wi h mo e affic ligh s in g een loca ed in
s ee s wi h a high numbe o ehicles ci cula ing,
and affic ligh s in ed loca ed in s ee s wi h a
low numbe o ehicles mo ing. The p opo ion o
colo s in each phase (ph) o all he l in e sec ions
can be o mula ed as ollows:
P=
l
∑
k=0
ph
∑
j=0
sk,j ·(Gk,j
k,j ),(2)
whe e Gk,j is he numbe o affic ligh s in
g een, and k,j is numbe o affic ligh s in ed in
he phase s a e j(wi h du a ion sk,j) and in he
in e sec ion k. The minimum alue o edk,j is 1
in o de o a oid di ision by 0.
4.3. Op imizing Timing P og ams wi h PSO
The op imiza ion s a egy is composed by wo
main pa s: he Pa icle Swa m Op imize (PSO),
and he simula ion p ocedu e wi h he SUMO a -
fic mic osimula o .
The PSO algo i hm [16] is a popula ion-based
me aheu is ic inspi ed by he social beha io o
bi ds wi hin a flock, and was ini ially designed o
con inuous op imiza ion p oblems. In PSO, each
po en ial solu ion o he p oblem is called pa icle
posi ion and he popula ion o pa icles is called
he swa m. We ha e ollowed he specifica ion o
he S anda d PSO 2011 [10]. In his algo i hm,
each pa icle posi ion xiis upda ed each i e a ion
gby means o he Equa ion 3.
xi
g+1 =xi
g+ i
g+1 (3)
whe e e m i
g+1 is he eloci y o he pa icle,
gi en by he Equa ion 4.
i
g+1 =w· i
g+G i
g−xi
g+HS(G , ∥G −xg∥) (4)
wi h
G i
g=xi
g+p′i
g+l′i
g
3(5)
and
p′i
g=xi
g+c·(pi
g−xi
g) (6)
l′i
g=xi
g+c·(li
g−xi
g) (7)
In his o mula, pi
gis he bes solu ion ha he
pa icle ihas seen so a , li
gis he bes pa icle o
a neighbo hood o ko he pa icles (also known as
he social bes ) andomly (uni o m) selec ed om
he swa m, and wis he ine ia weigh o he pa -
icle (i con ols he ade-off be ween explo a ion
and exploi a ion). The accele a ion coefficien c >
1 is a no mal (Gaussian) andom alue wi h µ=
1/2 and ρ= 1/12. This coefficien is sampled anew
o each componen o he eloci y ec o . Finally,
HS is a dis inc i e elemen o he S anda d PSO
2011 wi h ega ds o he p e ious ones. I is basi-
cally a andom numbe gene a o wi hin a Hype -
sphe e space, wi h G as cen e o g a i y. Tha is,
G is calcula ed as he equidis an poin o p′
g,l′
g,
and xg. This is a new o a ion in a iance mecha-
nism p o ided by he S anda d PSO 2011 o (pos-
6
sibly) a oid he in insic coo dina e dependence
showed by all p e ious e sions o PSO [10].
Since he op imal SLTP equi es solu ions en-
coded wi h a ec o o in ege s ( ep esen ing
phase du a ions), we ha e used he quan isa ion
me hod p o ided in he s anda d specifica ion o
PSO 2011 [10]. This quan isa ion is applied o
each new gene a ed pa icle (in Equa ion 3), and
ans o ms he con inuous alues o pa icles o
disc e e ones. I consis s o a Mid-Th ead uni o m
quan ise me hod as specified in Equa ion 8. The
quan um s ep is se he e o ∆ = 1.
Q(x)=∆· ⌊x/∆+0.5⌋(8)
Algo i hm 1 S anda d PSO 2011 o he SLTP
1: ini ializeSwa m()
2: while g < maxI e a ions do
3: o each pa icle xi
gdo
4: bn
g=bes Neighbou Selec ion(xi
g, n)
5: i
g+1=upda eVeloci y(w, i
g, xg, φ1, pg, φ2, bn
g)
6: xi
g+1=Q(upda ePosi ion(xi
g, i
g+1))
7: e alua e(xi
g+1) //SUMO Simula ion and Eq. 1
8: pi
g+1=upda e(pi
g)
9: end o
10: end while
Algo i hm 1 desc ibes he pseudo-code o he
S anda d PSO 2011 o he op imal SLTP. The al-
go i hm s a s by ini ializing he swa m (Line 1).
The co esponding elemen s o each pa icle (solu-
ions) a e ini ialized wi h andom alues ep esen -
ing he phase du a ions. These alues a e wi hin
he ime in e al [5,60] ∈Z+, and cons i u e he
ange o possible ime spans (in seconds) a affic
ligh can kep a signal colo (only g een o ed, he
ime o yellow is a cons an alue se in sumo o
5 seconds). Then, o a maximum numbe o i e -
a ions, each pa icle flies h ough he sea ch space
upda ing i s eloci y and posi ion (Lines 4, 5, and
6), i is hen e alua ed (Line 7), and i s pe sonal
bes posi ion piis also upda ed (Line 8). Finally,
he bes pa icle ound so a is e u ned.
The simula ion p ocedu e is hen used o as-
signing a quan i a i e quali y alue (fi ness) o he
solu ions, hus leading o op imized iming p o-
g ams ailo ed o a gi en u ban scena io ins ance.
This ask is ackled by he SUMO mic oscopic a -
fic simula o , which accep s new iming p og ams
o affic ligh s and compu e he equi ed alues in
Equa ion 1.
When ou PSO gene a es a new solu ion, i
is used o upda ing he iming p og am. Then,
SUMO is s a ed o simula e he ins ance wi h
s ee s, di ec ions, obs acles, affic ligh s, ehi-
cles, speed, ou es, e c., unde he new defined
schedule o iming p og ams. A e he simula ion,
SUMO e u ns he global in o ma ion necessa y
o compu e he fi ness unc ion. Each solu ion
e alua ion (Line 7 a Algo i hm 1) equi es a sim-
ula ion p ocedu e since ehicle ou es in SUMO
a e gene a ed de e minis ically. Each new iming
p og am is hen loaded o each simula ion p oce-
du e. In his sense, wha eal affic ligh human
schedule s ac ually demand a e cons an iming
p og ams o specific a eas and o p ees ablished
ime pe iods ( ush hou s, noc u ne pe iods, e c.),
which led us o ake his ocus.
5. Expe imen s and Resul s
In his sec ion we p esen he expe imen al
amewo k ollowed o assess he pe o mance o
ou PSO algo i hm o c ea ing op imized TPs.
Fi s , we desc ibe he scena io ins ances, he im-
plemen a ion de ails o ou app oach, and he pa-
ame e se ings. La e , esul s and compa isons
o o he echniques a e p esen ed. A s udy o he
esul ing iming p og ams is also ca ied ou in
o de o show he ac ual benefi s o using ou p o-
posal and hei impac in o he li ing en i onmen
o u ban a eas.
5.1. U ban Scena io Ins ances
As we a e in e es ed in de eloping an op imiza-
ion sol e capable o dealing wi h close- o- eali y
gene ic u ban a eas, we ha e gene a ed wo sce-
na ios by ex ac ing ac ual in o ma ion om eal
digi al maps. These wo scena ios co e simila a -
eas o app oxima ely 0.75 km2, and hey a e phys-
ically loca ed in he ci ies o Malaga and Se ille,
in Spain. The in o ma ion used conce ns: affic
ules, affic elemen loca ions, buildings, oad di-
ec ions, s ee s, in e sec ions, e c. Mo eo e , we
7
Figu e 2. P ocess o c ea ion o eal-wo ld ins ances o s udy. U ban cen e o Malaga (36◦43’01”N 4◦25’58”O) and Se ille
(37◦38’14”S 5◦97’23”O) ins ance iews. A e selec ing he a ea o in e es (Google Ea h iew), i is in e p e ed by means
o he OpenS ee Map ool, and hen expo ed o SUMO o ma
ha e se he numbe o ehicles ci cula ing, as well
as hei speeds by ollowing cu en specifica ions
a ailable in he Mobili y Delega ion o he Ci y
Hall o Malaga (h p://mo ilidad.malaga.eu/).
This in o ma ion was collec ed om senso ized
poin s in ce ain s ee s ob aining a measu e o
affic densi y in se e al ime in e als. In he case
o Se ille we consul ed he Mobili y Delega ion o
Se ille Council (h p://www. ajano.com/).
In Figu e 2, he selec ed a eas o he wo ci ies
a e shown wi h hei co esponding snapsho s o
Google Ea h, OpenS ee Map, and SUMO. This
figu e illus a es he p ocess o gene a ing he a -
fic ne wo k ins ances. The specific ea u es o hese
a eas a e as ollows:
(i) Malaga. In he zone be ween he ci y cen-
e and he ha bo . This second scena io
(Figu e 2, op) is composed by s ee s wi h
diffe en wid hs and leng hs, and se e al
oundabou s. I con ains junc ions including
om 4 o 16 affic ligh s each one. The main
a enues ound in his a ea a e: Andaluc´ıa,
Am´e icas and Au o a a enues, Hile a, and
Lehmbe g Ruiz s ee s.
(ii) Se ille. Loca ed in he popula dis ic o
Ne i´on in he ci y cen e o Se ille (Figu e
2, bo om), i is made up o in e sec ions
be ween s ee s including each one om 4 o
17 affic ligh s. The comple e a ea shows a
ep esen a i e o ganiza ion wi h almos all
he junc ions connec ing be ween h ee and
ou s ee s. The main a enues c ossing his
neighbo hood a e: Men´endez Pelayo, Ed-
ua do Da o, San F ancisco Ja ie , Mon o o,
Gal ´an, and Buha ´ıa.
We ha e chosen hese wo scena ios since hey
cons i u e diffe en me opoli an a eas wi h he -
e ogeneous s uc u es and affic o ganiza ions.
The numbe o s udied in e sec ions is 70 o he
wo ins ances, wi h 250 ci cula ing (PC and LDV
ypes) ehicles h ough each one o hem. We ha e
o no ice ha in spi e o ha ing in bo h ins ances
a simila numbe o in e sec ions (70), he num-
be o signal ligh s is no exac ly he same, since
hey con ain diffe en in e sec ion shapes (304
affic ligh s in Malaga and 368 ones in he case o
Se ille).
In he s udy, each ehicle pe o ms i s own ou e
om i s own o igin o des ina ion ci cula ing wi h
a maximum speed o 50 km/h ( ypical in u ban a -
eas). The ou es we e p e iously gene a ed by ol-
lowing andom pa hs. The simula ion ime was se
8
Table 1
SUMO and PSO pa ame e s
Sol e Phase Pa ame e Value
Simula ion Time (s eps) 500 s
A ea 0.75 km2
SUMO De ails Numbe o Vehicles 250
Vehicle Speed 0-50 km/h
Vehicles Types PC/LDV
N. o S udied In e sec ions 70
Max. N. o E alua ions 9,000
Swa m Size 30
Pa icle Size (N. T affic Ligh s) 368
304
PSO Pa ame e s Local Coefficien (φ1) 2.0
Social Coefficien (φ2) 2.0
Maximum Ine ia (wmax ) 0.5
Minimum Ine ia (wmin ) 0.1
Veloci y T unca ion Fac o (λ) 0.5
o 500 seconds (i e a ions o mic osimula ion) o
each ins ance. This ime was de e mined as a max-
imum ime o a ca o comple e i s ou e, e en i
i mus s op in all he affic ligh s along i s way.
Vehicles a e loca ed in hei own o igins and hey
mo e om he ini ial simula ion s eps. When a e-
hicle lea es he scena io ne wo k, i eaches i s des-
ina ion and i will no appea again.
5.2. Expe imen al Se up
We ha e used he implemen a ion in C++ o
he PSO algo i hm p o ided by he MALLBA [1]
amewo k. The simula ion phase is ca ied ou by
execu ing ( o he e alua ion o pa icles) he a -
fic simula o SUMO elease 0.12.0 o Linux. The
expe imen s we e pe o med in he compu ing a-
cili ies o he Depa men o Compu e Science o
he Uni e si y o Malaga (Spain). Mos o hem a e
equipped wi h mode n dual co e p ocesso s, 1GB
RAM, and Linux Debian O.S. They ope a e unde
a Condo [30] middlewa e pla o m ha ac s as a
dis ibu ed ask schedule (each ask dealing wi h
one independen un o PSO).
Fo each scena io ins ance we ha e ca ied ou 30
independen uns o ou PSO. The swa m size was
se o 30 pa icles pe o ming 300 i e a ion s eps,
hence esul ing a numbe o 9,000 solu ion e alu-
a ions (SUMO simula ions) pe un and ins ance.
As p e iously men ioned, he pa icle size di ec ly
depends on he numbe o affic ligh s o each in-
Algo i hm 2 Pseudocode o RANDOM
1: gene a e(x) //ini ial solu ion
2: i←0
3: while i < Max Numbe o E alua ions do
4: gene a e(xi) //new solu ion
5: i (x)≥ (xi) hen
6: x←xi
7: end i
8: i←i+ 1
9: end while
s ance. The emaining pa ame e s a e summa ized
in Table 1. These pa ame e s we e se a e p elim-
ina y execu ions. Specific pa ame e s o PSO we e
selec ed as ecommended in he s udy abou he
con e gence o his algo i hm in [8].
Addi ionally, we ha e implemen ed a Ran-
dom Sea ch algo i hm, also in he scope o he
MALLBA lib a y, wi h he aim o es ablishing
compa isons agains ou PSO. Thus, by pe o m-
ing he same expe imen a ion p ocedu e wi h PSO
and Random Sea ch algo i hm we expec o ob ain
some insigh s in o he powe o ou p oposal (how
much in elligen i is). The pseudocode o he Ran-
dom Sea ch algo i hm (RANDOM om now on)
is shown in Algo i hm 2. The maximum numbe
o e alua ions was se o 9,000, as o PSO.
SUMO p o ides a de e minis ic algo i hm o
gene a ing cycle p og ams (SCPG). Then we also
compa e he cycle p og ams ob ained by ou PSO
agains he ones ob ained by SUMO. This las al-
go i hm basically consis s in assigning o he phase
du a ions o he affic logics esh alues in he
ange o [6,31], acco ding o h ee diffe en ac o s:
(i) he p opo ion o g een s a es in he phases,
(ii) he numbe o incoming lanes o he in e sec-
ion, and
(iii) he b aking ime o he ehicles app oaching
o hei affic ligh s.
Fu he in o ma ion abou his algo i hm can be
ound in [4].
5.3. E ol abili y o PSO on he SLTP Landscape
P e ious o he pe o mance expe imen a ion,
we ha e ca ied ou a Fi ness-Cloud analysis [31]
wi h he aim o e i ying whe he ou op imiza ion
s a egy wi h PSO is able o success ully ackle he
signal ligh iming p oblem o no , o he scena io
9
[19] J. Leung, L. Kelly, and J. H. Ande son. Handbook
o Scheduling: Algo i hms, Models, and Pe o mance
Analysis. CRC P ess, Inc., Boca Ra on, FL, USA,
2004.
[20] X. Li, G. Li, S. Pang, X. Yang, and J. Tian. Signal
iming o in e sec ions using in eg a ed op imiza ion
o affic quali y, emissions and uel consump ion: a
no e. T anspo a ion Resea ch Pa D: T anspo and
En i onmen , 9(5):401 – 407, 2004.
[21] G. Lim, J. Jin Kang, and Y. Hong. The op imiza ion
o affic signal ligh using a ificial in elligence. In
FUZZ-IEEE, pages 1279–1282, 2001.
[22] J. McC ea and S. Mou a i. A hyb id mac oscopic-
based model o affic flow in oad ne wo ks. Eu opean
Jou nal o Ope a ional Resea ch, In P ess, Co ec ed
P oo :–, 2010.
[23] J. S´anchez Medina, M. Gal´an Mo eno, and E. Rubio
Royo. Applying a affic ligh s e olu iona y
op imiza ion echnique o a eal case: “Las Ramblas”
a ea in San a C uz de Tene i e. E olu iona y
Compu a ion, IEEE T ansac ions on, 12(1):25 –40,
eb. 2008.
[24] T. Naga ani. Effec o speed fluc ua ion on g een-
ligh pa h in 2d affic ne wo k con olled by signals.
Physica A: S a is ical Mechanics and i s Applica ions,
In P ess, Accep ed Manusc ip :–, 2010.
[25] L. Peng, M. Wang, J. Du, and G. Luo. Isola ion niches
pa icle swa m op imiza ion applied o affic ligh s
con olling. In 48 h IEEE Con e ence on Decision and
Con ol and 28 h Chinese Con ol Con e ence, pages
3318 –3322, dec. 2009.
[26] N. M. Rouphail, B. B. Pa k, and J. Sacks. Di ec
signal iming op imiza ion: S a egy de elopmen and
esul s. Technical epo , In XI Pan Ame ican
Con e ence in T affic and T anspo a ion Enginee ing,
2000.
[27] D. J. Sheskin. Handbook o Pa ame ic and
Nonpa ame ic S a is ical P ocedu es. Chapman &
Hall/CRC, 2007.
[28] J. C. Spall and D. C. Chin. T affic- esponsi e signal
iming o sys em-wide affic con ol. T anspo a ion
Resea ch Pa C: Eme ging Technology, 5(3-4):153 –
163, 1997.
[29] F. Teklu, A. Sumalee, and D. Wa ling. A gene ic
algo i hm app oach o op imizing affic con ol
signals conside ing ou ing. Compu e -Aided Ci il and
In as uc u e Enginee ing, 22:31–43, 2007.
[30] D. Thain, T. Tannenbaum, and M. Li ny. Dis ibu ed
compu ing in p ac ice: he condo expe ience.
Concu ency - P ac ice and Expe ience, 17(2-4):323–
356, 2005.
[31] L. Vanneschi, M. Cle gue, P. Colla d, M. Tomassini,
and S. V el. Fi ness clouds and p oblem ha dness in
gene ic p og amming., 2004.
[32] S. Zhou, X. Yan, and C. Wu. Op imiza ion model
o affic signal con ol wi h en i onmen al objec i es.
In P oceedings o he 2008 Fou h In e na ional
Con e ence on Na u al Compu a ion - Volume 06,
pages 530–534, Washing on, DC, USA, 2008. IEEE
Compu e Socie y.
[33] P. Zi o. Influence o coo dina ed affic ligh s
pa ame e s on oadside pollu an concen a ions.
T anspo a ion Resea ch Pa D: T anspo and
En i onmen , 14(8):604 – 609, 2009.
16