O problema de roteamento no transporte escolar
1. INTRODUÇÃO
O problema de roteamento clássico de veículos necessita de um conjunto de rotas
de coleta e/ou entrega a partir de um depósito central para vários pontos de
demanda, cada um tendo necessidades de serviços, com o objetivo de minimizar a
distância total a ser percorrida pela frota inteira. Os veículos têm restrições
de quantidade, capacidade e, possivelmente, de tempo. Todos os veículos iniciam
e terminam sua rota em um depósito central. A formulação deste problema como um
Problema de Programação Inteira Binária (PPIB) é devida a Golden et al., 1977
[Bodin et al., 1983]. Como o problema de roteamento de veículos é NP-hard,
resolvê-lo como um PPIB é inviável e, por este motivo, a solução é obtida, em
geral, através de procedimentos heurísticos.
O tratamento dado aos problemas de roteamento de veículos é bastante
diversificado, variando não apenas nos algoritmos utilizados, mas também no
tipo de tratamento dado às particularidades próprias de cada problema. Bodin et
al., 1983, fazem uma descrição do problema do roteamento no transporte escolar
para escolas americanas, onde um mesmo ônibus pode atender várias escolas,
sendo que cada escola tem um conjunto de pontos de demanda, com localizações
próximas às residências dos alunos, com um dado número de alunos designados a
cada ponto. Bowerman et al., 1995, também abordam o problema de roteamento de
ônibus escolar urbano. Graciolli, 1994, faz a abordagem do problema de
roteamento na coleta de resíduos sólidos de serviços de saúde. Renz, 1994,
aborda o problema de roteamento com restrições de tempos de viagens e de
trabalho para equipes de inventário florestal, responsáveis por coleta
sistemática de informações. E assim poder-se-ia citar muitos outros trabalhos
de roteamento de veículos, pois este é um dos assuntos mais estudados na área
de Pesquisa Operacional [Bodin et al., 1983].
O problema de roteamento no transporte escolar em foco neste trabalho, descrito
na seção 2, foi tratado através da junção de vários procedimentos heurísticos
da Pesquisa Operacional, conforme apresentados na seção 3, onde são
evidenciados os detalhes necessários para considerar as particularidades do
problema de forma a obter-se boa performance para os referidos procedimentos.
Na seção 4 é feita a implementação dos procedimentos heurísticos ao problema
real e os resultados são analisados. Finalmente, na seção 5, são apresentadas
as conclusões e sugestões para trabalhos futuros.
2. DESCRIÇÃO DO PROBLEMA REAL
Algumas escolas particulares na cidade de Curitiba, PR, possuem uma frota de
veículos composta por ônibus, micro-ônibus e/ou vans, que pode ser própria ou
terceirizada, para prestar atendimento aos seus alunos quanto ao serviço de
coleta e/ou entrega dos alunos nas suas residências (casas, apartamentos,
condomínios e outros).
A escola pesquisada possui 29 ônibus próprios de diversas capacidades, variando
de 32 até 60 lugares, que atendem a 997 alunos na data da pesquisa. Destes 29
ônibus, a escola utiliza apenas 24, sendo que os demais permanecem como reserva
para situações emergenciais. São em número de 12 os tipos de ônibus (conforme a
capacidade), de acordo com o Quadro_1, na seção 4. Estes veículos partem da
garagem aproximadamente uma hora antes do início das aulas, apanham um certo
número de alunos e se dirigem à escola. Como a escola pesquisada se situa na
região metropolitana de Curitiba, os ônibus permanecem na escola após a coleta,
retornando para a cidade apenas no final das aulas para o serviço de entrega
dos alunos.
São 997 alunos concentrados em 717 pontos de demanda, ou seja, muitos dos
pontos de demanda possuem mais de um usuário. Há alunos que são irmãos, bem
como alunos que moram em um mesmo edifício. A máxima demanda constatada em um
ponto de demanda foi de 10 alunos.
A escola faz a localização de todos os alunos em um mapa da cidade. Sobre o
mapa, o gerente de transportes da escola, com o auxílio de um taxista
conhecedor das particularidades da cidade e dos sentidos das vias, define os
roteiros, de forma a atender todos os alunos. A solução adotada pela escola
encontra-se no Quadro_1, onde se vê, por exemplo, que a escola utiliza 2 dos 3
ônibus do tipo 1, com capacidade para 32 lugares, sendo que as demandas são de
27 e 30 alunos cada um. As distâncias percorridas para este ônibus são,
respectivamente, 10.523 m e 17.953 m.
Conforme mencionado, o objetivo do presente trabalho é fornecer à escola uma
solução otimizada, que minimize, além da distância total percorrida pela frota
de ônibus, o número destes, considerando as suas capacidades e as
particularidades do problema.
Para isto, o trabalho foi dividido em 5 fases :
1a. Fase: Localização das residências dos alunos em um mapa digitalizado da
cidade de Curitiba obtendo-se, desta forma, as coordenadas geográficas para
cada um dos pontos de demanda. Na Figura_1 tem-se os pontos de demanda e também
a localização da garagem dos ônibus e da escola;
2a. Fase: Obtenção da quantidade e respectivas capacidades ótimas dos
veículos necessários para atender a demanda.
3a. Fase: Determinação dos clusters ótimos de atendimento, ou seja,
definição de quais pontos de demanda serão atendidos por cada um dos veículos
da frota. Numa 1ª etapa, sem considerar as capacidades dos ônibus e em uma 2ª
etapa, fazendo esta consideração;
4a. Fase: Obtenção dos roteiros em cada cluster de atendimento, ou seja,
obtenção da sequência em que os pontos de demanda devem ser atendidos;
5a. Fase: Aplicação de melhorias nos roteiros obtidos na 4a. Fase,
evitando-se cruzamentos entre rotas e cruzamentos dentro de uma rota;
Os resultados para as fases de 2 a 5 foram obtidos através da implementação das
heurísticas apresentadas na seção 3.
3. HEURÍSTICAS ABORDADAS PARA A SOLUÇÃO DO PROBLEMA REAL
Nesta seção são apresentadas as heurísticas utilizadas neste trabalho com o
objetivo de solucionar o problema de roteamento no transporte escolar
pesquisado. Na seção 3.1 é apresentado um modelo de um Problema de Programação
Linear Inteira (PPLI) para a obtenção da quantidade necessária de ônibus de
cada tipo a serem utilizados pela escola para atender a demanda. Na seção 3.2 é
apresentado um procedimento para a obtenção de sementes (que farão o
"papel" de depósitos artificiais) com o objetivo de inicializar a
formação dos clustersde atendimento, ou seja, dos agrupamentos de pontos de
demanda que serão atendidos pelos ônibus. Nas seções 3.3 e 3.4 estão descritos
procedimentos para a obtenção destes clustersótimos; primeiramente sem
considerar as restrições de capacidade dos veículos (1a. etapa), e depois,
considerando as capacidades (2a. etapa).
O objetivo na formação dos clusters é concentrar os pontos de demanda,
evitando-se assim que um aluno fique muito tempo no veículo. Com uma melhor
concentração dos pontos de demanda, o tempo que cada ônibus leva desde a sua
saída da garagem até o primeiro ponto de demanda de seu cluster não é
contabilizado para o aluno. Além disso, todos os alunos de um mesmo cluster
terão aproximadamente o mesmo tempo de permanência dentro do ônibus.
Definidos os clusters de atendimento, na seção 3.5 é descrito o procedimento de
construção de rota utilizado neste trabalho, o algoritmo da inserção mais
econômica. Para fazer uso deste algoritmo, foi considerado como primeiro nó de
cada rota, o ponto de demanda mais próximo da garagem e como último nó de dada
rota, o ponto de demanda mais próximo da escola, sendo que os demais pontos de
demanda foram inseridos entre o inicial e final pelo referido algoritmo de
inserção. E, na seção 3.6, são apresentados procedimentos de melhorias para se
evitar cruzamentos entre e dentro das rotas.
Em cada uma das seguintes sub-seções, de 3.1 a 3.6, são apresentados os
algoritmos heurísticos abordados e, na mesma sub-seção, a forma como os
referidos algoritmos foram utilizados para resolver o problema estudado.
3.1 O PPLI para a obtenção da Quantidade Ótima de Ônibus de cada Tipo
Para inicializar a solução do problema, obteve-se a quantidade e capacidades
ótimas dos ônibus a serem utilizados através de um PPLI considerando a
disponibilidade de todos os veículos (quantidades e capacidades) e a demanda
total de alunos.
O objetivo deste modelo, apresentado a seguir, é minimizar a quantidade de
ônibus, e consequentemente, estar-se-á minimizando o número de motoristas e os
custos operacionais com a frota, considerando que a frota de veículos é própria
e que os veículos encontram-se em igual estado de conservação.
sujeito a :
onde as variáveis de decisão xi são as quantidades de ônibus de cada tipo
disponíveis pela escola, ntipos é a quantidade de tipos de ônibus, conforme as
diversas capacidades, Capi é a capacidade de cada tipo de ônibus, Q é a
quantidade total de alunos a serem atendidos e qi é a quantidade de ônibus
disponível de cada tipo.
Utilizando os dados do Quadro_1, o modelo do PPLI para o problema abordado fica
estabelecido como se segue:
sujeito a :
onde a folga f é colocada com o objetivo de nas fases seguintes poder-se fazer
um melhor ajuste na formação dos clusters. Esta folga f assume valores variando
de 2 a 6 lugares, que corresponde de 5% a 15% da capacidade de um veículo médio
(40 lugares). Das 4 alternativas testadas nos procedimentos subsequentes
(obtenção das sementes e formação dos clusters ótimos), a alternativa com folga
igual a 4 foi a que apresentou melhores resultados, pelos motivos expostos na
seção 3.4.
A restrição (3.4-b) do modelo é devido a uma necessidade particular da escola:
ter disponíveis dois micro-ônibus para o atendimento da região central da
cidade, onde ônibus grandes não circulam ou o fazem com dificuldade.
A solução ótima para este modelo forneceu 24 ônibus, número este coincidente
com o número já utilizado pela escola. Observe-se que a quantidade e
capacidades dos veículos foram obtidas apenas para se inicializar o problema,
já que depois, como será visto na seção 3.4, estes dados serão remanejados.
3.2 Obtenção das Sementes (depósitos artificiais)
Para inicializar a formação dos clusters, precisa-se fazer a determinação de m
sementes, uma para cada ônibus. Entre os diversos procedimentos existentes na
literatura, adotou-se o apresentado por Paraíba, 1990:
Passo 1. Faça k = 1. Encontre ik, tal que c(0, ik) = max {c(0, i)}, para
todo i, onde 0 é o depósito central, ou seja, encontre o ponto de demanda mais
distante do depósito central;
Passo 2. Enquanto 1 £ k < m, faça:
k = k + 1. Encontre o ponto de parada i*, ainda não selecionado tal que
:
c(i, ik-1) + c(i, ik-2) + ... + c(i, i2) + c(i, i1) seja máximo para i
= i*.
Faça ik = i*.
O algoritmo descrito determina as sementes de forma que estejam o mais longe
uma das outras, evitando a concorrência na subsequente formação dos clusters.
Como o problema abordado não possui um depósito central, e além disso,
necessita de clusters para os pontos de demanda localizados na região central
da cidade, fez-se o seguinte:
- primeiramente foram definidas sementes para a região central da cidade. Os
locais para estas sementes foram escolhidos manualmente, fazendo-se, desta
forma, uma interação entre o tomador de decisões e o algoritmo. Cada uma destas
sementes centrais agrupou os 30 alunos mais próximos, determinados pela
distância euclidiana. Para estes 2 clusters iniciais ficou definida uma folga f
de 2 lugares em cada um, para eventuais ajustes subsequentes, conforme
explanado na seção 3.4.
- em seguida, pelo algoritmo apresentado anteriormente, foram determinadas as
demais 22 sementes para o restante da cidade, onde foi considerado como
depósito central, nó 0, uma (das duas) sementes anteriormente escolhidas na
região central da cidade e, assim, obtiveram-se as 24 sementes, uma para cada
veículo. O que aconteceu, porém, foi que a partir da obtenção da 8ª semente, as
suas localizações começaram a ficar muito próximas, ou seja, as sementes
passaram a ser concorrentes para a aglutinação dos pontos de demanda. Optou-se,
então, por ficar com as 7 primeiras sementes, com localizações bem
diferenciadas. Na Figura_2 tem-se a localização das sementes, onde as sementes
centrais são as sementes 1 e 2, e as outras 7, obtidas pelo algoritmo, foram
numeradas de 3 a 9.
3.3 Procedimento para a obtenção dos clusters ótimos - 1a. Etapa
Obtidas as sementes, aplicou-se o procedimento proposto por Gillett e Johnson,
1973 [Bodin et al., 1983], [Golden et al., 1977] para a obtenção dos clusters:
Inicialmente, todos os pontos encontram-se sem designação.
Para cada nó i, seja t'(i) a semente mais próxima a i, e t"(i) a segunda
semente mais próxima a i.
Para cada nó i, a razão: r(i) = c(i, t'(i)) / c(i, t"(i)) é calculada e
todos os nós são colocados em ordem crescente pelos valores de r(i), e assim
fica determinada a ordem na qual os nós são designados a uma semente. Aqueles
que estão relativamente próximos a uma semente são considerados primeiro.
Depois que um certo número de nós foram designados da lista de r(i), um pequeno
cluster é formado ao redor de cada semente.
Os nós i cuja razão r(i) está próxima de 1, ou seja, i é um nó que pode ser
agrupado por t' ou t", são designados como se segue. Se dois nós
adjacentes j e k já estão designados a uma semente, inserindo i entre j e k na
rota ligada a t (t' ou t"), cria um custo adicional igual a c(j, i) + c(i,
k) - c(j, k) ao custo total. Ou seja, o algoritmo designa o nó i a uma semente
t (t' ou t") inserindo i entre dois nós já designados a semente t (t' ou
t") de maneira que minimize os custos. O nó i será designado à semente t
(t' ou t") que fornecer o menor custo adicional.
No problema abordado, fez-se a designação dos pontos de demanda às 7 sementes
definidas em 3.2 seguindo o procedimento anteriormente proposto, não esquecendo
que para as 2 sementes da região central da cidade, já tinham sido designados
30 alunos. Nesta fase não foram consideradas as capacidades dos veículos, mas
simplesmente o cálculo da razão r(i) como apresentado anteriormente para se
fazer a designação. Para os pontos i duvidosos, com r(i) > 0.7, fez-se a
designação de acordo com a expressão c(j, i) + c(i, k) - c(j, k). Desta forma,
ficou-se com 2 clusters com demanda de 30 alunos e 7 grandes clusterscujas
demandas ficaram superiores às capacidades dos ônibus.
A designação dos pontos de demanda nesta 1ª etapa tem por objetivo fornecer uma
solução inicial para a aplicação do algoritmo apresentado na seção 3.4 a
seguir, o qual estabelece a formação definitiva dos clusters.
3.4 Procedimento para a obtenção dos clusters ótimos - 2a. Etapa
Este procedimento, devido a Tillman e Cain, 1972 [Tillman e Cain, 1972], [Bodin
et al., 1983], começa com uma solução inicial consistindo por servir cada nó
exclusivamente por uma rota a partir do depósito mais próximo.
A partir desta solução inicial, o procedimento consta basicamente do seguinte:
seja c(i, j) o custo ou distância entre os nós i e j; c(i, k) o custo ou
distância entre o nó i e o depósito k. O custo total inicial de todas as rotas
é dado por
D = {c
(i, k)}.
O método liga sucessivamente pares de nós sempre visando um custo total mínimo.
Uma regra básica é assumida no algoritmo: a designação inicial dos nós ao
depósito mais próximo é temporária, mas assim que dois ou mais nós tenham sido
designados a uma rota comum a partir de um mesmo depósito, os nós não podem ser
redesignados a outro depósito. Além disso, assim como no algoritmo original dos
savings de Clarke e Wright, 1964, os nós i e j podem ser ligados somente se i e
j não forem pontos interiores de uma rota existente.
A cada passo, a escolha de ligar um par de nós i e j em uma rota a partir de um
depósito k é feita em termos dos savings. Os nós i e j podem ser ligados
somente se as restrições de capacidade e de ligação não forem violadas. O
cálculo dos savings não é tão simples quanto no caso de um único depósito. Os
savings s(i, j, k) estão associados com todas as combinações dos nós i e j e
depósito k, e representa o decréscimo no custo total ou distância viajada
quando se liga i e j a k. A fórmula é dada por :
s(i, j, k) = c'(i, k) + c'(j, k) - c(i, j) ,
onde c'(i, k) = 2 <formula/> {c(i, t)} - c(i, k), se i
ainda não recebeu uma designação permanente;
c(i, k), caso contrário.
No primeiro caso, o nó i está sendo redesignado do seu depósito mais próximo e
a designação previamente feita de custo 2 min {c(i, t)} é economizada; no
segundo caso, o nó j está sendo inserido entre o depósito k e o nó i e a
ligação de i a k é retirada da solução atual.
Os savings s(i, j, k) são calculados para i , j = 1, ..., n(i ¹ j) e k = 1,
..., m a cada passo. Eles são armazenados em m matrizes de ordem nx n. A cada
passo, a ligação i - j em k é escolhida tal que maximize s(i, j, k) e que
produza uma solução viável (capacidade e outras restrições).
Seguindo o procedimento descrito para o problema abordado, tem-se já a solução
inicial para o problema determinada na seção 3.3. Inicialmente tem-se nrotas,
sendo que estas rotas vão sendo ligadas de acordo com o cálculo dossavings
anteriormente apresentado, fazendo o devido controle das capacidades dos
ônibus. Ao se finalizar o processo de formação de rotas, alguns dos pontos de
demanda não tinham se ligado a nenhuma das rotas formadas, e, ao invés de se
ter a formação de 24 rotas, obtiveram-se 29 rotas, pois 5 pontos de demanda
ficaram isolados, cada um em uma rota formada por apenas ele próprio e o
depósito ao qual estava temporariamente ligado. Para contornar este problema,
utilizaram-se as folgas previstas em cada uma das rotas. Os lugares nos
veículos, correspondentes a estas folgas, passaram a ficar
"liberados" a partir deste momento, ou seja, cada ônibus passou a
usufruir de sua capacidade total.
Para fazer bom uso desta capacidade "adicional", foram designados os
pontos isolados em ordem decrescente de demanda, ou seja, quanto maior a
demanda, maior foi a prioridade para se fazer a designação, garantindo-se desta
forma, melhores inserções para estes pontos isolados. Foi nesta etapa que
verificou-se que para uma folga de 4 lugares obtinha-se, para este problema,
uma melhor solução: além de menor distância total, obteve-se maior
homogeneidade nas demandas dos ônibus, ou seja, os veículos ficaram com a taxa
de ocupação semelhante.
Fez-se também, nesta etapa, o remanejamento dos ônibus, pois as vezes ocorria o
fato de ônibus menores terem maior quantidade de alunos do que ônibus maiores,
ou seja, alocaram-se as demandas dos clusters em ordem crescente aos ônibus com
capacidades em ordem crescente também. O resultado deste procedimento, ou seja,
a definição dos clustersfinais, está na Figura_3.
Obtidos os clusters ótimos, deve-se obter o roteiro para cada veículo, ou seja,
definir a sequência na qual a coleta de alunos deve ser feita, e para isto foi
utilizado o algoritmo heurístico de Inserção mais Econômica, descrito a seguir.
3.5 Algoritmo Heurístico para Construção de Rota - Inserção mais econômica
O algoritmo heurístico da Inserção mais Econômica, devido a Rosenkrantz, Sterns
e Lewis, 1977 [Golden et al., 1980], [Bodin et al., 1983], considera uma rota
com k nós na iteração k e determina qual nó, que ainda não está na rota,
poderia ser o próximo a ser ligado à rota (seleção) e então determina onde na
rota ele deveria ser inserido (inserção). Para isso, são adotados os seguintes
passos:
Passo 1. Comece com um sub-grafo consistindo somente do nó i;
Passo 2. Ache um nó k tal que c(i, k) seja mínimo e forme a sub-rota i-k-i;
Passo 3. Passo da Seleção e Inserção. Ache (i, j) na sub-rota e k que não
esteja na rota, tal que c(i, k) + c(k, j) - c(i, j) seja mínimo e, então,
insira k entre i e j;
Passo 4. Se um circuito Hamiltoniano tiver sido formado, pare. Caso
contrário, volte ao passo 3.
O algoritmo da inserção mais econômica foi aplicado separadamente para cada um
dos clusters formados em 3.4, considerando sempre as distâncias euclidianas
entre os pontos de demanda.
Esgotados os estágios dos algoritmos heurísticos, ou seja, construidos os
roteiros para cada um dos ônibus, propõe-se um refinamento baseado em trocas de
pontos entre rotas ou ainda, em trocas na sequência de pontos numa mesma rota
de tal forma a obter uma redução do custo total, evitando cruzamentos entre
rotas e dentro de uma mesma rota, respectivamente. Estes refinamentos estão
descritos na seção 3.6 a seguir.
3.6 Procedimentos para melhoria da solução
Dos numerosos procedimentos existentes para melhoria de rotas, o presente
trabalho faz a abordagem e a aplicação do procedimento de troca de pontos entre
duas rotas, descrito por Paraíba, 1990, e do procedimento das melhorias 2-opt e
3-opt em uma rota, desenvolvido por Lin e Kernighan, 1973, apresentados a
seguir:
Procedimento 1 : Troca de pontos entre duas rotas Rs e Rk:
Seja st Î Rs (localizado entre st-1 e st+1) e km Î Rk (localizado entre km-1 e
km+1). Se
c(st-1, km) + c(km, st+1) + c(km-1, st) + c(st, km+1) < c(st-1, st) + c(st,
st+1) + c(km-1, km) + c(km, km+1),
então troque st por km na rota Rs e km por st na rota Rk.
Se este procedimento for repetido para todos os pares de pontos, então ele
reduz a interseção entre os roteiros.
Procedimento 2 : Troca de pontos em uma mesma rota:
Os procedimentos 2-opt e 3-opt para trocas em uma rota consistem no seguinte:
para um dado k, define-se uma k-troca de uma rota consistindo da deleção de k
arcos de uma rota que serão trocados por k outros arcos de modo a formar uma
nova rota. Uma rota é k-ótima se não for mais possível efetuar trocas para
melhorar a distância total viajada. Geralmente o 3-opt se aproxima bastante da
solução ótima.
Os procedimentos 1 e 2 foram aplicados ao problema pesquisado até que não fosse
mais possível efetuar trocas entre as rotas e nas rotas.
Os resultados das heurísticas adotadas, demandas de cada ônibus e distâncias
euclidianas percorridas, encontram-se no Quadro_1. Para exemplificar, a Figura
4 mostra o roteiro obtido para um dos ônibus, a nível de quadra após o
procedimento de inserção e de melhorias.
4. IMPLEMENTAÇÃO DAS HEURÍSTICAS E ANÁLISE DOS RESULTADOS
Para o problema real de roteamento no transporte escolar, apresentado na seção
2, utilizando-se as técnicas e as respectivas particularidades necessárias
descritas na seção 3, implementadas em linguagem Visual Basic 4.0, obteve-se a
solução apresentada no Quadro_1, nas colunas da Solução Otimizada. Para medir-
se o grau de eficiência das técnicas abordadas, os resultados obtidos foram
comparados com a solução realizada pela escola, atentando para o fato de que em
ambas soluções foram consideradas as distâncias euclidianas.
No Quadro_1 verifica-se que tanto a solução da escola quanto a solução
otimizada fez uso de 24 ônibus, observando que um dos ônibus do tipo 4, com
capacidade para 43 lugares, faz 2 viagens, na solução da escola.
Vê-se, por exemplo noQuadro_1, que dos 3 ônibus do tipo 1, cuja capacidade é de
32 lugares, a escola utiliza 2 que percorrem 10.523 m e 17.953 m, ocupando 27 e
30 lugares, respectivamente. Já a solução otimizada também faz uso de 2 destes
ônibus ocupando 30 lugares cada um deles, sendo que cada um dos ônibus deverá
percorrer 3.351 m e 6.537 m, respectivamente. E assim tem-se a leitura dos
demais resultados.
Através destes resultados observa-se que o percentual de melhoria ao adotar-se
os procedimentos de otimização é bastante significativo, sendo de
aproximadamente 25% ((451.594 - 338.258) / 451.594). Esta melhoria foi obtida,
principalmente, devido a maneira de se concentrar os pontos de demanda.
Na Figura_5, tem-se a visualização de todas as rotas para a solução otimizada.
5. CONCLUSÕES E SUGESTÕES PARA FUTUROS TRABALHOS
Dentre as diversas formas possíveis de se resolver o problema de roteamento no
transporte escolar, foi adotada uma metodologia, neste trabalho, que consta
basicamente das seguintes etapas:
- fez-se a localização dos pontos de demanda em um mapa digitalizado
de maneira exata: não apenas considerando rua, bairro, mas também a
quadra e o lado da quadra (direito ou esquerdo). Com isto, obtiveram-
se as coordenadas geográficas de cada ponto de demanda;
- obtiveram-se, em seguida, as sementes que fazem o "papel"
dos depósitos (fictícios) dos algoritmos abordados para a formação de
clustersde atendimentode acordo com a quantidade de veículos;
- obtiveram-se os clusters para cada uma das sementes;
- formaram-se as rotas envolvendo os pontos de demanda de cada
cluster;
- finalmente, fizeram-se melhorias nestas rotas.
As melhorias obtidas através da solução otimizada em relação a solução da
escola foram muito significativas, como pode ser constatado no Quadro_1, e não
podem ser desprezadas. Ao se minimizar a distância total percorrida pela frota
de ônibus, obtém-se como consequências economia de combustível e de manutenção
dos ônibus além da minimização do tempo de permanência dos alunos nos ônibus,
fator considerado como sendo de maior importância para a escola e maior
satisfação por parte dos pais e alunos.
Deve-se considerar, entretanto, que uma boa solução matemática, apresentando
elevado percentual de melhoria, pode não significar que seja uma boa solução
para a escola, que possui muitas particularidades na sua forma de atendimento
como, por exemplo, motoristas que estão acostumados com a sua região de
atendimento e não aceitam grandes mudanças; ou então pais que exigem que seu
filho seja atendido por determinado motorista, ou ainda, exigência de horários,
em que os motoristas não podem seguir a sequência de pontos otimizada para
entrega e/ou coleta.
Além deste problemas, pode-se dizer que a maior dificuldade encontrada para a
implementação deste trabalho na prática foi, sem dúvida, o fato da solução
precisar sofrer ajustes no decorrer do ano, devido a atualização frequente na
localização dos pontos de demanda, ocorrendo de 2 a 3 atualizações semanais.
Estas atualizações ocorrem pela inclusão, exclusão e, principalmente, devido a
mudanças nos endereços dos alunos. A solução vai sendo modelada, de acordo com
estas alterações, sempre tentando minimizar as alterações nos roteiros dos
ônibus, normalmente obtendo-se soluções mais distantes da solução ótima, até
que toda a solução deva ser remodelada, a cada semestre, por exemplo.
Como complemento a este trabalho, precisa-se ainda "transformar" os
roteiros obtidos considerando apenas as distâncias euclidianas, em roteiros
quadra a quadra, isto é, considerando os sentidos das vias, mãos e contra-mãos,
obtendo-se assim, os roteiros reais e suas respectivas distâncias reais.
Seria, também, bastante interessante, comparar os procedimentos heurísticos
utilizados com as outros desenvolvidos mais recentemente, como por exemplo,
Algoritmos Genéticos [Goldberg, 1989], Redes Neurais [Hopfield, 1984] e
Simulated Annealing [Kirkpatrick et al., 1983]. Por se tratar de procedimentos
heurísticos, ter-se-á uma infinidade de soluções para o problema de roteamento
no transporte escolar; quais e de que maneira estes procedimentos devem ser
adotados de forma a obter uma boa solução deve ser uma preocupação constante no
tratamento de todo problema de roteamento.
Os autores agradecem a Maxi Data Tecnologia em Informática pela
disponibilização do mapa digitalizado da cidade de Curitiba, PR, para a
realização deste trabalho.