Revista TRANSPORTES: Artigos sobre Logística e Segurança Viária

Prévia do material em texto

anpet 
associação nacional de pesquisa e ensino em transportes 
 
 
 
 
 
 
TRANSPORTES 
volume 9 • número 2 • novembro de 2001 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Transportes - vol 1, n. 1 (jun. 1993). - Rio de Janeiro, Associação 
Nacional de Pesquisa e Ensino em Transportes. 1993 - v; 21 cm 
 
 
Semestral 
ISSN 1415-7713 
 
 
1. Transporte-Periódico. 
I. Associação Nacional de Pesquisa e Ensino em Transportes. 
 
 
CDD 20 ed. 388 
TRANSPORTES 
volume 9 - número 2 - novembro de 2001 
 
 
 
SUMÁRIO 
 
 
 
 
 
 
EDITORIAL ................................................................................................7 
 
 
ARTIGOS 
 
 
UMA PROPOSTA ALTERNATIVA PARA AVALIAÇÃO DO 
DESEMPENHO DE SISTEMAS DE TRANSPORTE EMERGENCIAL DE 
SAÚDE BRASILEIROS 
Renata Algisi Takeda, João Alexandre Widmer & 
Reinaldo Morabito................................................................................................ 9 
 
UMA ABORDAGEM ADAPTATIVA DE BUSCA TABU APLICADA AO 
PROBLEMA DE ROTEAMENTO DE VEÍCULOS 
Vitória Pureza & Paulo Morelato França .......................................................... 28 
 
AUDITORIA DA SEGURANÇA VIÁRIA 
Christine Tessele Nodari & Luis Antonio Lindau..............................................48 
 
AVALIAÇÃO DA INFLUÊNCIA DO TIPO DE CIMENTO NA 
EXPANSIBILIDADE DAS MISTURAS DE FOSFOGESSO E CIMENTO 
Andréa Regina Kaneko Kobayashi & Alexandre Benetti Parreira......................67 
 
 
 
 
 
 
ESPECIAL 
 
TRANSPORTES NO BRASIL: QUE HISTÓRIA CONTAR? 
Joaquim José Guilherme de Aragão, Oswaldo Lima Neto, 
Anísio Brasileiro, Enilson Medeiros dos Santos, José Menezes Senna & 
Rômulo Dante Orrico Filho................................................................................87 
 
 
RESENHA 
 
THE TRANSIT METROPOLIS: A GLOBAL INQUIRY 
Ronaldo Balassiano...........................................................................................108 
 
 
NORMAS PARA PUBLICAÇÃO ..............................................................119 
 
 
 
 
 
 
EDITORIAL 
 
 
Liedi Bariani Bernucci 
Editora de TRANSPORTES 
 
 
Este número completa o volume 9 da TRANSPORTES, referente ao 
ano de 2001. Um aspecto positivo a ser destacado nas edições deste 
ano foi o aumento da quantidade de artigos científicos publicados 
nos números de maio e de novembro. As duas edições contam com 
quatro artigos científicos, superando o observado nos últimos anos. 
Este crescimento tem se dado com garantia da qualidade da 
publicação, graças ao criterioso processo de seleção adotado pela 
TRANSPORTES. É fundamental que se mantenha o esforço da 
comunidade científica da área para sustentar esta tendência positiva, 
para que a revista possa receber o apoio financeiro também de órgãos 
de fomento, os quais estabelecem, entre outros critérios de avaliação, 
números mínimos de artigos publicados por edição. 
 
Os quatro artigos publicados neste número da TRANSPORTES 
abordam temas diversos, abrangendo da pesquisa sobre materiais 
para pavimentação ao desenvolvimento de técnicas de otimização 
aplicadas a problemas de Logística. O artigo de Takeda et al. 
apresenta uma aplicação do modelo hipercubo de filas para a 
avaliação do desempenho de sistemas de transporte emergencial de 
saúde. Os autores descrevem a aplicação desse modelo para o 
município de Campinas, SP, avaliando cenários alternativos de 
organização do serviço, comparativamente à configuração atual. O 
segundo artigo, de autoria de Pureza & França, explora a aplicação 
de técnicas heurísticas de otimização de busca tabu ao problema 
clássico de roteamento de veículos, comparando os resultados com 
os obtidos por outros métodos. A abordagem adaptativa proposta 
pelos autores apresenta vantagens ao poupar recursos 
computacionais sem sacrificar a qualidade das soluções obtidas. 
Nodari & Lindau fazem uma revisão das técnicas de Auditoria da 
8 TRANSPORTES 
Segurança Viária, utilizada com sucesso em alguns países na redução 
de acidentes viários. Os autores apontam a utilização ainda 
incipiente destas técnicas no Brasil e indicam benefícios potenciais 
significativos decorrentes de seu uso. Finalmente, o artigo de 
Kobayashi & Parreira apresenta um estudo laboratorial sobre a 
potencialidade de aproveitamento de fosfogesso, resíduo sólido 
gerado em grandes quantidades na fabricação de fertilizantes, como 
material de construção de camadas de pavimentos. O enfoque 
principal da pesquisa é a redução de expansão deste produto pela 
adição de cimento Portland de diferentes naturezas e em teores 
diversos, procurando viabilizar a destinação de um produto que tem 
apresentado problemas de armazenagem e ambientais. 
 
A revista traz ainda um artigo Especial, “Transportes no Brasil: que 
história contar?”, de autoria de Aragão et al., onde os autores, em 
uma abordagem original na área, fazem um exercício metodológico 
para identificar os períodos e as questões relevantes para os 
pesquisadores que objetivam historiar os transportes em nosso país. 
Na seção Resenha, encerrando este número da TRANSPORTES, 
Balassiano faz a revisão do livro The Transit Metropolis: a global 
inquiry, de Robert Cervero. O livro propõe uma tipologia de áreas 
urbanas e seus sistemas de transportes públicos, descrevendo 
exemplos de 12 cidades em diversos países. 
 
Os artigos recebidos em fluxo contínuo têm sido selecionados por 
meio de avaliação pelo Conselho Editorial e por Assessores Ad-Hoc 
que procedem a uma análise baseada em diversos aspectos 
considerados de relevância para uma publicação científica. Têm sido 
convidados e incluídos na revista, artigos originalmente 
encaminhados para os congressos anuais da Associação e que 
recebem avaliação destacada pelo Comitê Científico da ANPET 
devido à conjugação de qualidade e originalidade. 
 
Graças aos nossos patrocinadores, a ANPET cumpre mais uma vez 
sua meta de garantir a periodicidade semestral da TRANSPORTES. 
Externamos nossos sinceros agradecimentos pelo apoio recebido para 
este número: à ABCP – Associação Brasileira de Cimento Portland, à Rede 
Transportes - RECOPE e à Escola Politécnica da Universidade de São 
Paulo. 
 
ARTIGO 
 
UMA PROPOSTA ALTERNATIVA PARA 
AVALIAÇÃO DO DESEMPENHO DE 
SISTEMAS DE TRANSPORTE 
EMERGENCIAL DE SAÚDE 
BRASILEIROS 
 
 
Renata Algisi Takeda 
João Alexandre Widmer 
Departamento de Transportes 
Escola de Engenharia de São Carlos 
Universidade de São Paulo 
 
Reinaldo Morabito 
Departamento de Engenharia de Produção 
Universidade Federal de São Carlos 
 
 
RESUMO 
 
A rapidez na realização do atendimento às vítimas é uma das 
maiores exigências dos serviços de atendimento médico de urgência, 
e o tempo decorrido entre o instante da ocorrência da solicitação pelo 
serviço e o início do atendimento junto às vítimas é um dos 
principais fatores que influenciam o desempenho do sistema. Este 
tempo depende das condições do tráfego, dia e período do dia, 
número de veículos disponíveis e suas localizações, capacitação 
profissional da equipe, etc. Este trabalho apresenta uma análise do 
desempenho atual do serviço oferecido pela cidade de Campinas-SP, 
tratando o problema por meio do modelo hipercubo de filas, que 
considera as variações aleatórias dos processos de chegadas e 
atendimento dos chamados. Sua aplicação produz uma ampla 
variedade de indicadores de desempenho para o sistema, além de 
possibilitar, através da investigação de cenários alternativos, a busca 
de configurações operacionais com melhores níveis de serviço. 
10 TRANSPORTES 
 
ABSTRACT 
 
One of the major concerns in medical emergency systems is the 
quickness to accomplish the attendance to the victims.Its 
performance is mainly influenced by the time elapsed between the 
emergency call and the rescue. This time depends on the traffic 
features, the day and the hour, the number of available vehicles and 
their locations, professional team training, etc. This paper presents a 
performance analysis of the current service offered in Campinas-SP, 
facing the problem through the hypercube queuing model, which 
considers stochastic variations of the arrivals and service processes. 
Its application produces a wide variety of system performance 
measures, besides making possible, through a careful investigation of 
alternative sceneries, the indication of a better operational 
configuration looking for the service level increase. 
 
1. INTRODUÇÃO 
 
A qualidade de vida da população está ligada a uma diversidade de 
serviços que podem ser classificados em três grandes grupos: 
serviços de rotina, serviços semi-emergenciais e serviços de 
emergência, dentre os quais destaca-se o Serviço de Atendimento 
Médico de Urgência (SAMU). Quando projetado e operado com 
eficiência, o SAMU pode salvar vítimas; por outro lado, quando 
ineficiente, é um potencial responsável pelo agravamento clínico dos 
casos. 
 
A função básica de um SAMU é responder de forma organizada, a 
fim de evitar o uso excessivo de recursos, a toda situação de urgência 
que necessite de meios médicos, desde o primeiro contato telefônico 
até a liberação das vítimas ou seus encaminhamentos hospitalares. O 
sistema deve determinar e desencadear a resposta mais adequada 
para o caso, assegurar a disponibilidade dos meios hospitalares, 
determinar o tipo de transporte exigido e preparar o acolhimento dos 
pacientes. 
 
Serviços emergenciais como os SAMU’s apresentam altos graus de 
incerteza, e normalmente suas eficiências são medidas através do 
ARTIGO – UMA PROPOSTA ALTERNATIVA PARA… 11 
 
tempo médio de resposta a um chamado, ou seja, o tempo que uma 
vítima espera em média para começar a receber algum tipo de 
atendimento. Quanto maior o grau de incerteza envolvido e maior a 
necessidade de se obter respostas rápidas, menor deve ser a taxa de 
utilização dos operadores e equipamentos do sistema. Caso 
contrário, o nível de serviço oferecido pode ser deteriorado. Neste 
contexto, quando bem dimensionados, geralmente ocorrem longos 
períodos em que os operadores e equipamentos permanecem 
desocupados (Gonçalves, 1994). 
 
