APLICAÇÃO E FLEXIBILIZAÇÃO DO METODO DE
GERAÇÃO DE ARCOS ARCGEN PARA A PROGRAMAÇÃO DE
ÔNIBUS DE TRANSPORTE PÚBLICO
Gustavo Peixoto Silva
Departamento de Engenharia de Produção – UFOP
Nicolau D. Fares Gualda
Departamento de Engenharia de Transportes – POLI/USP
Abstract – This work presents partial results obtained in a PhD resource, which explores network
flow algorithms to solve public mass vehicle scheduling problem. The basic problem is solved
through circulation model combined with the arc generation technique, derived from the column
generation approach of the linear programming theory.
The proposed method was applied to a real case, producing extensions to support operational
practices in Brazil. This work briefly presents the basic methodology, explaining in details the
extensions achieved in order to generate alternative vehicle schedules.
Keyword: Vehicle scheduling, network flow algorithms, arc generation.
1
INTRODUÇÃO
Um problema básico para programar a operação de uma frota de ônibus no transporte
coletivo urbano consiste em determinar o número mínimo de veículos necessários para
realizar um dado conjunto de viagens, assim como definir a seqüência das viagens
executadas por cada veículo. Este problema é trivial quando o número de linhas é
reduzido, mas ele se complica à medida que este número aumenta. Para os casos mais
complexos, a utilização de métodos matemáticos pode levar a uma redução no número de
veículos, além de minimizar o custo operacional da frota (Bodin 1983).
Este problema pode ser formulado com a teoria de fluxo em redes de diferentes maneiras.
Para melhor compreensão dos diversos modelos ver Daduna e Paixão (1995), Carraresi e
Gallo (1984) e Bodin et al. (1983). Independente da formulação adotada, o gargalo que
surge na resolução do problema de fluxo subjacente diz respeito ao elevado número de
arcos na rede. Para contornar este problema pode-se empregada a técnica de geração de
arcos, que consiste em inicializar o domínio do problema com um conjunto de arcos com
grande possibilidade de participarem da solução. Posteriormente este conjunto é
incrementado com os arcos com alguma possibilidade de melhorar a solução corrente.
Assim, é possível atingir a otimalidade sem processar a rede toda (Freling et al. 1995).
A metodologia utilizada neste trabalho transforma a formulação de pseudo-designação
proposta por Paixão e Branco (1987) em um problema de circulação que é resolvido com o
algoritmo Out-of-Kilter combinado com a técnica de geração de arcos (Silva e Gualda
2000). Desta forma o problema de programação de veículos pode ser resolvido sem que
haja degeneração no tempo de processamento.
Os objetivos deste trabalho são: i) Aplicar a metodologia de programação de ônibus
urbano apresentada em Silva e Gualda (2000) ao serviço de transporte coletivo
diferenciado em operação na cidade de Santos, denominado “Seletivo” e verificar a
viabilidade operacional da solução. ii) Explorar a operação da empresa a fim de incorporar
ao modelo novos recursos de utilidade prática.
Este trabalho conta ainda com quatro seções: na seção seguinte são relatadas as práticas
operacionais e características do problema estudado. A seção três mostra os diversos
experimentos realizados, com os resultados encontrados. Finalmente são apresentadas as
conclusões e continuidade do trabalho.
2
SITUAÇÃO ATUAL
O sistema de transporte “Seletivo” de Santos é um serviço diferenciado por apresentar as
seguintes características: a) os veículos são de tamanho reduzido (28 assentos) e equipados
com ar condicionado, b) os passageiros só viajam sentados, c) o motorista também
desempenha a função de cobrador, d) os veículos cumprem suas tabelas de horários com
rigidez, e d) o preço da passagem é mais alto do que no transporte coletivo comum. O
serviço é composto de oito linhas circulares, partido de três terminais distribuídos na
cidade de Santos. A operação do serviço em curso apresenta as seguintes características:
•
•
•
•
Para cada linha é definido o número de veículos que nela atua, tendo em vista a
demanda na linha e o tamanho da frota disponível.
Atualmente cada veículo só opera em uma determinada linha.
A freqüência de partida de cada linha é calculada dividindo-se o tempo de duração da
viagem pelo número de veículos que atuarão na linha. São feitos os arredondamentos
necessários para facilitar a operação.
Ao final de cada viagem é dado 10 minutos para o descanso do motorista.
Analisando as características operacionais do serviço de transporte pode-se concluir que:
•
•
•
•
Não é considerada a variação da demanda nas linhas, visto que a freqüência é constante
no decorrer do dia, computado o tempo de ponto.
Ocorre uma super-utilização dos veículos no período de pico e uma sub-utilização no
período de entre-pico.
Não existe retorno de veículos à garagem no período de entre-pico.
Este serviço segue um padrão operacional de linhas de baixa demanda.
Este trabalho explora as diversas possibilidades de flexibilização no sistema, gerando
soluções que variam tanto em custo capital quanto na dificuldade de sua implementação.
As programações apresentadas representam os principais resultados alcançados e incluem
apenas aquelas que mais aproximam-se da situação atual.
3
ESTUDOS REALIZADOS
Foram realizados dois estudos diferentes tendo em vista o cumprimento rigoroso das
viagens programadas ou a relaxação desta condição, gerando programações que omitem
algumas viagens para reduzir a frota em operação.
3.1
PROGRAMAÇÕES QUE REALIZAM TODAS AS VIAGENS PLANEJADAS
As programações geradas nesta etapa executam todas as viagens programadas, respeitando
os seus respectivos horários e locais de partida e de chegada. Os dados básicos que
alimentaram o sistema foram: o total de viagens programadas, os horários e locais de
início, horários e locais de término das viagem, o tempo de viagem entre os terminais, e o
tempo de viagem entre os terminais e a garagem, estando o veículo fora de operação.
1
Também é informado o tempo mínimo de permanência na garagem, caso o veículo retorne
a ela no período de entre-pico. A prática mostra que um período mínimo da ordem de 30
minutos de estacionamento temporário na garagem é razoável (Kwan e Rahin 1999).
3.1.1
Com restrição de troca de linhas
Nestes casos não foi permitido que os veículos atuassem em mais de uma linha durante a
operação. Quanto ao descanso do motorista foram testadas duas situações diferentes.
3.1.1.1 Com tempo de descanso para o motorista
Considerando um período de 10 minutos ao final de cada viagem para o descanso do
motorista, foi gerada uma programação com as seguintes características:
Frota
34
Tempo total de viagens vazias
31:50 hh:mm
Tempo livre nos terminais
00:00 hh:mm
Retornos à garagem
0
Tabela 2: Programação sem troca de linha e com tempo de descanso para o motorista.
Esta programação tem as mesmas características da situação atual e foi gerada para
verificar a validade do modelo. Foi verificado que a totalidade das viagens não apresenta
folga no terminal além do tempo de descanso do motorista.
3.1.1.2 Sem garantia de tempo de descanso para o motorista
Se não for assegurado o tempo mínimo de 10 minutos ao final de cada viagem para o
descanso do motorista, a programação ótima gerada pelo modelo apresenta as seguintes
características:
Frota
32
Tempo total de viagens vazias
30:50 hh:mm
Tempo livre nos terminais
44:50 hh:mm
Retornos à garagem
0
Tabela 3: Programação sem troca de linha nem garantia do tempo de descanso do
motorista.
Embora esta programação não garanta o tempo de descanso, ela conta com 44 horas e 50
mínimo livres nos terminais para criar condições operacionais aos motoristas. Segundo o
histograma de folga, 200 viagens não apresentam folga no terminal, o que impossibilita o
descanso do motorista. No restante das viagens é possível acomodar o descanso do
motorista, sendo que em 205 viagens o tempo livre no terminal é de 10 minutos.
3.1.2
Com liberdade de troca de linhas durante a operação
Esta é uma situação de maior flexibilidade onde um veículo pode realizar viagens de
diferentes linhas em um mesmo dia de trabalho. No entanto o sistema teve seus parâmetros
ajustados para que não houvesse muita troca de linha, mantendo ao máximo as
características da programação atual.
Assim como no caso anterior, foram testadas duas situações diferentes em função do
descanso do motorista, as quais são apresentadas abaixo.
3.1.2.1 Com tempo de descanso para o motorista
Uma vez garantido o tempo mínimo de 10 minutos ao final de cada viagem para o
descanso do motorista, a programação gerada conta com as seguintes características:
Frota Tempo total de viagens vazias Tempo livre nos terminais
34
31:50 hh:mm
00:00 hh:mm
Obs: Nesta programação os ônibus atuam em média em 3 linhas diferentes.
Retornos à garagem
0
Tabela 4: Programação com troca de linha e com tempo de descanso para o motorista.
2
Neste caso, embora seja garantido o descanso do motorista, não existe redução no número
de ônibus, ocorrendo ainda a desvantagem da troca de linhas dos veículos durante a
operação.
3.1.2.2 Sem garantia de tempo de descanso para o motorista
A programação apresentada abaixo não assegura o tempo mínimo para o descanso do
motorista e suas principais características são:
Frota Tempo total de viagens vazias Tempo livre nos terminais Retornos à garagem
32
32:40 hh:mm
32:20 hh:mm
1 (com 02:55 estacionado)
Obs: Nesta programação os ônibus atuam em média em 4 linhas diferentes.
Tabela 5: Programação com troca de linha e sem tempo de descanso para o motorista.
Embora ocorra uma redução na frota em operação, programações deste tipo são pouco
atraentes por não permitir o descanso adequado ao motorista em grande parte das viagens.
3.1.3
Conclusão
As situações que garantem o descanso do motorista (3.1.1.1 e 3.1.2.1) coincidem com a
programação atual, independentemente de haver flexibilização quanto à permanência dos
veículos nas suas linhas. Isto se deve pelo fato do intervalo entre as partidas ter sido
calculado dividindo-se o tempo de viagem pelo número desejado de veículos em operação
na respectivas linha.
Nos casos em que o descanso do motorista não foi imposto ao modelo (3.1.1.2 e 3.1.2.2)
houve uma diminuição da frota em operação. Em contra partida, surgem os problemas de
alocação e treinamento dos motoristas.
Logo, é observado que as programações geradas nesta seção que reduzem a dimensão da
frota levam ao problema de programação dos motoristas, o qual é de grande complexidade.
Surgiu então a necessidade de permitir a supressão de algumas viagens para que novos
quadros de interesse fossem produzidos.
3.2
PROGRAMAÇÕES QUE OMITEM ALGUMAS VIAGENS PLANEJADAS
Foram testadas outras alternativas para o planejamento das linhas do sistema de transporte
estudado. Assim, o modelo foi adaptado para possibilitar a não realização de algumas
viagens, caso esta omissão levasse a uma economia na operação do sistema.
A omissão de algumas viagens em função da redução a frota está associada à relação
custo/benefício no sistema como um todo. Neste sentido, viagens com maior custo são
consideradas mais importantes do que viagens com menor custo de omissão.
Todas as programações geradas neste subseção contemplam o descanso do motorista, de
10 minutos após o cumprimento de cada viagem, como na situação atual.
A seguir são descritos os diferentes custos associados à omissão das viagens, juntamente
com os resultados proporcionados pelo modelo.
3.2.1
Custo por omissão constante para todas as viagens
Inicialmente foi considerado um custo de omissão constante para todas as viagens. Desta
forma foram suprimidas viagens que levam à economia de veículos, independentemente
das suas características de demanda de passageiros ou de suas inter-relações com as outras
viagens da mesma linha. Logo, o custo de omissão de uma viagem é dado por:
Coi = K para cada viagem i
(1)
3
Onde K é uma constante adimencional manipulada pelo usuário para controlar o número de
viagens suprimidas na programação.
Considerando a operação onde os veículos podem realizar viagens em diferentes linhas
durante o dia de trabalho, a programação ótima tem as características que seguem.
Ao assumir um custo de omissão constante para todas as viagens, a retirada de 16 viagens
da programação, reduziu em dois o número de veículos em operação, sendo um veículo da
linha 206 e outro da linha 207. Algumas viagens destas linhas foram incorporadas a dois
veículos da linha 202. Por outro lado, as viagens suprimidas estão distribuídas ao longo do
dia, abrangendo períodos de pico e fora do pico. O mesmo resultado foi gerado tendo em
vista o custo de omissão dado em função da taxa de ocupação dos veículos (1o da tabela 7)
porém, neste caso surgem outras programações de interesse prático.
Total de veículos:
32 ônibus
Viagens omitidas:
8 viagens da linha 206 (redução de 1 veículo)
8 viagens da linha 207 (redução de 1 veículo)
Total de retornos à garagem:
0
Obs: apenas 2 ônibus operam em 2 linhas diferentes, realizando no final do período um bloco de
quatro viagens em uma segunda linha.
Tabela 6: Programação com custo constante por omissão de viagem.
3.2.2
Custo por omissão dependente da taxa de ocupação do veículo e fator
multiplicativo
Para serem considerados fatores da demanda de passageiros relativos às viagens, foi
associado ao custo de omissão informações referentes à taxa de ocupação do veículo. O
período de operação de cada linha foi dividido em intervalos caracterizados pela demanda
tais como: pré pico, pico da manhã, entre pico, etc. A empresa forneceu, para cada
intervalo, a taxa de ocupação do veículo. Esta taxa, que reflete a demanda na linha, foi
incorporada ao custo de omissão da viagem. Foi utilizado ainda, um multiplicador para
calibrar os custos e regular o número de viagens omitidas, como pode ser verificado na
expressão abaixo.
Coi = K×Di, para cada viagem i
(2)
Onde K tem a mesma interpretação da expressão (1) e Di representa a taxa média de
ocupação do veículo para a viagem i.
Consideração da demanda nos custos de omissão das viagens, não foi possível que o
modelo gerasse programações alternativas sem que houvesse alguma troca de linha durante
a operação. Portanto, as programações apresentadas a seguir realizam pelo menos uma
troca de linha.
As duas primeiras programações na tabela 7 utilizam 32 veículos omitindo 16 e 17 viagens
respectivamente. Na primeira programação apenas dois veículos operam em duas linhas
diferentes, realizando um bloco de 4 viagens no final do período. No caso da segunda
programação quatro veículos atuam em duas linhas diferentes, sempre em blocos de 3 a 4
viagens no início e final do período. Esta programação suprime 17 viagens e portanto uma
a mais do que a programação anterior. A vantagem é que as viagens não realizadas estão
distribuídas em períodos fora do horário de pico das respectivas linhas.
As duas últimas programações na tabela 7 utilizam 33 veículos omitindo em ambos os
casos 8 viagens. Na terceira programação todas as viagens não realizadas pertencem à
4
linha 206, abrangem horários de pico e fora do pico, e um único veículo da frota atua em
linhas diferentes. Este veículo realiza um bloco de 4 viagens na linha secundária no final
do período. Na última programação apresentada acima, as viagens não realizadas
pertencem a duas linhas diferentes, 206 e 207, não se encontram em horários de pico, e
dois veículos atuam em linhas diferentes, realizando blocos de viagens na linha secundária
no início e final do período.
Veículos com troca de linha
Número. veículos /
Linha/Viagens omitidas
Total de omissões
- período das viagens
32 / 16
206/8 viagens – entre 202
07:30 e 17:25.
202
207/8 viagens – entre
07:50 e 17:45.
206 × 4
fim período
207 × 4
fim período
208/3 viagens – entre 201
07:05 e 09:45.
202
207/4 viagens – entre
207
07:50 e 12:05.
208
206/10 viagens – entre
11:05 e 18:10.
206 × 3
fim período
206 × 4
fim período
206 × 4
início período
206 × 3
início período
206/8 viagens – entre 202
07:30 e 17:25
206 × 4
fim período
207/4 viagens – entre 202
7:50 e 12:05.
207
206/4 viagens – entre
13:10 e 17:25.
206 × 4
fim período
206 × 4
início período
Programação 1
32 / 17
Programação 2
33 / 8
Programação 3
33 / 8
Programação 4
Linha
principal
L. secundária× Período viagens
secundárias
no viagens
Tabela 7: Programações com custo por omissão dado em função da taxa média de
ocupação dos veículos por viagem.
3.2.3
Custo por omissão dependente da taxa de ocupação do veículo, do intervalo
até a próxima viagem e fator multiplicativo
Outro fator que reflete a qualidade de um serviço de transporte público é o intervalo entre
as partidas dos veículos de uma dada linha. Se por um lado o intervalo mais amplo entre
duas partidas garante uma alta taxa de ocupação do veículo, por outro lado ele caracteriza
uma escassez de opções para o usuário. Este fator foi incorporado ao modelo atribuindo ao
custo de omissão de cada viagem a expressão abaixo, ou seja, o produto entre a taxa de
ocupação do veículo e o intervalo de tempo até a próxima partida, além do fator
multiplicativo.
Coi = K×Di×Ti para cada viagem i
(3)
Onde K e Di têm a mesma interpretação da expressão (2) e Ti é o intervalo de tempo até a
próxima partida da linha a que pertence a viagem i.
A tabela abaixo mostra as programações resultantes tendo em vista os custos expressos em
(3). Foram apresentadas apenas aquelas que mais se aproximam da programação corrente,
embora em todas as soluções ocorra troca de linha por parte dos veículos. Somente desta
forma foi possível reduzir o número de veículos em operação.
5
Número. Veículos /
Total omissões
32 / 19
Programação 1
33 / 9
Programação 2
Linha/
omitidas
Veículos com troca de linha
Viagens
- período das viagens
Linha
principal
L. secundária Período viagens
× no viagens secundárias
208/9 viagens - entre 208
07:05 e 12:25.
202
204/10 viagens - entre
208
13:05 e 18:10.
204 × 6
Início período
208 × 1
Início período
204 × 5
Início período
208/4 viagens - entre 202
08:00 e 12:00.
208
204/5 viagens - entre
13:05 e 17:45.
208 × 1
Início período
204 × 5
Início período
Tabela 8: Programações que consideram a taxa de ocupação do veículo e o intervalo até a
próxima partida na omissão de uma viagem.
Para reduzir a frota ao mesmo número de veículos (32 e 33) das programações
apresentadas na tabela 7, as programações desta seção suprimiram um número maior de
viagens. No primeiro caso, para uma frota de 32 ônibus, foi necessário suprimir um total
de 19 viagens e portanto 3 e 2 viagens a mais do que nas duas primeiras programações da
tabela 2. Por outro lado 3 veículos que fazem troca de linhas correspondendo à média dos
casos anteriores.
4
CONCLUSÕES
A possibilidade de não executar todas as viagens programadas permite gerar programações
alternativas com diferentes graus de redução na frota. Os resultados mais interessantes do
ponto de vista operacional são aqueles que refletem a taxa de ocupação dos veículos e os
que associam a taxa de ocupação e o intervalo até a próxima viagem para definir o custo de
omissão da viagem.
A tabela 7 apresenta dois grupos de programações com a mesma taxa de redução da frota,
porém com diferentes características operacionais. Enquanto na primeira e terceira
programações algumas das viagens omitidas pertencem ao horário de pico das respectivas
linhas, as viagens não realizadas na segunda e quarta programações pertencem ao horário
de entre pico. Em contrapartida, existe um número menor de veículos operando em linhas
diferentes na primeira e terceira programações do que na segunda e quarta programações.
Embora os resultados apresentados na tabela 8 suprimam algumas viagens a mais do que
nos casos anteriores, para as mesmas dimensões da frota (32 e 33 veículos), adotando-se a
função de custo de omissão de viagens na expressão (3) foi possível gerar outras
alternativas de programação. A primeira e segunda programações da tabela 8 podem ser
comparadas à segunda e quarta programações da tabela 7, pois ambos os pares têm a
mesma frota e todas as viagens omitidas estão fora do horário de pico. A diferença
qualitativa entre estes resultados, além do número de viagens omitidas, está nas linhas que
sofrem redução de viagem, no número de veículos que atuam em linhas diferentes e o
número viagens realizadas na linha secundária.
Comparando as programações com 32 veículos pode-se observar que: a) existe uma
interseção entre elas de apenas três viagens da linha 208, b) 4 e 3 veículos atuam em linhas
diferentes nas programações da tabela 7 e tabela 8 respectivamente e c) são realizadas 14 e
12 viagens nas linhas secundárias nas
programações da tabela 7 e tabela 8
respectivamente. Para as programações com 33 veículos observa-se que: a) as
6
programações omitem viagens pertencem a linhas distintas
viagens nas linhas secundárias nas programações da tabela 7
Logo, são gerados resultados alternativos e de certa forma
mesma dimensão da frota, propiciando liberdade de escolha
transporte.
e b) são realizadas 8 e 6
e tabela 8 respectivamente.
complementares para uma
ao operador do sistema de
Como continuidade do trabalho pretende-se permitir que o modelo de programação faça
também o planejamento de partidas das linhas. Uma descrição da metodologia adotada na
etapa subsequente se encontra abaixo.
5
CONTINUAÇÃO DO TRABALHO
O que se pretende na continuidade deste estudo é que o modelo de otimização determine a
tabela de horários de forma integrada com a programação dos veículos. Assim, é gerado
um conjunto maior de viagens, a partir do qual é escolhido um subconjunto de viagens a
ser executado, associado à minimização da frota em operação. Este processo associa o
planejamento das linhas com a otimização da programações, executando ambas ao mesmo
tempo.
5.1
MÉTODO INTEGRADO DE PLANEJAMENTO DAS LINHAS E VEÍCULOS
Inicialmente o dia de trabalho é dividido em tantos intervalos quantos forem necessários
para se obter uma caracterização da curva de demanda em cada linha. Para cada intervalo
são geradas viagens em subintervalos constantes e suficientemente pequeno, de tal forma
que se tenha uma discretização do tempo com suas respectivas viagens. O usuário informa
o número mínimo de viagens realizadas por intervalo para cada linha e o modelo
matemático baseado em Relaxação Lagrangeana, determina as viagens a serem realizadas.
Desta forma é gerado um planejamento cuja programação resultante satisfaz às condições
mínimas impostas pela usuário, maximizando a utilização do veículo e minimizando o
custo operacional da frota como um todo. Esta esta flexibilização já foi implementada,
porém o método ainda não foi avaliado com dados reais.
6
BIBLIOGRAFIA
Bodin, L.; B. Golden; A. Assad e M. Ball. (1983) Routing and scheduling of vehicles and
crews: The state of the art. Computers and Operations Research, v 10, p. 63-211.
Carraresi, P. e G. Gallo (1984) Network models for vehicle and crew scheduling.
European Journal of Operational Research, v 16, p. 139-151.
Daduna, J. R. e J. M. P. Paixão (1995) Vehicle scheduling for public mass transport- an
overview. In: Daduna, J. R.; I. Branco e J. M. P. Paixão (eds.) Computer-Aided
Transit Scheduling, Lectures Notes in Economics and Mathemaitcal Systems.
Springer Verlag, Berlin, Alemanha.
Freling, R.; J. M. P. Paixão e A. P. M. Wagelmans (1995) Models and Algorithms for
Vehicle
Scheduling.
Aviable
via
WWW
at
http://kaa.cs.few.eur.nl/few/people/freling/.
Kwan, R. K. e M. A. Rahin (1999) Object oriented bus scheduling - the BOOST system. A
ser publicado em: Computer Aided Scheduling of Public Transport ed. N. H. M.
Wilson. Springer, Berlin.
Paixão, J. e L. Branco (1987) A quasi-assignment algorithm for bus-scheduling, Networks,
v 17, p. 249-269.
Silva, G. P. e N. F. D. Gualda (2000) Uma algoritmo de Geração de Arcos para o Problema
de Programação de Veículos”. TRANSPORTES, v 8 (1) p. 35-54.
7