ISSN-L: 0798-1015 • eISSN: 2739-0071 (En línea)
https://www.revistaespacios.com Pag. 1
Vol. 42 (16) 2021 • Art. 1
Recibido/Received: 02/04/2021 • Aprobado/Approved: 15/08/2021 • Publicado/Published: 30/08/2021
DOI: 10.48082/espacios-a21v42n16p01
Heuristic algorithm based on Ant Colony Optimization for
the Capacitated Location-Routing problem with
Homogeneous Fleet
Algoritmo heurístico basado en optimización para el problema de localización y ruteo con
flota homogenea
GATICA, Gustavo
1
ESCOBAR, John W.
2
LINFATI, Rodrigo
3
Abstract
This paper considers the Capacitated Location-Routing Problem with Homogeneous Fleet (CLRP). The
objective is to minimize the sum of the open depots' costs, the costs for the used vehicles, and the costs
associated with the distances traveled. A metaheuristic algorithm of two phases for the CLRP is
proposed. In the first phase, customers establish the clusters to be subsequently heuristically assigned
to the depots. In the second phase, the initial routes are improved using an algorithm based on Ant
Colony. The obtained results show the efficiency of the proposed approach.
Key words: capacitated location routing, ant colony, metaheuristic.
Resumen
Este artículo considera el problema de localización y ruteo capacitado con flota homogénea (CLRP). El
objetivo es minimizar la suma de los costos de los depósitos abiertos, los costos de los vehículos usados
y los costos asociados con las distancias recorridas. Se propone un algoritmo metaheurístico de dos
fases para el CLRP. En la primera fase, los clústeres son establecidos por los clientes para luego ser
asignados heurísticamente a los depósitos. En la segunda fase, se mejoran las rutas iniciales mediante
un algoritmo basado en Colonia de Hormigas. Los resultados obtenidos muestran la eficiencia del
algoritmo propuesto.
Palabras clave: localizacion y ruteo capacitado, colonia de hormigas, metaheurística
1. Introduction
The logistic function, "oriented to the customer," requires that the supply departments fulfill diverse
requirements. In this way, it is necessary to apply specialized techniques to support customer service (i Cos & De
Navascués, 1998). The logistics include integrating different activities to reduce resources and costs through
1
Full Professor. Faculty of Engineering. Universidad Andres Bello. Chile. Contact e-mail. ggatica@unab.cl
2
Full Professor. Department of Accouting and Finance. Universidad del Valle. Colombia. Contact e-mail. john.wilmer.escobar@correounivalle.edu.co
3
Full Professor. Department of Industrial Engineering. Universidad del del Bío-Bío. Chile. Contact e-mail. rlinfati@ubiobio.cl
ISSN-L: 0798-1015 • eISSN: 2739-0071 (En línea) – Revista Espacios – Vol. 42, Nº 16, Año 2021
GATICA, Gustavo et al. «Heuristic algorithm based on Ant Colony Optimization for the Capacitated Location-
Routing problem with Homogeneous Fleet»
Pag. 2
available solutions (García, 2016). The problem of location routing (LRP) is critical in logistics because it
establishes criteria regarding the opening of depots and customers' assignment for a later routing. The problem
presents externalities considering social, environmental, and financial activities and economic impacts within the
transport of goods in the urban area. The problems from the depots' location, however, the location of the
depots and an efficient routing is relevant and necessary to optimize for a better supply chain (Luna López, 2015;
Vasquez Delgado, 2012, Escobar & Linfati, 2012; Farkavcova et al., 2018).
The problem of location routing is NP-Hard (Garey & Johnson, 1979) because when determining the
opening of facilities, it simultaneously contributes to the problem of installation location (FLP) and
subsequent vehicle routing (VRP) (Tokgoz & Trafalis, 2014). Furthermore, for the solution of this
problem, different approaches have been suggested through various algorithms; for example, exact
methods: Baldacci et al. (2011), which solves the problem using strategies based on the well-known
“Set Partition Problem”; Belenguer et al. (2011), and Contardo et al. (2010) with an exact approach
based on the Branch-and-Cut algorithm. Harks et al. (2013) combined algorithms and lower limits for
different relaxations allow applying cross-docking. Laporte et al. (1989) suggest a linear programming
model optimally solved for small instances (less than 50 customers).
Duhamel et al. (2010) proposed heuristic methods based on greedy search (GRASP) for solving the LRP. Wu et al.
(2002) suggested a method based on the decomposition of the problem into two subproblems: location and
routing problems. Finally, metaheuristic algorithms have been proposed by Caballero et al. (2007), which show
a real application of the problem in Andalucia, Spain. Algorithms based on Tabu search have been proposed by
Linfati et al. (2014), which use an approach called granular tabu search to solve the location-routing problem
heterogeneous fleet. Prins et al. (2006a) applied a GRASP based on an extended and random version of the Clarke
& Wright (1964) algorithm for the first and tabu search heuristic in the second phase. In this way, the article
contributes to the state of the art of the LRP by employing a metaheuristic based on Ant Colony Optimization
(ACO), with a performance equivalent to GRASP, MA|PM, and hybrid metaheuristics using the problem's
benchmarks.
The literature review of the LRP considers characteristics of the distribution and logistics areas being applied in
diverse applications such as garbage collection, vendor routing, location of train lines and subways, passenger
transport, merchandise distribution, mail collection, and distribution, among others (Toro et al., 2017). However,
few papers have been published dealing with the location routing problem efficiently satisfying the whole
customer network and minimizing the total logistic cost (Toth & Vigo, 2002).
The solutions regarding the location and routing vehicle problem have been studied since the last decade,
generally solved by exact and heuristic algorithms. The VRP concept was introduced by Dantzig & Ramser (1959).
It was initially called the "Trucking Dispatching Problem," which is similar to the following VRP. Later, Clarke &
Wright (1964) formalized the classical Vehicle Routing Problem (Classic VRP). Thereby, over the years, several
researchers consider different variants for the problem of VPR. First, the researchers analyzed the cost of routing
for a facility's location (Webb, 1968). In this work, a cost function for each potential facility might not accurately
represent the facility location problem. Second, Beardwood et al. (1959) suggested an approximate solution to
the length of the route if the customers are uniformly distributed in a square. Finally, Watson-Gandy & Dohrn
(1973) use a heuristic procedure to solve a location routing by considering multi-depots such as Tuzun & Burke
(1999).
ISSN-L: 0798-1015 • eISSN: 2739-0071 (En línea) – Revista Espacios – Vol. 42, Nº 16, Año 2021
GATICA, Gustavo et al. «Heuristic algorithm based on Ant Colony Optimization for the Capacitated Location-
Routing problem with Homogeneous Fleet»
Pag. 3
2. Methodology
2.1. Problem Formulation
The Capacitated Location Routing Problem (CLRP) could be described by a complete graph problem as follows
Escobar et al. (2015): Let be
𝐺" = " (𝑉, 𝐸)"
a complete graph non-directed, where
𝑉" = " {1, … , 𝑚 + 𝑛}
is the set of
nodes and
𝐸
is the set of arcs that connects each pair of nodes
𝑉
. The set of vertices is divided into two subsets,
vertices
𝐼" = "1, … , 𝑚
that corresponds to the potential depots and the other subset
𝐽" = "𝑚 + 1, … , 𝑚 + 𝑛
with
customers. There is a cost of trip
𝑐
!"
non-negative associated with each arc
(𝑖, 𝑗) " ∈ "𝐸
. Each depot
𝑖" ∈ "𝐼
have a
capacity
𝑊
!
and a fixed cost of opening
𝑂
!
. Each customer
𝑗" ∈ "𝐽
has a
𝑑
"
demand that the homogenous fleet of
vehicles
"𝐾
must fulfill, each with
𝑄
capacity, that are available in each depot
𝑖" ∈ "𝑉
. Each vehicle, when used
by one depot, performs a route that generates a fixed cost
𝐹
!
. The CLRP considers the following constraints: i)
each route must begin and end in the same depot; ii) the total cargo must not exceed the capacity of the vehicle
𝑄
; iii) each customer must be visited exactly once by a single route; iv) the total load of the assigned routes to
one depot must be adjusted to the capacity of the depot
𝑊
!
; and finally, v) the flow between depots are not
allowed. The problem's objective is to determine which depots must be opened and which routes must be
performed to minimize the total cost.
According to Prins et al. (2007), the formulation of the mathematical model of three index uses the following
binary variables: y
i
= 1 if the i depot is open, f
ij
= 1 if the customer j is assigned to the depot i, and finally x
ijk
= 1 if
the (i,j) arc is visited from i to j in the performed route by the vehicle k ∈ K. Then, the problem could be formulated
as follows:
(1)
Subject to:
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
The objective function (1) considers the sum of the open depots' costs, the trip costs associated with the visited
arcs by the routes, and the fixed costs associated with the used vehicles. Constraints (2) guarantee that each
customer belongs exactly to a route and only has one predecessor in its route sequence. Constraints (3) and (8)
are associated with the depot's capacities and the customer. Constraints (4) and (5) ensure each route's
continuity and determine that each route begins and ends in the same depot. Constraints (6) consider the
!"#$ %
&
'
(
)
(
(*+,
-
&& &
.
(/
0*1/*2(*2+
3
(/0
-
& &&
4
(
/*5(*,0*1+
3
(/0+
!!
𝑥
𝑖𝑗𝑘
= 1((((((((∀𝑗 ∈ 𝐽
𝑖∈𝑉𝑘∈𝐾
((
!!
𝑑
𝑗
𝑥
𝑖𝑗𝑘
≤ 𝑄))))))∀𝑘 ∈ 𝐾
𝑖∈𝑉𝑗∈𝐽
))
!
𝑥
𝑖𝑗𝑘
−'
!
𝑥
𝑗𝑖𝑘
𝑗∈𝑉
= 0'''''''∀𝑖 ∈ 𝑉,∀𝑘
𝑗∈𝑉
∈ 𝐾
!!
𝑥
𝑖𝑗𝑘
= 1(((((((((∀𝑘 ∈ 𝐾((((((((((((((((((((((((((((((((((((((((((((((
𝑗∈𝐽𝑖∈𝐼
!!
𝑥
𝑖𝑗𝑘
≤
|
𝑆
|
− 1+++++++∀𝑆 ⊆ 𝐽,
𝑗 ∈𝑆𝑖∈𝑆
+∀𝑘 ∈ 𝐾
!
𝑥
𝑖𝑢𝑘
+'
!
𝑥
𝑢𝑗𝑘
𝑢∈𝑉\{𝑗}
≤ 1 +𝑓
𝑖𝑗
'''' ''''∀𝑖 ∈ 𝐼,∀𝑗
𝑢∈𝐽
∈ 𝐽,∀𝑘 ∈ 𝐾'
!
𝑑
𝑗
𝑓
𝑖𝑗
≤ 𝑊
𝑖
𝑦
𝑖
))))))∀𝑖 ∈ 𝐼))))))))) ))))) ))))) )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) ))))) ))))) )))))))))))
𝑗∈𝐽
𝑥
𝑖𝑗𝑘
∈
{
0,1
}
+++++++∀𝑖 ∈ 𝑉, ∀𝑗 ∈ 𝑉,∀𝑘 ∈ 𝐾
𝑦
𝑖
∈
{
0,1
}
)))))))))∀𝑖 ∈ 𝐼)
𝑓
𝑖𝑗
∈
{
0,1
}
*********∀𝑖 ∈ 𝐼, ∀𝑗 ∈ 𝑉
ISSN-L: 0798-1015 • eISSN: 2739-0071 (En línea) – Revista Espacios – Vol. 42, Nº 16, Año 2021
GATICA, Gustavo et al. «Heuristic algorithm based on Ant Colony Optimization for the Capacitated Location-
Routing problem with Homogeneous Fleet»
Pag. 4
elimination of sub tour. Constraints (7) specify that a customer must be assigned to a depot only if there is a
route that joins them. Finally, constraints (9), (10), and (11) represent the integrality of the variables.
A solution of the CLRP must indicate the depots to be opened, the costumers to be assigned to each open depot
(each customer must be assigned to only one depot), and the sequence of customers to satisfy their demand.
The proposed algorithm uses two phases. The initial phase allows the opening of the best depots and considering
some initial routes. Such routes are improved in the final phase by applying a metaheuristic algorithm based on
Ant Colony. The suggested phases are described as follows.
2.2. Initial Heuristic Procedure
The initial procedure is implemented according to Escobar & Linfati (2012) work, where the algorithm can obtain
high-quality solutions with reduced computational times. This procedure combines exact and heuristic methods.
The following steps are performed to generate the initial solution:
Step 1: Construct a TSP tour with all the customers using the library Lin-Kernighan (LKH) (Helsgaun, 2000)
available in Stützle & Ruiz (2018).
Step 2: The giant TSP tour is split into many customer groups, called clusters. The criterion to obtain the customer
group is the vehicle capacity. Therefore, the first customer is determined to be assigned to a cluster
corresponding to a vehicle
k
"
∈
"
K.
Then, one by one of the new customers are added following the TSP trip. Once
the
k
"
∈
"
K
vehicle's capacity is completed, the process restarts until all the customers are assigned to one
cluster. This process selects the best customer assignment changing the initial customer iteratively to select the
clusters.
Step 3: For each depot
i
"and each cluster
g
"
∈
"
G
, the LKH procedure is applied to find the corresponding TSP
tour. In this way, the route length (
l
#$
) is obtained when depot
i
is assigned to cluster
g
.
Step 4: The depots are assigned to the clusters solving the corresponding Single Source Capacitated Plant
Location Problem (FLPS). The depots to be opened and the TSP tours assigned to each depot are determined.
The FLPS model is the following (Barceló & Casanovas, 1984):
(12)
Subject to:
(13)
(14)
(15)
(16)
The objective function (12) corresponds to the sum of the total costs of depots' opening and the costs associated
with covered distance when the depots are assigned to the clusters. The constraints (13) guarantee that each
customer group being strictly assigned to only one depot. Constraints (14) determine the capacity of each one
of the depots. Finally, constraints (15) and (16) determine the binary variables group used in the model. Note
that the initial procedure is repeated n times, considering each customer as a start to split the TSP tour. In this
procedure, the best feasible solution (best objective function) is kept (Linfati et al., 2014).
!"#$ % &'
(
)
(
(*+,
-&&.
(/
0
(/
/*1(*,
!𝑋
𝑖𝑔
= 1''''''∀𝑔∈ 𝐺'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' ''''''''''''''''''''''''''
𝑖∈𝐼
!𝑑𝑐
𝑔
𝑋
𝑖𝑔
≤𝑊
𝑖
𝑦
𝑖
******∀𝑖∈ 𝐼*************************************************************************************************
𝑔∈𝐺
𝑥
𝑖𝑔
∈
{
0,1
}
*********∀𝑖 ∈ 𝐼, ∀𝑔 ∈ 𝐺
𝑦
𝑖
∈
{
0,1
}
)))))))))∀𝑖 ∈ 𝐼
ISSN-L: 0798-1015 • eISSN: 2739-0071 (En línea) – Revista Espacios – Vol. 42, Nº 16, Año 2021
GATICA, Gustavo et al. «Heuristic algorithm based on Ant Colony Optimization for the Capacitated Location-
Routing problem with Homogeneous Fleet»
Pag. 5
2.3. Improvement Phase Based on Ant Colony
Biologically, ants explore randomly in their environment, from their nest to the hunt for food. Each time the ants
explore, they depot a constant amount of pheromones, a chemical that other ants could smell and follow. Since
ants are blind, this trace helps them move from one point to another under efficient routes, finding the shorter
trips between the nest and the food (Negrotto, 2015). The main reason for their success in the battle for survival
is that the ants cooperate (Dorigo & Gambardella, 1997). The research of the ants' collective performance covers
the analysis of their behavior when they transport and forage for food. The Ant Colony is an optimization
algorithm based on swarm intelligence, imitate the behavior of an ant colony that hunts for food. The Algorithm
was suggested by Dorigo (1992). In this investigation, each movement from one node to another considers the
probabilistic artificial transition rule, defined by the probability that the ant
𝑘
, located in the customer
𝑟
, decides
to move towards the customer
𝑢
(Dorigo, 1992).
(17)
Where:
•
𝜏(𝑟, 𝑢 )
: is the pheromone from arc
"𝑟
to
𝑢
.
•
𝜂(𝑟, 𝑢):
is the heuristic information from the arc
𝑟
to
𝑢
, also pointed out as 1.0 divided the distance
between the customers.
•
𝛼
and
𝛽
are weights that set the relative importance between pheromone levels and the local search
criterion.
Once all the ants have constructed a complete trail from the initial node to the destination node, all the internal
bonds (in case of existing) are eliminated, and every ant follows the constructed trail again to the initial node in
a deterministic way (Colorni et al., 1992). In this process, it is deposited a specific amount of pheromone
∆𝜏
!"
%
in
each connection.
(18)
Being Q, a constant
𝐿
%
(𝑡)
is the total length of the traveled arcs by the ant
𝒌
. The total value of pheromones for
a single and after a tour (Colorni et al., 1992). In this way, the intensity of the trails is updated with the following
formula:
(19)
Thus, the pheromone levels are updated in the arcs of TSP. Finally, it is considered the evaporation of pheromone
as a way to discard poor trails (Colorni et al., 1992). The evaporation is modeled by the equation:
(20)
It is important to consider that
0" < "𝜌" < 1
. The iterative process among each Hamiltonian cycle found by the
ant process is depicted in Figure 1.
Algorithm 1
Pseudocode algorithm ant colony for TSP
𝜌 = #
[
𝜏
(
r,u
)]
𝛼
∗ #
[
η
(
r, u
)]
𝛽
#
∑ [
𝜏
(
r,u
)]
𝛼
∗ #
[
η
(
r,u
)]
𝛽
𝑘
##
∆𝜏
𝑖𝑗
𝑘
&
(
𝑡
)
=
𝑄&
𝐿
𝐾
(𝑡)
&&&&&&&
𝜏
𝑖𝑗
𝑘
%
(
𝑡
)
=% 𝜏
𝑖𝑗
𝑘
%
(
𝑡
)
+ %∆𝜏
𝑖𝑗
𝑘
%
(
𝑡
)
%%%
𝜏
𝑖𝑗
𝑘
%
(
𝑡
)
= 𝜏
𝑖𝑗
𝑘
%
(
𝑡
)
∗
(
%1 − 𝜌
)
ISSN-L: 0798-1015 • eISSN: 2739-0071 (En línea) – Revista Espacios – Vol. 42, Nº 16, Año 2021
GATICA, Gustavo et al. «Heuristic algorithm based on Ant Colony Optimization for the Capacitated Location-
Routing problem with Homogeneous Fleet»
Pag. 6
1: Input: NNodes, Parameters ACO (
𝛼
,
𝛽
,
𝜌
,
𝑄
, MaxIterations).
2: Output: TspTour.
3: Begin
4: Current Iteration = 0
5: While Current Iteration < NNodes * MaxIterations do
6: While does not exist solution do
7: Select the next node for each ant.
8: End While
9: Random Diversification ()
10: Update Pheromone by considering parameters
𝛼
and
𝛽
()
11: Current Iteration ++;
12: End While
13: TspTour = Tour of lower cost found by the ants.
14: End
We have considered three additional parameters to proposed approach ACO:
•
𝑁𝑁𝑜𝑑𝑒𝑠
: Amount of nodes that belong to TSP tour.
•
𝑀𝑎𝑥𝐼𝑡𝑒𝑟𝑎𝑡𝑖𝑜𝑛𝑠
: Parameters to determine the number of ACO iterations.
•
𝑇𝑠𝑝𝑇𝑜𝑢𝑟
: Solution of TSP tour indicating the order of visit to the node.
2.4. Solution Improvement
Initially, to improve each route, a TSP-ACO is applied. Then, local search procedures are applied, such as insertion
and swap:
1. Insertion: A customer is removed from its current position, and it is inserted in another position in the
same route or another route.
2. Swap: Exchange of two customers belonging to the same route or different routes.
The integration of the Ant Colony Optimization meta-heuristic and the Insertion and Swap local search are
depicted in the Figure 2.
Algorithm 2
Pseudocode algorithm improvement phase
1: Begin
2: it = 0
3: While it < NumIT do
4: For each i in the solution
5: ACO-TSP(route i)
6: End for
7: Local search - Insertion
8: Local search - Swap
9: it ++
10: End While
11: End
3. Results
3.1. Calibration of Parameters
The ACO algorithm uses four parameters:
𝛼
,
𝛽
,
𝜌
,
𝑄
. If
𝛼
"
= "0
, the closest costumers are the ones with more
probability to be chosen (the classic algorithm of the gradient with different departure points). Thus, it is chosen
ISSN-L: 0798-1015 • eISSN: 2739-0071 (En línea) – Revista Espacios – Vol. 42, Nº 16, Año 2021
GATICA, Gustavo et al. «Heuristic algorithm based on Ant Colony Optimization for the Capacitated Location-
Routing problem with Homogeneous Fleet»
Pag. 7
the value of
𝛼
"
= "1
, following the algorithms' obtained information for similar problems that can be found in
the literature (Colorni et al., 1992). If
𝛽
"
= "0
, only the pheromone levels are taken into account, which implies
very poor results, especially if
𝛼 > "1
is a stagnation, where all the ants follow the same path converging to
suboptimal solutions (Dorigo et al., 1996). Therefore, the literature's extremes (2 and 5) are chosen, besides
𝛽
"
=
"8
, to identify what happens when this value is chosen;
𝛽"
might be an arbitrary value. For
𝜌
, the set values are
between
0
and
1
, and this is the parameter that considers the biggest changes within the bibliographic review
of TSP-ACO (Asmar et al., 2005; Dorigo & Stützle, 2019; Mehrjerdi & Nadizadeh, 2013). In consequence the
values
𝜌
"
= " {0.2, 0.5, 0.8}
are chosen.
Table 1
Parameters ACO
ACO algorithm
α
β
Ρ
m
τ0
AS
1
2 to 5
0.5
n
m/C
nn
EAS
1
2 to 5
0.5
n
(e +m)/ρ C
n
ASrank
1
2 to 5
0.1
n
0.5r(r – 1) / ρ C
n
MMAS
1
2 to 5
0.02
n
1 / ρ C
n
ACS
-
2 to 5
0.1
n
1 / n C
n
Source: Dorigo 1992; Dorigo et al., 1996
For MaxIterations, 5 and 30 are considered, and for NumIT 10 and 50. These parameters directly influence the
solution's computational time; therefore, the upper ends were chosen according to the criterion of responding
within short computing times. On the other hand, the lower ends were chosen according to the criterion of
responding within a low computational time without affecting the solution's quality. In this way, it is proved only
with both ends for the parameters combination.
Table 2
Calibration of Parameters
Parameters
Values
α
1
Β
2
5
8
ρ
0,2
0,5
0,8
Q
1000000
MaxIteraciones
5
30
NumIT
10
50
Source: Authors
3.2. Obtained Results
Regarding the computational experiment, the best results are generated with the combination of
parameters
𝛽
"
= "2"
and
𝜌
"
= " {0.2, 0.5}
. Therefore, the analysis concludes that these values are appropriate to
perform the test of the proposed algorithm. Furthermore, it is verified and discard the value of
𝛽
"
> "5
pointed
out in the literature of Coloni et al., 1992).
The obtained results of the run tests for each of the following instances of the test are presented (Barreto, 2004;
Tuzun & Burke, 1999):
ISSN-L: 0798-1015 • eISSN: 2739-0071 (En línea) – Revista Espacios – Vol. 42, Nº 16, Año 2021
GATICA, Gustavo et al. «Heuristic algorithm based on Ant Colony Optimization for the Capacitated Location-
Routing problem with Homogeneous Fleet»
Pag. 8
Table 3
Instances of Test
Source
Instances
Depots
Customers
Barreto (2004)
Christofides69-50x5
5
50
Christofides69-75x10
10
75
Christofides69-100x10
10
100
Daskin95-88x8
8
88
Daskin95-150x10
10
150
Min92-134x8
8
134
Tuzun & Burke (1999)
111112
10
100
111122
20
100
132222
20
150
123222
20
200
Source: Owner
The proposed algorithm (HACO) has been compared with the following heuristics published for the CLRP: GRASP
(Prins et al., 2006b), MA|PM (Prins et al., 2006a), LRGTS (Prins et al., 2007), GRASP+ELS (Duhamel et al., 2010),
SALRP (Vincent et al., 2010), 2-Phase HGTS (Escobar et al., 2013) and GSA (Escobar & Linfati, 2012). The reported
results for GRASP, MA|PM, LRGTS, SALRP, and 2-Phase HGTS correspond to only one run of the associated
algorithm. Finally, GRASP + ELS executed five times with five random seeds, reports the best result of the runs
with their computational time. Table 4 and 5 shows the results.
Table 4
Comparison Instances Barreto (2004)
Source: Owner
ISSN-L: 0798-1015 • eISSN: 2739-0071 (En línea) – Revista Espacios – Vol. 42, Nº 16, Año 2021
GATICA, Gustavo et al. «Heuristic algorithm based on Ant Colony Optimization for the Capacitated Location-
Routing problem with Homogeneous Fleet»
Pag. 9
Table 5
Comparison Instances Tuzun & Burke (1999)
Source: Owner
We have applied the following notation for the tables:
Instance: Name of the instance;
Cost: Cost of the solution obtained by each method (in only one run or the best run);
BR: Cost of the best result found by the considered algorithm;
Gap BR: Percentage variation of the cost found by each algorithm concerning the BR value;
CPU time: Execution time in seconds in the used CPU for each algorithm;
Average: Average of the column values;
CPU: CPU used by each algorithm.
Therefore, it can be noticed that in the Gap BR column, the suggested algorithm obtains good solutions compared
to the algorithms of the literature. It is displayed that such an algorithm gives better results than other
algorithms. On the other hand, it might be considered that the algorithm gives the solution in a reduced
computational time (CPU time).
Mainly, the average difference of the objective functions' values, compared to the cost of the best result, is
analyzed (Average column). In this way, the average difference is obtained, identifying a reduced average
difference concerning the algorithms' best result. Consequently, feasibility in the algorithm is shown.
Although the best results of the literature were not achieved, the ACO algorithms applied to the LRP prove to be
efficient in quality versus computational time, with only an average gap of 2.258%.
4. Conclusions
We proposed a metaheuristic algorithm for the CLRP based on Ant Colony Optimization. When the ACO algorithm
gave different feasible solutions, it searched for new alternatives for the LRP problem. Therefore, since the
algorithm is stochastic, it is concluded that it allowed increasing the diversification of solutions and intensifying
the best solutions.
ISSN-L: 0798-1015 • eISSN: 2739-0071 (En línea) – Revista Espacios – Vol. 42, Nº 16, Año 2021
GATICA, Gustavo et al. «Heuristic algorithm based on Ant Colony Optimization for the Capacitated Location-
Routing problem with Homogeneous Fleet»
Pag. 10
The future researches that might be presented to solve the Location Routing Problem with ACO following the
same investigation line are:
1. Develop the use of multiple ant colonies.
2. Implement new strategies to improve the algorithm, monitoring the pheromone concentration in the
different global and local updating strategies.
References
Asmar, D., Elshamli, A., & Areibi, S. (2005). A comparative assessment of ACO algorithms within a TSP
environment. Dynamics of Continous Discrete and Impulsive Systems-Series B-Applications &
Algorithms, 1, 462-467.
Baldacci, R., Mingozzi, A., & Wolfler Calvo, R. (2011). An exact method for the capacitated location-routing
problem. Operations research, 59(5), 1284-1296.
Barceló, J., & Casanovas, J. (1984). A heuristic Lagrangean algorithm for the capacitated plant location
problem. European Journal of Operational Research, 15(2), 212-226.
Barreto, S. D. S. (2004). Análise e Modelização de Problemas de localização-distribuição (Doctoral dissertation,
Universidade de Aveiro).
Beardwood, J., Halton, J. H., & Hammersley, J. M. (1959). The shortest path through many points.
In Mathematical Proceedings of the Cambridge Philosophical Society. Vol. 55, No. 4, pp. 299-327.
Cambridge University Press.
Belenguer, J. M., Benavent, E., Prins, C., Prodhon, C., & Calvo, R. W. (2011). A branch-and-cut method for the
capacitated location-routing problem. Computers & Operations Research, 38(6), 931-941.
Caballero, R., González, M., Guerrero, F. M., Molina, J., & Paralera, C. (2007). Solving a multiobjective location
routing problem with a metaheuristic based on tabu search. Application to a real case in Andalusia.
European Journal of Operational Research, 177(3), 1751-1763.
Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery
points. Operations research, 12(4), 568-581.
Colorni, A., Dorigo, M., & Maniezzo, V. (1992). An Investigation of some Properties of an" Ant Algorithm".
In Ppsn, Vol. 92, No. 1992.
Contardo, Claudio., Cordeau, J. F., & Gendron, Bernard (2010). A branch-and-cut algorithm for the capacitated
location-routing problem. In Conference CAOR (Vol. 10).
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.
Dorigo, M. (1992). Optimization, learning and natural algorithms. Ph. D. Thesis, Politecnico di Milano.
Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. IEEE
Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26(1), 29-41.
Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: a cooperative learning approach to the traveling
salesman problem. IEEE Transactions on evolutionary computation, 1(1), 53-66.
ISSN-L: 0798-1015 • eISSN: 2739-0071 (En línea) – Revista Espacios – Vol. 42, Nº 16, Año 2021
GATICA, Gustavo et al. «Heuristic algorithm based on Ant Colony Optimization for the Capacitated Location-
Routing problem with Homogeneous Fleet»
Pag. 11
Dorigo M., Stützle T. (2019) Ant Colony Optimization: Overview and Recent Advances. In: Gendreau M., Potvin
JY. (eds) Handbook of Metaheuristics. International Series in Operations Research & Management Science,
vol 272. Springer, Cham. https://doi.org/10.1007/978-3-319-91086-4_10.
Duhamel, C., Lacomme, P., Prins, C., & Prodhon, C. (2010). A GRASP× ELS approach for the capacitated location-
routing problem. Computers & Operations Research, 37(11), 1912-1923.
Escobar, J. W., & Linfati, R. (2012). Un algoritmo metaheurístico basado en recocido simulado con espacio de
búsqueda granular para el problema de localización y ruteo con restricciones de capacidad. Revista
Ingenierías Universidad de Medellín, 11(21), 139-150. Available in
https://revistas.udem.edu.co/index.php/ingenierias/article/view/604/545
Escobar, J. W., Linfati, R., & Toth, P. (2013). A two-phase hybrid heuristic algorithm for the capacitated location-
routing problem. Computers & Operations Research, 40(1), 70-79.
Escobar, J. W., Linfati, R., & Adarme-Jaimes, W. (2015). A hybrid metaheuristic algorithm for the capacitated
location routing problem. Dyna, 82(189), 243-251.
Farkavcova, V. G., Rieckhof, R., & Guenther, E. (2018). Expanding knowledge on environmental impacts of
transport processes for more sustainable supply chain decisions: A case study using life cycle
assessment. Transportation Research Part D: Transport and Environment, 61, 68-83.
García, L. A. M. (2016). GESTION LOGISTICA INTEGRAL: las mejores practicas en la cadena de abastecimiento .
Ecoe Ediciones. Retrieved from: https://www.ecoeediciones.com/wp-content/uploads/2016/12/Gestion-
logistica-integral-2da-Edici%C3%B3n.pdf
Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness.
WH Freeman & Co. New York, NY, USA.
Harks, T., König, F. G., & Matuschke, J. (2013). Approximation algorithms for capacitated location
routing. Transportation Science, 47(1), 3-22.
Helsgaun, K. (2000). An effective implementation of the Lin–Kernighan traveling salesman heuristic. European
Journal of Operational Research, 126(1), 106-130.
i Cos, J. P., & De Navascués, R. (1998). Manual de logística integral. Ediciones Díaz de Santos. Retrieved from:
http://www.diazdesantos.com.co/libros/pau-i-cos-jordi-manual-de-logistica-integral-L03003450303.html
Laporte, G., Louveaux, F., & Mercure, H. (1989). Models and exact solutions for a class of stochastic location-
routing problems. European Journal of Operational Research, 39(1), 71-78.
Linfati, R., Escobar, J. W., & Gatica, G. (2014). A metaheuristic algorithm for the location routing problem with
heterogeneous fleet. Ingeniería y Ciencia, 10(19), 55-76.
Luna López, L. C. (2015). Localización de paradas y diseño óptimo de rutas para transporte de personal
(Doctoral dissertation, Universidad Autónoma de Nuevo León). Retrieved from:
http://eprints.uanl.mx/9541/1/1080214944.pdf
Mehrjerdi, Y. Z., & Nadizadeh, A. (2013). Using greedy clustering method to solve capacitated location-routing
problem with fuzzy demands. European Journal of Operational Research, 229(1), 75-84.
ISSN-L: 0798-1015 • eISSN: 2739-0071 (En línea) – Revista Espacios – Vol. 42, Nº 16, Año 2021
GATICA, Gustavo et al. «Heuristic algorithm based on Ant Colony Optimization for the Capacitated Location-
Routing problem with Homogeneous Fleet»
Pag. 12
Negrotto, D. (2015). Algoritmos para el problema de localización y ruteo de vehículos con capacidades y
premios (Doctoral dissertation, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales).
Retrieved from: https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n5818_Negrotto.pdf
Prins, C., Prodhon, C., & Calvo, R. W. (2006a). A memetic algorithm with population management (MA| PM) for
the capacitated location-routing problem. In European Conference on Evolutionary Computation in
Combinatorial Optimization (pp. 183-194). Springer, Berlin, Heidelberg.
Prins, C., Prodhon, C., & Calvo, R. W. (2006b). Solving the capacitated location-routing problem by a GRASP
complemented by a learning process and a path relinking. 4OR, 4(3), 221-238.
Prins, C., Prodhon, C., Ruiz, A., Soriano, P., & Wolfler Calvo, R. (2007). Solving the capacitated location-routing
problem by a cooperative Lagrangean relaxation-granular tabu search heuristic. Transportation
Science, 41(4), 470-483.
Stützle, T., & Ruiz, R. (2018). Iterated Local Search: A Concise Review. IRIDIA, Institut de Recherches
Interdisciplinaires et de D´eveloppements en Intelligence Artificielle, Universite Libre de Bruxelles,
Technical Report. Belgium
Tokgoz, E., & Trafalis, T. B. (2014). Manifold Location Routing Problem with Applications in Network Theory.
In International Conference on Network Analysis, pp. 89-114. Springer, Cham.
Toro, E. M., Franco, J. F., Echeverri, M. G., & Guimarães, F. G. (2017). A multi-objective model for the green
capacitated location-routing problem considering environmental impact. Computers & Industrial
Engineering, 110, 114-125.
Toth, P., & Vigo, D. (2002). Models, relaxations and exact approaches for the capacitated vehicle routing
problem. Discrete Applied Mathematics, 123(1-3), 487-512.
Tuzun, D., & Burke, L. I. (1999). A two-phase tabu search approach to the location routing problem. European
journal of operational research, 116(1), 87-99.
Vasquez Delgado (2012), Implementación de un algoritmo basado en la Búsqueda Tabú para la resolución de
un problema de ruteo de vehículos con ventana temporal de acceso. Capítulo 4 resolución del problema
de ruteo de vehículos VRP, Francisco de asís. Escuela técnica superior de ingenieros, Universidad de
Sevilla. pp. 27-39.
Vincent, F. Y., Lin, S. W., Lee, W., & Ting, C. J. (2010). A simulated annealing heuristic for the capacitated
location routing problem. Computers & Industrial Engineering, 58(2), 288-299.
Watson-Gandy, C. D. T., & Dohrn, P. J. (1973). Depot location with van salesmen—a practical
approach. Omega, 1(3), 321-329.
Webb, M. H. J. (1968). Cost functions in the location of depots for multiple-delivery journeys. Journal of the
Operational Research Society, 19(3), 311-320.
Wu, T. H., Low, C., & Bai, J. W. (2002). Heuristic solutions to multi-depot location-routing problems. Computers
& Operations Research, 29(10), 1393-1415.
