Session: Workforce Scheduling Set Covering

Session: Workforce Scheduling
Set Covering/Partitioning Models for the Vehicle and
Crew Scheduling Problem
Marta Mesquita 1,(a)
[email protected]
Ana Paias 2,(a)
[email protected]
1
Instituto Superior de Agronomia, Universidade Técnica de Lisboa
Tapada da Ajuda, 1349-017 Lisboa, Portugal
and Centro de Investigação Operacional – FCUL
2
Universidade de Lisboa, Faculdade de Ciências, DEIO
BLOCO C6, Piso 4, 1749-016 Lisboa, Portugal
and Centro de Investigação Operacional – FCUL
Abstract
Vehicle and Crew Scheduling problems are important combinatorial optimization problems that
arise in the planning process of Mass Transit Companies. Traditionally, due to their complex
nature, these problems have been dealt with separately and sequentially.
In this talk we present an approach for solving the two problems simultaneously. Integer linear
programming formulations incorporating both the multi-depot vehicle scheduling problem and
the crew scheduling problem are stated. For each formulation, two sets of variables are
considered: scheduling variables that establish the assignment between compatible trips and
between trips and the depots; variables associated with the feasible duties for the crews. Since,
for real life applications, the set of feasible crew duties become too large to be considered
explicitly, we solve the linear relaxations of the models by a column generation scheme.
Actually, the columns corresponding to the duties can be seen as paths in an adequate network
and are generated as needed by solving shortest path problems with resource constraints.
Whenever the resulting solution is not integer we obtain a solution for the integer problem using
branch and bound techniques over a subset of feasible duties for the crews. A heuristic
procedure, based on the optimal solution of the Vehicle Scheduling Problem without
requirement that vehicles return to the source depot, is used to obtain the initial set of crew
duties.
Computational experience, with random generated and real life data publicly available for
benchmarking on the WEB, is reported.
Keywords: Integer Linear Programming, Vehicle Scheduling, Crew Scheduling.
(a) Supported by POCTI-ISFL-1-152