Problema de ruteo para flota de vehículos heterogénea con ventanas de tiempo y múltiples orígenes y destinos

Abstract

En el presente trabajo se estudia la problemática actual de una empresa estatal, la Administración Nacional de Correos. Se trata de un problema de planificación de rutas de un grupo heterogéneo de vehículos que deben pasar por ciertos puntos a recoger paquetes. Los vehículos tienen diferentes capacidades y pueden partir desde orígenes distintos así como pueden finalizar su recorrido en diferentes destinos. Los puntos cuentan con diversas características como ventana de tiempo, prioridad, volumen a ser recogido y restricciones de ciertos vehículos. El objetivo es que los vehículos pasen por la mayor cantidad de puntos, contemplando sus prioridades, y tratando de encontrar la mejor ruta para cada vehículo de manera que la distancia total recorrida sea mínima. Para la resolución de dicho problema se implementaron técnicas de programación genética, mas precisamente, algoritmos evolutivos. El análisis experimental se realizó utilizando un conjunto de instancias del problema construidas en base a coordenadas reales (pertenecientes a puntos válidos de Montevideo) generadas de forma aleatoria y fue comparado frente a un algoritmo ávido. Como adicional al proyecto se presenta un conjunto de servicios desarrollados para la Administración Nacional de Correos la cual se encarga de recibir solicitudes de clientes y se encarga de realizar las peticiones de ejecución al algoritmo evolutivo. El trabajo realizado abre la puerta a futuras investigaciones sobre el estudio de métodos de resolución eficientes para problemas de índole similar.