Diseño de jornadas laborales de conductores y coloreo por listas en grafos

Abstract

En este trabajo abordamos el problema de diseñar las jornadas laborales de los conductores en empresas de transporte público de pasajeros. Estas empresas tienen adjudicados viajes que deben garantizar. Para ello, asignan diariamente a cada conductor de su planta los viajes a realizar, de forma de satisfacer las restricciones que imponen los convenios laborales existentes y la política de la empresa. El objetivo es minimizar la cantidad de horas extras necesarias. Este problema lo modelamos como problema de Coloreo por Listas en Grafos con ciertas restricciones adicionales. Desarrollamos una formulación como Programa Lineal Entero. Evaluamos su performance, con la finalidad de mostrar la superioridad del mismo con respecto a los existentes en la literatura. Luego, diseñamos una heurística constructiva y una heurística de mejora que hacen uso del modelo propuesto, obteniendo una solución que mejora significativamente la utilizada actualmente por una empresa, correspondiente a una instancia con 818 viajes.