Muitas pesquisas vêm sendo desenvolvidas no sentido de se obter 
métodos para analisar e dimensionar tais sistemas, de forma a elevar 
o nível de serviço oferecido e também racionalizar os recursos 
exigidos. No entanto, uma limitação dos estudos é que muitos deles 
não consideram a natureza probabilística dos processos de chegada e 
atendimento dos chamados, e não levam em conta o fato de que as 
ambulâncias nem sempre estão disponíveis para iniciar um 
atendimento. Dentre as importantes contribuições, destacam-se 
trabalhos onde a atenção é concentrada em questões tais como 
localização de bases, roteirização de veículos, zoneamento da área de 
atuação do sistema e problemas de congestionamento. A modelagem 
integrada destas questões é muito complexa, pois geralmente os 
sistemas reais são compostos por um grande número de veículos, as 
solicitações por serviço ocorrem temporária e espacialmente, existe 
cooperação entre veículos de áreas distintas, podem ocorrer 
múltiplos despachos para atender a um mesmo chamado, o tempo 
médio de viagem varia de acordo com a região, o dia e o período do 
dia, e existe a possibilidade de formação de filas de espera. 
 
Alguns pesquisadores dedicaram-se exclusivamente a problemas de 
localização de bases (Toregas et al., 1971, Anderson e Fontenot, 1992 e 
Louveaux, 1993), enquanto outros consideraram o problema de 
projeto das áreas de cobertura específicas (Keeney, 1972 e Larson, 
1974). Daskin e Stern (1981) usaram problemas de cobertura com o 
objetivo de determinar o número necessário de veículos para cobrir 
cada região individualmente, e também para um conjunto de regiões 
vizinhas. 
 
12 TRANSPORTES 
 
Outra maneira de se abordar o problema é por meio de modelos de 
simulação. Savas (1969) usou um modelo de simulação na cidade de 
Nova Iorque para mostrar que o tempo médio de resposta a um 
chamado pode ser reduzido redistribuindo as ambulâncias em suas 
bases, enquanto Swoveland et al. (1973) aplicaram um modelo de 
simulação para determinar o tempo médio de resposta das 
ambulâncias em toda a extensão de Vancouver e, usando o algoritmo 
branch and bound, determinou novas localizações e novas 
configurações das áreas de cobertura do sistema a fim de reduzir o 
tempo médio de resposta. Fitzsimmons (1973) desenvolveu um 
modelo baseado em teoria de filas para analisar a localização de 
ambulâncias na cidade de Los Angeles, que considera como principal 
fator o tempo médio de viagem de cada veículo a cada chamado. 
 
No presente trabalho utilizou-se o modelo hipercubo, desenvolvido por 
Larson (1974) e estudado por diversos autores (Swersey, 1994), para 
analisar o desempenho atual do serviço oferecido pelo SAMU da 
cidade de Campinas-SP. Trata-se de uma ferramenta analítica e 
descritiva que permite calcular uma ampla variedade de medidas de 
desempenho, que auxiliam nas decisões operacionais e de 
configuração do sistema (Brandeau e Larson, 1986). O hipercubo não 
é um modelo de otimização que determina uma configuração ótima 
para o sistema, mas fornece uma completa avaliação de desempenho 
de cada configuração sugerida (Halpern, 1977). 
 
A aplicação original do modelo foi para o problema de 
patrulhamento policial. Porém, sistemas como bombeiros, 
ambulâncias, defesa civil, reparos em redes de infra-estruturas 
básicas, guinchos e entregas domiciliares também podem ser bem 
representados por esta técnica. No Brasil, alguns exemplos 
importantes são: o atendimento a interrupções de energia elétrica em 
Florianópolis, SC (Albino, 1994), a localização de ambulâncias em um 
trecho da BR 111 – SC (Gonçalves et al., 1994, 1995), e o 
balanceamento das workloads de ambulâncias no sistema Anjos do 
Asfalto da Rodovia Presidente Dutra (Mendonça e Morabito, 2000). 
Um exame recente do uso do modelo hipercubo na solução de 
problemas de localização probabilísticos foi apresentado em 
Chiyoshi et al. (2000). 
ARTIGO – UMA PROPOSTA ALTERNATIVA PARA… 13 
 
2. UMA BREVE APRESENTAÇÃO DO MODELO HIPERCUBO 
 
2.1. Descrição do sistema e utilização do modelo 
 
Em um sistema de atendimento de emergência, as principais 
hipóteses são: 
 
• os chamados chegam em instantes distintos, de diferentes 
partes de uma região, em uma central telefônica; 
 
• caso exista um veículo disponível, ele é despachado para o 
local do evento; caso contrário, o primeiro a se tornar “livre” 
é alocado para realizar o atendimento, ou o chamado é 
transferido para outro sistema de atendimento; 
 
• ao chegar junto às vítimas, a equipe despende um tempo no 
local do evento (tempo em cena), as transporta até um 
hospital (caso necessário), e então retorna a sua base, estando 
pronta para realizar um novo atendimento. 
 
O modelo hipercubo considera a cidade particionada em um número 
finito de regiões, denominadas átomos geográficos. O analista coleta 
informações do processo de chegada das solicitações de cada átomo 
(intervalos de tempo entre chegadas), processo de atendimento de 
cada servidor (tempos de atendimento), e tempos de viagem entre 
todos os pares de átomos, para descrever estatisticamente as 
operações do sistema e realizar a calibração do modelo. Uma vez 
calibrado, o hipercubo pode ser usado para determinar indicadores 
de desempenho para diferentes configurações do sistema. Para cada 
configuração, o modelo calcula medidas de desempenho para: (i) a 
extensão total da região, (ii) um veículo específico, (iii) um 
subconjuntofinito de átomos, e (iv) um átomo específico. Baseado 
nos resultados produzidos e nas exigências do sistema, o tomador de 
decisões pode pesquisar configurações alternativas que ofereçam 
níveis de serviço mais elevados aos usuários. 
 
 
14 TRANSPORTES 
 
2.2. A matemática do modelo básico 
 
A modelagem pressupõe que a área a ser estudada seja particionada 
em NA regiões (átomos geográficos), cada qual gerando uma fração fj 
do número total de solicitações de serviços 


 =∑
=
1
AN
1j
jf . O tempo 
médio de viagem entre dois átomos i e j quaisquer é dado por ijτ . 
Existem N veículos em operação no sistema, e a probabilidade de o 
veículo n estar localizado no átomo j é lnj 


 =∑
=
1
AN
1j
njl . Admite-se 
que os chamados ocorram no sistema conforme um processo de 
Poisson, com taxa média λ chamados por unidade de tempo (por 
exemplo, hora), sendo cada átomo j um gerador de processos de 
Poisson independentes com taxas médias jj f⋅λ=λ . Caso os 
servidores sejam homogêneos, com mesma taxa média µ de 
atendimentos por unidade de tempo, as medidas agregadas do 
modelo hipercubo equivalem às do modelo clássico M/M/N (com 
ou sem possibilidade de formação de fila, isto é, M/M/N/∞ ou 
M/M/N/0), sob as seguintes condições: 
 
• apenas um veículo é alocado para atender um chamado; 
 
• o tempo de atendimento de qualquer veículo tem 
distribuição exponencial negativa, com taxa média µ; 
 
• o tempo de atendimento é independente da identidade do 
servidor, da localização das vítimas e da história do sistema; 
 
• para o caso M/M/N/∞, todos os chamados que chegam 
enquanto os N veículos estão ocupados entram em fila, e são 
posteriormente atendidos segundo a disciplina first-come, 
first-served (FCFS); 
 
ARTIGO – UMA PROPOSTA ALTERNATIVA PARA… 15 
 
• para o caso M/M/N/0, todos os chamados que chegam 
enquanto os N veículos estão ocupados são perdidos (ou 
transferidos para outro sistema de atendimento). 
 
Para cada átomo, a política de despachos de veículos é fixada por 
meio de uma ordem de preferências de despachos, como mostra a tabela 1 
(nji indica o i-ésimo servidor escolhido para atender um chamado do 
átomo j). 
 
Tabela 1: Matriz de preferências de despachos 
Veículo Átomo 
1ª preferência 2ª preferência 3ª preferência … Nª preferência 
M M M M M 
j nj1 nj2 nj3 … njN 
M M M M M 
 
Consideradas todas estas hipóteses, o sistema pode ser caracterizado 
como um processo de Markov em tempo contínuo, com O(2N) 
possíveis estados, para todas as combinações (livre/ocupado) 
admissíveis para os veículos. Cada estado do sistema é representado 
por uma seqüência de N 0´s e 1´s, onde, em cada posição n da 
seqüência, o valor 0 corresponde à condição “livre” (ou disponível) 
do servidor n, e 1 à condição “ocupado”. Com isto, as probabilidades 
de equilíbrio de estado podem ser calculadas, analogamente às 
probabilidades de estado do modelo M/M/N, resolvendo-se um 
sistema linear com O(2N) equações e incógnitas, gerando uma grande 
variedade de indicadores de desempenho para o sistema. 
 
2.3. Extensão do modelo básico: atendimentos com prioridades 
 
Muitos sistemas reais contêm regras operacionais complexas, que 
nem sempre são facilmente descritas nos modelos analíticos, como é 
o caso de sistemas com múltiplas classes de usuários. Serviços que 
possuem atendimentos diferenciados quanto ao tipo de veículo, 
formação da equipe, ou até procedimentos tomados junto às vítimas, 
também podem ser representados pelo modelo hipercubo. Um 
exemplo é o SAMU de Campinas-SP, onde o sistema é composto por 
ambulâncias de quatro tipos distintos: VSA (veículos de suporte 
avançado, ou seja, as unidades de tratamento intensivo móveis), VSB 
16 TRANSPORTES 
 
(veículos de suporte básico, semelhante ao veículo-resgate do corpo de 
bombeiros), VRS (veículos de remoção simples) e PSQ (veículos 
psiquiátricos). 
 
Para modelar tal situação, Larson e Odoni (1981) recomendaram o 
“processo de camadas”, onde cada átomo é particionado em “sub-
átomos”, um para cada tipo de chamado do átomo original, e então 
os veículos específicos para realizar o atendimento são considerados 
como primeiras prioridades de despacho para o átomo. Esta simples 
adaptação permite o cálculo de todos os indicadores de desempenho 
para cada classe de usuários e cada tipo de veículo, separadamente, e 
também para o sistema como um todo. 
 
2.4. Indicadores de desempenho 
 
Determinadas as probabilidades de equilíbrio, o modelo produz 
algumas medidas importantes para avaliar o comportamento do 
sistema para uma dada configuração operacional. Dentre elas: 
 
