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.
Esta es una versión de prueba de citación de documentos de la Biblioteca Virtual Pro. Puede contener errores. Lo invitamos a consultar los manuales de citación de las respectivas fuentes.
Artículo:
Estudio comparativo de flujo de fluido a través de una placa de orificio usando las ecuaciones de Stokes y de Navier-Stokes
Artículo:
Modelo teórico del rendimiento de la bomba de anillo líquido basado en el ciclo de funcionamiento real
Artículo:
Características de fluidización de suspensiones de fibra de pulpa de consistencia media-alta con un impulsor
Artículo:
Un nuevo enfoque para evaluar las ventajas del tratamiento de la carcasa en compresores axiales
Artículo:
Modelización numérica de una hélice marina sometida a movimientos de oleaje y oscilación
Libro:
Metodología del marco lógico para la planificación, el seguimiento y la evaluación de proyectos y programas
Presentación:
Estudio de movimientos y tiempos
Artículo:
Estudio sobre la evaluación de la sostenibilidad de los productos innovadores
Software:
Simulación del proceso de extracción sólido-líquido EXTSL