Solution to Vehicle Routing Problem with Genetic Algorithm

Solución al Problema de Ruteo de Vehículos Empleando Algoritmo Genético

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 obtenidos históricamente hasta la fecha y los obtenidos en el desarrollo de este artículo.

1. INTRODUCCIÓN

El Problema de Rutas de Vehículos (VRP), que ha sido introducido por Dantzig y Ramser en 1959 [1], se basa en minimizar el coste de distribución de la mercancía desde un almacén a un conjunto de clientes. El Problema de Rutas de Vehículos (VRP) puede entenderse como la relación o intersección de dos problemas de optimización combinatoria bien conocidos. El primero, el Problema del Vendedor Viajero (TSP), que considera la capacidad de cada coche como infinita, y el Problema de Embalaje de Contenedores (BPP) [2].

El interés de este problema proviene de dos causas principales. Por un lado, el VRP es un problema de alto interés académico debido a su dificultad (es un problema NP-duro, lo que nos indica que la resolución de este problema busca exhaustivamente todas las combinaciones posibles ya que la mejor solución no es posible de ser alcanzada en un tiempo razonable útil para el problema) [3], que incluye restricciones, y la multitud de variantes existentes. Por otro lado, tiene una aplicación directa a la realidad, siendo aplicable a grandes empresas de logística y distribución (periódicos, alimentación) [4].

El "AG es un método de búsqueda global estocástica que imita la metáfora de la evolución biológica natural. El AG opera sobre una población de soluciones potenciales aplicando el principio de supervivencia del más apto para producir (con suerte) aproximaciones cada vez mejores a una solución" [5].

La idea general de este trabajo se basa en la búsqueda de soluciones a las instancias clásicas del problema VRP E-n33-k4, B-n41-k6, F-n45-k4, que han sido desarrolladas por Christofides [6], como el problema de Bench-marking por ejemplo.

Teniendo en cuenta lo anterior, es evidente que los algoritmos genéticos son útiles para optimizar los problemas VRP para este caso concreto, ya que proporcionan las soluciones óptimas más cercanas a las ofrecidas por la heurística simple. Sin embargo, este será el caso de estudio.