• probabilidade de existência de fila: PQ; 
 
• workload ou fator de utilização dos veículos: ρn, n = 1, ..., N 
(na prática, este valor representa a fração do tempo em que o 
veículo n está ocupado); 
 
• freqüência de despachos inter-átomos fnj, isto é, fração de 
todos os despachos que enviam o veículo n ao átomo j, que 
pode ser decomposta em: 
 
fnj = f [1]nj+ f [2]nj (1) 
 
onde 
f [1]nj :fração dos despachos do veículo n ao átomo j, para 
atender a um chamado que não vem de fila, e 
f [2]nj :fração dos despachos do veículo n ao átomo j, para 
atender a um chamado que vem de fila de espera; 
 
ARTIGO – UMA PROPOSTA ALTERNATIVA PARA… 17 
 
• tempo médio de viagem para chamados sujeitos a esperas 
em fila: 
∑∑
= =
⋅⋅= A A
N
1i
N
1j
ij2
ji
Q τλ
λλ
T (2) 
• tempo médio de viagem do veículo n ao átomo j: 
∑
=
τ⋅= A
N
1k
kjnknjt l (3) 
 
• tempo médio de viagem para o átomo j: 
( ) ∑∑
∑
=
=
= ⋅⋅


λ
λ+−⋅
⋅
= A
N
1i
'
Qij
i'
QN
1n
]1[
nj
nj
N
1n
]1[
nj
j PτP1
t
T
f
f
 (4) 
onde PQ’ = PQ + P11...1 representa a probabilidade de 
saturação do sistema (P11...1 é a probabilidade do sistema 
estar com todos os servidores ocupados); 
 
• tempo médio de viagem de cada veículo n: 
( )
( )NP
NPTt
TU
'
Q
N
1j
[1]
nj
'
QQ
N
1j
nj
]1[
nj
n
A
A
+
⋅+⋅
=
∑
∑
=
=
f
f
 (5) 
 
3. APLICAÇÃO DO MODELO NO SAMU-192 DE CAMPINAS 
 
Baseados no modelo francês de atendimento às urgências, os 
SAMU’s começaram a ser implantados em algumas cidades 
brasileiras no início da década de 90. Funcionam como centros 
reguladores das urgências médicas, oferecendo suporte básico de 
vida, com veículos adequados para tal e operadores preparados para 
realizar o atendimento de forma segura, não colocando em risco as 
condições de vida dos seus usuários. 
 
18 TRANSPORTES 
 
Muitos sistemas que hoje operam em cidades brasileiras surgiram a 
partir da parceria entre as Secretarias Municipais de Saúde e o Corpo 
de Bombeiros, com a chegada dos veículos RESGATE. Isto levou a 
um aumento considerável no nível de serviço oferecido, e os 
resultados positivos passaram a justificar novos recursos e 
investimentos no setor, além de resgatar a confiabilidade da 
população no tipo de atendimento. Atualmente, nota-se um crescente 
aumento no número de municípios que procuram adequar-se às 
modernas diretrizes de planejamento e operação do serviço de 
transporte por ambulância no país, visando alcançar níveis 
internacionais de qualidade no atendimento às urgências. 
 
3.1. A pesquisa de campo 
 
Dentre diversas cidades de pequeno, médio e grande porte 
consultadas, apenas oito se dispuseram a mostrar em detalhes os 
seus sistemas: Jaú, Rio Claro, Araraquara, São Carlos, Limeira, 
Piracicaba, Ribeirão Preto e Campinas. O principal objetivo desta 
primeira fase da pesquisa foi conhecer o ambiente e identificar os 
possíveis problemas a serem estudados, para construir um método 
de investigação eficaz, de acordo com a realidade envolvida. 
 
Emtodos os casos, observou-se a existência de uma base de dados 
significativa, com registros das principais informações a respeito da 
operação dos sistemas. Porém, interesses outros acabaram 
dificultando o acesso a algumas destas informações. Neste contexto, 
a cidade de Campinas, que dispunha de um sistema considerado 
modelo no Estado de São Paulo, interessou-se por participar do 
estudo, contribuindo de forma expressiva para o levantamento dos 
dados e a interpretação dos resultados obtidos posteriormente com a 
aplicação do modelo. A equipe de gerentes do SAMU-192 da 
Campinas julgava possuir um tempo médio de resposta aos 
chamados insatisfatório, se comparado aos padrões internacionais de 
excelência. 
 
ARTIGO – UMA PROPOSTA ALTERNATIVA PARA… 19 
 
3.2. O cenário observado 
 
Em 1998, o sistema operava com 18 ambulâncias, sendo 2 veículos de 
suporte avançado (VSA), 4 veículos de suporte básico (VSB), 11 
veículos de remoção simples (VRS) e 1 veículo psiquiátrico (PSQ). 
Dentre os 11 VRS’s, 7 eram dedicados às operações de remoções 
simples (pacientes agendados) e 4 operavam como sendo VSB’s, 
totalizando 10 veículos dedicados, de fato, às operações de urgência. 
Portanto, para efeito de análise, foram considerados apenas estes 10 
veículos, já que o caso de pacientes agendados e transferências 
psiquiátricas não são característicos de um sistema de transporte 
médico de urgência 
 
Todos os veículos permaneciam centralizados na base operacional do 
sistema, quando disponíveis, local onde se encontra, até o presente 
momento, a central telefônica 192 para onde convergem todos os 
chamados. O sistema também permite que seus usuários entrem em 
uma fila de espera (limitada, em média, por 1 usuário por veículo em 
operação), caso todas as ambulâncias estejam ocupadas no instante 
da ocorrência do evento. 
 
Figura 1: Atuação do SAMU-192 em Campinas-SP 
 
A equipe gerenciadora estava preocupada com o crescimento dos 
índices de utilização das ambulâncias em determinados períodos do 
dia, bem como dos tempos de espera das vítimas. Surgiram 
 CAMPINAS 
• Área: 796 km2 
• população estimada: 908.906 habitantes 
(Contagem Populacional, IBGE, 1996) 
 
 SAMU-192 
• média anual de atendimentos de urgência: 
30.000 
• motoristas/socorristas: 65 
• auxiliares de enfermagem: 49 
• enfermeiros: 6 
• técnicos de enfermagem: 3 
• médicos reguladores das emergências: 42 
• hospitais: 5 públicos 
 8 privados conveniados 
 base SAMU 
20 TRANSPORTES 
 
discussões sobre uma possível descentralização do serviço, ou seja, 
quanto uma localização estrategicamente descentralizada das 
ambulâncias poderia interferir no nível de serviço oferecido, e qual o 
número ideal de veículos para realizar a operação. 
 
3.3. A coleta de dados 
 
Para implementar o modelo hipercubo no SAMU-192 foi preciso 
levantar: 
 
• número de regiões de atuação do sistema (átomos 
geográficos), intervalos de tempo entre chegadas dos 
chamados, com as respectivas taxas médias de chegadas por 
região; 
 
• tempo médio de viagem entre todas as regiões; 
 
• tempos de atendimento, com os respectivos tempos médios 
de atendimento por ambulância, e a fração correspondente 
do tempo junto ao paciente (tempo em cena); 
 
• localização das ambulâncias. 
 
3.3.1. Átomos geográficos 
 
Há diversas maneiras de se representar os átomos geográficos de um 
sistema: através da divisão política da cidade, ou dos setores 
policiais, bairros, etc. Em Campinas, o SAMU obedece as regiões 
correspondentes às áreas de cobertura dos Centros de Saúde: Norte, 
Sul, Leste e Oeste, sendo também considerada uma região Central no 
entorno de sua base. 
 
A coleta de dados determinou taxas médias de solicitação pelo 
serviço distintas ao longo das 24 horas de operação do sistema. Para 
fins de modelagem, foi considerado o período de 10 às 14 horas, que 
representa o período crítico para os gerentes do sistema. Neste 
período, observou-se uma taxa média λ = 5,4 chamados/h. Também 
ARTIGO – UMA PROPOSTA ALTERNATIVA PARA… 21 
 
foram determinadas as taxas de cada área específica, sendo que as 
regiões periféricas e central apresentaram os maiores índices. 
 
Com isto, pode-se verificar, através da aplicação do teste não-
paramétrico Kolmogorov-Smirnov, a hipótese de que o processo de 
chegada de chamados no sistema, bem como os processos de 
chegada em cada região, seguem padrão poissoniano, com nível de 
significância de 5%. Esta verificação foi realizada a partir das 
observações dos intervalos de tempo entre chegadas de solicitações. 
 
3.3.2. Tempos de atendimento 
 
O tempo médio de atendimento observado no sistema foi de 65 
minutos, sendo de 63 minutos para os veículos avançados e de 66 
minutos para os veículos básicos. Estes valores foram determinados a 
partir das observações dos atendimentos realizados por todas as 
ambulâncias. Também foi verificado, através do teste de Kolmogorov-
Smirnov, que os tempos de atendimento das ambulâncias são 
exponencialmente distribuídos, com nível de significância de 5%. 
 
3.3.3. Localização das ambulâncias 
 
Quando disponíveis, as ambulâncias permaneciam centralizadas na 
base do SAMU. Uma das propostas para descentralização das 
mesmas era localizá-las nos pólos geradores de demanda do sistema. 
 
3.4. Introduzindo classes de usuários na modelagem 
 
Como mencionado anteriormente, o SAMU-192 de Campinas possui 
classes diferenciadas de usuários. Neste estudo, foram consideradas 
apenas duas classes: 
 
• básica – definida pelos chamados atendidos por VSB’s; 
 
• avançada – definida pelos chamados atendidos por VSA’s. 
 
As cinco regiões foram biparticionadas, gerando um total de 10 
átomos geográficos no sistema (Norte B, Norte A, Sul B, Sul A, Leste 
22 TRANSPORTES 
 
B, Leste A, Oeste B, Oeste A, Centro B, Centro A), conforme pode ser 
observado na figura 2. 
 
 
Figura 2: Redistribuição espacial do sistema 
 
4. VALIDAÇÃO DA TÉCNICA DE MODELAGEM 
 
O modelo foi implementado computacionalmente (linguagem Pascal, 
estação de trabalho IBM 3CT com 128 MB de memória e sistema 
operacional IBM AIX) e executado para as condições originais do 
sistema, ou seja, NA = 10 átomos e N = 10 ambulâncias, todas 
centralizadas na base quando disponíveis. 
 
Os resultados obtidos mostraram a eficiência do modelo hipercubo 
para avaliar o serviço de transporte médico-emergencial de 
Campinas, apresentando desvios pouco significativos com relação 
aos dados reais (desvio médio de 4,84%). A tabela 2 ilustra as 
workloads e os desvios com relação aos tempos médios de resposta de 
cada ambulância (outros indicadores de desempenho foram 
comparados, gerando desvios também pouco significativos). 
 
Estes valores confirmam as observações iniciais de que as workloads 
são relativamente altas, em se tratando de um serviço emergencial. 
Uma das vantagens deste cenário, onde todos os veículos encontram-
NA 
SA 
LA 
OA 
CA 
B 
B 
B 
B 
B 
Os veículos avançados foram 
alocados como primeiras 
preferências de despachos 
para os átomos Norte A, Sul 
A, Leste A, Oeste A e Centro 
A, e últimas opções, para os 
demais. 
 
A classe avançada representa 
10% do total de chamados de 
emergência do sistema 
ARTIGO – UMA PROPOSTA ALTERNATIVA PARA… 23 
 
se centralizados, é o fato de existir um bom balanceamento das 
workloads dentro de cada classe. 
 
A partir de então, novos cenários foram avaliados com o objetivo de 
encontrar melhores alternativas operacionais para o sistema. A 
seguir, serão apresentados apenas dois destes cenários (os demais 
podem ser encontrados em Takeda, 2000). 
 
Tabela 2: Resultados gerados pelo modelo hipercubo para a configuração 
original do sistema 
 Tempo médio de resposta (minutos) desvio 
 veículo Workload modelo amostra minutos% 
1 0,38 10,88 10,38 0,51 4,91 
V
SA
 
2 0,39 10,90 10,70 0,20 1,89 
3 0,63 14,22 13,39 0,83 6,22 
4 0,65 14,24 13,54 0,70 5,19 
5 0,62 14,23 14,30 -0,07 -0,49 
6 0,64 14,24 13,64 0,60 4,43 
7 0,63 14,23 13,17 1,06 8,09 
8 0,62 14,22 13,27 0,95 7,17 
9 0,64 14,24 13,23 1,01 7,61 
V
SB
 
10 0,65 14,24 13,76 0,47 3,42 
 
5. DESCENTRALIZAÇÃO DAS AMBULÂNCIAS 
 
Membros da comunidade médica julgam o tempo médio de resposta 
como sendo o principal indicador do desempenho de um sistema 
emergencial. Para avaliar o impacto da descentralização dos veículos, 
foram realizados testes com cenários onde os veículos básicos foram 
descentralizados. A tabela 3 compara os tempos médios de resposta 
do sistema original (centralizado) com os de um sistema 
descentralizado, onde as regiões Norte B, Oeste B e Centro B 
tornaram-se bases para dois veículos, ficando as regiões Sul B e Leste 
B (com baixas taxas de solicitação pelo serviço) com apenas uma 
ambulância, e os veículos avançados ainda posicionados no Centro. 
 
Baseados na equação (4), e calibrando os valores dos tempos médios 
de atendimento para esta nova configuração, os tempos médios de 
resposta diminuem sensivelmente quando é implantada a 
24 TRANSPORTES 
 
descentralização das ambulâncias. Observa-se que isto não ocorreu 
com a região CB devido ao fato de que esta é solicitada como 
primeiro back-up para todas as outras regiões, dado que a distância 
média percorrida entre o Centro e os demais átomos é um pouco 
menor do que entre quaisquer dois outros pares. Também observa-se 
que as diferenças entre os valores determinados para as regiões 
geradoras de chamados avançados não é muito significativa, visto 
que eles permanecem centralizados. 
 
Tabela 3: Tempos médios de resposta para cada região 
 
Outro cenário investigado foi com relação ao efeito causado pelo 
aumento do número de ambulâncias na operação diária. Incentivado 
pela tendência de redução do tempo médio de resposta a um 
chamado quando se tem um sistema descentralizado, avaliou-se os 
impactos causados ao se implantar duas novas ambulâncias em 
operação, ficando cada região geradora de chamados básicos com 
duas ambulâncias disponíveis. Os valores dos tempos médios de 
resposta encontrados diminuíram, em média, 30% com relação ao 
cenário original (aproximadamente 4 minutos), e em torno de 15% 
com relação ao cenário descentralizado para as oito ambulâncias 
básicas avaliado anteriormente. As workloads dos veículos básicos 
reduziram cerca de 30% com relação ao cenário original (de 0,64 para 
0,45), resultando em uma sensível redução da probabilidade de um 
chamado ocorrer quando todas as ambulâncias estão ocupadas (igual 
a 0,12 no sistema original e 0,05 para o sistema remodelado com os 
dois novos veículos). 
 Tempo médio de resposta (minutos) desvio 
átomo centralizado descentralizado Minutos % 
NB 16,01 11,06 -4,96 -30,95 
NA 13,09 12,48 -0,61 -4,63 
SB 15,93 13,01 -2,92 -18,31 
SA 13,00 12,69 -0,31 -2,42 
LB 15,96 12,68 -3,28 -20,56 
LA 13,03 12,65 -0,38 -2,88 
OB 15,76 11,25 -4,51 -28,63 
OA 12,83 12,26 -0,57 -4,45 
CB 5,50 7,84 2,34 42,59 
CA 4,33 4,58 0,25 5,83 
ARTIGO – UMA PROPOSTA ALTERNATIVA PARA… 25 
 
Convém salientar que os resultados aqui apresentados são ainda 
preliminares. Os resultados completos estão sendo compilados, junto 
com uma análise dos trade-off entre as várias configurações 
operacionais estudadas, e deverão ser reportados em breve. 
 
6. CONSIDERAÇÕES FINAIS 
 
O modelo hipercubo de filas, desenvolvido por Larson (1974) para 
redimensionar o patrulhamento policial na cidade de Nova Iorque, 
foi utilizado para avaliar o desempenho do serviço de transporte 
médico-emergencial da cidade de Campinas-SP. O modelo mostrou-
se uma ferramenta eficaz para auxiliar no planejamento e operação 
deste sistema. 
 
Observou-se que o processo de camadas é uma técnica eficaz para 
modelar sistemas com múltiplas classes de usuários, onde 
prioridades estão embutidas no processo de atendimento, como é o 
caso do SAMU da cidade de Campinas. A avaliação de cenários 
alternativos mostrou a importância da descentralização de 
ambulâncias no sistema, o que reduz consideravelmente o tempo 
médio de resposta a um chamado em relação ao da configuração 
atual e, com isso, aumenta as chances de sobrevivência das vítimas. 
 
A aplicação do modelo hipercubo no SAMU-192 contribuiu para 
difundir para a Rede Brasileira de Cooperação em Emergências 
(RBCE) a importância de conciliar a experiência administrativa da 
classe médica com o uso de ferramentas analíticas, para auxiliar nas 
decisões de planejamento e operação dos sistemas de transporte 
emergencial de saúde brasileiros. 
 
AGRADECIMENTOS 
 
Os autores agradecem à equipe do SAMU-192 de Campinas, em 
especial à Dra. Arine Campos Oliveira Assis, coordenadora do 
sistema, pelo apoio à realização da presente pesquisa. 
 
26 TRANSPORTES 
 
REFERÊNCIAS BIBLIOGRÁFICAS 
 
Albino, J. C. C. (1994) Quantificação e locação de unidades móveis de 
atendimento de emergência a interrupções em redes de distribuição de 
energia elétrica: aplicação do modelo hipercubo. Florianópolis. 66p. 
Dissertação (Mestrado) – Universidade Federal de Santa 
Catarina. 
Anderson, L. R. e R. A. Fontenot (1992) Optimal positioning of 
service units along a coordinate line. Transportation Science, v. 
26, n. 4, p. 346-351. 
Brandeau, M. L. e R. C. Larson (1986) Extending and applying the 
hypercube queueing model to deploy ambulances in Boston. 
TIMS studies in the Management Science, v. 22, p. 121-153. 
Chiyoshi, F.; R. D. Galvão e R. Morabito (2000) O uso do modelo 
hipercubo na solução de problemas de localização 
probabilísticos. Gestão & Produção, v.7, n.2, p.146-174. 
Daskin, M. S. e E. H. Stern (1981) A hierarchical objective set covering 
model for emergency medical service vehicle deployment. 
Transportation Science, v. 15, p. 137-152. 
Fitzsimmons, J. A. (1973) A methodology for emergency ambulance 
deployment. Management Science, v. 19, n. 6, p. 627-636. 
Gonçalves, M. B. (1994) Métodos de pesquisa operacional em 
serviços emergenciais. Anais do XXVIº Simpósio Brasileiro de 
Pesquisa Operacional, SOBRAPO, Florianópolis, v. 1, p. 597-601. 
Gonçalves, M. B.; A. G. N. Novaes e J. C. C. Albino (1994) Modelos 
para localização de serviços emergenciais em rodovias. Anais 
do XXVIº Simpósio Brasileiro de Pesquisa Operacional, SOBRAPO, 
Florianópolis, v. 1, p. 591-596. 
Gonçalves, M. B.; A. G. N. Novaes e R. Schmitz (1995) Um modelo de 
otimização para localizar unidades de serviços emergenciais 
em rodovias. Anais do IXº Congresso Brasileiro de Pesquisa e 
Ensino em Transportes, ANPET, São Carlos, v. 3, p. 962-972. 
Halpern, J. (1977) The accuracy of estimates for the performance 
criteria of certain emergency service queueing systems. 
Transportation Science, v. 11, n. 3, p. 227-242. 
Keeney, R. L. (1972) A method for districting among facilities. 
Operations Research, v. 20, n. 3, p. 613-618. 
ARTIGO – UMA PROPOSTA ALTERNATIVA PARA… 27 
 
Larson, R. C. (1974) A hypercube queueing model for facility location 
and redistricting in urban emergency services. Computer and 
Operations Research, v. 1, n. 1, p. 67-95. 
Larson, R. C. e A. R. Odoni (1981) Urban Operations Research. New 
Jersey, Prentice-Hall. 
Louveaux, F. (1993) Stochastic location analysis. Location Science, v. 1, 
p. 127-154. 
Mendonça, F. C. e R. Morabito (2000) Aplicação do modelo 
hipercubo para análise de um sistema médico-emergencial em 
rodovia. Gestão & Produção, v. 7, n. 1, p. 73-90. 
Savas, E. S. (1969) Simulation and cost-effectiveness analysis of New 
York’s emergency ambulance service. Management Science, v. 
15, n. 12, p.B-608 – B-627. 
Swersey, A. J. (1994) The deployment of police, fire and emergency 
medical units. Handbooksin OR &MS, v. 6, p. 151-200. 
Swoveland, C.; D. Uyeno; I. Vertinsky e R. Vickson (1973) 
Ambulance location: a probabilistic enumeration approach. 
Management Science, v. 20, n. 4, Part II, p. 686-698. 
Takeda, R. A. (2000) Uma contribuição para avaliar o desempenho de 
sistemas de transporte emergencial de saúde. São Carlos. Tese 
(Doutorado) – Escola de Engenharia de São Carlos, 
Universidade de São Paulo. 
Toregas, C.; R. Swain; C. ReVelle e L. Bergnan (1971) The location of 
emergency service facilities. Operations Research, v. 19, p. 1363-
1373. 
 
Endereço dos Autores: 
Renata Algisi Takeda 
João Alexandre Widmer 
Departamento de Transportes - EESC – USP 
Avenida Trabalhador São-Carlense, 400 
13566-590 - São Carlos-SP - Brasil 
E-mail: renata_at@uol.com.br 
widmer@usp.br 
 
Reinaldo Morabito 
Departamento de Engenharia de Produção – UFSCar 
Caixa Postal 676 
13565-905 - São Carlos-SP - Brasil 
E-mail: morabito@power.ufscar.br
 
ARTIGO 
 
UMA ABORDAGEM ADAPTATIVA DE 
BUSCA TABU APLICADA AO 
PROBLEMA DE ROTEAMENTO DE 
VEÍCULOS 
 
Vitória Pureza 
Departamento de Engenharia de Produção 
Universidade Federal de São Carlos 
 
Paulo Morelato França 
Departamento de Engenharia de Sistemas 
Faculdade de Engenharia Elétrica e de Computação 
Universidade Estadual de Campinas 
 
RESUMO 
 
Neste trabalho descrevemos experimentos com a abordagem 
adaptativa de busca tabu HTA que sistematicamente perturba 
elementos tabu selecionados. A natureza, grau e duração de cada 
perturbação é determinada pela análise de padrões descritos pelas 
trajetórias de busca mais recentes. O objetivo principal desta 
abordagem é o de alterar os níveis de restritividade de forma a 
intensificar a busca em regiões promissoras e de provocar 
diversificação se as possibilidades de melhoria parecem mínimas. 
Uma implementação tabu inicialmente aplicada ao Problema do 
Caixeiro Viajante (PCV) foi estendida ao Problema de Roteamento de 
Veículos (PRV). São analisados tempo computacional e qualidade de 
solução entre a implementação adaptativa e a implementação sem 
estes mecanismos. Os testes envolvem 14 problemas da literatura e as 
implementações foram sujeitas a níveis de restritividade não 
controlados e impostos por outros elementos tabu. Comparações de 
desempenho também incluem outros algoritmos de busca tabu 
competitivos. 
 
 
ARTIGO – UMA ABORDAGEM ADAPTATIVA… 29 
ABSTRACT 
 
This paper describes experiments on the adaptive tabu search HTA 
approach that systematically perturbs selected tabu elements. The 
nature, degree and span of each perturbation is determined by the 
analysis of patterns described by the most recent search trajectories. 
The main goal of this approach is to alter restrictiveness levels in 
order to intensify the exploration when the conditions indicate 
promising regions, and to yield diversification if improvement 
possibilities seem to be minimal. An adaptive tabu implementation 
initially applied to the Traveling Salesman Problem (TSP) was 
extended to the Vehicle Routing Problem (VRP). Our main purpose 
is to compare time and solution quality for this adaptive 
implementation and for the same implementation deprived of 
adaptive mechanisms. Tests for the VRP involve 14 benchmark 
instances, and our implementations were subjected to varying free-
running levels of restrictiveness imposed by other tabu elements. 
Performance comparisons also include other competitive tabu search 
algorithms. 
 
1. INTRODUÇÃO 
 
A natureza flexível da metodologia tabu (Glover, 1989,1990; Glover e 
Laguna,1997) permite e estimula a elaboração de técnicas que 
promovam melhorias adicionais ao desempenho da busca. Algumas 
dessas técnicas caracterizam-se pela variação sistemática do período 
e da configuração da lista tabu, sendo, portanto, uma extensão do 
conceito de listas tabu dinâmicas. A alteração das listas é um 
mecanismo que provoca a integração das estratégias de intensificação 
e diversificação. A orientação básica é a de se utilizar tamanhos de 
listas menores ao se atingir regiões atraentes, próximas a ótimos 
locais. Reduzindo-se os níveis de restritividade impostos pelas listas, 
permite-se a exploração detalhada da região. Tamanhos de listas 
maiores são empregados quando se torna necessário a fuga da 
vizinhança desses ótimos. 
 
Hübsher e Glover (1992) propõem uma forma elaborada de variação 
sistemática do período tabu dinâmico e da configuração da lista ao 
30 TRANSPORTES 
introduzir o conceito de moving gaps em problemas de programação 
de tarefas em multiprocessadores. A lista tabu consiste de uma parte 
dinâmica e de uma parte estática: a configuração da parte dinâmica é 
alterada de tal forma que uma fase de intensificação é seguida de 
uma fase de diversificação e vice-versa. Seis configurações de lista 
foram utilizadas e a transição entre uma configuração e a próxima é 
ativada se nenhuma melhoria for encontrada durante um número 
especificado de iterações. 
 
Chakrapani e Skorin-Kapov (1993) aplicam um conceito similar ao 
problema de designação quadrática com a variação dinâmica do 
tamanho da lista tabu através de oito configurações fixas. Quando 
uma fase sem melhorias é verificada, o número de atributos tabu-
ativos é sistematicamente diminuído, definindo novas configurações 
de lista. A lista diminui até tornar-se inoperante. O objetivo desta 
fase é o de permitir um exame mais detalhado da região factível. Um 
aumento sistemático do tamanho da lista é então iniciado como 
forma de quebrar a ciclagem e produzir maior diversificação. No fim 
desta fase, a configuração inicial da lista é restabelecida, resultando 
em um processo no qual a lista tabu cicla através de diferentes 
configurações. Note-se que em ambas implementações, a 
configuração corrente da lista é função da configuração anterior. 
 
A abordagem tabu adaptativa HTA, a ser aqui utilizada, pode 
também ser considerada uma estratégia que integra fases de 
diversificação e intensificação. Assim como as abordagens anteriores, 
baseia-se na variação ou perturbação de valores de elementos tabu 
selecionados com o propósito de criar níveis de restritividade que 
promovam intensificação em regiões promissoras e diversificação se 
possibilidades de melhoria parecem remotas. Diferentemente, 
porém, a perturbação dos elementos tabu não é ativada por fases sem 
melhoria, mas depende da análise de padrões de trajetória de busca 
recentemente traçada. A análise é realizada ao longo de todo o 
processo de busca, após um número relativamente pequeno de 
iterações. Isso significa que as condições operacionais estão sujeitas a 
constantes perturbações. A análise determina não apenas a natureza 
da perturbação (aumento ou diminuição dos níveis de restritividade) 
mas também o grau e a duração (número de iterações) da 
ARTIGO – UMA ABORDAGEM ADAPTATIVA… 31 
perturbação. Distintamente das abordagens anteriores, o valor da 
perturbação corrente não é explicitamente dependente do valor de 
uma perturbação anterior. 
 
Estas idéias foram inicialmente aplicadas ao Problema do Caixeiro 
Viajante (PCV) (Pureza e França, 1996) e, mais recentemente, ao 
Problema de Agrupamento Capacitado (França et al., 1999). Neste artigo 
são descritos alguns experimentos com o Problema de Roteamento de 
Veículos (PRV). Foi desenvolvida uma implementação tabu 
adaptativa que sistematicamente perturba a regra de ativação tabu. 
São reportados resultados computacionais envolvendo 14 problemas 
clássicos do PRV com tamanhos entre 51 e 199 nós. O principal 
objetivo destes experimentos é o de verificar se a incorporação do 
procedimento de perturbação da regra de ativação tabu é capaz de 
melhorar o desempenho da meta-heurística em relação ao mesmo 
algoritmo desprovido de mecanismos adaptativos. Também foi 
analisado o impacto emtermos de tempos de processamento, e a 
efetividade do método em lidar com condições operacionais menos 
apropriadas e mantidas fora do escopo do controle. Os resultados 
indicam que para o conjunto de problemas tratados, a 
implementação proposta é capaz de produzir com menor esforço 
computacional, soluções de maior qualidade que a versão não 
adaptativa. 
 
2. O PRV E A IMPLEMENTAÇÃO TABU ORIGINAL 
 
O Problema de Roteamento de Veículos (PRV) com limitações de 
capacidade e tempo máximo de rota consiste na definição de rotas de 
custo mínimo que se originem e terminem em uma garagem ou 
depósito. A frota serve a um conjunto de clientes ou nós, cada um 
caracterizado por sua localização no espaço bidimensional, demanda 
e tempo de serviço. A demanda de cada cliente precisa ser satisfeita 
por exatamente um veículo. A demanda total dos clientes alocados a 
um dado veículo não pode exceder a capacidade do mesmo. O 
tempo total de rota não pode exceder um dado limitante pré-
especificado e inclui tempos de viagem entre clientes e tempos de 
serviço em cada cliente. 
 
32 TRANSPORTES 
A abordagem adaptativa HTA foi aplicada a uma implementação 
tabu baseada no algoritmo de Pureza e França (1991), originalmente 
elaborado para problemas de roteamento de veículos com janelas de 
tempo. Por ser uma das primeiras implementações de busca tabu 
para o PRV, apenas os elementos mais simples da metodologia tabu 
foram incorporados. 
 
O algoritmo utiliza a heurística de construção de rotas proposta por 
Solomon et al. (1987) para geração da solução inicial. Após a semente 
da primeira rota ter sido escolhida, a melhor posição factível para 
cada cliente não roteado é calculada de acordo com um critério que 
favorece a economia em distância, tempo ou uma combinação de 
ambos. Outro critério, baseado no primeiro, seleciona o cliente a ser 
inserido. Sempre que a inserção de um novo cliente provocar 
infactibilidade da rota atual, uma nova rota passa a ser construída 
com a escolha de uma nova semente. O procedimento é repetido até 
que todos os clientes tenham sido roteados. 
 
A heurística de melhoria de rotas é baseada no método de Dror e 
Levy (1986), elaborado para roteamento de estoque. Esta heurística 
utiliza trocas de nós ao invés de trocas de arestas, generalizando as 
técnicas de melhoria r-opt limitadas a sistemas de uma única rota. A 
heurística realiza operações de inserção de um único nó da rota 
corrente a uma rota alternativa e de troca simples entre dois nós que 
pertençam a rotas distintas. Estas operações são aqui chamadas de 
movimentos inter-rotas. A seleção do movimento é guiada pelo 
critério da máxima redução da distância total. 
 
A partir da solução inicial são aplicados movimentos inter-rotas até 
que as possibilidades de melhoria sejam exauridas. Antes de iniciar 
movimentos de não melhoria, a heurística de troca de arestas 2-opt 
(Croes, 1958) é aplicada em cada rota. Estas operações são chamadas 
de movimentos intra-rotas. Apenas trocas 2-opt de melhoria são 
realizadas. A aplicação destes movimentos pode ser vista como um 
refinamento do roteamento após a aplicação de operações de 
inserção e troca de nós, mostrando-se bastante efetiva. 
 
ARTIGO – UMA ABORDAGEM ADAPTATIVA… 33 
As arestas adicionadas e eliminadas são os atributos dos movimentos 
intra-rota e inter-rotas, uma vez que estes últimos podem ser 
reduzidos a procedimentos de adição e eliminação de arestas. 
Quando o algoritmo foi elaborado, períodos tabu dinâmicos ainda 
não tinham sido considerados. Foram utilizadas 2 listas tabu fixas. 
As arestas que pertencem às listas são consideradas tabu-ativas por 
um número de iterações correspondente ao tamanho da lista tabu. O 
status dos movimentos é definido por um parâmetro T que 
determina o número máximo tolerável de arestas tabu-ativas. Além deste 
valor, o movimento é considerado tabu. 
 
Os experimentos consideraram 3 tamanhos de lista tabu (20, 30 e 40). 
O parâmetro T assumiu os valores 2, 3 e 4, considerados os mais 
efetivos em testes preliminares. Como critério de parada, usou-se 
500 ou 600 movimentos de trocas de nós a partir do primeiro ótimo 
local. Finalmente, foi incluído um critério de aspiração que permite 
movimentos tabu que resultem em soluções melhores do que a 
melhor até o momento. 
 
Antes de aplicar a abordagem adaptativa, o algoritmo original foi 
modificado de forma a incorporar melhorias metodológicas mínimas. 
Como critério de parada, utilizou-se número de iterações sem 
melhoria. Foram adotados períodos tabu dinâmicos; arestas tabu-
ativas mantêm este status durante um número t de iterações, número 
este gerado aleatoriamente em um intervalo pré-especificado [tmin, 
tmax]. 
 
3. A ABORDAGEM ADAPTATIVA HTA 
 
A regra de ativação tabu e o período tabu definem o nível de 
restritividade imposto à busca. Níveis de restritividade têm um 
grande impacto no desempenho da meta-heurística, o qual é refletido 
no padrão geral das trajetórias de busca (a curva função objetivo vs. 
iteração). A abordagem foi elaborada para identificar e reagir a três 
padrões de trajetória que parecem especialmente relevantes para o 
desempenho da meta-heurística – estagnação da busca, trajetórias 
ascendentes e trajetórias descendentes. 
 
34 TRANSPORTES 
A estagnação da busca é geralmente o resultado de restrições tabu 
fracas ou de curta duração. As trajetórias são caracterizadas pela 
geração de custos de solução em uma faixa relativamente estreita. O 
processo de busca experimenta grande dificuldade em encontrar 
melhores soluções e parece preso a uma região muito limitada. Como 
a estagnação é uma condição adversa para a efetividade de qualquer 
processo de busca, a abordagem adaptativa responde a este padrão 
com o aumento dos níveis de restritividade. Os atributos de 
movimento recentemente utilizados mantêm o status tabu mais 
rigorosamente que previamente especificado, resultando na seleção 
de movimentos menos atraentes e conseqüente diversificação da 
busca. 
 
A trajetória ascendente é caracterizada pelo aumento dos custos de 
solução. Deve-se, em geral, a restrições severas ou de longa duração. 
No contexto adaptativo, é geralmente o resultado da aplicação de 
diversificação após uma fase de estagnação. A abordagem responde 
a trajetórias ascendentes com a relaxação das restrições tabu, a qual 
pode assumir diferentes graus dependendo da severidade dos níveis 
de restritividade alcançados. O objetivo desta fase é o de permitir 
que novas regiões promissoras do espaço de busca sejam atingidas. 
É também a fase mais crítica já que as restrições devem ser 
suficientemente vigorosas para impedir o retorno ao vale de onde a 
busca emergiu e, ao mesmo tempo, permitir o aproveitamento das 
possibilidades de melhoria que a nova região venha a apresentar. 
 
O terceiro e último padrão considerado corresponde a seqüências de 
soluções que resultam em uma trajetória descendente, caracterizadas, 
portanto, pela diminuição dos custos de solução. A abordagem 
adaptativa estabelece níveis de restrititividade moderados de forma a 
permitir uma exploração mais detalhada da região em busca de 
melhorias adicionais. Trajetórias descendentes podem resultar da 
relaxação de restrições tabu. 
 
A identificação dos padrões de trajetória é feita através da análise 
comparativa entre as médias dos custos de solução (função objetivo) 
observados nos últimos dois estágios de busca. As médias destes 
dois conjuntos de custos são chamadas de média anterior e média 
ARTIGO – UMA ABORDAGEM ADAPTATIVA… 35 
corrente. Por exemplo, se os valores das médias são aproximadamente 
iguais, conclui-se que está ocorrendo estagnação. Se a média 
corrente é maior que a anterior, a busca está descrevendo uma 
trajetória ascendente. Se a média corrente é menor que a anterior, a 
buscaestá descrevendo uma trajetória descendente. 
 
O uso da função objetivo para detecção de padrões implicitamente 
admite que a estrutura do espaço de soluções exibe uma alta 
correlação entre os valores da função objetivo entre pares de soluções 
x e y e a distância dp[x,y], por sua vez definida como o número 
mínimo de operações do tipo p para se obter y a partir de x 
(Charleston, 1995). Como cada análise individual se restringe a 
segmentos relativamente pequenos da trajetória de busca, uma alta 
correlação para dp[x,y] ≤ k (k relativamente pequeno) é suficiente. 
Apesar de nenhuma prova formal desta hipótese ser apresentada, 
observa-se que altos níveis de restritividade (custos de solução 
crescentes) tendem a produzir soluções consecutivas distantes uma 
das outras já que a escolha de arestas para adição e eliminação está 
restrita a conjuntos envolvidos em movimentos realizados a pelo 
menos um número it (grande) de iterações anteriores. O mesmo 
raciocínio pode ser aplicado a níveis baixos de restritividade (custos 
de solução similares) - dada a natureza agressiva da Busca Tabu, 
soluções consecutivas compartilham várias arestas. Neste trabalho 
foram utilizadas médias simples apesar de medidas mais elaboradas 
como médias rolantes pudessem também ter sido utilizadas (veja 
Seção 6). 
 
Como o uso destas estatísticas simples para inferir padrões de 
trajetória apresenta limitações, a escolha apropriada do comprimento 
do estágio de busca é crucial para evitar interpretações equivocadas. 
O comprimento do estágio de busca é chamado de horizonte de 
avaliação e define o período durante o qual a perturbação deve ser 
aplicada e o número de iterações e os custos de solução associados a 
serem utilizados na próxima avaliação. Horizontes de avaliação são 
obtidos gerando-se aleatoriamente um número inteiro e positivo 
(hoz) em uma faixa [hmin,hmax]. A Figura 1 ilustra o processo de 
identificação de trajetórias. Considere que c(xi) é o custo da solução 
calculado na iteração iti. 
36 TRANSPORTES 
média anterior=(c(xk) + ... + c(xm))/(itm - itk) 
média corrente=(c(xm+1) + ... + c(xp))/(itp - itm+1) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 1: Identificação de trajetórias 
 
Neste trabalho foram exploradas alterações dinâmicas no parâmetro 
T. Tais perturbações são realizadas em intervalos pré-determinados, 
de forma que a iteração da próxima avaliação é conhecida 
previamente. Em geral, a iteração da próxima avaliação é calculada 
adicionando-se a parte inteira de m*hoz à iteração corrente (m≥0). O 
parâmetro m é um fator de ajuste do período de aplicação a cada tipo 
de perturbação. Perturbações que envolvem a aplicação de altos 
níveis de restritividade (T=0) requerem pequenos valores de m, 
geralmente menores que 0, de forma a limitar o aumento nos custos. 
Trajetórias descendentes, por outro lado, sugerem valores de m 
maiores que 1 como forma de explorar ao máximo as possibilidades 
de melhoria da região. Utilizou-se também um critério de aspiração 
que mantém a busca operando em um valor de T padrão 
(independente das características das trajetórias), caso ocorra a 
atualização da melhor solução no último estágio da busca. Neste 
caso, m é maior que 1. 
 
O algoritmo realiza 3 tipos diferentes de movimentos (inserção de 
nós, troca de nós e troca de arestas intra-rota 2-opt) e, para cada tipo, 
hoz 
hoz 
c(xp) 
c(xm) 
c(xk) 
Itk Itm Itp 
ARTIGO – UMA ABORDAGEM ADAPTATIVA… 37 
T pode assumir diferentes valores dependendo do número de arestas 
afetadas. Para inserção de nós, estes valores estão entre 0 e 6; para 
troca de nós, entre 0 e 8, e para troca de arestas, entre 0 e 4. Por esta 
razão, T foi substituído por 3 parâmetros que definem o número 
máximo tolerável de arestas tabu-ativas em cada tipo de movimento: 
TI (movimentos de inserção), TT (movimentos de troca) e TO 
(movimentos intra-rota). Quando alguma perturbação é realizada, os 
valores dos 2 primeiros parâmetros são modificados 
simultaneamente. TO é mantido fixo e igual a 4 dado que apenas 
movimentos intra-rota de melhoria são permitidos (a ocorrência de 
ciclagem não é possível). Como na implementação original, o status 
do movimento candidato depende do valor de T associado. Quanto 
ao critério de aspiração, experimentos preliminares indicaram que 
TT=6 e TI=5 resultam em maiores ganhos na qualidade das soluções 
quando aplicados em regiões promissoras (por exemplo, quando a 
melhor solução é atualizada). 
 
4. PASSOS DO ALGORITMO 
 
1. (Inicialização) Seja it a iteração corrente. Faça it=0. A partir 
da solução inicial, faça TT=TI=3 e TO=4 e proceda com a 
busca até que o primeiro ótimo local seja atingido, 
armazenando os custos das soluções geradas em uma lista C. 
 
2. Faça média_anterior igual à média dos custos armazenados e 
reinicialize C. Gere aleatoriamente um valor de hoz na faixa 
adotada e continue a busca nas mesmas condições por hoz 
iterações. A próxima avaliação prox_aval ocorrerá na iteração 
it + hoz. Neste meio tempo, armazene os custos em C. 
Quando it=prox_aval, faça média_corrente igual à média dos 
custos em C e reinicialize C. Gere um novo hoz. 
 
3. Se o critério de parada tiver sido satisfeito, páre e retorne a 
melhor solução. Caso contrário: 
 
3.1 Se houve atualização da melhor solução, faça TT=6 e TI=5 
por 2*hoz iterações (prox_aval=it + 2*hoz). Armazene os 
custos em C. 
 
38 TRANSPORTES 
3.2 Caso contrário, calcule diff=(média_anterior - média_corrente)/ 
média_corrente. 
 
3.2.1 Se |diff| ≤ 0,0025 então estagnação é o padrão corrente. 
Aplique restritividade máxima (TT=TI=0) e mantenha a 
busca por hoz/2 iterações (prox_aval=it + hoz/2). 
Armazene os custos em C. 
 
3.2.2 Caso contrário, se diff < 0 então trajetória ascendente é o 
padrão corrente. Neste caso, altere os níveis de 
restritividade segundo uma função do valor de diff, de 
acordo com a Tabela 1. Mantenha a busca por 2*hoz 
iterações (prox_aval=it + 2*hoz). Armazene os custos em 
C. 
 
3.2.3 Caso contrário, se diff >0 então trajetória descendente é o 
padrão corrente. Se TT=7 e TI=6, faça TT=6 e TI=5 de 
forma a aumentar a restritividade por 2*hoz iterações 
(prox_aval=it+ 2*hoz). Caso contrário, mantenha a busca 
por hoz iterações (prox_aval=it+ hoz). Armazene os custos 
em C. 
 
3.3 Quando it=prox_aval, faça média_anterior=média_corrente e 
média_corrente igual à média dos custos armazenados em C. 
Reinicialize C. Gere novo hoz e retorne ao passo 3. 
 
A Tabela 1 apresenta os valores de TT e TI para faixas específicas de 
valores de diff. Quanto menores os valores de diff, maiores os níveis 
de restritividade. De acordo com os conceitos adaptativos, tais níveis 
precisam ser diminuídos (impondo-se altos valores de TT e TI). 
Experimentos preliminares indicaram que as chances de se retornar 
ao vale anterior são muito pequenas mesmo quando se adota níveis 
de restritividade muito pequenos (TT=7 e TI=6). Isso provavelmente 
se deve aos diferentes tipos de movimento que competem pela 
seleção. É possível que esta estratégia funcione como um elemento 
diversificante no sentido de que ao revisitar a mesma solução exista 
uma probabilidade razoável de seleção de um caminho de busca 
ARTIGO – UMA ABORDAGEM ADAPTATIVA… 39 
diferente. O procedimento 2-opt aplicado após cada ótimo local 
complementa este efeito. 
 
Tabela 1: Valores de TT e TI para trajetórias ascendentes 
Faixa de diff TT TI 
(-∞, -0,03) 7 6 
(-0,03, -0,025) 6 5 
(-0,025, -0,02) 5 4 
(-0,02, -0,015) 4 3 
(-0,015, -0,005) 3 3 
(-0,005, -0,0025) 2 2 
 
Conforme os valores de diff aumentam, os níveis de restritividade são 
aumentados de forma a impedir o retorno ao vale de onde a busca 
emergiu e, simultaneamente, explorar as possibilidades da região 
corrente. A partir de umcerto ponto, valores maiores de diff indicam 
que a busca está muito próxima ou ainda explorando a mesma 
região. Impondo-se maior restritividade (valores pequenos de TT e 
TI), força-se a busca a novas regiões. Deve-se enfatizar que se 
trabalha com valores de TT e TI hipotéticos que não devem ser 
excedidos de forma a impedir um aumento muito grande nos custos 
de solução, mas que precisam ser suficientemente grandes para 
resultar em diversificação. Os valores (válidos) 1 e 8 de TT não foram 
considerados em trajetórias ascendentes porque os níveis de 
restritividades associados foram satisfatoriamente atingidos por 
valores adjacentes. 
 
Nos experimentos com o PCV foram realizados vários testes para 
definir valores de parâmetros e as condições que caracterizam 
padrões de trajetória. A maioria destes valores foi utilizada neste 
trabalho. A condição para estagnação (passo 3.2.1) foi definida da 
seguinte forma. Considere ε-platôs onde K ≤ c(x) ≤ K + ε para todo x 
no conjunto e e um número pequeno e positivo. A condição de 
estagnação é de fato utilizada para identificar "passeios" (walks) em 
ε-platôs que também contêm bases de atração. Isso significa que não 
se espera encontrar nenhuma solução com custo menor que K no 
40 TRANSPORTES 
conjunto. Para um número de problemas teste, foram adotados 
valores de T de média restritividade e testados períodos tabu em 
ordem decrescente. Para cada período, valores de diff foram 
computados em estágios de busca imediatamente subseqüentes à 
obtenção do primeiro ótimo local. Como condição de estagnação, foi 
escolhido maior valor de diff para o qual nenhuma melhoria foi 
obtida dentro de um número razoavelmente grande de iterações. 
 
5. EXPERIMENTOS COMPUTACIONAIS 
 
5.1. Dados e Experimentos Computacionais 
 
Os experimentos envolveram 14 problemas clássicos do PRV 
(Christofides et. al, 1979), com tamanhos entre 51 e 199 nós. Estes 
problemas têm características específicas com respeito à distribuição 
dos nós (agrupada ou uniforme), capacidade dos veículos e tempo 
máximo de rota. Alguns deles incluem tempos de serviço. Foi 
utilizada a métrica euclidiana para calcular as distâncias entre cada 
par de nós. 
 
Os experimentos (executados em estações Sun Ultra1) consistiram de 
execuções a partir de 4 soluções de partida, 7 faixas de períodos tabu 
e 4 horizontes de avaliação. As soluções de partida foram definidas 
por alguns dos valores sugeridos para os parâmetros da heurística de 
Solomon. Como critério de parada, adotou-se 4000 iterações sem 
melhoria. Para alguns problemas foram testadas variações do 
algoritmo que basicamente consistem em alterações do valor do 
parâmetro m e que resultaram em um número diferente de iterações 
nos passos 3.1, 3.2.2 ou 3.2.3. 
 
Todas as faixas de período tabu têm comprimento 10. Para 
problemas até 100 nós, utilizou-se [tmin,tmax] =[0,10] como a faixa de 
período tabu menos restritiva e [tmin, tmax] =[20,30] como a mais 
restritiva. Para problemas maiores tais valores foram 
respectivamente [10,20] e [30,40]. Observou-se que pequenos 
períodos tabu são eficientes na geração de boas soluções, mesmo em 
problemas de maior porte. Faixas de período tabu além de [30,40] 
provocaram degradação do desempenho do algoritmo, 
ARTIGO – UMA ABORDAGEM ADAPTATIVA… 41 
contrariamente ao que foi obtido nos experimentos com o PCV. É 
possível que o desempenho desfavorável decorrente do uso de 
períodos tabu maiores se deva ao menor número de caminhos de 
busca factíveis que resultam das restrições do PRV. 
 
Os horizontes de avaliação foram determinados a partir dos 
resultados do algoritmo adaptativo para o PCV. As mesmas faixas 
sugeridas para problemas de tamanho n foram utilizadas no PRV. 
Considerando que são problemas distintos, foram incluídas faixas de 
horizonte adjacentes. 
 
Os resultados da implementação adaptativa (PF+HTA) foram 
comparados aos resultados obtidos por outros 5 algoritmos. O 
algoritmo original (PF) foi modificado de forma a incluir períodos 
tabu dinâmicos. Foi utilizado o mesmo critério de parada e as 
execuções foram realizadas a partir das mesmas soluções de partida e 
períodos tabu usados na versão adaptativa. Os experimentos foram 
repetidos para valores de T iguais a 2, 3, 4 e 5. O principal objetivo 
destes testes é o de observar se a abordagem proposta é capaz de 
adaptar a busca a níveis de restritividade impostos pelas faixas de 
período tabu. 
 
Quatro outros algoritmos foram selecionados devido ao seu 
desempenho em termos de qualidade de solução: o algoritmo de 
Taillard(1993), o algoritmo de Osman (1993), TABUROUTE 
(Gendreau et. al,1994) e DETABA (Barbarosoglu et. al, 1999). Todos 
são implementações tabu e resultaram nos melhores resultados para 
este conjunto de problemas. 
 
5.2. Comparação da Qualidade da Solução - 5 Algoritmos 
 
A Tabela 2 apresenta os resultados computacionais para os 14 
problemas considerados. Tomando como referência as melhores 
soluções até então reportadas, resultados equivalentes foram obtidos 
por PF+HTA em 7 problemas. Para os problemas p8 e p9 (100 e 150 
nós), PF+HTA encontrou uma solução melhor que a melhor solução 
dos 4 algoritmos. Em média, PF+HTA apresentou um desvio 
percentual dos custos das melhores soluções de 0,25%. Se 
42 TRANSPORTES 
considerarmos apenas os resultados apresentados pela versão padrão 
de PF + HTA, obteve-se um desvio percentual médio de 0,35%. 
 
Tabela 2: Resultados 
# Algoritmos 
 TAILLARD OSMAN TABUROUTE DETABA PF PF+HTA 
p1 524,61† 524,61† 0,6 524,61† 1,4 524,61† - 524,63 0,4 524,61† 0,15 
p2 835,26† 844 0,4 835,32 - 836,71 - 837.94 1,6 835,26† 0,8 
p3 826,14† 835 6,7 826,14† - 828,72 - 827,88 57,7 826,64 0,7 
p4 1028,42† 1044,35 22,9 1031,07 - 1043,89 - 1042,29 64,3 1032,53 51,5 
p5 1298,79† 1334,35 28,4 1311,35 - 1306,16 - 1340,98 26,1 1327,98 26,6 
p6 555,43† 555,43† 1,1 555,43† 7,8 - - 556,68 2,6 555,43† 1,5 
p7 909,68† 911 27,6 909,68† - - - 920,30 0,25 909,68† 5,7 
p8 865,94 866,75 13,7 865,94 5,9 - - 865,51 7,4 865,51† 1,9 
p9 1162,89 1184 14,9 1162,89 - - - 1168,65 58,1 1161,93† 82,7 
p10 1397,94† 1422 28,8 1404,75 - - - 1419,07 192 1407,63 145,2 
p11 1042,11† 1042,11† 13,4 1042,11† - 1051,18 - 1044,30 17,4 1042,11† 1,8 
p12 819,56† 819,56† 2,1 819,56† 1,7 819,56† - 819,56 1,2 819,56† 0,8 
p13 1541,15† 1547 10,2 1545,93 - - - 1547,01 61,3 1542,97 47 
p14 866,37† 866,37† 6,9 866,37† 29,7 - - 866,37† 0,25 866,37† 0,2 
AV 0,01 0,76 0,15 0,49* 0,66 0,25 
† : melhor solução 
* : para 7 problemas 
1a coluna : custo da melhor solução 
2a coluna : tempo de CPU p/ melhor 
solução (min.) 
AV : desvio percentual médio das 
melhores soluções 
encontradas pelos 5 algoritmos 
Computadores: 
TAILLARD: Silicon Graphics 4D/35 
OSMAN: VAX 8600 
TABUROUTE: Silicon Graphics, 36MHz, 
5.7 Mflops 
DETABA: Pentium 133 MHz - 32MB Ram 
PF e PF + HTA: Sun Ultra 1 workstation. 
 
É interessante comparar o desempenho dos algoritmos OSMAN e PF 
já que ambos usam recursos básicos similares: 3 tipos de movimentos 
(inserção de nós, troca de nós e troca de arestas) e períodos tabu 
dinâmicos. Dado que PF+HTA é superior a PF, comparações entre 
OSMAN e PF+HTA poderiam tornar mais claro o papel da 
abordagem adaptativa. Por outro lado, os algoritmos TAILLARD 
and TABUROUTE usam estratégias mais sofisticadas tais como 
paralelização e busca em regiões infactíveis. 
 
5.3. Sensibilidade aos Períodos Tabu 
 
A fim de avaliar a sensibilidade de PF+HTA às faixas de período 
tabu, foram calculados os custos mínimos, médios e máximos nas 
execuções obtidas com o horizonte de avaliação e solução de partida 
ARTIGO – UMA ABORDAGEM ADAPTATIVA… 43 
que resultaram na melhor solução (versão padrão do algoritmo). Os 
mesmos cálculos foram feitos para PF, desta vez utilizando as 
execuções com o valor de T e solução de partida quegeraram a 
melhor solução. A Figura 2 ilustra estes resultados, onde as marcas 
em cada linha indicam a tripla de custos. Em geral, os custos obtidos 
por PF+HTA são inferiores aos de PF o que sugere sua maior 
adaptabilidade aos períodos tabu considerados. 
 
Figura 2:. Sensibilidade ao Período Tabu 
 
5.4. Tempos de Processamento - PF e PF+HTA 
 
Como PF+HTA claramente supera PF com relação à qualidade da 
solução, deve-se observar como o tempo de processamento é afetado 
pela inclusão dos mecanismos adaptativos. A análise do esforço 
computacional requerido pelos dois algoritmos considerou duas 
medidas: o tempo para atingir a melhor solução e o tempo total de 
execução. Os cálculos realizados abrangem apenas a execução que 
resultou na melhor solução encontrada pelos algoritmos. 
 
Em problemas até 120 nós, o esforço computacional requerido por 
PF+HTA tanto para obtenção da melhor solução como para 
finalização da busca é substancialmente menor do que o verificado 
em PF. A introdução dos mecanismos adaptativos provocou uma 
redução destes tempos de 60 e 40% respectivamente. Para 
problemas de 150 e 199 nós, as reduções diminuem (10% para as 
44 TRANSPORTES 
duas medidas), mantendo-se, porém, positivas. Tempos mais curtos 
de obtenção da melhor solução levam à conclusão de que PF+HTA é 
mais efetivo nas explorações do espaço de busca. Tempos mais 
curtos para finalização do processo sugerem, por sua vez, que ao 
longo das 4000 iterações sem melhoria subseqüentes (critério de 
parada), fases onde se aplica maior restritividade (mais demoradas) 
parecem ser compensadas por fases menos restritivas (mais rápidas). 
Note que o algoritmo não adaptativo PF trabalha com um único nível 
de restritividade (T) ao longo de todo o processo, e que as melhores 
soluções foram geralmente obtidas adotando-se T=3 ou T=4 . A 
Tabela 3 apresenta as razões entre os tempos médios de 
processamento exibidos pelos dois algoritmos. 
 
Tabela 3:. Tempo médio (PF + HTA) / Tempo médio (PF) 
 Melhor solução Total 
n obtida 
n ≤ 120 0,40 0,57 
> 120 0,90 0,90 
todos 0,75 0,77 
 
6. CONCLUSÕES E DISCUSSÃO 
 
Neste artigo apresentamos alguns experimentos resultantes da 
aplicação da abordagem tabu adaptativa HTA a 14 problemas 
clássicos do Problema de Roteamento de Veículos. A abordagem 
HTA é caracterizada pela perturbação sistemática da regra de 
ativação tabu e baseada na análise de trajetórias de busca 
recentemente descritas. A implementação teve como base o 
algoritmo de Pureza e França (1991) e absorveu a estrutura das 
rotinas elaboradas em experimentos anteriores com o Problema do 
Caixeiro Viajante. 
 
O procedimento adaptativo é bastante simples, não requerendo mais 
do que uma estrutura de lista relativamente pequena para armazenar 
os custos de solução e duas subrotinas adicionais. Não obstante, os 
resultados dos experimentos indicam que o algoritmo adaptativo foi 
capaz de produzir ganhos tanto em qualidade de solução como em 
ARTIGO – UMA ABORDAGEM ADAPTATIVA… 45 
tempos de processamento em relação à versão não adaptativa. O 
papel da estratégia HTA é também evidente se considerada a 
simplicidade de recursos do algoritmo frente às heurísticas que o 
superam. 
 
Deve ser observado que o propósito deste trabalho é o de apresentar 
os benefícios relativos de utilização desta abordagem em uma 
implementação relativamente modesta ao invés de propor um 
algoritmo elaborado. Por esta razão, é importante aplicar estes 
conceitos a implementações mais sofisticadas, como as que 
empregam vizinhanças de busca mais poderosas e estratégias de 
exame de partes de vizinhanças. Acredita-se que uma maior 
efetividade seja alcançada. Como esta abordagem não se destina a 
um problema específico tal como o PRV, sua eficiência deve ser 
testada em um número maior de problemas. Uma idéia interessante 
é o de aplicá-la a problemas ainda mais restritos, onde seja difícil a 
obtenção de caminhos factíveis que resultem em soluções de alta 
qualidade. 
 
Os próximos passos desta pesquisa envolvem o desenvolvimento de 
uma implementação adaptativa (HTSA) onde o aumento da 
restritividade é feito de forma gradual, alternada com fases de 
restritividade moderada. Esta estratégia parece ser mais adequada 
para lidar com a natureza restritiva do PRV e usa alguns conceitos 
similares a moving gaps (Hübscher e Glover, 1992). Em HTSA, a 
estagnação é uma condição esperada, detectada através de médias 
móveis enquanto as outras duas fases (estabilização e diversificação) 
ainda são aplicadas por um número pré-determinado de iterações. 
HTSA pode ser considerado um passo para o desenvolvimento de 
uma abordagem adaptativa onde parâmetros exógenos tais como 
horizontes de avaliação são substituídos por uma avaliação dinâmica 
de padrões de trajetória. Neste caso, a informação provida define a 
duração da aplicação da perturbação de uma forma não arbitrária, 
teoricamente resultando em uma capacidade maior de adaptação a 
um processo de busca particular. 
 
AGRADECIMENTOS 
 
Esta pesquisa teve apoio da FAPESP e do CNPq. 
46 TRANSPORTES 
REFERÊNCIAS BIBLIOGRÁFICAS 
 
Barbarosoglu G. e D. Ozgur (1999) A Tabu Search Algorithm for the 
Vehicle Routing Problem. Computers and Operations Research 26, 
p. 255-270. 
Chakrapani, J. e J. Skorin-Kapov (1993) Massively parallel tabu 
search for the quadratic assignment problem. Annals of 
Operations Research 41, p. 327-341. 
Charleston, M. A. (1995) Toward a Characterization of Landscapes of 
Combinatorial Optimization Problems, with Special Attention 
to the Phylogeny Problem. Journal of Computational Biology v. 2, 
n. 3, p. 439-450. 
Christofides, N.; A. Mingozzi e P. Toth (1979) The Vehicle Routing 
Problem. In: Christofides N., Mingozzi A., Toth P. and Sandi 
C. (eds.) Combinatorial Optimization, Wiley, Chichester. 
Dror M. e L. Levy (1986) A Vehicle Routing Improvement Algorithm 
Comparison of a Greedy and a Matching Implementation for 
Inventory Routing. Computers and Operations Research v. 13, n. 
1, p. 33-45. 
França, P. M.; N. M. Sosa e V. Pureza (1999) An Adaptive Tabu 
Search Algorithm for the Capacitated Clustering Problem. 
International Transactions in Operational Research 6, p. 665-678. 
Gendreau M, A. Hertz e G. Laporte (1994) A Tabu Search Heuristic 
for the Vehicle Routing Problem. Management Science v. 40, n. 
10, p. 1276-1290. 
Croes, A. (1958) A Method for Solving Traveling-Salesman Problems. 
Operations Research v. 5, p. 791-812. 
Glover, F. (1989) Tabu Search, Part I, Orsa Journal on Computing v. 1, 
p. 190-206. 
Glover, F. (1989) Tabu Search, Part II, Orsa Journal on Computing v. 2, 
p. 4-32. 
Glover, F. e M. Laguna (1997) Tabu Search. Kluwer Academic 
Publishers, Massachussetts. 
Hübscher, R. e F. Glover (1992) Applying Tabu Search with 
Influential Diversification to Multiprocessor Scheduling. 
Personal Communication. 
ARTIGO – UMA ABORDAGEM ADAPTATIVA… 47 
Osman, I. H (1993) Metastrategy Simulated Annealing and Tabu 
Search Algorithms for the Vehicle Routing Problem. Annals of 
Operations Research 41. 
Pureza, V. e P. M. França (1996) An Adaptive Tabu Metaheuristic 
Approach based on the Topology of the Solution Space. II 
ALIO/EURO Workshop on Practical Combinatorial Optimization, 
Valparaiso, Chile, p. 233-249. 
Pureza, V. e P. M. França (1991) Vehicle Routing Problems via Tabu 
Search Metaheuristic. Centre de Recherche sur les Transports, 
Université de Montréal, cahier CRT 747. 
Solomon, M. (1987) Algorithms for the Vehicle Routing and 
Scheduling Problems with Time Window Constraints. 
Operations Research v. 35, n. 2, p. 254-265. 
Taillard, E. (1993) Parallel Iterative Search Methods for Vehicle 
Routing Problems. Networks v.23, n. 8. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Endereço dos autores: 
Vitória Pureza