Paper

UCR - A40847

1

Algoritmos genéticos como solución al problema de ruteo de vehículos
Bolaños Solano, Emilia. Estudiante de Ingeniería Industrial, Universidad de Costa Rica
Dadas las condiciones anteriores, se requiere la aplicación de herramientas que permitan obtener la mejor solución dentro del entorno en que se desarrolla el problema; esto quiere decir, la solución más viable, nonecesariamente el óptimo absoluto. La aplicación de modelos metaheurísticos en este caso aporta la flexibilidad necesaria para lograr maximizar la satisfacción del cliente, al tiempo que se logran disminuir los costos y “jugar” con los recursos disponibles (cantidad de vehículos, cantidad de personal, presupuesto, etc.). Esta es una alternativa asequible que puede proporcionar buenas soluciones en unentorno de problemas reales (que por experiencia, vienen a ser también complejos), cuando se cuenta con una posibilidad infinita de soluciones (todas las posibles rutas que se pueden obtener de la combinación de los pueblos a visitar por ejemplo) y cuando además de esto, se cuenta con múltiples objetivos, como se mencionó anteriormente. El problema de ingeniería de rutas, como también es llamado eldiseño de rutas o problema de ruteo de vehículos, consta así del problema donde se deben determinar los recorridos para una flota de vehículos específica que trabajan alrededor de uno o más centros de distribución, y que deben satisfacer a un cierto número de clientes dispersos en una cantidad de lugares. Una solución sencilla de un problema de ruteo de vehículos se puede observar a continuación,donde cada una de las figuras es una ruta escogida, y cada uno de los puntos es un cliente a visitar.

Abstract— The planning of delivery routes based on tools and decision support is becoming increasingly important in all businesses. This article explains the use of genetic algorithms methodology for such planning, its advantages, compared to other types of methodologies and an applied examplethat proves the feasibility of its use in solving such problems. Keywords—Genetic Engineering VRP. Algorithms, Distribution, Routing

Resumen—La planificación de las rutas de distribución basada en herramientas de apoyo a la decisión tiene cada día mayor importancia en todas las empresas. Este artículo explica la utilización de la metodología de Algoritmos Genéticos para realizar dichaplanificación, sus ventajas, su comparación con otros tipos de metodologías y un ejemplo aplicado que comprueba la viabilidad de su utilización en la solución de este tipo de problemas. Palabras Clave—Algoritmos genéticos, Distribución, Ingeniería de Rutas, VRP.

I. INTRODUCCIÓN
A planificación y diseño de rutas de distribución es actualmente una de las trabas más importantes a la que se enfrentan lasempresas en el proceso de comercialización de sus productos. Los enfoques que se desarrollaron hasta hace algunos años se orientaban únicamente a la optimización de un factor: la minimización de la distancia o la disminución de los costos. Pero la realidad actual es otra: nos enfrentamos a problemas con múltiples objetivos, en donde se debe maximizar la satisfacción del cliente trabajando con elmínimo costo posible. Dentro de los fines fundamentales de las empresas hoy día se encuentra el lograr que el proceso de distribución de sus productos sea lo más eficiente posible, brindando al mismo tiempo la mayor flexibilidad para el cliente; para lograr esto, es necesario que la planificación de las rutas en el transporte de sus productos sea correctamente desarrollada.

L

Fig. 1. Soluciónsencilla a un problema de ruteo de vehículos

II. TIPOS DE PROBLEMAS EN EL RUTEO DE VEHÍCULOS Cuando se trata de solucionar un problema de diseño de rutas, se deben tomar dos tipos de decisiones que afectarán directamente la solución que se obtiene:

Trabajo recibido el 16 de noviembre, 2010 B. Emilia. La autora se desarrolla en la Universidad de Costa Rica, en San Pedro de Montes de Oca,...