Artigo Claio 2006

Artigo Claio 2006

(Parte 1 de 2)

Metaheurísticas Aplicadas ao Sistema de Transporte Público

Gustavo Peixoto Silva••••

Marcone Jamilson Freitas Souza

Jorge von Atzingen

Universidade Federal de Ouro Preto Ouro Preto, Minas Gerais, Brasil

Resumo

Este trabalho apresenta uma abordagem para a resolução integrada do Problema de Programação de Veículos e Tripulantes de Ônibus Urbano. Este problema é tradicionalmente resolvido em duas etapas: primeiro é realizada a programação dos veículos; em seguida, a programação das tripulações. Neste trabalho, a programação dos veículos é feita considerando características pertinentes às tripulações, de forma a tirar proveito da interação entre os dois problemas, sendo por isso denominada abordagem integrada. A metodologia de solução proposta é baseada nas metaheurísticas Simulated Annealing e Busca Tabu e foi testada com dados reais de uma empresa de transporte coletivo de Belo Horizonte.

Palavras-Chaves: programação integrada de veículos e tripulações; simulated annealing; busca tabu.

1. INTRODUÇÃO

Este trabalho aborda o Problema de Programação Integrada de Veículos e de Tripulações do Sistema de Transporte Público (PPVT). O Problema de Programação de Veículos (PPV) consiste em: dada uma tabela de horários, determinar quais os veículos que realizam cada viagem, estabelecendo um conjunto de blocos dos veículos (conjunto de viagens a serem realizadas por cada veículo) que agrupem todas as viagens de tal forma que estas sejam realizadas com um custo operacional mínimo. O Problema de Programação da Tripulação consiste em determinar o número mínimo necessário de tripulações (motorista e cobrador), tal que a programação dos veículos (conjunto de viagens atribuídas a cada veículo) seja realizada com sucesso. A solução deste problema também envolve o seqüenciamento das atividades de cada tripulação, gerando um conjunto de jornadas de trabalho viáveis e cujo custo operacional total seja mínimo.

No PPVT são geradas simultaneamente a programação dos veículos e dos tripulantes possibilitando encontrar soluções com custo operacional menor que o custo obtido pela solução seqüencial do PPV e PPT. Entretanto, o PPVT é um problema mais complexo que o PPV e o PPT quando resolvidos separadamente. A complexidade do PPT ocorre devido às restrições operacionais vigentes nas empresas e às cláusulas contidas nas Convenções

• Endereço: Universidade Federal de Ouro Preto, Departamento de Comptação, Campus Universitário Morro do

Cruzeiro, 35.400-0, Ouro Preto, MG, Brasil. E-mails: gustavo@iceb.ufop.br.

Coletivas de Trabalho. Além destas características do PPT, o PPVT também possui restrições operacionais impostas aos veículos.

O trabalho [1] trata da aplicação de uma abordagem integrada para os problemas de programação de veículos e de programação de tripulações. Esta abordagem integrada foi originalmente proposta em [2] e foi modificada para incorporar algumas restrições complexas que surgem em uma aplicação real. Tradicionalmente estes problemas são abordados seqüencialmente. Neste trabalho, a programação de veículos é resolvida utilizando relaxação lagrangeana e a programação da tripulação é resolvida como um problema de recobrimento (set covering). Freling et al. [1] apresentam uma formulação inteira para a programação de veículos e tripulações, o qual é resolvido com uma combinação de relaxação lagrangeana e da técnica de geração de colunas.

Com o objetivo de avaliar a utilidade desta abordagem integrada, em [3] são comparadas diversas soluções obtidas com a abordagem integrada e com a abordagem seqüencial veículoprimeiro-tripulação-depois. Modelos matemáticos são apresentados para o problema integrado e para o problema seqüencial. A relaxação lagrangeana e heurísticas lagrangeanas foram desenvolvidas para o problema integrado e o modelo associado de recobrimento foi resolvido usando a técnica de geração de colunas.

Uma abordagem exata para resolver o PPVT é apresentada por Haase et al. [4]. O problema é formulado como um problema de particionamento para a escala de motoristas com restrições laterais para o itinerário dos veículos. Ele é resolvido usando o método branch-andbound em conjunto com a técnica de geração de colunas e o método de planos de cortes. Determinada a escala de tripulantes, a resolução de um problema de fluxo em rede define o itinerário dos veículos.

