XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
ESCALONAMENTO INTEGRADO PARA O TRANSPORTE COLETIVO
UTILIZANDO GRASP, PATH-RELINKING E PARALELISMO
Thiago Serra
GOA: Grupo de Otimização Aplicada – Instituto de Computação, UNICAMP
Avenida Albert Einstein, 1251 – 13084-971 – Campinas, SP
[email protected]
Arnaldo Vieira Moura
GOA: Grupo de Otimização Aplicada – Instituto de Computação, UNICAMP
Avenida Albert Einstein, 1251 – 13084-971 – Campinas, SP
[email protected]
RESUMO
O Problema de Programação de Viagens (PPV) visa gerir, da forma mais econômica
possível, linhas de transporte urbano pré-estabelecidas e de características conhecidas. Uma
solução para o PPV consiste na escala de veículos e tripulações para atenderem à demanda diária
de passageiros. Este trabalho envolveu a implementação de um módulo resolvedor utilizando
GRASP para a geração de soluções, aliado às estratégias de busca local e ligação de caminho na
fase de intensificação, juntamente com programação paralela para o estabelecimento de
estratégias colaborativas. Foram realizados testes com dados reais da região metropolitana de
São Paulo, nos quais a qualidade das soluções obtidas pôde ser atestada pela comparação com
outros trabalhos realizados com as mesmas instâncias.
PALAVRAS CHAVE. GRASP Paralelo. Ligação de Caminho. Problema de Programação
de Viagens. LGT – Logística e Transportes.
ABSTRACT
The Urban Transportation Problem (UTP) aims to manage, in the most economic
possible way, urban transportation lines already established and with known operational
characteristics. A solution to the UTP consists of a scheduling of vehicles and crew to satisfy the
daily passengers demand. This work involves the implementation of a solver module using a
GRASP heuristic to generate solutions, coupled with local search and path-relinking strategies in
the intensification phase, together with parallel programming for the establishment of
collaborative strategies.The implementation was tested using real data from the metropolitan
region of São Paulo, in which the solutions' quality could be attested by the comparison with
other works using the same instances.
KEYWORDS. Parallel GRASP. Path-Relinking. Urban Transportation Problem. LGT –
Logistics and Transportation.
XXXVIII SBPO
[ 963 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
1. Introdução
Desde a década de 1970 foram realizados muitos estudos acerca da realização de
atividades operacionais e de planejamento em transporte urbano com o auxílio de ferramentas
computacionais. Essas ferramentas vêm sendo utilizadas para atividades que vão desde o
roteamento de veículos para o estabelecimento de linhas de ônibus, até a determinação de
horários de partida para as viagens, e a designação de veículos e tripulação para sua realização.
Entre algumas das cidades nas quais foram aplicadas técnicas desenvolvidas em estudos
acadêmicos para o planejamento de transporte urbano, pode-se destacar São Paulo, Fortaleza,
Sorocaba e Belo Horizonte (Yunes (2000), Rodrigues (2001) e Vaz (2003)).
O Problema de Programação de Viagens (PPV) visa resolver parte do problema de
operação do transporte coletivo urbano, realizando o escalonamento diário de veículos e de
tripulação para o atendimento em uma linha de ônibus pré-estabelecida e com demanda de
atendimento conhecida. Esse atendimento deve preservar um nível de qualidade de serviço
exigido pelos órgãos gestores do transporte público na região, além de satisfazer restrições
trabalhistas relacionadas à duração da jornada diária, períodos de descanso e limites de horaextra da tripulação. Este problema é classificado como NP-Difícil por Wren (1998). Dessa
forma, o emprego de técnicas heurísticas para a obtenção de soluções de boa qualidade em tempo
razoável provou-se muito atraente ao longo dos anos (Lourenço et. al. (2001), Souza et. al.
(2003) e Ciré et. al. (2005)).
O objetivo deste trabalho consiste na resolução integrada dos problemas de atribuição de
veículos e de alocação de tripulação para o atendimento da demanda de passageiros, e na análise
das técnicas empregadas para tanto. A principal ferramenta de resolução foi a meta-heurística
GRASP, empregada com grande sucesso há 17 anos em muitos problemas de otimização
combinatória - com resultados superiores a outras técnicas em problemas como o de
recobrimento de conjuntos (Feo e Resende (1995) e Goldbarg e Luna (2000)), que se assemelha
bastante ao PPV pela forma como o mesmo será abordado neste trabalho. Adicionalmente, foram
utilizadas estratégias gulosas de busca local e de ligação de caminho, além da paralelização do
módulo resolvedor tanto como forma para aumentar a quantidade de soluções obtidas quanto
como meio de explorar a colaboração entre processos de resolução simultâneos.
O resultado do trabalho consistiu em um módulo resolvedor que gerava rapidamente
soluções viáveis e de boa qualidade. Foram realizados testes com instâncias reais da região
metropolitana de São Paulo, já utilizadas em outros trabalhos (Rodrigues (2001), Vaz (2003) e
Ciré et. al. (2005)), sendo possível comparar o desempenho das técnicas empregadas com relação
às soluções obtidas manualmente, ou por meio de programação matemática, ou programação por
restrições, além de outras meta-heurísticas paralelizadas.
Os resultados foram muitos animadores, havendo várias instâncias nas quais foram
obtidas soluções melhores, além de um padrão geral de qualidade uniforme com relação às outras
abordagens. Esse desempenho contrariou resultados pessimistas sobre a meta-heurística neste
problema apresentados por Souza et. al. (2003). Por fim, foram realizados estudos acerca do
desempenho do módulo fixando valores para seus parâmetros, o que produziu alguns
comportamentos interessantes acerca da ligação de caminho e do paralelismo colaborativo.
A organização deste documento é descrita a seguir. A seção 2 trata da definição formal
do problema, contendo sua descrição, a definição da solução e sua formulação matemática. A
seção 3 apresenta mais detalhadamente as técnicas empregadas na resolução do problema e a
forma como foram utilizadas. A seção seguinte apresenta os resultados - tanto uma análise
comparativa quanto alguns estudos sobre o desempenho do módulo resolvedor. A seção 5 traz as
conclusões e perspectivas de trabalhos futuros.
2. Definição do problema
2.1. Descrição do Problema de Programação de Viagens
As jornadas de tripulação são constituídas por tarefas, que podem ser de um dos três
tipos: viagens de atendimento à demanda, viagens envolvendo a garagem como destino ou
partida, e períodos de descanso. Na situação abordada, existe apenas uma garagem. Cada
XXXVIII SBPO
[ 964 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
instância dispõe de um ou dois Pontos de Controle (ou PCs) distintos. As viagens de atendimento
à demanda são realizadas entre os PCs, nos quais ocorrem também o descanso da tripulação. A
permuta de tripulações de um veículo pode ser realizada no PC, a não ser quando envolvam
intervalos maiores entre as jornadas e que impliquem no retorno do carro à garagem para evitar o
empilhamento de veículos no PC.
O dia é dividido em faixas horárias (ou FHs), que possibilitam tanto uma especificação
mais adequada da demanda, como uma melhor estimativa sobre as características de trânsito nas
faixas. Cada instância apresenta tabelas com o tempo de viagem entre a garagem e cada PC em
cada FH do dia, o tempo de viagem entre um PC e outro por FH, e a demanda de passageiros
para as viagens partindo de um PC para o outro e vice-e-versa de acordo com a FH. A qualidade
de serviço é determinada pela quantidade máxima de passageiros que um ônibus pode atender em
uma viagem. Existe também um número máximo de veículos que podem ser utilizados em cada
instância.
Para as instâncias utilizadas da região metropolitana de São Paulo, existe uma série de
restrições relativas à qualidade de serviço, à utilização de frota e às jornadas de tripulação,
descritas a seguir.
– A quantidade de viagens partindo de cada PC em cada FH deve ser suficiente para
atender à demanda de passageiros.
– Não devem ser utilizados mais veículos do que a quantidade disponível.
– Nenhum veículo pode ter mais de duas jornadas de tripulação associadas.
– Uma jornada de tripulação deve ser realizada integralmente em um veículo.
– Deve haver algum espaçamento entre viagens consecutivas de uma jornada.
– O tamanho máximo de uma jornada é de 7 horas e 20 minutos, sendo que devem ser
alocados 30 minutos de descanso entre a segunda e a sexta horas; ou, se não há
descanso, a jornada terá um limite de 6 horas e 50 minutos.
– Existe um limite máximo de horas-extra que cada tripulação pode realizar em sua
jornada.
– Evitar situações nas quais a jornada é interrompida (períodos de inatividade
superiores a 2 horas).
– A troca de motoristas implica, para sua realização, em um intervalo de 20 minutos
computados no final tanto da jornada da tripulação que está encerrando quanto da
que está iniciando suas atividades.
O PVV pode ser fracionado em três problemas interdependentes (Rodrigues (2001)),
descritos a seguir. O primeiro deles seria o Problema de Montagem de Horários, no qual a
demanda representada pela quantidade de passageiros que utilizam a linha de transporte por FH é
utilizada para o estabelecimento de um conjunto de horários de partida de cada PC com relativa
uniformidade nos horários. O segundo seria o Problema de Escalonamento de Veículos, que se
baseia nos horários de partida para alocar a quantidade mínima possível de carros de forma que
todas as viagens sejam executadas por exatamente um veículo. Por fim, temos o Problema de
Escalonamento de Tripulação, que visa associar uma tripulação para os veículos, com o intuito
de minimizar a quantidade de jornadas e de horas-extras necessárias, além de procurar reduzir a
quantidade de tempo na qual a tripulação fica ociosa.
A Abordagem Seqüencial Tradicional consistiria na resolução separada de cada um
desses problemas. Neste trabalho, entretanto, foi adotada a Abordagem Integrada, que visa a
resolução conjunta dos três problemas, evitando o foco excessivo em um único aspecto e
objetivando um ganho em qualidade devido a essa integração na resolução.
2.2. Definição do conjunto de elementos
Quanto tratamos problemas de otimização combinatória, uma questão de suma
importância consiste no estabelecimento das unidades elementares para a construção das
soluções. Unidades muito pequenas podem trazer simplicidade ao processo decisório imediato,
mas acarretam em conjuntos representando uma solução com tamanho muito grande e de
manipulação complexa. Tendo em vista que grande parte das restrições envolvendo jornadas de
tripulação não dependem das interações das mesmas entre si, foi utilizado neste trabalho uma
XXXVIII SBPO
[ 965 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
abordagem de enumeração prévia de jornadas para a resolução posterior do problema (Lourenço
et. al. (2001) e Ciré et. al. (2005)).
Com a finalidade de evitar enumerações exaustivas de jornadas muito semelhantes, foi
estabelecido um conjunto de propriedades para indexação das jornadas que serão posteriormente
manipuladas pelo módulo resolvedor. Em seqüência, essas 8 dimensões seriam as seguintes: (1)
FH da tarefa inicial, (2) tempo de duração, (3) quantidade de tarefas, (4) PC da primeira tarefa,
(5) PC da última tarefa, (6) FH de descanso, (7) tempo ocioso em serviço e (8) para que possa ser
gerada mais de uma jornada com todos os outros índices idênticos.
A enumeração de jornadas atentou às características de jornadas sabidamente
pertencentes a soluções de boa qualidade: a folga entre tarefas é sempre pequena, o que
possibilita um número maior de tarefas por jornada de tripulação e - por conseqüência - uma
quantidade menor de horas-extra e de jornadas requeridas.
As soluções para o PPV passam então a serem descritas por uma estrutura de dados
consistindo em um vetor de veículos contendo conjuntos de jornadas de motoristas, conforme
visto na figura 1 (Ciré et. al. (2005)).
Figura 1: Estrutura de dados utilizada para uma solução do PPV.
2.3. Formulação por restrições do PPV
A formulação apresentada a seguir foi extraída de Ciré et. al. (2005). Partindo de uma
enumeração de jornadas E, o PPV pode ser formulado abstraindo-se restrições relativas à
tripulação. É definida alguma notação prévia relativa a parâmetros e variáveis para melhor
compreensão da formulação, especificada na tabela 1. As FHs são numeradas de 1 a 24, os PCs
de 0 e 1, o tipo de tarefa 0 associado a viagens e o tipo 1 a descanso.
A função objetivo define a minimização do total de veículos, tripulação, horas-extra e
ociosas dos motoristas. Para a abordagem deste trabalho, definimos ca>>cb>>cc , cd =0. A
primeira restrição refere-se à quantidade máxima de veículos. A segunda restrição define o
veículo como uma dupla de jornadas que deve se suceder no tempo. As duas últimas restrições
referem-se à necessidade de atendimento integral da demanda, assemelhando-se àquelas relativas
ao problema de cobertura de conjuntos.
3. Abordagem de resolução
A construção e modificação das soluções baseou-se na descrição das mesmas como um
conjunto de jornadas de tripulação. A associação dessas jornadas a veículos foi feita utilizando
XXXVIII SBPO
[ 966 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
uma modelagem sobre grafos, na qual as jornadas seriam os vértices e são estabelecidas arestas
entre jornadas que podem ser inseridas em um mesmo veículo (i.e., que não apresentam
sobreposição de tarefas). Usando o algoritmo de pareamento máximo de complexidade
quadrática no número de vértices de Gabow (1976), cada conjunto de pares de jornada casados bem como as jornadas não casadas - constituem veículos para a solução. Com essa decomposição
de parte da construção da solução para um problema polinomial, o processo de construção de
soluções foi bastante simplificado.
Parâmetros
Variáveis
ca , cb , cc , cd Custos de cada variável da solução,
definidos pelo planejador
S
Solução formada pelo
conjunto de veículos V
Demanda na faixa horária f e no PC
p
V
Veículo definido por, no
máximo, uma dupla
consecutiva de jornadas J
df,p
E
Ti
ti , PCIi , Hi
Conjunto de jornadas J, sendo cada n (V) Tripulação total do veículo V
m
uma um conjunto de tarefas T
(valor inferido)
i-ésima tarefa de uma jornada
Tipo, PC inicial e minuto de início
da i-ésima tarefa
Df,p
Total de tarefas na faixa
horária f e iniciando no PC p
(valor inferido)
he(J)
Total de horas extras da
jornada J (valor inferido)
Quantidade e capacidade dos
Total de horas ociosas da
ho(J)
veículos utilizados na linha
jornada J (valor inferido)
Tabela 1: Parâmetros e variáveis utilizados na formulação do PPV.
nv , capv
Toda solução construída é avaliada para determinar sua inserção, ou não, em um
conjunto de soluções de elite, que consistiriam nas melhores soluções obtidas até o momento.
Este conjunto é utilizado tanto para reter a melhor solução encontrada quanto para a realização
do procedimento de ligação de caminho descrito a seguir.
Muitas decisões de implementação são justificadas por testes realizados durante o
desenvolvimento do módulo resolvedor, com resultados apresentados apenas textualmente.
3.1. A meta-heurística GRASP
A meta-heurística GRASP (de Greedy Randomized Adaptive Search Procedures) foi
proposta em 1989 por Feo e Resende (1989 e 1995). Consiste em um procedimento iterativo de
inclusão de elementos na solução em construção ponderando entre uma avaliação adaptativa do
benefício de escolha e um certo grau de aleatoriedade na decisão. Após obtida uma solução,
realiza-se uma busca local para melhorá-la.
A cada iteração, os elementos passíveis de inclusão são considerados mediante uma
função gulosa que avalia o ganho resultante da inserção deste elemento na solução parcialmente
construída. Os melhores elementos são inseridos em uma lista chamada RCL (de Restricted
Candidates List), que pode ter um tamanho fixo ou variável. Em caso de tamanho variável,
utiliza-se um parâmetro α que determina a razão mínima entre as diferenças do elemento
avaliado e do melhor elemento encontrado com o pior elemento encontrado, de acordo com a
função gulosa, para aceitação na RCL. Objetivando uma boa exploração do espaço de soluções,
as gerações de soluções devem ser rápidas, acompanhadas de uma busca local de poucos passos
para a obtenção de ótimos locais.
Para o PPV, a função gulosa utilizada foi o somatório da demanda de passageiros ainda
por atender na faixa horária de cada viagem de atendimento à demanda (se ainda houver
demanda pendente na FH). A utilização dessa função gulosa se baseou na meta de uniformizar as
demandas das FHs conforme os elementos fossem sendo incluídos.
XXXVIII SBPO
[ 967 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
As RCLs de tamanho fixo só mostraram bons resultados quando seu tamanho
representava algum percentual do total de elementos, e mesmo assim com alguma degeneração
ao final do processo iterativo, pois a quantidade de elementos com um bom atendimento relativo
da demanda passa a ser cada vez menor. Dessa forma, optou-se pela utilização do parâmetro α ao
invés das RCLs de tamanho fixo. Outra vantagem dessa escolha consistiu no fim da necessidade
de se ordenar todos os elementos avaliados, em troca de um processo de seleção qualitativa de
elementos, de complexidade linear.
3.2. Busca local
A estratégia de busca local se baseou em um procedimento iterativo guloso. Cada
iteração consiste em uma aplicação do operador de remoção de viagens ou do operador de fusão
de jornadas. A remoção de viagens pode envolver o conjunto das primeiras ou das últimas tarefas
da jornada (podendo mesmo remover completamente a jornada), com o objetivo de reduzir a
quantidade de horas-extra e de jornadas. A fusão é realizada inserindo em uma jornada todas as
viagens de outra jornada que podem ser realizadas antes do início ou após o fim da primeira.
A escolha da próxima operação a ser realizada envolve a avaliação do ganho resultante e
a viabilidade de remoção de viagens de atendimento à demanda (i.e., que as mesmas sejam
redundantes para o atendimento). São avaliadas todas as remoções possíveis de viagens do início
ou do fim de cada jornada, bem como a fusão de todas as jornadas entre si. A principal meta
definida foi a redução de jornadas, sendo secundária a diminuição da quantidade total de horasextra. Como critério de desempate, foi escolhida sempre a operação que removesse menos
viagens de atendimento à demanda. Dessa forma, o melhor benefício é obtido mantendo o maior
número possível de viagens de atendimento redundantes para serem utilizadas em etapas
posteriores da busca local.
Uma das grande vantagens da utilização desses operadores foi que tornou possível a
obtenção de soluções fora do espaço gerado pela prévia enumeração de jornadas, garantido uma
diversidade adicional não prevista em outros trabalhos envolvendo a abordagem por enumeração
antecipada.
3.3. Ligação de caminho
A ligação de caminho (ou Path Relinking, na literatura em inglês) é uma espécie de
busca local guiada, i.e., partindo de uma solução origem, as operações de modificação da solução
devem ser tais que a mesma se transforme progressivamente em uma solução destino préestabelecida. A estratégia foi proposta como uma forma de intensificação da exploração das
regiões adjacentes a boas soluções (Glover e Laguna (1997) e Resende e Ribeiro (2003-2)),
sendo aplicada ao GRASP em Laguna e Marti (1999). É sugerido na literatura (Resende e
Ribeiro (2003-1)) que uma forma de economizar tempo com esse procedimento seja realizando o
mesmo apenas a partir da melhor entre as duas soluções envolvidas e truncando a busca quando a
qualidade da solução intermediária deixar a desejar. Entretanto, alguns resultados apresentados a
seguir sugerem fortemente o caminho contrário para a abordagem gulosa de ligação de caminho.
A implementação no módulo resolvedor envolveu um processo de remoção de jornadas
da solução origem associado à inserção de jornadas pertencentes à solução destino. As jornadas
foram ordenadas de acordo com sua quantidade de horas-extra. As jornadas da solução destino
foram sendo inseridas uma a uma, em ordem crescente de horas-extra. Para cada jornada
inserida, era avaliada a possibilidade de remoção de cada uma das jornadas restante da solução
origem, partindo daquela com maior quantidade de horas-extra. O procedimento inverso procurar aumentar a quantidade de horas-extra visando diminuir a quantidade de jornadas - não
obteve melhores resultados em nenhum dos testes durante a implementação.
Cada solução gerada pelo GRASP e tratada pela busca local foi utilizada para ligação de
caminho com todas as soluções presentes no conjunto de elite, tanto como origem quanto como
destino do caminho traçado, sendo então avaliado se a melhor solução obtida pelo caminho
realizado poderia ser inserida no conjunto de elite.
3.4. Paralelismo em dois níveis
O procedimento de geração de soluções foi paralelizado através da utilização de um
XXXVIII SBPO
[ 968 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
protocolo de passagem de mensagens. Conforme testes realizados durante a implementação do
módulo resolvedor, o principal gargalo de execução consistia no processo de geração de soluções
iniciais pelo GRASP. Dessa forma, a estratégia inicial de paralelismo focou principalmente um
aumento na criação de soluções através da geração simultânea. O módulo inicializa uma
quantidade N de processos, sendo que um deles se comporta como mestre, e os demais como
escravos. A tarefa dos escravos é gerar soluções e submetê-las ao mestre, onde é realizada a
busca local e é mantido um conjunto de elite para a realização da ligação de caminho. Como não
havia sido aplicada busca local às soluções transmitidas, a comunicação entre escravo e mestre
podia ser resumida à transmissão dos índices das jornadas utilizadas numa enumeração
compartilhada de elementos.
A segunda etapa da implementação de paralelismo consistiu no estabelecimento de uma
estratégia de colaboração entre os processos visando um ganho em qualidade, além do ganho em
tempo. Um parâmetro adicional M foi estabelecido: os N processos inicializados são divididos
em sub-blocos de M processos cada. Cada sub-bloco possui um mestre, e o conjunto de mestres é
interligado através de uma topologia na forma de anel. Quando a solução gerada pelo escravo de
um mestre é boa o suficiente para ser inserida no conjunto de elite local, essa solução é
transmitida pelo mestre a seus dois vizinhos.
Foi tomada a precaução de que a semente de geração aleatória de cada processo fosse
diferente, de forma que o paralelismo pudesse atingir uma melhor exploração do espaço de
soluções através da geração independente de soluções em pontos distintos do mesmo. Não foi
tentada uma paralelização visando a redução no tempo de geração das soluções individuais, pois
isso implicaria em uma carga alta de comunicação para a resolução de dependências durante o
processo de construção, tendo em vista o caráter adaptativo da meta-heurística, que torna
inviável qualquer paralelismo genérico no nível de geração de soluções.
4. Resultados
O módulo resolvedor foi programado em C++ e o paralelismo foi implementado
utilizando a biblioteca LAM-MPI. Os códigos foram compilados utilizando o compilador GNUGCC. Todos os testes foram realizados utilizando máquinas dual core Intel Xeon 2.4 GHz com 1
GB de RAM cada. Cada um desses dois processadores por máquina emulava dois processadores
virtuais distintos. No testes envolvendo paralelismo, foram utilizadas 4 dessas máquinas
conectadas por meio de uma rede local e fechadas a acesso para a execução de outras tarefas.
Todas as máquinas envolvidas operavam o sistema operacional Fedora Core 4.
Foram realizados testes sem paralelismo utilizando, para cada instância, 11 sementes
aleatórias e o conjunto de valores {0.60, 0.65, 0.70, 0.75, 0.80, 0.85, 0.90} para o parâmetro α,
com 5000 iterações por rodada. Os testes com paralelismo cooperativo envolveram 1 semente
aleatória geral e o conjunto de valores {0.60, 0.70, 0.80, 0.90} para α, com N=16 processos, M=2
processos para cada conjunto mestre e escravos, e 4000 iterações distribuídas (500 por bloco).
Outros testes utilizando ligação de caminho e paralelismo para análise de comportamento dos
métodos são descritos nas respectivas seções a seguir.
4.1. Análise comparativa
Os melhores resultados obtidos pelo módulo resolvedor são apresentados na tabela 2, de
acordo com as instâncias oriundas das cidades de São Paulo e de São Bernardo do Campo, e
comparados com as soluções manuais, as obtidas por meio de Programação Linear Inteira (PLI)
em Rodrigues (2001), Programação por Restrições associada a Programação Linear Inteira (PRPLI) em Vaz (2003) e Programação por Restrições associada a Busca Tabu e Algoritmo Genético
Paralelizado (BTP e AGP) em Ciré et. al. (2005).
Os parâmetros utilizados para a comparação das soluções foram o número de ônibus
(NO), número de motoristas (NM) e total de horas-extra (HE), além do tempo médio de
execução dos módulos (TE). A geração da enumeração, realizada apenas uma vez por instância,
não foi computada nesse tempo de execução por esse mesmo motivo. O tempo de geração para
cada instância é de cerca de 5 a 10 minutos. O tempo considerado no caso do GRASP foi do
módulo não paralelizado, como forma de comparação mais justa com as demais abordagens.
XXXVIII SBPO
[ 969 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
Constatamos que a solução obtida pelo GRASP foi melhor em 4 das 6 instâncias. O
tempo de execução excedeu em alguns casos aquele apresentado por outras meta-heurísticas
devido ao tamanho do conjunto de elementos constituintes da solução, que se provou um gargalo
muito evidente na implementação do resolvedor GRASP para o PPV. De uma maneira geral, a
qualidade das soluções se manteve uniforme no conjunto de instâncias quando comparada com a
dos outros métodos, e o tempo de execução foi muito bom – considerando que esse tempo é para
o módulo não paralelizado.
Instância Parâmetro Manual
2280
376
702
476
5758
2210
PLI
PR-PLI
BTP
AGP
GRASP
NO
-
31
19
17
16
17
NM
-
42
33
31
31
31
HE
-
15:48
38:34
15:55
23:40
19:46
TE
-
-
03:31:31
00:08:12
00:10:26
00:09:05
NO
19
20
13
10
10
10
NM
30
28
24
18
18
18
HE
11:44
18:01
02:58
05:36
08:00
01:53
TE
-
-
01:17:06
00:06:10
00:07:54
00:04:34
NO
32
35
23
20
20
20
NM
52
51
40
39
40
37
HE
34:25
02:15
03:26
03:36
09:13
06:58
TE
-
-
04:26:50
00:11:03
00:13:41
00:13:11
NO
-
12
11
9
9
9
NM
-
22
21
18
18
17
HE
-
08:05
03:49
01:23
02:15
00:00
TE
-
-
02:13:26
00:05:34
00:05:15
00:11:46
NO
-
10
8
7
8
7
NM
-
14
14
14
15
13
HE
-
13:13
12:10
03:27
02:24
00:24
TE
-
-
01:03:53
00:05:23
00:05:48
00:06:04
NO
-
33
26
21
21
21
NM
-
47
42
36
37
36
HE
-
21:42
35:34
19:38
14:38
41:50
08:24:43 00:09:37 00:11:12 00:18:07
TE
Tabela 2: Melhores soluções obtidas para o PPV através do método manual e de 4 outras
abordagens além do GRASP.
4.2. Análise das técnicas empregadas
4.2.1. Obtenção de soluções por ligação de caminho
A análise que se segue procurou avaliar a relação entre o parâmetro α da geração de
soluções do GRASP com a quantidade e a distribuição das melhores soluções obtidas em cada
aplicação da ligação de caminho. Uma implementação especial do módulo computou
informações sobre a proximidade da melhor solução do caminho com a solução origem e destino,
XXXVIII SBPO
[ 970 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
separando os casos em que a origem é a melhor entre as duas soluções e o destino é a melhor.
Essa proximidade foi calculada pela razão entre a quantidade de operações utilizadas para atingir
a melhor solução do caminho com relação à solução destino, havendo uma discretização em
intervalos de 1%.
A tabela 3 apresenta o percentual de ligações de caminho nas quais foi encontrada uma
solução melhor do que os extremos do caminho, sendo a solução origem a melhor ou a pior entre
as duas soluções, para cada valor de α no conjunto {0.60, 0.70, 0.80, 0.90}. As figuras 2 e 3
apresentam, respectivamente, a distribuição dessas soluções encontradas no caminho para
ligações de caminho partindo da melhor e da pior entre as duas soluções.
α
Partido da melhor solução Partindo da pior solução
0.60
09,9 %
49,0 %
0.70
05,2 %
36,1 %
0.80
07,7 %
35,2 %
06,5 %
32,6 %
0.90
Tabela 3: Percentual de execuções da ligação de caminho que
obtiveram soluções intermediárias melhores que os extremos, de
acordo com a qualidade do extremo de origem e o valor do parâmetro
α da geração.
Figura 2: Distribuição das soluções encontradas pela ligação de caminho (percentual das
operações de transformação realizadas quando a melhor solução foi encontrada) partindo da
melhor solução entre as duas envolvidas, com (a) α=0.60, (b) α=0.70, (c) α=0.80 e (d) α=0.90.
Podemos observar pelos resultados que a ligação de caminho executada com origem na
pior entre as duas soluções apresenta uma distribuição um pouco menos tímida nas proximidades
da pior solução e uma menor exploração do espaço em torno da melhor solução, mas com um
aumento na incidência de soluções encontradas de cerca de cinco vezes. Quanto menor o valor
do parâmetro α, maior a variabilidade das soluções e - conseqüentemente - maior a quantidade de
XXXVIII SBPO
[ 971 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
soluções encontradas no caminho.
4.2.2. Aceleração do resolvedor pelo paralelismo
Foram realizados dois testes envolvendo paralelismo. O primeiro deles procurou
estabelecer a aceleração quantitativa proporcionada pela implementação. Foram realizados testes
sobre tempo de execução para 1600 iterações na instância 2280 com α=0.70, executando 5 vezes
cada versão do módulo resolvedor utilizada: não-paralela (NP), paralela em primeiro nível (P1) e
paralela colaborativa (P2). O tempo médio de execução para cada configuração testada de cada
abordagem são apresentados na tabela 4, junto com a medida de aceleração para as versões
paralelas com relação à NP (Acel. paralela) e do ganho entre testes envolvendo P1 e P2 para um
mesmo número de processadores (Acel. Colaborativa).
Figura 3: Distribuição das soluções encontradas pela ligação de caminho (percentual das
operações de transformação realizadas quando a melhor solução foi encontrada) partindo da pior
solução entre as duas envolvidas, com (a) α=0.60, (b) α=0.70, (c) α=0.80 e (d) α=0.90.
Observamos que a prática mais eficiente consiste na utilização de blocos pequenos, com
praticamente um mestre por escravo. Por esse motivo, os ganhos com o aumento no número de
processos só foram sentidos com a abordagem colaborativa. Esses testes indicaram que a melhor
configuração para a abordagem colaborativa seria N=16 e M=2 para uma configuração como a
descrita para esses testes, tendo a mesma sido utilizada no segundo teste sobre convergência.
O teste sobre convergência se baseou na métrica utilizada por Aiex et. al. (2003): para
cada instância, foi estabelecida uma qualidade mínima da solução, de forma que o programa só
pararia quando atingisse essa meta. Cada instância foi rodada com o módulo não-paralelizado e
com o paralelo colaborativo, sendo α=0.70, utilizando 10 sementes diferentes e computando o
tempo médio de execução, ignorando o tempo mais rápido e o mais lento. Essa medida foi
tomada para evitar arbitrariedades devidas à escolha da semente (execuções muito rápidas ou
demoradas, deslocando muito o média com relação à mediana do conjunto de valores). Os
resultados são apresentados na tabela 5.
Conforme pode ser observado, os ganhos em desempenho qualitativo da abordagem
colaborativa foram muito superiores ao quantitativo em geração de soluções. Para todas as
XXXVIII SBPO
[ 972 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
instâncias o ganho foi superior ao número de máquinas, chegando a superar o número de
processadores reais em uma delas.
Versão
N
M
Execução
NP
-
-
381,0 s
-
-
P1
2
-
324,0 s
1,18
-
P1
4
-
314,6 s
1,21
-
P1
8
-
311,4 s
1,22
-
P1
16
-
360,8 s
1,06
-
P2
4
2
153,8 s
2,48
2,04
P2
8
2
134,2 s
2,84
2,32
P2
8
4
183,0 s
2,08
1,70
P2
16
2
088,0 s
4,33
4,10
P2
16
4
162,0 s
2,35
2,23
Acel. paralela Acel. colaborativa
Tabela 4: Tempo de execução e aceleração relativa para cada
configuração aplicada nas três versões do módulo testadas.
Instância Solução alvo
Tempo médio Tempo médio Aceleraçã
não paralelo colaborativo
o
2280
18 veículos
32 motoristas
232,25 s
40,25 s
5,77
376
10 veículos
19 motoristas
010,88 s
02,12 s
5,11
702
21 veículos
40 motoristas
061,75 s
09,12 s
6,77
476
10 veículos
18 motoristas
062,88 s
10,88 s
5,78
5758
7 veículos
14 motoristas
067,75 s
07,25 s
9,34
2210
22 veículos
39 motoristas
044,12 s
06,00 s
7,35
Tabela 5: Tempo de execução médio para atingir a solução alvo de cada
instância e aceleração relativa à utilização de paralelismo.
5. Conclusões e trabalhos futuros
A qualidade das soluções e o tempo de execução do módulo resolvedor foram tão bons
quanto, ou em certos casos um pouco melhores, do que aqueles obtidos por outras abordagens
utilizando meta-heurísticas paralelas. A utilização do GRASP para o PPV provou-se tanto viável
quanto altamente interessante, sendo esta contribuição valiosa para o incentivo ao surgimento de
outros trabalhos envolvendo o emprego dessa técnica, não só em problemas na área de
transportes.
A abordagem paralela colaborativa atingiu um ganho considerável em eficiência, e os
resultados dos estudos envolvendo ligação de caminho constituem um material promissor para a
realização de estudos futuros que explorem mais a fundo as características do método.
Com relação ao PPV, espera-se realizar a integração desse módulo resolvedor com outras
XXXVIII SBPO
[ 973 ]
XXXVIII SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL
Pesquisa Operacional na Sociedade: Educação, Meio Ambiente e Desenvolvimento
12 a 15/09/06 Goiânia, GO
meta-heurísticas em uma abodagem paralela hibridizada. A obtenção de instâncias adicionais
sujeitas a restrições semelhantes seria de grande valia para atestar que a qualidade apresentada
nas instâncias trabalhadas pode ser estendida ao caso geral.
6. Agradecimentos
Este trabalho contou com aporte financeiro da Fundação de Amparo à Pesquisa do
Estado de São Paulo (FAPESP) através do processo 04/13159-9.
7. Bibliografia
Aarts, E. e Lenstra, J. Local Search in Combinatorial Optimization. Willey & Sons, 1st edition,
1996.
Aiex, R.M., Binato, S. e Resende, M.G.C. (2003), Parallel GRASP with path-relinking for job
shop scheduling. Parallel Computing, 29:393-430.
Ciré, A.A., Lopes, T.M.T. e Moura, A.V. (2005), Hibridização de programação por restrições e
metaheurísticas paralelas para o escalonamento integrado de veículos e tripulação. Anais do
XXXVII SBPO.
Duni, S., Pardalos, P.M., e Resende, M.G.C. Parallel metaheuristics for combinatorial
optimization. In Models for Parallel and Distributed Computation – Theory, Algorithmic
Techniques and Applications, pages 179-206. Kluwer Academic Publishers, 2002.
Feo, T.A. e Resende, M.G.C. (1989), A probabilistic heuristic for a computationally difficult set
covering problem. Operations Research Letters, 8:67–71.
Feo, T.A. e Resende, M.G.C. (1995), Greedy randomized adaptive search procedures. J. of
Global Optimization, 6:109–133.
Festa, P. e Resende, M.G.C. (2002), GRASP: An annoted bibliography. Essays and Surveys on
Metaheuristics, pages 325-367. Kluwer Academic Publishers.
Gabow, H.N. (1976), An efficient implementation of Edmond's algorithm for maximum
matching on graphs. JACM, 23:221–234.
Glover , F. e Laguna, M. Tabu Search. Kluwer Academic Publishers, Boston, 1997.
Goldbarg, M. e Luna, H. Otimização Combinatória e Programação Linear: Modelos e
Algoritmos. Editora Campus, 1a edição, 2000.
Laguna, M. e Marti, R. (1999), GRASP and Path Relinking for 2-Layer Straight Line Crossing
Minimization. Journal on Computing, 11(11);44-52.
Lourenço, H.R., Paixão, J.P. e Portugal, R. (2001), Multiobjective metaheuristics for the busdriver scheduling problem. Transportation Science, 35(3):331–343.
Resende, M.G.C. Greedy randomized adaptive search procedures (GRASP). In Encyclopedia of
Optimization, volume 2, pages 373-382. Kluwer Academic Publishers, 2001.
Resende, M.G.C. e Ribeiro, C.C. (2003), A GRASP with path-relinking for private virtual
circuit routing. Networks, 41(1):104–114.
Resende, M.G.C. e Ribeiro, C.C. (2003), GRASP and path-relinking: Recent advances and
applications. Proceedings of the Fifth Metaheuristics International Conference (MIC2003),
pages T6-1 - T6-6.
Resende, M.G.C. e Ribeiro, C.C.. Greedy randomized adaptive search procedures. In
Handbook of Metaheuristics, pages 219-249. Kluwer Academic Publishers, 2002.
Rodrigues, M.M. Problema de planejamento de viagens no transporte coletivo. Dissertação de
mestrado, Instituto de Computação – Unicamp. 2001.
Souza, M., Cardoso, L. e Silva, G. (2003), Programação de tripulações de ônibus urbano: uma
abordagem heurística. Anais do XXXV SBPO, 1285–1294.
Vaz, G.J. Uma abordagem alternativa para o escalonamento de ônibus e motoristas.
Dissertação de mestrado, Instituto de Computação – Unicamp. 2003.
Wren, A. (1998), Heuristics ancient and modern: Transport scheduling through the ages.
Journey of Heuristics, (4):87–100.
Yunes, T.H. Problemas de escalonamento no transporte coletivo : programação por restrições
e outras tecnicas. Dissertação de mestrado, Instituto de Computação – Unicamp. 2000.
XXXVIII SBPO
[ 974 ]