Recorrido óptimo de la recolección de los desechos urbanos en el sector de Betania - Bhana Hafeji, Fezel, (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.