202
6 h In e na ional Con e ence on Indus ial Enginee ing and Indus ial Managemen .
XVI Cong eso de Ingenie ía de O ganización. Vigo, July 18-20, 2012
Op imiza ion o ecyclable was e collec ion
using eal- ime in o ma ion.
G osso de la Vega R
1
, Muñuzu i Sanz J
2
, Rod íguez Pale o M
3
, Teba
Fe nandez J
4
Abs ac This pape add esses he ecyclable was e collec ion p oblem in u ban
a eas. The wo k ocuses on he ecyclable glass bins collec ion, bu wi h he pecu-
lia i y ha hese a e p o ided wi h a de ice ha sends ill le el da a daily o he
con ol cen e . Wi h his addi ional eal ime in o ma ion we p opose a collec ion
policy ha minimizes he leng h o he ou es o ehicles on wo le els, one daily
and o he o a la ge planning ho izon. This p oposed policy is compa ed o he
one used in he cu en li e a u e and only op imizes he daily ou es. Se e al sim-
ula ions o he wo policies a e pe o med on a model o he ci y o Se ille. Re-
sul s show he p oposed policy achie es be e esul s in e ms o mee ing demand
and be e u iliza ion o esou ces.
Keywo ds: was e collec ion, ehicle ou ing, eal ime da a, op imiza ion
1
Ra ael G osso de la Vega ()
Depa amen o de O ganización Indus ial y Ges ión de Emp esas II. Escuela Tecnica Supe io de
Ingenie ia de Se illa, Camino de los Descub imien os, s/n. Isla de la Ca uja, 41092, Se ille,
Spain
e-mail: g [email protected]
2
Jesus Muñuzu i Sanz
Depa amen o de O ganización Indus ial y Ges ión de Emp esas II. Escuela Tecnica Supe io de
Ingenie ia de Se illa, Camino de los Descub imien os, s/n. Isla de la Ca uja, 41092, Se ille,
Spain
e-mail: munuzu [email protected]
3
Ma ia Rod íguez Pale o
Depa amen o de O ganización Indus ial y Ges ión de Emp esas II. Escuela Tecnica Supe io de
Ingenie ia de Se illa, Camino de los Descub imien os, s/n. Isla de la Ca uja, 41092, Se ille,
Spain
e-mail: ma ia od [email protected]
4
José Teba Fe nandez
Depa amen o de O ganización Indus ial y Ges ión de Emp esas II. Escuela Tecnica Supe io de
Ingenie ia de Se illa, Camino de los Descub imien os, s/n. Isla de la Ca uja, 41092, Se ille,
Spain
e-mail: j [email protected]
203
1. In oduc ion
T ying o sol e he p oblem o was e collec ion in ci ies is no a new p oblem. Al-
eady in he 70 au ho s can be ound a emp ing o add ess he p oblem, ei he
om a ma hema ical poin o iew (Ma ks & Liebman, 1970), ei he modeling and
sol ing a ehicle ou ing p oblem o VRP (Bel ami & Bodin, 1974; Tu ne &
Hougland, 1975). This p oblem is no easy o sol e because i is included wi hin
he amily o p oblems called Vehicle Rou ing P oblem (VRP), as e e known,
hey all all unde he classi ica ion o NP-ha d.
The inc eased le els o consump ion and associa ed was e gene a ion, en i-
onmen al conside a ions and sus ainabili y o ci ies ha e led o he eme gence o
new Eu opean and na ional policies ega ding he managemen o municipal
was e. An example is he Na ional In eg a ed Was e Plan implemen ed in Spain in
2009, which is o con inue he an e io Na ional U ban Was e Plan (PNRU), and,
among o he hings, o ces municipali ies wi h mo e han 5000 inhabi an s o en-
su e p ope sepa a ion o selec i e collec ion o was e. Such measu es make o
conside new challenges o municipali ies, e en mo e so in he economic ecession
amewo k in which we li e. Di e en ypes o con aine s, di e en ypes o
was e, con aine s loca ion, pollu ion, ene gy consump ion, cos educ ion, a e any
o hese challenges. Thus au ho s ha add ess he p oblem om he consump ion
o uel (Sonesson, 2000), un il which encompass en i onmen al and economic
goals can be ound in he li e a u e.
Nowadays wi h he eme gence o new echnologies and he lowe ing o i s
p ice gi e esea che s new ools o sol e his p oblem. Examples o hese new
echnologies a e Geog aphic in o ma ion sys em (GIS), olume ic senso s, adio
equency iden i ica ion (RFID). Using his echnology he issues can be ad-
d essed as elimina ing unnecessa y s ops, lee educ ion and balancing acco ding
o demand, pollu ion impac educ ion, ope a ing cos s educ ion, e c. In his di ec-
ion i wo ks in ecen yea s (Chang e al., 1997; Nuo io e al., 2006), and in
which he e is g ea po en ial o u u e wo k.
And i is in his di ec ion ha his wo k mo es. In his pape we add ess he
p oblem o was e disposal in u ban a eas wi h he eal- ime le el da a o he con-
aine s. In pa icula we ocus on he collec ion o glass con aine s. We desc ibe in
his wo k he p oblem o sol e; we p esen he p oposed collec policy, and com-
pa ed wi h o he classical op imiza ion algo i hm. Finally, we show he esul s ob-
ained and p esen he conclusions o he wo k.
2. P oblem desc ip ion
We conside a capaci a ed ehicle ou ing p oblem on a g aph: ܩǣሾܰǡܣሿ], whe e N
is he se o nodes and L is he se o links communica ing hem. The se o nodes
204
N con ains one node ݀ wi h a posi i e le el o demand (depo ), a subse ܥ o
nodes wi h a posi i e le el o supply (con aine s), and ano he subse ܥҧo nodes
wi h ze o le els o supply and demand, so ha ܰൌሺܥ׫ܥ
ഥሻ׫݀.The supply le -
el o con aine s in subse ܥ is ime a ian , and is known daily.
A numbe ܸ o ehicles (whe e ܸ is a a iable) will a el h ough he g aph
isi ing he di e en con aine s, only one ehicle pe con aine . We conside ca-
paci y es ic ions on ehicles ሺܳሻ equal o all o hem.
The p oblem is de ined inside a p ede ined ime ho izon, ܰ days, and he ob-
jec i e is o minimize he numbe o ehicles ha need o be used and he cos (in
ime uni s) o anspo ing was e om he con aine s o ܥ o he depo ݀, c ossing
along he way he necessa y nodes o he subse ܥҧ.
We also de ine a se ܶ o ime cos s associa ed o he di e en links in he
g aph. These cos s depend only on he ansi o ehicles h ough links, and no on
he amoun o was e ca ied by hose ehicles. In gene al, we will incu in cos
ݐ௜௝when a elling om node ݅ o node ݆. We will also compu e he loading ime
a each cus ome as a ime cos ݐݎ, incu ed e e y ime a ehicle isi s one o he
nodes con ained in ܥ.
3. P oposed Solu ion
We p opose a collec ion policy based on h ee s ages: calcula ion, es ima ion
and op imiza ion. P e iously we ixed he ill le el ሺܴܮሻ o con aine s which a e
o collec .
In he i s s age, we calcula e he ou es needed o minimize he a el leng h
a e knowing he con aine s o collec in a day ݐ wi h he olume ic senso da a
and he ixed RL. In he nex s age, we es ima e he con aine s o be collec ed o e
he nex ܰ daysሺ൅ͳǡǥǡ൅ሻ. We use i s cu en ill le el and i s daily ill
a e. The necessa y ou es a e also calcula ed o hose ܰ days. In he las s age
and seeking o educe he numbe o kilome e s a eled in he planning ho izon,
we look o he possible con aine s, om hose ܰ days, which can be collec ed on
day ݐ. Ob iously he ill le els ha ha e hese con aine s in he day ݐ is lowe han
he alue ܴܮ ixed by he policy, so he p oposed decision ule akes in o accoun
ha no exploi ed con aine capaci y.
This policy is compa ed wi h ano he used in he li e a u e (Nuo io e al.,
2006; Johansson, 2006; Faccio e al., 2011), which simply collec s he con aine s
wi h he ixed ill le el.
Below cla i ies he nomencla u e used in he desc ip ion o he implemen ed
algo i hm o simula ing policies.
•ܮሺݎሻ deno es he leng h o ou e ݎ, in ime uni s.
205
•The used ope a o s a e known (B äysy & Gend eau, 2005). These a e: Inse ion
Ope a o , Local Sea ch Ope a o , 2-Op , OR-Op , 3-Op , Exchange, Reloca e,
2-op *, CROSS-Exchange and GENI-Exchange.
•Pa ame e ha we use as decision ule o de e mine which con aine s wi h ill
le els lowe han ܴܮ a e collec ed a day ݐ is de ined as ollows:
ܲሺ݅ሻൌ൫ͳെ݈݈ܰሺ݅ሻ൯ήݐݎή݇ (1)
–Being ܰܮܮሺ݅ሻ he ill le el o each con aine a he cu en momen , and ݇
a pa ame e as a weigh o no exploi ed con aine capaci y in he decision
ule. The simula ion uses di e en alues o ݇ in sea ch o i s op imal al-
ue.
Below we p esen he pseudo-code o he algo i hm used by he p oposed poli-
cy. This algo i hm calcula es he ou es needed o a pa icula day, bu as dis-
cussed abo e, i will be simula ed con inuously o h ee mon hs in o de o com-
pa e he o e all esul s.
Calcula e con aine s o collec day ݐ ( eal- ime da a)
o ݀ͳ ൌ ͳǣܰ Es ima e con aine o collec in day ݐ൅݀ͳ (his o ic da a)
end
o ݀ʹ ൌ ͳǣܰ ൅ ͳ Build collec ion ou es (Ope a o s al eady men ion)
end
o ݀͵ ൌ ͳǣܰ o each day since ݐ൅ͳ o ݐ൅͹ and conside ing he capaci y
cons ains
o each con aine ݆ in each ou e ݎ a day ݐ
o each con aine ݅ in each ou e ݏ a day ݐ൅݀͵
i ܮሺݎݓ݅ݐ݄݅ܾ݁ݐݓ݁݁݊݆ܽ݊݀݆൅ͳሻ൅ܲሺ݅ሻ൅ܮሺݏݓ݅ݐ݄݋ݑݐ݅ሻ ൏
ܮሺݎሻ൅ܮሺݏሻ
Sa e con aine ݅in con aine s o collec in day ݐ
end
end
end
end
o build day ݐ ou es wi h he new con aine s
while he leng h o ou es imp o es
end
end
The algo i hm o simula e he policy o compa e:
Calcula e con aine s o collec day ݐ ( eal- ime da a)
o build day ݐ ou es (Ope a o s al eady men ion)
while he leng h o ou es imp o es
end
end
206
4. Case s udy
We conside he p oblem o collec ing ecyclable was e con aine s in he ci y o
Se ille, in pa icula glass con aine s. These con aine s a e loca ed h oughou he
ci y so dispe sed. These con aine s is no necessa y o collec daily because o
non-deg adable na u e o he glass, he a e o gene a ion o his ype o was e
which is no e y high and he capaci y o he con aine s ( in he case o Se ille is
3 m
3
).
Cu en ly i used a policy ha combines on he one hand he collec ion o con-
aine s acco ding o es ima es o his o ic illing a es and on he o he he con ain-
e s collec ed a e ecei ing a call om a neighbo ale ing he comple e illing o
any o hem.
The implemen a ion o au oma ed senso s ha emi a signal o he was e man-
agemen cen e wi h he ill le el da a in he con aine s o his ype o was e is a
end seen in ecen imes (Nuo io e al., 2006; Johansson, 2006; Faccio e al.,
2011).
And assuming ha such senso s ha e been implemen ed in he ci y o s udy he
p oblem o sol e is:
•A model o Se ille consis ing o a g aph: ܩǣሾܰǡܣሿ], wi h ܰൌͳʹͳ͹ nodes and
ܰൌͶͷͳͲ a cs. The cos associa ed wi h each a c is in ݐ
௜௝
kilome e s.
•I assumes he exis ence o a su icien lee o se ice. The capaci y o he
uck was ixed in e ms o numbe o ull con aine s ha can con ain. Each e-
hicle can collec ܳൌ͹ ull con aine s. Associa ed wi h ehicles is also ixed in
ݐݎ ൌ ʹǤͷ minu es he ime equi ed o collec each con aine ( he mechanical
collec ion o glass con aine s in Se ille equi es a c ane). The es ima ed a e -
age speed o ehicles was ixed a ʹͲȀ.
•A single depo ሺ݀ሻ om which he ehicles begin and end collec ion ou es is
conside ed.
•Dis ibu ed by he g aph a e loca ed con aine s (subse ܥ) o be collec ed. The
numbe o con aine s was ixed a 300. I is conside ed ha each con aine has
a olume ic senso ha p o ides daily he ill le el o each o hem. In addi ion
o i s exac loca ion, wo da a ha e associa ed o each con aine ; one is he cu -
en illing le el (%) and he o he a daily illing a e (%), di e en o each.
This a e is assumed o ollow a no mal dis ibu ion (Johansson, 2006), wi h an
a e age alue 0.1428, he s anda d de ia ion alue is a pa ame e in he expe -
imen s (0.5 o 1).
•The p oblem is o sol e o a planning ho izon o ൌ͸ day, al hough he p o-
posed policy aims o minimize he numbe o kilome e s wi hin a ime o h ee
mon hs, so he e will be a olling-ho izon p ocedu e o ha ime.

