Solución al Problema de Ruteo de Vehículos Empleando Algoritmo Genético
DOI:
https://doi.org/10.18041/1909-2458/ingeniare.15.599Palabras clave:
Algoritmo genérico, VRP, Programación lineal, HeurísticaResumen
El presente artículo compara dos métodos para solucionar el problema clásico de rutas de vehículos (VRP), conocido así por sus siglas en inglés (Vehicle Routing Problem), introducido por Dantzig y Ramser en el año de 1959, el cual consiste en minimizar el costo de repartir la mercancía desde un almacén a un conjunto de clientes, donde se utiliza un método exacto de programación lineal y
una meta heurística basada en algoritmos genéticos. El objeto de comparación será el problema de benchmark desarrollado por Christofides (1976). En la comparación se tendrán en cuenta los mejores resultados históricamente hasta la fecha y los obtenidos en el desarrollo de este artículo.
Descargas
Los datos de descarga aún no están disponibles.
Referencias
G. B. Dantzig y J. H. Ramser, “The Truck Dispatching Problemˮ, Management Science, vol. 6, n. 1, pp. 80-91, October 1959.
S. Martello y P. Toth, Bin-packing problem. Knapsack Problems: Algorithms and Computer Implementations. Wiley, capítulo 8, 1990, pp. 221-245.
M. Garey and D. Johnson, Computers and Intractability: A guide to the theory of NP-Completeness. New York, NY, USA: W. H. Freeman & Co., 1979.
B. Dorronsoro, A. J. Nebro, D. Arias y E. Alba, Un algoritmo genético híbrido paralelo para instancias complejas del problema VRP. s.f.
A. Chipperfield, P. Fleming, H. Pohleim y C. Fonseca, “Genetic Algorithm Toolbox Userʼs Guideˮ. ACSE Research Report No. 512, University of Sheffield, 1994.
N. Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.
J. M. Daza, J. R. Montoya, F. Narducci, Resolución del problema de enrutamiento de vehículos con limitaciones de capacidad utilizando un procedimiento metaheurístico de dos fases, 2009.
O. Díaz Parra, M. A. Cruz Chavez, El problema del transporte. Centro de Investigación en Ingeniería y Ciencias Aplicadas, Cuernavaca. Morelos. /Papadimitriou, C.H., Steiglitz, K. Combinatorial
optimization, algorithms and complexity. Mineola, New York, USA: Dover Publications, Inc., 1998.
P. Toth and D. Vigo, The Vehicle Routing Problem, Monographs on Discrete Mathematics and Applications. Philadelphia: SIAM, 2001.
G. Clarke and J. Wright, “Scheduling of vehicles from a central depot to a number of delivery points”, Operations Research, 12 n. 4, 568-581, 1964.
N. Christofides, A. Mingozzi, P. Toth, The Vehicle Routing Problem. In: Combinatorial Optimization. Wiley, Chichester, 1979, 315-338.
A. Olivera, Heurísticas para problemas de Ruteo de Vehículos. Montevideo, Uruguay, 2004.
A. Diaz, J. De Vasconcelos, “Multiobjective genetic Algorithms Applied to solve optimization problems” IEE, Transaction of magnetic, vol. 38, n. 2, March 2002.
E. Zitzler, M. Laumanns and L. Thiele. “SPEA II: Improving the Strength Pareto Evolutionary Algorithmˮ. TIK-Report 103. May 2001.
S. Martello y P. Toth, Bin-packing problem. Knapsack Problems: Algorithms and Computer Implementations. Wiley, capítulo 8, 1990, pp. 221-245.
M. Garey and D. Johnson, Computers and Intractability: A guide to the theory of NP-Completeness. New York, NY, USA: W. H. Freeman & Co., 1979.
B. Dorronsoro, A. J. Nebro, D. Arias y E. Alba, Un algoritmo genético híbrido paralelo para instancias complejas del problema VRP. s.f.
A. Chipperfield, P. Fleming, H. Pohleim y C. Fonseca, “Genetic Algorithm Toolbox Userʼs Guideˮ. ACSE Research Report No. 512, University of Sheffield, 1994.
N. Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.
J. M. Daza, J. R. Montoya, F. Narducci, Resolución del problema de enrutamiento de vehículos con limitaciones de capacidad utilizando un procedimiento metaheurístico de dos fases, 2009.
O. Díaz Parra, M. A. Cruz Chavez, El problema del transporte. Centro de Investigación en Ingeniería y Ciencias Aplicadas, Cuernavaca. Morelos. /Papadimitriou, C.H., Steiglitz, K. Combinatorial
optimization, algorithms and complexity. Mineola, New York, USA: Dover Publications, Inc., 1998.
P. Toth and D. Vigo, The Vehicle Routing Problem, Monographs on Discrete Mathematics and Applications. Philadelphia: SIAM, 2001.
G. Clarke and J. Wright, “Scheduling of vehicles from a central depot to a number of delivery points”, Operations Research, 12 n. 4, 568-581, 1964.
N. Christofides, A. Mingozzi, P. Toth, The Vehicle Routing Problem. In: Combinatorial Optimization. Wiley, Chichester, 1979, 315-338.
A. Olivera, Heurísticas para problemas de Ruteo de Vehículos. Montevideo, Uruguay, 2004.
A. Diaz, J. De Vasconcelos, “Multiobjective genetic Algorithms Applied to solve optimization problems” IEE, Transaction of magnetic, vol. 38, n. 2, March 2002.
E. Zitzler, M. Laumanns and L. Thiele. “SPEA II: Improving the Strength Pareto Evolutionary Algorithmˮ. TIK-Report 103. May 2001.
Descargas
Publicado
2013-07-01
Número
Sección
Artículos
Cómo citar
1.
Solución al Problema de Ruteo de Vehículos Empleando Algoritmo Genético. ingeniare [Internet]. 2013 Jul. 1 [cited 2025 Feb. 23];(15):31-43. Available from: https://revistas.unilibre.edu.co/index.php/ingeniare/article/view/599
