350-1295-1-PB

Fecha de recepción: Febrero 14 de 2013 • Fecha de aceptación: Abril 30 de 2013
INGENIARE, Universidad Libre-Barranquilla, Año 8, No. 14, pp. 13-29 • ISSN: 1909-2458
* Docente de Ingeniería Industrial Universidad Libre Barranquilla, Estudiante de Doctorado en Ingeniería Industrial,
Universidad del Norte. [email protected]
** Estudiante de Maestría en Ingeniería Industrial, Universidad del Norte. [email protected]
*** Estudiante de Doctorado en Ingeniería Industrial, Universidad del Norte. [email protected]
ABSTRACT
Verde Azul project Triple A is a set of activities to recover
from the source, recyclable material that will be duly pro-
cessed and sold to companies for reuse. The problem to
solve in this articles is to find a set of delivery routes sat-
isfying pick up requirements and giving minimal total cost.
In practice, we are minimizing the total distance travelled
from the scepter collection to customers.
Key words: Vehicle routing and Logistics distribution,
VRP.
RESUMEN
El proyecto Verde Azul es un conjunto de actividades para reco-
lectar desde la fuente material reciclable que será debidamente
procesado y vendido a las empresas para su reutilización. El pro-
blema a resolver en este artículo es hallar un conjunto de rutas de
entrega que satisfagan los requerimientos de recolección y que
generen un costo mínimo. En la práctica, se está minimizando la
distancia total recorrida desde el punto de procesamiento a los
clientes.
Palabras clave: Vehicle routing y Logistics distribution, VRP.
Vehicle Routing for Verde Azul Project Triple A
Ruteo de Vehículos para el Proyecto Verde Azul Triple A
Diego Fernando Suero Pérez*
Hugo Armando Caro Rivera**
José Luis López Prado***
14
I. INTRODUCTION
Triple A S.A. ESP has established recycling program Verde Azul, which is to perform a specialized gar-
bage collection, the program lies in giving a financial reward to companies and the residential sector to
make a separation of garbage: recyclables and organic material, which can mainly consists of the fol-
lowing materials: cardboard, glass, PET plastics, paper, newsprint and scrap.
The main purpose of the program is Verde Azul recycling increase user participation in the recycling
process through incentives such as discounts on the bill for the Triple A services according to the weight
of recyclables collected at time t.
Such, this type of project or policy is consistent with current trends. Reduction of the primary resource
use, pollutioen prevention, waste management and sustainable products policy became the focus points
of modern industrial societies and environmental policy efforts. Among these, waste management is an
essential part of any environmental management activities of production enterprises, recycling nowa-
days are also becoming more and more important

