Thesis UN ACERCAMIENTO HEURÍSTICO MULTI-OBJETIVO PARA EL PROBLEMA DE DISTRIBUCIÓN DE MATERIALES PELIGROSOS CON MEZCLA
Date
2021-08
Authors
RUZ ROJAS, ALEXANDER MAXIMILIANO
Journal Title
Journal ISSN
Volume Title
Publisher
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 la 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. Los resultados de las pruebas muestran que el algoritmo es capaz de conseguir un amplio conjunto de soluciones no dominadas para la mayoría de los casos evaluados. Por otro lado, al comparar los resultados con los resultados de un modelo resuelto a través del solver CPLEX 12.8 se observa que los resultados del método heurístico presentan un peor nivel de convergencia que se ve contrarrestado por su capacidad de encontrar soluciones de calidad en gran parte de los frentes.
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. The test results show that the algorithm can achieve a wide set of non-dominated solutions for most of the cases evaluated. On the other hand, when comparing the results with the results of a model resolved through the CPLEX 12.8 solver, it is observed that the results of the heuristic method show a poor level of convergence due to its ability to find quality solutions to a large extent of the Pareto fronts.
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. The test results show that the algorithm can achieve a wide set of non-dominated solutions for most of the cases evaluated. On the other hand, when comparing the results with the results of a model resolved through the CPLEX 12.8 solver, it is observed that the results of the heuristic method show a poor level of convergence due to its ability to find quality solutions to a large extent of the Pareto fronts.
Description
Keywords
ALGORITMOS , SUSTANCIAS PELIGROSAS , TRANSPORTE TERRESTRE