🤖 AI

Integrating Column Generation and Large Neighborhood Search for Bus Driver Scheduling with Complex Break Constraints

Este artigo apresenta e avalia uma abordagem híbrida que integra a Geração de Colunas e a Busca em Vizinhança de Grande Escala para resolver o Problema de Agendamento de Motoristas de Ônibus com restrições complexas de intervalo, alcançando resultados de última geração em instâncias de diversos tamanhos.

Autores originais: Lucas Kletzander, Tommaso Mannelli Mazzoli, Nysret Musliu, Pascal Van Hentenryck

Publicado 2026-04-23

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Lucas Kletzander, Tommaso Mannelli Mazzoli, Nysret Musliu, Pascal Van Hentenryck

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você é o gerente de uma grande empresa de ônibus. Sua tarefa diária é um quebra-cabeça gigante: você tem dezenas de rotas de ônibus que precisam ser percorridas e uma equipe de motoristas. Seu objetivo é criar os "turnos" (os horários de trabalho) para cada motorista de forma que:

Nenhuma rota fique sem motorista.
O custo seja o menor possível (menos motoristas, menos horas extras).
Os motoristas fiquem felizes (não trabalhem demais, tenham pausas para comer, não troquem de ônibus a cada 5 minutos e tenham horários que combinem com a vida pessoal).

O problema é que as leis e os acordos sindicais são extremamente rígidos. Um motorista não pode dirigir por mais de 4 horas sem parar, precisa de pausas específicas dependendo de quanto tempo trabalhou, e certas pausas são pagas ou não pagas dependendo de quando elas acontecem no turno.

Este artigo é como um manual de como os autores criaram um "super-gerente" de computador para resolver esse quebra-cabeça de forma brilhante. Eles combinaram duas estratégias diferentes para vencer o problema.

Aqui está a explicação simples, usando analogias do dia a dia:

1. O Problema: O Quebra-Cabeça Infinito

Pense em cada trecho de viagem de ônibus como uma peça de Lego. Você tem que encaixar essas peças nas mãos dos motoristas. Mas as regras são chatas:

"Você só pode pegar 3 peças seguidas antes de fazer uma pausa de 30 minutos."
"Se você fizer uma pausa de 3 horas, isso conta como um dia de trabalho separado."
"Não pode trocar de ônibus no meio do caminho, a menos que seja muito necessário."

Se você tentar montar isso na mão, vai ficar louco. Se tentar usar um computador simples, ele vai demorar anos para achar a solução perfeita.

2. A Estratégia 1: O Arquiteto Perfeccionista (Branch and Price)

Os autores primeiro criaram um método chamado Branch and Price (B&P).

A Analogia: Imagine um arquiteto que quer construir a casa perfeita. Ele desenha um plano, depois divide a casa em cômodos, depois em paredes, e assim por diante. Em cada passo, ele verifica se o plano é possível.
Como funciona: O computador tenta encontrar a solução matematicamente perfeita. Ele cria milhões de possibilidades de turnos e descarta as ruins.
O Resultado: Para cidades pequenas (poucos ônibus), esse método é incrível. Ele encontra a solução perfeita em segundos. Mas, se a cidade for gigante (muitos ônibus), o computador fica sobrecarregado, como um cérebro tentando resolver um labirinto de 1 milhão de caminhos ao mesmo tempo. Ele demora demais.

3. A Estratégia 2: O Detetive Criativo (Large Neighborhood Search - LNS)

Para cidades grandes, eles usaram uma segunda estratégia chamada Large Neighborhood Search (LNS).

A Analogia: Imagine que você já tem um roteiro de viagem pronto, mas não é o melhor. O LNS é como um detetive que diz: "Vamos apagar 10% do roteiro atual e tentar reinventar essa parte do zero, de forma criativa".
O "Destruidor" e o "Consertador":
- Destruidor: O computador escolhe aleatoriamente alguns motoristas e "demite" seus turnos atuais (destrói a solução).
- Consertador: Ele usa o "Arquiteto Perfeccionista" (o método B&P) apenas para resolver aquele pequeno pedaço do problema que foi destruído. Como o pedaço é pequeno, o Arquiteto resolve rápido e cria um turno melhor.
- Repetição: Ele faz isso milhares de vezes, melhorando o roteiro aos poucos.

4. A Grande Inovação: A Colaboração (Integração)

Aqui está a parte genial do artigo. Antes, o "Detetive" (LNS) jogava fora tudo o que aprendia a cada vez que consertava um pedaço. Era como jogar fora as peças de Lego que você já encaixou bem.

Os autores criaram uma integração estreita:

A Biblioteca de Ideias (Armazenamento de Colunas): Quando o "Consertador" cria um turno incrível para um pequeno grupo de motoristas, ele guarda esse turno em uma "biblioteca". Da próxima vez que precisar consertar outro grupo, ele olha na biblioteca: "Ei, já fizemos um turno parecido com esse antes? Vamos usar!" Isso economiza tempo e evita reinventar a roda.
O Supervisor de Fundo (Background Solver): Enquanto o "Detetive" trabalha no turno principal, um segundo computador (um supervisor de fundo) fica olhando para a "biblioteca" inteira de turnos que foram criados até agora. Ele tenta montar a melhor solução global possível usando todas aquelas peças guardadas. Se ele achar algo melhor, ele avisa o Detetive: "Ei, parei de olhar e encontrei uma solução melhor! Vamos usar essa agora!"

5. O Resultado Final

Ao combinar essas técnicas, os autores criaram o melhor sistema já visto para esse problema:

Para cidades pequenas: O "Arquiteto Perfeccionista" resolve tudo sozinho, garantindo a solução perfeita.
Para cidades grandes: O "Detetive Criativo" com a "Biblioteca de Ideias" e o "Supervisor de Fundo" encontra soluções quase perfeitas muito rapidamente, superando todos os métodos anteriores.

Em resumo: Eles ensinaram ao computador a não jogar fora as boas ideias que ele teve no passado e a ter um "olho extra" que vigia o progresso global enquanto ele trabalha nos detalhes. Isso permite que as empresas de ônibus economizem dinheiro e, o mais importante, ofereçam turnos mais justos e menos estressantes para os motoristas.

Título: Integração de Geração de Colunas e Busca em Vizinhança Grande para o Agendamento de Motoristas de Ônibus com Restrições Complexas de Pausas

1. Problema Investigado

O artigo aborda o Problema de Agendamento de Motoristas de Ônibus (BDSP - Bus Driver Scheduling Problem). O objetivo é atribuir turnos (shifts) a motoristas para cobrir uma série de viagens de ônibus pré-agendadas, minimizando custos operacionais e maximizando a satisfação dos motoristas.

Características e Desafios Específicos:

Restrições Legais e Coletivas: O problema segue o acordo coletivo austríaco para provedores de ônibus privados, que impõe regras rigorosas.
Restrições Complexas de Pausas: Diferente de problemas tradicionais, este exige pausas frequentes que podem ser divididas em múltiplos partes (ex: três pausas de 15 min ou duas de 20 min).
Tipos de Pausas: Distinção entre pausas pagas e não pagas, dependendo da posição no turno (ex: pausas não pagas não podem ocorrer nos primeiros ou últimos 2-3 horas do turno, com limites máximos de duração).
Objetivo Multi-critério: A função objetivo combina custos (tempo de trabalho pago, tempo total, tempo de viagem passiva) com critérios de satisfação (redução de mudanças de veículo, redução de divisões de turno e pausas não pagas longas).
Escala: Instâncias variam de pequenas (10 tours) a muito grandes (250 tours), com centenas de pernas de viagem.

2. Metodologia Proposta

Os autores propõem uma abordagem híbrida combinando métodos exatos e heurísticos, focando em duas técnicas principais: Branch and Price (B&P) e Large Neighborhood Search (LNS).

A. Branch and Price (B&P) - Método Exato

Utilizado principalmente para instâncias pequenas e médias.

Estrutura: O problema mestre é um Problema de Partição de Conjuntos (Set Partitioning) e o subproblema é um Problema de Caminho Mais Curto com Restrições de Recursos (RCSPP).
O Subproblema (RCSPP): É altamente desafiador devido à alta dimensionalidade (11 recursos a serem rastreados simultaneamente, como tempo de direção, tempo de trabalho, contagem de pausas, etc.).
Otimizações no Subproblema:
- Particionamento do Subproblema: Divisão do RCSPP em três grafos disjuntos baseados no tipo de pausa de 30 minutos (inexistente, não centralizada, centralizada) para simplificar as restrições de dominância.
- Algoritmo de Dominância Aprimorado: Uso de árvores k-d (k-d trees) e caixas delimitadoras (bounding boxes) em uma abordagem de dois estágios para acelerar a eliminação de rótulos não dominados, substituindo a comparação quadrática tradicional.
- Controle de Taxa (Throttling): Mecanismo exponencial para limitar o custo das arestas no início da busca, reduzindo o tamanho do grafo e focando em colunas promissoras.

B. Large Neighborhood Search (LNS) - Método Heurístico

Utilizado para instâncias maiores onde métodos exatos são computacionalmente inviáveis.

Operadores de Destruição (Destroy):
- Seleção uniforme de motoristas.
- Seleção ponderada pelo custo.
- Operador Inovador ( $\omega_{tr}$ ): Remove todos os motoristas que compartilham pelo menos uma viagem (tour) específica. Este operador mostrou-se superior, pois explora a estrutura do problema para recombinações significativas.
Operador de Reparo (Repair): Resolve o subproblema gerado (um BDSP menor) usando Geração de Colunas (CG) no nó raiz, em vez de um B&P completo, para obter soluções de alta qualidade rapidamente.

C. Integração Tightly Coupled (Integração Ajustada)

A contribuição central do artigo é uma integração profunda entre LNS e CG, superando o uso de LNS como uma "caixa preta":

Armazenamento e Reutilização de Colunas (+r): As colunas (turnos) geradas em subproblemas anteriores são armazenadas e reutilizadas para inicializar subproblemas futuros. Isso evita a regeneração de soluções viáveis já conhecidas.
Solver de Fundo (Background Solver) (+b): Um segundo thread executa continuamente a resolução do problema mestre inteiro (Integer Master Problem) utilizando o conjunto global de colunas acumuladas. Se o solver de fundo encontrar uma solução melhor, ela atualiza a melhor solução global imediatamente, permitindo que o LNS continue a partir de um ponto melhorado.

3. Principais Contribuições

Método Exato (B&P) Otimizado: Desenvolvimento de um B&P capaz de resolver instâncias pequenas a médias de forma ótima ou com lacunas (gaps) muito baixas, graças a otimizações no RCSPP de alta dimensionalidade.
Novo Operador de Destruição: Introdução do operador $\omega_{tr}$ (removedor de tours), que explora a estrutura de compartilhamento de veículos para melhorar a eficiência da busca local.
Integração Híbrida Inovadora: Proposta de um framework onde o LNS e a CG trocam informações ativamente (colunas armazenadas e solver de fundo), estabelecendo um novo estado da arte.
Avaliação Abrangente: Análise detalhada de componentes (dominância, throttling, tamanhos de subproblema, adaptividade) e comparação com métodos anteriores (Simulated Annealing, Tabu Search, CMA-SA).

4. Resultados Experimentais

Os experimentos foram realizados em um conjunto de benchmark público com 65 instâncias (tamanhos de 10 a 250 tours).

Desempenho por Tamanho:
- Pequenas Instâncias (< 30 tours): O B&P é superior, encontrando soluções ótimas em segundos.
- Instâncias Médias (30-90 tours): A versão integrada LNS + RB(f) (Reutilização de colunas + Solver de fundo com conjunto completo) supera todos os outros métodos, incluindo o B&P e o estado da arte anterior (CMA-SA).
- Grandes Instâncias (> 100 tours): O método integrado continua a fornecer as melhores soluções, embora a vantagem sobre o B&P puro diminua (já que o B&P falha em encontrar soluções viáveis em tempo hábil para instâncias muito grandes).
Comparação com o Estado da Arte: O método proposto lns+rb(f) superou consistentemente o algoritmo Construct, Solve, Merge, and Adapt (CMA-SA) e outras meta-heurísticas anteriores em todas as faixas de tamanho, estabelecendo um novo recorde de qualidade de solução.
Eficiência: A reutilização de colunas reduziu significativamente o uso de memória no solver de fundo, evitando o acúmulo de colunas subótimas, enquanto o solver de fundo garantiu a melhoria contínua da solução global.

5. Significado e Conclusão

O artigo demonstra que a integração estreita entre métodos exatos (dentro do reparo do LNS) e heurísticas (LNS) pode superar abordagens tradicionais que tratam esses componentes de forma isolada.

Inovação Técnica: A combinação de árvores k-d para dominância em problemas de caminho mais curto com restrições complexas e a arquitetura de "solver de fundo" para LNS são avanços significativos na pesquisa operacional.
Aplicabilidade Prática: O método lida com restrições realistas e complexas (acordos coletivos detalhados) que são frequentemente simplificadas em outros estudos, tornando-o altamente relevante para operadores de transporte público.
Generalidade: Embora focado no BDSP austríaco, as técnicas de otimização de RCSPP de alta dimensionalidade e a integração LNS-CG são generalizáveis para outros problemas de agendamento de pessoal e otimização combinatória complexa.

Em resumo, o trabalho estabelece um novo padrão de qualidade para o agendamento de motoristas de ônibus, provando que a sinergia entre busca local inteligente e geração de colunas reutilizável é a chave para resolver problemas de escala industrial com restrições complexas.