Un método de búsqueda local para el problema de asignación de tripulaciones utilizando algoritmos de grafos

Abstract

Dado un conjunto de viajes entre distintas estaciones, con tiempos de inicio y fin determinados, se plantea el problema de cubrir todos estos viajes utilizando una cantidad mínima de tripulaciones. Estos deben respetar que cada tripulación puede participar solamente en un viaje a la vez, que debe descansar entre cada par de viajes y que debe comenzar los viajes en las estaciones apropiadas. Adicionalmente se impone la restricción de que una vez terminado el período estudiado, los mismos viajes deben volver a realizarse con el mismo número de tripulaciones, por lo que la planificación debe ser compatible con el próximo periodo de tiempo. El problema se modela construyendo un grafo adecuado, donde se plantea un método de búsqueda local que utiliza los algoritmos de camino de peso máximo y de matching bipartito como subrutinas para encontrar soluciones cada vez mejores. Por otro lado, se demuestran dos cotas inferiores a la mínima cantidad de tripulaciones necesarias para resolver una instancia del problema. Una de estas se obtiene gracias a una versión simplificada del problema que puede ser resuelta en tiempo polinomial, mientras que la otra se obtiene al analizar el número mínimo de tripulaciones que se necesita en cada instante de la planificación.