Clustering : aplicación a ruteo de vehículos

Abstract

Este trabajo pertenece al Taller V de la Facultad de Ingeniería de la Universidad de la República Oriental del Uruguay, y esta planteado dentro del Departamento de Investigación Operativa del Instituto de Computación. El mismo se divide en dos partes: Investigación y Desarrollo. Como resumen de la investigación se ofrece una reseña del Clustering actual. Para ello se estudiaron los métodos y se clasificaron los diversos algoritmos existentes. El objetivo del Clustering es ordenar los datos en grupos o clusters a través de un criterio de similitud de tal forma que el grado de asociación sea fuerte entre los miembros del mismo cluster y débil entre los miembros de clusters distintos. Cada cluster entonces, describe en término de datos relevados, la case a la cual sus miembros pertenecen. Dentro de los métodos existentes para clusterizar destacamos los de clustering jerárquico, de particionamiento y basado en grafos. En particular, se trabajó con el método de particionamiento, centrando nuesto trabajo en el estudio, implementación y comparación de los siguientes algoritmos: KNN, K-Means y PAM. Este estudio resulta particularmente importante debido a que estas técnicas de clustering nunca fueron aplicadas como preprocesamiento de datos para un problema de ruteo de vehículos con múltiples depósitos y restricciones de ventanas de tiempo. Como resultado del proceso de desarrollo de software se presenta la implementación de los algoritmos de clustering arriba mencionados aplicados al preprocesamiento de un problema de ruteo de vehiculos con múltiples depósitos y restricciones de ventanas de tiempo, aportando un nuevo punto de vista a la resolución de este tipo de problemas. También se ofrecen conclusiones y comparaciones de los tres algoritmos implementados mostrando sus debilidades y fortalezas al aplicarlos en la resolución de este problema puntual.