Um caso especial do problema de programação integrada da escala de veículos e tripulantes é considerado por Valouxis e Housos [5]. O problema é modelado com programação inteira em vez de um problema de recobrimento. A modelagem inteira resultante tem uma relaxação linear muito livre, mas pode ser apertada por meio de novas famílias de desigualdades válidas, ou cortes. Estes cortes são baseados em um algoritmo branch-and-cut. Testes numéricos com um conjunto de problemas gerados aleatoriamente e com um conjunto com características reais mostram como o método é competitivo em alguns casos.

Conforme afirmam Freling et al. [3], existem três tipos de abordagens para a resolução do

PPV e do PPT: Seqüencial, Independente e Integrada. A abordagem seqüencial foi a primeira a ser utilizada e consiste em resolver o PPV e em seguida o PPT. Uma variação desta abordagem consiste em inverter a ordem de resolução dos problemas, isto é, resolver primeiramente o PPT e em seguida o PPV.

A abordagem independente baseia-se em resolver o PPV ignorando a programação dos tripulantes e em seguida resolver o PPT independentemente dos resultados obtidos pela programação dos veículos. Dificilmente essas duas soluções são compatíveis.

A abordagem integrada pode ser dividida em dois tipos: o primeiro consiste em resolver simultaneamente a programação dos veículos e dos tripulantes, o qual é um problema complexo devido a sua magnitude. O segundo tipo de abordagem integrada é baseado na resolução do PPV considerando características dos tripulantes, de tal forma que a programação dos tripulantes é facilitada já na resolução da programação dos veículos.

Este trabalho apresenta a implementação de um método de resolução do PPVT baseado no terceiro tipo de abordagem mencionada, ou seja, a integrada que resolve o PPV incluindo neste características do PPT. O método computacional foi testado com os dados de um problema real de programação de veículos e tripulações e os resultados obtidos são apresentados e analisados nesse trabalho.

2. DESCRIÇÃO E MODELAGEM

O método apresentado neste trabalho para a resolução do PPVT consiste em resolver o

PPV com características da tripulação. Para resolver o PPV, foi desenvolvido um algoritmo baseado na técnica Simulated Annealing (SA), que é uma metaheurística de busca local probabilística. Posteriormente, o PPT foi resolvido por um algoritmo utilizando a metaheurística Busca TABU (BT), que é um procedimento adaptativo que utiliza uma estrutura de memória (denominada lista tabu) para guiar um método de descida a continuar a exploração do espaço de soluções.

O algoritmo proposto atende as restrições operacionais dos veículos e a legislação trabalhista em vigor no município de Belo Horizonte/Brasil. Para a resolução do PPVT a metodologia proposta elabora a programação dos veículos com características da tripulação, isto é, cada veículo deve atender as restrições impostas aos veículos além das restrições de descanso da tripulação. Desta forma, é obtida uma solução do PPV que facilitará atender as restrições do PPT.

No processo de resolução do PPVT foram consideradas as Restrições Essenciais abaixo. i. Um veículo não pode realizar duas viagens ao mesmo tempo, isto é, não pode haver sobreposição de viagens; i. Um veículo deve ter o início e o término de sua atividade diária de operação na garagem; i. Os veículos só podem mudar de linha dentro de um mesmo grupo de linhas, ou seja, grupos predeterminados de linhas com as mesmas características; iv. Um veículo não pode ficar mais de 23 horas e 30 minutos fora da garagem por dia; v. O número de veículos com dupla pegada estará limitado a um determinado valor; vi. Para um veículo ser considerado como dupla pegada deve haver um intervalo entre duas viagens superior a 2 horas somado com o tempo de deslocamento do veículo até a garagem; vii. Uma tripulação não pode realizar mais de uma tarefa ao mesmo tempo, ou seja, não pode haver sobreposição de tarefas; viii. As trocas das tripulações só podem ocorrer nas Oportunidades de Trocas, ou seja em determinados pontos e entre viagens com mais do que um dado intervalo de tempo; ix. As trocas das tripulações só podem ocorrer entre linhas de um mesmo grupo; x. Existem dois tipos de jornadas para as tripulações: pegada simples e dupla pegada. A jornada tipo pegada simples tem duração de 7 horas e 10 minutos com direito a uma pausa para descanso/alimentação. A dupla pegada tem duração total de 6 horas e 40 minutos dividida em duas etapas separadas por pelo menos duas horas de interrupção. Neste caso os tripulantes não têm direito à pausa para descanso/alimentação. xi. A pausa na jornada tipo pegada simples deve ser no mínimo de 30 minutos para descanso/alimentação, podendo este intervalo ser fracionado, desde que pelo menos um deles seja maior ou igual a 15 minutos; xii. O número de tripulações com dupla pegada deve estar limitado a um certo valor; xiii. As jornadas de trabalho podem ser acrescidas de até duas horas extras; xiv. O tempo entre o final de uma jornada diária de trabalho e o seu início no dia seguinte deve ser de, no mínimo, 1 horas.

