Diseño y aplicación de un algoritmo memético basado en sistema de colonias de hormigas para la resolución del problema VRP en servicios de control metrológico

Abstract

Vivimos en un mundo globalizado, en el que acceder a cualquier tipo de producto o servicio resulta cada vez más sencillo para el consumidor. El abanico de posibilidades de las que dispone crece exponencialmente a medida que se expande el comercio tanto nacional como internacional, fomentado entre otras cosas por la mejora de las redes de transporte, la evolución de los medios de comunicación que dan visibilidad al mundo y la mejora continua en tecnología. Debido a la feroz competencia entre empresas, hoy en día no basta con fabricar o realizar un buen producto o servicio. La gestión logística juega un papel decisivo en la diferenciación entre compañías ya que no solo puede incrementar su competitividad en el mercado al ser capaces de ofrecer productos con menor coste, sino que también pueden aumentar la satisfacción del cliente ofreciendo mayor calidad en el servicio. El Problema de Ruteo de Vehículos o VRP (Vehicle Routing Problem), trata de un problema de optimización combinatoria que ha sido objeto de multitud de estudios en las últimas décadas y que juega un papel de gran importancia en entornos logísticos, ya que una adecuada planificación puede acarrear considerables ahorros. El objetivo del trabajo es introducir y resolver el problema de enrutamiento de vehículos en empresas de control metrológico. Este problema de la vida real, combina múltiples atributos que se distinguen de los introducidos en los problemas tradicionales de enrutamiento de vehículos. Para resolver el problema se ha diseñado un Algoritmo de Colonia de Hormigas hibridado con una búsqueda local, al que llamaremos Algoritmo Memético ACS. A su vez, la búsqueda local es realizada por un algoritmo híbrido basado en un algoritmo de búsqueda en entornos variables en el que se utiliza un algoritmo de búsqueda tabú en el proceso de búsqueda local (VNTS). Finalmente, el algoritmo ha sido evaluado comparándolo con otros algoritmos del estado del arte de la literatura científica y ha sido aplicado con éxito al diseño y planificación de rutas de un caso real de una empresa que presta servicios de control metrológico.

In today’s globalized world, it is easier than ever before for consumers to have access to any product or service of their choosing. The range of possibilities available keeps growing exponentially, as both national and international trade expand, fostered by the improvement of transport networks, the expansion and reach of traditional and social media and the ongoing improvement in technology. Due to fierce competition among companies, nowadays it is just not enough to deliver a quality product or service. Logistics management plays a decisive role in the differentiation of companies. It can not only increase their competitiveness by being able to offer products with lower cost, but it can also increase customer satisfaction by offering higher quality services. The Vehicle Routing Problem or VRP deals with a problem of combinatorial optimization that has been the subject of many studies and plays a role of great importance in logistics environments, since proper planning can lead to considerable savings. The focus of this master’s thesis is to introduce and solve the VPR in metrological control companies. This real-life problem combines multiple attributes that are distinguished from those introduced in traditional vehicle routing problems. To achieve this, it is have been designed an Ant Colony Algorithm hybridized with a local search, which we will call the ACS Memetic Algorithm. In turn, the local search is performed by a hybrid algorithm based on a search algorithm in variable environments in which a tabo search algorithm is used in the local search process (VNTS). Finally, the algorithm has been evaluated comparing it with others from the state of the art in the scientific literature. It has then been successfully applied to the design and planning of routes of a real case of a company that provides metrological control services.