Waste Management 31 (2011) 2391–2405

Contents lists available at ScienceDirect

Waste Management
journal homepage: www.elsevier.com/locate/wasman

Waste collection multi objective model with real time traceability data
Maurizio Faccio a,⇑, Alessandro Persona b, Giorgia Zanin b
a
Department of Innovation in Mechanics and Management, University of Padova, Via Venezia 1, 35131 Padova, Italy
b
Department of Management and Engineering, University of Padova, Stradella San Nicola 3, 36100 Vicenza, Italy

a r t i c l e i n f o a b s t r a c t

Article history: Waste collection is a highly visible municipal service that involves large expenditures and difficult
Received 24 December 2010 operational problems, plus it is expensive to operate in terms of investment costs (i.e. vehicles fleet),
Accepted 6 July 2011 operational costs (i.e. fuel, maintenances) and environmental costs (i.e. emissions, noise and traffic con-
Available online 6 August 2011
gestions). Modern traceability devices, like volumetric sensors, identification RFID (Radio Frequency
Identification) systems, GPRS (General Packet Radio Service) and GPS (Global Positioning System) tech-
Keywords: nology, permit to obtain data in real time, which is fundamental to implement an efficient and innovative
Waste collection
waste collection routing model.
Routing
Real time data
The basic idea is that knowing the real time data of each vehicle and the real time replenishment level
RFID at each bin makes it possible to decide, in function of the waste generation pattern, what bin should be
Traceability devices emptied and what should not, optimizing different aspects like the total covered distance, the necessary
number of vehicles and the environmental impact.
This paper describes a framework about the traceability technology available in the optimization of
solid waste collection, and introduces an innovative vehicle routing model integrated with the real time
traceability data, starting the application in an Italian city of about 100,000 inhabitants. The model is
tested and validated using simulation and an economical feasibility study is reported at the end of the
paper.
! 2011 Elsevier Ltd. All rights reserved.