As Restrições Não Essenciais consideradas na resolução do PPVT foram: i. O tempo ocioso de um veículo deve ser minimizado; i. O número de veículos utilizados deve ser o menor possível; i. O número de vezes que um veículo realiza uma troca de linha deve ser mínimo; iv. O tempo de viagem vazia de um veículo deve ser o menor possível; v. O tempo ocioso de uma tripulação deve ser o menor possível; vi. O número de horas extras deve ser minimizado; vii. O número de tripulações deve ser mínimo; viii. O número de vezes que uma tripulação troca de veículo deve ser reduzido; ix. O número de vezes que uma tripulação com dupla pegada finaliza a primeira pegada em um ponto e inicia a segunda pegada em um outro ponto deve ser reduzido; x. O número de vezes que uma tripulação troca de linha deve ser reduzido.

A função de avaliação utilizada no modelo visa avaliar matematicamente uma solução s para o PPVT através da penalização de cada uma das restrições essenciais e não-essenciais que forem infringidas. A função objetivo é dada pela expressão (1), onde s é uma solução para o PPVT.

FRE(s) = A1×FRE1(s) +A2×FRE2(s) ++ A14×FRE14(s) (2)
FRNE(s) = B1×FRNE1(s) +B2×FRNE2(s) ++ B10×FRNE10(s) (3)

A expressão (1) contém as penalizações referentes às restrições essenciais FRE(s) e as não essenciais FRNE(s) de uma dada solução s. A parcela FRE(s), dada pela expressão (2) é composta pelas 14 restrições descritas no início desta seção. Já a expressão (3) computa as penalidades referentes ao não atendimento das restrições não essenciais consideradas. Os pesos utilizados na função FO(s) foram calculados da seguinte forma:

Ai = iCα, i = 1,, 14 e Bj = jDδ
, j = 1,, 10 (4)

onde Ci, Dj, αi e δj são elementos de uma função exponencial, calculados de tal forma que as restrições não-essenciais, tempo de viagem morta e tempo de terminal, têm suas penalidades variando em uma faixa entre os valores 1 e 16. Para as restrições essenciais, os valores dos pesos variam entre 50 e 100.

Para explorar o espaço de soluções, são utilizados dois tipos de movimentos: realocação e troca. O movimento de realocação consiste em atribuir uma viagem de um veículo a outro veículo. A Figura 1 ilustra este movimento, sendo que a viagem 2 passa do veículo i para o veículo j.

Fig. 1 Movimento de Realocação

O movimento de troca consiste em trocar uma viagem de um veículo com outra viagem de outro veículo. Na Figura 2 as viagens 1 e 5 são trocadas entre os veículos i e j.

Fig. 2 Movimento de Troca

Veículo i:

Veículo j: Viagem 1

Viagem 2

Viagem 3 Viagem 4 Viagem 5 Viagem 6 Viagem 7

Veículo i:

Veículo j: Viagem 1

Viagem 3 Viagem 4 Viagem 5

Viagem 6 Viagem 7 Viagem 2

Na resolução do PPT integrado, o algoritmo proposto utiliza dois tipos diferentes de movimentos para geração de uma solução vizinha: movimento de realocação ou 1-optimal e movimento de troca ou 2-optimal. Conforme comprovado por Mapa [6], estes dois tipos de movimento devem ter probabilidades diferentes de serem realizados. Desta forma pode-se obter soluções melhores do que as obtidas quando utilizamos a mesma probabilidade de escolha para ambos os movimentos. Neste trabalho, o PPT foi resolvido escolhendo o movimento 1-optimal com 90% de probabilidade e o movimento 2-optimal com 10% de probabilidade.

3. RESULTADOS OBTIDOS

Durante a resolução do PPV foram consideradas, além das restrições impostas aos veículos, um tempo mínimo de 20 minutos de folga durante as 07:10 (sete horas e dez minutos) que o veículo fica fora da garagem. Este tempo de folga pode ser dividido em até dois intervalos de 10 minutos. Em seguida, considerando os blocos de viagens gerados para os veículos, o algoritmo Busca Tabu resolveu o problema de programação das tripulações. Para a obtenção dos resultados computacionais expostos nas Tabelas 1 e 2, foi utilizado um microcomputador Athlon XP 2000 com 778 MB de RAM.

Tabela 1 Resultados obtidos para o domingo

Função Objetivo

Nº de

(Parte 1 de 2)

Comentários