How can we find the best garbage collection route?

Authors

DOI:

https://doi.org/10.22201/cuaieed.16076079e.2024.25.1.12

Keywords:

Graph theory, Garbage collection, Optimal path, Algorithm, Eulerian graph

Abstract

Facing the challenge of optimizing garbage collection in the Rosarito neighborhood, Los Cabos, Mexico, we utilized tools from Graph Theory to model and solve the problem. We constructed a graph representing the street layout and applied the Fleury algorithm, modified to minimize U-turns. Without a Eulerian graph, we added edges to ensure complete routes and employed the Kruskal algorithm to obtain a minimum-weight spanning tree. Results reveal an optimal route with a reduced distance of 0.695 km compared to the current route, leading to a significant annual savings of approximately 108,718 km. The proposal eliminates avoidable U-turns, enhances collection efficiency, and holds potential applications in other urban logistics contexts.

Author Biographies

Omar Martínez Cano, Instituto Tecnologico de Estudios Superiores, Los Cabos

Es ingeniero industrial egresado del ites Los Cabos y licenciado en matemáticas por la unadm. Con más de 10 años de experiencia docente en nivel universitario en el área de matemáticas del Instituto Tecnológico de Estudios Superiores de Los Cabos. Ha participado en la elaboración e impartición de cursos de matemáticas y de enseñanza de las matemáticas para la actualización docente. Tiene como interés el desarrollo social, por tanto, ha impartido cursos a alumnos y docentes pertenecientes a la educación básica, con la intención de fomentar el gusto por las matemáticas en edades tempranas. Actualmente, se desempeña como jefe de la división de Ingeniería Civil en ites Los Cabos.

María del Alba Pacheco Blas, Universidad Nacional Autónoma de México, Facultad de Ciencias

Actualmente labora como Ingeniera de Datos en ids. Estudió la carrera de física en la Facultad de Ciencias, la maestría en Física en el Instituto de Física y el Doctorado en Ciencias e Ingeniería de Materiales en la unam. Realizó un posdoctorado en la Facultad de Química de la unam y otro en la Universidad de Guanajuato, Campus León. Interesada en la remediación de agua de contaminantes metálicos mediante simulaciones computacionales. Ha sido docente en la Facultad de Ciencias de la unam durante 10 años de materias teóricas y experimentales para diversas carreras. Ha impartido cursos en la unadm de manera virtual, principalmente en la carrera de matemáticas. Ha realizado contenido educativo y formado profesores en el bachillerato Pilares y Policial de la cdmx. Es una apasionada divulgadora de la ciencia, ha organizado una gran cantidad de eventos y entrevistas para Laboratorios Facultad de Ciencias unam en Facebook, contenido divulgativo en su canal de Youtube Ciencia Cometa, y es organizadora de los Talleres Navegando con Ciencia

Pilar Valencia Saravia, Universidad Nacional Autónoma de México, Coordinación de Universidad Abierta, Innovación Educativa y Educación a Distancia

Es matemática de la Facultad de Ciencias de la unam, maestra y doctora en Ciencias Matemáticas en la misma institución. Tiene más de 20 años siendo profesora de nivel universitario —en la unam, uam, itam, uia y tese —. Ha participado en la elaboración de contenidos y planes de estudio en la UAM Cuajimalpa, en la Universidad a distancia de México (unadm) y en el Bachillerato a distancia de la unam (B@UNAM). También ha participado en la creación e impartición de cursos de formación docente. Es instructora externa registrada en la Secretaría del Trabajo y Previsión Social (stps) y ha impartido cursos en empresas para el desarrollo de habilidades matemáticas para el trabajo. Actualmente es Jefa del Departamento de Planes y Programas de Estudio en el Área de físico-matemáticas y de las ingenierías de la Subdirección de planes y programas de estudio de la cuaieed en la unam.

References

Chartrand, G., Lesniak, L., y Zhang, P. (2010). Graphs & Digraphs. En Chapman and Hall/CRC eBooks. https://doi.org/10.1201/b14892.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms, third edition. mit Press. https://pd.daffodilvarsity.edu.bd/course/material/book-430/pdf_content.

Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical society, 7(1), 48-50. http://5010.mathed.usu.edu/Fall2018/THigham/Krukskal.pdf.

Martínez Cano, O. (2021). Uso de la Teoría de Gráficas para optimizar la ruta de recolección de basura en la colonia Rosarito del municipio de Los Cabos. [Tesis de licenciatura, en proceso de publicación]. Universidad Abierta y a Distancia de México, unadm.

Wikipedia. (2021, 4 de diciembres). Discusión: problema de los puentes de Königsberg. https://goo.su/YCUxsd.

Published

2024-01-25

Issue

Vol. 25 No. 1 (2024): El inexorable tiempo: un viaje de 24 años hacia el conocimiento

Section

Varietas

License

Copyright (c) 2023 Revista Digital Universitaria

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Licencia Creative Commons
Revista Digital Universitaria es editada por la Universidad Nacional Autónoma de México se distribuye bajo una Licencia Creative Commons Atribución-NoComercial 4.0 Internacional. Basada en una obra en http://revista.unam.mx/.