1. Introduction lection operation, etc.), but in case of urban waste in cities with
high population density and high traffic congestion, the non-
In recent years, many municipalities, particularly in industrial- transportation time, which includes time spent for load–unload
ized nations, have been forced to assess their solid waste manage- operations and other idle times can reach 50% of the total time.
ment and examine its cost-effectiveness and environmental impact This consideration highlights the importance not only to optimize
in terms of designing collection routes, due to a number of con- the vehicle route, in order to reduce the transportation time, but
cerns such as cost, health and environment (Nuortio et al., 2006). also to reduce the number of load–unload stops.
The most common difficulties encountered in the management of The cost of collection of municipal solid waste is typically mea-
waste collection are the optimization of resources for an efficient sured in terms of cost per ton, with an inverse relationship be-
management system. tween the costs of collecting solid waste and the amount of
Specialty vehicles, with self-compactors, are usually designated materials collected, as a consequence moving bins that are only
to collect urban solid waste, with considerable operating expenses, partially full seems an unnecessary misuse of resources, and an
hence designing efficient collection strategies is vital not only to avoidable production of polluting emissions.
reduce operating costs and vehicle emissions, but also to maximize Waste collection business is divided into three major areas:
the amount of re-cycling, while minimizing traffic congestion asso- commercial, residential and roll-on–roll-off. Each area includes
ciated with refuse collection vehicles (RCV) operations (McLeod municipal solid waste and re-cycling material, and each one is very
and Cherrett, 2008). While loading and unloading bins, trucks have different from the others. Residential waste collection generally
to keep their engines running, producing constant exhaust emis- involves servicing private homes, while the commercial waste col-
sions, but also causing noise and traffic congestion. The portion lection involves servicing customers such as strip malls, restau-
of time spent loading and unloading typically depends on different rants and small office buildings. The difference between roll-on–
factors (the technology employed, the size and location of the col- roll-off collection and commercial collection is the size of the
container. This paper considers a particular type of residential
⇑ Corresponding author. Tel.: +39 0498276796, fax: +39 0498276816. waste collection, largely diffused in Italy, in which waste is located
E-mail address: maurizio.faccio@unipd.it (M. Faccio). in bins along the streets of a defined road network. Nuortio et al.

0956-053X/$ - see front matter ! 2011 Elsevier Ltd. All rights reserved.
doi:10.1016/j.wasman.2011.07.005
2392 M. Faccio et al. / Waste Management 31 (2011) 2391–2405

(2006) observed that the amount of municipal solid waste for each ! The savings methods: this method starts with a vehicle route
garbage bin is variable and the accumulation of waste depends on containing the depot and one other vertex. At each step, two
several factors such as the number of inhabitants, lifestyle, time of routes are merged according to the largest saving possibly
the year, etc., therefore, the considered waste collection problem is generated.
stochastic by nature. ! The sweep algorithm: initially feasible clusters are formed
This paper aims to present a new multi objective routing model through the rotation of a ray system centered at the depot.
with real time data interchange for the residential waste collection, Then, a vehicle route is obtained for each cluster by solving a
based on the integration of new technological traceability systems traveling salesman problem.
with a new heuristic routing model. The basic idea is that, if the ! The nearest neighbor: this algorithm starts with a vehicle route
real time position and replenishment level of each vehicle are containing the depot and an arbitrary vertex. At each step, the
known, as it is the real time waste level at each bin and which bins system determines the closest vertex to the last vertex consid-
have been visited, it is possible to decide which bins should be ered and includes it in the route.
emptied and which can be avoided at a certain time. This allows ! The tabu search: starts from an initial solution x1 and moves at
an optimization of the route plan and to minimize covered distance each iteration t from xt to its best neighbor xi+1, until a stopping
and number of vehicles needed, which, as a consequence, would criterion is satisfied. To avoid cycling, solutions that were
minimize travel time, number of load–unload stops, exhaust emis- recently examined are forbidden for a number of iterations.
sions, noise and traffic congestion. Today, modern traceability de-
vices, like volumetric sensors, identification RFID (Radio For a detailed classification of the literature, see Eksioglu et al.
Frequency Identification), GPRS (General Packet Radio Service) (2009) on a taxonomic framework to define and integrate the do-
and GPS (Global Positioning System) technology, can be used to ob- main of the existing VRP literature, and Laporte et al. (2000) with a
tain all the data defined before. proposed survey of heuristics for the vehicle routing problem in
The potential benefits of this new approach are both economic which they distinguished two parts: classical and modern heuristics.
and environmental: From the literature it is possible to notice that, like the classical
VRP, many articles considered other constrains such as vehicle
! Reduction in investment costs for vehicles fleet, thanks to the routing problem with time windows (VRPTW), dynamic pickup
ability to schedule on-demand pick-ups according to the effec- and delivery problem (PDPTW) and the combination of the VRP
tive need, with a consequent reduction in the number of with other problems like location-routing.
vehicles. In the VRPTW, the time windows constraint considers a time
! Reduction in operational costs (fuel, maintenance, etc.), thanks interval, given by an earliest arrival time and a latest arrival time.
to the reduction of vehicles, covered distance and stationary The vehicles can leave the depot not earlier than the earliest arrival
load and unload times. time and they must return to the depot not later than the latest ar-
! The elimination of unnecessary stops, which means a reduction rival time.
of engine emissions, produced both by sanitation vehicles and Kim et al. (2006) addressed a real life waste collection vehicle
traffic congestion. routing problem with time windows (VRPTW) assuming multiple
! The reduction of noise especially in urban areas. disposal trips and drivers’ lunch breaks. They assumed a weekly
predetermined schedule and presented a route construction algo-
After a brief review of literature on vehicle routing problems rithm that was an extension of Solomon’s insertion algorithm (Sol-
and their applications, developed in Section 2, Section 3 introduces omon, 1987). Benjamin and Beasley (2010) considered exactly the
a framework about the traceability technology available to waste same waste collection problem as in Kim et al. (2006) involving
collection and shows an application in the case study. It also pre- multiple disposal facilities, drivers rest period and customer/de-
sents the software application developed in order to obtain and pot/disposal facility time windows. The authors presented a num-
manage real time data used as inputs for the proposed routing ber of meta-heuristic approaches which provide better solutions
model. Later, in Section 4, the authors introduce the heuristics than previous work existing in the literature. Nuortio et al.
model for waste collection. Section 5 validates the model, simulat- (2006) described the optimization of vehicle routes and schedules
ing the results and comparing the new approach with other classi- for collecting municipal solid waste. The authors demonstrated,
cal routing models in function of different patterns of waste through experimental results, that significant savings, can be ob-
generation. The section concludes the simulative study analyzing tained using the proposed heuristic solution method based on
the optimization of a set of parameters necessary for the proposed the guided variable neighborhood thresholding, compared to the
routing model, such as the optimal bin replenishment level, which current practice. Nuortio et al. observed that the amount of muni-
is the parameter that defines if a bin has to be emptied or not. Sec- cipal solid waste is highly variable and the accumulation of waste
tion 6 analyzes the economical feasibility of the real time traceabil- depends on several factors, as a consequence, in their study the
ity routing model in terms of costs/benefits versus the classical average accumulation rate of waste in each container type is esti-
waste collection model, considering different scenario. Our conclu- mated separately using the historical weight and route. The vehicle
sions wrap up the study in Section 7. routing problem with time windows was considered in many arti-
cle that analyzed the problem of perishable food distribution, like
Hsu et al. (2007), Osvald and Stirn (2008) and Chena et al.
(2009). Examples of other application of this problem have been
2. Literature review proposed in Solomon (1987), Li et al. (2010), Hashimoto et al.
(2006, 2008) and Qureshi et al. (2009). Solomon (1987) proposed
Since the very beginning of the vehicle routing problem (VRP), an interesting analysis of algorithms for vehicle routing and sched-
literature has become quite disjointed and disparate. As a conse- uling problems with time windows constraints, after describing a
quence, several versions of the problem, and a wide variety of exact variety of heuristics, and conducting an extensive computational
and approximate algorithms have been proposed. Generally, the study of their performance. Li et al. (2010) studied a version of sto-
VRP is computationally very hard, and cannot be solved by exact chastic vehicle routing problems in which travel and service times
methods, therefore the literature proposes many heuristics. The were stochastic, and time windows constraints are associated with
classical heuristics are each customer.
 M. Faccio et al. / Waste Management 31 (2011) 2391–2405 2393

The vehicle routing problem with pickups and deliveries 2. Only few authors considered the waste collection problem and
(VRPPD) is an extension of the vehicle routing problem (VRP) its unique characteristics in the routing problem.
where the vehicles are not only required to deliver goods to cus- 3. Many studies in VRP use deterministic input data, and consider
tomers, but also to pick some goods up at customer’s locations the waste collection problem, where the quantity of waste
(Nagy and Salhi, 2005). Mitrović-Minić et al. (2004) considered inside the bins is a stochastic variable which invalidates this
the time windows constraint for pickup and delivery, analyzing assumption.
how the distribution of such waiting time may affect the overall 4. Only few studies considered real time input data for the routing
solution quality. In a different article Mitrović-Minić and Laporte optimization and no one focuses on the waste collection
(2004) introduced the concept of double-horizon based heuristics problem.
for dynamic pickup and delivery problem with time windows. 5. Many models in literature are mono-objective, instead, modern
The location-routing problem considers the simultaneous opti- distribution and collection networks aim to be multi-objectives
mization of facility location and design of an underling transporta- (minimize the total cost, minimize the total distance, minimize
tion network. Melkote and Daskin (2001) proposed a studied of the total time, minimize the number of used vehicles, etc.).
this problem motivated by the simple observation that changing
the network topology is often more cost-effective than adding This preliminary literature analysis evidences how a real time
facilities to improve service levels. Nagy and Salhi (2007) observed traceability data integrated with a multi objective routing model
many articles on the location-routing problem (LRP), and proposed in residential waste collection, represents an important contribu-
a survey about the state of the art in location-routing with a clas- tion in the management of the last phase of the life cycle of food
sification scheme. An example of research on this problem was and its packaging material. Not only the integration of real time
proposed in a study by Albareda-Sambola et al. (2007), in which data with the multi-object vehicle routing model allows to reduce
a stochastic location-routing problem was defined and cast as a the number of visited and emptied bins, but as direct effects envi-
two-stage model: in a first stage, are determined set of plants ronmental impacts like emissions, noise and traffic congestion are
and a family of routes; in a second stage a recourse action was ap- reduced.
plied to adapt these routes to the actual set of customers to service,
once that information is available.
The literature review and Table 1, where a classification of sci- 3. Waste collection framework
entific literature dedicated to vehicle routing problem (VRP) is
summarized shows that: The problem of municipality solid waste collection optimization
considering real time input data, homogeneous and variable fleet
1. The vehicle routing problem (VRP), especially with time win- size and single depot is evaluated here and a framework for the
dows (VPRTW) is computationally very hard, and cannot be solution of this problem is presented in Fig. 1. The inputs data
solved by exact methods and heuristics are used for this pur- can be classified in two main types: static inputs and real time
pose (Nuortio et al., 2006). traceability data inputs.

Table 1
Literature analysis.

Authors Year Type of input Solution Num. of Vehicle fleetd Fleet Vehicle capacity Time Objective
dataa methodb depotsc sizee constraint window
Albareda- 2007 Stochastic Heuristic Multiple – – – – Minimize the total cost
Sambola et al.
Benjamin & 2010 Stochastic Heuristic Single Homogeneous Variable X X Minimize the total distance
Beasley
Chena et al. 2009 Stochastic Heuristic Multiple Homogeneous Variable X – Maximize the expected total
profit
Eksioglu et al. 2009 – – – – – – – Literature review
Hashimoto et al. 2006 Stochastic Dynamic Single Homogeneous Fixed X X Minimize the total cost
programming
Hashimoto et al. 2008 Stochastic Dynamic Single Homogeneous Fixed X X Minimize the total cost
programming
Hsu et al. 2007 Deterministic Heuristic Single Homogeneous Variable X X Minimize the total cost
Kim et al. 2006 Deterministic Heuristic Single Homogeneous Variable X X Minimizing fleet size and
total travel time
Laporte et al. 2000 – – – – – – – Literature review
Li et al. 2010 Stochastic Heuristic Single Homogeneous Variable X X Minimize transportation
costs
Melkote & 2001 Deterministic Exact Multiple – – – – Minimize the total cost
Daskin
Mitrovic-Minic & 2004 Real Heuristic Single Homogeneous Variable X X Minimize the total distance
Laporte traveled
Mitrovic-Minic 2004 Real Heuristic Multiple Homogeneous Variable X X Minimize total route length
et al.
Nagy & Salhi 2007 – – – – – – – Literature review
Osvald & Stirn 2008 Deterministic Heuristic Single Homogeneous Variable X X Minimize the total cost
Qureshi et al. 2009 Stochastic Exact Single Homogeneous Variable X X Minimize the total cost
Solomon 1987 Stochastic Heuristic Single Homogeneous Variable X X Parametric analysis
a
Deterministic or stochastic.
b
Exact or heuristic.
c
Single or multiple.
d
Homogeneous or not-homogeneous.
e
Fixed or variable.
2394 M. Faccio et al. / Waste Management 31 (2011) 2391–2405

Fig. 1. Real time traceability data routing model for waste collection.

! The static inputs regard the information about bins types and and logistic environments have been developed using RFID tech-
positions, maximum volume capacity and type of waste stored. nology (Battini et al., 2009), where common automatic identifica-
Secondly they are about vehicles, their type and their maximum tion devices like bar codes, magnetic strips, microprocessor
weight capacity. papers and biometric systems that require a line of sight with
! The real time traceability data inputs are received by the trace- the object are not possible. These systems, as convenient as they
ability technology devices installed and are relative to the effec- might seems in some instances, actually present a fairly limited
tive replenishment of bins and vehicles, visited bins and range of possible applications. Bar codes offer a limited amount
vehicles position. of data stored, little flexibility of stored data due to the impossibil-
ity of re-writing, the incapacity of reading more codes simulta-
By processing all these information through the proposed heu- neously, degradation of the identification systems, need for a
ristic routing optimization model is possible to obtain the optimal very precise range reading, and reading difficulties due to dirt
route for each vehicle in order to reduce the number of bin to ser- and damage to look of the code. RFID technology aims at avoiding
vice, minimize fleet covered distance, number of vehicles used and these problems by using the electromagnetic field between the tag
collection time. Every time a vehicle empties a bin the input data that is applied to the object and the antenna. This electromagnetic
are reprocessed at the operations center, both static and real time field allows automatic data capture, unique for each object, and, if
inputs are updated, defining the new optimal route for each vehi- needed, it allows an automatic insertion of these data into several
cle, and the real time traceability data routing model starts again software and databases, using a middleware system able to com-
(Fig. 1). pute and filter the identification code and the data stored in the
The real time traceability system necessary for real time input is tags. In a nutshell, it allows the automatic acquisition of identifica-
based on three fundamental levels, each one connected to other as tion data without a line of sight with the object and the automatic
indicated in Fig. 2: insertion of the data in the tags.
The reliability of this technology is relative to the reliability of
! Bins the tags themselves and the reader antenna device: in normal con-
! Vehicles ditions the tag reliability is approximately equal to 100%, especially
! Operations center if using passive tags (composed by principally a spire covered by
plastic material), while the reader device is protected. According
The considered vehicle types are self-compactors, and for this to Battini et al. (2009) to achieve a successful application of the
reason it is assumed that they saturate their capacity in weight RFID technology, the main variables to keep into account in the
not in volume, while in general, bins saturate their capacity in vol- preliminary study of RFID project are: project variables (PVs) and
ume. Bins periodically communicate to the operations center their project conditions (PCs). PVs represent different aspects of the
waste replenishment level in term of volume, every time a vehicle technology and they are related to the main decisions faced by
empties one bin, the bin communicates to the vehicle its identifi- the project manager during the technical–economic evaluation of
cation number and its waste type. Usually, at bin level, the trace- the RFID project. PCs take into consideration the different operat-
ability devices can be fed with solar energy rechargeable battery. ing aspects where the RFID system will be implemented.
Operations center know in real time the vehicles position and, at The PVs variables and their definition in this waste collection
each bin serviced, the vehicle communicates to the operations cen- project are
ter the weight of loaded waste, the bin identification and the avail-
able weight capacity for the vehicle. The vehicle subsequently ! Tag type: the tag is used at the bin level for its identification.
receives information from the operations center about the next Due to its use we recommend a rugged passive tag in order to
bins to visit according the proposed routing model. increase reliability, to reduce the need of energy at the bin level,
The real time traceability data inputs need the application of to survive extreme environmental conditions of humidity and
different traceability devices, like volumetric sensors, RFID, GPRS temperature, and in order to overcome difficulties due to dirt
and GPS. If GPS and GPRS technology are nowadays largely avail- and damage.
able used and diffuse, even in the day by day life (cell phones, sa- ! Reader type: a middle frequency RFID antenna is positioned on
tellite navigator, etc.), RFID devices are not as popular or as user- the vehicle’s container hooking (13.56 MHz), so that the dis-
friendly. In the past few years, many applications in industrial tance between devices is less that 1 m.
 M. Faccio et al. / Waste Management 31 (2011) 2391–2405 2395

Fig. 2. Traceability technology framework.

! Middleware-software and system integration: the RFID system is ! A GPRS data service technology ensures data exchange with
interfaced with the other devices through systems of data inter- the other levels of the system.
change and to operations center traceability software
application.
Vehicle level:
The PCs variables and their definition in this waste collection
project are ! A GPS system can determine the real time location of each
! Environmental conditions: in the application the environmental vehicle.
variables that can influence the results are related to humidity ! A GPRS data service technology ensures data exchange with
and temperature levels that can easily managed using rugged other levels of the system.
passive tags protected by plastic materials. In this application ! The vehicle traceability software application, installed in a
the interference created by magnetic fields is unusual and the mobile laptop, allows the driver to know the next bin to ser-
short reading distance between antenna and tag prevents dis- vice, according to the proposed routing model.
turbance due to metal objects in the vicinity of the tag. ! An RFID antenna positioned on the container hooking rack
! Operating conditions: the reading range is short and the for the bin identification.
amount of storing data and concurrent reading is low. ! A weighing system, consisting of two units installed at the
ends of the bin lifting arm, allows to weight the loaded waste
Looking at PVs and PCs variables the proposed RFID solution ap- in order to define the instantaneous available capacity of the
pears reliable and robust respect the working conditions. vehicle.
Summarizing the three traceability levels are composed, by
(Fig. 2): Operations center level:

Bin level: ! A GPRS data service technology ensures data exchange with
the other levels of the system.
! A programmable microprocessor (MPU) that is the heart of ! The operations center traceability software application per-
the system at bin level. It manages the detective measures mits to collect and illustrate all real time data from the dif-
inside the bin (such as volume, time). ferent levels of the traceability system, and to process
! A volumetric ultrasonic detection sensor connected to the them in order to define the optimal routing according to
microprocessor for the periodic volume measure. the proposed model.
! A rugged passive RFID tag for the bin identification.
2396 M. Faccio et al. / Waste Management 31 (2011) 2391–2405

4. Real time traceability data routing model ! The static and real time traceability data inputs.
! The oversize risk parameter, OR [%]. The oversize risk is the risk to
This section shows the heuristic model for routing optimization. exceed bin capacity, and it depends, on the number of users, on
The objective of the routing model is multiple: a management decision about the admitted maximum % of bins
that are allowed to exceed their capacity, respect the total num-
! To minimize number of vehicles per fleet. ber of bins. Obviously the oversize risk needs to be kept low and
! To minimize travel time. close to 0 in order to preserve the integrity and safety of the
! To minimize total distance covered. city, but in case of very variable patterns of waste creation, this
parameter is an indication that the bin needs to be visited with
These three objectives are achieved according to the basic idea high frequency. As reported in the simulation analysis section
of the proposed routing model: if it is possible to reduce the num- the definition of the oversize risk parameter, OR [%] is a critical
ber of serviced bins, then it becomes possible to minimize number aspects related to the pattern of waste creation at the bin.
of vehicles needed to serve an area, distance covered and travel ! The optimal replenishment level parameter, RL [%]. The optimal
time. As a direct effect it is possible to reduce environmental im- replenishment level is the minimum level of filled that the bins
pact of emissions, noise and traffic congestion. must reach before it is eligible to be emptied. This parameter
In order to apply these criteria is important to consider the is, like the OR [%] parameter, another management decision, that
following data: directly influences the costs of waste collection. As reported in

Table 2
Notations, inputs and outputs of the routing model.

Temporary variables Description Measure

unit
I ID number. I = 1, . . ., n identifies the actual bin serviced by the vehicle, while I = 0 indicate that the vehicle is at the depot [num.]
J ID number. J = 1, . . ., n identifies the possible next bin to be serviced by the vehicle, while I = 0 indicate that the next possible [num.]
stop of the vehicle is at the depot
K ID number of the vehicle, K = 1, . . ., n_vehicles [num.]
p Mission. It defines the sequence of trips for a considered vehicle [num.]
Travel_time (I, J) Travel time from I to J [h]
Time Time variable [h]
q_vehicle (K) Replenishment level of the vehicle k [kg]
qw (J) Weight of waste inside the bin J. with J = 1, . . ., n [kg]
qv (I) Volume of waste inside the bin I with I = 1, . . ., n ]liters]
Not visited Counter: number of bins not serviced [num.]
Exceed_capacity Counter: number of bins that exceed their capacity [num.]
Ok Cycle control binary variable (for the while cycle)
Static inputs
n Number of bins [num.]
x(I) and y(I) Position of each bin, I = 1, ...., n (x, y)
x(0) and v(0) Position of die depot (x, y)
unload time Fixed time to unload a bin [h]
vehicle speed Average vehicle speed [km/h]
start_time (I) Time windows: start time imposed equal for bin I [h]
finish_time (I) Time windows: finish lime imposed equal for bin I [h]
OR Oversize risk: maximum number of bins that can exceed (heir capacity [%]
INIT_RL Initial value of the replenishment level of the bin to be serviceable [%]
maxd_vehicle Maximum distance to be traveled per vehicle per day [km]
maxq_vehicle Maximum weight capacity of the vehicle [kg]
maxq_bin Maximum volume capacity of the bin [liters]
Distance (I, J) Distance from I to J [km]
Realtime traceability
data inputs
qv0 (I) Volume of waste generated at period 0 inside the bin I [liters]
qvl (I) Volume of waste generated at period 1 inside the bin I [liters]
ratio_weight_volume Average ratio weight/volume [kg/liters]
ac_time Actual time [h]
visited (I) Binary value, it is equal to 1 if the bin I has already been visited, zero otherwise. I = 1, .., n
k_vehicle ID number of die vehicle [num.]
n_vehicles_in Number of vehicles already in use = max (K_vehicle) [num.]
posiz ID number of the position of the considered vehicle. It corresponds to the position of die last visited bin by the considered [num.]
vehicle
q_vet (K) Actual replenishment of the vehicle K [kg]
L_not (K) Distance already traveled by the vehicle K [km]
Outputs
n_vehicles Number of planned vehicles in order to complete the collection in the considered period [num.]
L (K) Planned distance traveled by the vehicle K [km]
rout (Kp) Planned bin to service by the vehicle K in the mission p
bin_not_to_vis (I) List of the planned bin not to be emptied
tot dist Planned total covered distance as sum of the distance covered by each vehicle [km]
bin_time (I) Planned collection time for the bin located in I [h]
Tot_q Total quantity of generated waste [liters]
RL Optimal replenishment level parameter [%]
 M. Faccio et al. / Waste Management 31 (2011) 2391–2405 2397

the simulation analysis section the definition of the optimal An important consideration is that the three parameters defined
replenishment level parameter, RL [%] is a critical aspects, related are inter-dependent. The proposed model allows using stochastic
to the decision of the oversize risk parameter, OR [%] and on the input, based on historical data, to analyze the parameters relations
pattern of waste creation at the bin. As highlighted in the next and to define the value of oversize risk and optimal replenishment le-
section it is possible to optimize the RL [%] in order to minimize vel that allow to achieve the expected benefits and results.
the total costs for waste collection once OR [%] is defined accord- The proposed heuristics consists of two main steps (Table 3):
ing to the pattern of waste creation at the bin.
1. To define which bins must be serviced. Only the bins that reach
The oversize risk parameter has to be a fixed parameter because the imposed minimum replenishment level are visited. This
waste generation at each bin is typically a stochastic variable, and information depends on the real time traceability data acquired
the risk of oversize bin capacity has to be considered. and on the optimal replenishment level parameter.

Table 3
Heuristic waste collection routing model with real time traceability data.
2398 M. Faccio et al. / Waste Management 31 (2011) 2391–2405

2. Once defined which bins have to be emptied each vehicle route chastic variable. From the historical data obtained in an applicative
is optimized according to the real time traceability data (Fig. 1). case in northeastern Italy the normal distribution optimally fits the
quantity of waste generated at each bin. So these results are vali-
Moreover the following main constraints are considered: dated in case of normal distribution, in other cases the results
could be altered.
Vehicles constrains: The two parameters of the normal distribution for waste gener-
1. The capacity constraint: when a vehicle is full, it needs to ation at each bin are
return to the depot to be emptied. Typically this parameter ! WAL, waste average level, as the % of the replenishment level of
is fixed in weight. The weight of each unloaded bin is given the bin [%].
by the traceability devices installed in the vehicle. ! SD/WAL, as the ratio between the standard deviation and the
2. The distance constraint: each vehicle can, and typically does, waste average of the replenishment level of the bin [%].
make multiple disposal trips per day. When the vehicle
reached the maximum daily distance covered, another vehicle They have been changed from an initial average value obtained
will take over. For the waste collection problem this kind of by the historical data with the objective of:
constrain is overcome by the start and finish time constrain.
3. The time windows constraint: the vehicles can leave the 1. To compare the classical vehicle routing models versus the pro-
depot only after the imposed ‘‘start time’’ and they must pose heuristics in function of the oversize risk parameter, OR [%],
return to the depot within the set ‘‘finish time’’. In this in order to validate the proposed approach.
study, due to the small number of vehicles considered (4– 2. To define the optimal replenishment level parameter, RL [%], i.e.
5 vehicles), it is implied that all the vehicles leave the depot the minimum bin replenishment level for waste collection,
at the same time without queuing problems. In case of a parameter that defines if a bin has to be emptied or not, in func-
large number of vehicles the queuing problem at the depot tion of the oversize risk OR and of the pattern of waste genera-
has to be considered and managed (Wilson et al., 2002). tion with a normal distribution with average value WAL and
4. The time constraint: in terms of average speed and unload standard deviation SD.
time for each bin.
The fixed input data are derived from an applicative case rela-
Bins constrains: tive to a city, in northeastern Italy, with more than 100,000 inhab-
5. The capacity constraint: a bin has a limited capacity. Typi- itants with a twice/weekly waste collection as illustrated in Table
cally this parameter is fixed in volume, so the replenishment 4.
level of each bin is given by the traceability devices installed
in the bin itself. The admitted maximum number of bins 5.1. Routing models benchmark and proposed approach validation
that can exceed this limit is given by the OR parameter.
6. The geographical position of each bin, the location of the The objective of this section is to validate the proposed ap-
depot and the distance between each other. proach for waste collection, through a simulation and a routing
model benchmark. The simulation is made using Matlab software
Boundary conditions: package (www.mathworks.com). Table 5 summarizes the range
7. The initial waste level at each bin: it depends on the waste quan- of variation for the input data in the simulation ( WAL, SD/WAL,
tity generation pattern at each bin. If a bin is not serviced in OR, RL) considering waste generation at each bin as stochastic var-
period 0, in the second waste collection mission at period 1 iable with average value WAL and standard deviation SD. The range
its replenishment level will be the sum of the waste generation of variation has been fixed looking at historical data of the applica-
at instant 0 and at instant 1. The waste generation quantity at tive case.
each considered periods depends on the waste generation pat- The analysis compares different models and whether to adopt
tern of the considered bin, an information provided by the real or not real time traceability data as inputs and whether or not they
time traceability data device. respect the collection rules. The considered routing models in the
8. The ratio weight/volume for the collected waste, due the analysis are
different saturation parameter at bins (volume) and self- (A) Model A is the classic vehicle routing model for waste collec-
compactors vehicles (weight) is directly given by the real tion, where all the location are visited at each trip
time traceability data.
! The collection rule is the nearest neighbor.
Finally, the model assumes an operational area composed by a ! Real time traceability data inputs are not necessary.
set of bins that must be emptied, a single depot that is also the ! All bins are visited.
landfill and an homogeneous vehicles fleet. Vehicles start and re-
turn to the depot. (B1) Model B1 is a real time traceability data routing model
Table 2 introduces the notation used in the model such as tem- where
porary variables, inputs, composed by static inputs and real time
traceability data inputs, and outputs of the model. ! The collection rule is the maximum ratio quantity of waste/
Table 3 shows a step-by-step description of the proposed rout- distance.
ing model, defined using the pseudocode language. Pseudocode is a ! Real time traceability data are necessary.
kind of structured English for describing algorithms that allows to ! Only bins that exceed the optimal replenishment level parameter
focus on the logic and on the basic idea of the algorithm. RL are visited according the collection rule. RL is optimized as a
function of the waste generation pattern and of the OR [%].

5. Simulative analysis (B2) Model B2 is a real time traceability data routing model
where
This section presents a simulative analysis. The waste genera-
tion input data, given by the real time traceability devices is a sto- ! The collection rule is the maximum ratio of waste/distance2.
 M. Faccio et al. / Waste Management 31 (2011) 2391–2405 2399

Table 4 level of waste for bin WAL, because of the number of bins to service
Fixed inputs, waste collection problem characteristics. when available real time data decrease. Another consequence is
Bins characteristics the identification of the best collection rule in case of real time
n Number of bins [num.] 200 traceability data utilization, showing how model C gives better
x(I) and y(I) Geographical coordinates of each bin (x; y) overall results than models B, when the average level of waste
maxq_bin Maximum volume capacity of the bin [l] 1100
for bin WAL grows. This result defines that critical factors to con-
Vehicles characteristics sider in the collection rule are distance, in terms of covered dis-
maxd_vehicle Maximum distance that can be traveled per 400
vehicle per day [km]
tance and vehicles utilization as you go from routing model B1 to
maxq_vehicle Maximum weight capacity of the vehicle [kg] 12,625 routing model B3, where the distance weight is growing in respect
unload_time Duration of bin unload [h] 0.05 to the quantity of waste in the bin.
vehicle_speed Average vehicle speed [km/h] 40 Looking at Figs. 3–5, where the oversize risk OR changes from
INIT_RL Initial value bins replenishment level for 100%
5% to 10% and to 15%, the benchmark between model A (the clas-
waste collection [%]
start_time Start time imposed [time] 5 a.m. sical waste collection routing model) versus model C (the proposed
finish_time Finish time imposed [time] 8 a.m. routing model for waste collection) shows an increment of benefits
Network characteristics with OR risk growth, for a fixed value of WAL parameter. This point
x(0) and y(0) Position of the depot (x; y) is very clear comparing OR = 5% with OR = 15% for fixed WAL = 70%.
distance (I,J) Minimum distance between two location 0.04 The final results of the routing models benchmarking are
[km] ! The proposed routing model (model C) that considers real time
distance (I,J) Maximum distance between two location 12.56
[km]
traceability data as input, with optimal replenishment level
ratio_weight_volume Average ratio weight/volume [kg/l] 0.8 parameter RL as a fixed function of the waste generation pattern
and of the OR [%] in order to define what bin has to be serviced,
and uses the nearest neighbor as collection rule, results to be
always the best method in terms of used vehicles and total cov-
Table 5 ered distance reduction.
Range of variation of the inputs for routing models benchmark. ! The proposed routing model (model C) with respect to the clas-
Variable inputs Percent values Values sical routing model used for waste collection (model A) gives
OR [%] 5–10–15 10–20–30 [num. bins]
better results when the oversize risk parameter OR increases
WAL [%] 40–55–70 440–605–770 [l] and when the average waste level at bin WAL decreases.
SD/WAL [%] 20 88–121–154 [l] ! Looking for example at the case of OR = 5% and WAL = 55% com-
paring model C versus model A, for an average total generated
waste of 122 m3 the reduction of vehicles necessary is about
! Real time traceability data are necessary. 20% (from 5 to 4) and the total distance covered by all the vehi-
! Only bins that exceed the optimal replenishment level parameter cles in a waste collection is reduced of 12% (from 179 to
RL are visited according the collection rule. RL is optimized as a 158 km).
function of the waste generation pattern and of the OR [%].
5.2. Optimal bin’s replenishment level parameter analysis
(B3) Model B3 is a real time traceability data routing model
where The objective of this section is to define, for a given waste gen-
eration pattern at bin level and for an assumed oversize risk OR [%],
! The collection rule is the maximum ratio quantity of waste/ what is the optimal replenishment level parameter RL [%], that
distance3. would define which bin has to be serviced and which does not. This
! Real time traceability data are necessary. Only bins that exceed analysis gives a valid decision making tool in using the proposed
the optimal replenishment level parameter RL are visited accord- real time traceability data routing model. This analysis has been
ing the collection rule. RL is optimized as function of the waste explained in Section 4 and validated in Section 5. The waste gener-
generation pattern and of the OR [%]. ation pattern, verified using data derived by the applicative case, is
a Normal distribution, with average value WAL and standard devi-
(C) Model C corresponds to the real time traceability data rout- ation SD. In this analysis, like previously explained, these parame-
ing model proposed by the authors as shown in Section 4 where ters are related to the bin capacity in term of percentage for WAL
[%], and standard deviation is related to the average value consid-
! The collection rule is the nearest neighbor. ering SD/WAL [%]. The range of variation for this analysis is re-
! Real time traceability data are necessary. ported in Table 6.
! Only bins that exceed the optimal replenishment level parameter The results of this analysis it is reported in Fig. 6.
RL are visited according the collection rule. RL is optimized as a In case the optimal replenishment level parameter RL [%] is equal
function of the waste generation pattern and of the OR [%]. to 0, the number of bins that need to be serviced corresponds to all,
and the proposed routing model (model C) is equal to the classical
Fig. 3 shows the results in terms of number of necessary vehi- routing model for waste collection (model A). As reported in Fig. 6
cles and total covered distance in function of the total amount of it is possible to obtain different curves in function of the oversize
generated waste with 5% of OR, Fig. 4 shows the same with 10% risk OR [%] chosen. Such curves give the optimal replenishment level
of OR, and Fig. 5 with 15% of OR. As reported in Table 5, RD/ parameter RL [%] output in function of the waste average WAL [%]
WAL = 20% for all the considered cases. and of the standard deviation percentage SD/WAL [%].
Considering Fig. 3 and looking at the first case with WAL = 40%, The main results of the optimal bin’s replenishment level
it is clear how the real time traceability routing models (models B parameter analysis are
and C) produce benefits compared to the classical routing model ! When the optimal replenishment level parameter RL [%]
(model A) in term of the reduction of number of vehicles necessary decreases, a major number of bins has to be serviced. That
and total distance covered in function of the total generated waste. means that the benefits of the proposed model in term of nec-
As predictable, these benefits are directly related to the average essary vehicles and total covered distance reduction are limited.
2400 M. Faccio et al. / Waste Management 31 (2011) 2391–2405

Fig. 3. OR = 5%, routing models benchmark.

! The presented curves allow to chose the optimal replenishment ! The optimal replenishment level parameter RL [%] decreases
level in function of the waste generation pattern and in function when
of the oversize risk OR [%] chosen, which turns out to be an opti- s OR [%] decreases.
mal decision making tool for engineers who decide to adopt the s WAL increases.
proposed routing model. s SD/WAL increases.
 M. Faccio et al. / Waste Management 31 (2011) 2391–2405 2401

Fig. 4. OR = 10%, routing models benchmark.

! In case of SD/WAL = 20% the proposed routing model (model C) ! When SD/WAL = 35% for OR = 5% with WAL P 65% all the bins
is always (in the considered range of WAL) better than the clas- have to be emptied.
sic (model A) in terms of number of bins to service, of vehicles ! When SD/WAL = 50% for OR = 5% with WAL P 55% all the bins
necessary and total distance covered. have to be emptied.
2402 M. Faccio et al. / Waste Management 31 (2011) 2391–2405

Fig. 5. OR = 15%, routing models benchmark.

cate real time data, a fundamental input for the model which is an
6. Economical feasibility analysis expense outweighed by a reduction of vehicles necessary and total
distance covered. Objective of this section is to analyze, from an
The implementation of the proposed routing model for waste economic feasibility point of view, the return of the investment
collection imposes, as highlighted in Section 3, to install traceabil- in using traceability devices and applying the proposed routing
ity devices at different levels of the system to be able to communi- model (model C) versus the classical routing model for waste
 M. Faccio et al. / Waste Management 31 (2011) 2391–2405 2403

Table 6 and PbP of the analysis. For the purpose of our study, the duration
Range of variation of the inputs for optimal bin’s replenish-
of the investment has been fixed to 5 years, even if it could be con-
ment level parameter analysis.
sidered longer.
Variable inputs Values As highlighted in Fig. 7 the proposed real time traceability data
OR [%] 5–10–15 routing model gives, even from an economic point of view, optimal
WAL [%] 35–40–45–50–55–60–65–70 results in the average condition of waste collection management,
SD/WAI [%] 20–35–50
with an average replenishment level per bin WAL = 55% (scenario
2 and scenario 3) if compared with the classical waste collection
routing model. The PbP is less than 3 years and the PV is almost
collection (model A). The analysis, as reported in Table 7, defines equal to 50,000 € in 5 years. Only if the condition are very extreme
installation costs and operative annual costs but does not consider (scenario 4 WAL = 70%) the initial investment in traceability sys-
costs that are necessary in both models. The analysis uses the tems is not regained in the first 5 years.
classical indicators for economic feasibility studies like Present
Value (PV), that defines the final value of the investment return,
and Pay Back Period (PbP), which defines how long is the period 7. Conclusion and further research
to regain the initial investment. The scenarios differ in function
of OR [%] and WAL [%] parameters, given that SD/WAL [%] is fixed Waste collection is an important, but expensive municipal ser-
at 20%. The considered conditions are the same as those in the case vice, especially in terms of investment costs, operational costs and
study analyzed (Table 4) for a urban environment of 100,000 environmental impact. Modern traceability devices, like volumet-
inhabitants, where waste collection happens twice weekly. Table 7 ric sensors, identification RFID systems, GPRS and GPS technology,
shows the specific costs considered and the results in terms of PV allow to obtain real time data which are fundamental to the

Fig. 6. Optimal bin’s replenishment level parameter analysis.

2404 M. Faccio et al. / Waste Management 31 (2011) 2391–2405

Table 7 model for waste collection that aims to minimize the number of
Installation costs and annual costs. vehicles necessary and travel time and increase total covered dis-
Installation costs tance, without mentioning the direct effect of reducing environ-
Vehicles purchase cost It includes initial cost for the purchase of vehicles mental impact like emissions, noise and traffic congestion. The
Traceability equipment It includes purchase of traceability equipment main innovative aspects introduced are a framework to implement
cost per vehicle per vehicle (Fig. 3)
Traceability equipment It includes purchase of traceability equipment
the modern traceability devices in waste collection, the integration
cost per bin per bin (Fig. 3) of real time traceability data inputs with static inputs in an effec-
Traceability operations It includes purchase of traceability equipment for tive and innovative routing model, and the optimization of some
center cost operations center (Fig. 3) critical parameters used in the routing model in function of utiliza-
Annual costs tion conditions like, for instance, waste generation patterns.
Fuel and oil consumption It includes cost for fuel and oil consumption The main results can be summarized as follows:
depending on the number of kilometers/year
Drivers cost It includes cost for drivers/operators and
depends on number of vehicles ! The use of the modern traceability technology in waste collec-
tion, as described in Section 3, allows to produce real time input
(like real time replenishment level of each bin, real time vehicle
implementation of an efficient and innovative waste collection position, etc.) which are fundamental in the proposed routing
routing model. This paper introduces a multi-objective routing model.

Fig. 7. Economic feasibility analysis.

 M. Faccio et al. / Waste Management 31 (2011) 2391–2405 2405

! The integration of static inputs with real time traceability data References
inputs in an effective routing model, where the collection rule
is the nearest neighbor and only bins that exceed the optimal Albareda-Sambola, M., Fernàndez, E., Laporte, G., 2007. Heuristic and lower bound
for a stochastic location-routing problem. European Journal of Operational
replenishment level parameter RL are serviced, as described in Research 179, 940–955.
Section 4, allows to achieve the different objectives described Battini, D., Faccio, M., Persona, A., Sgarbossa, F., 2009. A new methodological
before. If this model is compared with the classical routing framework to implement an RFID project and its application. International
Journal of RF Technologies: Research and Applications 1 (1), 77–94.
model used in waste collection, where the collection rule is Benjamin, A.M., Beasley, J.E., 2010. Metaheuristics for the waste collection vehicle
the nearest neighbor, real time traceability data inputs are not routing problem with time windows, driver rest period and multiple disposal
used and all bins are services all the times, the results reported facilities. Computers & Operations Research 37, 2270–2280.
Chena, H.K., Hsuehb, C.-F., Changc, M.S., 2009. Production scheduling and vehicle
in Section 5.1 demonstrate and validate the potential benefit in
routing with time windows for perishable food products. Computers &
using the proposed routing approach. Operations Research 36, 2311–2319.
! A set of important parameters are introduced in the proposed Eksioglu, B., Vural, A.V., Reisman, A., 2009. The vehicle routing problem: a
routing model: taxonomic review. Computers & Industrial Engineering 57, 1472–1483.
Hashimoto, H., Ibaraki, T., Imahori, S., Yagiura, M., 2006. The vehicle routing
o The oversize risk parameter, OR [%], i.e. the risk of oversize problem with flexible time windows and traveling times. Discrete Applied
bin capacity, that define the maximum % of risk and Mathematics 154, 2271–2290.
depends on a waste collection management decision. Hashimoto, H., Yagiura, M., Ibaraki, T., 2008. An iterated local search algorithm for
the time-dependent vehicle routing problem with time windows. Discrete
o The optimal replenishment level parameter, RL [%], i.e. the Optimization 5, 434–456.
minimum bin replenishment level for waste collection, Hsu, C.I., Hung, S.F., Li, H.C., 2007. Vehicle routing problem with time-windows for
that defines the % of replenishment that make a bin ser- perishable food delivery. Journal of Food Engineering 80, 465–475.
Jedermann, R., Ruiz-Garcia, L., Langa, W., 2009. Spatial temperature profiling by
viceable or not. semi-passive RFID loggers for perishable food transportation. Computer and
These parameters are interdependent with the waste Electronics in Agriculture 65, 145–154.
generation pattern at bin level. Section 5.2 analyzes this Kim, B.I., Kimb, S., Sahoo, S., 2006. Waste collection vehicle routing problem with
time windows. Computers & Operations Research 33, 3624–3642.
interdependency assuming a normal distribution (as Laporte, G., Gendreau, M., Potvin, J.Y., Semet, F., 2000. Classical and modern
highlighted by the experimental results) for waste gener- heuristics for the vehicle routing problem. International Transaction in
ation pattern and outputs a valid decision making tool in Operational Research 7, 285–300.
Li, X., Tian, P., Leung, S.C.H., 2010. Vehicle routing problems with time windows and
setting these parameters, for the proposed routing model
stochastic travel and service times: models and algorithm. International Journal
as functions of the utilization conditions. Production Economics 125, 137–145.
! The economical feasibility analysis, developed in Section 6, McLeod, F., Cherrett, T., 2008. Quantifying the transport impacts of domestic waste
demonstrates that the benefits of using the proposed routing collection strategies. Waste Management 28, 2271–2278.
Melkote, S., Daskin, M.S., 2001. An integrated model of facility location and
approach are averagely wider than the costs for the implemen- transportation network design. Transportation Research Part A 35, 515–538.
tation of the traceability technology. This result validates not Mitrović-Minić, S., Krishnamurti, R., Laporte, G., 2004. Double-horizon based
only from a technical point of view, but also from an economical heuristics for the dynamic pickup and delivery problem with time windows.
Transportation Research Part B 38, 669–685.
point of view, the proposed routing model for waste collection. Mitrović-Minić, S., Laporte, G., 2004. Waiting strategies for the dynamic pickup and
delivery problem with time windows. Transportation Research Part B 38, 635–655.
This study represents an important contribution in the manage- Nagy, G., Salhi, S., 2007. Location-routing: issues, models and methods. European
Journal of Operational Research 177, 649–672.
ment of the last phase of the life cycle of food and its packaging Nagy, G., Salhi, S., 2005. Heuristic algorithms for single and multiple depot vehicle
material, and other applications are still now in progress. However routing problems with pickups and deliveries. European Journal of Operational
this kind of approach in the routing optimization it is potentially Research 162, 126–141.
Nuortio, T., Kytöjoki, J., Niska, H., Bräysy, O., 2006. Improved route planning and
applicable in other fields of the food industry. For example, accord- scheduling of waste collection and transport. Expert Systems with Applications
ing with Jedermann et al. (2009) perishable food products are at 30, 223–232.
risk of suffering various damages along the cold chain. The parties Osvald, A., Stirn, L.Z., 2008. A vehicle routing algorithm for the distribution of fresh
vegetables and similar perishable food. Journal of Food Engineering 85, 285–295.
involved should control and monitor the conditions of goods in or-
Qureshi, A.G., Taniguchi, E., Yamada, T., 2009. An exact solution approach for vehicle
der to ensure their quality for consumers and to comply with all le- routing and scheduling problems with soft time windows. Transportation
gal requirements. Consequently an important research area Research Part E 45, 960–977.
appears the development of effective distribution routing models Solomon, M.M., 1987. Algorithms for the vehicle routing and scheduling problems
with time window. Constraints Operations Research 35 (2), 254–265.
in very critical contexts in term of perishable food, integrating Wilson, B.G., Baetz, B.W., Hall, F.L., 2002. Reduction of queuing delays at waste
the presented real time traceability data with the physical condi- management facilities. Civil Engineering and Environmental Systems 19 (4),
tions of the transported items (temperature, humidity, etc.). 311–331.