Recorrido óptimo de la recolección de los desechos urbanos en el sector de Betania - Bhana Hafeji, Fezel; Laguardia Cupertino, José Javier; Jiménez Hidalgo, Iris Marina (Panamá : Universidad Tecnologíca, 2020)
La basura es uno de los grandes problemas que afecta al país, en especial a la ciudad de Panamá, pues, posee grandes debilidades desde su generación, recolección y disposición. En este sentido, la recolección es una de las tareas más complejas y costosas. Sumado a esto, la falta de planificación, escasez de vehículo recolectores, una reducida cuadrilla, alta morosidad por parte de los clientes y un presupuesto asignado que no cumple con la demanda de la recolección de la basura y la falta de interés de las autoridades por buscar otras alternativas a la crisis, agravan la problemática de la recolección de la basura. El objetivo de este trabajo es encontrar una ruta óptima con la finalidad de reducir los costos del consumo de combustible, prolongar la vida útil del vehículo recolector y reducir el tiempo de recolección. La pregunta de la investigación es la siguiente: ¿ Qué recorrido debe realizar el vehículo recolector, de tal forma que, partiendo desde un punto, recorra todas las calles la menor cantidad de veces y termine en el mismo punto, recorriendo la menor distancia posible? Para que exista tal recorrido, el grafo del sector de estudio debe tener en sus vértices (intersecciones de las calles) un grado par de entradas y de salidas. Si todos sus vértices cumplen con dicha condición, el grafo es euleriano y admite un ciclo euleriano, de lo contrario se deben agregar enlaces (aristas / arcos). El planteamiento anterior es modelado por el Problema de Cartero Chino (CPP) para grafos no dirigidos, el problema de Cartero Chino Dirigido (DCPP) para grafos dirigidos y el Problema de Cartero Chino Mixto (MCPP) para grafos mixtos. Como en las calles de Betania - 2 encotramos calles de un solo sentido y de ambos sentidos, el respectivo grafo del sector es un grafo mixto y es resuelto por el MCPP. Para encontrar el valor óptimo (mínimo costo) del recorrido para el MCPP, se utilizará un conjunto de algoritmos; en primer lugar, el algoritmo de Minieka, para encontrar una cota superior por medio de seis etapas; luego si es posible, es mejorada la cota superior con el algoritmo de Floyd - Warshall y al final por medio del algoritmo de Branch and Bound se busca la cota inferior, con la finalidad de encontrar un grafo euleriano óptimo. Una vez encontrado el grafo óptimo, con el algoritmo de Hierholzer se procederá a encontrar un ciclo euleriano. Debido a la topología del sector, el grafo representativo permite la división en subgrafos. Esta alternativa facilita encontrar solución óptima, con la ventaja de reducir las variables a estudiar por cada subgrafo. De los tres subgrafos en que se divide el grafo G, para los subgrafo-1 y subgrafo-3, la costa superior resultó ser la cota óptima y en el subgrafo-2, la cota superior mejorada resultó ser la cota óptima. En niguno de los subgrafos las cotas encontradas fueron mejoradas por el algoritmo de Branch and Bound. La unificación de los tres subgrafos óptimo da como resultado al grafo óptimo final , el cual es un grafo euleriano que admite un ciclo euleriano.
Abstract. Litter is one the biggest problems that affect the country particularly the Panama City. It maintains great weaknesses from its generation, collection and disposal, being the recollection the most complex and costly task. Additionally, the lack of planning, shortage of garbage collection vehicles, limited personnel, delay in payments by customers, a low budget assigned that does not meet the demand of garbage collection and the lack of interest from the authorities to find other solutions to this conflict, worsen the difficuties of the collection of litter. The purpose of this project is to draw an ideal path with the aim of reducing fuel consumption cost, extend operating life of the garbage collection vehicles and reduce the collection time. For this purpose, the investigationquestion is the following: ¿ What path should the collection vehicle follow, in such a way that by starting from a certain point, it can go through all the roads the least amount of times and finishes at the same initial point, covering the less distance possible? To ensure this path, the graph of the study field should have, on its vertices (intersection between the streets) an equal point of entries and exist. If all the vertices follow this condition, the graph is eurelian and support and eurelian cycle,otherwise, new links (edges/arcs) should be added. The previous planning followa the Chinese Postman (CPP) for undirected graphs, the Directed Chinese Postman Problem (DCPP) for directed graphs and the Mixed Chinese Postman Problem for mixed graphs. Since the streets in Betania-2 are one way or both ways, the graph for this area is a mixed graph and is solved by the MCPP. To find the optimal value (lower cost) of the path for the MCPP, a set of algorithms will be used; in first place, the Minieka algorithm, to find an upper bond through six steps; thenif possible, the upper bond is enhanced with the Floyyyyyd-Warshall algorithm; and finally, the lower bond is found through the Branch and Bound algorithm, with the purpose of finding an optimal Eulerian graph. Once the optimal graph is found, proceed with the Hierholzer algorithm to find the Eulerian cycle. Due to the field´s topology the representative graphs allows to the divide it in sub graphs. This alternative enables to find an optimal solution, with the advantage of reducing the variables to study per each sub-graph. From the three sub-graphs in which was divided the graph G; for the sub graph-3, the upper bond was the best; and in the sub graph-2, the improved upper bond proved to be the optimal. In neither of the sub graph, the found bons were improved with the Branch an Bound algorithm. The unification of the three optimal sub graphs results in a final optimal graph, which is an eulerian graph tha follows an eulerian cycle.
Introducción. -- Capítulo I. Planeamiento del problema. -- Capítulo II. Preliminares. -- Capítulo III. Programación y ejecución del modelo. -- Capitulo IV. Resultados.
Tesis (
Incluye referencias bibliográficas, hojas 122-124, apéndice y anexo 125-127.
MINMA
Fezel Bhana Hafeji.
Keywords: Recolección de basuras; Recolección urbana; Algoritmos de grafos; Teoría de grafos; Teoría de grafos eulerianos; Maestría en Ciencias en Ingeniería Matemática