Algoritmo de generación de columnas para la asignación de tareas en el sistema Metrobus-Q

Abstract

In this project, the duty scheduling problem will be addressed in the context of the Trolebús mass transit system. An integer linear programming model based on a set partitioning formulation is presented. This model aims at minimizing the total idle time of drivers in the terminals, while complying to labor agreements and minimizing the number of buses used in the solution. A column generation method is proposed to address the problem. The solution scheme involves solving shortest paths problems with resource constraints, one different subproblem for each type of task path. Due to the large number of variables, we make use of a variable fixing strategy. Finally, a maximum matching model is formulated to join duties that can be done in one block, in a day. Computational results for real instances, covering up to 1400 scheduled trips, are reported.