algorimo genico
Optimización de diseño de rutas de vehículos
usando algoritmos genéticos
Fredy Alejandro Martínez Álvarez*
Fecha de envio: 19 de octubre de 2007.
Fecha de aceptación: 23 de marzo de 2008.
Resumen
El objeto de presente estudio es el diseño de rutas de
distribución de un producto dentro de la red, seleccionando la secuencia devisitas y aplicando restricciones de capacidad de volumen de carga y distancia
máxima por recorrido, minimizando los costos de
En el artículo se propone un método de solución
distribución.
meta heurística, por medio de la aplicación de algo-
Dentro de los modelos existentes para solucionar
centro de distribución y ocho diferentes centros de
este problema se encuentran los algoritmosde Clarke y Wrigth, el método del ahorro y los modelos de
transporte basados en las teorías de programación
lineal y entera, los cuales se desempeñan de manera
óptima y eficiente en una cantidad reducida de centros de consumo. La eficiencia de estos algoritmos
decrece conforme se aumenta el número de centros
de consumo, debido a que el espacio de soluciones
aumenta exponencialmente,convirtiendo el problema de ruteo en un problema de tipo NP-Completo.
ritmos genéticos en un problema compuesto por un
consumo, donde las medidas de desempeño establecidas son costo, distancia y volumen (carga).
Aplicando el modelo, los resultados muestran la
consecución de una buena solución en un tiempo
de búsqueda polinomial, las cuales fueron evaluadas con diferentes medidas de desempeñoprincipalmente por los costos asociados a la distribución del
producto en la red de distribución.
Palabras clave: ruteo de vehículos, algoritmos genéticos, logística de distribución.
* Profesor Facultad de Ingeniería Civil de la Universidad de La Salle. Correo electrónico: fmartineza@unisalle.edu.co
21
Revista Épsilon Nº 11 / Julio - diciembre 2008
Design
optimization of routes ofvehicles using genetic algorithms
Abstract
The object of the present research is design of paths
of distribution of a product within the delivery network, selecting the sequence of visits and applying
to restrictions of capacity of load volume and maximum distance by path, diminishing the distribution
In the article a solution using a heuristic method is
costs.
proposed, by meansof the application of genetic algorithms in a problem made up of a center of dis-
Within the existing models to solve this problem are
tribution and eight different centers from consump-
the algorithms of Clarke and Wrigth, the method of
tion, where the established measures of performance
the saving and the models of transport based on the
are cost, distance and volume (load).theories of linear integer programming, which evolve of optimal and efficient way in a reduced amount
Applying the model, the results show the achieve-
of consumption centers. The efficiency of these al-
ment of a good solution in a polynomial time search,
gorithms decreases as is increased the number of
which were evaluated with different measures from
consumption centers,because the space of solutions
performance mainly for the associate cost to product
increases exponentially, turning the path problem
distribution in the distribution network.
on a problem of NP-Complete type.
Key Words: Vehicle Router, Genetic Algorithms, Distribution Logistic.
22 / Fredy Alejandro Martínez Álvarez
Revista Épsilon Nº 11 / Julio - diciembre 2008
IntroducciónPor lo anterior, el diseñar las rutas de distribución se
Es común en el medio empresarial moderno la distri-
logística de cualquier empresa, más aún en el merca-
bución de productos o servicios donde el cliente final
do globalizado de los últimos años.
los requiera, esto con el fin de proporcionarle a éste la
mayor satisfacción y, de esta forma, asegurar su predi-
convierte en...
Regístrate para leer el documento completo.