in all fields [1].
II. ROUTING (VRP PROBLEM)
The VRP belongs to the class NP-Hard, because the TSP (Travelling Salesman Problem) belongs to
this class, and is a particular case of VRP, when there is only one vehicle available, and there are no
capacity constraints and total distance traveled [2].
The required computational time and effort to solve this problem increases exponentially with respect
to the size of the problem, for example, the number of nodes to be visited by vehicles. For this type of
problems is often desirable to obtain approximate solutions, so they can be found fast enough and which
are sufficiently good to become useful in making decisions [3].
The problem identified Verde Azul program model corresponds to the family of vehicle routing problems
with capacity constraints in the fleet as a central repository and a set of customers with known demands
collection and delivery of certain goods homogeneous, they want to find a set of routes to meet the
demand of all customers at the lowest cost. All tours start and end in the central repository, which has a
fleet of vehicles, heterogeneous in terms of capacity and fixed cost associated with each and the vehicle
can not exceed its capacity [4].
A CVRP instance can easily be transformed to a VRPTW instance. This can for example be done by set-
ting all travel and service times to zero and all time windows to [0,0]. If the CVRP contains a route dura-
tion constraint then travel times and durations should be set as in the CVRP. All time windows (including
the ones at the end terminals) should be set to [0, D] where D is the route duration [5].
INGENIARE, Universidad Libre-Barranquilla, Año 8, No. 14, pp. 13-29 • ISSN: 1909-2458
VEHICLE ROUTING FOR VERDE AZUL PROJECT TRIPLE A
15
III. TRANSPORT OF MATERIALS (PL PROBLEM)
The method of work in the project is as follows:
1. Routing of trucks.
2. Upload and weighing of materials at the point of delivery, destination winery.
3. Upload and weighing of materials in the warehouse, bound for industry.
Picture 1. Verde Azul project vehicle
Source: By Authors
IV. GENERAL DESCRIPTION OF THE PROBLEM OF TRANSPORT
1. A set of m points of supply from which a product is shipped. The supply point i caters to the uttermost
if units.
2. A set of n demand points to which the product is shipped. The demand point j must receive at least
dj units of the product shipped.
3. Each unit produced at point i and sent to the supply demand point j incurs a variable cost cij.
Xij is the number of units shipped from supply point i to demand point j, then the general formulation of
a transportation problem is [6]:
INGENIARE, Universidad Libre-Barranquilla, Año 8, No. 14, pp. 13-29 • ISSN: 1909-2458
Diego Fernando Suero Pérez, Hugo Armando Caro Rivera, José Luis López Prado
16
Subject to:
When the total supply and total demand are equal restrictions must be active
Subject to:
Definition of variables
Demand: goods received daily volume (mass)
m = 1 number of collection points
n = number of demand points n = 96
Residential: 40 customers a day, with two vehicles
Industrial: 1-5 clients per day, with two vehicles
Xij = number of units collected demand point to the delivery point j i
Cij = cost of collecting a unit of demand point j to supply point i
Dj = demand at the point of demand j
T n = Timeout on each node or point of collection
Process data
Average distance between nodes = 1.44 Km
Average truck speed 50 km/h top speed of the truck 70 km/h
Average distance from the point of collection to each node 4.26 km
Customer costs: 172.640,56 pesos
Transportation costs: 16.573.493 pesos
INGENIARE, Universidad Libre-Barranquilla, Año 8, No. 14, pp. 13-29 • ISSN: 1909-2458
VEHICLE ROUTING FOR VERDE AZUL PROJECT TRIPLE A
17
V. SOLUTION FOR ROUTING PROBLEM
Where 0 is the storage cellar of the “Verde Azul”, and the other nodes correspond to the list presented
in the Excel file with addresses each.
For the model presented, we considered the following assumptions:
• All channels work both ways and have no mobility restrictions for trucks.
• The corners of the blocks are separated by a distance of 64 m/block.
• To get from point A to point B, the trucks would travel a maximum of two straight as to connect two
points on a Cartesian plane, without making diagonal or shortcuts.
• The service time at each node is constant and not optimize, unlike the transition time from one node
to another.
Table 1. Costs
Average distance per node 4,268666667
Payroll employees $ 1.000.000,00
Maintenance $ 8.000.000,00
Fuel consumption 25
Fuel price $ 7.850,00
Price for kilometer 314
Total daily fuel consumption $ 107.228,91
Fuel month $ 2.573.493,76
Total transportation costs months $ 16.573.493,76
Picture 2. Verde Azul project collection center
Source: By Authors
INGENIARE, Universidad Libre-Barranquilla, Año 8, No. 14, pp. 13-29 • ISSN: 1909-2458
Diego Fernando Suero Pérez, Hugo Armando Caro Rivera, José Luis López Prado
Source: By Authors
18
The distance obtained by performing the full path of the route that touches every node is not to possible
to obtain:
Picture 3. Result of GAMS procedure for PL problem
Source: By Authors
As it could be seen, the GAMS linear programming model didn’t produce any results due to the high
complexity and size that a 96-node routing problem implies for exact methods. The free version of
GAMS lacks the capacity to get any solution beyond its regular limits.
This fact supports the thesis that for NP-Hard problems, such as vehicle routing with vehicle limited
capacity as is Verde Azul Program’s situation, it might be more appropriate to start off with Heuristic or
Metaheuristic procedures, as exact methods like linear programming may result incapable of giving a
neighbor to optimal solution in a reasonable computational time, or sometimes it would even fail to give
a solution at all, such as the present case.
However thereby varying times (over longer distances or more time spent on trips) must be reasonably
low. As mentioned previously, this opens analysis of greatest accommodate other nature for future deliv-
eries may consider more realistic elements, for example, divide the route into two sub-aggregate routes
INGENIARE, Universidad Libre-Barranquilla, Año 8, No. 14, pp. 13-29 • ISSN: 1909-2458
VEHICLE ROUTING FOR VERDE AZUL PROJECT TRIPLE A
19
each assigned to one of two trucks, which the total distance traveled and the time decreases further. The
next most important aspect to be treated for the problem is the ability to free up space in the warehouse
to avoid extra accumulations of material, which will be seen in the next section.
VI. TRANSPORT PROBLEM (HEURISTIC METHOD)
The first thing to be done is to identify the type of routing problem that could describe in a better way
the Verde Azul project situation, which by a short-timed analysis may be concluded that the program fits
into a routing problem with capacity limitations and homogenous fleet (CVRP). Once identified the type
of transport problem, it was preceded with the design of the routes the trucks should travel in order to
accomplish node demand while minimizing total travelling distance (less distance means less costs).
To design this routes, the chosen method was: clustering first, routing next, which is a very effective
heuristic for cases like this one [7].
The method consists on basically the development of two phases. In the first one, clients are grouped
into clusters that would guarantee an enclosed region among which they could be visited with short
times due their close positions, and would also imply that all the nodes in the same cluster would be vis-
ited by the same vehicle during the same voyage following a pre-established route that would make part
of the final solution. Nodes demands and vehicle capacity are considered during this first stage in order
to assure that the vehicle does not have to return to the depot mid-voyage, but can visit all the nodes
at once. Then, during the second phase, after each cluster is created, a route is calculated in order to
match all the clients in the group to be visited with minimum traveled distance [8].
For this particular case, we employed the Sweeping Heuristic during the first phase, which implies no
complicated steps, reason thanks to which it was calculated without the use of specialized softwares nor
highly advanced computers. The method consists of three basic steps [9].
1. Locate all Customers Geographically
The project owners provided us with the information of 96 clients with their respective addresses, thanks
to which we were able to graph their relative positioning in Barranquilla. We will next show the Excel
graph that resulted from this.
On the graph, the blue spots are residential clients, green spots are industrial/commercial clients, and
the red spot is the Verde Azul warehouse.
2. Calculate the polar coordinates of all customers where the center is the depot and an arbitrary
customer is chosen to be at angle 0
To do this, we first converted absolute Cartesian coordinates to relative Cartesian coordinates, the Depot
being the 0,0 and the others would be positioned according to their distance in Carrera and called from
INGENIARE, Universidad Libre-Barranquilla, Año 8, No. 14, pp. 13-29 • ISSN: 1909-2458
Diego Fernando Suero Pérez, Hugo Armando Caro Rivera, José Luis López Prado
20
the depot. Then we converted said coordinates into polar coordinates by calculating:
r = x
2
+ y
2
and φ
= arctan
y
x
. The next table shows this calculations, r on Excel column “I” and phi on Excel column “L”
Graph 1. Node positions
Source: By Authors
Graph 2. Node positions
Source: By Authors
The table is not complete due to the fact that there were 96 nodes, so it would occupy a significant space
of several pages. A portion of it is shown as an example.
3. Draw a line from the depot, starting from the un-routed customer with smallest angle and be-
gin a sweep until the first vehicle’s capacity is met
In the previously shown table, this step was already done. Basically, we arranged the Angle Cells (Col-
INGENIARE, Universidad Libre-Barranquilla, Año 8, No. 14, pp. 13-29 • ISSN: 1909-2458
VEHICLE ROUTING FOR VERDE AZUL PROJECT TRIPLE A
21
umn “L”) in increasing order, and amplified the selection to all the corresponding cells, and we started
assigning the vehicles to the routes. Column “M”: “Camion” indicates the remaining capacity of a certain
truck after supplying the demand of the node it was just assigned to (Note that in this case, demands
means units (or Kilograms) to be picked up, since it is an inverse logistics program). Considering the
two vehicles the program has have a total capacity of 5 Ton (5.000 Kg), the remaining capacity was sub-
tracted with the amount of weigh the truck picked up at the visited node (Demand is shown on column B
“Promedio”). When the truck’s capacity was met, the truck was sent back to the depot to free space, and
the other truck was assigned to continue the route. In the normal version of this method, every time a
vehicle’s capacity is met, a new vehicle is created to generate a whole new route. In this case, we have
that there is a set number of trucks equal to two, so when a truck met its capacity, the second truck came
in, and when the second truck met its capacity, the first truck came in again, in a second route, and so
on. The number of trucks remained constant, but the number of routes realized by each truck increased.
A new graph with color-differentiated clusters was made, as seen next:
Graph 3. Node positions
Source: By Authors
The second phase of the Heuristic was developed with genetic algorithms taking as a base a Matlab
Demo designed to solve the Travelling Salesman Problem. We adapted the mentioned Demo to our
problem, by following these steps [10]:
a. Load the the file usborder.mat, which is a map sketch in which the clients’ coordinates will be in-
serted.
i. load(‘usborder.mat’,’x’,’y’,’xx’,’yy’);
ii. plot(x,y,’Color’,’red’); hold on;
b. The customers’ coordinates are introduced:
>> cities = 5;
>> locations = zeros(cities,2);
INGENIARE, Universidad Libre-Barranquilla, Año 8, No. 14, pp. 13-29 • ISSN: 1909-2458
Diego Fernando Suero Pérez, Hugo Armando Caro Rivera, José Luis López Prado
22
>> n = 1;
>> while (n <= cities)
switch n
case 1
xp=0.1;
yp=1.1;
locations (n,1)=xp;
locations (n,2)=yp;
n=n+1;
end
end
>> plot(locations(:,1),locations(:,2),’bo’);
c. Now it is calculated the distance matrix between all customers called cities.
distances = zeros(cities);
for count1=1:cities,
for count2=1:count1,
x1 = locations(count1,1);
y1 = locations(count1,2);
x2 = locations(count2,1);
y2 = locations(count2,2);
distances(count1,count2)=sqrt((x1-x2)^2+(y1-y2)^2);
distances(count2,count1)=distances(count1,count2);
end;
end;
d. Three necessary functions are created and registered. An individual in a population is an arranged
set, so, the population may easily be represented by a set of cells.
i. The function Custom Creation: It will create a set of cells, say P, where each element represents
an arranged set of the costumers as a permutation vector. Which means, de vendor will displace
himself in the specific order P.
>> type create_permutations.m
ii. The Crossover Function: It takes a series of cells from the population and returns a set of sibling
cells that result from it.
>> type crossover_permutation.m
iii. The custom Mutation Function: It takes an individual, which is an arranged cell of customers and
returns a mutated established order.
>> type mutate_permutation.m
e. A fitness function is created. This is the total distance traveled for an arranged set of clients. This
function needs the distance matrix to calculate total distance.
>> type traveling_salesman_fitness.m
INGENIARE, Universidad Libre-Barranquilla, Año 8, No. 14, pp. 13-29 • ISSN: 1909-2458
VEHICLE ROUTING FOR VERDE AZUL PROJECT TRIPLE A
23
f. A function to trace the customers’ routes is created:
>> %distances defined earlier
FitnessFcn = @(x) traveling_salesman_fitness(x,distances);
>> type traveling_salesman_plot.m
>> %locations defined earlier
my_plot = @(options,state,flag) traveling_salesman_plot(options, ...
state,flag,locations);
g. The Genetic Algorithm configurations are established. Then an options structure is created to indi-
cate a personalized data type and the population range.
>> options = gaoptimset(‘PopulationType’, ‘custom’, ’PopInitRange’, ...
[1;cities]);
h. The created functions are graphed, and also some stop conditions are setup:
>> options = gaoptimset(options,’CreationFcn’,@create_permutations, ...
‘CrossoverFcn’,@crossover_permutation, ...
‘MutationFcn’,@mutate_permutation, ...
‘PlotFcn’, my_plot, ...
‘Generations’,500,’PopulationSize’,60, ...
‘StallGenLimit’,200,’Vectorized’,’on’);
i. The Genetic Algorithm is ran and if desired, a new iteration can be done by repeating the code.
>> numberOfVariables = cities;
[x,fval,reason,output] = ga(FitnessFcn,numberOfVariables,options)
Next, we will share the obtained results when the developed genetic algorithms were ran. Note, the
Demo brough a U.S.A. map sketch that we did not find out how to remove, yet, the problem we’re
here working takes place at Barranquilla, Colombia. The nodes have obviously no relationships in
scare nor position with the background sketch.
First: The route corresponding to Truck 1 – Route 1. The following two images show the obtained
route by the genetic algorithm metaheuristic, which was the best found route (found after iteration
number 10) out of 30 iterations that were ran for this case.
The total distance for this route was:
fval = 21.232 Km
Next, we calculated the route for Truck 2 - Route 1. This time, out of 30 iterations done, the best route
was found at the 7
th
iteration.
INGENIARE, Universidad Libre-Barranquilla, Año 8, No. 14, pp. 13-29 • ISSN: 1909-2458
Diego Fernando Suero Pérez, Hugo Armando Caro Rivera, José Luis López Prado
24
Figure 1. Obtained Route for Truck 1- Cluster 1. Image 1
Source: By Authors
Figure 2. Amplified image for Obtained Route of Truck 1 – Route 1
Source: By Authors
INGENIARE, Universidad Libre-Barranquilla, Año 8, No. 14, pp. 13-29 • ISSN: 1909-2458
VEHICLE ROUTING FOR VERDE AZUL PROJECT TRIPLE A
25
Figure 3. Route Obtained from the Genetic Algorith for the Cluster of Truck 2 - Route 1
Source: By Authors
Figure 4. Zoom of Route Obtained from the Genetic Algorith for the Cluster of Truck 2 - Route 1
Source: By Authors
INGENIARE, Universidad Libre-Barranquilla, Año 8, No. 14, pp. 13-29 • ISSN: 1909-2458
Diego Fernando Suero Pérez, Hugo Armando Caro Rivera, José Luis López Prado
26
The distance for the complete path was:
fval = 19.397 Km
Next, will be shown the results for the route calculated for Truck 1, Route 2. 30 Iterations were ran, and
this one shown was the one found at the 28
th
iteration.
Figure 5. View of Truck 2 - Route 1 with higher zoom
Source: By Authors
Figure 6. Obtained Route for the Traveling of Truck 1’s second cluster clients
Source: By Authors
INGENIARE, Universidad Libre-Barranquilla, Año 8, No. 14, pp. 13-29 • ISSN: 1909-2458
VEHICLE ROUTING FOR VERDE AZUL PROJECT TRIPLE A
27
Figure 7. Amplified Image of Truck 1, Route 2
Source: By Authors
Figure 8. More clear view of the route generated for Truck 1 on it is second travel
Source: By Authors
INGENIARE, Universidad Libre-Barranquilla, Año 8, No. 14, pp. 13-29 • ISSN: 1909-2458
Diego Fernando Suero Pérez, Hugo Armando Caro Rivera, José Luis López Prado
28
Total traveled distance:
fval = 17.266 Km.
Finally, we have the Cluster for Truck 2’s second Route.
Figure 9. Route for Truck 2, Travel 2
Source: By Authors
As it may be seen, the only nodes remaining to be visited after the first 3 routes, were the only 4 that are
seen on the picture. This was due to the fact that the Clustering Procedure was followed strictly without
modifications, but seeing how much capacity was left on Truck 2 by the second route, it may be inferred
that certain post-processing adjustments may be tried in a search for even better solutions. Let’s re-
member that Metaheuristics are good at finding good solutions at reasonable computational times even
for big problems, but they don’t necessarily find the optimum, so there’s always a chance they can be
fatherly improved.
The traveled distance was:
fval = 8.273 Km
So taking into account the 4 routes, travelled by the two available trucks, would mean that all nodes
would be visited with a total distance of:
Total distance = (21.232 + 19.397 + 17.266 + 8.273) Km = 66.168 Km
VII. CONCLUSIONS
• This kind of NP-Hard problems, such as vehicle routing with vehicle limited capacity, it might be
INGENIARE, Universidad Libre-Barranquilla, Año 8, No. 14, pp. 13-29 • ISSN: 1909-2458
VEHICLE ROUTING FOR VERDE AZUL PROJECT TRIPLE A
29
more appropriate to start off with Heuristic or Metaheuristic procedures for the complex of the prob-
lem and the time for wait a result.
• Sadly, this result may not be compared to the one given by GAMS’ Linear Programming Model,
due to the size and complexity of the problem, which didn’t allow GAMS to give a result precisely
because the model exceeded the available version at Universidad del Norte, Barranquilla.
• Metaheuristics are excellent for finding fine solutions at reasonable computational times even for
big problems, but they do not necessarily find the optimum, so there is always a chance they can be
furtherly improved.
• The total distance was 66.168 Km. Using an adaptation of the Matlab Sofware with the sales man
route problem, it will be useful for the Verde Azul program because they does not have any rout plan-
ning.
VIII. REFERENCES
[1] K. Logozar, G. Radonjic, & M. Bastic, “Incorporation of reverse logistics model into in-plant recy-
cling process: A case of aluminium industry. Resourser”, Conservation and Recycling, n°. 49, pp.
49-67, 2006.
[2] G. Laporte, “What You Should Know about the Vehicle Routing Problem”, Naval Research Logis-
tics, n°. 8, pp. 811-819, 2007.
[3] A. Lüer, M. Benavente, J. Bustos, & B. Venegas, El problema de rutas de vehículos: Extensio-
nes y métodos de resolución, estado del arte. En U. d. Frontera (Ed.), Workshop Internacional
EIG2009. Chile: Departamento de Ingeniería de Sistemas, 2009.
[4] A. Fernández (23 de noviembre de 2012). Obtenido de Problema de enrutamiento de vehícu-
los con recogida y entrega simultánea considerando una flota heterogénea. http://www.matcom.
uh.cu/postgrd/Maestria_Matematica/serieInterna/OPAlina2010.pdf
[5] D. Pisinger y S. Ropke (23 de noviembre de 2012). A general heuristic for vehicle routing prob-
lems. Obtenido de http://www.diku.dk/~sropke/Papers/GeneralVRP_TechRep.pdf
[6] W. Winston, Investigación de operaciones, aplicaciones y algoritmos. México: Thomson, 2005.
[7] V. Pillac, M. Gendreau, C. Guéret, y A. Medaglia, A review of dynamic vehicle routing problem.
European Journal of Operational Research, 2012.
[8] J. Renaud, y F. Boctor, A sweep-based algorithm for the fleet size and mix. European Journal of
Operational Research, 2001.
[9] M. Daza, J. Montoya y F. Narducci, “Resolución del problema de enrutamiento de vehículos con
limitaciones de capacidad utilizando un procedimiento Metaheurístico de dos fases”, Revista EIA,
2009.
[10] J. Kirk (23 de noviembre de 2012). Traveling Salesman Problem - Genetic Algorithm. Obtenido
de MATLAB CENTRAL. http://www.mathworks.com/matlabcentral/fileexchange/13680-traveling-
salesman-problem-genetic-algorithm
INGENIARE, Universidad Libre-Barranquilla, Año 8, No. 14, pp. 13-29 • ISSN: 1909-2458
Diego Fernando Suero Pérez, Hugo Armando Caro Rivera, José Luis López Prado