[en] The complex problem of assigning duties to public transport drivers is the fourth and last phase in which the problem is usually divided. It is a scheduling problem well known in the business world, due to the fact that crews work in rotating shifts. The three phases that precede the above mentioned problem are widely studied and mechanized by the majority of the large transport companies. However, the rostering problem is complicated by each country's use of this phase and to the labour agreements of each company. It makes a universal solution practically impossible. This thesis presents an approach to the requirements imposed by some of the main Spanish companies. It confirms this fact by establishing that distinct and contradictory restrictions exist among companies. In many cases the imposed restrictions are the result of historically acquired rights and are difficult to change. Nevertheless, it is feasible to improve the assignment without violating any of the imposed requirements. In short the present thesis raises the question of how to improve the situation. It details a procedure that is supported in lineal programming techniques and a greedy heuristic. Finally the thesis presents a general problem where only criteria of equity are imposed in the sense of seeking solutions that better distribute the workload and the days-off. Seeking to solve the problem has led to a new procedure that is divided into two phases: constructions of patterns and roster construction. The construction of the patterns requires short cycles, leading to an innovation that summarizes two alternative strategies that dynamically modify an Integer lineal program and displays the different solutions, or short cycle patterns that cover perfectly the drivers' demands. The roster elaboration is approached and solved satisfactorily by means of a GRASP algorithm, which raises a mixed lineal programs sequence that give the lower band of the assignments presented. With this information one arrives at different solutions from which the local search is carried out. Examples with real data have been processed, the data coming from existing companies. The results spectacularly reduce the differences observed in the present driver workload distribution.

[es] La asignación de los conductores es la cuarta y última fase de las cuatro etapas en que se suele dividir el complejo problema de la organización de servicios en una empresa de transporte terrestre regular. Se encuadra dentro de lo que se conoce como problema de rostering ya que se concreta en la elaboración de turnos de trabajo rotativo. Así como las tres etapas que preceden al rostering son problemas ampliamente estudiados y mecanizados en la mayor parte de las grandes compañías de trasporte, el problema de rostering plantea peculiaridades debidas a los usos de cada país y a los convenios laborales de cada empresa que hace prácticamente imposible una solución universal. La tesis presenta un acercamiento a los requisitos impuestos en algunas de las principales compañías españolas y ratifica este hecho mediante la constatación de que existen restricciones no sólo distintas sino contradictorias entre compañías. En muchos casos las restricciones impuestas son fruto de unos derechos adquiridos históricamente y en consecuencia difíciles de cambiar, cabe no obstante preguntarse si es posible mejorar la asignación que se está haciendo actualmente sin violar ninguno de los requisitos impuestos. Como respuesta, el presente trabajo plantea el cómo mejorar una situación concreta, para ello elabora un procedimiento que apoyado en técnicas de programación lineal y una heurística greedy mejora la actual asignación notablemente. Por último plantea un problema genérico donde sólo se imponen criterios de equidad en el sentido de tratar de buscar aquellas soluciones que mejor repartan la carga de trabajo y los días libres. Para resolverlo aporta un nuevo procedimiento que se divide en dos fases: construcción de patrones y construcción de listas de tareas. En la construcción de los patrones se exige que estos sean de ciclo corto, lo cual lleva a la innovación de un procedimiento que concretado en dos estrategias alternativas modifica de forma dinámica un programa lineal entero y va presentando las distintas soluciones o patrones de ciclo corto que cubren perfectamente la demanda de conductores solicitada. La elaboración de listas de tareas se aborda y resuelve satisfactoriamente mediante una heurística GRASP, la cual plantea una secuencia de programas lineales mixtos que dan la cota inferior de las asignaciones planteadas, con dicha información se van construyendo las distintas soluciones a partir de las cuales, posteriormente se lleva a cabo la búsqueda local. Se han procesado ejemplos con datos reales facilitados por algunas compañías y los resultados obtenidos reducen espectacularmente el desequilibrio observado en la carga laboral actual entre conductores.