XXX ENCONTRO NACIONAL DE ENGENHARIA DE PRODUÇÃO
Maturidade e desafios da Engenharia de Produção: competitividade das empresas, condições de trabalho, meio ambiente.
São Carlos, SP, Brasil, 12 a15 de outubro de 2010.
PROGRAMAÇÃO DE VEÍCULOS
APLICADO AO TRANSPORTE
RODOVIÁRIO
Elaine Corrêa Pereira (FURG)
[email protected]
Sérgio Fernando Mayerle (UFSC)
[email protected]
Vilmar Trevisan (UFRGS)
[email protected]
Este trabalho tem foco no plano de operação de empresas de
transporte rodoviário regional de passageiros, visando à alocação da
frota. Tem por objetivo desenvolver um modelo dinâmico, que permita
corrigir os desvios ocorridos durante a execcução do plano ao longo
do horizonte de planejamento em tempo computacional razoável. O
modelo de programação da frota se resolve através de um processo
seqüencial de aplicação do algoritmo húngaro, e os resultados obtidos
se comparam com limite inferior, calculado pela relaxação de algumas
restrições do problema. O modelo desenvolvido foi aplicado aos dados
de uma empresa que atua na região sul do Brasil e os resultados
obtidos são analisados.
Palavras-chaves: programação de veículos, algoritmo húngaro,
otimização combinatorial, alocação heurística, transporte rodoviário
regional de passageiros
1. Introdução
Um dos mais importantes problemas em pesquisa operacional é o problema de alocação de
veículos (VSP), que consiste em atribuir veículos a um conjunto de viagens predeterminadas,
com horários e locais de saída e chegada fixos, minimizando uma função de custo.
As variações específicas do VSP são consideradas problemas NP- difícies, o que significa
dizer que até o presente momento não pode ser resolvido otimamente em tempo polinomial;
técnicas heurísticas foram desenvolvidas ao longo do tempo com o objetivo de encontrar
algoritmos mais eficientes.
O VSP foi inicialmente introduzido por Christofides e Eilon (1969) como um problema de
despacho de caminhões. Ceder e Stern (1981) resolveu este problema usando uma heurística
inteligente baseada em um algoritmo de economias e em Bodin et al. (1983) fez uma revisão
bibliográfica do VSP e suas variações.
O VSP formulado como um problema de atribuição aplicado ao transporte rodoviário urbano
de passageiros foi proposto por Mayerle (1996), encontrando sua solução através do algoritmo
húngaro. Baita et al (2000) fez uma comparação de três métodos para resolver o VSP: modelo
de atribuição, programação lógica e algoritmos genéticos. As soluções obtidas pelos métodos
de atribuição e programação lógica foram consideradas merecedoras de uso prático, enquanto
o algoritmo genético foi incapaz de obter resultados semelhantes.
Nota-se que com o tempo houve avanços na procura de técnicas que resultassem soluções
melhores para o VSP, o que conduziu a melhorias concretas aplicadas a problemas do mundo
real. No entanto, quase todos os modelos desenvolvidos têm um enfoque particular, que é
levado em consideração para a resolução do problema. Por isso, é praticamente impossível
desenvolver ferramentas gerais que se aplicam a todos problemas de programação de frota.
Mesmo quando se trabalha com o mesmo tipo de transporte, digamos, transporte de
passageiros, existem singularidades entre as diferentes companhias de transporte e as
abordagens gerais devem ser adaptadas antes de serem usadas.
Este trabalho tem foco no plano de operação de empresas de transporte rodoviário regional de
passageiros, visando à alocação da frota. Tem como objetivo desenvolver um modelo
dinâmico, que permita corrigir os desvios ocorridos durante a execução do plano ao longo do
horizonte de planejamento em tempo computacional razoável. O modelo de programação da
frota é resolvido através de um processo seqüencial de aplicação do algoritmo húngaro e os
resultados obtidos são comparados com limites inferiores, calculados pela relaxação de
algumas restrições do problema. O modelo foi aplicado para a programação da frota de uma
empresa que transporte que opera na região sul do Brasil.
2. Caracterização do problema
O transporte rodoviário regional de passageiros se caracteriza pelo transporte entre cidades,
estados e países, onde o ciclo de viagens se repete em períodos ou dias alternados com linhas
regulares de longa distância, com horários e itinerários bem definidos. Feriados e datas
especiais, o número de viagens aumenta. A freqüência das atividades de cada veículo é
pequena, visto que algumas viagens não terminam no mesmo dia que começam. As garagens
se localizam em diversos pontos da rede viária regional. Estas garagens são para a
manutenção ou tempo ocioso em que determinado veículo aguarda a próxima viagem.
2
Uma viagem é caracterizada pelo seu local de saída, horário de saída, local de chegada,
horário de chegada e tipo de veículo. Cada viagem exige um tipo de veículo diferenciado que
está associado a comodidade e conforto do veículo e têm um custo associado a ela. Existem
também viagens sem passageiros, ou seja, deslocamentos do veículo entre terminal (local de
chegada) até garagem após terminar uma viagem e aguardar a próxima atribuição ou entre
garagem e terminal (local de saída) para iniciar uma nova viagem . O objetivo é alocar o tipo
de veículo exigido a cada viagem, minimizando uma função custo. O processo de alocação de
viagens aos veículos dentro de um horizonte de planejamento aplicado ao transporte
rodoviário regional de passageiros é distinto, pois o início de um novo horizonte de
planejamento tem que levar em consideração o resultado do anterior.
Na literatura estudada o VSP que mais se assemelha a formulação do problema de transporte
rodoviário regional de passageiros são os problemas VSPMD (problema de alocação de
veículos com múltiplos depósitos) e o VSPMVT (problema de alocação de veículos com
múltiplos tipos de veículos), como os trabalhos desenvolvidos em 2006 por Kliewer et al e
Rodrigues et al. Estes problemas podem ser modelados como problemas de fluxos em redes e
podem ser resolvidos por heurísticas evitando a explosão combinatorial.
Na seqüência, usa-se a experiência de várias implementações anteriores, a fim de gerar um
modelo e uma boa solução viável que pode ser obtida em um período de tempo razoável. Uma
solução viável é aquele que atribui um veículo para cada viagem não violando qualquer
restrição. Esta solução é boa se usa poucos veículos e seu custo é pequeno. Uma vez que não
existe um meio eficaz para comparar a solução encontrada com a solução ótima, desenvolveuse um algoritmo capaz de obter um limite inferior para a solução ótima e assim poder
comparar este limite com a solução encontrada.
O método desenvolvido é dinâmico, o que significa que a solução encontrada para o horizonte
de planejamento é obtida em tempo razoável e, se for necessário acrescentar novos
deslocamentos e ou novas restrições para o problema, um novo planejamento pode ser
rearranjado a partir de qualquer ponto, respeitando a solução obtida até o momento.
3. Modelo proposto
A rede viária do problema é representada por um grafo, onde o conjunto de nós é formado
pelos locais de início e fim de viagens (terminais), que são cidades de uma determinada
região. Alguns terminais também são garagens. O conjunto de arcos é formado pelas vias não
direcionadas que ligam estas cidades. Os tempos de deslocamentos nos arcos correspondem
aos deslocamentos produtivos (movimentos de veículos com demanda) e aos deslocamentos
improdutivos, estes últimos, referentes a movimentos de veículos vazios. A frota é constituída
de tipos de veículos classificados de acordo com as características de conforto e comodidade
oferecida aos passageiros.
O problema consiste em encontrar uma solução viável de mínimo custo que satisfaça o
conjunto de restrições, ou seja, não pode haver sobreposição de viagens para cada veículo,
adequar o veículo às necessidades específicas de cada viagem e assegurar os tempos mínimos
necessários aos deslocamentos dos veículos vazios entre os terminais, caso seja necessário.
A solução consiste em construir seqüências de viagens, alocadas ao tipo de veículo exigido,
através da análise dos custos, respeitando restrições, tais como: local de saída, local de
chegada, hora de saída e hora de chegada das viagens, de forma a minimizar os custos
improdutivos (tempo de permanência e deslocamentos) e cobrir todas as viagens do horizonte
de planejamento.
3
No modelo proposto de alocação da frota considera-se um grafo G(V, A), onde V é o conjunto
das viagens e A é o conjunto de arcos, constituído pelos arcos viáveis (vu, vl), ou seja, caso
seja possível a realização da viagem vl após a viagem vu, pelo mesmo veículo. Observa-se que
o grafo G está disposto por camadas, onde cada camada k está constituída por um subconjunto
de viagens Vk de V. As camadas são constituídas por viagens que não podem ser realizadas
uma na seqüência da outra. A figura 1 mostra um exemplo de um grafo com 8 viagens
distribuídas em 4 camadas.
1
3
Camada 1
2
5
Camada 2
4
7
Camada 3
6
8
Camada 4
Figura 1: Camada e possíveis seqüencias de viagens
A cada camada do grafo G, formula-se um problema de atribuição. A princípio considera-se
que todos os veículos estão disponíveis. A solução de cada problema de atribuição aloca as
viagens de uma camada do grafo G à frota disponível. O processo se repete para todas as
camadas; considera-se a solução de cada camada como uma solução parcial.
Assim, formulam-se K problemas de atribuição, isto é, um problema de atribuição a cada
camada da seguinte forma, onde M é o número de veículos e L é o número de viagens da
camada:
M  LM  L
Z  Min   cij xij
i 1
(1 a)
j 1
s.a.
m L
x
ij
1
j  1,..., M  L
(1 b)
x
ij
1
i  1,..., M  L
(1 c)
i 1
m L
j 1
xij  0, 1
(1 d)
As restrições (1 b) e (1 c) garantem que cada viagem será alocada a um veículo distinto; a
restrição de integridade (2 d) garante que, se xij = 1, a viagem i é realizada pelo veículo j ou,
caso contrário, xij = 0. A função objetivo (1 a) minimiza os custos operacionais de alocar
viagens aos veículos. Associa-se a cada problema de atribuição de uma camada uma matriz
quadrada de custos C =[ cij ] de ordem M + L.
4
3.1. Custo operacional de uma seqüência de viagem
Para calcular o custo de alocar uma viagem i à seqüência de viagens de um veículo j, isto é,
calcular os elementos, cij, da matriz C, fazem-se as seguintes considerações.
As viagens são caracterizadas pelo local de saída, local de chegada, horário de saída e horário
de chegada, tipo de viagem e tipo de veículo adequado para sua realização.
Seja SVj, uma seqüência de viagens alocada ao veículo j, onde vu é a última viagem realizada
pelo veículo; a viagem vi é uma das possibilidades de viagem a ser adicionada a seqüência
SVj. Para alocar vi a SVj é necessário analisar o terminal ou garagem onde se encontra este
veículo, o tempo de deslocamento do local onde se encontra até o terminal de saída da viagem
vi e analisar se este veículo é adequado para a viagem vi.
Pode ocorrer que o veículo após término de uma viagem tenha que permanecer em um dos
terminais ou em uma das garagens e também se deslocar de um terminal ao outro; a busca do
melhor local para permanência do veículo é feita pelo custo mínimo entre esses locais. Evitase a invibialidade de alocação de viagens a veículos através de penalidades.
3.2. Algoritmo de Alocação
Para obter a solução do modelo apresentado, segue-se os seguintes passos:
Inicialização: Entre com os seguintes conjuntos: conjunto de viagens do horizonte de
planejameto, conjunto de veículos da frota e a matriz de tempos de deslocamentos
improdutivos. Faça k = 1.
Seleção de Camadas: Monte a camada k, ou seja, o subconjunto de viagens, Vk de V.
Matriz de Custos: Monte a matriz C, calculando seus custos.
Problema de Atribuição: Resolva o problema de atribuição para a matriz de custos C , através
do algoritmo húngaro, que resulta uma solução parcial de pares, que representam
(viagem, veículo).
Alocação das Viagens: Atribua ao veículo a viagem, seguindo os pares (viagem,veículo)
resultantes da solução do problema de atribuição e calcule o custo da seqüência de viagens do
veículo com o acréscimo da viagem alocada.
Teste de Finalização: Retire as viagens da camada k de V e faça k = k + 1. Se ainda existir
viagens no conjunto de viagens do horizonte de planejamento, volte ao passo 2; em caso
contrário, vá para o passo 7.
Finalização: Determine os seguintes conjuntos: conjunto das viagens alocadas, conjunto das
viagens não alocadas e conjunto dos movimentos de veículos vazios.
4. Validação
Como o modelo de programação desenvolvido é um método heurístico cuja solução é
aproximada, não se tem como medir o quanto esta solução está próxima ou longe da melhor
solução em termos de qualidade. Então para validar a solução que será obtida com a aplicação
desse modelo, propõe-se o cálculo de limite inferior para o problema de programação da frota
através do relaxamento de algumas restrições do problema real e assim avaliar a qualidade da
solução obtida.
5
Para encontrar o limite inferior para o problema de alocação da frota proposto nesse trabalho,
relaxa-se a restrição de adequar a viagem ao tipo de veículo exigido, ou seja, considera-se
uma frota homogênea.
No problema de alocação de frota homogênea, considera-se um grafo, onde os nós são
representados pelas viagens de um intervalo de tempo e o conjunto de arcos representam a
viabilidade de uma viagem ser realizada após outra.
Este problema é formulado como problema de atribuição e resolvido através do algoritmo
húngaro. A função objetivo minimiza a soma dos custos improdutivos relativos a movimentos
de veículos vazios e tempos ociosos.
A solução do problema de alocação de frota homogênea pode ser uma solução inviável para a
solução do problema de alocação de frota, proposto neste trabalho; o número de veículos na
alocação de frota homogênea certamente será menor, pois o veículo que se encontra mais
próximo e com tempo hábil para realizar uma viagem é que será alocado, não sendo
necessário analisar a exigência da viagem em relação ao tipo de veículo; a solução obtida com
a alocação da frota homogênea pode ser considerada como um limite inferior para avaliar a
qualidade da solução obtida pelo método proposto.
5 Análise dos Resultados
Os dados obtidos para este experimento foi fornecido por uma empresa privada que tem o
direito de explorar o transporte de passageiros das linhas de ônibus no sul do Brasil, mais
precisamente linhas entre cidades dos estados de Santa Catarina e Rio Grande do Sul.
O transporte de passageiros se caracteriza por linhas intermunicipais dentro dos dois estados,
totalizando 671 viagens semanais. Nos feriados e vésperas de feriados, há acréscimos de
linhas para algumas localidades, assim como em dias alternados. Também, devido à exigência
do mercado, há acréscimo diário de linhas para algumas localidades em determinados
períodos do ano O número de linhas com vigência anual, acrescidas das linhas com vigência
especial, resultam em 38 linhas.
O plano operacional da empresa para uma semana regular é apresentado na tabela 1 e o
número de linhas e viagens adicionais durante o ano é apresentado na tabela 2.
PERÍODO
ANUAL DOM SEG
Linhas
27
25
Viagens
104
97
VÉSPERA
DIAS
TER QUA QUI SEX SÁB FERIADO FERIADO ALTERNADOS
26
26
29
25
27
17
3
1
98
98
105
95
74
42
4
2
Tabela 1 – Número de linhas e viagens em semana regular
PERÍODO ESPECIAL DOMINGO
Março a
Linhas
2
Dezembro
Viagens
5
Abril a
Outubro
Novembro a
Março
Dezembro a
SÁBADO
2
DIAS ÚTEIS
1
FERIADOS
2
5
9
6
Linhas
1
0
1
0
Viagens
1
0
5
0
Linhas
2
1
1
1
Viagens
5
1
5
4
Linhas
1
1
1
0
6
Fevereiro
Viagens
3
3
15
0
Dezembro a
Março
Linhas
4
4
4
1
Viagens
10
11
54
5
Tabela 2 – Número de linhas e viagens em período especial do ano
As viagens são de três tipos: direta, semidiretas e seccionadas. Viagens diretas não possuem
locais de embarque e desembarque durante seu percurso, apenas paradas de descanso,
obrigatórias por lei, a cada 300 km rodados. Viagens semidiretas têm um local de embarque e
desembarque durante seu percurso, e as viagens seccionadas possuem vários locais de
embarque e desembarque ao longo de seu percurso. Cada viagem exige um tipo de veículo
adequado.
A frota da empresa é composta de 97 veículos, sendo 4 leitos, 48 executivos e 45
convencionais.
Para a implementação do algoritmo utilizou-se um horizonte de planejamento de 4 meses (18
semanas), o que possibilita uma visão futura dos acontecimentos e discussões das soluções
para a tomada de decisão.
A abordagem para se chegar ao parâmetro adequado das penalidades para o algoritmo foi
através de vários testes comparativos entre as soluções obtidas pelo algoritmo proposto de
forma a não violar as restrições; caso essas soluções violem restrições, modificam-se os
parâmetros das penalidades e uma nova solução é obtida; o processo repete-se até não violar
restrições.
A figura 2 representa o histograma de viagens, de um intervalo de tempo de uma semana
(domingo a sábado). Os picos representam os pontos onde o número de viagens diárias que
ocorrem simultaneamente é mais acentuado. È evidente que este é um limite inferior para o
número de veículos necessários para a atribuição de todas as viagens. Neste caso (uma
semana normal), 27 veículos é o número máximo de veículos a serem utilizados
simultaneamente.
30
A
B C
D
F
25
L
I
G
E
H
M
N
J
Viagens
20
15
10
5
0
0
1440
2880
4320
5760
7200
8640
10080
Tempo (minutos)
Figura 2 - Histograma de viagens do período
7
Após executar o algoritmo, resultou um conjunto de viagens sem passageiros, por exemplo,
um ônibus viajando para iniciar uma nova viagem a partir de uma garagem. O histograma de
viagens vazias estão representados na figura 3. Percebe-se que há no máximo 8 viagens sem
passageiros em uma semana regular.
Adicionado as seqüências dos histogramas representados na figura 2 e na figura 3, obtém-se
um número máximo de viagens simultâneas, que não ultrapassam 30 viagens. Conclui-se que
o limite mínimo para o problema de programação da frota, analisado de forma estática é 30
veículos. Em outras palavras, numa situação estática do problema ocorrem no máximo 30
viagens simultâneas. Logo, na hipótese mais simples, seriam necessários 30 veículos para
cobrir as viagens do intervalo e este será um limite inferior absoluto vinculado a alocação de
veículos da frota. É evidente que este é um processo estático, onde não se leva em
consideração para a atribuição da próxima semana, a localização do veículo. Observa-se que
este é um modelo dinâmico de programação da frota. Cada vez que o algoritmo é executado,
situações diferentes ocorrem, uma vez que os veículos possivelmente se encontram em
localidades distintas.
9
8
7
Viagens
6
5
4
3
2
1
0
0
1440
2880
4320
5760
7200
8640
10080
Tempo (minutos)
Figura 3 - Histograma dos movimentos de veículos vazios do período
O algoritmo proposto atribuiu 37 veículos para uma semana regular, onde 32 ônibus são
convencionais, 3 são executivos e 2 são leitos cobrindo todas as viagens do horizonte de
planejamento, respeitando as restrições impostas do problema, como: a não sobreposição de
viagens e a adequação do tipo de veículo às exigências das viagens. Em uma semana com
feriado, houve necessidade de adicionar 7 ônibus convencionais para cobrir todas as viagens.
Este acréscimo de viagens resultou em um pequeno número de viagens atribuído para cada
veículo adicional, mas necessário para cobrir a demanda.
Este número de ônibus alocados não está longe demais do limite inferior absoluto, de 30
veículos. Para comparar a solução obtida pelo método de uma forma mais realista, recorreu-se
ao procedimento de validação. Se não houvesse a exigência de tipos de veículos seriam
8
necessários 35 veículos para cobrir as viagens de uma semana regular e 40 veículos para
cobrir as viagens de uma semana com feriado.
Na tabela 3, apresenta-se um resumo comparativo entre a solução obtida pelo algoritmo
proposto e do limite inferior da frota homogênea, considerando uma semana regular e uma
semana com feriado.
Observa-se que apenas 45% da frota é necessária para cobrir todas as viagens, resultando que
mais da metade da frota torna-se ociosa para a empresa. Em relação a tempos ociosos há no
máximo 4% em relação a movimentos de veículos vazios. Ainda nesta tabela, observa-se que
dos veículos efetivamente alocados na operação, apenas 35% e 32%, respectivamente, para
uma semana regular e para uma semana com feriado, é produtiva, tornando lucro para a
empresa.
Pode-se observar que os resultados obtidos são muito próximos do limite inferior discutido na
seção 4, garantindo que a solução está próxima da solução ótima. A maior discrepância ocorre
em movimentos de veículos vazios, o que é necessário devido a exigência de tipos
diferenciados de veículos para as viagens.
Situação Algoritmo
Veic.
Aloca
dos
Indice Total de Tempo (minutos)
de
Utiliza
ção
Improdutiva
dos
Veic.
s/feriado
Limite
Inferior
35
36%
37
38%
40
41%
44
45%
Taxa de Utilização
Improdutiva
Produtiva
Produtiva
Tempo
Mov.
Tempo
Mov.
Ocioso
Vazio
Ocioso
Vazio
213538
7122
132140
61%
2%
37%
225324
15496
132140
61%
4%
35%
256592
6153
140455
64%
1%
35%
288065
15000
140455
65%
3%
32%
frota
homogênea
Proposto
frota
heterogêne
a
c/feriado
Limite
Inferior
frota
homogênea
Proposto
frota
heterogêne
a
Tabela 3: Resumo dos Resultados
9
6. Conclusões
Nesse trabalho foi apresentado um modelo para a solução do problema de programação da
frota aplicado ao transporte rodiviário regional de passagiros, considerando um horizonte de
planejamento de 18 meses. Tal modelo se presta a aplicação em casos reais, dada sua
eficiência em encontrar a solução de um problema de otimização combinatória em tempo
computacional razoável, através de um método heurístico. Desenvolveu-se um plano
operacioal, cobrindo todas as viagens do horizonte de planejamento, com um tempo total de
processamento de 4 minutos e 36 segundos.
A qualidade das soluções do problema de programação da frota é comprovada para os dados
testados pela proximidade dessas soluções com seus limites inferiores, determinados pela
relaxação de algumas restrições do problema real. A qualidades dos serviços prestados a
comunidade foi mantida, pois toda a programação horária foi cumprida com veiculos
adequados às viagens e houve redução de custos fixos da frota, pois o número de veículos é
significativamente menor que o número total de veiculos disponíveis.
Referências
BAITA, F.; PESENTI, R.; UKOVICH, W. & FAVARETTO, D. A comparison of different solution
approaches to the vehicle scheduling problem in a practical case. Computers and Operations Research, Vol 27,
n. 13, p. 1249-1269, 2000.
BODIN, L.; GOLDEN, B.; ASSAD, A. & BALL, M. Routing and scheduling of vehicles and crews. The State
of the Art. Computers and Operations Research, Vol. 10, n. 2, p. 63-212, 1983.
CEDER, A. & STERN, H. I. Deficit function bus scheduling with deadheading trip insertions for fleet size
reduction. Transportation Science, Vol.15, p. 338-363, 1981.
CHRISTOFIDES, N. & EILON, S. An algorithm for the
Quart, n. 20, p. 309-318,1969.
vehicle dispatching problem. Operations Research
KLIEWER, N.; MELLOULI, T. 7 SUHL, L. A timespace network based exact optimization model for multidepot bus scheduling. European Jornal of Operational Research, n. 175, p. 1616-1627, 2006.
MAYERLE, S. F. Um Sistema de apoio à decisão para o planejamento operacional de empresas de
transporte rodoviário urbano de passageiros. Tese de Doutorado. Programa de Pós-Graduação em Engenharia
de Produção, UFSC, 1996.
RODRIGUES, M. M.; SOUZA, C. C & MOURA, A. V. Vehicle ande crew scheduling for urban bus lines.
European Journal of Operational Research, n. 170, p. 844-862, 2006.
10