Un acercamiento heurístico multi-objetivo para el problema de distribución de materiales peligrosos con mezcla

Abstract

En el presente trabajo de memoria, se aborda el problema distribución de materiales peligrosos con mezcla. En este se busca asignar rutas a camiones, para que distribuyan los materiales peligrosos a los clientes. Se considera mezcla, porque durante el transporte el camión puede llevar más de un tipo de material peligroso, siempre y cuando estos sean compatibles entre sí. El problema es un problema multi-objetivo ya que, por un lado, se busca minimizar los costos del transporte asociados al proceso de distribución, es decir, abaratar costos. Por otro lado, dado el transporte de materiales que pueden ser riesgosos para la salud de la población se busca minimizar su exposición a posibles reacciones de los materiales peligrosos, debidas a accidentes durante que se puedan dar durante el proceso. Para la resolución del problema, se propone utilizar el algoritmo Greedy para la construcción inicial de las soluciones factibles al problema. Además, para proceso de búsqueda local se propone un algoritmo basado en Tabu Search que incorpora dos movimientos. Estos operadores son 2-OPT e Insert. El movimiento 2-opt se encarga de buscar secuencias de visitas diferentes dado un conjunto de clientes mientras que el operador insert es capaz de modificar el conjunto de clientes visitados por cada ruta. Además, se considera el uso de la lista tabú para impedir ciclos durante el proceso de búsqueda que lleven a re-visitar zonas del espacio de búsqueda ya analizadas. El algoritmo es aplicado a un caso real de la ciudad de Santiago de Chile, la cual es dividida en siete zonas, cada una funcionando de forma independiente. Las instancias solo comparten el depósito desde donde se distribuyen los materiales y salen los camiones de reparto. La data provista considera la información de la red de Santiago de Chile que considera todas las intersecciones como nodos de un gran grafo que es recorrido usando un algoritmo Dijkstra para determinar los mejores caminos entre cada par de nodos y bajo ciertas condiciones de importancia relativa de los dos objetivos. This work studied the problem of distribution of hazardous materials with blending. The problem consists of assigning routes to trucks in order to distribute hazardous materials to customers. It is considered a blending problem, because during transportation trucks can carry more than one type of dangerous material, if they are compatible with each other. On the other hand, the problem is a multi-objective problem because it seeks to minimize the transportation costs associated with the distribution process, that is, reducing costs. On the other hand, given the transportation of materials that may be risky for the health of the population, it is sought to minimize their exposure to possible reactions of hazardous materials due to accidents that may occur during the process. To solve the problem, here we proposed to use the Greedy algorithm for the initial construction of feasible solutions to the problem. In addition, an algorithm based on Tabu Search that incorporates two movements is proposed for the local search process. These operators are 2-OPT and Insert. The 2-opt movement is in charge of searching for different visit sequences given a set of clients, while the insert operator is capable of modifying the set of clients visited by each route. In addition, the use of the tabu list is considered to prevent cycles during the search process that lead to re-visit areas of the search space already analyzed. The algorithm is applied in a real case of the city of Santiago, Chile, which is divided into seven zones, each one operating independently. The instances only share the warehouse from where the materials are distributed and the delivery trucks leave. The data provided considers the information from Santiago, network that considers all intersections as nodes of a large graph that is traversed using a Dijkstra algorithm to determine the best paths between each pair of nodes and under certain conditions of relative importance of the two objectives.