207
4.1 Resul s
A e hese we p esen and analyze he esul s o he implemen a ion o wo poli-
cies o he p oblem.
Se e al expe imen s on he model o Se ille om he wo policies we e con-
duc ed o compa e.
As pa ame e s o s udy he sensi i i y on he esul s we used he s anda d de ia-
ion ሺߪሻ o he con aine s daily a e o illing and he ixed ܴܮ in bo h cases. And
he alue o ݇ in p oposed policy. Fo a be e compa ison we added he alue o
݇ in he cos unc ion o bo h policies.
As se ice sa is ac ion index we used he demand me daily. Unme demand is
conside ed, and he e o e is no accoun ed o in he index, he es ima ed amoun
o glass a i ing o he con aine once i is ull. This amoun o was e is no col-
lec ed.
The cos unc ion used is:
ܥܶ ൌ ቀ ௄௜௟௢௠௘௧௘௥௦
஺௩௘௥௔௚௘௦௣௘௘ௗቁ൅ܰݑܾ݉݁ݎ݋݂ܿ݋݈݈݁ܿݐ݁݀ܿ݋݊ݐܽ݅݊݁ݎݏήݐݎή݇ (2)
Table 1 P oposed policy esul s
ı RL Km Nº R Nº RT NllMV (%) DS (%) k CT
0.5 0.95 19611 548 3759 91.7% 94.7% 0.5 63532
0.5 0.95 19337 547 3657 91.6% 94.9% 1 67154
0.5 0.95 19222 542 3568 92.5% 94.5% 3 84426
1 0.95 22935 655 4478 93.2% 91.6% 0.5 74401
1 0.95 22647 651 4409 93.6% 91.5% 1 78965
1 0.95 22629 646 4310 94.1% 91.4% 3 100213
0.5 1 22293 586 4664 91.3% 99.3% 0.5 72710
0.5 1 22133 592 4503 90.1% 98.6% 1 77656
0.5 1 21608 581 4331 91.3% 98.3% 3 97308
1 1 27309 728 5880 91.6% 98.5% 0.5 89276
1 1 26842 725 5752 91.6% 98.3% 1 94907
1 1 26699 725 5640 91.4% 97.9% 3 122396
ı Ł S anda d de ia ion, RL Ł ixed ill le el, Km Ł To al dis ance a eled in kilome e s, Nº R Ł
numbe o ou es, Nº RT Ł numbe o collec ed con aine s, NllMV Ł ehicles ill le el, DS Ł
me demand, CT Ł o al cos (depending on he alue o k in able 2)
•Table 1 show ha he p oposed policy is be e sui ed o he di e en scena ios
wi h ݇ ൌ ͲǤͷ, because ge s he bes pe cen ages o me demand wi h lowe
cos s.
208
•I is also no ewo hy ha he p oposed policy is be e sui ed o la ge alues o
ı wi h he ܴܮ ൌ ͳ, because ge s pe cen ages o me demand e y high, al -
hough wi h highe cos s.
•The p oposed policy is in gene al mo e expensi e, al hough in small pe cen -
ages, han he o he policy, bu also ge s a signi ican ly highe pe cen age o
me demand, so mo e ga bage is collec ed.
•E en wi h he abo e, he dis ance a eled in p oposed policy ou es is no sig-
ni ican ly g ea e han he o he . So in en i onmen al and economic conside a-
ions would be conside ed mo e balanced.
•Unde he p oposed policy ge s be e esou ce use and mo e op imized, be-
cause collec ed g ea e numbe o con aine s wi h less numbe o ou es, so ha
he a e age ill le el o he ehicle is highe . This may lead o a educ ion in
he lee o ehicles needed.
Tabla 2 Resul s om expe imen s on he model o compa e policy
ı RL Km Nº R Nº RT NllMV (%) DS (%) CT k=0.5 CT k=1 CT k=3
0.5 0.94 19565 552 3582 91.53% 95.05% 63174 67651 85561
1 0.94 22762 656 4318 93.10% 91.97% 73685 79082 100672
0.5 0.96 20054 583 3694 89.94% 98.98% 64778 69396 87866
1 0.96 22351 651 4226 92.37% 90.62% 72336 77619 98749
0.5 0.98 18907 541 3424 89.95% 92.17% 61000 65280 82400
1 0.98 21971 660 4146 89.68% 89.22% 71095 76277 97007
0.5 1 18702 605 3397 80.08% 91.03% 60352 64598 81583
1 1 21975 720 4121 81.68% 87.96% 71076 76227 96832
5. Conclusions
We ha e buil a ou e op imiza ion p ocedu e o ecyclable was e collec ion using
eal- ime in o ma ion abou he con aine s ill le el.
In o de o do i we p opose a collec ion policy based on h ee s ages: calcula ion,
es ima ion and op imiza ion. In he i s s age, we calcula ed he ou es needed o
minimize he a el leng h a e knowing he con aine s o collec in a day ݐ wi h
he olume ic senso da a and he ixed ܴܮ. In he nex s age, we es ima ed he
con aine s o be collec ed o e he nex 6 days ሺݐ൅ͳǡǤǤǤǡݐ൅͸ሻ. We use i s cu -
en ill le el and i s daily ill a e. The necessa y ou es a e also calcula ed o
hose 6 days. In he las s age and seeking o educe he numbe o kilome e s
a eled in he 90 days, we look o he possible con aine s, om hose 6 days,
which can be collec ed on day ݐ. And we ecalcula ed he necessa y ou es wi h
he new con aine s. Thus he p oposed p ocedu e using eal da a op imizes ou es
on wo le els, daily and wi hin a la ge planning ho izon.
209
The p oposed policy has been compa ed o policies cu en ly used in he li e a-
u e which only akes in o accoun he daily op imiza ion.
Acco ding o he conclusions d awn, he policy wi h which we compa e could
be op imal om he poin o iew o he concessiona y company, because i has
lowe cos s, in gene al, wi h me demand ha could be conside ed wi hin he ac-
cep able le els.
And he policy p oposed in his pape could be adop ed by he municipali ies,
because while ha ing highe cos s i has highe le els o me demand and uses e-
sou ces mo e op imally, using ewe ehicles.
6. Bibliog a ía
Bel ami EJ, Bodin LD (1974) Ne wo ks and ehicle ou ing o municipal was e collec ion.
Ne wo ks, 4(1):65-94.
B äysy O, Gend eau M (2005) Vehicle ou ing p oblem wi h ime windows, Pa I: Rou e con-
s uc ion and local sea ch algo i hms, T ansp Sci, 39(1):104-118.
Chang N-, Lu HY, Wei YL (1997) GIS echnology o ehicle ou ing and scheduling in solid
was e collec ion sys ems, J.En i on.Eng., 123(9):901-910.
Faccio M, Pe sona A, Zanin G (2011) Was e collec ion mul i objec i e model wi h eal ime
aceabili y da a, Was e Manage., 31(12):2391-2405.
Johansson OM (2006) The e ec o dynamic scheduling and ou ing in a solid was e manage-
men sys em, Was e Manage., 26(8):875-885.
Ma ks DH, Liebman JC (1970) Ma hema ical analysis o solid was e collec ion, U S Public
Heal h Se Publ 2104 1970.
Nuo io T, Ky öjoki J, Niska H, B äysy O (2006) Imp o ed ou e planning and scheduling o
was e collec ion and anspo , Expe Sys Appl, 30(2):223-232.
Sonesson U (2000) Modelling o was e collec ion - A gene al app oach o calcula e uel con-
sump ion and ime, Was e Manage.Res., 18(2):115-123.
Tu ne WC, Hougland ES (1975) Op imal ou ing o solid was e collec ion ehicles. A I I E
T ansac ions, 7(4): 427-431.