Solving Large Scale Crew Scheduling Problems with Constraint Programming and Integer Programming
Abstract: We consider several strategies for computing optimal solutions to large scale crew scheduling problems, which are known to be notoriously difficult combinatorial optimization problems. Provably optimal solutions for very large real instances of such problems were computed using a hybrid approach that integrates mathematical and constraint programming techniques. A declarative programming environment was used to develop the constraint based models. The declarative nature of such an environment proved instrumental when modeling complex problem restrictions and, particularly, in efficiently searching the very large space of feasible solutions. The code was tested on real problem instances, stemming from the operation of two bus lines of a typical Brazilian transit company that serves a major urban area. Some of those instances contained an excess of $1.8 \times 10^9$ entries and could be solved to optimality in an acceptable running time when executing on a typical desktop PC.
Resumo: Neste texto, problemas de grande porte para escalonamento de mão-de-obra são abordados e diversas estratégias de solução são descritas. Tais problemas são reconhecidos como problemas difíceis em Otimização Combinatória e foram resolvidos até a otimalidade. Soluções ótimas comprovadas para instâncias reais e de grande porte são obtidas utilizando-se uma abordagem híbrida que integra técnicas de Programação Matemática e Programação por Restrições. Um ambiente de programação declarativa foi utilizado para se desenvolverem os modelos baseados em restrições. A natureza declarativa deste ambiente mostrou-se valiosa durante a modelagem de restrições complexas do problema e, particularmente, ao se explorar, de forma eficiente, o enorme espaço de soluções viáveis. O código foi testado em instâncias reais do problema oriundas da operação diária de duas linhas de ônibus de uma empresa brasileira de transporte urbano que serve uma grande região metropilitana. Algumas dessas instâncias contêm um número de entradas superior a $1.8 \times 10^9$ e puderam ser resolvidas até a otimalidade em um microcomputador pessoal típico, em um tempo de computação aceitável.
1999