Formulación y evaluación de un algoritmo, basado en la meta-heurística "búsqueda tabú" para la optimización del ruteo de vehículos con capacidad

Abstract

El algoritmo desarrollado, es una herramienta que permite la solución del problema de ruteo de vehículos con capacidad. Este utiliza la metodología Búsqueda Tabú para la optimización de las rutas, apoyada en la técnica Clarke and Wright para la creación de la ruta inicial y en la técnica Lin-Kernighan para la construcción del vecindario. En la Búsqueda Tabú también se implementan las estrategias de Intensificación y Diversificación para explorar mejor el espacio de soluciones y hallar soluciones cercanas a las óptimas, evitando caer en óptimos locales. El problema de CVRP o problema de Ruteo de Vehículos con capacidad es una variante del TSP (Traveling Salesman Problem) que se caracteriza por la existencia de una flota de vehículos que debe satisfacer la demanda de los clientes en una sola visita. Además cada vehículo tiene una capacidad limitada y debe regresar al depósito al término de la secuencia trazada para él. En este tipo de problema de ruteo se debe considerar la demanda de cada cliente y la capacidad de cada vehículo. Todos los itinerarios comienzan y terminan en el depósito común. El algoritmo ideado fue implementado en un programa de computadora, desarrollado en la plataforma Java, a través del cual se calculan las soluciones dependiendo de ciertos parámetros iniciales como: Número de Iteraciones, Tamaño de la Lista Tabú, Tamaño de la Población y Número de Intercambios. Dicho programa arroja la mejor ruta encontrada y su debida descripción que incluye: Costo (Unidades de Distancia), Parámetros iniciales (Número de Iteraciones, Número de Intercambios, Capacidad de los Vehículos), la secuencia en la cual deben ser atendidos los clientes con sus respectivos datos (Coordenada en X, Coordenada en Y, Demanda). Como es posible observar, el problema del Ruteo de Vehículos tiene su aplicación más directa en el área Logística de cualquier organización. Los estudios realizados acerca de éste datan de 1920, a pesar de la simplicidadfl de su enunciado, el reto de científicos y estudiantes en el área de la optimización consiste en encontrar mejores rutas en tiempos más cortos. Lo anterior implica un gran esfuerzo en el desarrollo de nuevas metodologías más efectivas, apoyadas en la tecnología para alcanzar el objetivo. El proyecto está dirigido hacia el sector de la investigación a nivel universitario, específicamente en el área de logística e investigación de operaciones, con el propósito que éste pueda ser utilizado como un punto de partida para futuras generaciones interesadas en esta rama del conocimiento.