/02/
EFECTO DE LA APLICACIÓN DEL ALGORITMO DE COLONIA
DE HORMIGAS EN UN SERVICIO LOGÍSTICO
EFFECT OF THE APPLICATION OF THE ANT COLONY
ALGORITHM IN A LOGISTIC SERVICE
Ángel Geovanny Guamán Lozano
Profesor investigador. Facultad de Mecánica. Escuela Superior Politécnica de Chimborazo.
Riobamba. (Ecuador).
E-mail: a_guaman@espoch.edu.ec ORCID: https://orcid.org/0000-0002-5145-6994
Gloria Elizabeth Miño Cascante
Profesora investigadora. Vicerrectora Académica. Escuela Superior Politécnica de Chimborazo.
Riobamba. (Ecuador).
E-mail: vracademico@espoch.edu.ec ORCID: https://orcid.org/0000-0003-2896-3987
Julio Cesar Moyano Alulema
Profesor investigador. Facultad de Mecánica. Escuela Superior Politécnica de Chimborazo.
Riobamba. (Ecuador).
E-mail: j_moyano@espoch.edu.ec ORCID: https://orcid.org/0000-0001-6672-9409
Alcides Napoleón García Flores
Profesor investigador. Facultad de Mecánica. Escuela Superior Politécnica de Chimborazo.
Riobamba. (Ecuador).
E-mail: an_garcia@espoch.edu.ec ORCID: https://orcid.org/0000-0001-6883-7067
Juan Carlos Cayán Martínez
Profesor investigador. Facultad de Mecánica. Escuela Superior Politécnica de Chimborazo.
Riobamba. (Ecuador).
E-mail: j_cayan@espoch.edu.ec ORCID: https://orcid.org/0000-0001-9573-3706
Recepción: 22/01/2018. Aceptación: 27/02/2018. Publicación: 14/12/2018
Citación sugerida:
Guamán Lozano, Á. G., Miño Cascante, G. E., Moyano Alulema, J. C., García Flores, A. N. y Cayán Martínez,
J. C. (2018). Efecto de la aplicación del algoritmo de colonia de hormigas en un servicio logístico. 3C Tecnología.
Investigación y pensamiento crítico. doi:http://dx.doi.org/10.17993/3ctecno.2018.v7n4e28.28-47/
30
3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143
RESUMEN
Con el desarrollo tecnológico que se evidencia en la actualidad, el uso de algoritmos enfocados a
la resolución de problemas de la vida real se da con mayor frecuencia. La presente investigación
tuvo como objetivo determinar una ruta eciente para la distribución de productos en la ciudad
de Riobamba en el Ecuador, utilizando un vehículo repartidor mediante la aplicación de un
algoritmo de optimización denominado colonia de hormigas y considerando variables como la
distancia, costo y visibilidad. La recopilación de los datos se ejecutó a través del levantamiento
en campo de todas las rutas de la empresa panicadora. A continuación, se desarrolló el
algoritmo informático utilizando el lenguaje de programación C# en Visual Basic. El programa
generó una ruta con menores distancias de recorrido. Una vez determinada la solución de
enrutamiento se evaluaron los tiempos de respuesta del programa considerando el número
de iteraciones ejecutadas. Como conclusión se observa que existen problemas en los tiempos
de procesamiento, evidenciándose que el algoritmo optimización de colonias de hormigas
presenta soluciones cercanas a la óptima en tiempos extensos de respuesta.
ABSTRACT
With the technological development that is evidenced at present, the use of algorithms focused
on solving real-life problems occurs more frequently. The objective of the present investigation
was to determine an ecient route for the distribution of products in the city of Riobamba in
Ecuador, using a delivery vehicle through the application of an optimization algorithm called
an ant colony and considering variables such as distance, cost and visibility. The data collection
was carried out through the eld survey of all routes of the bakery company, then the computer
algorithm was developed using the C # programming language in Visual Basic. The program
generated a route with shorter travel distances. Once the routing solution was determined, the
program response times were evaluated considering the number of iterations executed. As a
conclusion it is observed that there are problems in the processing times, evidencing that the
ant colony optimization presents solutions close to the optimum.
PALABRAS CLAVE
Enrutamiento, modelo, optimización de colonias de hormigas, logística.
KEY WORDS
Routing, model, optimization of ant colonies, logistics.
31
Ed. 28. Vol.7 Nº 4. Diciembre 2018-Marzo 2019
DOI: http://dx.doi.org/10.17993/3ctecno.2018.v7n4e28.28-47/
1. INTRODUCCIÓN
Un servicio logístico de calidad está orientado a la satisfacción de los clientes a través de múltiples
ventajas competitivas que hacen que un consumidor preera un producto y no el de la competencia.
La distribución comercial es responsable de la eciencia de la entrega del producto hacia los clientes
en el tiempo y lugar exacto (Perez, 2013).
Una característica de calidad se presenta en el tiempo de ejecución de las actividades en la cadena
de suministro. Con el n de mejorar el panorama de las organizaciones, se han formulado soluciones
exactas, heurísticas y genéticas que reducen el consumo de recursos y mejoren los tiempos de entrega
de productos y servicios.
Los algoritmos genéticos son procesos que están dados por la evolución que ha surgido en la
selección natural, y al relacionarles con la vida real resultan factibles especialmente cuando se
tratan de casos con datos en cadenas nitas en alfabeto nito (Luaces, Beyris y Rosales, 2011).
Los operadores genéticos proporcionan potenciales soluciones que se generan por iteraciones,
actualizando su sistema a cada instante, para lo cual se señalan tres tipos: un operador de
selección de las mejores soluciones, un operador de cruce que otorga nuevas soluciones a partir
de dos respuestas previas y, un operador de mutación que realiza una pequeña trasformación
sobre una solución previa.
Por otra parte, una alternativa de solución es el llamado Algoritmo de Optimización de Colonia
de Hormigas (ACO). El modelo fue desarrollado en la década de los 90 (Robles, 2010) y es un
considerado un método heurístico porque presenta una serie de procedimientos antes de llegar a
la solución factible, entre los que se encuentran el establecer el problema, delimitar y mostrar el
problema para volver a vericar los resultados de las actividades.
El desarrollo del algoritmo se basa en la capacidad de las hormigas para comunicarse entre sí
sin contar con una adecuada visibilidad, sin embargo, utilizan una sustancia química llamada
feromona que permite establecer las rutas más cortas para encontrar alimentos en el menor tiempo.
Previamente a este resultado debieron realizar un recorrido de exploración, es decir, su trabajo se
ejecuta en equipo y se transforma en la manera más adecuada de funcionar y subsistir, de ahí el
nombre del algoritmo Ant Colony Optimization (Perez, 2011).
La meta del algoritmo es dar soluciones aproximadas a problemas generales, permitiendo que su
32
3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143
implementación en la vida real sea posible por la facilidad de obtener resultados sin recorrer todo
el espacio de búsqueda. El grado de aceptación que presenta la solución es dependiente de los
objetivos que se deseen satisfacer o garantizar (Fernandez, 2015).
Los ACO persiguen, precisamente, explotar esta realidad: a través de un conjunto de agentes
individuales simples (hormigas), trabajando en conjunto (colonia), se pretende obtener soluciones a
problemas de optimización complejos. En concreto, los algoritmos simulan el comportamiento de
recolección de comida de una colonia de hormigas. En el ejemplo que se muestra en la Figura 1, se
puede observar como las hormigas salen desde su colonia en busca de comida recorriendo todas las
posibles rutas hasta llegar a su destino.
Gráco 1. Exploración de las hormigas a la ruta más corta, en busca de alimentos.
Fuente: elaboración propia.
Debido a que estos insectos no tienen una visión desarrollada, su comunicación con el entorno se
lleva a través de un rastro de feromonas (Cobo & Maria, 2005). Las hormigas, en su camino del
nido a la fuente de alimento y viceversa, depositan feromonas en el suelo formando un rastro que el
resto de componentes de la colonia son capaces de oler. Contra mayor es la concentración en una
ruta, mayor es la probabilidad de que una hormiga la siga. Por tanto, en un principio las hormigas
se desplazan por un camino u otro indiferentemente, pero con el paso del tiempo se acumula más
feromona en el camino más transitado, por lo que las hormigas lo escogen con mayor probabilidad
(Aparicio, 2012).
Las hormigas, en su camino del nido a la fuente de alimento y viceversa, depositan feromonas
en el suelo formando un rastro que el resto de componentes de la colonia son capaces de oler.
Contra mayor es la concentración en una ruta, mayor es la probabilidad de que una hormiga la
siga.
33
Ed. 28. Vol.7 Nº 4. Diciembre 2018-Marzo 2019
DOI: http://dx.doi.org/10.17993/3ctecno.2018.v7n4e28.28-47/
Las hormigas tienen la capacidad de recordar las rutas que han visitado y las que son desconocidas
para ellas (Tito, Silva, Alfaro, & Evelyn, 2015). En la Figura 2, se ilustra los depósitos de feromonas
que dejan las hormigas como rastro para que sus colegas sigan la ruta hasta que completen el
trabajo.
Gráco 2. Depósito de feromonas y ruta.
Fuente: elaboración propia.
Al hablar de las feromonas se encuentran aspectos muy interesantes como la dependencia directa
que tienen con el entorno natural, y se debe a que este es el encargado de evaporarlas después de
que transcurra un tiempo. Según estudios biológicos la rapidez con la que desaparece la feromona
está dada por la clase de hormigas y el suelo, ya que pueden tardar horas o hasta meses según sea
el caso (Alonso, 2012).
ACO ha sido exitosamente utilizado en la resolución de problemas de combinación así como
algunas de sus extensiones como el SoSACO-v2 (Sense of Smell - Ant Colony Optimization) ( Calle,
Rivero, Cuadra & Isasi), siendo sus elementos básicos las variables que se procede a detallar: la
variable que hace relación a las hormigas articiales y la matriz de feromonas τ. Por otro lado, están
los algoritmos de EACO o evolutivos, este algoritmo puede resolver los problemas de topología, lo
que hace que EACO sea muy atractivo para resolver problemas de optimización no combinatoria
(Buntara, et al., 2017).
La matriz τ es el medio indirecto que utilizan las hormigas para comunicarse, depositando y
censando a la vez feromonas durante un recorrido en la construcción de una solución sobre un
grafo G (E, V) (Insfrán, Pinto, & Benjamín, 2006), siendo este una representación de un mapa de
recorrido que las hormigas persiguen hasta encontrar su objetivo, por ello es importante establecer
lugares de llegada conocidos como nodos.
Básicamente, la elección de un nodo j mientras una hormiga se encuentra en un nodo i es dada
por la siguiente ecuación probabilística:
34
3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143
(1)
Dónde:
= representa el nivel de feromonas depositado en el enlace (i,j);
= es el conjunto de nodos factibles, vecinos del nodo i.
La convergencia hacia la solución óptima utilizando la ecuación (1), es relativamente lenta, quedan-
do en muchas ocasiones estancada en óptimos locales. Para intentar superar este problema, algunos
trabajos han propuesto el concepto de visibilidad. La visibilidad en su forma más simple es la de-
seabilidad en función de algún parámetro asociado a los enlaces (Cruz, 1999). En ese contexto, la
elección del siguiente nodo es regido por la ecuación (2).
(2)
Dónde:
= representa la visibilidad del enlace (i, j),
=Parámetros que determinan la importancia relativa entre y .
Para evitar una convergencia prematura hacia óptimos locales, otros trabajos han introducido el
concepto de evaporación de las feromonas. La evaporación es regida por la ecuación 3:
(3)
Dónde:
0 ≤ ρ ≤ 1 es el factor de persistencia de las feromonas.
35
Ed. 28. Vol.7 Nº 4. Diciembre 2018-Marzo 2019
DOI: http://dx.doi.org/10.17993/3ctecno.2018.v7n4e28.28-47/
La teoría de grafos es de gran ayuda para modelar estructuras matemáticas y para representar
fenómenos discretos, se hace referencia al algoritmo de la colonia de hormigas para resolver el
modelo matemático con un análisis inductivo (Luaces, Beyris, & Rosales, 2011).
En este caso, el trabajo se centra en la aplicación del algoritmo colonia de hormigas para la
distribución de productos de una empresa panicadora, para de esta manera llegar a determinar la
ruta más adecuada en un tiempo corto. En su desarrollo ACO se maniesta en dos problemas, tanto
estática como dinámicamente, entendiéndose como la aplicación de la parte estática, esto se debe
a que la topología y los costos no cambian mientras se ejecuta el algoritmo, claro está que son dos
circunstancias muy similares, pero dieren en la implementación, lo que signica que se destinan
según la necesidad y requerimientos (Dorigo-Stützle, 2006).
2. METODOLOGÍA
La investigación es de tipo experimental, el estudio transversal cuantitativo fue desarrollado en el año
2017, con el registro del recorrido completo de distribución con 15 destinos de recepción de mercadería.
La toma de datos se realizó par tiendo desde el lugar de producción e incluyó todos los destinos establecidos
en la planicación de la empresa ´´La Vienesa´´, que cuenta con una matriz de producción en la ciudad
de Riobamba, y una sucursal ubicada a 4 kilómetros del lugar, la investigación fue realizada en la matriz
de producción.
La ruta se generó partiendo desde una perspectiva realista que se obtuvo una vez realizada la
medición cuantitativa, haciendo uso de una muestra de tamaño amplio, pues la toma de datos
se dio en tiempo real. Con lo cual, permitió conocer la importancia de adquirir cierto tipo de
consideraciones a tener en cuenta en el desarrollo de este problema en particular, fundamentada en
el algoritmo de colonia de hormigas (Collazos, 2013).
Se establecen dos tipos de variables para la resolución de este tipo de problemas, siendo una de ellas
el nivel de feromonas depositadas por las hormigas durante el trayecto hacia el lugar de origen. En
este caso son las calles, no obstante es ineludible el número de nodos que existentes acorde a cada
sitio de distribución que se encuentran sujetos a las siguientes restricciones: el número de veces que
el vehículo debe pasar por un nodo especíco no excederá una, sin tomar en cuenta los tiempos de
aprovisionamiento del producto y demora que conlleva este tipo de actividad comercial. El principal
36
3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143
propósito al realizar este estudio es determinar la ruta optima de distribución de la panicadora de
la ciudad de Riobamba ubicada en las calles Larrea y 10 de agosto.
Las fuentes de información son de tipo secundaria y primaria, entendiendo por secundaria aquella
prevista que se relaciona con todas las investigaciones realizadas en años anteriores por diversos autores,
sin olvidar la importancia de partir de modelos de tipo heurístico (Gutiérrez, 2007). La información
primaria corresponderá a los trabajos producidos en campo por parte de los sujetos participantes.
Los instrumentos utilizados en la investigación fueron todos aquellos que permitieron la toma de
muestras precisas y acertadas. Se contó con una cha de observación diseñada para la toma de
datos de acuerdo a recorrido del vehículo, validando la recepción de muestras a través del software
libre Google Maps existente en la Web 2.0. Por otro lado, se programó una hoja de cálculo en el
programa Excel que permite observar y obtener las posibles rutas que el camión puede seguir. Todas
estas herramientas son útiles porque permiten que los datos sean de manera precisa y ecaz. Con
la aplicación del Algoritmo de Colonia de Hormigas se realizan varias iteraciones que permiten
encontrar una solución factible al problema antes planteado. Estos datos se presentan antes, durante
y después de la investigación debido a que ayudan a dar soluciones ecaces y pertinentes haciendo
un método totalmente justicable para enrutamiento vehicular.
3. RESULTADOS
3.1. SITUACIÓN ACTUAL
La empresa comienza la repartición del producto a las 05h00 visitando 15 centros de distribución dentro
de la ciudad. En la Tabla 1 se observa una recopilación de datos obtenidos en la ruta que se realiza por
cada punto de entrega desde el punto de distribución o de inicio, además de presentar la dirección de
llegada facilitando así la red de distribución que se muestra continuación con la ayuda de Google Maps.
ITEM DIRECCIÓN LLEGADA
1 Paseo Shopping
2 Calle SN
3 Edelberto Bonilla y Antonio José de Sucre
4 Junín y Diego de Ibarra
5 Eucaliptos y Arrayanes
6 Junin y Jacinto Gonzales
7 Av. La Prensa y Argentinos
37
Ed. 28. Vol.7 Nº 4. Diciembre 2018-Marzo 2019
DOI: http://dx.doi.org/10.17993/3ctecno.2018.v7n4e28.28-47/
ITEM DIRECCIÓN LLEGADA
8 Av. 11 de Noviembre y Lizarzaburo
9 Romero y Cordero
10 Río Quininde y Río Amazonas
11 Pasaje Río Quevedo y Río Amazonas
12 Río Quevedo y Panamericana Lizarzaburo
13 Av. Monseñor Leónidas Proaño y Panamericana Lizarzaburo
14 Av. Monseñor Leónidas Proaño y Araucanos
15 Larrea y 10 de Agosto
Tabla 1. Puntos de visita de carro repartidor de “La Vienesa”. Fuente: elaboración propia.
En la Tabla 2 se especica la distancia y el tiempo empleado por el camión repartidor de la “La
Vienesa, la distancia fue calculada mediante la ayuda de Google Maps mientras que el tiempo se
midió con el empleo del cronometro.
ITEM DISTANCIA (m) TIEMPO (min)
1 2090 7
2 400 1
3 1100 2
4 1200 5
5 850 4
6 300 2
7 550 2
8 1300 6
9 1600 4
10 1400 6
11 190 2
12 210 2
13 600 3
14 1500 7
15 5900 16
TOTAL 19190 69
Tabla 2. Datos de distancia y tiempo empleado en cada distribución. Fuente: elaboración propia.
3.2. DESARROLLO DEL ALGORITMO
El programa se basa en un bucle repetitivo que establece un número determinado de iteraciones,
buscando siempre una solución factible actualizando las variables en cada ciclo.
38
3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143
Gráco 3. Diagrama de ujo del programa. Fuente: elaboración propia.
A continuación, se muestra el código de la programación utilizada en la macro desarrollada, es
importante detallar el número nodos por los cuales las hormigas seguirán su ruta determinada y
los bucles de repetición de acuerdo al número de ciudades ingresadas. Con estas dos variables se
realizan las iteraciones para comparar y mandar a ejecutar la siguiente línea de código. En el bucle
de comparaciones se aplica la fórmula (2), con el valor obtenido se procede a vincular a otra sub
función. La resolución se hizo con 10 vinculaciones de sub funciones, cada una de ellas con una
programación denida, una parte del código se detalla a continuación.
39
Ed. 28. Vol.7 Nº 4. Diciembre 2018-Marzo 2019
DOI: http://dx.doi.org/10.17993/3ctecno.2018.v7n4e28.28-47/
Sub Iteraciones ()
‘Determinación iterativa de las rutas de las hormigas
For w = 1 To Ciudades - 1 ‘Numero de Iteraciones del Algoritmo
For a = 1 To h ‘Iteracion Hormiga
‘Borrado de la Iteracion de Hormiga Anterior
ReDim Dist_Temp(Ciudades)
ReDim P(Ciudades, Ciudades)
revisionmatrizdistancias ‘Llama la rutina “revisionmatrizdistancias”
‘Calcula la matriz de probabilidades
For j = 1 To Ciudades ‘ El 8 lo determina el numero de ciudades
If Dist_Temp(j) <> “” Then
If Dist_Temp(j) <> 0 Then
cociente = 0
For f = 1 To Ciudades
If Dist_Temp(f) <> 0 Then
If Dist_Temp(f) <> “” Then
cociente = cociente + (t(k(a, w), f) ^ alfa) * (1
/ (Dist_Temp(f) ^ beta))
End If
End If
Next f
If cociente <> 0 Then
P(k(a, w), j) = ((t(k(a, w), j) ^ alfa) * (1 / (Dist_
Temp(j) ^ beta))) / cociente
Else
P(k(a, w), j) = 0
End If
End If
End If
Next j
‘Eleccion de la siguiente Ciudad
For j = 1 To Ciudades ‘ El 8 lo determina el numero de ciudades
If P(k(a, w), j) = WorksheetFunction.Max(P()) Then
k(a, w + 1) = j
N(a, j) = “x”
40
3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143
Exit For
End If
Next j
Next a
Next w
End Sub
Sub revisionmatrizdistancias()
For j = 1 To Ciudades ‘ Columna
If N(a, j) <> “x” Then
Dist_Temp(j) = distancias(k(a, w), j)
End If
Next j
End Sub
Para el algoritmo antes expuesto fue necesaria la recolección de datos de dos variables de impor tancia:
las rutas de distribución y nodos que se obtuvieron a través de una indagación de campo. La
ejecución de las variables parte de conocer las variables distancia y sitios de distribución, que hacen
referencia a las feromonas y a las hormigas que siguen por dicho camino respectivamente. Entonces,
una hormiga (vehículo repartidor) parte del nodo inicial i hacia a otro nodo j, comenzando de un
grafo que se obtuvo al realizar la representación de la repartición del producto en cuestión.
La distancia hacia cada nodo de las diferentes coordenadas con una probabilidad, está marcada
por la entrada de nodos del grafo, lo que quiere decir que mientras más sean los datos de ingreso
mayor será el número de rutas posibles. Es así como el nivel de dicultad se incrementa debido a las
posibles permutaciones que se pueden presentar para resolverlo.
El número de soluciones posibles dependerá de la cantidad de nodos ingresados por la factorial
del mismo número para compararlas entres si, así, la complejidad de resolución del problema se
incrementará.
Los datos de cada nodo se ingresan y se procede a encontrar la distancia aplicando distancias
euclidianas entre dos puntos. Con estos resultados se realizan iteraciones que corresponden a la
hormiga en un ciclo completo mientras ejecuta una probabilidad, siempre y cuando se tenga en
cuenta que la ciudad no haya sido visitada dos veces en el ciclo.
41
Ed. 28. Vol.7 Nº 4. Diciembre 2018-Marzo 2019
DOI: http://dx.doi.org/10.17993/3ctecno.2018.v7n4e28.28-47/
La visibilidad de las ciudades representadas por los coecientes alfa y beta, tienen una característica
en común, su valor es 1, pero también se presentan como parámetros ajustables, porque al nal
del recorrido cada hormiga debe depositar una cierta cantidad de feromona en cada nodo por el
que ha pasado dependiendo del recorrido obtenido con respecto a otras hormigas. Por lo tanto, se
recomienda tomar tantas hormigas como nodos exista. La cantidad de feromona que se encuentra
presente en los nodos del algoritmo es una información renovada a cada instante debido a la
dependencia del número de veces que se ha pasado por dicha ruta.
3.3. POSIBLES ESCENARIOS
En la Tabla 4 se establecen los valores o parámetros utilizados para la aplicación de la fórmula del
ACO mencionada anteriormente.
Tabla 3. Parámetros empelados en ACO.
PARÁMETROS
Alfa 1
Beta 1
ρ
0,8
Max Iteraciones 5
Nº Hormigas 5
Ciudades 16
Fuente: elaboración propia.
Para encontrar la solución factible es necesario colocar los datos en una matriz cuadrática, que
está dada por las distancias mostradas en la Tabla 2, además se despliega la matriz inversa, de esta
manera se tiene la Tabla 4.
Tabla 4. Matriz e inversa en función a distancias. Fuente: elaboración propia.
42
3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143
El programa presenta mediante la macro las rutas factibles que el camión podría seguir en sus
entregas, también muestra las distancias cuando en un inicio los camiones salen en busca de comida
sin conocer el camino como se muestra en la Tabla 5.
Tabla 5. Solución factible presentada por el programa.
Distancias Ruta Óptima
38.380 15
38.380 14
38.380 13
38.380 12
38.380 11
10
9
8
7
6
5
4
3
2
1
16
15
Fuente: elaboración propia.
La investigación necesitaba ser aún más detalla, por este motivo se utilizó el programa Ant Algorithm
Simulator” mediante el cual se simulan las rutas que el camión puede seguir representado por
hormigas variando los parámetros de ingreso. En la Figura 4 se muestra la ruta del primer tramo
que se realizó de 5 puntos de entrega a partir de las calles Larrea y 10 de agosto hasta Eucaliptos y
Arrayanes.
43
Ed. 28. Vol.7 Nº 4. Diciembre 2018-Marzo 2019
DOI: http://dx.doi.org/10.17993/3ctecno.2018.v7n4e28.28-47/
Gráco 4. Ruta desde Larrea y 10 de agosto hasta Eucaliptos y Arrayanes.
Fuente: elaboración propia.
Los resultados alcanzados indican que existen varias rutas adecuadas para realizar el recorrido
de distribución de pan, disminuyendo el tiempo de repartición, reduciendo costos de producción
debido al transporte e incrementado la eciencia de entrega del producto, brindando así un mejor
servicio a los clientes y satisfaciendo sus necesidades.
3.4. FACTOR DE TIEMPO DE PROCESO
Las simulaciones anteriormente detalladas fueron ejecutadas en un computador con procesador
Intel Core i7-4510U, 2.00 GHz y memoria RAM de 8GB. Con estos antecedentes se establecieron
de forma aleatoria 50 corridas para el programa, con incrementos de 5 iteraciones en cada ciclo
como se muestra en la Figura 5.
44
3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143
Gráco 5. Ruta desde Larrea y 10 de agosto hasta Eucaliptos y Arrayanes.
Fuente: elaboración propia.
El comportamiento de los datos establece una tendencia lineal (Figura 6), mediante un método de
regresión lineal se puede predecir el tiempo en que tardaría en realizar todas las combinaciones
posibles y encontrar la solución óptima agotando todas las alternativas.
Gráco 6. Tendencia lineal ascendente.
Fuente: elaboración propia.
45
Ed. 28. Vol.7 Nº 4. Diciembre 2018-Marzo 2019
DOI: http://dx.doi.org/10.17993/3ctecno.2018.v7n4e28.28-47/
Aplicando estos métodos se obtienen las siguientes relaciones matemáticas de la ecuación 4.
(4)
Donde:
y: tiempo de respuesta
x: número de iteraciones
El número de combinaciones para el caso llega a n=15 ! permutaciones posibles, es decir que n=
1307674368000, resultando como tiempo análisis total 513,16 años. Un valor improcedente que
hace que el algoritmo sea útil para soluciones cortas de pocos nodos o a su vez para las primeras
iteraciones.
4. CONCLUSIONES
Si bien es cierto, el algoritmo de la colonia de hormigas es de tipo heurístico, por lo cual no asegura
soluciones óptimas. Sin embargo, es de gran contribución para obtener resultados aceptables
reduciendo el tiempo de cómputo en el desarrollo con respecto a métodos alternativos, mediante
una adecuada denición de variables dependientes e independientes.
En la distribución de mercadería, es necesario encontrar rutas factibles que ayuden a los distribui-
dores a entregar su producto en el lugar y tiempo indicado. Los resultados obtenidos muestran
claramente que en el algoritmo colonia de hormigas es importante tomar en cuenta η_ij como la
visibilidad del enlace (i, j) para el problema la inversa de las distancias, α y β factores asumidos con
el valor de uno porque destaca la solución factible, ya que incrementa las feromonas dejadas en el
camino, τij hizo referencia a las diferentes rutas por donde el camión realiza el recorrido habitual-
mente.
Los resultados obtenidos muestran claramente que en el algoritmo colonia de hormigas es
importante tomar en cuenta η_ij como la visibilidad del enlace (i, j) para el problema la inversa
de las distancias, α y β factores asumidos con el valor de uno porque destaca la solución factible.
46
3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143
Es necesario considerar que al aplicar el mencionado algoritmo existen diferentes factores que no se
consideran, tales como: en primer punto el estado de la vía, debido a la situación geografía de una
ciudad puede tener algunas vías en mejores condiciones que otras. En segundo punto el tránsito,
que en el caso de estudio fue bajo en el horario de las 4:15 a.m. hasta las 5:23 a.m., garantizando
de esta manera una toma de datos certera, pero no exacta. Como tercer punto el tiempo de espera,
por las señales de tránsito que se debe seguir. Como cuarto punto el clima que es independiente de
mejoras, pero es clave ya que en el transporte resulta una variable no denida.
Los tiempos de procesamiento hacen que el ACO sea un método limitado y se acepten tan solo
soluciones viables, más no totalmente optimizadas, elevando de forma considerable la búsqueda de
una ruta optima de servicio en el caso de estudio presentado.
5. REFERENCIAS BIBLIOGRÁFICOS
Alonso, S., Cordón, O., Fernández de Viana, I. y Herrera, F. (2012). La Metaheurística de
optimización basada en colonias de hormigas: modelos y nuevos enfoques. Granada, España: Universidad de
Granada.
Aparicio, D. (2012). Aplicación de los algoritmos de hormigas para la resolución de un RALBP. Barcelona,
España: ETSEIB.
Calle, J., Rivero, J., Cuadra, D. e Isasi, P. (2017). Extending ACO for fast path search in
huge graphs and social networks. Expert Systems With Applications, 86, pp. 292–306. doi: 10.1016/j.
eswa.2017.05.066
Cobo, A., y Maria, S. A. (2005). Un algoritmo híbrido basado en colonias de hormigas para la resolución de
problemas de distribución en la planta orientados a procesos. Recuperado de: https://w w w.uv.es/asepuma/
XIII/comunica/comunica_04.pdf
Collazos, C. (2013). Rediseño del sistema productivo utilizando técnicas de distribución de planta. Recuperado
de: http://www.bdigital.unal.edu.co/12157/1/8912504.2013.pdf
Cruz, I. (1999). Los canales de distribución de produc tos de gran consumo. Barcelona, España: Piramide.
Dorigo, M. (2006). The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and
Advances. En International Series in Operations Research & Management Science (pp. 250-285). doi:https://
doi.org/10.1007/0-306-48056-5_9
47
Ed. 28. Vol.7 Nº 4. Diciembre 2018-Marzo 2019
DOI: http://dx.doi.org/10.17993/3ctecno.2018.v7n4e28.28-47/
Buntara, G., Takahiro, H., Aylie, H., Alisjahbana, S. y As’ad, S. (2017). Evolutionary ACO
algorithms f or truss optimization problems. Procedia Engineering, 171. doi: https://doi.org/10.1 O
16/j .proeng.2017.O1.467
Fernandez, J. (2005). Equipo de Algoritmos Evolutivos Multiobjetivo Paralelos (Tesis de Final de
Grado). Recuperado de: https://www.cnc.una.py/publicaciones/4_130.pdf
Gutiérrez, V. (2007). Modelos de Gestión de I nventarios en Cadenas. Recuperado de: http://www.scielo.
org.co/pdf/rua/n43/n43a12.pdf
Insfrán, C., Pinto, D. y Benjamín, B. (2006). Diseño de Topologías Virtuales en Redes Ópticas.
Recuperado de: https://www.cnc.una.py/publicaciones/4_143.pdf
Luaces, R., Beyris, M., y Rosales, M. (2011). Colonia de hormigas aplicada a la teoría de grafos.
En Ac ta Latinoamericana de Matemática Educativa (pp. 545-552). Cuba: Comité Latinoamericano de
Matemática Educativa A.C.
Ortega, A., y Ana, S. (2005). Un Algoritmo Híbrido Basado en Colonias de Hormigas para la
Resolución de Problemas. XIII Jornadas de ASEPUMA, 3.
Perez, I. (2011). Heurística inspirada en el análisis sistémico del “vecino más cercano para solucionar instancias
simétricas TSP empleando una base comparativa multicriterio. ( Tesis de Final de Máster). Recuperado de:
http://bdigital.unal.edu.co/5443/1/71225056.2011.pdf
Perez, S. (2013). Implementación de un algoritmo basado en Colonias de Hormigas para la optimización de
funciones con datos mezclados. Santa Clara: Universidad Central Marta Abreu de Las Villas.