Transcript Routing Wastesum

International Conference on
Sustainable Solid Waste Management (SSWM -09)
Application of a software tool for routing
optimisation in the Azemmour area
D. Malamis, M. Loizidou, M. Mountadar, M. Rihani
et O. Assobhei
Friday 19 June 2009
Introduction
• The municipality Azemmour
– population 40.000
– 30tn of MSW/day,
– 0.75kg of MSW/capita/day
• The collection and transfer of the
Municipal Solid Waste (MSW) is a Vehicle
Routing Problem (VRP)
• Presentation of a software tool – “Container
Collector” -that optimizes the collection and
transfer of MSW in the municipality of
Azemmour
Importance of VRPs
Produce routes that contribute to the reduction
of:
– cost, by offering simultaneously significant
savings in all related expenses (capital and
maintenance cost, fuel cost, personnel cost)
– potential environmental impacts (e.g. air
emissions from vehicles)
“Container Collector” software
• designed, implemented and deployed under
the platform of MS Windows XP
• solving the Vehicle Routing Problem in the
case of urban waste container collection
• automatically generates optimum vehicle
routes (which vehicles should deliver to which
customers and in which order) minimizing
simultaneously
– the vehicle costs and
– the total distance traveled by the vehicles
Constrains are set through equations
n
• minimization of the vehicle costs
and the total distance covered by
the vehicles
• each container is serviced by
exactly one vehicle
• ensuring the route continuity –
means that a vehicle arriving at a
customer must also leave this
customer
• each vehicle must not service
more than its capacity in each
route
• maximum route length or duration
• each vehicle is used exactly once
n
K
 ciju xiju
(1)
i o j 0 u 1
n
K
 x
i  0 u 1
n
u
ij
1
j = 1,…,n
(2)
u
ij
1
i = 1,…,n
(3)
K
 x
j 0 u 1
n
x
i 0
u = 1,…,M
n
x  0
u
ip
j 0
n
n
j 0
i 0
n
n
j 1
i 0
u
pj
 d j ( xiju )  Cu
n
x
j 1
i 1
u = 1,…,M
(5)
u=1,…,M
(6)
i 0 j 0
u
0j
1
u = 1,…,M
(7)
u
i0
1
u=1,…,M
(8)
n
x
(4)
n
 s uj ( xiju )   tiju xiju  Tu
n
p = 1,…,n
u
P={( xij ) :
xiju 
 x
iQ jQ
u
ij
 Q  1, Q  N /{0}; B  2}
(9)
i = 1,…,n
P
j = 1,…,n
u=1,…,M
(10)
Azemmour municipality road network
• A snapshot of the
application main
document window
• Spatial reproduction of
application data on an
appropriate road network
Basic Application Navigation
The basic application view is navigated through a set of button
controls that is given below.
Arrow Tool. Depicts road names.
Zoom in & out Tools. They have a
typical GIS zooming in & out tool
function
Pan Tool. It has a typical GIS pan
tool function
Restore Tool. Restores original map
Presentation of MSW containers
in graphical mode on the application screen
MSW containers distribution
in Azemmour municipality
69 bins in total at the main
road network
Starting & Ending point of the vehicles route
Presentation of the basic problem parameters dialog
Solving the Vehicle Routing Problem
Presentation of all routes and containers in
graphical mode (total and each one route)
Software Results
• 4 trucks for the collection of bins
• 4 different routes
1st
route
2nd
route
3rd
route
4th
route
Presentation of each truck route separately –
1st Route and containers involved
Which truck?
1st Truck
Which route
should the truck
follow?
How many bins did
the truck collect?
20 containers
How much time
does the truck need
for the collection of
the bins?
2hr and 24 min
Presentation of each truck route separately –
2nd Route and containers involved
2nd Truck
Which route
should the truck
take?
18 containers in
1hour and 51min
Presentation of each truck route separately –
3rd Route and containers involved
3rd Truck
Which route
should the truck
take?
19 containers in
2hrs and 21min
Presentation of each truck route separately –
4th Route and containers involved
Which truck?
4th Truck
Which route
should the truck
take?
12 containers
1hr and 26min
Conclusions
• Design and implementation of a Vehicle Routing Problem (VRP) software
for the optimization of MSW collection and transfer for the case of
Azemmour municipality
– Minimizes the total distance traveled,
– Minimizes the total length of tours
– Minimizes costs (wages, fuel consumption etc)
• Possible to determine optimal routes by simply setting the appropriate
parameters
–
–
–
–
the maximum number of containers per truck
the mean speed of the vehicles/trucks
the shift period
the container service time
• Illustrates graphically and in tubular mode the routing information needed
– Number of routes and trucks needed
– The route that each trucks should take
– The total containers that each truck should collect and transfer as well as the
as associated time
Thank You