Solution to Vehicle Routing Problem with Genetic Algorithm
DOI:
https://doi.org/10.18041/1909-2458/ingeniare.15.599Keywords:
Genetic algorithm, VRP, Linear programming, HeuristicsAbstract
This paper compares two methods to solve the classic problem of vehicle routing (VRP), well known for its acronym in English (Vehicle Routing Problem), introduced by Dantzig and Ramser in 1959, which is to minimize the cost to distribute the goods from one warehouse to a set of clients, which uses an accurate method of linear programming and goal heuristic based on genetic algorithms. The object of comparison is the benchmark problem developed by Christofides (1976). In the comparison will be considered historically the best results to date and those obtained in the development of this paper
Downloads
References
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.
Downloads
Published
2013-07-01
Issue
Section
Artículos
How to Cite
1.
De la Hoz Domínguez E, Peña Segura K, Mendoza Mendoza A. Solution to Vehicle Routing Problem with Genetic Algorithm. ingeniare [Internet]. 2013 Jul. 1 [cited 2025 Apr. 11];(15):31-43. Available from: https://revistas.unilibre.edu.co/index.php/ingeniare/article/view/599
