Title
Design optimization of routes of vehicles using genetic algorithms
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 de visitas y aplicando restricciones de capacidad de volumen de carga y distancia máxima por recorrido, minimizando los costos de distribución. Dentro de los modelos existentes para solucionar este problema se encuentran los algoritmos de 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. En el artículo se propone un método de solución meta heurística, por medio de la aplicación de algoritmos genéticos en un problema compuesto por un centro de distribución y ocho diferentes centros de 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ño principalmente 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
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 costs. Within the existing models to solve this problem are the algorithms of Clarke and Wrigth, the method of the saving and the models of transport based on the theories of linear integer programming, which evolve of optimal and efficient way in a reduced amount of consumption centers. The efficiency of these algorithms decreases as is increased the number of consumption centers, because the space of solutions increases exponentially, turning the path problem on a problem of NP-Complete type. In the article a solution using a heuristic method is proposed, by means of the application of genetic algorithms in a problem made up of a center of distribution and eight different centers from consumption, where the established measures of performance are cost, distance and volume (load). Applying the model, the results show the achievement of a good solution in a polynomial time search, which were evaluated with different measures from performance mainly for the associate cost to product distribution in the distribution network
Keywords
Vehicle Router, Genetic Algorithms, Distribution Logistic
Fecha de recepción
19 de octubre de 2007
Fecha de aceptación
23 de marzo de 2008
Fecha de publicación
2008-12-01
Licencia Creative Commons
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.
Tipo de documento
Artículos de investigación
Editorial
Universidad de La Salle. Ediciones Unisalle
Citación recomendada
Martínez Álvarez, Fredy Alejandro
(2008)
"Optimización de diseño de rutas de vehículos usando algoritmos genéticos,"
Épsilon:
No.
11
, Article 3.
Disponible en:
