Download PDF
ads:
HOMERO FERNANDES OLIVEIRA
DESENVOLVIMENTO DE UM SISTEMA INFORMATIZADO
PARA DETERMINAR O ESPAÇAMENTO ÓTIMO ENTRE
PONTOS DE PARADA DE TRANSPORTE COLETIVO
Tese apresentada ao Programa de Pós-
Graduação em Engenharia de Produção e
Sistemas – Área de Concentração: Transporte
e Logística da Universidade Federal de Santa
Catarina, como requisito à qualificação para a
obtenção do título de Doutor em Engenharia
de Produção.
Orientadora: Profa. Dra. Mirian Buss
Gonçalves
FLORIANÓPOLIS
27 de fevereiro de 2008
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
ii
TERMO DE APROVAÇÃO
HOMERO FERNANDES OLIVEIRA
DESENVOLVIMENTO DE UM SISTEMA INFORMATIZADO PARA
DETERMINAR O ESPAÇAMENTO ÓTIMO ENTRE PONTOS DE PARADA DE
TRANSPORTE COLETIVO
Tese apresentada como requisito para qualificação para obtenção do grau de Doutor no
Curso de Pós-Graduação em Engenharia de Produção e Sistemas – Área de
Concentração: Transportes e Logística, Universidade Federal de Santa Catarina, pela
seguinte banca examinadora:
__________________________________
Prof. Antônio Sérgio Coelho, Dr.
Coordenador
________________________________ __________________________________
Profa. Mirian Buss Gonçalves, Dra. Prof. Antônio Galvão N. Novaes, Dr.
Programa de Pós Graduação em Programa de Pós Graduação em
Engenharia de Produção, UFSC Engenharia de Produção, UFSC
Orientadora Co-orientador
________________________________ __________________________________
Prof. Edson Tadeu Bez, Dr. Prof. José Eduardo Souza de Cursi
Programa de Pós Graduação em Laboratoire de Mécanique de Rouen
Engenharia de Produção, UFSC INSA – Rouen - França
Moderador Co-orientador e Examinador Externo
________________________________ __________________________________
Prof. João Carlos Souza, Dr. Prof. Sérgio Fernando Mayerle, Dr
Departamento de Arquitetura e Programa de Pós Graduação em
Urbanismo, UFSC Engenharia de Produção, UFSC
_________________________________
Prof. Orlando Strambi, Dr.
Escola Politécnica
Universidade de São Paulo
Examinador Externo
Florianópolis
27 de fevereiro de 2008
ads:
iii
Este trabalho é dedicado à minha esposa Luciana e
aos meus filhos Hélio e Henrique pelo apoio e
paciência durante toda a sua execução e por serem
a razão de tudo na minha vida.
iv
AGRADECIMENTOS
Agradeço inicialmente a DEUS, por ter me proporcionado condições para alcançar este
momento em minha vida.
Aos meus pais, por terem me dado a vida e terem se esforçado ao máximo pela minha
educação.
À Profa. Mirian Buss Gonçalves por me receber como orientando e pela sua dedicação e
esforço.
Ao meu co-orientador Prof.
Antônio Galvão N. Novaes pelas idéias e pelas experiências
a mim apresentadas.
À Prof. Débora Silva Lobo pela apoio prestado durante esta jornada.
Ao meu co-orientador Prof. José Eduardo Souza de Cursi, pela sua orientação e pela acolhida
na cidade de Rouen.
Ao Prof. Edson Tadeu Bez pelo seu apoio quando precisei de socorro.
Ao Prof. Rui Rossi dos Santos que muito me auxiliou no início dos trabalhos.
À funcionária Sonia Lemanski da Unioeste pela competência e pelo auxílio durante o meu
afastamento.
Ao pessoal do Pronex, em especial à Helena, pelo seu apoio e amizade.
Ao pessoal do LABTRANS pela amizade no curto espaço de tempo em que estivemos juntos.
À Universidade Estadual do Oeste do Paraná por ter me proporcionado esta oportunidade de
qualificação profissional.
À CAPES e ao CNPQ pelo apoio financeiro durante o curso.
v
SUMÁRIO
TERMO DE APROVAÇÃO ................................................................................................................................ii
AGRADECIMENTOS.........................................................................................................................................iv
SUMÁRIO.............................................................................................................................................................. v
LISTA DE FIGURAS .........................................................................................................................................vii
LISTA DE TABELAS........................................................................................................................................viii
RESUMO .............................................................................................................................................................. ix
ABSTRACT ........................................................................................................................................................... x
1
INTRODUÇÃO ............................................................................................................................................. 1
1.1
Problema.................................................................................................................................................. 2
1.2
Objetivo Geral......................................................................................................................................... 3
1.2.1
Objetivos Específicos..................................................................................................................... 3
1.3
Limitações do Trabalho.......................................................................................................................... 4
1.4
Estrutura do Trabalho............................................................................................................................ 5
2
REVISÃO DA LITERATURA..................................................................................................................... 6
2.1
Regulamentações Existentes no Mundo ................................................................................................ 8
2.2
Regulamentações Existentes no Brasil ................................................................................................ 10
2.3
Modelos de Otimização......................................................................................................................... 11
2.4
Estudo de Caso 1 ................................................................................................................................... 13
2.4.1
Aplicação do Modelo ................................................................................................................... 16
2.5
Estudo de Caso 2 ................................................................................................................................... 17
2.5.1
Situação 1: O espaçamento é constante ao longo da linha e se mantém constante em todas as
linhas 21
2.5.2
Situação 2: O espaçamento é constante ao longo de uma linha, mas pode variar de uma
linha para outra........................................................................................................................................... 21
2.5.3
Situação 3: Considera-se que a distribuição de demanda pode variar entre rotas e ao longo
de cada rota.................................................................................................................................................. 22
2.5.4
Conclusões do Estudo de Kuah e Perl (1988) ............................................................................ 23
2.6
Estudo de Caso 3 ................................................................................................................................... 23
2.7
Estudo de Caso 4 ................................................................................................................................... 27
2.8
Estudo de Caso 5 ................................................................................................................................... 30
2.9
Considerações Finais............................................................................................................................. 38
3
DIAGRAMA DE VORONOI ..................................................................................................................... 40
3.1
Histórico................................................................................................................................................. 40
3.2
Considerações Iniciais........................................................................................................................... 41
3.3
Definições............................................................................................................................................... 43
3.3.1
Diagrama de Voronoi .................................................................................................................. 43
3.4
Triangulação de Delaunay.................................................................................................................... 48
3.4.1
Definição Matemática da Triangulação de Delaunay............................................................... 50
3.5
Propriedades Básicas ............................................................................................................................ 53
3.5.1
Diagrama de Voronoi .................................................................................................................. 53
3.5.2
Triangulação de Delaunay .......................................................................................................... 55
3.6
Generalizações do Diagrama de Voronoi............................................................................................ 56
3.6.1
Diagrama de Voronoi Ponderado............................................................................................... 56
3.6.2
Diagrama de Voronoi Ponderado por Multiplicação ............................................................... 57
3.6.3
Diagrama de Voronoi Ponderado por Adição........................................................................... 59
3.7
Considerações Finais............................................................................................................................. 60
4
PROGRAMAÇÃO NÃO-LINEAR............................................................................................................ 62
4.1
O Problema da Programação Não Linear .......................................................................................... 62
4.1.1
Condições de Otimalidade .......................................................................................................... 63
4.1.2
Definição de Convexidade........................................................................................................... 64
4.1.3
Funções Convexas Diferenciáveis............................................................................................... 65
4.2
Métodos de Solução de Problemas de Programação Não Linear...................................................... 65
4.2.1
Método do Gradiente................................................................................................................... 66
4.2.2
Método das Direções Conjugadas (Gradiente Conjugado)...................................................... 67
4.2.3
Método Davidon-Fletcher-Powell............................................................................................... 68
4.2.4
Determinação do Tamanho do Deslocamento........................................................................... 69
4.2.5
Método Simulated Annealing (Metrópolis) ............................................................................... 72
4.2.6
Método Numérico para o Cálculo da Derivada ........................................................................ 73
4.3
Considerações Finais............................................................................................................................. 74
5
DEFINIÇÃO DO PROBLEMA ................................................................................................................. 75
5.1
Município de São Paulo ........................................................................................................................ 75
vi
5.1.1
O Transporte Coletivo em São Paulo......................................................................................... 76
5.2
Linha 4 do Metrô de São Paulo............................................................................................................ 77
5.3
Linha Alimentadora da Linha 4 do Metrô de São Paulo................................................................... 78
5.3.1
Modelo Matemático..................................................................................................................... 80
5.4
Linha 5108-10 – Jd. Celeste / Parque Dom Pedro II .......................................................................... 86
5.4.1
Modelo Matemático..................................................................................................................... 88
5.5
Considerações sobre a Densidade Demográfica da Região de Abrangência.................................... 91
5.6
Metodologia para o Cálculo dos Valores............................................................................................. 92
6
RESULTADOS COMPUTACIONAIS ..................................................................................................... 94
6.1
Desenvolvimento das Ferramentas Computacionais.......................................................................... 94
6.2
Teste das Ferramentas Computacionais ............................................................................................. 95
6.3
Operação do Sistema para a Linha Alimentadora............................................................................. 98
6.3.1
Funcionamento do Programa ................................................................................................... 103
6.3.2
Resultados Obtidos.................................................................................................................... 104
6.4
Operação do Sistema para a Linha 5108........................................................................................... 108
6.5
Considerações sobre os Resultados.................................................................................................... 114
7
CONCLUSÕES E RECOMENDAÇÕES................................................................................................ 116
7.1
Conclusões............................................................................................................................................ 116
7.2
Recomendações e Trabalhos Futuros................................................................................................ 117
REFERÊNCIAS BIBLIOGRÁFICAS............................................................................................................. 118
ANEXO 1 ........................................................................................................................................................... 123
ANEXO 2 ........................................................................................................................................................... 127
ANEXO 3 ........................................................................................................................................................... 128
ANEXO 4 ........................................................................................................................................................... 129
ANEXO 5 ........................................................................................................................................................... 152
ANEXO 6 ........................................................................................................................................................... 154
ANEXO 7 ........................................................................................................................................................... 155
ANEXO 8 ........................................................................................................................................................... 156
vii
LISTA DE FIGURAS
FIGURA 2.1 DIAGRAMA DEMONSTRANDO AS FASES DE ACELERAÇÃO E DESACELERAÇÃO ..... 15
FIGURA 2.2: GEOMETRIA DA ÁREA ANALISADA...................................................................................... 18
FIGURA 2.3 – DISTÂNCIA MÉDIA DE ACESSOS POR NÚMERO DE PARADAS ..................................... 27
FIGURA 2.4 – DESLOCAMENTO DO USUÁRIO ATÉ A LINHA DO ÔNIBUS............................................ 28
FIGURA 2.5 – DESLOCAMENTO DO USUÁRIO NA LINHA DO ÔNIBUS.................................................. 28
FIGURA 2.6 – REGIÃO URBANA SERVIDA POR UMA LINHA DE ÔNIBUS E METRÔ .......................... 31
FIGURA 2.7 – LOCALIZAÇÃO DAS ESTAÇÕES CALCULADAS PELO MODELO ................................... 34
FIGURA 2.8 – NOVO DIAGRAMA DE VORONOI CALCULADO................................................................. 36
FIGURA 2.9 – NOVO DIAGRAMA DE VORONOI CALCULADO NA REGIÃO .......................................... 38
FIGURA 3.1: LE TRAIT DE LA LUMIERE ....................................................................................................... 40
FIGURA 3.2: DIAGRAMA DE VORONOI......................................................................................................... 42
FIGURA 3.3: DIAGRAMA ORDINÁRIO DE VORONOI NO PLANO ............................................................ 45
FIGURA 3.4: DIAGRAMA DE VORONOI DEGENERADO ............................................................................ 45
FIGURA 3.5: DIAGRAMA DE VORONOI COM BARREIRAS ....................................................................... 47
FIGURA 3.6: TRIANGULAÇÃO DE DELAUNAY ........................................................................................... 48
FIGURA 3.7: PRÉ-TRIANGULAÇÃO DE DELAUNAY .................................................................................. 49
FIGURA 3.8: TRIANGULAÇÃO DE DELAUNAY OBTIDAS DA FIGURA 3.4 ............................................ 49
FIGURA 3.9: CONSTRUÇÃO DE UMA TRIANGULAÇÃO DE DELAUNAY............................................... 52
FIGURA 3.10: DIAGRAMA DE VORONOI E TRIANGULAÇÃO DE DELAUNAY ..................................... 52
FIGURA 3.11: TRIANGULAÇÃO DE DELAUNAY ......................................................................................... 53
FIGURA 3.12: DIAGRAMA DE VORONOI PONDERADO POR MULTIPLICAÇÃO................................... 58
FIGURA 3.13: DIAGRAMA DE VORONOI PONDERADO POR ADIÇÃO.................................................... 60
FIGURA 4.1: ALGORITMO SIMULATED ANNEALING................................................................................ 72
FIGURA 4.2: ALGORITMO PARA CÁLCULO NUMÉRICO DA DERIVADA .............................................. 74
FIGURA 5.1: MAPA DA LINHA 4 DO METRO DE SÃO PAULO COM A ESTAÇÃO ESCOLHIDA.......... 78
FIGURA 5.2: ESQUEMA DAS LINHAS DE ÔNIBUS EM RELAÇÃO À LINHA DO METRÔ..................... 79
FIGURA 5.3: TRAÇADO DA LINHA ALIMENTADORA................................................................................ 80
FIGURA 5.4: GEOMETRIA DA ÁREA DE SERVIÇO...................................................................................... 81
FIGURA 5.5: ÁREA DE ABRANGÊNCIA DE UM USUÁRIO......................................................................... 85
FIGURA 5.6: ARESTAS DOS DIAGRAMAS DE VORONOI REFERENTES ÀS PARADAS DE ÔNIBUS . 86
FIGURA 5.7: TRAÇADO DA LINHA 5108-10 .................................................................................................. 87
FIGURA 5.8: DADOS GERAIS DA LINHA 5108-10......................................................................................... 88
FIGURA 5.9: GEOMETRIA DA ÁREA DE SERVIÇO...................................................................................... 89
FIGURA 5.10: MODELO ESQUEMÁTICO DO COMPORTAMENTO DO USUÁRIO .................................. 90
FIGURA 5.11: MODELO ESQUEMÁTICO DA VARIAÇÃO DA DENSIDADE DEMOGRÁFICA .............. 92
FIGURA 6.1: TELA INICIAL DO SISTEMA PARA A RESOLUÇÃO DE PROBLEMAS DE
PROGRAMAÇÃO NÃO-LINEAR .............................................................................................................. 95
FIGURA 6.2: TEMPO DE PROCESSAMENTO PARA A FUNÇÃO DAVIS ................................................... 96
FIGURA 6.3: TEMPO DE PROCESSAMENTO PARA A FUNÇÃO SCHWEFEL .......................................... 97
FIGURA 6.4: TEMPO DE PROCESSAMENTO PARA A FUNÇÃO ACKLEY ............................................... 98
FIGURA 6.5: ÁREA DE ABRANGENCIA DA LINHA COM AS DIVISÕES DOS BAIRROS..................... 101
FIGURA 6.6: MODELO ESQUEMÁTICO DA ÁREA COM ALGUNS PONTOS E COORDENADAS ....... 102
FIGURA 6.7: TELA INICIAL DO PROGRAMA.............................................................................................. 103
FIGURA 6.8: TEMPO MÉDIO DE VIAGEM POR USUÁRIO POR NÚMERO DE PARADAS ................... 105
FIGURA 6.9: LOCALIZAÇÃO DAS PARADAS SOBRE A LINHA DE ÔNIBUS ........................................ 107
FIGURA 6.10: LINHA 5108 COM SUA ÁREA DE ABRANGÊNCIA............................................................ 109
FIGURA 6.11: MODELO ESQUEMÁTICO DA LINHA E REGIÃO .............................................................. 110
FIGURA 6.12: TEMPO MÉDIO DE VIAGEM POR USUÁRIO...................................................................... 111
FIGURA 6.13: TEMPO MÉDIO DE VIAGEM POR USUÁRIO...................................................................... 112
FIGURA 6.14: RESULTADO FINAL DA LINHA 5108 COM DIAGRAMA DE VORONOI ........................ 113
viii
LISTA DE TABELAS
TABELA 2.1 – ÍNDICE DE EFICIÊNCIA POR TIPO DE VEÍCULO .................................................................7
TABELA 2.2 – ÍNDICES RELATIVOS POR TIPO DE VEÍCULO E POR PASSAGEIRO................................ 7
TABELA 2.3 – EXEMPLOS DE NORMAS DE ESPAÇAMENTO EXISTENTES NOS EUA........................... 9
TABELA 2.4 – NORMAS DE ESPAÇAMENTO EXISTENTES NA EUROPA ................................................. 9
TABELA 2.5 – VARIÁVEIS E PARÂMETROS................................................................................................. 18
TABELA 2.6 – NOTAÇÃO UTILIZADA NO MODELO................................................................................... 24
TABELA 2.7 – RESULTADOS DO MODELO................................................................................................... 26
TABELA 2.8 – RESULTADOS DO MODELO................................................................................................... 33
TABELA 2.9 – RESULTADOS DO NOVO MODELO ...................................................................................... 37
TABELA 5.1: DENSIDADE DEMOGRÁFICA DO MUNICÍPIO DE SÃO PAULO ........................................ 76
TABELA 6.1: DENSIDADE DEMOGRÁFICA AO LONGO DO TRAJETO DA LINHA................................ 99
TABELA 6.2: RESULTADO FINAL PARA 10 PONTOS DE PARADA ........................................................ 106
TABELA 6.3: RESULTADO FINAL PARA 21 PONTOS DE PARADA ........................................................ 114
ix
RESUMO
Este trabalho tem por finalidade o desenvolvimento de uma ferramenta computacional
baseada em conceitos de Diagramas de Voronoi e Programação Não-linear para estudar e
definir o espaçamento ideal entre paradas de transporte coletivo de uma região urbana com o
objetivo de minimizar o tempo médio de viagem dos passageiros até o seu destino. Foi
utilizada como parâmetro a densidade demográfica da região afetada pela linha como
parâmetro de demanda de utilização da linha. Ao final, aplica-se a ferramenta a uma região
metropolitana com os dados reais disponíveis de sua densidade demográfica. Os resultados
obtidos demonstraram a possibilidade de redução do número de paradas existentes
atualmente, com redução no tempo de viagem dos usuários. O sistema também resolveu
problemas de divisão regional de áreas afetas às paradas determinando a região de
abrangência de cada uma delas.
x
ABSTRACT
This work has the purpose to develop a computational tool based on the concepts of
Voronoi Diagrams and Non-linear Programming to study and define the ideal bus-stop
spacing in urban areas in order to minimize the total travel time of all passengers until their
destination. The demographic density of the region was used as a parameter of the demand of
the region. The tool will be applied to a metropolitan region with real data available about the
population density function. The results showed that it is possible to reduce the number of bus
stops with a considerable reduction in the travel time of the users. The model also solved
problems of regional division of the affected areas to each bus-stop determining the scope
area of each one of them.
1
1 INTRODUÇÃO
Atualmente uma das maiores preocupações em termos de planejamento urbano diz
respeito ao transporte coletivo. A quantidade de automóveis nas ruas das grandes cidades tem
causado grandes problemas, quer na perspectiva de infra-estrutura (quantidade de automóveis
acima da capacidade das vias públicas), quer no âmbito relativo à segurança da população
(altos índices de acidentes e atropelamentos), quer no aspecto relativo ao meio-ambiente
(quantidade de poluentes despejados na atmosfera pelos veículos), entre outros. Sob o ponto
de vista da infra-estrutura, um problema acarretado pelo excesso de veículos nas vias públicas
é o tempo de deslocamento que um cidadão utiliza para ir de um local a outro.
Esses problemas se intensificam principalmente nas grandes cidades, nas quais os
congestionamentos se tornaram algo comum na vida das pessoas e também parte da paisagem
urbana.
Nesse sentido, torna-se importante para o planejamento das cidades em ritmo de
crescimento populacional e de desenvolvimento urbano acelerado, um sistema de transporte
coletivo eficiente que atenda as necessidades dos cidadãos, evitando assim o uso individual do
automóvel no seu dia a dia.
Dentre os tipos de transporte coletivo existentes, o mais flexível, simples, rápido e
barato de se implantar é o ônibus. Diferentemente de outros tipos de transporte coletivo que
utiliza linhas fixas, o ônibus pode operar virtualmente em qualquer via pública com várias
rotas possíveis. Eles podem operar com paradas fixas ao longo da rota, o que é normalmente
utilizado em áreas urbanas, ou podem operar num sistema onde o usuário solicita a parada em
qualquer ponto onde seja necessário, sistema este utilizado em áreas rurais ou com baixa
2
densidade demográfica. Mesmo as paradas fixas possuem um baixo custo de instalação e são
bastante fáceis de ter a sua localização alterada, caso isso seja necessário.
Um dos principais aspectos a serem considerados num sistema de transporte coletivo é
o tempo de viagem e, como podemos imaginar, o número de paradas influi no tempo total da
viagem. Desse modo, o número total de paradas deve ser estabelecido de maneira bem
criteriosa, a fim de tornar a linha mais atrativa para o usuário. Um número excessivo de
paradas faz com que o usuário se desloque pouco a pé, porém torna a viagem bastante lenta e
desconfortável para aqueles que utilizam longos trechos da linha. Por outro lado, um número
pequeno de paradas torna a viagem mais rápida, porém obriga o passageiro a andar muito até
chegar ao ponto de parada, bem como ao destino desejado.
1.1 Problema
As constatações mencionadas acima nos conduzem à seguinte indagação: como
determinar o número ideal de paradas a fim de tornar a linha de ônibus mais atrativa para o
usuário?
Ammons (2001) estudou várias regulamentações de espaçamento entre paradas de
ônibus no mundo e descobriu que o espaçamento médio varia entre 200 e 600 metros em
áreas urbanas. Reilly (1997) verificou que as agências européias de trânsito têm padrões
diferentes dos americanos para determinar o espaçamento entre as paradas de ônibus. Na
Europa utiliza-se o padrão de 2 a 3 paradas por quilômetro, ou seja, um espaçamento de 330 a
500 metros, contrastando com a prática nos Estados Unidos, onde as paradas possuem um
espaçamento entre 160 e 250 metros.
Esses e outros estudos demonstram que o espaçamento entre as paradas não segue um
padrão único, nem são baseados em estudos com metodologias padronizadas. Segundo Kehoe
(2004), em muitas rotas nos Estados Unidos, as paradas de ônibus foram definidas ao longo
3
do tempo, resultado de um processo baseado em solicitações dos usuários que eram, ou não,
atendidos pelas autoridades e/ou empresas de transportes. Por terem sido estabelecidas
inicialmente por solicitações dos usuários, modificar o espaçamento entre as paradas torna-se
um processo muito difícil, pois a população já se acostumou ao padrão atual.
1.2 Objetivo Geral
Desse modo, o objetivo principal deste trabalho é propor um modelo matemático, a
fim de avaliar a viabilidade de se utilizar os conceitos de Diagramas de Voronoi e
Programação Não-linear, com a finalidade de determinar o espaçamento ideal entre as paradas
de ônibus de uma região urbana com a finalidade de minimizar o tempo médio de viagem dos
passageiros desde as suas casas até os seus destinos.
1.2.1 Objetivos Específicos
Como objetivos específicos podem-se listar as seguintes metas:
a) Determinar o espaçamento ótimo entre os pontos de parada de uma linha de
transporte coletivo a fim de minimizar o tempo de viagem do usuário;
b) Utilizar a densidade demográfica da região observada como um dos
parâmetros para a projeção da demanda de utilização da linha;
c) Determinar a área de influência de cada parada para que cada cidadão possa
saber, através de um diagrama, qual é a parada mais adequada para que ele
tome o transporte coletivo e chegue mais rapidamente ao seu destino;
d) Desenvolver um sistema informatizado para resolver o problema. O sistema
será desenvolvido em linguagem Delphi 6.0;
4
Sendo a finalidade principal do sistema minimizar o tempo de viagem dos passageiros
até o seu destino, acredita-se que a sua implantação seja mais facilmente assimilada pelos
usuários, uma vez que tornará a viagem mais rápida e mais atrativa.
1.3 Limitações do Trabalho
O espaçamento obtido utilizando os conceitos de Diagramas de Voronoi desenvolvido
neste trabalho pretende minimizar apenas o tempo de viagem do usuário em uma linha de
ônibus real ou hipotética. O modelo utiliza como parâmetros apenas a velocidade do usuário a
pé, a velocidade do ônibus e a densidade populacional da região atendida.
Alguns fatores não serão abrangidos por este estudo. Alguns deles estão listados a
seguir:
a) Fatores como custos operacionais, competitividade entre empresas e o estudo
de múltiplas linhas não fazem parte do escopo deste trabalho;
b) Tamanho da frota, espaçamento entre os ônibus e tempo de espera do usuário
no ponto não fazem parte dos parâmetros analisados;
c) O estudo sobre uma área que contenha alguma forma de barreira como rio,
lago, grande avenida, parque, dentre outras, também não foi abordado;
d) A topografia não foi levada em consideração neste modelo. Assume-se que a
topografia é constante em toda a região, variando apenas a sua densidade
demográfica.
Todas essas limitações poderão ser abordadas em trabalhos futuros.
5
1.4 Estrutura do Trabalho
Para compreensão do estudo proposto, este trabalho foi organizado em sete capítulos,
incluindo esta introdução.
O segundo capítulo traz uma revisão bibliográfica sobre espaçamento de paradas de
transportes coletivos. Nele são levantados os vários aspectos que compõem a problemática da
logística urbana no tocante aos transportes coletivos, os modelos existentes e as metodologias
empregadas atualmente para resolver o problema.
No terceiro capítulo discutem-se conceitos e aspectos técnicos sobre os Diagramas de
Voronoi, seu histórico, seus tipos e suas propriedades principais. Descreve-se também a sua
utilidade no planejamento urbano em geral.
No quarto capítulo é feita uma revisão sobre Programação Não-Linear. Procura-se
destacar os aspectos relevantes à solução do problema a ser resolvido, bem como as
heurísticas que serão implementadas para resolver o problema proposto.
No quinto capítulo é apresentada a formulação matemática do modelo proposto, com a
sua fundamentação teórica. São discutidas as restrições do modelo, a sua função objetivo e
também os aspectos relevantes para a sua solução. Também é mostrada a região geográfica e
os dados técnicos das linhas que são utilizadas para a aplicação do sistema desenvolvido.
No sexto capítulo descreve-se os aspectos da implementação computacional do
modelo, os resultados obtidos, na aplicação a um problema real e um hipotético, com os seus
resultados e análises.
No sétimo capítulo são apresentadas as conclusões deste trabalho e as recomendações
para trabalhos futuros.
6
2 REVISÃO DA LITERATURA
Neste capítulo serão analisados vários estudos desenvolvidos sobre o espaçamento de
pontos de parada de transporte coletivo. Vários operadores de vários países foram
pesquisados a fim de que fosse obtido um panorama geral de como esse problema é tratado e
quais os parâmetros que costumam ser adotados a fim de melhor equacionar as demandas
locais. Vários artigos que trazem modelos matemáticos a fim de estudar e otimizar o
espaçamento das paradas de ônibus também serão estudados. Os artigos mais relevantes para
este trabalho serão descritos mais detalhadamente a fim de auxiliar na compreensão do
modelo a ser proposto.
Segundo Quinn (1992, citado por LINDAU; KHÜN 2000), o congestionamento viário
é um fenômeno que assola grandes áreas urbanas em países ricos e pobres. Face à dimensão
atual do problema, o congestionamento, antes encarado como um aborrecimento, agora é tido
como uma ameaça à viabilidade econômica dos centros urbanos.
Quando considerado o impacto sobre o transporte coletivo, um estudo do
IPEA/ANTP(1999) demonstra, por exemplo, que o congestionamento responde por 16% do
custo operacional do ônibus na cidade de São Paulo e 10% no Rio de Janeiro.
Ainda segundo Lindau e Khün (2000), na Europa, onde, assim como no Brasil, vem
ocorrendo uma gradativa redução na quantidade de passageiros transportados pelo sistema de
transporte coletivo (NTU, 1998), cresce o interesse por medidas que priorizem a circulação do
sistema de transporte coletivo em detrimento do transporte individual.
O ônibus é também entendido como a modal mais flexível de transporte coletivo
urbano e, portanto, com papel importante a desempenhar dentro dos objetivos traçados pelo
transporte sustentável.
Vasconcellos (2000) enfatiza que as políticas de circulação devem analisar, além da
7
fluidez e segurança, a acessibilidade, o nível de serviço dos transportes, o custo do transporte
e a qualidade ambiental, pois são essenciais para o controle da circulação.
Segundo SEDU/PR - NTU (2002), o índice de motorização privada nas cidades
brasileiras aumentou de 9 veículos por 100 habitantes em 1980 para cerca de 17 em 2000. Isto
vem dificultando sobremaneira o planejamento urbano. A superlotação das vias gera cada vez
mais congestionamentos, o que acarreta inúmeros prejuízos para toda a comunidade.
TABELA 2.1 – ÍNDICE DE EFICIÊNCIA POR TIPO DE VEÍCULO
Modo Passageiros Transportados por Espaço
de Via
Índice de Eficiência
Automóvel = 1,0
Automóvel
1% de via – 0,35% dos passageiros 1,0
Vans e Peruas
1% de via – 1,00% dos passageiros 2,8
Ônibus
1% de via – 2,80% dos passageiros 7,9
FONTE: CNT – Pesquisa CNT. Passageiros nos corredores de transporte. Brasília: CNT,
maio 2002, p.23, citado por SEDU/PR - NTU (2002).
Nas tabelas 2.1 e 2.2 temos uma comparação entre os diferentes tipos de veículos de
transporte utilizados nas cidades em relação à sua eficiência no transporte de passageiros. Na
tabela 2.1 temos o índice de eficiência do transporte de passageiros por área ocupada na via de
transporte.
TABELA 2.2 – ÍNDICES RELATIVOS POR TIPO DE VEÍCULO E POR PASSAGEIRO
Índices Relativos por Passageiro/Km
1
Modo
Energia
2
Poluição
3
Custo Total
4
Área de Via
Ônibus
1 1 1 1
Motocicleta
4,6 32,3 3,9 4,2
Automóvel
12,7 17,0 8,0 6,4
FONTE: ANTP Associação Nacional de Transportes Públicos - Desenvolvimento Urbano,
Transporte e Trânsito no Brasil. Propostas para debate. São Paulo: ANTP (2001, p. 11), citado
por SEDU/PR - NTU (2002)
NOTA: ¹ Ocupação de 50 pessoas por ônibus, 1 por moto e 1,3 por automóvel.
² Base calculada em gramas equivalentes de petróleo (diesel e gasolina).
³ Monóxido de carbono(CO), hidrocarbonetos, óxidos de nitrogênio(NOx) e material
particulado(MP).
4
Custos totais, fixos e variáveis.
Na tabela 2.2 temos a comparação de vários índices relativo ao transporte de
passageiros por quilômetro, tendo o ônibus como referência, ou seja, como índice unitário.
8
É possível perceber a grande importância do transporte coletivo para o desafogamento
das vias urbanas, melhorando a trafegabilidade como um todo.
Ainda segundo SEDU/PR - NTU (2002), o transporte coletivo é o responsável pela
maioria dos deslocamentos motorizados nas cidades (59% dos passageiros/dia contra 41% do
transporte privado). Mas essa participação vem caindo de ano para ano. As causas ainda não
foram identificadas, mas pode se perceber uma reação negativa dos usuários em relação ao
transporte coletivo.
Para combater essa reação são utilizadas medidas diretas (atração) e indiretas
(dissuasão) que são:
e) Atração: melhorias no nível de serviço do transporte público, tarifas,
informação e marketing e melhorias na integração do transporte público e
privado, entre outras;
f) Dissuasão: restrições no estacionamento de veículos particulares, moderação
do tráfego, taxação do combustível, cobrança pelo uso da via, por exemplo.
Uma das medidas de atração citadas, a melhoria no nível de serviço do transporte
público, pode ser implementada com a diminuição no tempo médio de viagem entre a origem
e o destino final do passageiro. Esta medida vai permitir que os usuários prefiram o transporte
coletivo em vez do automóvel.
Um dos itens que podem ser utilizados para melhorar o tempo de viagem é o
espaçamento entre os pontos de paradas. Sendo possível reduzir o tempo médio de viagem
dos passageiros desde a sua origem até o seu destino, haverá um ganho de qualidade no
serviço prestado, tornando a viagem de ônibus mais atrativa.
2.1 Regulamentações Existentes no Mundo
Benn (1995), após analisar vários sistemas de trânsito do mundo todo concluiu o
9
seguinte: “O número de padrões de espaçamento existentes equivale ao número de operadores
existentes.”
TABELA 2.3 – EXEMPLOS DE NORMAS DE ESPAÇAMENTO EXISTENTES
NOS EUA
Pace Company – Chicago-IL USA Espaçamento
Alto: > 1500 hab/Km² 200m
Médio: 750-1500 hab/km² 400m
Baixo: < 750 hab/km² Sem local fixo(flag areas)
Texas Transportation Institute – USA Espaçamento
Áreas comerciais centrais 90 a 300m
Áreas residenciais centrais 150 a 360m
Áreas residenciais periféricas 180 a 750m
Áreas Rurais 200 a 800m
Transportation District of Oregon – USA Espaçamento
Áreas comerciais centrais 120 a 180m
Áreas residenciais centrais 150 a 220m
Áreas residenciais periféricas 180 a 300m
Áreas Rurais Como necessário
San Francisco and Oakland – CA USA Espaçamento
Linha Local 240 a 400m
Linha Expressa(rápida) 520 a 1500m
Transbay(Intermunicipal) 300 a 800m
FONTE: Os operadores de cada região mencionada
Nas tabelas 2.3 e 2.4 estão listados os dados referentes a vários operadores de
transporte coletivo. Nela pode-se verificar a diversidade das normas de espaçamento entre as
paradas.
TABELA 2.4 – NORMAS DE ESPAÇAMENTO EXISTENTES NA EUROPA
Local Espaçamento
Portugal¹ 250 a 330m
Europa² 320 a 500m
Holanda² 300 a 450m
Hannover(Alemanha)³ 450m
FONTE: ¹ Silva, D.F.P.(2006)
² Bertini, R.L.(2004)
³ Special report 257
Ao estudar com mais detalhes os padrões estabelecidos, percebe-se também que não
10
existe uma metodologia clara e objetiva para determinar o espaçamento ideal. Muitas vezes o
padrão é definido com base em dados históricos que apenas são regulamentados pelos órgãos
gestores do transporte público.
2.2 Regulamentações Existentes no Brasil
Segundo Andrade et. al. (2004), o distanciamento recomendado entre as paradas deve
ser estabelecido de forma que o passageiro realize uma caminhada de no máximo 500 metros,
distância esta considerada normal. Porém, o mais comum é utilizar o espaçamento de 300
metros entre os pontos de ônibus.
De acordo com a Secretaria Especial de Desenvolvimento Urbano da Presidência da
República e a Associação Nacional de Empresas de Transportes Urbanos (SEDU/PR - NTU
(2002)), o padrão recomendado para o distanciamento médio entre paradas é de:
a) 300 a 400m nas áreas centrais;
b) 400 a 600m nas áreas intermediárias;
c) 600 a 800m nas áreas periféricas das cidades.
Já a fabricante de ônibus urbanos MERCEDES-BENZ, em seu manual editado em
1987 aponta que o espaçamento adequado deve ser de 300 a 800 metros.
A Associação Nacional de Transportes Públicos (ANTP (1995) considera que, para
operações em corredores de transporte, os distanciamentos devam ser de 300 a 500m entre os
pontos de parada.
A Empresa Brasileira dos Transportes Urbanos (EBTU, 1998), considera que, do
ponto de vista operacional, a quantidade e a distância média entre os pontos de parada têm
uma grande influência na velocidade de percurso, podendo-se estimar a distância ótima entre
os pontos de parada, utilizando como critério a minimização do custo da operação.
11
2.3 Modelos de Otimização
Furth e Rahbee (2000) propõem um modelo discreto para modelar o impacto de
mudança no espaçamento entre paradas de ônibus numa rota específica.
Entre os impactos observados estão os atrasos causados pela demora dos usuários, o
aumento dos custos operacionais devido a esses atrasos e o caminho mais curto perpendicular
à rota do ônibus. Toda a intersecção ao longo da rota foi tratada como um local potencial para
uma parada.
Foi utilizado um modelo geográfico para observar a demanda nas paradas existentes
para as ruas perpendiculares e paralelas, resultando na distribuição de demanda da área de
serviço.
Um algoritmo de programação dinâmica foi utilizado para determinar o espaçamento
ótimo entre as paradas. Uma rota da cidade de Boston foi analisada como parâmetro. Essa
linha possuía um espaçamento inicial de 200m e após a aplicação do modelo foi encontrada
uma solução ótima com espaçamento de 400m.
Murrray (2003) apresentou um modelo de cobertura híbrida com a finalidade de
expandir a área de serviço atendida pela linha de ônibus, bem como aumentar a sua
acessibilidade. Foi discutida também a integração do modelo com um sistema de informação
geográfica com a finalidade de planejamento estratégico.
O modelo proporcionou uma boa flexibilidade no desenvolvimento de políticas
viáveis para a melhoria e expansão do serviço de ônibus. Um dos aspectos analisados e
otimizados foi o espaçamento entre as paradas.
Murray (2003) utilizou o Modelo de Cobertura Máxima (MCLP), que busca
maximizar a proporção da população a ser atendida. São selecionados vários valores para o
número de paradas a fim de atender a maior proporção da população possível.
O modelo foi aplicado na cidade de Brisbane, Austrália, cuja população era de
12
806.000 habitantes. A distância de acesso padrão na cidade é de 400m até a parada mais
próxima. A cidade possui 7.543 paradas no total. Após análise, constatou-se que essa
quantidade proporciona atendimento para 86% da população, deixando 14% sem um serviço
adequado. Utilizando esse modelo, chegou-se à conclusão que 11.776 paradas elevariam o
atendimento para 99% da população e que devido à topografia da cidade e ao desenho das
linhas de ônibus não seria possível atender 100%.
Gonçalves (1995) efetuou um estudo cujo enfoque foi o detalhamento da análise do
problema operacional de uma linha de ônibus urbano, englobando conjuntamente o ponto de
vista do operador e do usuário. Neste sentido, a autora buscou analisar uma situação real com
parâmetros operacionais diferenciados ao longo da linha de ônibus (tempos de parada,
velocidade, distância entre pontos de parada, etc.), possibilitando um tratamento prático e
mais detalhado da teoria.
A pesquisa foi feita utilizando a linha número 11 - Monte Verde/Florianópolis, na
cidade de Florianópolis/SC. Foram feitos levantamentos dos dados referentes ao tempo de
deslocamento do veículo, ao tempo de parada nos pontos, ao tempo de embarque e
desembarque de passageiros e à velocidade de deslocamento do ônibus. Os dados foram
coletados nos dias 15, 16 e 17 de junho de 1994, no horário de 7h30min da manhã no sentido
centro-bairro.
O modelo foi baseado nos custos, tanto do operador, quanto do usuário, a fim de
determinar a situação do serviço ofertado e a sua otimização. O custo do operador foi formado
por uma parcela de custo variável e por outra de custo fixo. Os custos foram calculados para a
frota, para um período padrão de uma hora.
O custo generalizado dos usuários foi calculado separadamente para cada par de
pontos de parada, ou seja, para cada elemento da matriz Origem-Destino. O custo
generalizado do usuário compõe-se por 5 elementos:
a) Tarifa;
13
b) Custo do tempo de percurso dentro do veículo;
c) Custo de espera;
d) Custo do desconforto;
e) Custo do trajeto a pé.
Foi também feita uma pesquisa entre os usuários através de técnicas de preferência
declarada a fim de obter a percepção do usuário em relação ao serviço ofertado.
Dentre os vários aspectos analisados no estudo, um aspecto importante foi o
espaçamento entre os pontos de parada. Hoje, na linha em questão, existem 58 pontos
distribuídos ao longo de 22750 metros, ou seja, um espaçamento médio de 392 metros entre
pontos. A título de análise de sensibilidade foi feita a simulação de um caso modificado, em
que 14 pontos atuais foram eliminados.
Nessa nova configuração, observou-se que houve um ganho, tanto para os usuários,
como também para o operador. Houve uma redução de 3,2% no custo total dos usuários e de
2,8% no custo do operador. O tempo de viagem foi reduzido de 4,1% ( 2 min. 39 seg. ).
O espaçamento médio entre pontos de parada, nessa configuração é de 22750/44 = 517
metros, significando um acréscimo de 32%. O custo total (usuários + operador) foi reduzido
de 3,1%.
A conclusão obtida pelo autor é que o aumento do número de pontos de parada, além
de certo limite, passa a prejudicar o sistema no seu todo, e não apenas o operador, mas
também os usuários.
2.4 Estudo de Caso 1
Anthony A. Saka, da Morgan State University propôs, no artigo “Model For
Determining Optimum Bus-Stop Spacing In Urban Areas” (Saka, 2001), um modelo que
possa ser usado para determinar uma política sub-ótima para o espaçamento de paradas de
14
transporte coletivo em áreas urbanas. Ele demonstra, através de uma análise de sensibilidade,
que o espaçamento apropriado pode melhorar a qualidade do serviço de transporte, o tempo
do percurso e a diminuição da frota.
A seguir tem-se um breve resumo do modelo proposto.
O tempo total de viagem Tbus percorrido por um veículo é descrito pela seguinte
equação:
T
bus
= T
a,d
+ T
S
+ T
C
+ T
O
+ T
M
(2.1)
onde:
Ta,d= tempo de aceleração e desaceleração;
TS = tempo de embarque e desembarque de passageiros;
TC = tempo de atraso devido a dispositivos de controle de tráfego (Sinais de trânsito);
TO = tempo de viagem em velocidade normal de tráfego;
TM = tempo perdido em outras situações (não modelado neste artigo)
Não se objetivou descrever todo o modelo desenvolvido no artigo mencionado, mas
apenas o primeiro termo da fórmula para fornecer uma idéia da metodologia empregada. O
primeiro termo da fórmula é Ta,d , ou seja, o tempo de aceleração e desaceleração, que é
ilustrado pela figura 2.1.
A fórmula é a seguinte:
( )
(
)
, ,
*
* * * * 1 *
2* *
a d s s c c s c s c s c
u a d
T p N p N p p p p N
a d
+
= + + + − +
(2.2)
Onde:
p
c
= probabilidade de que o ônibus pare num sinal;
N
c
= número de sinais existentes na rota;
15
p
s
= probabilidade de que o ônibus pare num ponto de parada;
N
s
= número de pontos de paradas existentes na rota;
N
s,c
= número de paradas combinadas com sinais de trânsito existentes na rota;
u = velocidade normal de cruzeiro
a = taxa de aceleração
d = taxa de desaceleração
FIGURA 2.1 DIAGRAMA DEMONSTRANDO AS FASES DE ACELERAÇÃO E
DESACELERAÇÃO
FONTE: Saka (2001, p. 196).
As probabilidades acima descritas são calculadas da seguinte maneira:
c
C g
p
C
−
=
(2.3)
Onde:
C =
Tempo médio do ciclo dos sinais ao longo da rota;
g
= Tempo médio da duração do sinal aberto ao longo da rota;
(
)
2
1
s
p e
λ
−
= − (2.4)
16
Onde:
( )
,
* 1
s s c
Q
f N N
λ
=
+ +
(2.5)
f =
freqüência horária dos ônibus na rota;
Q
= demanda horária de passageiros na rota;
Dessa maneira, são calculados todos os demais termos até se obter a fórmula final:
( )
(
)
( )
( )
( )
,
, ,
1 *
120
60
1 *
3600 120 60
bus s s c c s c s c s c
s s s c s c c s c
u a d
T p N p N p p p p N
ad
k C g D
p N N hq p N N
u
τ
+
= + + + − + +
−
+ + + + + +
(2.6)
A partir dessa fórmula, foi feito um modelo para determinar o efeito do espaçamento
entre as paradas no tamanho da frota.
Em sua conclusão, Saka (2001, p. 198) considera falhos os vários modelos existentes
porque eles não levam em consideração o efeito do espaçamento no desempenho operacional
do sistema. Este modelo de espaçamento é bastante útil como ferramenta de apoio à decisão
para o planejamento e implantação de um projeto de transporte coletivo.
2.4.1 Aplicação do Modelo
Owen de Vries Kehoe, em seu trabalho intitulado “Effects of Bus Stop Consolidation
on Transit Speed and Reliability: a Test Case” (Kehoe, 2004), utilizou o modelo apresentado
por Saka (2001) para aprimorar a rota 48 da cidade de Seattle, estado de Washington, USA.
O estudo avaliou vários aspectos tais como: segurança de pedestres, troca entre linhas
distintas, passageiros com necessidades especiais de locomoção, dentre outros, a fim de
escolher a linha mais adequada. Uma vez escolhida a linha, foram avaliados os aspectos
operacionais envolvendo a malha viária, as características que se identificaram nas origens e
17
nos destinos dos passageiros. A frota também foi analisada, bem como o intervalo de tempo
entre os ônibus.
Através desse modelo foi possível aumentar o espaçamento médio entre as paradas de
218m para 260m, sem prejuízo para os usuários.
2.5 Estudo de Caso 2
Kuah e Perl (1988), em seu artigo intitulado “Optimization of Feeder Bus Routes and
Bus-Stop Spacing”, propõem um modelo analítico para o projeto de uma rede de linhas de
ônibus que seriam utilizadas para a alimentação de uma linha de trem existente. O objetivo do
trabalho é encontrar um modelo que otimize as três variáveis básicas:
a) Espaçamento entre as linhas;
b) Intervalo entre ônibus;
c) Espaçamento entre as paradas.
Observa-se a geometria da área que é objeto do estudo na figura 2.2.
Os dois primeiros itens são analisados normalmente. Já o espaçamento entre as
paradas foi analisado em três situações diferentes. Na primeira, o espaçamento é considerado
uniforme em toda a região analisada, ou seja, ele é constante em todas as linhas. Na segunda
opção, o espaçamento é considerado constante em cada rota, porém difere de uma rota para
outra. Já na terceira opção o espaçamento varia tanto entre as rotas como também na própria
rota.
O modelo proposto assume uma demanda inelástica para as linhas de ônibus que são
representadas pela função contínua
p(x,y)
. Tal assunção é válida no contexto onde se projeta
um sistema de transporte onde a demanda é afetada principalmente pela qualidade do serviço
oferecido. O espaçamento entre as rotas
r(x)
e o intervalo entre os ônibus
h(x)
são expressos
através de funções contínuas da distância
x
medida a partir do final da linha férrea. Já o
18
espaçamento entre as paradas
s(x,y)
é expresso através de uma função contínua da localização
da rota
(x)
e da distância da linha férrea ao longo da linha de ônibus
(y)
.
FIGURA 2.2: GEOMETRIA DA ÁREA ANALISADA
FONTE: Kuah e Perl (1988, p. 342)
A tabela 2.5 mostra os parâmetros que foram utilizados no desenvolvimento do
modelo. Nela pode-se notar que tudo foi quantificado em valores monetários, inclusive o
tempo de espera do usuário entre outros.
TABELA 2.5 – VARIÁVEIS E PARÂMETROS
Símbolo Unidade Descrição
r(x)
km Espaçamento entre rotas
s(x,y)
km Espaçamento entre paradas
h(x)
hora Intervalo entre os ônibus
l
y
km Dimensão vertical da área de serviço
l
x
km Dimensão horizontal da área de serviço
V
a
km/hora Velocidade a pé do usuário
δ horas/parada Tempo perdido em cada parada
x
y
Iníci
o da
linha férrea
Estação de
trem
Paradas de
ônibus
Linhas de
ônibus
19
U
km/hora Velocidade média do ônibus
λ
o
$/veículo-hora Custo operacional do ônibus
λ
a
$/passageiro-hora
Valor do tempo gasto pelo usuário andando até a
parada
λ
r
$/passageiro-hora Valor do tempo gasto pelo usuário no ônibus
λ
w
$/passageiro-hora Valor do tempo de espera do usuário
p(x,y)
nº passageiros/km-hora Densidade da demanda no ponto (x,y) por hora
FONTE: Kuah e Perl (1988, p. 344)
O objetivo final do modelo é minimizar o custo total do sistema, incluindo os tempos
de espera e de viagem. No resultado final têm-se diferentes espaçamentos entre rotas em
diferentes partes da área atendida e diferentes intervalos entre os ônibus de uma linha para
outra. O espaçamento entre as paradas pode ainda variar de uma linha para outra ou numa
mesma linha.
Apresenta-se a seguir algumas fórmulas utilizadas no modelo.
O custo do acesso às rotas de ônibus para todos os passageiros é dado por:
0 0
1
( ) ( , )
4
y x
l l
a
a
r x p x y dxdy
V
λ
∫ ∫
(2.7)
O custo do acesso às paradas de ônibus ao longo das rotas é dado por:
0 0
1
( , ) ( , )
4
y x
l l
a
a
s x y p x y dxdy
V
λ
∫ ∫
(2.8)
O custo da espera nas paradas de ônibus ao longo das rotas é dado por:
0 0
1
( ) ( , )
2
y x
l l
w
h x p x y dxdy
λ
∫ ∫
(2.9)
20
O número total de paradas de ônibus ao longo da rota localizada no ponto
x
e na
distância
y
é dado por:
0
1
( , )
y
dt
s x t
∫
(2.10)
O tempo total gasto pelo usuário em cada parada de ônibus ao longo da rota é dado
por:
0 0 0
1
( , )
( , )
y x
l l y
r
dt p x y dxdy
s x t
λ δ
∫ ∫ ∫
(2.11)
O custo total de deslocamento e o custo em cada parada de ônibus ao longo da rota são
dados respectivamente por:
0 0
2
1
( ) ( )
y x
l l
o
dxdy
U h x r x
λ
∫ ∫
(2.12)
0 0
1
( ) ( , ) ( )
y x
l l
o
dxdy
r x s x y h x
λ δ
∫ ∫
(2.13)
O custo total do sistema é dado por:
[ ]
0 0
( ), ( ), ( , ) ( , )
y x
l l
Z h x r x s x y I x y dxdy
=
∫ ∫
(2.14)
Sendo:
[ ]
0
1 1
( , ) ( ) ( , ) ( ) ( , )
4 2 ( , )
2
1
( ) ( ) ( ) ( , ) ( )
y
a
w r
a
o o
I x y r x s x y h x dt p x y
V s x t
U h x r x r x s x y h x
λ
λ λ δ
λ λ δ
= + + +
+ +
∫
(2.15)
21
Para a finalidade desse trabalho, será analisado apenas o estudo envolvendo o
espaçamento entre as paradas. Como foi esclarecido anteriormente, o espaçamento entre as
paradas foi analisado sob três aspectos diferentes.
2.5.1 Situação 1: O espaçamento é constante ao longo da linha e se mantém constante
em todas as linhas
Considera-se a demanda uniformemente distribuída ao longo de toda a região, ou seja,
s(x,y)=s
. Como o integrando
I(x,y)
é contínuo e diferenciável e
s(x,y)
é constante, tem-se que
a equação de primeira ordem pode ser simplificada. Desse modo, a solução para um valor
ótimo de
s
é dada pela equação:
*
4
*
a r
a
V
s y
λ δ
λ
=
(2.16)
Onde:
0 0
0 0
. ( , )
( , )
y x
y x
l l
l l
y p x y dxdy
y
p x y dxdy
=
∫ ∫
∫ ∫
(2.17)
2.5.2 Situação 2: O espaçamento é constante ao longo de uma linha, mas pode variar
de uma linha para outra
Considera-se a demanda uniformemente distribuída ao longo de uma determinada
rota, ou seja,
s(x,y) = s(x).
22
Seguindo a metodologia do caso anterior, tem-se que a equação de custo pode ser
simplificada e a solução para o espaçamento ótimo para
s(x)
é dada por:
*
4
( ) *
a r
x
a
V
s x y
λ δ
λ
=
(2.18)
Onde:
0
0
. ( , )
( , )
y
y
l
l
y p x y dy
y
p x y dy
=
∫
∫
(2.19)
2.5.3 Situação 3: Considera-se que a distribuição de demanda pode variar entre rotas e
ao longo de cada rota
A solução para um valor ótimo de
s(x,y),
é obtida através da minimização do
integrando
I(x,y)
. O espaçamento ótimo é obtido através da seguinte equação:
( )
*
8
( , )
a r
a
V
s x y c y
λ δ
λ
= −
(2.20)
Onde
c
é uma constante que depende das condições iniciais (por exemplo, o
espaçamento inicial na rota) e é dada por:
( )
2
,
8
a
y y
a r
c l s x l
V
λ
λ δ
= +
(2.21)
Foi efetuado um estudo utilizando o modelo a partir de três funções de distribuição de
demanda diferentes. Os valores utilizados, as funções e os resultados obtidos estão no Anexo
I.
23
2.5.4 Conclusões do Estudo de Kuah e Perl (1988)
O estudo concluiu que o espaçamento entre as linhas e o intervalo entre os ônibus não
sofrem muita variação quando analisados separadamente nas três situações descritas acima.
Concluiu também que o espaçamento ótimo entre as paradas é uma função da raiz
quadrada de parâmetros relevantes.
Ele aumenta com:
a) A velocidade a pé;
b) Valor do tempo a bordo;
c) Tempo médio perdido nas paradas;
Ele diminui com o valor do tempo da viagem a pé.
2.6 Estudo de Caso 3
Murray e Wu (2003) desenvolveram um método de modelagem integrada para
examinar e planejar o espaçamento ideal entre os pontos de parada de ônibus a fim de
melhorar a acessibilidade dos usuários ao sistema. O acesso é considerado importante porque
ele está associado à entrada e à saída do sistema. No artigo os autores frisam que a
acessibilidade é percebida em termos espaciais através da distância física do usuário até a
parada ou estação mais próxima.
O modelo foi aplicado a uma rota de transporte coletivo da cidade de Columbus,
Ohio-USA.
Na formulação do modelo, o objetivo estratégico e operacional do planejamento do
sistema de transporte coletivo é o equilíbrio entre os vários aspectos da acessibilidade
espacial, ou seja, do acesso propriamente dito juntamente com a cobertura geográfica. Foram
também levados em conta os custos de operação do sistema.
24
O método apresentado é baseado no “Problema da p-mediana com Restrição de
Distância”.
A tabela 2.6 abaixo mostra a notação referente ao modelo.
TABELA 2.6 – NOTAÇÃO UTILIZADA NO MODELO
i
índice das áreas de serviço atendidas(áreas são pré-definidas);
j
índice de um potencial ponto de parada (O conjunto é representado por
J
);
p
número de paradas estipulado;
a
i
demanda potencial da área de serviço
i
;
d
ij
menor distância da área de serviço
i
até o potencial ponto de parada
j
;
S
Distância máxima aceitável de deslocamento a pé;
N
i
{
j
|
d
ij
≤
S
}
x
j
Será 1 se o ponto de parada
j
permanecer na rota;
Será 0 caso contrário;
z
ij
Será 1 se a área
i
for atribuída ao ponto de parada
j
;
Será 0 caso contrário;
FONTE: Murray e Wu (2003, p. 5)
Problema da p-mediana com Restrição de Distância:
Minimizar
1
i
i ij ij
i j N
Z a d z
∈
=
∑ ∑
(2.22)
Sujeito a:
1;
i
ij
j N
z i
∈
= ∀
∑
(2.23)
; ,
ij j
z x i j
≤ ∀
(2.24)
j
j
x p
=
∑
(2.25)
(
)
0,1 ;
j
x j
= ∀
(2.26)
25
(
)
0,1 ; ,
ij
z i j
= ∀
(2.27)
A função objetivo (equação 2.22) visa minimizar o valor total da demanda potencial
que é atribuída ao próximo ponto de parada.
A primeira restrição (equação 2.23) exige que cada área de serviço seja atendida por
uma parada dentro de uma distância razoável. A segunda (equação 2.24) impede que seja
atribuída a uma área de serviço uma parada inexistente. A terceira (equação 2.25) faz com que
sejam atribuídas
p
paradas.
Foram efetuados cálculos com o número de paradas
p
variando de 74 a 164. Foram
utilizados os seguintes Softwares:
a) ArcView 3.2 – Geographic Information System (GIS);
b) Programas em Visual Basic para produzir os modelos de otimização em
formato texto;
c) CPLEX 6.6 – Para resolver os problemas de PL cujos resultados foram
exportados para o ArcView.
Foi utilizada a distância Euclidiana do centróide da área de serviço até o ponto de
parada. A distância máxima aceitável para deslocamento a pé
S
foi definida em 400m. Foram
relacionados 873 blocos com 43.622 habitantes e 5.080 áreas comerciais com 71.039
empregados.
Na tabela 2.7 existe um resumo dos resultados obtidos. Nele pode-se observar algumas
das conclusões obtidas:
a) O número atual de paradas
p
é de 164. Pode-se notar que a partir de 120
paradas a distância média de acesso quase não diminui (Figura 2.3);
b) Para
p
=75 a redução no número de pontos de parada é de 42,07% e o aumento
na média da distância de acesso é de 7,77% (apenas 15m em média);
26
c) Ainda para
p
=75 o aumento no espaçamento entre os pontos de parada é de
72,63% (passa dos atuais 265m para 457,38m).
TABELA 2.7 – RESULTADOS DO MODELO
Número de
pontos de
parada(p)
Redução no nº
de paradas (%)
Espaçamento
médio em (m)
Diferença no
espaçamento
médio (%)
Distância
média de
acesso (m)
Diferença na
distância
média (%)
75 42,07 457,38 72,63 214,59
7,77
80 38,41 430,21 62,38 207,38
4,15
85 35,37 409,92 54,72 205,09
3,00
90 31,71 387,96 46,43 203,72
2,31
95 28,05 368,23 38,98 202,78
1,84
100 25,61 356,16 34,43 202,05
1,47
105 21,34 336,83 27,13 201,42
1,15
110 18,29 324,26 22,39 200,86
0,87
115 17,07 319,49 20,59 200,43
0,66
120 14,02 308,16 16,31 200,08
0,48
125 11,59 299,66 13,10 199,80
0,34
130 10,37 295,59 11,56 199,59
0,24
FONTE: Murray e Wu (2003, p. 10)
27
FIGURA 2.3 – DISTÂNCIA MÉDIA DE ACESSOS POR NÚMERO DE PARADAS
FONTE: Murray e Wu (2003, p. 10)
2.7 Estudo de Caso 4
Suzuki (1987) citado em Okabe
et. al.
(2000, p. 559-563) fez um estudo sobre uma
linha de ônibus em Ichikawa, Japão. Ele utilizou conceitos de Diagramas de Voronoi para
estabelecer o espaçamento ótimo entre paradas de ônibus numa linha alimentadora visando
minimizar o tempo médio de viagem dos passageiros até um destino comum.
Essa linha foi escolhida devido ao fato de ter um traçado quase reto e a população na
região por ela servida ter uma distribuição praticamente uniforme.
Suzuki (1987) partiu do princípio que o usuário se desloca até o ponto mais próximo
da linha de ônibus e, a partir desse ponto, procura a parada mais próxima. Imaginando-se que
todos os usuários se deslocariam dessa maneira, então o problema fica reduzido a apenas uma
dimensão, pois a distância que mudaria com uma nova distribuição seria a distância
percorrida na linha do ônibus, ou seja, sobre uma reta (Figuras 2.4 e 2.5).
28
FIGURA 2.4 – DESLOCAMENTO DO USUÁRIO ATÉ A LINHA DO ÔNIBUS
FONTE: Okabe
et. al.
(2000, p. 560)
Esse tipo de simplificação se fez necessária para que o problema pudesse ser resolvido
analiticamente, uma vez que a solução do problema original seria muito complicada e
trabalhosa.
FIGURA 2.5 – DESLOCAMENTO DO USUÁRIO NA LINHA DO ÔNIBUS
FONTE: Okabe
et. al.
(2000, p. 560)
Para formular matematicamente o problema descrito acima, consideremos um ônibus
na rota
L
, na região
S
, onde
n
pontos de paradas são colocados. Os pontos são indexados de 1
até
n
a partir do terminal. Seja
l
i
a distância na rota do ponto
i
até o ponto
i
+1, com
i
variando
de 1 até
n
. O ponto 0(zero) é o terminal final da linha. A localização do ponto na rota
L
pode
ser representada pela distância
s
do ponto até o terminal final. A localização do ponto
i
é
então indicada por:
1
i
i j
j
s s l
=
= =
∑
(2.28)
Os usuários são distribuídos sobre a região
S
de acordo com a função de densidade
∅ (
x
).
s
1
s
2
s
3
0
x
1
x
s
1
s
2
s
3
0
L
s
29
Seja
v
b
a velocidade média do ônibus,
v
w
a velocidade do usuário a pé e
b
o tempo
gasto pelo ônibus em cada parada. O tempo total de viagem do ponto
s
até o ponto
i
a pé e do
ponto
i
até o terminal final de ônibus é dado pela seguinte fórmula:
( )
*
i
i
w b
s s
s
i b
v v
−
+ +
(2.29)
A seguinte restrição precisa ser satisfeita, senão andar seria mais rápido do que ir de
ônibus:
i i
b w
l l
b
v v
+ <
(2.30)
Como todo usuário deseja minimizar o seu tempo de viagem, ele então vai procurar o
ponto que lhe proporcione o menor tempo possível. Ou seja, se ele está no ponto
s
, ele vai
escolher o ponto
i
que minimize o tempo de viagem até o terminal. A equação que representa
essa situação é:
( )
min *
i
i
i
w b
s s
s
i b
v v
−
+ +
(2.31)
Como resultado, temos, para todo ponto
i
, uma área de abrangência definida por:
( ) ( )
| * * , para \{ }
j
j
i
i
i n
w b w b
s s
s
s s
s
V s i b j b j I i
v v v v
−
−
= + + ≤ + + ∈
(2.32)
A equação acima representa uma região de Voronoi gerada na linha
L
. A partir dessa
equação, temos o tempo total de viagem de todos os usuários da região que é dado por:
( ) ( )
1
0
( ,..., ) *
i
n
i
i
n L
i
w b
v
s s
s
F l l i b x ds
v v
φ
=
−
= + +
∑
∫
(2.33)
30
O problema fica então definido da seguinte maneira:
( ) ( )
1
,...,
0
min *
n
i
n
i
i
L
l l
i
w b
v
s s
s
i b x ds
v v
φ
=
−
+ +
∑
∫
(2.34)
Sujeito a:
para todo
i i
n
b w
l l
b i I
v v
+ < ∈
(2.35)
1
n
i
i
l L
=
≤
∑
(2.36)
1
0 para todo
i n
l i I
+
> ∈
(2.37)
Este é um problema de programação não-linear com restrições. Como a função de
densidade é considerada uniforme, a função objetivo pode ser reescrita transformando o
problema num problema de programação quadrática (um caso especial de programação não-
linear).
O problema descrito acima foi resolvido para vários números de paradas, com
n
variando de 2 até 34. Foi calculada a solução ótima para cada caso. A menor solução ótima
encontrada foi para n=8, com um espaçamento entre os pontos de 608m. O espaçamento
inicial era de 325m, com 15 pontos de parada (n=15).
2.8 Estudo de Caso 5
Novaes
et. al.
(2009) utilizou conceitos de diagramas de Voronoi e modelos de
aproximação contínua para resolver problemas de alocação distrital voltados para aplicações
em transporte e logística.
No artigo em questão, os autores analisaram um problema de localização de estações
de metrô numa região urbana que também é servida por uma linha de ônibus.
31
A figura 2.6 abaixo mostra uma área
ℜ
a qual é atualmente servida por uma linha de
ônibus que segue para um terminal urbano. Ao longo da linha existem 07 (sete) pontos de
parada numerados de 1 a 7. Uma nova linha de metrô está sendo analisada para ser implantada
na área em questão. A linha tem um traçado circular com raio de 3,85Km, como mostra a
figura 2.6. O problema em questão é encontrar o número ideal de estações, bem como as suas
respectivas localizações, a fim de otimizar uma função objetivo específica. Neste caso, o
objetivo é maximizar arrecadação da linha do metrô, ou seja, atrair o maior número de
passageiros possível.
FIGURA 2.6 – REGIÃO URBANA SERVIDA POR UMA LINHA DE ÔNIBUS E METRÔ
FONTE: Novaes
et. al.
(2009, p. 14)
A função de demanda é descrita como sendo uma função de densidade decrescente em
torno do terminal. As curvas circulares na figura 2.5 indicam a variação da densidade (em
porcentagem) na região. Como podemos perceber, no terminal a densidade é máxima (100%).
Pela manhã os usuários andam desde suas casas até o ponto de ônibus ou estação do metrô
32
mais próxima. Seja Γ = {
P
1
,
P
2
,
...
,
P
m
} a representação dos
m
pontos de embarque (ônibus ou
metrô) no plano euclidiano. Seja
X
um ponto arbitrário na região ℜ com coordenadas (
x,y
). A
área de abrangência dos passageiros referente ao ponto de embarque
P
i
é representada por um
diagrama de Voronoi ordinário poligonal definido por:
(
)
{
}
2
| , , 1,...,
i i j
V P X R X P X P j i j m
= ∈ − ≤ − ≠ =
(2.38)
Onde
P
1
,
P
2
, ...,
P
m
são os pontos geradores do diagrama de Voronoi. Com
i
representando qualquer ponto de embarque, tem-se a seguinte representação:
a)
i
= 0 como sendo o terminal;
b)
i
= 1, 2,...,
b
representando os pontos de ônibus;
c)
i
=
b
+1,
b
+2,...,
b
+
s
representando as estações de metrô.
Assim temos
b
pontos de ônibus e
s
estações de metrô, sendo
b
+
s
=
n
. Assim sendo, o
conjunto de pontos geradores compõem-se de três subconjuntos:
0
b s
Γ = Γ ∪ Γ ∪ Γ
, onde
{
}
0 0
P
Γ =
,
{
}
1
,...,
b b
P P
Γ =
e
{
}
1
,...,
s b b s
P P
+ +
Γ =
.
Seja
V
(
P
1
),
V
(
P
2
), ...,
V
(
P
m
) os diagramas de Voronoi ordinários gerados por Γ. Por
construção,
( )
1
m
i
i
V P
=
∪ cobre toda a região ℜ . Seja
(
)
X
Φ
a função densidade de demanda no
ponto
X
. O objetivo é maximizar a arrecadação do metrô através de duas variáveis de decisão:
a) O número de estações;
b) A localização das estações ao longo da linha de metrô.
Uma vez que a linha do metrô descreve um arco, os pontos de Γ ficam restritos a essa
curva. Eles podem ser então descritos parametricamente por uma variável real θ, ou seja, um
ângulo ou um comprimento de arco. Cada ponto na linha do metrô corresponde a um valor de
θ
,
pertencente ao intervalo (θ
min
,
θ
max
). Tem-se então uma equação paramétrica
P
=
P
(θ) que
descreve a localização geométrica da linha do metrô. Os elementos de Γ são definidos por um
vetor real Θ = (θ
1
, ...,
θ
s
), ou seja, existe uma correspondência biunívoca entre os sub-
33
conjuntos viáveis de Γ
s
e um sub-conjunto
A
pertencente ao conjunto real
R
s
e, para um
s
e
A
:
Γ
s
= Π (Θ
s
), onde Π é uma função biunívoca. Temos então:
(
)
(
)
(
)
{
}
{
}
1 min max
, :1 , |
s
b i i i
P P P i s A R
θ θ θ θ θ
+
= Π Θ = ≤ ≤ = Θ∈ ≤ ≤ (2.39)
Assim sendo, as variáveis a serem numericamente determinadas são s e
Θ
s
. A função
objetivo a ser maximizada é:
( ) ( )
1
i
b s
s i
i b
V
G X P X dX
φ
+
= +
Θ = −
∑
∫
(2.40)
A resolução numérica da equação 2.40 envolve a construção de um diagrama de
Voronoi ordinário definido pelos pontos geradores
{
}
1 2 0
, ,...,
m b s
P P P
Γ = = Γ ∪ Γ ∪ Γ
, sendo
(
)
s s
Γ = Π Θ
. Existe ainda a necessidade de ser estabelecida uma distância mínima entre as
estações do metrô. Considerando
AB
como a extensão total da linha do metrô, temos então a
seguinte restrição:
min
1
AB
d
s
≥
+
(2.41)
Onde
d
min
é a menor distância permitida entre as estações do metrô. Neste caso, foi
utilizada a distância mínima de 800m. Isso nos dá um limite para o número máximo de
estações, ou seja,
s
=1, 2, ...,
s
max
. Assim sendo, resolve-se o problema para todos os números
de estações, de um até
s
max
.
TABELA 2.8 – RESULTADOS DO MODELO
Número de Estações
(
s
)
Número de Iterações Distância entre
Estações
(em metros)
Quantidade de
Passageiros(em % da
demanda total)
1 29 2103 26,77
2 105 1402 41,73
3 115 1051 46,42
4 259 841 48,27
5 371 701 49,03
FONTE: Novaes
et. al.
(2009, p. 16)
34
Para encontrar a solução do problema de programação não-linear descrito acima,
utilizou-se o método de busca direta de Hooke e Jeeves(1962). Foram calculadas as soluções
ótimas para
s
= 1 até 5. Os resultados estão na tabela 2.8.
Como podemos perceber na tabela 2.8, a diferença obtida aumentando de 4 para 5
estações é mínima, apenas 1,6%. Como 5 é o número máximo de estações determinado pelo
espaçamento mínimo, temos que o valor ideal é obtido com
s
= 4, devido o custo elevado de
construção de uma estação para um ganho muito pequeno. A localização das estações está
indicada na figura 2.7.
FIGURA 2.7 – LOCALIZAÇÃO DAS ESTAÇÕES CALCULADAS PELO MODELO
FONTE: Novaes
et. al.
(2009, p. 17)
Outra abordagem feita pelos autores do artigo foi colocando algumas restrições de
tempo no modelo. Assumiu-se que os usuários estariam dispostos a andar no máximo 20
minutos até uma estação do metrô, 15 minutos até um ponto de ônibus e 30 minutos até o
terminal. Foi considerada uma velocidade a pé de 4,4 km/h. Para calcular a distância
35
percorrida pelo usuário, foi aplicado um fator de correção de 1,35 na distância euclidiana
entre dois pontos. Esta modificação gerou uma mudança no resultado, pois o diagrama de
Voronoi deixou de ser um diagrama ordinário, e o resultado está na figura 2.8.
Outro modelo, mais realístico que o descrito acima, também é descrito no artigo. A
diferença está na função objetivo, que busca minimizar o tempo de viagem dos passageiros,
desde as suas casas até o terminal, ou seja, o passageiro vai escolher a estação do metrô ou
ponto de ônibus que o faça chegar mais rápido ao seu destino.
Suponhamos um usuário localizado no ponto
X
que caminha até o ponto de ônibus
P
i
(
i
=1,...,
n
). O tempo total para que ele chegue no terminal é composto dos seguintes
elementos:
a)
Tempo de viagem a pé até o ponto de ônibus (
t
h
);
b)
Tempo de espera no ponto (
t
w
);
c)
Tempo percorrido dentro do ônibus, excluindo o tempo nas paradas (
t
t
);
d)
Total do tempo perdido nos pontos subseqüentes (
t
s
).
O tempo a pé é calculado da seguinte maneira:
( )i
H i
H
k
t X P
V
= −
(2.42)
Onde
V
H
é a velocidade média a pé e
k
é o fator de correção mencionado
anteriormente. O valor esperado para o tempo gasto no ponto
t
w
é a metade do tempo
observado entre um ônibus e o próximo na rota
L
(
L
τ
).
O tempo percorrido no ônibus é dado por:
1
( )
1
0
i
i
t j j
j
Lt
k
t P P
V
−
+
=
= −
∑
(2.43)
Onde
V
Lt
é a velocidade média do ônibus na rota. A soma do tempo gasto nas paradas
é calculada por:
( )
1
i
i
S Lj
j
t S
=
=
∑
(2.44)
36
Onde
S
Lj
é o tempo médio gasto no ponto
j
da rota
L
. O custo geral atribuído a cada
usuário partindo do ponto
X
até o terminal, através do ponto
i
, é dado por:
(
)
(
)
( ) ( ) ( ) ( ) ( )
; 1,...,
i i i i i
H H W W t t S
C t t t t i n
α α α
= + + + =
(2.45)
Onde
H
α
,
W
α
e
t
α
são pesos associados ao tempo da viagem a pé, ao tempo de
espera no ponto e ao tempo percorrido na viagem no ônibus, respectivamente.
FIGURA 2.8 – NOVO DIAGRAMA DE VORONOI CALCULADO
FONTE: Novaes
et. al.
(2009, p. 19)
Portanto, para todo ponto
X
o modelo procura o ponto
i
(
i
= 1,...,n) que torna
C
(i)
mínimo. Após algumas substituições e simplificações na fórmula anterior (2.45)
C
(i)
pode ser
expresso como:
1
( )
1
0 1
2
i i
i
W L tH
i j j t Lj i i
j j
H Lt
k
V
C X P P P s X P w
k V
α τ α
α
α
−
+
= =
= − + + − + = − −
∑ ∑
(2.46)
O que vem a ser uma região de Voronoi ponderado por soma.
37
Assumindo
V
H
= 4,4Km/h,
V
Lt
= 20Km/h para o ônibus,
V
Lt
= 60Km/h para o metrô, o
tempo gasto na parada 90 e 30 segundos para o ônibus e o metrô respectivamente. O tempo
entre dois ônibus consecutivos é de 5 minutos e entre os trens do metrô é de 1,5 minutos. O
fator de correção de distância
k
é igual a 1,35 e os limites de tempo do exemplo anterior, ou
seja, que os usuários estariam dispostos a andar no máximo 20 minutos até uma estação do
metrô, 15 minutos até um ponto de ônibus e 30 minutos até o terminal.
Aplicando-se o modelo tem-se o resultado descrito na tabela 2.9.
TABELA 2.9 – RESULTADOS DO NOVO MODELO
Número de Estações
(
s
)
Número de Iterações Distância entre
Estações
(em metros)
Quantidade de
Passageiros(em % da
demanda total)
1 29 2103 25,38
2 65 1402 44,04
3 205 1051 50,71
4 227 841 52,19
5 359 701 52,62
FONTE: Novaes
et. al.
(2009, p. 20)
Como podemos perceber, o melhor valor para
s
é 4, ou seja, quatro estações de metrô
vão obter a melhor quantidade de passageiros na região quando o que se deseja minimizar é o
tempo de viagem do usuário.
38
FIGURA 2.9 – NOVO DIAGRAMA DE VORONOI CALCULADO NA REGIÃO
FONTE: Novaes
et. al.
(2009, p. 21)
A figura 2.9 mostra a localização final das estações, bem como as suas áreas de
abrangência. Comparando a figura 2.9 com a figura 2.8 podemos perceber que utilizando a
nova metodologia, a área de abrangência das estações do metrô tende a aumentar
consideravelmente.
2.9 Considerações Finais
O ônibus é um importante veículo de transporte coletivo urbano devido a sua
facilidade de implantação, flexibilidade e adaptabilidade. Ele continua sendo o meio de
transporte mais utilizado pela população e é uma alternativa importante para desafogar o
trânsito nas grandes cidades.
O espaçamento entre os pontos de parada é um importante componente na maneira de
se melhorar o desempenho do sistema em áreas urbanas e que vem a ser uma ferramenta de
atração para induzir mais passageiros a utilizarem o sistema de transporte coletivo.
39
Atualmente existem inúmeras metodologias para definir o espaçamento entre os
pontos de parada, sendo que alguns carecem de um melhor embasamento científico. Vários
estudos existentes procuram minimizar custos e/ou tamanho da frota. Alguns procuram
também minimizar o tempo médio da viagem, porém combinado com outros fatores.
No Anexo 8 temos um resumo dos artigos apresentados neste capítulo.
O estudo do espaçamento dos pontos de parada visando reduzir o tempo médio de
viagem dos usuários pretende proporcionar uma importante ferramenta para o
desenvolvimento do transporte coletivo em áreas urbanas.
40
3 DIAGRAMA DE VORONOI
3.1 Histórico
A primeira referência sobre o Diagrama de Voronoi data de 1644, quando Descartes
publicou um estudo chamado
Le Trait de la Lumière
, onde ele utilizou formas parecidas com
Diagrama de Voronoi a fim de ilustrar o Sistema Solar e os seus arredores, conforme observa-
se na ilustração na figura 3.1.
FIGURA 3.1: LE TRAIT DE LA LUMIERE
Fonte: Okabe
et. al.
(2000, p. 7)
Os primeiros estudos utilizando os conceitos que no futuro seriam definidos como
Diagramas de Voronoi foram efetuados por Peter Gustav Lejeune Dirichlet, no ano de 1850,
cujo conteúdo tratava de uma teoria sobre Formas Quadráticas Positivas Definidas. Ele
estudou o assunto para os casos bi e tri-dimensionais.
41
Outro estudo foi feito por John Snow através de um Relatório sobre Epidemia de
Cólera, na Inglaterra, que foi publicado em 1855.
Mais tarde, em 1896 Georgy Fedoseevich Voronoi, em sua tese de doutorado
intitulada “
Ob odnom obobshchenii algorifma nepreryvnykh drobei”
que em russo significa
“
Sobre uma generalização do algoritmo de quebra de cadeias”
, publicada em Varsóvia,
Polônia. Ele desenvolveu um método em que, com base em uma triangulação pré-existente de
pontos que representam os centros de alguma coisa (no caso da primeira aplicação, agências
de correio), se determina qual a área de influência de cada um destes centros em função da
posição dos outros centros, delimitando de forma geométrica cada área de influência.
Até onde se sabe, foi o matemático russo Boris Nikolaevitch Delaunay (1929, 1932)
quem primeiro relacionou os nomes de Dirichlet e Voronoi a esses poliedros. Ele os chamou
de Domínio de Dirichlet e Região de Voronoi (Okabe
et. al.
, 1998).
Shamos e Hoey (1975) desenvolveram um algoritmo computacional para a construção
de um Diagrama de Voronoi e mostraram como utilizar esse conceito para resolver outros
problemas correlatos. Desde então, vários algoritmos computacionais foram desenvolvidos
para aplicações gerais ou para resolver problemas mais específicos.
3.2 Considerações Iniciais
Considere-se as seguintes situações:
a)
Estudo astronômico da Estrutura do Universo;
b)
Estudos arqueológicos para definir a área de influência de uma determinada
tribo;
c)
Estudo meteorológico sobre a quantidade de chuva numa determinada região
atendida por um certo número de pluviômetros;
d)
Planejamento sobre a distribuição de escolas numa cidade;
42
e)
Um estudo sobre a capilaridade da irrigação sanguínea num tecido muscular.
Aparentemente essas atividades teriam pouca coisa em comum, porém existe algo em
comum a todas elas: o Diagrama de Voronoi. Os conceitos matemáticos desenvolvidos por
Voronoi são utilizados para a solução desses problemas e de muitos outros.
O conceito, apesar de bastante simples e intuitivo, possui características matemáticas
importantes que vem sendo utilizadas há mais de um século na ciência em diversas áreas. O
conceito é o seguinte: “Dado um conjunto finito de pontos
P
, distintos e isolados, num espaço
contínuo, nós associamos todos os demais pontos do espaço ao ponto mais próximo do
conjunto de pontos
P
.”
1
(OKABE
et. al.
, 2000, p. 44).
O resultado da definição acima é a partição do espaço em regiões. Essas regiões são
conhecidas como Regiões de Voronoi. Ao se representar essas regiões num espaço Euclidiano
bi-dimensional, ou seja, num plano, as regiões ficam reduzidas a polígonos, denominados
Diagrama de Voronoi (Figura 3.2).
FIGURA 3.2: DIAGRAMA DE VORONOI
FONTE: Elaboração do autor.
1
Tradução livre.
43
3.3 Definições
Os conceitos apresentados neste capítulo são oriundos de Okabe
et. al.
(2000).
3.3.1 Diagrama de Voronoi
Suponha-se um conjunto de pontos
P
no plano e que o número de pontos é de dois ou
mais, porém finito, sendo que todos são distintos. Dado um ponto fixo qualquer, será
assumido que toda localização no plano está associada ao membro mais próximo dentre os
pertencentes ao conjunto de pontos
P
. Se uma localização acontece de tal forma a estar
igualmente perto de dois ou mais membros do conjunto de pontos, a locação será designada a
todos esses membros. Como resultado, os conjuntos de localizações designados a cada
membro no conjunto de pontos formam suas próprias regiões. As regiões resultantes são
coletivamente exaustivas no plano porque cada locação é designada a, pelo menos, um
conjunto de pontos. O conjunto de locações designado a dois ou mais membros do conjunto
de pontos formam as regiões de fronteiras. Assim, o conjunto das regiões é coletivamente
exaustivo e mutuamente exclusivo com exceção das fronteiras, ou seja, o conjunto das regiões
forma uma tecelagem. O nome desta tecelagem é
Diagrama Comum de Voronoi
no plano, e
as regiões que constituem o Diagrama de Voronoi são
Polígonos Comuns de Voronoi
.
3.3.1.1 Definição Matemática do Diagrama de Voronoi
Seja
P
= {
p
1
, p
2
,..., p
n
} um conjunto finito de dois ou mais pontos não colineares do
plano euclidiano, chamados de centros geradores ou centróides. Particione o plano atribuindo
a cada ponto do plano o centróide mais próximo de acordo com a distância Euclidiana.
44
Todos os pontos associados a
p
i
formam um polígono de Voronoi
V (p
i
).
O conjunto
de todos os pontos associados a mais de um centro forma o diagrama de Voronoi
Vor (P)
.
Seja
P =
{
p
1
, p
2
,..., p
n
}
⊂ ℝ
2
onde 2 <
n
<
∞
e
p
i
≠
p
j
para todo
i
≠
j , com i,j
∈
I
n
:
{
}
)(),...,(),(
21 n
o
pVpVpVV =
(3.1)
E o conjunto é dado por:
{
}
,; : )(
njii
IjijxpxpxpV ∈≠−≤−=
(3.2)
Este é o Diagrama de Voronoi no plano, ou
Diagrama Ordinário de Voronoi
no plano.
Esse conjunto pode ser descrito como:
)(
1 i
n
i
pV∂∪
=
(3.3)
Onde
)(
i
pV
∂
ou
i
e
é o conjunto das
Arestas de Voronoi
referente ao ponto gerador
p
i
. O ponto de término de uma Aresta é chamado de
Vértice de Voronoi
.
Na figura 3.3 pode-se ver um exemplo de um Diagrama Ordinário de Voronoi
no
plano, com os seus componentes especificados.
45
FIGURA 3.3: DIAGRAMA ORDINÁRIO DE VORONOI NO PLANO
FONTE: Elaboração do autor.
3.3.1.2 Degeneração do Diagrama de Voronoi
Degeneração: considera-se que um Diagrama de Voronoi é Não Degenerado quando
todos os seus vértices são formadas por exatamente três Arestas. Caso contrário, ele será
considerado um Diagrama de Voronoi Degenerado.
Na figura 3.4 temos um exemplo de um Diagrama de Voronoi Degenerado.
FIGURA 3.4: DIAGRAMA DE VORONOI DEGENERADO
FONTE: Elaboração do autor.
Vértice com mais
de três arestas
Vértices
Arestas
Centróides
46
Em algumas aplicações, um diagrama de Voronoi Degenerado requer um tratamento
especial para garantir a precisão no resultado.
3.3.1.3 Diagrama de Voronoi com Barreiras
Considerando as definições anteriores, define-se um diagrama de Voronoi em um
plano ilimitado. Na prática, porém, freqüentemente ele está limitado de acordo com a região S
onde os geradores são alocados. Neste caso é considerado o conjunto dado por:
V
∩
S
={
V
(
p
1
)
∩
S
,
V
(
p
2
)
∩
S
,...,
V
(
p
n
)
∩
S
}
,
A união dos conjuntos de Diagramas Limitados de Voronoi ou Diagrama de Voronoi
Limitado denota-se
S
. Se o polígono de Voronoi
V(p
i
)
compartilha da fronteira de
S
, então é
chamada a região
V(p
i
)
∩
S
por polígono de fronteira de Voronoi ou região (o termo “região”
é usado quando
∂
S
é curvo ou quando
V(p
i
)
∩
S
é não conectado).
Deve-se notar que uma região de fronteira de Voronoi pode ser desligada e esse
segmento de reta unindo um ponto em
V
(
p
i
) e
p
i
pode não estar contido em
V
(
p
i
)
∩
S
. Na
prática, como a fronteira dos polígonos de Voronoi são freqüentemente problemáticas, tem-se
assim que definir um diagrama de Voronoi de modo mais apropriado. Um diagrama limitado
de Voronoi pode ser significativo na prática se toda região de fronteira de Voronoi for com
ligações inteiramente contidas em cada polígono com respeito ao ponto gerador. Na prática,
usualmente se trabalha com uma fronteira bem formada do diagrama de Voronoi.
A figura 3.5 possui um exemplo de um Diagrama de Voronoi com barreiras,
exemplificando os conceitos acima.
47
FIGURA 3.5: DIAGRAMA DE VORONOI COM BARREIRAS
FONTE: Elaboração do autor.
3.3.1.4
Diagrama de Voronoi no
m
R
Aqui apenas apresenta-se uma generalização do Diagrama de Voronoi do
2
»
para o
m
»
apenas para ilustração, pois a intenção desse estudo é trabalhar com os conceitos do
Diagrama de Voronoi no plano Euclidiano.
Seja
P
= {
p
1
, p
2
,..., p
n
}
⊂
ℝ
m
onde 2 <
n
<
∞
e p
i
≠
p
j
para todo
i
≠
j
, com
i,j
∈
I
n
tem-
se:
{
}
\{ }
( ) : ; , ( , )
n
i i j n i j
j I i
V p x p x p x j i j I H p p
∈
= − ≤ − ≠ ∈ =
∩
(3.4)
Onde
H(p
i
, p
j
)
é a região de dominância de
p
i
sobre
p
j
.
Área
Desconectada
Área não convexa,
porém sem afetar as
propriedades do
Diagrama de Voronoi:
(Star-shaped)
Área não convexa cuja
barreira influencia nas
propriedades do
Diagrama de Voronoi.
48
3.4 Triangulação de Delaunay
Dado um Diagrama de Voronoi com
n
Centros Geradores não-colineares e sendo
3
≤
n
<
∞
, liga-se todos os Centros Geradores que compartilham uma aresta de um Polígono de
Voronoi. O resultado dessa operação é um novo diagrama. Se ele consiste apenas de
triângulos, então é denominado de Triangulação de Delaunay, caso contrário, de Pré-
triangulação de Delaunay.
A Triangulação de Delaunay é o dual do Diagrama de Voronoi, como pode-se ver na
figura 3.6 abaixo. As linhas mais escuras representam a Triangulação de Delaunay.
FIGURA 3.6: TRIANGULAÇÃO DE DELAUNAY
FONTE: Okabe
et. al.
(2000, p. 53).
Na figura 3.7 observa-se uma Pré-triangulação de Delaunay, pois existe um polígono
entre os pontos assinalados que não é um triângulo.
49
FIGURA 3.7: PRÉ-TRIANGULAÇÃO DE DELAUNAY
FONTE: Okabe
et. al.
(2000, p. 53).
Inspecionando o diagrama de Voronoi indicado pelas linhas pontilhadas na figura 3.7
acima, observa-se que uma Pré-triangulação de Delaunay só acontece quando o diagrama de
Voronoi é degenerado.
FIGURA 3.8: TRIANGULAÇÃO DE DELAUNAY OBTIDAS DA FIGURA 3.4
FONTE: Okabe
et. al.
(2000, p. 53).
Uma pré-triangulação de Delaunay pode ter polígonos contendo quatro ou mais
vértices. Faz-se partição nesses polígonos não triangulares em triângulos por segmentos de
retas que não se interceptem juntando-se os vértices. Por exemplo, particionando o polígono
quadrangular com vértices
p
i1
,
p
i2
, p
i3
, p
i4
na figura 3.7 por segmentos
p
i1
p
i3
. Com este
resultado, a Pré-triangulação de Delaunay torna-se uma tecelagem, consistindo somente de
triângulos (figura 3.8). Esta tecelagem também é chamada de triangulação de Delaunay (e,
50
algumas vezes, de triangulação degenerada de Delaunay para distinguir da triangulação de
Delaunay dada acima). Deve-se notar que, como pode ser visto na figura 3.8, a triangulação
de Delaunay obtida da pré-triangulação de Delaunay não é única; o polígono quadrangular
p
i1
p
i2
p
i3
p
i4
pode ser triangulado pelos segmentos
p
i1
p
i3
ou
p
i2
p
i4
. Ambas as triangulações são
aceitas.
Uma triangulação de Delaunay deve consistir de no mínimo um triângulo, e esta
condição é garantida pela hipótese de não colinearidade e 3
≤
n
<
∞
.
Define-se como
CH(P)
como o conjunto de triângulos que formam o contorno do
fecho convexo dos pontos que geram o diagrama de Voronoi.
3.4.1 Definição Matemática da Triangulação de Delaunay
Seja
V(P)
um Diagrama de Voronoi generalizado por um conjunto de
n
pontos
distintos
P
={
p
1
, p
2
, ..., p
n
}
⊂
ℝ
2
sendo 3
≤
n
<
∞
, que satisfaça a hipótese de não
colinearidade. Seja
Q
={
q
1
, q
2
, ..., q
n
} o conjunto de vértices de Voronoi em
V(P)
e sejam
x
i1
,
x
i2
, ...,x
iki
os vetores locados para os centróides cujos polígonos de Voronoi partilham do
vértice
q
i
. Este conjunto é definido por:
∈≥===
∑∑
==
},0,1,:{
11
i
ii
kj
k
j
i
k
j
jii
IjondexxxT
λλλ
(3.5)
e seja
{
}
v
n
TTTD ,...,,
21
=
(3.6)
Se
k
i
=3 para todos os
i
∈
I
nv
, chama-se ao conjunto
D
triangulação de Delaunay de
CH(P)
cobrindo
P
. Se nele existe ao menos um
k
i
≥
4, chama-se ao conjunto
D
pré triangulação
de Delaunay de
CH(P)
cobrindo
P
. Particionando-se
T
i
tendo
k
i
≥
4 em
k
i
−2
triângulos por
segmentos que não se interceptam unindo-se os seus vértices, teremos como resultado os
triângulos resultantes por
T
i1
, T
i2
, ..., T
iki −2
. Seja
51
D=
{
T
11
,..., T
1k−2
,... ..., T
n1
,..., T
nk−2
} (3.7)
Chama-se o conjunto
D
de
Triangulação de Delaunay de CH(P) cobrindo todo o
conjunto P,
e os triângulos em
D
de
Triângulos de Delaunay
.
Como foi visto acima, um triângulo de Delaunay é definido como um conjunto
fechado e suas fronteiras consistem de segmentos de retas. Chamam-se estes segmentos de
extremidades de Delaunay. Especificamente, se uma extremidade de Delaunay é partilhada
por dois triângulos de Delaunay, chama-se de uma extremidade interna de Delaunay, caso
contrário ela será chamada de uma extremidade externa de Delaunay. Quando o Diagrama de
Voronoi é não degenerado, uma extremidade de Voronoi corresponde exatamente a uma
extremidade de Delaunay. Conseqüentemente, o número de extremidades de Voronoi em
D
é
o mesmo que o das extremidades de Voronoi em
V
.
Ao contrário de uma extremidade de Voronoi, uma extremidade de Delaunay é sempre
finita. Chamam-se os pontos finais de uma extremidade de Delaunay de vértices de Delaunay.
Obviamente, todo vértice de Delaunay é um gerador de
V(P)
, e conseqüentemente o conjunto
de vértices de Delaunay em
D
é dado por
P
.
Nas figuras abaixo temos a visualização da construção de uma Triangulação de
Delaunay. Na figura 3.9 temos alguns centróides sendo conectados sobre um Diagrama de
Voronoi.
52
FIGURA 3.9: CONSTRUÇÃO DE UMA TRIANGULAÇÃO DE DELAUNAY
FONTE: Elaboração do Autor
Na figura 3.10 tem-se a Triangulação de Delaunay sobre um Diagrama de Voronoi.
FIGURA 3.10: DIAGRAMA DE VORONOI E TRIANGULAÇÃO DE DELAUNAY
FONTE: Elaboração do Autor
Na figura 3.11 observa-se a Triangulação de Delaunay sobre os pontos que antes
formavam o Diagrama de Voronoi.
53
FIGURA 3.11: TRIANGULAÇÃO DE DELAUNAY
FONTE: Elaboração do Autor.
3.5 Propriedades Básicas
3.5.1 Diagrama de Voronoi
a)
Todo polígono
V(p
i
)
de Voronoi é convexo;
b)
V(p
i
)
é ilimitado se e somente se
p
i
estiver no fecho convexo;
c)
Para o diagrama de Voronoi gerado por um conjunto de pontos distintos
P
={
p
1
, p
2
, ..., p
n
} tem-se o seguinte:
c.1. Extremidades de Voronoi são retas infinitas se e somente se
P
for
colinear.
c.2. Extremidade de Voronoi
e(p
i
,p
j
)
(
≠∅
) é uma semi reta se e somente se
P
for não colinear e
p
i
e
p
j
sejam geradores consecutivos da fronteira do
Fecho Convexo ou
CH(P)
.
54
c.3. Suponha-se que
p
i
e
p
j
formem uma extremidade de Voronoi
e(p
i
,p
j
)
.
Então esta extremidade é um segmento de reta finito se e somente se
P
for
não colinear e ao menos um dos
p
i
, p
j
esteja no interior de
CH(P)
.
d)
O ponto gerador mais próximo de
p
i
gera uma extremidade de Voronoi de
V(p
i
)
;
e)
O ponto gerador mais próximo de
p
i
existe nos geradores cujos polígonos de
Voronoi compartilham as extremidades de Voronoi de
V
(
pi
);
f)
O gerador
p
i
é o ponto gerador mais próximo do ponto
p
se e somente se
V
(
p
i
)
contém
p
;
g)
Para todo vértice de Voronoi,
q
i
∈
Q
, em um diagrama de Voronoi, existe um
círculo vazio único
C
i
centrado em
q
i
que passa por três ou mais geradores.
Através da suposição da não degeneração,
C
i
passa por exatamente três
geradores;
h)
O círculo
C
i
na descrito na propriedade anterior é o maior círculo vazio entre
os círculos vazios centrados no vértice
q
i
de Voronoi;
i)
Deixe
n, n
e
e n
v
serem: o número de geradores, as arestas de Voronoi e os
vértices de Voronoi de um diagrama de Voronoi em R
2
, respectivamente
(2
≤
n<
∞
). Então
n
v
−n
e
+n=1;
j)
Deixe
n
k
ser o número de faces
k
-dimensional de Voronoi em um diagrama de
Voronoi
m
-dimensional. Então,
( ) ( )
m
k
k
m
k
n 11
0
−=−
∑
=
(3.8)
55
k)
Deixe
n, n
e
e n
v
serem: o número de geradores, as arestas de Voronoi e os
vértices de Voronoi, respectivamente, de um diagrama de Voronoi em R
2
, e
assume-se que 3
≤
n<
∞
. Então
ne
≤
3
n
−6 (3.9)
nv
≤
2
n
−5 (3.10)
l)
Deixe
n, n
e
, n
v
e
n
c
serem: o número de polígonos de Voronoi, as fronteiras de
Voronoi, os vértices de Voronoi e os polígonos infinitos de Voronoi de um
diagrama
V(P)
de Voronoi, respectivamente, onde 3
≤
n<
∞
e
p
satisfaz a
hipótese da não colinearidade. Então as seguintes relações são válidas:
n
v
≥½
(n−n
c
)+1 (3.11)
n
e
≥3n
v
+n
c
−3 (3.12)
m)
O número comum de fronteiras de Voronoi de um polígono de Voronoi não
excede seis;
n)
Uma tecelagem no plano que consiste em polígonos convexos cujos vértices
são em número de três é um diagrama de Voronoi se e somente se
p
i1
=
p
i2
=...=
p
ik
, assegurado para
i
∈
I
nv
, onde
p
ij
é definido como os pontos de
intersecção em
S
;
3.5.2 Triangulação de Delaunay
Apesar de não fazer parte específica do escopo deste trabalho, serão apresentadas a
seguir algumas propriedades da Triangulação de Delaunay(
Del(P)
):
a)
Del(P)
é o dual com arestas retilíneas do Diagrama de Voronoi
V(P)
;
56
b)
Del(P)
é uma triangulação se nenhum grupo de 4 pontos forem co-circulares.
Cada face é um triângulo (teorema de Delaunay);
c)
Cada triângulo de
Del(P)
corresponde a um vértice de
V(P)
;
d)
Cada aresta de
Del(P)
corresponde a uma aresta de
V(P)
;
e)
Cada vértice de
Del
(
P
) corresponde a um polígono (face) de
V(P)
;
f)
A fronteira de
Del(P)
é o fecho convexo dos centróides;
g)
O interior de cada triângulo (face) de
Del(P)
não contém centróides.
3.6 Generalizações do Diagrama de Voronoi
3.6.1 Diagrama de Voronoi Ponderado
No diagrama normal de Voronoi assume-se naturalmente que os geradores são
indiferentes entre si, ou seja, independentemente da localização e que cada ponto gerador tem
o mesmo peso. Em algumas aplicações práticas, porém, esta suposição pode não ser a melhor.
Em geral, é mais apropriado assumir que os pontos geradores tenham pesos diferentes que
reflitam as suas propriedades variáveis, tais como, o tamanho da população de um povoado, o
número de funções em um
shopping center
, a quantidade de emissões de um poluente, o
número de pessoas atendidas por uma escola, e assim sucessivamente. Esta seção mostra uma
parte da família do Diagrama de Voronoi que, generalizados, levam em conta estes pesos
diferentes em termos de “distância com peso”
d
w
(
p
,
p
i
).
Considere-se um conjunto de pontos distintos:
P
={
p
1
,...,
p
n
}
⊂
R
m
(2
≤
n
<
∞
) (
A
=
P
,
S
=
R
m
) (3.13)
57
e determine-se um peso a cada
p
i
que se relaciona a alguma propriedade variável do fenômeno
a ser estudado. Este peso será representado por um conjunto de parâmetros,
W
i
={
w
i1
,...,
w
in
w
}
(se
n
w
=1, é escrito
w
i
para
W
i
). Com este peso é definida uma distância,
d
w
(
p
,
p
i
) de
p
para
p
i
,
chamada distância com peso que será especificada mais adiante. A região de domínio de
p
i
sobre
p
j
com a distância com peso é escrita como:
Dom(
p
i
,
p
j
)={
p
/
dw
(
p
,
p
i
)
≤
dw
(
p
,
p
j
)}
j
≠
i
(3.14)
( )
( )
\( )
,
n
n
i i j
i I i
V p Dom p p
∈
= ∩
(3.15)
V
(
P
,
d
w
,
R
m
)=
V
w
={
V
(
p
1
),...,
V
(
p
n
)}. (3.16)
Se a região de domínio dada pela equação acima é bem comportada, o conjunto
V
w
resulta num diagrama generalizado de Voronoi. O nome dado a ele é
Diagrama de Voronoi
por Pesos
generalizado por
P
com peso {
W
1
,...,
W
n
}, e ao conjunto
V
(
p
i
) é dada a designação
de
Região de Voronoi por Pesos
associada ao
p
i
.
3.6.2 Diagrama de Voronoi Ponderado por Multiplicação
Este tipo de diagrama de Voronoi por pesos é caracterizado pela distância com peso
dada por:
0 w||,xi-x||
1
)p(p,d
iimw
>=
i
w
(3.17)
Essa distância é chamada de
distância multiplicativa por pesos
ou simplesmente de
MW-distância
. A região de domínio com relação a MW-distância é escrita como:
ji ||},x-x||
w
1
||x-x||
w
1
:{x )p,Dom(p
j
j
i
i
ji
≠≤=
(3.18)
58
FIGURA 3.12: DIAGRAMA DE VORONOI PONDERADO POR
MULTIPLICAÇÃO
FONTE: Okabe
et. al.
(2000, p. 121)
O Diagrama de Voronoi Ponderado por Multiplicação tem as seguintes propriedades:
a)
Uma região MW-Voronoi é um conjunto não vazio; não precisa ser convexo,
ou conectado; e pode ter buraco(s). Uma região MW-Voronoi
V(pi)
é convexa
se e somente se os pesos das regiões MW-Voronoi adjacentes não forem
menores que
w
i
;
b)
Deixe
w
max
=max
j
{w
j
,j
∈
In}
e
P
max
ser o subconjunto de
P
dado por
P
max
={p
j
/w
j
=w
max
}
. Uma região MW-Voronoi
V(p
i
)
é infinita se e somente se
p
i
∈
P
max
e
p
i
estiver sobre a fronteira de
CH(P
max
)
. Se o gerador com o peso
máximo é único, somente uma região MW-Voronoi é infinita;
c)
Duas regiões MW-Voronoi podem compartilhar arestas desconectadas. Uma
fronteira é um arco circular se e somente se os pesos das regiões MW-Voronoi
que compartilham a fronteira forem diferentes; uma fronteira é uma linha reta
59
se e somente se os pesos das regiões MW-Voronoi que compartilham a
fronteira forem iguais.
3.6.3 Diagrama de Voronoi Ponderado por Adição
Um outro tipo de Diagrama de Voronoi ponderado é o caracterizado pela equação:
iiiaw
wxxppd −−=),(
(3.19)
Ela é chamada
Distância Aditiva por Peso
, ou simplesmente
AW-Distance
. A região
de domínio de
p
i
sobre
p
j
com AW-Distance é escrita como:
(
)
{
}
jiwwxxxxxppDom
jijiji
≠−≤−−−= ,:,
(3.20)
A forma da região de dominação varia de acordo com o valor parâmetro
ji
xx −=
α
e
ji
ww −=
β
. Na figura 3.13 abaixo tem-se um exemplo de um Diagrama de Voronoi
Aditivo por Peso.
O Diagrama de Voronoi Ponderado por Adição tem as seguintes propriedades:
a)
O conjunto
V(pi)
é vazio se e somente se
{
}
inji
ijj
wIjwxx −<∈−−
≠
,min
,
(3.21)
b)
O conjunto
V(pi)
é uma semi-reta ou um segmento de reta se e somente se:
{
}
inji
ijj
wIjwxx −=∈−−
≠
,min
,
(3.22)
c)
O conjunto
V(pi)
tem área positiva se e somente se
{
}
inji
ijj
wIjwxx −>∈−−
≠
,min
,
(3.23)
d)
Uma aresta de uma região de Voronoi Ponderada Aditiva ou é um arco
hiperbólico ou um segmento de reta;
60
e)
Se apenas um peso,
w
i
, for diferente dos outros e a relação descrita no item
3.23 for verdadeira, então existe pelo menos uma região de Voronoi Aditiva
por Pesos que será não convexa. Toda região não convexa será “Star-
shaped”(ver figura 3.5).
3.7 Considerações Finais
Neste capítulo foi possível observar alguns princípios e conceitos relativos ao
Diagrama de Voronoi e à Triangulação de Delaunay. Ambos são conceitos muito importantes
na geometria computacional e possuem inúmeras utilidades nos mais diversos campos da
ciência.
FIGURA 3.13: DIAGRAMA DE VORONOI PONDERADO POR ADIÇÃO
FONTE: Elaboração do autor. Entre parênteses estão as coordenadas dos pontos e após
estão os pesos relativos a cada um deles.
61
No tocante ao planejamento urbano, o Diagrama de Voronoi possui uma grande
utilidade, pois pode ser aplicado nos seus vários tipos para resolver uma variedade de
problemas.
Foram descritos algumas propriedades do Diagrama de Voronoi e da Triangulação de
Delaunay, bem como alguns algoritmos para a implementação dos mesmos. Não houve a
intenção de aprofundamento nos conceitos apresentados, pois não era esse o escopo do
trabalho, porém são fundamentos importantes a serem conhecidos e que servem de base para
trabalhos futuros.
Os algoritmos para a construção dos diagramas de Voronoi descritos neste capítulo
podem ser encontrados em Okabe
et. al.
(2000).
No próximo capítulo serão discutidos conceitos de Programação Não-linear e os
métodos para a solução de problemas relativos a eles.
62
4 PROGRAMAÇÃO NÃO-LINEAR
Este capítulo tem por finalidade mostrar os conceitos básicos de programação não
linear que serão importantes para a solução do problema.
4.1 O Problema da Programação Não Linear
Os problemas de localização tratados neste estudo se enquadram nos tipos de
problemas de otimização matemática denominados “Problemas de Programação Não-Linear”.
Nesta seção serão descritos os conceitos básicos da Programação Não Linear. Para
maiores detalhes, consultar Luenberger (2005) e Frielander (1994).
O problema de programação não-linear é definido matematicamente como:
1
1
,...,
min ( ,..., )
n
n
x x
f x x
(4.1)
Sujeito a
1
( ,..., ) 0
i n
g x x
≤
, i=1, ... , m
1
(4.2)
1
( ,..., ) 0
i n
g x x
=
, i=m
1
+1, m
1
+ m
2
(4.3)
A primeira equação acima é a função objetivo. As equações g
i
são chamadas
restrições. Se m
1
+m
2
= 0 então o problema é denominado “Problema de Programação Não-
linear Sem Restrições”. Porém, se m
1
+m
2
≥
1 então o problema é denominado “Problema de
Programação Não-linear Com Restrições”. Como maximizar f(x) é o mesmo que minimizar –
f(x) então, por simplicidade, consideremos apenas os problemas de minimização. O mesmo
raciocínio se aplica às restrições: como g(x)
≥
0 é equivalente a -g(x)
≤
0, serão apenas
consideradas as relações = e
≤
nas equações de restrições. Por simplificação, utilizamos a
notação f(x) e g(x) onde x
T
=(x
1
,...,x
n
) é um vetor n-dimensional no espaço Euclidiano
n
»
.
63
A região
n
S
⊂
»
onde as restrições são atendidas é chamada de “Região Factível” ou
“Região de Viabilidade”. No caso das restrições apresentadas acima a região S é dada por:
{
}
1 1 1 2
| ( ) 0, 1,..., ; ( ) 0, 1,...,
i i
S x g x i m g x i m m m
= ≤ = = = + +
(4.4)
Considere-se um ponto
*
x S
∈
. Suponha-se que exista
0
ε
>
tal que f(x)
≥
f(x
*
)
para
todo
x S
∈
tal que
*
x x
ε
− <
. Pode-se dizer então que x
*
é um mínimo local de f.
Se existe um ponto
*
x S
∈
tal que f(x)
≥
f(x
*
) para todo
x S
∈
, então este ponto x
*
é
um mínimo global de f. E se f(x) > f(x
*
) para todo
x S
∈
e
*
x x
≠
, então x
*
é um mínimo
global estrito em S.
4.1.1 Condições de Otimalidade
Para complementar o estudo, é necessário analisar as condições de otimalidade para
problemas de minimização sem restrições, por ser o caso a ser resolvido neste trabalho.
Seja C
k
o conjunto de funções
:
n
f →
» »
tais que todas as derivadas de ordem
menor ou igual a k são contínuas.
Seja
1
: ,
f f C
→ ∈
» »
. Se x
*
é um mínimo local de f em
»
, então f’(x*)=0.
Seja
2
: ,
f f C
→ ∈
» »
. Se x
*
é um mínimo local de f em
»
, então f’(x*)=0 e
f’’(x*)=0.
São condições necessárias de primeira ordem:
Seja
1
: ,
n
f f C
→ ∈
» »
. Se x
*
é um mínimo local de f em
n
»
, então
*
( ) 0
f x
∇ =
.
Onde:
( )
( )
1
( )
n
f
x
x
f x
f
x
x
∂
∂
∇ =
∂
∂
(4.5)
64
São condições necessárias de segunda ordem:
Seja
2
: ,
n
f f C
→ ∈
» »
. Se x
*
é um mínimo local de f em
n
»
, então
*
( ) 0
f x
∇ =
e
2 *
( )
f x
∇
é semi-definida positiva, ou seja,
2 *
( ) 0
t
x f x
∇ ≥
para todo
n
x ∈
»
.
Onde
2
( )
f x
∇
é chamada de Matriz Hessiana de f e é definida por:
2
2
( )
( )
i j
f x
f x
x x
∂
∇ =
∂ ∂
(4.6)
São condições suficientes de segunda ordem:
Seja
2
: ,
n
f f C
→ ∈
» »
. Se
* * 2 *
, ( ) 0 e ( ) 0
n
x f x f x
∈ ∇ = ∇ >
»
, então x
*
é um
mínimo local estrito de f em
n
»
.(Frielander, 1994)
4.1.2 Definição de Convexidade
Após reconhecer um mínimo local não é muito fácil saber se ele é também um mínimo
global. Uma das maneiras mais simples é através de uma característica especial da função
analisada: a sua convexidade.
Um subconjunto
n
S ⊂
»
é convexo se e somente se para todo o
[
]
, , 0,1
x y S
λ
∈ ∈ se
verifica que
(
)
1
x y S
λ λ
+ − ∈
(Frielander, 1994).
Uma função f definida em um conjunto convexo S é convexa se e somente se para
todo
[
]
, , 0,1
x y S
λ
∈ ∈ se verifica que
(
)
(
)
(
)
(
)
(
)
1 1
f x y f x f y
λ λ λ λ
+ − ≤ + − .
Para todo
(
)
0,1
λ
∈
e
x y
≠
tem-se que
(
)
(
)
(
)
(
)
(
)
1 1
f x y f x f y
λ λ λ λ
+ − < + −
então pode-se dizer que f é estritamente convexa.
65
4.1.3 Funções Convexas Diferenciáveis
A seguir serão enumeradas algumas características das funções convexas que são
diferenciáveis.
Seja
1
f C
∈
e seja S também convexo. A função f é convexa em S se e somente se
para todo
,
x y S
∈
tem-se que
(
)
(
)
(
)
(
)
t
f y f x f x y x
≥ + ∇ −
. (4.7)
Seja
2
f C
∈
e seja
n
S ⊂
»
e convexo tal que
o
S
≠ ∅
, onde
o
S
é o conjunto interior de
S
. Então
f
é convexa se e somente se
2
( ) 0
f x
∇ ≥
para todo
x S
∈
.(Frielander, 1994)
Seja
f
uma função convexa definida em
S
convexo. Então:
a)
O conjunto
S
Γ ⊂
onde
f
tem o seu valor mínimo é convexo;
b)
Qualquer mínimo local de
f
é um mínimo global de
f
.
Seja
1
f C
∈
uma função convexa e definida em um conjunto
S
também convexo. Se
existe
*
x S
∈
tal que para todo
y S
∈
tem-se que
(
)
(
)
* *
0
t
f x y x
∇ − ≥
, então
x
*
é um mínimo
global de
f
em
S
.
4.2 Métodos de Solução de Problemas de Programação Não Linear
Problemas de programação não-linear com funções não convexas costumam ser de
difícil solução. Para resolver estes problemas existem vários métodos, dentre os quais o
método do Gradiente, o método do Gradiente Conjugado e o método de Davidon-Fletcher-
Powell, conhecido como método DFP (Luenberger (2005) e Press
et. al.
(2002)).
Existem também os critérios para o cálculo do tamanho do passo. As regras para o
cálculo do tamanho do passo implementadas são as de Wolfe, Goldstein e Armijo, descritas
em Luenberger (2005).
Todos esses métodos são descritos a seguir.
66
4.2.1 Método do Gradiente
O método do Gradiente, consiste em, a partir de um ponto inicial, realizar um
deslocamento em direção a um outro ponto onde o valor da função seja menor que o inicial.
Esse procedimento é repetido até que uma condição de parada seja atingida. O segredo do
processo está em escolher
d
k
na direção
(
)
k
f x
−∇
e, a seguir, o tamanho do deslocamento a
ser efetuado. A seguir descreve-se um algoritmo para o método.
Como já foi observado anteriormente, se existe
n
x ∈
»
e
(
)
0
f x
∇ ≠
então pode-se
dizer que em toda a vizinhança de
x
existe um ponto
n
z
∈
»
tal que
(
)
(
)
f z f x
<
.
O algoritmo que representa o método da descida é o seguinte:
a)
Escolha um ponto inicial
k n
x ∈
»
sendo
1
k
=
b)
Determine a direção
k
d
no ponto
x
k
;
c)
Determine o tamanho do deslocamento
k
α
no ponto
x
k
e na direção
k
d
;
d)
Faça
1
k k k k
x x d
α
+
← +
;
e)
Se
1
0
k k
x x
ε
+
− < ≈
, então
x
k+1
é o ponto de mínimo, senão faça
1
k k
← +
e
retorne ao passo
b
.
Para a execução do passo
b
, ou seja, a escolha da direção a ser seguida (
d
k
), escolhe-se
a direção do gradiente. Ou seja:
( )
(
)
( )
1
k
k
k k
k
k
n
f x
x
d f x
f x
x
∂
∂
= −∇ = −
∂
∂
(4.8)
Para o cálculo de
k
α
no passo
c
utilizamos o mesmo método descrito na seção 4.2.4.
67
Uma das características desse método é a sua baixa velocidade de convergência. Para
sanar esse problema outros métodos foram desenvolvidos. Alguns deles são descritos a seguir.
4.2.2 Método das Direções Conjugadas (Gradiente Conjugado)
O método das Direções Conjugadas foi criado visando à resolução de problemas
quadráticos. As técnicas desenvolvidas funcionaram tão bem que foram estendidas para
problemas genéricos. Um dos métodos mais populares é o método do Gradiente Conjugado.
Esse método tem provado ser extremamente efetivo na solução de problemas de programação
não-linear e é considerado um dos melhores métodos disponíveis no momento (Luenberger
(2005)). Ele consiste na seleção de sucessivos vetores direção como uma versão conjugada
dos sucessivos gradientes encontrados ao longo do processo de solução.
Cada nova direção do Gradiente Conjugado é uma combinação linear de resíduo
corrente com a direção anterior, ou seja, ele consiste em um método iterativo de busca do
mínimo local da função, gerando aproximações para a solução e, em cada iteração do método,
dois produtos internos são realizados para que se calculem dois escalares definidos de forma
que a seqüência obedeça a condições de ortogonalidade.
Modificações, como forma de melhorar a velocidade de convergência no método do
gradiente conjugado, são propostas por Fletcher e Reeves (1964). O seu algoritmo é muito
parecido com o anterior, com apenas algumas modificações. Ele é descrito a seguir:
a)
Escolha um ponto inicial
; 1
k n
x k
∈ =
»
e determine o número total de
iterações
n
desejado;
b)
Determine a direção
k
d
no ponto
x
k
;
c)
Determine o tamanho do deslocamento
k
α
no ponto
x
k
e na direção
k
d
;
d)
Faça
1
k k k k
x x d
α
+
← +
;
68
e)
Se
1
0
k k
x x
ε
+
− < ≈
, então
x
k+1
é o ponto de mínimo, senão se
k n
≤
então
1
k k
← +
e retorne ao passo
b
.
Para o cálculo de
k
α
no passo
c
utiliza-se o mesmo método descrito na seção 4.2.4.
Para a execução do passo
b
pela primeira vez, ou seja, a escolha da direção a ser seguida (
d
k
),
escolhemos a direção do gradiente, ou seja, de maneira idêntica ao algoritmo anterior. Para as
execuções subseqüentes, utiliza-se o seguinte método:
(
)
1 1
k k k k
d f x d
β
+ +
= −∇ +
(4.9)
Onde
k
β
é calculado da seguinte maneira:
1 2
2
( ) ( )
( )
t
t k k k
k
k k k
f x f x d
d f x d
β
+
−∇ ∇
=
∇
(4.10)
Este método é um pouco mais complicado que o método da descida, porém converge
com um número finito de iterações.
4.2.3 Método Davidon-Fletcher-Powell
É um dos métodos chamado Quase-Newton que tratam os inconvenientes relacionados
à possibilidade de singularidade da matriz Hessiana que impossibilitam o cálculo de sua
inversa. Tais inconvenientes são amenizados quando são utilizados esses métodos. Eles
buscam estimar um valor aproximado para a matriz Hessiana com base em informações da
derivada de primeira ordem.
O método foi inicialmente proposto por Davidon (1959), mas desenvolvido por
Fletcher, em 1963. O método de Davidon-Fletcher-Powell, conhecido como método DFP
(Luenberger (2005); Press
et. al.
(2002)), determina uma aproximação para a matriz Hessiana,
através da seguinte expressão:
69
1
t t
t t
k k k k k k
k k
k k k k k
B B
B B
B
δ δ γ γ
δ γ γ γ
+
= + −
(4.11)
Onde
1
k x k
x x
δ
+
= −
e (4.12)
(
)
(
)
1
k k k
f x f x
γ
+
= ∇ −∇
(4.13)
O algoritmo é o seguinte:
a)
Escolha um ponto inicial
; 1
k n
x k
∈ =
»
e determine o número total de
iterações
n
desejado;
b)
k
B I
=
(Matriz Identidade);
c)
Determine a direção
(
)
k k k
d B f x
= − ∇
;
d)
Faça
1
k k k k
x x d
α
+
← +
, tal que
(
)
k k k
f x d
α
+
seja mínimo para
0
α
>
;
e)
Calcule
1
k
B
+
de acordo com a equação 4.11;
f)
Se
1
0
k k
x x
ε
+
− < ≈
, então
x
k+1
é o ponto de mínimo, senão se
k n
≤
então
1
k k
← +
e retorne ao passo
c
.
Para o cálculo de
k
α
no passo
d
utilizamos o método descrito na próxima seção.
4.2.4 Determinação do Tamanho do Deslocamento
Após determinar a direção do deslocamento, falta determinar o tamanho dele (passo
c
dos algoritmos do Gradiente e do Gradiente Conjugado e passo
d
do algoritmo Davidon-
Fletcher-Powell). Os métodos utilizados neste trabalho são os que utilizam as regras de
Armijo, Goldstein e Wolfe conforme descrito em Luenberger (2005).
70
A idéia essencial da regra de Armijo é que ela deve primeiramente garantir que o valor
de
α
selecionado não seja muito grande, para em seguida garantir que também não seja
demasiadamente pequeno.
Seja
α
a distância de
x
k
ao longo da linha
L
k
na direção
d
k
, então
(
)
( )
k k k
h f x d
α α
= +
(4.14)
A regra de Armijo é implementada considerando a função
(0) ' (0)
k k
h h
ε α
+
para um
valor fixo de
,0 1
ε ε
< <
.Um valor de
α
é considerado não muito grande se o valor da função
correspondente obedece a seguinte condição:
(
)
(0) ' (0)
k k k
h h h
α ε α
≤ +
(4.15)
Para assegurar que
α
não é demasiadamente pequeno, um valor
1
η
>
é selecionado,
e o valor de
α
é considerado não demasiadamente pequeno se obedecer a seguinte condição:
(
)
(0) ' (0)
k k k
h h h
ηα ε ηα
> +
(4.16)
Isto significa que se
α
é aumentado por um fator
η
, ele não atenderá a condição 4.15.
Na prática, o algoritmo para o teste de Armijo, descrito em Luenberger (2005) é o seguinte:
a)
Escolha um ponto inicial
0
0
α
>
;
b)
Se o valor de
α
escolhido satisfaz a condição 4.15, então multiplique o valor
de
α
por
η
até a condição 4.15 não estiver mais satisfeita. O penúltimo valor
encontrado é selecionado;
c)
Se o valor de
α
escolhido não satisfaz a condição 4.15, então divida o valor de
α
por
η
até que a condição 4.15 esteja satisfeita. O último valor encontrado é
selecionado;
Outro teste bastante utilizado é o teste de Goldstein. Ele está descrito a seguir
conforme Okabe
et. al.
(2000).
Seja
α
a distância de
x
k
ao longo da linha
L
k
na direção
d
k
, então
71
(
)
( )
k k k
h f x d
α α
= +
(4.17)
A linha tangencial a
(
)
k
h
β α
=
quando
0
α
=
é dada por
( ) ( )
(
)
0
0
k
k k
h
h
τ α α
α
∂
= +
∂
(4.18)
Agora consideremos duas linhas passando pelo ponto (0,
h
k
(0)) cujas inclinações são
um pouco menores que a da equação acima. Essas equações são escritas assim:
( ) ( )
(
)
0
0 ; 1, 2
k
k k
i i
h
h i
η α µ α
α
∂
= + =
∂
(4.19)
onde
1 2
0 1
µ µ
< ≤ <
.
O algoritmo para determinar o tamanho do deslocamento
k
α
segundo a regra de
Goldstein é o seguinte:
a)
Escolha um ponto inicial
0
0
α
>
sendo
0
i
←
;
b)
(
)
0
1
i
i
α α
← +
;
c)
Se
(
)
(
)
2
k i k i
h
η α α
≤
então vá para o passo
d
; senão
1
i i
← +
e vá para o passo
b
;
d)
Se
(
)
(
)
1
k i k i
h
α η α
≤
, então
i
α
é o melhor tamanho; senão
(
)
1
2
i i
i
α α
α
−
+
←
e
vá para o passo
c
;
O teste de Wolfe é utilizado quando a derivada da função objetivo, bem como os seus
valores, pode ser facilmente calculada. Um deslocamento
k
α
satisfaz as condições de Wolfe
se ele satisfaz as seguintes inequações:
(
)
( )
k k k
h f x d
α α
= +
(4.20)
(
)
1
(0) ' (0)
k k k
h h h
α η α
≤ +
(4.21)
( ) ( )
2
' ' 0
t t
k k
d h d h
α η
≥
(4.22)
72
Onde
1 2
0 1
η η
< < <
.
4.2.5 Método Simulated Annealing (Metrópolis)
O método chamado Metrópolis ou “
Simulated Annealing
” consiste em uma técnica de
busca local probabilística que aceita movimentos de piora para escapar de ótimos locais
(Dowsland (1993)). Ele é fundamentado em uma analogia com a termodinâmica, simulando o
resfriamento de um conjunto de átomos aquecidos, operação essa que é conhecida como
recozimento.
FIGURA 4.1: ALGORITMO
SIMULATED ANNEALING
s
0
←
solução inicial;
T
0
←
temperatura inicial;
α
←
taxa de resfriamento;
SAmax
←
número máximo de iterações para se atingir o equilíbrio;
s
←
s
0
;
s'
←
s
;
T
←
T
0
;
IterT
←
0; {Número de iterações na temperatura T}
Enquanto (T > 0) faça
Enquanto (IterT < SAmax) faça
IterT
←
IterT + 1;
s’ ←
um vizinho qualquer de
s
∈
N (s)
;
∆
=
f(s’)
–
f(s)
;
Se (
∆
> 0)
então
s
←
s’
;
Se
f(s’)
> f(
s
*
) então
s
*
←
s’
;
senão
x
←
um valor aleatório no intervalo [0,1];
Se x < e
∆/T
então
s
←
s’
;
fim-se;
fim-enquanto;
T
←
α
×
T;
IterT
←
0;
fim-enquanto;
Retorne
s
*
;
FONTE: Dowsland (1993) e Press
et. al.
(2002)
Essa técnica começa com uma busca a partir de uma solução inicial qualquer, cujo
procedimento principal consiste em uma repetição que gera, em cada iteração, um único
73
vizinho
s’
da solução corrente
s
. Se este vizinho for melhor que o original ele é aceito e
substitui a solução atual. Se ele for pior por uma quantidade
∆
, ele é aceito com uma
probabilidade
e
∆
/T
, onde um parâmetro chamado de Temperatura (
T
) decresce gradualmente
conforme o progresso do algoritmo. Esse processo é repetido até que a temperatura (
T
) seja
tão pequena que mais nenhum movimento seja aceito. A melhor solução encontrada durante a
busca é tomada como uma boa aproximação para a solução ótima.
O pseudocódigo do algoritmo é apresentado na figura 4.1. Detalhes adicionais desse
algoritmo podem ser encontrados em Dowsland (1993) e Press
et. al.
(2002).
O método “
Simulated Annealing
” é muito utilizado em problemas de grande
magnitude, especialmente aqueles em que o mínimo global está escondido entre vários
mínimos locais (Press
et. al.
(2002)).
4.2.6 Método Numérico para o Cálculo da Derivada
Encontrar a derivada de uma função objetivo nem sempre é trivial. Para evitar esse
tipo de problema, optou-se por calcular a derivada da função numericamente, através de um
algoritmo desenvolvido por Ridders, descrito em Press
et. al.
(2002).
Partindo da definição da derivada, que é o limite da equação 4.23 quando
0
h
→
(
)
(
)
'
( )
f x h f x
f x
h
+ −
≈
(4.23)
Tem-se uma forma simétrica para minimizar o erro, que é:
(
)
(
)
'
( )
2
f x h f x h
f x
h
+ − −
≈
(4.24)
74
FIGURA 4.2: ALGORITMO PARA CÁLCULO NUMÉRICO DA DERIVADA
Início
hh
←
h;
A[0,0]
←
(f(x+hh) – f(x-hh)) / (2*h);
erro
←
infinito;
Para i=1 até N faça {
N representa o tamanho da matriz de resultados
}
hh
←
hh/ p {
p representa o passo de redução de h
};
A[0,i]
←
(f(x+hh) – f(x-hh)) / (2*h);
fac
←
hh * hh;
Para j=1 até i faça
A[j,i]
←
( A[j-1,i] * fac – A[j-1,i-1]) / (fac-1.0);
fac
←
fac * (hh * hh);
erro_aux
←
Max( Abs(A[j,i]-A[j-1,i], Abs(A[j,i]-A[j-1,i-1]));
Se erro-aux
≤
erro então
erro
←
erro_aux
Resp
←
A[j,i];
fim-se;
fim_para;
fim-para;
Retorne Resp;
FONTE: Press
et. al.
(2002)
Partindo da equação 4.24 como ponto inicial, temos na figura 4.2 o algoritmo para o
cálculo numérico da derivada.
4.3 Considerações Finais
Neste capítulo foram descritos os conceitos de programação não-linear e os métodos
que serão utilizados para resolver esses problemas.
No próximo capítulo será descrito o problema que é o objeto deste trabalho.
75
5 DEFINIÇÃO DO PROBLEMA
Este trabalho visa otimizar o espaçamento das paradas de transporte coletivo com o
objetivo de reduzir o tempo médio de viagem dos passageiros. A idéia principal é utilizar
conceitos de Diagrama de Voronoi e de Programação Não-linear para encontrar o
espaçamento ideal entre as paradas de transporte coletivo numa região urbana considerando a
densidade demográfica da região como parâmetro para a otimização. O objetivo principal será
minimizar o tempo médio de viagem dos usuários do sistema.
A idéia deste trabalho é utilizar o tempo de viagem dos usuários do sistema como
parâmetro para de estabelecer um padrão de espaçamento entre as paradas, uma vez que a
maioria das políticas de espaçamento existentes não possui um embasamento bem definido.
As duas linhas de ônibus que serão utilizadas para testar o modelo proposto possuem
características diferentes. A primeira é uma linha hipotética, na zona oeste de São Paulo, que
partiria do bairro da Lapa e alimentaria a estação Fradique Coutinho, na linha 4 do Metrô de
São Paulo.
A segunda é uma linha já existente, que liga a região sul do município de São Paulo ao
Terminal Parque Dom Pedro II, no centro da cidade.
Elas foram escolhidas por terem as características desejadas para o teste e avaliação do
modelo. Essas características serão explicadas a seguir.
5.1 Município de São Paulo
As duas linhas utilizadas neste estudo estão localizadas no município de São Paulo. O
município possui, segundo o censo do IBGE de 2000, uma população estimada em 10
76
milhões, quatrocentos e trinta e quatro mil, duzentos e cinqüenta e dois habitantes
(10.434.252), distribuídos em uma área de 150.900 hectares, ou 1.509 km². A densidade
demográfica do município está descrita na tabela 5.1 com a densidade dos bairros que são
atendidos pelas duas linhas. A coluna Linha da tabela informa qual das linhas atende aquele
bairro.
A tabela completa pode ser vista no Anexo 5.
TABELA 5.1: DENSIDADE DEMOGRÁFICA DO MUNICÍPIO DE SÃO PAULO
Área Total, População Residente e Densidade Demográfica
Município de São Paulo e Distritos Municipais
Ano de 2000
Densidade Populacional
Distritos Linha
População
Área em
Hectare
Hab/Ha Hab/m²
Hab/Km²
Município de S.
Paulo 10.434.252
150.900
69,15
0,0069
6.915
Alto de Pinheiros 1
44.454
770
57,73
0,0058
5.773
Cambuci 2
28.717
390
73,63
0,0074
7.363
Cursino 2
102.089
1.280
79,76
0,0080
7.976
Ipiranga 2
98.863
1.050
94,16
0,0094
9.416
Lapa 1
60.184
1.000
60,18
0,0060
6.018
Liberdade 2
61.875
370
167,23
0,0167
16.723
Perdizes 1
102.445
610
167,94
0,0168
16.794
Pinheiros 1
62.997
800
78,75
0,0079
7.875
República 2
47.718
230
207,47
0,0207
20.747
Sacomã 2
71.179
1.420
182,51
0,0183
18.251
Sé 2
20.115
210
95,79
0,0096
9.579
FONTE: Prefeitura Municipal de São Paulo – IBGE Censos Demográficos 2000.
O mapa do município com as divisões regionais e as subdivisões dos bairros está no
Anexo 6.
5.1.1 O Transporte Coletivo em São Paulo
O órgão responsável pela supervisão e controle do transporte coletivo na cidade de
São Paulo é a São Paulo Transportes S.A. – SPTrans. A SPTrans é oriunda da antiga
Companhia Municipal de Transportes Coletivos – CMTC que operava uma frota própria de
77
veículos na cidade. Hoje a SPTrans apenas administra o sistema de transporte coletivo da
cidade, o qual detém cerca de 55% de todas as viagens motorizadas de transporte coletivo do
município.
Em 2008 operavam no sistema 16 consórcios – formados por empresas e cooperativas
– que são responsáveis por 15 mil veículos para atender 1300 linhas, transportando um total
de 6 milhões de passageiros por dia útil.(Fonte: www.sptrans.com.br )
5.2 Linha 4 do Metrô de São Paulo
A linha 4 do Metrô da cidade de São Paulo ligará o bairro da Luz ao bairro de Vila
Sônia, na Zona Oeste, passando pela região da Consolação, Avenida Paulista e Pinheiros.
Com extensão de 12,8 quilômetros e 11 estações, a Linha 4-Amarela será implantada
em duas etapas:
a)
A primeira prevê a construção e inauguração de seis estações: Butantã,
Pinheiros, Faria Lima, Paulista, República e Luz; estrutura das estações
intermediárias Fradique Coutinho, Oscar Freire e Higienópolis-Mackenzie;
construção e inauguração do pátio de manutenção Vila Sônia.
b)
A segunda prevê o acabamento e a inauguração das estações intermediárias:
Fradique Coutinho, Oscar Freire e Higienópolis-Mackenzie; construção e
inauguração de duas estações: São Paulo-Morumbi e Vila Sônia. Haverá
integração com as linhas 1-Azul, 2-Verde e 3-Vermelha nas estações Luz,
Paulista, e República, respectivamente.
78
FIGURA 5.1: MAPA DA LINHA 4 DO METRO DE SÃO PAULO COM A ESTAÇÃO
ESCOLHIDA
FONTE: Companhia do Metropolitano de São Paulo – Metrô.
Esta linha foi escolhida porque está localizada numa área de alta densidade
populacional e as estações são separadas numa distância de 1 Km a 1,5 Km
aproximadamente.
Para efeito do estudo, analisaremos a Estação Fradique Coutinho, pois ela fica a 1,5
Km de distância das estações próximas a ela e se situa numa área de grande densidade
populacional.
As duas linhas que serão objeto deste estudo serão descritas a seguir.
5.3 Linha Alimentadora da Linha 4 do Metrô de São Paulo
Esta linha foi concebida de maneira a ter um traçado relativamente reto e atravessar
vários bairros com diferentes densidades demográficas.
Conforme foi visto no Capítulo 2, a distância máxima que uma pessoa deve se
deslocar a pé para pegar um ônibus varia entre 300 e 600m. Portanto, se cada estação desse
trecho for alimentada por duas linhas perpendiculares ao sentido da linha do metrô, conforme
79
está esquematizado na Figura 5.2, a distância máxima que um passageiro deverá percorrer
será de 585 metros aproximadamente. Isso se assumirmos que os pontos de parada estarão
espaçados em no máximo 500 metros.
FIGURA 5.2: ESQUEMA DAS LINHAS DE ÔNIBUS EM RELAÇÃO À LINHA DO
METRÔ.
FONTE: Elaboração do autor.
Esse cálculo é feito a partir da Distância Euclidiana medida a partir do centro do
retângulo formado pelas quatro paradas mais próximas do usuário até uma delas (Figura 5.2).
Essa distância medida é multiplicada por um fator de correção, pois o usuário não poderá se
deslocar em linha reta o tempo todo. O fator de correção utilizado neste trabalho é 1,3
(conforme Novaes, 2000). Portanto, a distância máxima que um usuário deverá se deslocar até
a parada mais próxima será de: 450,7 x 1,3 = 585,9 m.
A figura 5.3 mostra o traçado da linha a ser estudada. O seu itinerário completo
encontra-se no Anexo 2.
Linha do Metrô
Ponto de
Parada
Linha de
ônibus
80
FIGURA 5.3: TRAÇADO DA LINHA ALIMENTADORA
FONTE: Elaboração do autor com o auxílio do Google Maps.
5.3.1 Modelo Matemático
O modelo para esta linha baseia-se na hipótese de que os usuários do sistema de
transporte coletivo da região utilizem as linhas de ônibus para chegar até a estação do metrô e
de lá sigam viagem até o seu destino final.
A figura 5.4 mostra o modelo esquemático das linhas de ônibus em relação à linha do
metrô num plano cartesiano. A função de densidade populacional
Φ
será definida em relação
a região de onde parte o usuário.
81
FIGURA 5.4: GEOMETRIA DA ÁREA DE SERVIÇO
FONTE: Elaboração do Autor.
A área de abrangência das linhas em questão será definida por
S
. O conjunto de
estações existentes nas linhas é representado pelo conjunto
s
i
onde
n
i I
∈
sendo o número de
estações
n+1
. Existe também a variável
d
i
que representa a distância da estação
i
até a estação
i-1
.
Suponha-se que um usuário se encontra num ponto
r(x
0
,y
0
)
e deseja ir até a estação
s
1
(x
1
,y
1
),
sendo
1
,
r s S
∈
. A distância
D
a
a ser percorrida será calculada da seguinte forma:
2 2
1 1 0 1 0
* * ( ) ( )
a
D k r s k x x y y
= − = − + − (5.1)
Neste caso
k
é uma constante de correção já explicada na seção anterior.
O tempo
T
a
que o usuário leva para se deslocar até a estação é calculado pela divisão
da distância pela velocidade do usuário a pé. Ou seja:
a
a
a
D
T
V
=
(5.2)
y
x
Linha do
Metrô
Linhas de
ônibus
Pontos de
Parada
S
1
S
2
S
3
r
d
1
82
Conforme estudado no Capítulo 2, Saka (2001) demonstrou como calcular o tempo
que o ônibus leva para chegar até o seu destino (a estação do metrô). Ele é calculado da
seguinte maneira:
bus ad ed c o
T T T T T
= + + +
(5.3)
Onde:
a)
T
ad
= tempo de aceleração e desaceleração;
b)
T
ed
= tempo de embarque e desembarque de passageiros;
c)
T
c
= tempo de atraso devido a dispositivos de controle de tráfego (Sinais de
trânsito, etc.);
d)
T
o
= tempo de viagem em velocidade normal de tráfego.
Adaptando para o problema em questão, uma vez que a intenção é calcular o
espaçamento ideal entre os pontos de ônibus, podem-se eliminar algumas variáveis que não
afetarão o resultado do modelo. Temos então que o tempo de viagem do ônibus do ponto
s
i
até
o seu destino é descrito da seguinte maneira:
(
)
( )
*
120
i
b a d
i
s i p
a d b
V X X
y
T i hq t
X X V
τ
+
= + + +
(5.4)
onde
a)
V
b
= velocidade média do ônibus durante o percurso em m/s(metros por
segundo);
b)
X
a
= Taxa de aceleração em m/s²;
c)
X
d
= Taxa de desaceleração em m/s²;
d)
t
p
= Tempo de abertura e fechamento das portas em minutos;
e)
q
i
= Quantidade de passageiros por hora que embarcam ou desembarcam no
ponto
i
;
f)
τ
= Tempo médio de embarque ou desembarque por passageiro;
83
g)
h
= Intervalo entre os ônibus;
h)
y
i
= Distância da parada
i
até o destino final (Estação do Metrô).
O primeiro termo da equação é tempo de aceleração e desaceleração, ou seja:
(
)
120
b a d
ad
a d
V X X
T
X X
+
=
(5.5)
O segundo termo é o tempo de embarque e desembarque de passageiros, ou seja:
(
)
ed i p
T hq t
τ
= +
(5.6)
O último termo é o tempo gasto em velocidade normal de cruzeiro:
i
o
b
y
T
V
=
(5.7)
Assim sendo, o tempo total de viagem do usuário até a estação do metrô é dado pela
seguinte equação:
(
)
( )
*
120
b a d
a i
total i p
a a d b
V X X
D y
T i hq t
V X X V
τ
+
= + + + +
(5.8)
ou
(
)
( )
* *
120
i b a d
i
total i p
a a d b
r s V X X
y
T k i hq t
V X X V
τ
− +
= + + + +
(5.9)
ou
i
i
total s
a
r s
T k T
V
−
= +
(5.10)
Assumindo que todo o usuário procurará utilizar a parada que minimize o tempo de
viagem até o destino final, ele utilizará a parada que satisfaça a seguinte equação:
i
i
i s
a
r s
Min k T
V
−
+
(5.11)
Como resultado dessa escolha, toda parada terá a sua área de abrangência definida por:
84
| ; ; ,
i j
j
i
i s s n
a a
r s
r s
V r k T k T i j i j I
V V
−
−
= + ≤ + ≠ ∈
(5.12)
que vem a ser, conforme descrito no Capítulo 2, uma região de Voronoi Ponderada Aditiva.
Como se verifica através da Figura 5.5, o usuário poderá escolher entre duas linhas de
ônibus, a fim de chegar ao seu destino final. Desse modo, a função que define o tempo total
de viagem de todos os usuários na região estudada será dada a partir da função de densidade
populacional que varia em função das variáveis x e y. Neste caso, tem-se uma variação no
tempo de viagem entre uma linha e outra devido aos diferentes tempos utilizados nas paradas
e também pelos diferentes números de paradas existentes.
O tempo total de viagem de todos os passageiros da região estudada será dado por:
( )
1
( , )
,
i
i
n
i
s
V
i
a
r x y s
T k T x y ds
V
φ
=
−
= +
∑
∫
(5.13)
Pode-se, então, definir o problema de otimização como sendo:
( )
1 2
, ,...,
1
( , )
min ,
i
i
n
n
i
s
V
d d d
i
a
r x y s
k T x y ds
V
φ
=
−
+
∑
∫
(5.14)
Este é um problema de programação não linear sem restrições.
Porém, ao se analisar o problema detalhadamente, pode-se perceber que é muito pouco
provável que exista realmente uma diferença entre as densidades populacionais em uma
distância relativamente pequena (500m). Ao se assumir que a diferença entre as densidades
populacionais das regiões atendidas por duas linhas adjacentes é desprezível, pode-se supor
que o número de paradas e o espaçamento entre elas serão o mesmo (para as duas linhas
adjacentes). Isto faz com que o tempo de viagem de um ônibus de uma parada s
i
até o destino
final seja o mesmo que o de uma parada eqüidistante do destino final de uma linha adjacente.
85
FIGURA 5.5: ÁREA DE ABRANGÊNCIA DE UM USUÁRIO
FONTE: Elaboração do Autor.
Como foi visto no Capítulo 2, se um diagrama de Voronoi é gerado por um conjunto
de pontos distintos
P={p
1
, p
2
, ..., p
n
}
e, sendo esses pontos colineares, pode-se afirmar que as
arestas do Diagrama de Voronoi são retas infinitas.
Como as linhas de ônibus são praticamente em linha reta e as estações de uma linha
possuem o mesmo espaçamento se comparadas com as linhas adjacentes a ela, pode-se dizer
que a aresta da região de Voronoi entre as estações de uma linha com as estações da linha
adjacente será uma reta. A figura 5.6 mostra como ficam as arestas dos diagramas de Voronoi
referentes às paradas se elas forem consideradas colineares.
y
x
S
1
S
2
S
3
r
S
n
S
n-1
S
n-2
86
FIGURA 5.6: ARESTAS DOS DIAGRAMAS DE VORONOI REFERENTES ÀS
PARADAS DE ÔNIBUS
FONTE: Elaboração do autor.
Assim sendo, pode-se limitar o escopo do estudo para uma única linha de ônibus. A
região de abrangência dela estará limitada pelas arestas das regiões de Voronoi existentes
entre ela e as linhas adjacentes, as quais estarão numa distância média entre as duas linhas.
5.4 Linha 5108-10 – Jd. Celeste / Parque Dom Pedro II
A linha 5108-10, Jd. Celeste/Parque Dom Pedro II liga o bairro do Sacomã, no sul do
município de São Paulo, ao Parque Dom Pedro II no centro da cidade.
Essa linha foi escolhida por ser uma linha em parte alimentadora, pois vários usuários
se deslocam até o Parque Dom Pedro II, onde se localiza o maior terminal de ônibus urbano
do município de São Paulo, e em parte uma linha normal, pois uma boa parte dos usuários não
segue no ônibus até o final do trajeto.
y
x
Aresta da
região de
Voronoi
Estações
Colineares
S
1
S
2
S
3
S
n-1
S
n
87
O Terminal Parque Dom Pedro II, inaugurado em 1996, está localizado no Região
Central de São Paulo, junto ao Parque Dom Pedro II, na Av. do Exterior e próximo a Av. do
Estado, atende aos ônibus da SPTrans.
FIGURA 5.7: TRAÇADO DA LINHA 5108-10
FONTE: São Paulo Transporte S.A. - SPTrans.
Neste terminal circulam diariamente mais de 160 mil pessoas e atende principalmente
as regiões Leste, Sudeste e Nordeste da cidade.
A linha 5108-10 tem aproximadamente 17 km de extensão e funciona das 04h00min
até as 24h00min no sentido bairro-centro e das 04h50min até as 24h50min no sentido inverso.
A figura 5.8 mostra os dados relativos à linha 5108-10. O itinerário da linha está no
anexo 3.
88
FIGURA 5.8: DADOS GERAIS DA LINHA 5108-10
FONTE: São Paulo Transporte S.A. - SPTrans.
5.4.1 Modelo Matemático
Diferentemente do modelo anterior, este não se baseia unicamente na hipótese de que
os usuários do sistema de transporte coletivo da região utilizem a linha de ônibus para ir da
periferia da cidade até um terminal urbano situado no final da linha. Ele baseia-se também na
idéia de que apenas uma parte dos usuários utilize a linha para chegar até o ponto final e que
os demais usuários desçam em algum lugar antes do ponto final.
89
A figura 5.9 mostra o esquema da área de serviço abrangido pela linha em questão e a
figura 5.10 mostra a situação dos usuários dentro da área de abrangência da linha. Este
modelo foi desenvolvido através de informações colhidas empiricamente pelo autor.
FIGURA 5.9: GEOMETRIA DA ÁREA DE SERVIÇO
FONTE: Elaboração do Autor.
Para efeito de cálculo, este modelo é praticamente idêntico ao anterior. A única
diferença reside no fato de que neste caso os usuários não se deslocam na sua totalidade para
o destino final, ou seja, parte deles segue até um ponto da linha anterior ao ponto terminal.
Assim sendo, o tempo total de viagem de todos os passageiros da região estudada será dado
pelas equações 5.13 e 5.14 com apenas uma modificação: a variável
*
i
s
T
. Devido o fato de que
os usuários não seguirão todos até o ponto final da linha, ela deverá ser calculada da seguinte
maneira:
( )
(
)
( )
*
*
120
i
b a d
i c
s i p
a d b
V X X
y y
T i c hq t
X X V
τ
+
−
= − + + +
(5.15)
y
x
Terminal
Urbano
Linha de
ônibus
Pontos de
Parada
S
1
S
2
S
3
Usuário
r
d
1
S
0
90
Onde a variável
c
é calculada de acordo com a intenção do usuário, ou seja, é o ponto
onde o usuário pretende descer do ônibus.
( )
*
1
( , )
,
i
i
n
i
s
V
i
a
r x y s
T k T x y ds
V
φ
=
−
= +
∑
∫
(5.16)
Pode-se, então, definir o problema de otimização como sendo:
( )
1 2
*
, ,...,
1
( , )
min ,
i
i
n
n
i
s
V
d d d
i
a
r x y s
k T x y ds
V
φ
=
−
+
∑
∫
(5.17)
O critério para se definir valor de
c
obedecerá ao esquema descrito abaixo e está
esquematizado na figura 5.10.
FIGURA 5.10: MODELO ESQUEMÁTICO DO COMPORTAMENTO DO USUÁRIO
FONTE: Elaboração do Autor.
Inicialmente o percurso total da linha foi dividido em três partes iguais. Os usuários
que embarcam em qualquer ponto localizado no primeiro terço da linha(Zona 1) seguem até
um determinado ponto baseado nos seguintes critérios:
y
x
Terminal
Urbano
Zona 1:
⅓
dos usuários seguem até a zona 2;
⅓
dos usuários seguem até a zona 3;
⅓
dos usuários seguem até o terminal
.
S
1
S
2
S
3
d
1
Zona 2:
½ dos usuários seguem até a zona 3;
½ dos usuários seguem até o terminal.
Zona 3:
Todos os usuários seguem até o terminal.
S
0
91
a)
A terça parte dos usuários seguem até o segundo terço da linha(Zona 2);
b)
A terça parte dos usuários seguem até o terceiro terço da linha(Zona 3);
c)
A terça parte dos usuários seguem até o ponto final da linha(Terminal Urbano);
Os usuários que embarcam em qualquer ponto localizado no segundo terço da
linha(Zona 2) seguem até um determinado ponto baseado nos seguintes critérios:
a)
A metade deles segue até o terceiro terço da linha(Zona 3);
b)
A outra metade segue até o ponto final da linha(Terminal Urbano);
Os usuários que embarcam em qualquer ponto localizado no terceiro terço da
linha(Zona 3) seguem até o ponto final da linha(Terminal Urbano).
Para os usuários que desembarcam nas zonas 2 e 3 são atribuídos à variável
c
valores
aleatórios correspondentes aos pontos localizados nessas respectivas zonas.
5.5 Considerações sobre a Densidade Demográfica da Região de Abrangência
Nos dois modelos descritos anteriormente, a densidade demográfica é utilizada como
parâmetro para a distribuição dos usuários na área de abrangência da linha em questão.
Porém, ao longo da linha a densidade demográfica não é constante, variando nas várias
regiões atendidas pela linha de ônibus.
O modelo desenvolvido aceita que a densidade demográfica tenha valores diferentes
para cada setor da região abrangida pela linha sem que isso seja uma limitação. O cálculo será
feito levando em conta a variação da densidade demográfica em toda a região. A figura 5.11
trás um exemplo de como pode ser constituída a região de abrangência da linha em estudo.
92
FIGURA 5.11: MODELO ESQUEMÁTICO DA VARIAÇÃO DA DENSIDADE
DEMOGRÁFICA
FONTE: Elaboração do Autor.
5.6 Metodologia para o Cálculo dos Valores
Para o cálculo do valor da função objetivo o valor da integral definida ou integral de
Riemann é calculado numericamente.
O valor da integral de Riemann num intervalo qualquer é equivalente a soma de todos
os elementos da área sob a curva no intervalo. São definidas frações do intervalo e então é
calculada a soma de todas as áreas parciais dessas frações.
No modelo definido neste trabalho, é definido um valor que representa o tamanho do
lado de um quadrado que vai dividir a área de abrangência em várias frações. A partir daí é
feita a somatória dos tempos de viagem do centro de cada fração de área definida
anteriormente até o destino previsto para o usuário. O destino pode ser tanto o ponto final da
linha, como é o previsto no caso da linha alimentadora, como também pode ser um ponto
intermediário, como acontece para alguns passageiros da linha 5108.
y
x
Destino
Final
Densidade
Demográfica 3
S
1
S
2
S
3
d
1
Densidade
Demográfica 2
Densidade
Demográfica 1
S
0
93
Quanto menor for o valor que vai definir o tamanho da fração, maior será a precisão
alcançada, porém maior será também o tempo de processamento.
O valor do tempo médio de viagem dos usuários de cada linha é calculado da seguinte
maneira: multiplica-se o tempo de viagem de cada “ponto” (fração de área) da região de
abrangência pela densidade demográfica da região em que ele se encontra e então é calculada
a média ponderada para todos os valores encontrados.
No próximo capítulo serão descritas as rotinas e a implementação dos programas de
computador que permitirão resolver o problema descrito acima. Serão também apresentados
os resultados obtidos no estudo.
94
6 RESULTADOS COMPUTACIONAIS
Neste capítulo serão descritos os sistemas desenvolvidos para resolver o problema
descrito anteriormente e serão apresentados os resultados.
6.1 Desenvolvimento das Ferramentas Computacionais
Inicialmente foram desenvolvidos sistemas para resolver problemas de programação
não-linear. Foram utilizados os métodos descritos no capítulo 4, que são: Método da
Descida(Gradiente), Método das Direções Conjugadas(Gradiente Conjugado) e o Método
Davidon-Fletcher-Powel(DFP). Foram também implementados os métodos de Wolfe,
Goldstein e Armijo para o cálculo do passo.
Como método de refinamento da solução inicial foi implementado o Método
Simulated Annealing, ou Metropolis. O sistema também permite a geração de vários pontos
iniciais, geração essa que pode utilizar a distribuição uniforme ou normal. É possível ainda
calcular novos números a partir da combinação linear da população inicial a fim de gerar uma
nova população de pontos iniciais a serem avaliados.
O sistema foi desenvolvido utilizando a linguagem de programação Delphi, versão
6.0. A tela inicial do sistema está na figura 6.1.
95
FIGURA 6.1: TELA INICIAL DO SISTEMA PARA A RESOLUÇÃO DE PROBLEMAS
DE PROGRAMAÇÃO NÃO-LINEAR
FONTE: Elaboração do Autor.
6.2 Teste das Ferramentas Computacionais
Para a fase de teste do sistema foram implementadas várias funções matemáticas a fim
de verificar a precisão e eficiência do mesmo. As funções utilizadas nos testes são: Davis,
Rastringin, Ackley, Griewank, Rosenbrock e Schwefel, todas descritas em Bez (2005). Os
resultados de alguns dos testes estão listados no Anexo 4.
96
FIGURA 6.2: TEMPO DE PROCESSAMENTO PARA A FUNÇÃO DAVIS
Wolfe
Goldstein
Armijo
Gradiente
Gradiente Conjugado
DFP
27
36
27
18
99
18
2
2
3
0
10
20
30
40
50
60
70
80
90
100
Tempo (em segundos)
Heurísticas
Função Davis - Comparação de Desempenho
FONTE: Elaboração do autor.
Foram testadas as funções através de uma população inicial de números gerados
aleatoriamente. Para todos os testes foi utilizado também o método de
Simulated Annealing
.
Os testes foram realizados utilizando um computador dotado de um processador Intel
Core Duo com 2GHz de freqüência e 2 Gb de memória RAM. Foram registrados os
resultados obtidos para o menor valor das funções e o tempo de processamento.
Analisando os resultados podemos afirmar que todos os métodos obtiveram resultados
bastante próximos, tanto em relação ao resultado quanto em relação ao tempo de execução.
Porém em alguns casos ocorreram algumas discrepâncias, como a mostrada na figura 6.2,
onde podemos perceber que, para a função Davis, o tempo de processamento do método do
Gradiente Conjugado, utilizando a regra de Goldstein, foi bem maior que os demais.
97
FIGURA 6.3: TEMPO DE PROCESSAMENTO PARA A FUNÇÃO SCHWEFEL
Wolfe
Goldstein
Armijo
Grad
Grad Conj
DFP
63
72
54
18
18
18
45
45
36
0
10
20
30
40
50
60
70
80
Tempo (em segundos)
Heurísticas
Função Schwefel - Comparação de Desempenho
FONTE: Elaboração do autor.
Na figura 6.3 temos a comparação de tempo de processamento da função Schwefel.
Aqui o método do Gradiente Conjugado teve um desempenho melhor que os demais.
Na figura 6.4 está o resultado do desempenho dos diferentes métodos. Nela podemos
perceber que o método do Gradiente Conjugado foi o que mais tempo utilizou para encontrar
o valor final.
Para a resolução do problema do espaçamento das paradas de ônibus, o método do
Gradiente Conjugado foi o que melhor desempenho teve, embora os resultados tenham sido
semelhantes, sem variações significativas.
98
FIGURA 6.4: TEMPO DE PROCESSAMENTO PARA A FUNÇÃO ACKLEY
Goldstein
Armijo
Wolfe
Grad
Grad Conj
DFP
35
42
42
20
62
21
19
19
24
0
10
20
30
40
50
60
70
Tempo (em segundos)
Heurísticas
Função Ackley - Comparação de Desempenho
FONTE: Elaboração do autor.
6.3 Operação do Sistema para a Linha Alimentadora
Como foi descrito nas seções anteriores, este modelo representa uma linha de ônibus
que alimenta uma linha do Metrô de São Paulo. O trajeto total da linha possui 6,2km de
extensão. A área de abrangência da linha corresponde a uma faixa que cobre cerca de 600
metros para cada lado do trajeto da linha. Esse número é compatível com o que foi mostrado
no Capítulo 2 e na própria definição da linha feita nas seções anteriores.
Neste modelo considera-se que todos os passageiros irão embarcar em algum ponto da
linha e se deslocarão até o ponto final.
99
A densidade demográfica da área de abrangência da linha varia de acordo com a
região em que ela se encontra. A tabela 6.1 traz as diferentes densidades demográficas das
regiões ao longo do trajeto da linha em questão.
A figura 6.6 mostra a área de abrangência referente à linha em estudo. Mostra também
as divisões regionais que representam bairros com diferentes densidades demográficas.
TABELA 6.1: DENSIDADE DEMOGRÁFICA AO LONGO DO TRAJETO DA LINHA
Nome do Logradouro Bairro
Densidade
Demográfica(Hab/km²)
R. Martim Tenório Lapa 6.018
R. Dr. Cincinato Pomponet Lapa 6.018
R. Herbart Lapa 6.018
Praça Melvin Jones Lapa 6.018
R. Jeroaquara Lapa 6.018
R. Joaquim Machado Lapa 6.018
R. Catão Lapa 6.018
R. Fábia Lapa 6.018
R. Marco Aurélio Lapa 6.018
R. Aurélia Lapa / Perdizes 6.018 / 16.794
R. Heitor Penteado Perdizes / Alto de Pinheiros 16.794 / 5.773
R. Paulistânia Pinheiros 7.875
R. Harmonia Pinheiros 7.875
R. Rodésia Pinheiros 7.875
R. Girassol Pinheiros 7.875
R. Purpurina Pinheiros 7.875
R. Fradique Coutinho Pinheiros 7.875
FONTE: Prefeitura Municipal de São Paulo – IBGE - Censos Demográficos 2000.
Para a operação do sistema, inicialmente precisa-se definir a área de abrangência da
linha, conforme mostrado na figura 6.5. Feito isso, importamos a figura para uma tela do
sistema onde marcamos os pontos significativos que definem o limite da área. Os pontos são
anotados a partir de um sistema de coordenadas cartesianas que compreende toda a região
estudada. São considerados significativos os pontos que definem todos os segmentos de reta
das linhas que definem o problema em questão, ou seja, a linha do ônibus, os limites da área
de abrangência e os limites regionais, onde existe mudança de densidade demográfica.
100
A figura 6.6 mostra o modelo esquemático da região estudada com as coordenadas de
alguns pontos significativos em destaque. Os pontos estão definidos em coordenadas
cartesianas (x=horizontal, y=vertical) sendo a origem no canto superior esquerdo do mapa.
Uma versão simplificada deste modelo foi utilizado em Oliveira
a
et. al
. (2008).
101
FIGURA 6.5: ÁREA DE ABRANGENCIA DA LINHA COM AS DIVISÕES DOS
BAIRROS
FONTE: Elaboração do autor com o auxílio do Google Maps.
Legenda
Área de abrangência
Linha do ônibus
Divisão Regional
Ponto Inicial
Ponto Final
102
FIGURA 6.6: MODELO ESQUEMÁTICO DA ÁREA COM ALGUNS PONTOS E
COORDENADAS
FONTE: Elaboração do autor.
156,4
205 , 262
95,83
124,185
167,295
305,739
302,494
Legenda
Área de abrangência
Linha do ônibus
Divisão regional
373,697
240,781
206,572
103
6.3.1 Funcionamento do Programa
O programa parte de uma tela inicial, descrita na figura 6.7, onde é possível definir
alguns parâmetros de entrada e quais os métodos para a solução do problema que desejamos
utilizar.
FIGURA 6.7: TELA INICIAL DO PROGRAMA
FONTE: Elaboração do autor.
Para que os cálculos sejam efetuados é necessária a importação dos pontos que
delimitam as linhas que vão gerar o esquema mostrado na figura 6.7. Através desse esquema
o programa irá armazenar as informações sobre o trajeto da linha, os limites da área de
abrangência e as divisões regionais. Através do botão “desenhar” mostrado na tela da figura
6.7 é possível fazer a importação destes pontos.
104
Após a importação dos pontos, é gerada uma solução inicial, em que as paradas são
distribuídas em distâncias iguais ao longo da linha. Podem também ser gerados pontos
aleatórios distribuídos randomicamente sobre a linha.
A busca da solução ótima é feita através do método escolhido através de uma opção
feita na tela inicial. Deve-se escolher também o método para o cálculo do passo, bem como
definir os parâmetros necessários para a execução do programa. Se for escolhida a opção pela
aplicação do método
Simulated Annealing
este será executado após a otimização inicial. Para
maiores detalhes sobre o funcionamento do programa consulte o Anexo 7.
Após definido o espaçamento, o programa localiza as paradas ao longo do trajeto da
linha a fim de calcular a sua posição e as suas coordenadas, a fim de efetuar o cálculo dos
tempos de viagem para cada ponto da área de abrangência e assim calcular o valor da função
objetivo.
Esse procedimento é repetido para cada nova solução encontrada até que o valor final
seja obtido.
O cálculo do espaçamento ideal é feito individualmente para cada número de paradas
que se julguem necessárias. O número ideal de paradas, bem como o seu espaçamento, será o
que obtiver o menor valor para a função objetivo.
Após a obtenção do valor final o sistema localiza os pontos ótimos sobre a linha do
ônibus e a partir daí é desenhado o Diagrama de Voronoi referente aos pontos encontrados.
6.3.2 Resultados Obtidos
O programa foi executado de um total de cinco até um total de vinte e cinco paradas.
Foi utilizado como velocidade do usuário a pé o valor de 1 m/s e como velocidade normal de
cruzeiro do ônibus o valor de 20 m/s. O tempo médio de viagem por usuário foi calculado
para cada um desses valores e o resultado pode ser visto na figura 6.8.
105
FIGURA 6.8: TEMPO MÉDIO DE VIAGEM POR USUÁRIO POR NÚMERO DE
PARADAS
Tempo Médio de Viagem por Usuário
9,728
9,332
9,095
8,957
8,884
8,856
8,858
8,883
8,918
8,958
9,026
9,088
9,134
9,192
9,287
9,367
9,448
9,528
9,611
9,697
9,785
8,200
8,400
8,600
8,800
9,000
9,200
9,400
9,600
9,800
10,000
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Número de Paradas
Tempo(em minutos)
FONTE: Elaboração do autor.
Como podemos perceber no gráfico da figura 6.8 os tempos médios de viagem tendem
a ser bastante altos quando o número de paradas é baixo. Esse valor diminui à medida que o
número de paradas aumenta e depois de certo número ele começa a aumentar de novo.
O menor valor observado foi com dez paradas, com o tempo médio de viagem por
usuário de 8,856 minutos. Podemos perceber pelo gráfico que para pequenos aumentos do
número de paradas o tempo médio de viagem não sofre grandes variações. Porém com vinte e
cinco paradas o aumento é superior a dez por cento.
A tabela 6.2 mostra o resultado final obtido pelo sistema para um total de dez paradas.
A distância das paradas é medida a partir do ponto final da linha, que, neste caso, representa a
estação do metrô.
106
TABELA 6.2: RESULTADO FINAL PARA 10 PONTOS DE PARADA
Ponto
Distância desde a
origem
Distância desde a
parada anterior
Terminal
0
Ponto nº 1 992 992
Ponto nº 2 1865 873
Ponto nº 3 2633 768
Ponto nº 4 3309 676
Ponto nº 5 3904 595
Ponto nº 6 4428 524
Ponto nº 7 4888 461
Ponto nº 8 5294 405
Ponto nº 9 5650 357
Ponto nº 10 5964 314
Ponto Final 6200 236
FONTE: Elaboração do autor
Podemos perceber que quanto mais distante for a parada do final da linha, menor é o
espaçamento entre elas.
A figura 6.9 mostra a localização dos pontos obtidos sobre a linha de ônibus. Ela
mostra também o contorno do diagrama de Voronoi Ponderado e Ordinário referente a cada
parada. Neste caso, assumiu-se que o ponto final da linha possui uma parada. Isto se deve ao
fato de que cada parada próxima ao ponto final penaliza todos os usuários, causando um
aumento de tempo para a maioria da população que utiliza a linha.
107
FIGURA 6.9: LOCALIZAÇÃO DAS PARADAS SOBRE A LINHA DE ÔNIBUS
FONTE: Elaboração do autor.
FONTE: Elaboração do autor com o auxílio do Google Maps.
Legenda
Área de abrangência
Linha do ônibus
Divisão Regional
Parada de ônibus
Região de Voronoi Ponderada
Região de Voronoi Ordinária
108
6.4 Operação do Sistema para a Linha 5108
Esta é uma linha de ônibus urbana localizada no município de São Paulo. O modelo
foi descrito no capítulo anterior. A linha 5108, que liga a zona sul do município de São Paulo
até o terminal D. Pedro II, no centro da cidade, possui 17,1 km de extensão e conta
atualmente com 71 paradas, tendo um espaçamento médio de 240 metros.
O trajeto da linha, sua área de abrangência e as divisões regionais são mostradas na
figura 6.10. A figura 6.11 traz o modelo esquemático da linha contendo as três sub-divisões
descritas anteriormente, que define o comportamento do usuário.
Uma versão simplificada deste modelo foi utilizado em Oliveira
b
et. al
. (2008).
109
FIGURA 6.10: LINHA 5108 COM SUA ÁREA DE ABRANGÊNCIA
FONTE: Elaboração do autor com o auxílio do Google Maps.
Ponto
Inicial
Ponto Final
Legenda
Área de abrangência
Linha do ônibus
Divisão Regional
110
FIGURA 6.11: MODELO ESQUEMÁTICO DA LINHA E REGIÃO
FONTE: Elaboração do autor.
Zona 1:
⅓
dos usuários seguem até a zona 2;
⅓
dos usuários seguem até a zona 3;
⅓
dos usuários seguem até o terminal
.
Zona 2:
½ dos usuários seguem até a zona 3;
½ dos usuários seguem até o terminal.
Zona 3:
Todos os usuários seguem até o terminal.
Legenda
Área de abrangência
Linha do ônibus
Divisão Regional
Divisão das zonas 1, 2 e 3
111
O funcionamento do programa para este modelo é exatamente o mesmo que já foi
descrito na seção anterior. Existe a necessidade apenas de informar ao sistema os novos
parâmetros de entrada e os pontos significativos da nova rota. O único parâmetro novo é o
valor da variável
c
, que como já foi explicado anteriormente, determina o ponto em que o
usuário desce do ônibus.
O programa foi executado e obteve o tempo ótimo desde oito paradas até o total de
setenta e cinco paradas. O resultado pode ser verificado na figura 6.12. Neste caso também
podemos perceber que com um número baixo de paradas o tempo é bastante alto. Com o
aumento do número de paradas o tempo diminui para depois voltar a subir.
FIGURA 6.12: TEMPO MÉDIO DE VIAGEM POR USUÁRIO
Tempo Médio de Viagem por Usuário
0,00
5,00
10,00
15,00
20,00
25,00
30,00
8
1
0
12
1
4
1
6
18
20
2
2
2
4
26
28
3
0
32
34
3
6
3
8
40
42
4
4
46
48
5
0
5
2
54
56
5
8
6
0
62
6
4
6
6
68
70
7
2
7
4
Número de Paradas
Tempo em Minutos
FONTE: Elaboração do autor.
Na figura 6.13 temos um quadro mais reduzido do número de paradas, onde podemos
perceber que o menor valor corresponde a vinte e uma paradas, com o tempo médio de
viagem por usuário de 20,81 minutos. Esse número corresponde a um espaçamento médio de
750 metros entre as paradas.
112
Analisando o gráfico da figura 6.13 pode-se perceber que pequenos aumentos no
número de paradas não causa grandes aumentos no tempo médio de viagem. Isso nos permite
decidir por um número um pouco maior que o ideal a fim de reduzir o percurso caminhado
pelo usuário, sem grandes prejuízos no tempo de viagem.
Atualmente existem setenta e uma paradas ao longo dessa linha, o que corresponde a
um espaçamento de 240 metros. O tempo médio de viagem por usuário calculado para esse
número de paradas é de 27,82 minutos. Se aplicarmos um espaçamento mais amplo, podemos
reduzir o tempo médio de viagem em aproximadamente 24%.
FIGURA 6.13: TEMPO MÉDIO DE VIAGEM POR USUÁRIO
Tempo Médio de Viagem por Usuário
22,71
22,17
21,77
21,47
21,24
21,07
20,95
20,87
20,82
20,81
20,81
20,84
20,88
20,93
21,00
21,08
21,17
21,27
21,37
21,48
21,60
21,72
21,85
21,98
22,11
22,25
22,39
19,50
20,00
20,50
21,00
21,50
22,00
22,50
23,00
12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
Número de Paradas
Tempo (em minutos)
FONTE: Elaboração do autor.
A tabela 6.3 mostra o resultado final obtido pelo sistema para um total de vinte e uma
paradas. A distância das paradas é medida a partir do ponto final da linha, que, neste caso,
representa o terminal D. Pedro II.
Neste caso, como no modelo anterior, a distância entre as paradas decresce quanto
mais distante ela for do final da linha. Isto se deve ao fato de que cada parada próxima ao
113
ponto final penaliza todos os usuários, causando um aumento de tempo para a maioria da
população que utiliza a linha.
FIGURA 6.14: RESULTADO FINAL DA LINHA 5108 COM DIAGRAMA DE VORONOI
FONTE: Elaboração do autor com o auxílio do Google Maps.
Legenda
Área de abrangência
Linha do ônibus
Parada de ônibus
Diagrama de Voronoi
Ponderado
Diagrama de Voronoi
Ordinário
114
A figura 6.14 mostra o resultado final para um total de 21 paradas com o diagrama de
Voronoi Ponderado e Ordinário.
6.5 Considerações sobre os Resultados
Este trabalho teve por objetivo estabelecer um espaçamento ótimo entre as paradas de
transporte coletivo tendo por finalidade a redução do tempo médio de viagem do passageiro.
TABELA 6.3: RESULTADO FINAL PARA 21 PONTOS DE PARADA
Ponto
Distância desde a
origem(em metros)
Distância desde a
parada anterior
Terminal
0
Ponto nº 1
1197
1197
Ponto nº 2
2343
1146
Ponto nº 3
3439
1096
Ponto nº 4
4488
1049
Ponto nº 5
5492
1004
Ponto nº 6
6453
961
Ponto nº 7
7372
920
Ponto nº 8
8252
880
Ponto nº 9
9094
842
Ponto nº 10
9900
806
Ponto nº
11
10672
771
Ponto nº
12
11410
738
Ponto nº
13
12116
706
Ponto nº
14
12792
676
Ponto nº
15
13439
647
Ponto
nº
16
14058
619
Ponto nº
17
14651
592
Ponto nº
18
15218
567
Ponto nº
19
15760
543
Ponto nº
20
16280
519
Ponto nº
21
16777
497
FONTE: Elaboração do autor
115
As várias normas pesquisadas neste trabalho indicaram que a maioria dos modelos
existentes não possui um enfoque que vise estritamente o passageiro. Alguns desses modelos
estabelecem uma distância máxima para que o passageiro possa percorrer a pé, porém sem
estabelecer como essa distância máxima é calculada.
Nos vários estudos de caso analisados anteriormente no Capítulo 2, foi visto que em
todos eles o resultado indica que deveria haver uma redução no número de paradas ao longo
das linhas estudadas.
Os resultados encontrados neste trabalho demonstram também que uma redução no
numero de paradas reduz o tempo médio de viagem do passageiro até o seu destino. Pôde-se
perceber, no estudo de caso da linha 5108 da cidade de São Paulo, que a aplicação do modelo
causa uma redução bastante acentuada no número de paradas com uma redução no tempo
médio de viagem dos usuários em torno de 24%. Se for considerado um total de
aproximadamente seis milhões de passageiros por dia, podemos perceber a importância que
uma redução no tempo de viagem do passageiro terá sobre os vários aspectos econômicos e
sociais da cidade.
Embora o sistema aqui desenvolvido vise única e exclusivamente o tempo de viagem
do passageiro, ele proporciona também outros benefícios, pois reduzindo o número de
paradas, são reduzidos também os custos de manutenção e operação dos veículos (freios e
combustível gasto na aceleração do veículo), a poluição da atmosfera causada pela emissão de
gases, a poluição sonora gerada pela aceleração e desaceleração dos ônibus, etc.
Outro aspecto relevante do trabalho foi a opção pela resolução numérica do problema.
Em trabalhos anteriores, a utilização da resolução analítica forçou os autores a buscar
simplificações nos modelos a fim de que fosse viável a solução do mesmo. A opção pela
resolução numérica permitiu uma liberdade bem maior na elaboração e execução do modelo
proposto, possibilitando assim uma maior precisão nos resultados, bem como uma maior
proximidade do modelo com a situação real.
116
7 CONCLUSÕES E RECOMENDAÇÕES
7.1 Conclusões
O planejamento urbano tem hoje como uma de suas maiores preocupações o transporte
coletivo. O excesso de veículos nas ruas das grandes cidades é uma fonte de problemas de
vários tipos tais como: congestionamentos, poluição atmosférica e sonora, acidentes e
atropelamentos, etc. Outro problema acarretado pelo excesso de veículos nas vias públicas é o
tempo de deslocamento que um cidadão utiliza para ir de um local a outro. Por isso, um
sistema de transporte coletivo eficiente e rápido ajudaria a resolver esses problemas.
Neste trabalho foi desenvolvido um modelo para determinar o espaçamento ideal entre
paradas de transporte coletivo cujo objetivo é minimizar o tempo médio de viagem do usuário
do sistema de transportes. O modelo foi baseado nos conceitos de Diagramas de Voronoi e de
Programação Não-linear. Ele utiliza também a densidade demográfica da região observada
como um dos parâmetros para a otimização. Foi implementado um sistema informatizado
para a análise do modelo e avaliar os seus resultados.
Esse sistema, além das funções já descritas, determinará também a área de influência
de cada parada, ou seja, cada cidadão saberá, através de um diagrama, qual é a parada mais
adequada para que ele tome o transporte coletivo e chegue mais rapidamente ao seu destino.
O sistema foi aplicado a duas linhas de ônibus da cidade de São Paulo. A primeira é
uma linha hipotética localizada na região Oeste da cidade, que iniciaria no bairro da Lapa e
terminaria na futura estação Fradique Coutinho da Linha 4 do Metrô de São Paulo. A segunda
linha é uma linha já existente que liga a região Sul ao centro da cidade. O resultado nela
obtido reduziu significativamente o número de paradas e por conseqüência reduziu também o
tempo médio de viagem em 24%.
117
Este método aqui desenvolvido pode auxiliar bastante no planejamento do transporte
público das cidades, bem como avaliar e aperfeiçoar os sistemas já existentes.
7.2 Recomendações e Trabalhos Futuros
Os resultados obtidos pelo modelo desenvolvido foram bastante satisfatórios. Foi
possível reduzir o tempo médio de viagem o passageiro. Porém o sistema ainda não permite o
estudo de múltiplas linhas ou a integração com outros sistemas de transporte, tais como o
Metrô ou Trem Metropolitano.
Para trabalhos futuros poderiam ser desenvolvidos modelos que contemplassem esses
casos e, assim, melhorando o sistema de transporte coletivo de maneira mais global.
Alguns fatores que não foram abrangidos por este estudo poderão ser estudados no
futuro, tais como:
a)
Tamanho da frota, espaçamento entre os ônibus e tempo de espera do usuário
no ponto;
b)
O estudo sobre uma área que contenha alguma forma de barreira como rio,
lago, grande avenida, parque, dentre outras;
c)
A variação da topografia da região atendida, modificando a acessibilidade e a
velocidade do usuário.
Todas essas limitações poderão ser abordadas em trabalhos futuros.
A partir do modelo desenvolvido neste trabalho, poderão ser feitas também análises
sobre a influência de alguns fatores no resultado obtido. Esses fatores são: o tempo de espera
na parada, a freqüência do ônibus, a velocidade do passageiro a pé e a velocidade média do
ônibus durante o percurso.
118
REFERÊNCIAS BIBLIOGRÁFICAS
AMMONS, D. N.
Municipal benchmarks: Assessing local performance and establishing
community standards
. (2nd ed.). Thousand Oaks, CA: Sage Publications, 2001.
ANDRADE, K. R.; PAULA, V. A.; VILLELA, P. A.; MESQUITA, A. P.
Problemas
relacionados aos pontos de parada do transporte público nas cidades de porte médio.
IV
Seminário Internacional da LARES, São Paulo, ago. 2004.
ANTP – ASSOCIAÇÃO NACIONAL DE TRANSPORTES PÚBLICOS.
Pontos de parada
de ônibus urbano. Contribuição para sua implantação.
Caderno técnico n. 2, São Paulo –
SP, 1995.
BENN, H.
Bus Route Evaluation Standards.
Synthesis of Transit Practice 10. Transit
Cooperative Research Program, Transportation Research Board, National Research Council,
USA, 1995.
BERMAN, O., DREZNER, Z. AND WESOLOWSKY, G.O.
Routing and location on a
network with hazardous threats,
Journal of the Operational Research Society (2000) 51,
1093-1099
BERTINI, R. L.
Bus Stop Spacing.
Intelligent Transportation Systems Laboratory at
Portland State University, 2004.
BEZ, E.T.,
Procedimento de representação de soluções em otimização global: aplicação
em modelos de interação espacial
. Tese apresentada ao Programa de Pós-Graduação em
Engenharia de Produção da Universidade Federal de Santa Catarina como requisito parcial
para obtenção do grau de Doutor em Engenharia de Produção, Florianópolis, 2005.
BODIN, L.D., 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., 1983.
CENTRAL OHIO TRANSIT AUTHORITY.
Planning and development guidelines for
public transit.
COTA, Columbus, OH, 1999.
CUNHA, C.B.
Algoritmos para roteamento e programação de veículos no contexto da
distribuição física.
São Paulo: EPUSP, Departamento de Engenharia de Transportes.
Dissertação de Mestrado, 1991.
DOWSLAND, K.A. Simulated Annealing, In Reeves, C.R. (ed), Modern Heuristic
Techniques for Combinatorial Problems, Blackwell Scientific Publications, 20-69,
1993.
EBTU – EMPRESA BRASILEIRA DE TRANSPORTES URBANOS.
Planejamento e
Operação; Elementos Intervenientes.
v. 2. Empresa Brasileira dos Transportes Urbanos:
Brasília, DF, 1998.
119
EL-GENEIDY, A. M.; KIMPEL, T. J.; STRATHMAN, J. G.
Empirical Analysis of the
Effects of Bus Stop Consolidation on Passenger Activity and Transit Operations.
College
of Urban and Public Affairs: Portland State University, 2005.
FISHER, M.L.
The lagrangian relaxation method for solving integer programming
problems.
Management Science, 27(1):1-17, 1981.
FLEISCHER, M. 1995.
Simulated annealing: past, present, and future
. In
Proceedings of
the 27th Conference on Winter Simulation
, Arlington, Virginia, United States, 1995.
FLETCHER, R. ,REEVES, C.M.
Function minimization by conjugate gradients
. Computer
Journal, 7 (149--154), 1964.
FRIELANDER, A.
Elementos de Programação Não Linear.
Campinas, SP: Editora
Unicamp, 1994.
FURTH, P. G; RAHBEE, A. B.
Optimal bus stop spacing through dynamic programming
and geographic modeling.
Transportation Research Record, n. 1731, p. 15-22, 2000.
GALVÃO, L. C.
Dimensionamento de Sistemas de Distribuição Através do Diagrama
Multiplicativo de Voronoi com Pesos.
Tese de Doutorado, Departamento de Engenharia de
Produção e Sistemas, UFSC, 2003.
GENDREAU, M., HERTZ, A., LAPORTE, G.
A tabu search heuristic for the routing
problem.
Management Science, (10):1276-1290, 1994.
Goldbarg, Marco Cesar and Luna, Henrique Pacca L., “
Otimização Combinatória e
Programação Linear – Modelos e Algoritmos”, Editora Campus, 2000.
GOLDBARG, MARCO CESAR , LUNA, HENRIQUE PACCA L.
, Otimização
Combinatória e Programação Linear – Modelos e Algoritmos
, Editora Campus, 2000.
GOLDBERG, D.E.
Genetic Algorithms in Search Optimization and Machine Learning.
New York, Addson-Wesley, 412 p., 1989.
GOLDEN, B.; ASSAD, A. LEVY, L., GHEYSENS, F.
The Fleet Size and Mix Vehicle
Routing Problem,
Comput. & Ops Res
.
Vol. 11, nº 1, pp.49-66, 1984.
GOLDEN, B.L., ASSAD, A.
Vehicle routing: methods and studies.
North Holland,
Amsterdã, Países Baixos, 1988.
GONÇALVES, N.M., E
conomias de escala em uma linha de ônibus urbano: O Enfoque
Micro-Analítico.
Dissertação submetida à Universidade Federal De Santa Catarina para
obtenção do Grau De Mestre Em Engenharia., Florianópolis, 1995.
GRACIOLLI, O. D.
Dimensionamento e Otimização de Sistemas de Distribuição Física
de Produtos - Um Enfoque Contínuo.
Tese de Doutorado, Departamento de Engenharia de
Produção e Sistemas, UFSC, 1998.
120
HOOKE, R. JEEVES, T.A.
Direct search solution of numerical and statistical problems.
Journal of the Association for Computing Machinery 1962; 8, p.212-229.
IPEA – INSTITUTO DE PESQUISAS ECONÔMICAS APLICADAS / ANTP – AGÊNCIA
NACIONAL DE TRNASPORTES PÚBLICOS
. Redução das deseconomias urbanas com a
melhoria do transporte público.
Revista dos Transportes Públicos, n.
21 (1), pp. 35-92. São
Paulo, 1999.
KEHOE, O. V.
Effects of Bus Stop Consolidation on Transit Speed and Reliability: a
Test Case.
A thesis submitted in partial fulfillment of the requirements for the degree of
Master of Science in Civil Engineering University of Washington, 2004.
KUAH, G. K.; PERL, J.
Optimization of feeder bus routes and bus-stop spacing.
Journal
of Transportation Engineering. vol. 114, n. 3, p. 341-354, 1988.
LINDAU, L. A.; KÜHN, F.
Sistemas prioritários para ônibus: tendências decorrentes da
prática européia no limiar do século XXI
. Revista dos Transportes Públicos, São Paulo, v.
22, n. 2, p. 81-90, 2000.
LUENBERGER, D.G.
Linear and Nonlinear Programming.
Second Edition, Springer
Science + Business Media Inc., 2005
MERCEDES–BENZ DO BRASIL S. A.
Manual de Sistema de Transporte Coletivo
Urbano por Ônibus – Planejamento e Operação.
São Bernardo do Campo, SP, 1987.
MURRAY, A.
A coverage model for improving public transit system accessibility and
expanding access.
Annals of Operations Research, vol. 123, p. 143-156, 2003.
MURRAY, A.; WU, X.
Accessibility tradeoffs in public transit planning.
Journal of
Geographical Systems, n. 5(1), p. 93-107, 2003.
NOVAES, A.G.
Logistics Districting With Multiplicatively Weighted Voronoi Diagrams.
XI Congreso Panamericano de Ingeniería de Tránsito y Transporte, Gramado, RS. 19 al 24 de
Noviembre del 2000.
NOVAES, A.G.
Sistemas Logísticos: Transporte, Armazenamento e Distribuição Física
de Produtos.
São Paulo: Ed. Edgard Blucher, 1989.
NOVAES, A.G.; CURSI, J. E. S.; GRACIOLLI, O. D.
A continuous approach to the design
of physical distribution systems.
Computers & Operations Research, 2000.
NOVAES, A.G., CURSI, J.E.S., SILVA, A.C.L., SOUZA, J.C.,
Solving continuous
location–districting problems with Voronoi diagrams.
Computers & Operations Research,
Volume 36, Issue 1, January 2009, Pages 40-59.
NOVAES, A.G.; GRACIOLLI, O. D.
Designing Multi-Vehicle Delivery Tours in a Grid-
Cell Format.
European Journal of Operational Research, n. 119, p. 613-634 , 1999.
121
NTU - Secretaria de Desenvolvimento Urbano da Presidência da República – Núcleo de
Transporte Urbano.
Transporte Público Urbano: crise e oportunidades.
Associação
Nacional das Empresas de Transportes Urbanos. Versão Preliminar. Brasília, 1999.
OKABE, A.; BOOTS, B.; SUGIHARA, K.
Spatial Tessellations Concepts and
Applications of Voronoi Diagrams.
John Wiley & Sons, Chichester. New York – Brisbane –
Toronto – Singapore, 1992.
OLIVEIRA
a
, H.F.; GONÇALVES, M.B.; CURSI, E.S.; NOVAES, A.G
; Minimize the
travel time of all passengers of a bus line using concepts of Voronoi Diagrams
.
Proceedings of the Second International Conference on Multidisciplinary Design
Optimization and Applications, Gijon, Spain, 2008.
OLIVEIRA
b
, H.F.; GONÇALVES, M.B.; CURSI, E.S.; NOVAES, A.G
; A Model based in
Voronoi Diagrams Find the Best Bus-stop Spacing to Minimize the Total Travel Time of
the Travelers.
Proceedings of the International Conference on Engineering Optimization -
EngOpt 2008, Rio de Janeiro, Brazil, 2008.
PAMPLONA, M. R.
Considerações sobre O emprego dos diferentes tipos de ônibus no
transporte público urbano.
Dissertação de Mestrado. Escola de Engenharia de São Carlos
da Universidade de São Paulo, 2000.
PINTO, A. B.; DIÓGENES, M. C.; LINDAU, L. A.
Quantificação dos impactos de pólos
geradores de tráfego.
Porto Alegre: Notas de aula, 2003.
PRESS, W.H., TEULOSKY, S.A., VETTERLING, W.T., FLANNERY, B.P.
Numerical
Recipes in C++. The Art of Scientific Computing.
Second Edition, Cambridge University
Press, 2002
REILLY, J. M.
Transit service design and operation practices in western european
countries.
Transportation Research Record, 1604, 3-8, 1997.
ROCHAT, Y., SEMET, F.
A tabu search approach for delivering pet food and flour in
Switzerland
. Journal ofthe Operational Research Society
,
45(11):1233-1246, 1994.
SAKA, A. A.
Model for determining optimum bus-stop spacing in urban areas.
Journal
of Transportation Engineering, n. 127 (3), pp. 195–199,USA , 2001.
SEDU/PR ; NTU - Secretaria de Desenvolvimento Urbano da Presidência da República –
Núcleo de Transporte Urbano.
Relatório Técnico – Prioridade para o Transporte Coletivo
Urbano.
Secretaria Especial de Desenvolvimento Urbano da Presidência da República e
Associação Nacional de Empresas de Transportes Urbanos, Brasília, DF, 2002.
SILVA, D.F.P.,
Sistemas de Informação Geográfica para Transportes. Uma Aplicação
aos Transportes Urbanos de Guimarães.
Dissertação de Mestrado, Instituto Superior de
Estatística e Gestão, Universidade Nova Lisboa, Janeiro de 2006.
SPECIAL REPORT 257.
Making transit work: insight from Western Europe, Canada,
and the United States
., Committee for an International Comparison of National Policies and
122
Expectations Affecting Public Transit, Transportation Research Board, National Research
Council, USA, 2001.
SUZUKI, T.
Optimum locational patterns of bus-stops for many-to-travel demand.
Papers of the Annual Conference of the City Planning Institute of Japan, p-247-252, 1987
TEXAS TRANSPORTATION INSTITUTE (TTI).
Guidelines for the Location and Design
of Bus Stops.
TCRP Report 19, Transit Cooperative Research Program, Transportation
Research Board, National Research Council, 1996.
VASCONCELLOS, E. A.
Transporte urbano nos países em desenvolvimento: reflexões e
propostas.
São Paulo: Annablume, 2000.
WANGENHEIM, A. Notas de Aula. Departamento de Informática e Estatística, UFSC, 2004
123
ANEXO 1
Valores numéricos do Estudo de Caso 2
Valores para os Parâmetros utilizados no Exemplo Numérico:
Símbolo
Unidade
Descrição
ly 16 km Dimensão vertical da área de serviço
lx 16 km Dimensão horizontal da área de serviço
Va 5,0 km/hora Velocidade a pé do usuário
δ
0,01 horas/parada Tempo perdido em cada parada
U 40 km/hora Velocidade média do ônibus
λ
o $35/veículo-hora Custo operacional do ônibus
λ
a $8/passageiro-hora Valor do tempo gasto pelo usuário até a parada
λ
r $4/passageiro-hora Valor do tempo gasto pelo usuário no ônibus
λ
w $8/passageiro-hora Valor do tempo de espera do usuário
Funções de distribuição de demanda utilizadas
Exemplo 1:
p(x,y) = 300
Exemplo 2:
( )
1600 1 3
, 1
3 2 8
x y
x y
p x y
l l
= − −
124
Exemplo 3:
( )
2
2
7200 1 3
, 1
17 2 8
x y
x y
p x y
l l
= − −
Resultado da Otimização
Caso 1: O espaçamento é constante ao longo da linha e se mantém constante em todas as linhas, ou seja,
s(x,y) = s
.
Resultado do espaçamento
Exemplo s
*
(Km)
1 0,89
2 0,84
3 0,85
125
Caso 2: O espaçamento é constante ao longo de uma linha, mas pode variar de uma linha para outra, ou
seja, s(x,y) = s(x).
Resultado do espaçamento
Distância até o
final da linha
férrea
Exemplo 1 Exemplo 2 Exemplo 3
x (km)
s*(x) (km)
s*(x) (km)
s*(x)(km)
1
0,89
0,86 0,86
2
0,89
0,86 0,86
3
0,89
0,85 0,86
4
0,89
0,85 0,86
5
0,89
0,85 0,86
6
0,89
0,85 0,86
7
0,89
0,85 0,86
8
0,89
0,84 0,86
9
0,89
0,84 0,85
10
0,89
0,84 0,85
11
0,89
0,83 0,85
12
0,89
0,83 0,85
13
0,89
0,82 0,84
14
0,89
0,82 0,84
15
0,89
0,81 0,83
16
0,89
0,80 0,82
126
Caso 3: Considera-se que a distribuição de demanda pode variar entre rotas e ao longo de cada rota.
Resultado do espaçamento: exemplo 2
Resultado do espaçamento: exemplo 3
127
ANEXO 2
Linha alimentadora – Itinerário
1. R. Martim Tenório
ir por 51 m
total 51 m
2. R. Dr. Cincinato Pomponet
ir por 85 m
total 0,1 km
3. R. Herbart
ir por 82 m
total 0,2 km
4. Praça Melvin Jones
ir por 0,1 km
total 0,4 km
5. R. Jeroaquara
ir por 0,1 km
total 0,5 km
6. R. Joaquim Machado
ir por 93 m
total 0,6 km
7. R. Catão
ir por 0,6 km
total 1,2 km
8. R. Fábia
ir por 0,1 km
total 1,3 km
9. R. Marco Aurélio
ir por 0,8 km
total 2,1 km
10. R. Aurélia
ir por 0,7 km
total 2,9 km
11. R. Heitor Penteado
ir por 0,7 km
total 3,5 km
12. R. Paulistânia
ir por 0,3 km
total 3,8 km
13. R. Harmonia
ir por 0,5 km
total 4,3 km
14. R. Rodésia
ir por 0,1 km
total 4,4 km
15. R. Girassol
ir por 0,2 km
total 4,6 km
16. R. Purpurina
ir por 0,2 km
total 4,9 km
17. R. Fradique Coutinho
ir por 1,5 km
total 6,4 km
128
ANEXO 3
Linha nº 5108-10 – Itinerário
TP/TS - TERM. PQ. D. PEDRO II
TS/TP - JD. CELESTE
AV. BRASILIA
0
0
TERM. PARQUE DOM PEDRO II
0
0
PCA. CELITE
0
0
AV. DO EXTERIOR
775
1026
AV. CURIO
1
517
R. ALEXANDRIA
1
61
AV. CURSINO
6709
348
R. FREDERICO ALVARENGA
64
308
R. DR. OCTACILIO CAMARA SILVEIRA
1
198
AV. PREF. PASSOS
1517
276
R. VERGUEIRO
6853
6240
R. TEIXEIRA LEITE
719
201
R. MQ. DE OLINDA
1
192
R. DO LAVAPES
144
1144
R. SALVADOR SIMOES
444
1
LGO. CAMBUCI
276
416
PCA. PINHEIRO DA CUNHA
1065
1123
R. INDEPENDENCIA
748
506
R. SALVADOR SIMOES
1470
1312
AV. D. PEDRO I
488
1486
R. VIEIRA DE ALMEIDA
195
384
R. VASCONCELOS DRUMOND
1
122
R. GAMA LOBO
1035
543
PCA. DO MONUMENTO
24
0
R. MOREIRA E COSTA
156
734
AV. NAZARE
0
522
R. BOM PASTOR
1474
85
R. PE. MARCHETTI
304
1
R. TABOR
188
15
R. DR. MARIO VICENTE
606
1217
AV. D. PEDRO I
1453
427
R. VIEIRA DE ALMEIDA
195
324
AC. ACESSO A
19
1
R. SALVADOR SIMOES
1312
1470
R. INDEPENDENCIA
597
433
PCA. PINHEIRO DA CUNHA
1065
1123
R. CLIMACO BARBOSA
1087
1
R. SALVADOR SIMOES
1
327
LGO. CAMBUCI
432
112
R. DR. ELISIO DE CASTRO
227
1
R. LUIS GAMA
643
371
R. VERGUEIRO
6118
6465
R. SILVEIRA DA MOTA
1
143
R. STA. CRUZ
2380
2442
R. OTTO DE ALENCAR
363
1
AV. CURSINO
1
6709
R. JUNQUEIRA FREIRE
1
51
AV. CURIO
517
1
R. BR. DE IGUAPE
999
421
PCA. CELITE
0
0
R. CONS. FURTADO
163
1
AV. BRASILIA
0
0
VIAD. SHUHEI UETSUKA
58
1
R. CONS. FURTADO
1399
1030
PCA. DR. JOAO MENDES
265
294
R. ANITA GARIBALDI
208
1
PCA. CLOVIS BEVILAQUA
498
388
AV. RANGEL PESTANA
1
189
R. DR. BITTENCOURT RODRIGUES
0
149
PCA. FERNANDO COSTA
0
322
R. GEN. CARNEIRO
1
78
AC. ACESSO A
0
0
TERM. PARQUE DOM PEDRO II
0
0
* logradouro - nº inicial -> final
129
ANEXO 4
Resultado dos Testes
===========================================================================
==
Função avaliada: Davis
Método: Gradiente
Cálculo do Passo: Wolfe
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.000100096647
Ponto Ótimo Final
x[1]= 0.0000000000
x[2]= 0.0000000003
Hora de Término: 14:24:40
===========================================================================
==
Função avaliada: Davis
Método: Gradiente
Cálculo do Passo: Goldstein
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.000100096647
130
Ponto Ótimo Final
x[1]= 0.0000003006
x[2]= -0.0000001539
Hora de Término: 14:24:42
===========================================================================
==
Função avaliada: Davis
Método: Gradiente
Cálculo do Passo: Armijo
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.000100096647
Ponto Ótimo Final
x[1]= -0.0000000020
x[2]= 0.0000000012
Hora de Término: 14:24:45
===========================================================================
==
Função avaliada: Davis
Método: Fletcher-Reeves/Gradiente Conjugado
Cálculo do Passo: Wolfe
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.000100096647
Ponto Ótimo Final
131
x[1]= -0.0000001479
x[2]= 0.0000000616
Hora de Término: 14:24:50
===========================================================================
==
Função avaliada: Davis
Método: Fletcher-Reeves/Gradiente Conjugado
Cálculo do Passo: Goldstein
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.000100096647
Ponto Ótimo Final
x[1]= -0.0000000349
x[2]= 0.0000000465
Hora de Término: 14:25:01
===========================================================================
==
Função avaliada: Davis
Método: Fletcher-Reeves/Gradiente Conjugado
Cálculo do Passo: Armijo
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.000100096647
Ponto Ótimo Final
x[1]= 0.0000000197
132
x[2]= 0.0000001637
Hora de Término: 14:25:04
===========================================================================
==
Função avaliada: Davis
Método: Davidson-Fletcher-Powel
Cálculo do Passo: Wolfe
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.009715909878
Ponto Ótimo Final
x[1]= 1.0369421316
x[2]= -2.9622191911
Hora de Término: 14:25:09
===========================================================================
==
Função avaliada: Davis
Método: Davidson-Fletcher-Powel
Cálculo do Passo: Goldstein
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.009722129614
Ponto Ótimo Final
x[1]= 1.6111082983
x[2]= -2.6963168038
133
Hora de Término: 14:25:13
===========================================================================
==
Função avaliada: Davis
Método: Davidson-Fletcher-Powel
Cálculo do Passo: Armijo
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.003939204574
Ponto Ótimo Final
x[1]= 0.0264902029
x[2]= 0.0560244352
Hora de Término: 14:25:17
===========================================================================
==
Função avaliada: Rastringin
Método: Gradiente
Cálculo do Passo: Wolfe
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 1.242020982729
Ponto Ótimo Final
x[1]= -0.0659383852
x[2]= -0.9805153121
Hora de Término: 14:26:01
134
===========================================================================
==
Função avaliada: Rastringin
Método: Gradiente
Cálculo do Passo: Goldstein
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 1.619281741915
Ponto Ótimo Final
x[1]= 1.0488574521
x[2]= -0.0801568740
Hora de Término: 14:26:08
===========================================================================
==
Função avaliada: Rastringin
Método: Gradiente
Cálculo do Passo: Armijo
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 1.745698867239
Ponto Ótimo Final
x[1]= 0.9158163950
x[2]= 0.0921072457
Hora de Término: 14:26:13
135
===========================================================================
==
Função avaliada: Rastringin
Método: Fletcher-Reeves/Gradiente Conjugado
Cálculo do Passo: Wolfe
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.000000000000
Ponto Ótimo Final
x[1]= -0.0000000000
x[2]= 0.0000000000
Hora de Término: 14:26:19
===========================================================================
==
Função avaliada: Rastringin
Método: Fletcher-Reeves/Gradiente Conjugado
Cálculo do Passo: Goldstein
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.000000000000
Ponto Ótimo Final
x[1]= -0.0000000000
x[2]= 0.0000000000
Hora de Término: 14:26:23
136
===========================================================================
==
Função avaliada: Rastringin
Método: Fletcher-Reeves/Gradiente Conjugado
Cálculo do Passo: Armijo
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.015364092730
Ponto Ótimo Final
x[1]= 0.0117958941
x[2]= 0.0107752446
Hora de Término: 14:26:28
===========================================================================
==
Função avaliada: Rosenbrock
Método: Gradiente
Cálculo do Passo: Wolfe
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.055730859957
Ponto Ótimo Final
x[1]= 0.9933657409
x[2]= 1.0220646193
Hora de Término: 14:36:17
137
===========================================================================
==
Função avaliada: Rosenbrock
Método: Gradiente
Cálculo do Passo: Goldstein
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.301970518766
Ponto Ótimo Final
x[1]= 1.0418141581
x[2]= 1.0320520982
Hora de Término: 14:36:25
===========================================================================
==
Função avaliada: Rosenbrock
Método: Gradiente
Cálculo do Passo: Armijo
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.004615960141
Ponto Ótimo Final
x[1]= 1.0062925509
x[2]= 0.9976255704
Hora de Término: 14:36:32
138
===========================================================================
==
Função avaliada: Rosenbrock
Método: Fletcher-Reeves/Gradiente Conjugado
Cálculo do Passo: Wolfe
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.451536210064
Ponto Ótimo Final
x[1]= 1.0000000000
x[2]= 1.0629396347
Hora de Término: 14:36:40
===========================================================================
==
Função avaliada: Rosenbrock
Método: Fletcher-Reeves/Gradiente Conjugado
Cálculo do Passo: Goldstein
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 1.065851533075
Ponto Ótimo Final
x[1]= 1.0051354011
x[2]= 1.0938699418
Hora de Término: 14:36:47
139
===========================================================================
==
Função avaliada: Rosenbrock
Método: Fletcher-Reeves/Gradiente Conjugado
Cálculo do Passo: Armijo
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 1.352751309939
Ponto Ótimo Final
x[1]= 1.0507853476
x[2]= 0.0392807016
Hora de Término: 14:36:54
===========================================================================
==
Função avaliada: Griewank
Método: Gradiente
Cálculo do Passo: Wolfe
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = -1.000000000000
Ponto Ótimo Final
x[1]= -0.0000000021
x[2]= -0.0000000258
Hora de Término: 14:39:24
140
===========================================================================
==
Função avaliada: Griewank
Método: Gradiente
Cálculo do Passo: Goldstein
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = -1.000000000000
Ponto Ótimo Final
x[1]= 0.0000000099
x[2]= -0.0000000000
Hora de Término: 14:39:28
===========================================================================
==
Função avaliada: Griewank
Método: Gradiente
Cálculo do Passo: Armijo
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = -1.000000000000
Ponto Ótimo Final
x[1]= -0.0000000091
x[2]= -0.0000000030
Hora de Término: 14:39:31
141
===========================================================================
==
Função avaliada: Griewank
Método: Fletcher-Reeves/Gradiente Conjugado
Cálculo do Passo: Wolfe
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = -1.000000000000
Ponto Ótimo Final
x[1]= 0.0000006881
x[2]= 0.0000000954
Hora de Término: 14:39:41
===========================================================================
==
Função avaliada: Griewank
Método: Fletcher-Reeves/Gradiente Conjugado
Cálculo do Passo: Goldstein
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = -0.999999999658
Ponto Ótimo Final
x[1]= -0.0000236085
x[2]= 0.0000154302
Hora de Término: 14:39:44
142
===========================================================================
==
Função avaliada: Griewank
Método: Fletcher-Reeves/Gradiente Conjugado
Cálculo do Passo: Armijo
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = -1.000000000000
Ponto Ótimo Final
x[1]= 0.0000000035
x[2]= -0.0000001549
Hora de Término: 14:39:47
===========================================================================
==
Função avaliada: Griewank
Método: Davidson-Fletcher-Powel
Cálculo do Passo: Wolfe
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = -1.000000000000
Ponto Ótimo Final
x[1]= 0.0000003182
x[2]= -0.0000007213
Hora de Término: 14:39:54
143
===========================================================================
==
Função avaliada: Griewank
Método: Davidson-Fletcher-Powel
Cálculo do Passo: Goldstein
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = -0.999999999751
Ponto Ótimo Final
x[1]= -0.0000171342
x[2]= -0.0000198421
Hora de Término: 14:40:01
===========================================================================
==
Função avaliada: Griewank
Método: Davidson-Fletcher-Powel
Cálculo do Passo: Armijo
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = -1.000000000000
Ponto Ótimo Final
x[1]= -0.0000008254
x[2]= -0.0000005726
Hora de Término: 14:40:07
144
===========================================================================
==
Função avaliada: Ackley
Método: Gradiente
Cálculo do Passo: Wolfe
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 5.180918588776
Ponto Ótimo Final
x[1]= -1.1776958139
x[2]= 0.6964678226
Hora de Término: 14:40:20
===========================================================================
==
Função avaliada: Ackley
Método: Gradiente
Cálculo do Passo: Goldstein
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 3.911957325043
Ponto Ótimo Final
x[1]= 0.7032908746
x[2]= -0.2657388236
Hora de Término: 14:40:23
145
===========================================================================
==
Função avaliada: Ackley
Método: Gradiente
Cálculo do Passo: Armijo
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.387898390177
Ponto Ótimo Final
x[1]= 0.0721409458
x[2]= 0.0341875433
Hora de Término: 14:40:25
===========================================================================
==
Função avaliada: Ackley
Método: Fletcher-Reeves/Gradiente Conjugado
Cálculo do Passo: Wolfe
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 2.790945224044
Ponto Ótimo Final
x[1]= -0.0129352890
x[2]= 1.0418580537
Hora de Término: 14:40:29
146
===========================================================================
==
Função avaliada: Ackley
Método: Fletcher-Reeves/Gradiente Conjugado
Cálculo do Passo: Goldstein
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.388247011052
Ponto Ótimo Final
x[1]= -0.0057251387
x[2]= -0.0798235141
Hora de Término: 14:40:32
===========================================================================
==
Função avaliada: Ackley
Método: Fletcher-Reeves/Gradiente Conjugado
Cálculo do Passo: Armijo
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 2.594182278140
Ponto Ótimo Final
x[1]= 0.0095516404
x[2]= 0.9293913532
Hora de Término: 14:40:35
147
===========================================================================
==
Função avaliada: Ackley
Método: Davidson-Fletcher-Powel
Cálculo do Passo: Wolfe
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 2.686537433106
Ponto Ótimo Final
x[1]= -0.0309260075
x[2]= -1.0083646354
Hora de Término: 14:40:41
===========================================================================
==
Função avaliada: Ackley
Método: Davidson-Fletcher-Powel
Cálculo do Passo: Goldstein
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 3.641424568794
Ponto Ótimo Final
x[1]= 1.0076793415
x[2]= -0.9369065738
Hora de Término: 14:40:45
148
===========================================================================
==
Função avaliada: Ackley
Método: Davidson-Fletcher-Powel
Cálculo do Passo: Armijo
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 100 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.007332780837
Ponto Ótimo Final
x[1]= 0.0008867916
x[2]= -0.0023718079
Hora de Término: 14:40:50
===========================================================================
==
Função avaliada: Schwefel
Método: Gradiente
Cálculo do Passo: Wolfe
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 1000 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.025353721554
Ponto Ótimo Final
x[1]= 421.1412406806
x[2]= 420.5552272312
149
Hora de Término: 14:50:28
===========================================================================
==
Função avaliada: Schwefel
Método: Gradiente
Cálculo do Passo: Goldstein
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 1000 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.168978202795
Ponto Ótimo Final
x[1]= 420.0333623681
x[2]= 420.2872132324
Hora de Término: 14:51:05
===========================================================================
==
Função avaliada: Schwefel
Método: Gradiente
Cálculo do Passo: Armijo
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 1000 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.034120197758
Ponto Ótimo Final
x[1]= 420.4810213298
x[2]= 420.7888194267
Hora de Término: 14:51:43
150
===========================================================================
==
Função avaliada: Schwefel
Método: Fletcher-Reeves/Gradiente Conjugado
Cálculo do Passo: Wolfe
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 1000 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.000038469122
Ponto Ótimo Final
x[1]= 420.9718611537
x[2]= 420.9590802437
Hora de Término: 14:52:02
===========================================================================
==
Função avaliada: Schwefel
Método: Fletcher-Reeves/Gradiente Conjugado
Cálculo do Passo: Goldstein
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 1000 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.000025588812
Ponto Ótimo Final
x[1]= 420.9680499396
x[2]= 420.9695042522
Hora de Término: 14:52:21
151
===========================================================================
==
Função avaliada: Schwefel
Método: Fletcher-Reeves/Gradiente Conjugado
Cálculo do Passo: Armijo
TMax = 1.00000000
M1 = 0.10000000
M2 = 0.70000000
DtMin = 0.00000100
Critérios de Parada:
Err = 0.00000100
NitMax = 10000 Número máximo de interações
NitIgualMax = 200 Número máximo de interações sem mudança no valor
da função
Região de Busca Limitada(Dist. Uniforme):
Limite Inferior = -1000 Limite Superior = 1000
Aplicar análise da População
TotPop = 1000 Total de números a serem gerados
++++++++++++++++++
-------------------
Valor da função = 0.000025884715
Ponto Ótimo Final
x[1]= 420.9700814544
x[2]= 420.9674728026
Hora de Término: 14:52:40
152
ANEXO 5
Área Total, População Residente e Densidade Demográfica
Município de São Paulo e Distritos Municipais
Ano de 2000
Densidade Populacional
Distritos População
Área em
Hectare
Hab/Ha Hab/m²
Hab/Km²
Município de S. Paulo 10.434.252
150.900
69,15
0,0069
6.915
Água Rasa 85.896
690
124,49
0,0124
12.449
Alto de Pinheiros 44.454
770
57,73
0,0058
5.773
Anhanguera 38.427
3.330
11,54
0,0012
1.154
Aricanduva 94.813
660
143,66
0,0144
14.366
Artur Alvim 111.210
660
168,50
0,0169
16.850
Barra Funda 12.965
560
23,15
0,0023
2.315
Bela Vista 63.190
260
243,04
0,0243
24.304
Belém 39.622
600
66,04
0,0066
6.604
Bom Retiro 26.598
400
66,50
0,0067
6.650
Brás 25.158
350
71,88
0,0072
7.188
Brasilândia 247.328
2.100
117,78
0,0118
11.778
Butantã 52.649
1.250
42,12
0,0042
4.212
Cachoeirinha 147.649
1.330
111,01
0,0111
11.101
Cambuci 28.717
390
73,63
0,0074
7.363
Campo Belo 66.646
880
75,73
0,0076
7.573
Campo Grande 91.373
1.310
69,75
0,0070
6.975
Campo Limpo 191.527
1.280
149,63
0,0150
14.963
Cangaíba 137.442
1.600
85,90
0,0086
8.590
Capão Redondo 240.793
1.360
177,05
0,0177
17.705
Carrão 78.175
750
104,23
0,0104
10.423
Casa Verde 83.629
710
117,79
0,0118
11.779
Cidade Ademar 243.372
1.200
202,81
0,0203
20.281
Cidade Dutra 191.389
2.930
65,32
0,0065
6.532
Cidade Líder 116.841
1.020
114,55
0,0115
11.455
Cidade Tiradentes 190.657
1.500
127,10
0,0127
12.710
Consolação 54.522
370
147,36
0,0147
14.736
Cursino 102.089
1.280
79,76
0,0080
7.976
Ermelino Matarazzo 106.838
870
122,80
0,0123
12.280
Freguesia do Ó 144.923
1.050
138,02
0,0138
13.802
Grajaú 333.436
9.200
36,24
0,0036
3.624
Guaianases 98.546
860
114,59
0,0115
11.459
Iguatemi 101.780
1.960
51,93
0,0052
5.193
Ipiranga 98.863
1.050
94,16
0,0094
9.416
Itaim Bibi 81.456
990
82,28
0,0082
8.228
Itaim Paulista 212.733
1.200
177,28
0,0177
17.728
Itaquera 201.512
1.460
138,02
0,0138
13.802
Jabaquara 214.095
1.410
151,84
0,0152
15.184
Jaçanã 91.809
780
117,70
0,0118
11.770
Jaguara 25.713
460
55,90
0,0056
5.590
Jaguaré 42.479
660
64,36
0,0064
6.436
Jaraguá 145.900
2.760
52,86
0,0053
5.286
Jardim Ângela 245.805
3.740
65,72
0,0066
6.572
Jardim Helena 139.106
910
152,86
0,0153
15.286
Jardim Paulista 83.667
610
137,16
0,0137
13.716
Jardim São Luiz 239.161
2.470
96,83
0,0097
9.683
153
José Bonifácio 107.082
1.410
75,94
0,0076
7.594
Lajeado 157.773
920
171,49
0,0171
17.149
Lapa 60.184
1.000
60,18
0,0060
6.018
Liberdade 61.875
370
167,23
0,0167
16.723
Limão 82.045
630
130,23
0,0130
13.023
Mandaqui 103.113
1.310
78,71
0,0079
7.871
Marsilac 8.404
20.000
0,42
0,0000
42
Moema 71.276
900
79,20
0,0079
7.920
Moóca 63.280
770
82,18
0,0082
8.218
Morumbi 34.588
1.140
30,34
0,0030
3.034
Parelheiros 102.836
15.350
6,70
0,0007
670
Pari 14.824
290
51,12
0,0051
5.112
Parque do Carmo 64.067
1.540
41,60
0,0042
4.160
Pedreira 127.425
1.870
68,14
0,0068
6.814
Penha 124.292
1.130
109,99
0,0110
10.999
Perdizes 102.445
610
167,94
0,0168
16.794
Perus 70.689
2.390
29,58
0,0030
2.958
Pinheiros 62.997
800
78,75
0,0079
7.875
Pirituba 161.796
1.710
94,62
0,0095
9.462
Ponte Rasa 98.113
640
153,30
0,0153
15.330
Raposo Tavares 91.204
1.260
72,38
0,0072
7.238
República 47.718
230
207,47
0,0207
20.747
Rio Pequeno 111.756
970
115,21
0,0115
11.521
S.Miguel Paulista 228.283
750
160,76
0,0161
16.076
Sacomã 71.179
1.420
182,51
0,0183
18.251
Santa Cecília 124.654
390
98,93
0,0099
9.893
Santana 60.539
1.260
38,81
0,0039
3.881
Santo Amaro 82.834
1.560
82,83
0,0083
8.283
São Domingos 139.333
1.000
140,74
0,0141
14.074
São Lucas 154.850
990
119,12
0,0119
11.912
São Mateus 97.373
1.300
129,83
0,0130
12.983
São Rafael 125.088
1.320
94,76
0,0095
9.476
Sapopemba 282.239
1.350
209,07
0,0209
20.907
Saúde 118.077
890
132,67
0,0133
13.267
Sé 20.115
210
95,79
0,0096
9.579
Socorro 39.097
1.290
30,31
0,0030
3.031
Tatuapé 79.381
820
96,81
0,0097
9.681
Tremembé 163.803
5.630
29,09
0,0029
2.909
Tucuruvi 99.368
900
110,41
0,0110
11.041
Vila Andrade 73.649
1.030
71,50
0,0072
7.150
Vila Curuçá 146.482
970
151,01
0,0151
15.101
Vila Formosa 93.850
740
126,82
0,0127
12.682
Vila Guilherme 49.984
690
72,44
0,0072
7.244
Vila Jacuí 141.959
770
184,36
0,0184
18.436
Vila Leopoldina 26.870
720
37,32
0,0037
3.732
Vila Maria 113.845
1.180
96,48
0,0096
9.648
Vila Mariana 123.683
860
143,82
0,0144
14.382
Vila Matilde 102.935
890
115,66
0,0116
11.566
Vila Medeiros 140.564
770
182,55
0,0183
18.255
Vila Prudente 102.104
990
103,14
0,0103
10.314
Vila Sônia 87.379
990
88,26
0,0088
8.826
Elaborção: Sempla/Dipro
154
ANEXO 6
155
ANEXO 7
Fases de Execução do Programa
Passo 1: Escolha o método para a resolução do problema de PNL
Passo 2: Escolha o método pra o cálculo do passo, bem como os parâmetros associados a eles.
Passo 3: Defina se deseja que seja aplicado o Método de Simulated Annealing. Este método será aplicado após a
otimização inicial feito pelos métodos definidos anteriormente.
156
ANEXO 8
Resumo dos trabalhos analisados no capítulo 2:
Modelos Apresentados
Autores/Ano Tema/Assunto Parâmetros
Analisados
Resultado
Encontrado
Furth e Rahbee
(2000)
Propõem um modelo
discreto para modelar
o impacto de
mudança no
espaçamento entre
paradas de ônibus
numa rota específica.
Os atrasos causados
pela demora dos
usuários, o aumento
dos custos
operacionais devido
a esses atrasos.
O espaçamento
aumentou de 200 m
para 400 m.
Gonçalves (1995) Um estudo cujo
enfoque foi o
detalhamento da
análise do problema
operacional de uma
linha de ônibus
urbano, englobando
conjuntamente o
ponto de vista do
operador e do
usuário.
A pesquisa foi feita
utilizando a linha
número 11 - Monte
Verde/Florianópolis,
na cidade de
Florianópolis/SC.
Foram feitos
levantamentos dos
dados referentes ao
tempo de
deslocamento do
veículo, ao tempo de
parada nos pontos, ao
tempo de embarque e
desembarque de
passageiros e à
velocidade de
deslocamento do
ônibus.
Hoje existem 58
pontos, com um
espaçamento médio
de 392 m. Simulou-
se uma redução para
44 pontos. Observou-
se que houve um
ganho, tanto para os
usuários, como
também para o
operador.
Houve uma redução
de 3,2% no custo
total dos usuários e
de 2,8% no custo do
operador. O tempo
de viagem foi
reduzido de 4,1% ( 2
min. 39 seg. ).
Saka (2001) Model For
Determining
Optimum Bus-Stop
Spacing In Urban
Areas
Tempo de aceleração
e desaceleração;
Tempo de embarque
e desembarque de
passageiros;
Tempo de atraso
devido a dispositivos
de controle de
tráfego (Sinais de
trânsito);
Tempo de viagem em
velocidade normal de
tráfego.
Ver próximo artigo.
(Kehoe, 2004), Effects of Bus Stop
Consolidation on
Transit Speed and
Reliability: a Test
Case
Utilizou o modelo
apresentado por Saka
(2001) para
aprimorar a rota 48
da cidade de Seattle,
Através desse
modelo foi possível
aumentar o
espaçamento médio
entre as paradas de
157
estado de
Washington, USA
218m para 260m,
sem prejuízo para os
usuários.
Kuah e Perl (1988) Optimization of
Feeder Bus Routes
and Bus-Stop
Spacing.
É proposto um
modelo analítico para
o projeto de uma
rede de linhas de
ônibus que seriam
utilizadas para a
alimentação de uma
linha de trem
existente
O objetivo do
trabalho é encontrar
um modelo que
otimize as três
variáveis básicas:
Espaçamento entre as
linhas;
Intervalo entre
ônibus;
Espaçamento entre as
paradas.
O espaçamento
ótimo entre as
paradas é uma função
da raiz quadrada de
parâmetros
relevantes.
Ele aumenta com:
A velocidade a pé;
Valor do tempo a
bordo;
Tempo médio
perdido nas paradas;
Ele diminui com o
valor do tempo da
viagem a pé.
Murray e Wu (2003) Método de
modelagem integrada
para examinar e
planejar o
espaçamento ideal
entre os pontos de
parada de ônibus a
fim de melhorar a
acessibilidade dos
usuários ao sistema.
A acessibilidade é
percebida em termos
espaciais através da
distância física do
usuário até a parada
ou estação mais
próxima.
O modelo foi
aplicado a uma rota
de transporte coletivo
da cidade de
Columbus, Ohio-
USA.
Número atual de
paradas: p=164;
A partir de 120
paradas a distância
média de acesso
quase não diminui;
Para p=75 a redução
no número de pontos
de parada é de
42,07% e o aumento
na média da distância
de acesso é de 7,77%
(apenas 15m em
média);
Ainda para p=75 o
aumento no
espaçamento entre os
pontos de parada é de
72,63% (passa dos
atuais 265m para
457,38m).
Suzuki (1987) Um estudo sobre
uma linha de ônibus
em Ichikawa, Japão.
Ele utilizou conceitos
de Diagramas de
Voronoi para
estabelecer o
espaçamento ótimo
entre paradas de
ônibus numa linha
alimentadora visando
minimizar o tempo
médio de viagem dos
Partiu do princípio
que o usuário se
desloca até o ponto
mais próximo da
linha de ônibus e, a
partir desse ponto,
procura a parada
mais próxima.
O espaçamento
inicial era de 325m,
com 15 pontos de
parada (n=15).
A solução ótima
encontrada foi para
n=8, com um
espaçamento entre os
pontos de 608m.
158
passageiros até um
destino comum.
Novaes et. al. (2009) Utilizaram conceitos
de diagramas de
Voronoi e modelos
de aproximação
contínua para
resolver um
problema de
localização de
estações de metrô
numa região urbana
que também é
servida por uma linha
de ônibus.
O problema em
questão é encontrar o
número ideal de
estações, bem como
as suas respectivas
localizações, a fim de
maximizar
arrecadação da linha
do metrô, ou seja,
atrair o maior
número de
passageiros possível
O valor ideal é
obtido com s = 4, ou
seja, 4 estações de
metrô.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo