Ricardo Saldanha, Diretor de Inovação, @SISCOG | 5 min leitura
___________
O DESAFIO
Meses antes do dia das operações, os operadores ferroviários elaboram planos detalhados que especificam como os seus recursos serão aplicados para fornecer o serviço de transporte que desejam oferecer. O plano que define como o material circulante será utilizado nas operações efetuadas na rede é chamado de plano de rotação do material circulante. É composto por um conjunto de rotações, onde cada rotação define, sob a forma de um padrão repetitivo, a sequência de operações a realizar por unidades de material circulante do mesmo tipo, durante um número limitado ou ilimitado de semanas do calendário. Essas operações incluem o fornecimento de capacidade de transporte e tração para viagens de comboio programadas, bem como oportunidades de manutenção periódica de acordo com as regras do negócio.
Dado que os operadores ferroviários pretendem utilizar os seus recursos da forma mais eficiente, procuram ferramentas que sejam capazes de produzir planos operacionais como rotações de material circulante (doravante rotações) de forma automática e otimizada. É por isso que a VIA Rail Canada (VIA) e a SISCOG desenvolveram um projeto há alguns anos. O desafio era fornecer à VIA suporte algorítmico para produzir rotações que trouxessem maior lucro através de um ajuste eficiente da capacidade disponível à procura de passageiros em cada viagem de comboio.
A equipa de algoritmos da SISCOG foi escolhida para enfrentar este desafio. O ponto de partida foi um conjunto de algoritmos previamente desenvolvidos pela equipa e a literatura sobre otimização de material circulante. Ambos abordavam este problema como um problema de minimização de custos com a procura de passageiros modelada como uma restrição rígida ou flexível. Esta abordagem não era adequada para operadores ferroviários, como a VIA, que operam comboios com lugares reservados, porque neste contexto a maximização do lucro não pode ser alcançada minimizando apenas os custos, devendo também considerar a receita. Por outro lado, as abordagens de gestão de receita descritas na literatura tendem a ignorar ou simplificar demais os custos operacionais.
A equipa de algoritmos da SISCOG desenvolveu uma nova abordagem híbrida para resolver aproximadamente o problema de Planeamento de Rotação de Material Circulante com Lucro Máximo.
______________________
Para superar essas limitações, a nossa equipa desenvolveu uma nova abordagem híbrida para resolver aproximadamente o problema de Planeamento de Rotação de Material Circulante com Lucro Máximo (PRMCLM), com restrições de manutenção assumindo preços de bilhete fixos.
Descrevemos a abordagem e como ela está a ser usada com sucesso na prática pela VIA para planear a sua operação de transporte de passageiros com locomotivas e carruagens ao longo de um corredor que liga Toronto, Montreal e a cidade do Québec.
O problema do PRMCLM pode ser enunciado da seguinte forma: dado um conjunto de viagens de comboio, cada uma com a sua procura de passageiros (classe executiva e económica), encontrar, a partir do zero, para uma semana padrão, as rotações mais lucrativas que atribuem uma composição de veículos (doravante composição) a cada viagem que cubra toda ou parte da procura e que satisfaça todos os condicionalismos operacionais, nomeadamente restrições de manutenção e muitos outros. O lucro total é igual à receita menos o custo operacional, onde a receita é derivada da venda de bilhetes estimada (obtidas pela correspondência entre a procura e a capacidade dos comboios nas classes económica e executiva), e o custo inclui aspetos como a ocupação da via, a depreciação da frota, a manutenção e o consumo de energia, e a utilização da tripulação.
No âmbito da VIA, todas as rotações devem obedecer aos seguintes condicionalismos de manutenção: semanalmente, deve ser realizada uma manutenção do tipo B, e quinzenalmente do tipo C, com a particularidade de a manutenção C incluir a B.
No contexto da VIA, as rotações cumprem também um requisito especial. A composição atribuída a cada viagem possui duas partes: uma, chamada de “composição base”, formada por veículos que circulam sempre juntos conforme a Figura 1; e uma segunda parte formada por veículos que não possuem essa restrição. Geralmente, a composição base é formada por uma locomotiva, uma carruagem executiva e uma económica, mas também pode incluir mais carruagens económicas e uma segunda locomotiva na parte traseira.
Figure 1: Rotação da locomotiva mostrando a composição base a que ela pertence (dentro do retângulo pontilhado vermelho).
A SOLUÇÃO
Como o problema não pode ser resolvido com exatidão, devido ao tamanho das instâncias do problema da VIA, desenvolvemos um otimizador que utiliza um método de resolução aproximado inspirado no conceito de composição base descrito anteriormente. Este otimizador faz parte do FLEET, um produto de software para planeamento e gestão das operações de material circulante na rede e que está a ser utilizado pela VIA.
O método da solução resolve o problema em duas etapas:
- Produzir rotações para a composição base,
- Produzir rotações para as carruagens extras usadas para formar composições que são extensões das composições base obtidas na primeira etapa.
A primeira etapa é resolvida através de uma versão adaptada da heurística utilizada pelo CREWS(1), baseada em relaxação Lagrangeana e em geração de colunas, que resolve um problema de cobertura de conjuntos de custo mínimo com restrições adicionais, onde:
- elementos do conjunto representam viagens,
- conjuntos representam rotações definidas para tipos de composição específicos,
- custo representa prejuízo (custo menos receita) de rotações,
- restrições adicionais modelam restrições de tamanho de frota para cada tipo de veículo.
Além de fazermos esse mapeamento, também adaptámos o procedimento de definição de preços (que explora caminhos num grafo de viagem) para resolver um problema de caminho mais curto com restrição de recursos com um algoritmo de programação dinâmica em que os recursos foram configurados adequadamente para descartar caminhos no grafo de viagem que correspondem a rotações que violem a manutenção ou qualquer outra restrição relevante. Também fizemos ajustes no grafo de viagens para acomodar o conceito de rotação.
A nova solução de otimização de frota híbrida pode ser aplicada a qualquer operador ferroviário.
______________________
A segunda etapa é resolvida com uma abordagem que usa um modelo de rede de hipergrafos. No nosso caso, o hipergrafo contém apenas hiperarcos relacionados com as carruagens extra que servem para ampliar as composições obtidas na primeira fase. Isso reduz consideravelmente o número geral de hiperarcos para um número que torna o problema tratável. Para maximizar o lucro, este modelo favorece (evita) a atribuição de carruagens extra para viagens com falta (excesso) de lugares de passageiro.
OBSERVAÇÃO: Embora o método da solução apresentado se tenha inspirado no conceito de composição base, específico da VIA, este pode ser aplicado a qualquer operador ferroviário. É apenas uma questão de reduzir a composição base a um único veículo, por ex. uma locomotiva.
IMPACTO
O desempenho da nossa abordagem foi comparado com planeadores humanos. Como resultado direto do uso do FLEET no ambiente de produção, a VIA relatou os seguintes ganhos em relação às rotações anteriores (produzidas manualmente por planeadores humanos):
- 10.000.000 CAD de poupança anual dado poder operar todas as viagens com uma composição a menos,
- 3% a 5% de aumento na receita,
- 3% a 4% de aumento de lugares de passageiro disponíveis por milha.
CONCLUSÃO
Abordámos um problema de otimização de frota relevante para operações de comboios com lugares reservados. Dado que instâncias de problemas práticos não podem ser resolvidas exatamente, propusemos um método de resolução aproximado que combina técnicas existentes de uma nova maneira. Ao usar essa abordagem em ambiente de produção, a VIA Rail Canada obteve um crescimento significativo da receita e uma redução de custos.
(1) CREWS é um produto de software premiado para o planeamento e gestão otimizada de pessoal.