Hiperheurística para el problema del transporte multi-depósito con ventanas de tiempo.

Hoy en día, una gran parte de los problemas de distribución de bienes consiste básicamente, en asignar una ruta a cada vehículo de una flota para repartir o recoger mercancías, lo cual constituye un conjunto de problemas habituales que no se resuelven de manera óptima y causan una merma significativa en los ingresos de las empresas. Hacer una buena planeación de ruteo vehicular requiere de herramientas tecnológicas precisas que logren un mejor aprovechamiento de la flota en términos de su capacidad de transporte y, por consecuencia, un mejor nivel de servicio. El diseño de rutas eficientes permite definir el número de vehículos que serán utilizados para visitar un número importante de clientes (destinos), es un factor crítico que afecta de manera considerable la logística y la competitividad de muchas compañías. El problema tratado en esta tesis doctoral se le conoce como el problema de ruteo vehicular con capacidades homogéneas (CVRP por sus siglas en inglés Capacitated Vehicle Routing Problem) en el cual, cada cliente tiene una demanda que es conocida y no se puede dividir y es atendida por un único vehículo. Cada uno de los clientes es un nodo de una red, para conectar a los clientes, geográficamente dispersos, se tienen arcos (arista) los cuales son no dirigidos. Cada arco tiene asociado un costo (positivo). Se cuenta con un número K de vehículos disponibles los cuales tienen una capacidad limitada Q. El objetivo es determinar la ruta para cada uno de los vehículos, los cuales parten del depósito y deben regresar a él de tal forma que se minimicen los costos y se satisfagan las demandas de todos los clientes. Se considera una serie de restricciones entre las que destacan, que los vehículos no pueden exceder su capacidad ni visitar a un cliente dos veces. Para tratar este problema se proponen dos algoritmos, un algoritmo de recocido simulado secuencial apoyado en una estructura híbrida de vecindad y con reinicio como mecanismo de exploración y explotación del espacio de soluciones. El otro algoritmo es el de recocido simulado distribuido también con reinicio y una estructura híbrida de vecindad, el cual fue desarrollado con la librería de “Paso de Mensajes (MPI)”. Los algoritmos desarrollados se ejecutan de manera secuencial y distribuida en CPU y en el clúster Cuexcomate respectivamente. Fueron evaluados utilizando un conjunto de instancias obtenidas de la literatura para el CVRP. Los resultados obtenidos fueron muy cercanos a los óptimos reportados en el estado del arte y en algunos casos se igualó a éstos. En la metodología experimental, se utilizaron instancias pequeñas (de 32 a 150 clientes) para evaluar el desempeño del algoritmo secuencial. Para el algoritmo distribuido se usaron instancias medianas (de 199 a 261 clientes).

Currently, there are several models that are breaking the paradigms in the design of transport routes, allowing solve problems that have to do with the uncertainty of customer demand. The benefit is the better use of the fleet in terms of transport capacity and, consequently, a better level of the service. The design of efficient routes to define the number of vehicles that will be used to visit a large number of clients (destinations), is a critical factor affecting significantly the logistics and competitiveness of many companies. This fact allows the creation of specific areas, in several companies, dedicated to design their vehicle routing, in order to obtain strategies to reduce the transportation costs, instead of the generation of functions of operational nature. Make a good vehicle routing planning requires precise technological tools. This thesis is focused on the problem known as Capacitated Vehicle Routing Problem (CVRP), which deals with the design a routing from the deposit, where begin and end their tour routes. Vehicles go to visit a set of geographically dispersed customers, whose demand is known. Its goal is to travel the route with minimal cost. Among restrictions, it is important to point out that vehicles cannot exceed their capacity or visit a client twice. To solve this problem, two algorithms are proposed: a sequential simulated annealing algorithm supported by a hybrid neighborhood structure and with restart as a mechanism for exploring and exploiting the solution space. The other algorithm is simulated annealing also distributed with restart and a hybrid neighborhood structure, which was developed with the "Message Passage (MPI)" library. The developed algorithms are executed sequentially and distributed in CPU and in the cluster Cuexcomate respectively. They were evaluated using a set of instances obtained from the literature for the CVRP. Results were very close to the optimal reported. In the experimental methodology, small instances (from 32 up to 150 customers) were used to evaluate the performance of sequential algorithm and medium instances (from 199 up to 261 customers) for the distributed algorithm.