Resumen

El Problema de ruteo de vehículos sobre arcos con punto de inicio/fin variable (Open Capacitated Arc Routing Problem - OCARP), en su versión clásica, busca determinar la mejor estrategia para servir un conjunto de clientes localizados en los arcos de una red usando vehículos. A diferencia del Capacitated Arc Routing Problem (CARP), el OCARP no tiene las restricciones que aseguran que cada vehículo debe iniciar y terminar su ruta en un vértice dado (también conocido como depósito). El objetivo de este trabajo es proponer una heurística para encontrar la frontera eficiente dados dos objetivos: minimizar el número de vehículos y minimizar el costo total. Adicionalmente se propone complementar la heurística, la cual es basada en algoritmos genéticos, con operadores de inteligencia artificial.

1 INTRODUCCIÓN

El problema de ruteo de vehículos sobre arcos (CARP, por sus siglas en inglés) busca determinar qué vehículo y en qué secuencia se debe visitar un conjunto de arcos, definidos sobre un grafo, a los cuales se busca prestar algún servicio, minimizando una o varias funciones de costo. Este trabajo considera la situación en la cual los vehículos no necesariamente salen (o llegan) del depósito y tiene libertad de escoger el punto de inicio (o terminación) de acuerdo a decisiones bi-objetivo. Debido a que la complejidad del problema crece exponencialmente según el tamaño del grafo, en este documento se presenta un método de solución basado en Algoritmos Genéticos (AG) en el que se utiliza algoritmos de inteligencia artificial para mejorar la evolución de los individuos.

La estructura de este artículo es la siguiente: en la sección 2 se establece cuál es el problema y cómo ha sido el trabajo previo desarrollado por otros autores. En la sección 3 se describe formalmente en problema. En la sección 4 discuten las estrategias de solución trabajadas. Y finalmente, en las secciones 5 y 6 se describe el proceso de experimentación y análisis de resultados.

2 REVISIÓN DE LA LITERATURA

El CARP fue propuesto en 1981 [1] como un problema de optimización combinatoria, en el que dado un grafo G(V,A) no dirigido se busca determinar un conjunto de rutas que deben seguir un número fijo de vehículos de tal manera que se minimice la distancia total recorrida. Los arcos pueden ser clasificados en dos: arcos obligatorios y arcos de paso. Los arcos obligatorios son aquellos que tienen una demanda que debe ser satisfecha y por tanto deben ser visitados, mientras que los arcos de paso son visitados como medio de conexión entre otros dos arcos obligatorios. Todos los arcos cuentan con una distancia la cual debe ser recorrida cuando es visitado por un vehículo. Por otra parte, los vehículos son considerados iguales y tienen una capacidad máxima.

• Materias:Logística Algoritmos genéticos Redes neuronales (Computadores) Técnica heurística Tiempos y movimientos
• Subjects:Logistics Genetic algorithms Neural networks (Computer science) Metaheuristic technique Predetermined motion time systems
• Palabras claves:Algoritmo genético; Algoritmo memético; Optimización multiobjetivo; CARP; OCARP; MO-OCARP; Redes neuronales; Búsqueda local; Ruteo de vehículos sobre arcos.
• Keywords:Genetic algorithm; Memetic algorithm; Multi-objective optimization; CARP; OCARP; MO-OCARP; Neural networks; Local search.