Ana Carvalho, Software Engineer e Ricardo Saldanha, Diretor de Inovação @SISCOG | 9 min leitura
___________
INTRODUÇÃO
A SISCOG foi fundada em 1986 como uma empresa baseada em Inteligência Artificial, com o objetivo de desenvolver produtos de software de apoio à decisão para áreas de aplicação que ainda estavam por definir. A certa altura, a SISCOG identificou o sector dos transportes como o seu nicho de mercado e percebeu que os otimizadores eram um componente-chave dos produtos de software necessários nesse mercado. Isto levou à adoção da visão e do slogan da SISCOG: “Otimizar os Recursos do Mundo”.
Ao longo dos anos, a SISCOG percebeu que a combinação de Inteligência Artificial (IA) com Investigação Operacional (IO) era a melhor abordagem para enfrentar os complexos problemas de otimização combinatória que era necessário resolver para fornecer um apoio à decisão eficaz no sector dos transportes.
A Investigação Operacional, um ramo da matemática aplicada, é uma das áreas que mais tem contribuído com uma vasta gama de métodos para os otimizadores utilizados diariamente por empresas de transporte em todo o mundo. Ao contrário do que muitas pessoas pensam, a matemática é muito mais do que um conjunto de números e fórmulas abstratas. As técnicas de IO permitem transformar problemas complexos em soluções eficientes. Através da aplicação da IO, os produtos da SISCOG contribuem para aumentar o lucro, a produtividade e, em última instância, a satisfação dos passageiros.
Este artigo explica o papel central da IO no desenvolvimento de soluções inovadoras, que são depois incorporadas nos produtos da SISCOG e que têm impacto na vida de milhões de pessoas em todo o mundo.
O PAPEL DA MATEMÁTICA NA SISCOG
Já alguma vez pensou como é que a Investigação Operacional pode ser usada para…
... gerar um horário?
... planear a operação e a manutenção dos veículos?
... produzir as escalas da tripulação?
Quando apanhamos o comboio de manhã para ir trabalhar, estamos longe de imaginar toda a matemática que está por detrás de tudo isto. Vale a pena perceber como essa realidade se reflete nos diferentes produtos da SISCOG.
O mesmo comboio chega todas as manhãs às 7h50 à mesma plataforma da estação. Se, por alguma razão, perder esse comboio, o próximo chegará às 8h10 e o seguinte às 8h30. Este padrão repete-se às 8h50, 9h10, 9h30, e assim sucessivamente. Isto é o que se chama um horário regular ou periódico, criado e gerido através do produto ONTIME da SISCOG.
______________________
O ONTIME é responsável por produzir e ajustar um horário, ou seja, um conjunto de viagens de comboio onde cada viagem é definida por um dia da semana, uma rota na rede, estações de início, fim e intermédias, assim como os horários de partida e chegada nessas estações.
Os horários são produzidos num processo de duas etapas.
- A primeira etapa diz respeito à geração do plano de linhas ou padrões de serviço, que pode ser definido como um conjunto de viagens de comboio ainda não escalonadas, concebidas para responder à procura de passageiros e satisfazer, tanto quanto possível, as preferências dos passageiros, mas respeitando a capacidade limitada em termos de via-férrea e material circulante.
- A segunda etapa, chamada planeamento dos comboios, atribui horários às viagens ainda não escalonadas, garantindo que todas as regras de tráfego são cumpridas e que os tempos de viagem são minimizados. O horário original precisa, muitas vezes, de ser ajustado em situações específicas em que as condições de operação mudam (por exemplo, vias indisponíveis, estações encerradas, alterações nos limites de velocidade, etc.). Nestes casos, é necessário replanear os comboios, procurando minimizar o número de alterações em relação ao horário original.
Os horários periódicos são um tipo de horários geralmente atrativo para os passageiros, pois são regulares e fáceis de memorizar. Neste tipo de horários, as viagens com a mesma rota ou padrão de serviço estão distribuídas uniformemente no tempo.
O problema da geração de horários é um problema muito complexo de otimização combinatória, que é resolvido através da combinação de técnicas de Inteligência Artificial (IA) e Investigação Operacional (IO). Por exemplo, sabe-se que o problema do planeamento de linhas é resolvido com algoritmos genéticos, enquanto os problemas de planeamento e replaneamento de comboios são resolvidos por: (a) SAT combinado com programação linear inteira mista ou outras técnicas de IO, (b) SAT combinado com aprendizagem por reforço, ou (c) MaxSAT. SAT (e MaxSAT) é tanto uma forma de modelar problemas de viabilidade (otimização) como um conjunto de técnicas para os resolver. Em SAT (e MaxSAT), um problema é modelado como um Problema de Satisfação Booleana, que serve para decidir se uma fórmula proposicional satisfaz ou não (ou satisfaz da melhor forma possível).
Figura 1 – Exemplo de uma solução de horário produzida pelo ONTIME. No topo encontra-se um diagrama espaço-tempo - uma representação visual do tempo em relação à posição e movimento dos comboios nas estações entre a partida e a chegada. Na parte inferior estão as viagens de comboio correspondentes.
O comboio que apanhamos todas as manhãs foi cuidadosamente escolhido para responder à procura dos passageiros através do produto FLEET.
______________________
O produto FLEET é responsável por produzir e ajustar os planos operacionais dos veículos, o que significa resolver o problema de planeamento do material circulante (rolling stock planning problem - RSPP). Em resumo, o RSPP consiste em atribuir veículos às viagens planeadas no horário criado pelo ONTIME.
No RSPP, um conjunto de veículos combinados para formar uma composição (o que normalmente chamamos de “comboio”) é atribuído a uma viagem. A composição atribuída a uma viagem do horário tem em conta a procura prevista de passageiros. Cada veículo numa composição tem um conjunto de tarefas que correspondem a viagens sequenciadas, ou seja, viagens que são operadas uma após a outra (por vezes com um intervalo de tempo entre elas). Podem ocorrer manobras para reduzir ou aumentar o tamanho da composição quando sequenciadas com a viagem seguinte. Além disso, os veículos precisam de manutenção frequente, o que gera várias restrições adicionais com diferentes necessidades técnicas. O principal objetivo de otimização do RSPP é minimizar o número total de quilómetros percorridos pelos veículos (o que impacta o consumo de energia e os custos de manutenção) e o tamanho da frota. Outros objetivos adicionais de otimização podem incluir a maximização da receita (número esperado de bilhetes vendidos).
Para resolver o problema anteriormente descrito, o FLEET recorre a diferentes abordagens envolvendo Investigação Operacional (IO). Uma dessas abordagens é a programação linear inteira mista. As possíveis composições a atribuir a uma viagem, assim como as possíveis manobras entre viagens sequenciadas, podem ser representadas num grafo. Depois, considerando um modelo de fluxo, com restrições adicionais relativas à manutenção dos veículos, obtém-se a solução ótima para o RSPP.
Figura 2 – Exemplo de uma solução produzida pelo FLEET. Cada linha representa o conjunto de tarefas de cada composição. Cada tarefa corresponde a uma viagem (verde) ou a uma necessidade de manutenção (amarelo).
A nossa rotina matinal para chegar ao trabalho termina após uma viagem de 30 minutos. O comboio chega à estação terminal e finalmente alcançamos o nosso destino. O maquinista saiu do comboio; terminou o seu turno de trabalho para o esse dia. Consegue imaginar toda a Investigação Operacional por trás deste plano de trabalho? É responsabilidade do produto CREWS.
______________________
O produto CREWS é responsável por produzir e ajustar os planos operacionais da tripulação, tendo em conta os horários dos comboios e os planos operacionais dos veículos. São considerados vários constrangimentos operacionais e regras laborais, bem como as competências e preferências da tripulação. A complexidade deste problema está relacionada com o número e a duração das tarefas a planear e com as regras que devem ser cumpridas. O CREWS também pode ser utilizado para produzir e ajustar planos operacionais de outros tipos de pessoal, mas os planos operacionais dos tripulantes são muito mais complexos do que os dos outros trabalhadores. Por isso, damos especial ênfase aos planos operacionais da tripulação.
No CREWS, os planos operacionais são elaborados para uma semana padrão através de um processo de duas fases.
- Na primeira fase, chamada problema de planeamento de turnos, são criados turnos para várias bases operacionais da tripulação, resultando num conjunto de sequências de viagens de comboio que começam e terminam na mesma base operacional, cumprindo as regras laborais relacionadas com tempos de trabalho, pausas para refeições, tempos de deslocação, capacidade da base operacional e muitos outros aspetos. O objetivo de otimização mais comum é minimizar o número de turnos necessários para cobrir todo o trabalho.
- Na segunda fase, chamada problema de planeamento de escalas, são elaboradas escalas independentes para cada base operacional como conjuntos de turnos sequenciados, tipicamente de forma cíclica. Estas escalas devem cumprir regras relacionadas com dias de descanso, tempos de trabalho, capacidade da base operacional, entre outros. Os objetivos típicos de otimização incluem maximizar as preferências da tripulação e a equitatividade. Os problemas de replaneamento de turnos e escalas consistem em ajustar os planos originais para acomodar alterações específicas nas condições sob as quais os planos originais foram elaborados, como mudanças no horário dos comboios, ausências da tripulação, etc. Os objetivos típicos do replaneamento são cobrir o máximo possível de trabalho e minimizar as alterações relativamente aos planos originais.
Os problemas de planeamento e replaneamento de turnos são normalmente modelados como um problema de cobertura de conjuntos de custo mínimo com restrições adicionais e são tipicamente resolvidos com várias técnicas de IO, como relaxação Lagrangeana, geração de colunas, programação dinâmica e heurísticas gananciosas. Os problemas de planeamento e replaneamento de escalas são geralmente resolvidos com técnicas de IO, como programação linear inteira mista, agregação de restrições e pesquisa em vizinhança alargada. Nos problemas de replaneamento, também são utilizadas técnicas de pesquisa local.
Figura 3 – Exemplo de uma solução produzida pelo CREWS para o planeamento de turnos.
DESAFIOS DO MUNDO REAL
Os problemas descritos anteriormente podem não parecer difíceis de resolver se considerarmos realidades de pequena dimensão, com apenas algumas viagens e planos de tripulação, e sem restrições adicionais complexas. No entanto, esta raramente é a situação na prática. Os problemas reais, nomeadamente os que são resolvidos pelos produtos ONTIME, FLEET e CREWS, envolvem milhares de viagens e restrições adicionais complexas. Para enfrentar estes desafios do mundo real, a Investigação Operacional tem-se revelado altamente eficaz, produzindo resultados que melhoraram tanto a rentabilidade como a produtividade.
Exemplos de ganhos relatados pelos clientes da SISCOG com o uso de otimizadores:
- Aumento de 3% a 4% na receita devido a um melhor ajuste da capacidade de transporte à procura
- Redução de 5% a 6% no número de tripulantes devido à geração de planos operacionais mais eficientes
- Redução de até 90% nas horas extraordinárias devido à geração de planos operacionais mais eficientes
- Redução de até 60% no número de planeadores humanos devido à diminuição do trabalho manual
INOVAÇÃO E COLABORAÇÕES
A inovação é um valor central na SISCOG, e a Investigação Operacional desempenha um papel fundamental na manutenção desta vantagem inovadora. Para preservar esta posição, a SISCOG incentiva a colaboração com diversas pessoas e organizações. Estas colaborações ocorrem tanto a nível interno como externo.
- As colaborações internas centram-se no trabalho em equipa. Diferentes departamentos trabalham em conjunto, partilhando experiências e ideias. Cada membro da equipa contribui para o sucesso global da SISCOG.
- As colaborações externas incluem parcerias com Universidades e Centros de Investigação, sendo a IO uma das principais áreas de foco. Todos os anos, a SISCOG orienta estudantes de Mestrado ou Doutoramento e acolhe jovens talentos através de estágios. Para além disso, participa em eventos que ajudam os estudantes a compreender o papel da IO para além do meio académico. É especialmente enriquecedor para os estudantes perceberem como os seus conhecimentos podem ser aplicados na resolução de problemas do mundo real.
CONCLUSÃO
A SISCOG mantém um foco contínuo na inovação, tanto para fornecer produtos competitivos e de elevada qualidade aos seus clientes atuais como para atrair novos. A Matemática – e, mais concretamente, a Investigação Operacional – é reconhecida como uma das ferramentas mais essenciais para manter este elevado padrão de inovação, nomeadamente nos produtos ONTIME, FLEET e CREWS. De facto, a aplicação de técnicas de IO tem contribuído consistentemente para melhorar a rentabilidade, a produtividade e a qualidade do serviço de transporte dos nossos clientes ao longo dos anos.
A colaboração com diferentes entidades é também fundamental para potenciar ao máximo a IO e integrar inovação nos produtos da SISCOG.
Seja engenheiro, académico ou operador de transportes, convidamo-lo a partilhar connosco as suas ideias sobre o potencial da IO no sector dos transportes públicos.
Que novos desafios no sector dos transportes acredita que a Investigação Operacional pode ajudar a resolver com sucesso?