La metaheurística de Búsqueda Tabú aplicada al problema de Enrutamiento de Vehículos

Abstract

En el presente trabajo se lleva a cabo el estudio del problema de enrutamiento de vehículos (conocido como VRP) repasando sus variantes más significativas. Este problema de optimización combinatoria, de gran interés en la Industria, es difícil de tratar computacionalmente. Por ello para su resolución se han venido empleado muy diferentes técnicas, siendo las metaheurísticas, y en particular la búsqueda tabú, de las más exitosas. Por ello, se incluye el estudio de los algoritmos utilizados en la resolución del VRP, con especial hincapié en los de búsqueda tabú. Se ha seleccionado la búsqueda tabú granular, junto con la heurística de Clark y Wright, para la presentación de una explicación pormenorizada detallando su estructura paso a paso aplicada al VRP clásico y la resolución de un ejemplo, para su mejor comprensión. Además, la búsqueda tabú granular se ha implementado en Python y, con el programa creado, se han resuelto varios casos.