Dissertação
Planejamento de rotas veiculares e otimização de mobilidade urbana utilizando algoritmo bioinspirado e paralelo
Registro en:
PAZ, Fillipe Almeida. Planejamento de rotas veiculares e otimização de mobilidade urbana utilizando algoritmo bioinspirado e paralelo. 2022. 89 f. Dissertação (Mestrado em Ciência da Computação) – Universidade Federal de Sergipe, São Cristóvão, 2022.
Autor
Paz, Fillipe Almeida
Institución
Resumen
The concentration of the world’s population in urban areas has posed challenges to the quality
of life of citizens. Traffic jams, increased air pollution, waste of natural resources and reduced
productivity of citizens are some examples of damage resulting from poor mobility in cities.
Simultaneously, technologies applied to cities can help mitigate these effects, improving society’s
quality of life and producing a more environmentally and economically sustainable environment.
Processes and technologies for data collection, analysis and transmission make up the ecosystem
of smart cities and can help in decision-making in order to optimize resources. However, although
the amount of data regarding the situation of urban traffic is considerable, the dynamic planning
of vehicular routes that takes into account a large amount of roads, vehicles and calculations on
real-time data is limited due to the computing time involved.
In this context, this work aims to experimentally evaluate the impact of dynamic vehicular
routing on metrics related to urban mobility and computing time. Heuristic-based, classical
and bio-inspired algorithms were evaluated under different road flow conditions, with emphasis
on PPUMO (Parallel and Pheromone-based Urban Mobility Optmization), an algorithm for
vehicular routing proposed in this work.
It was evidenced in the Results of this work that PPUMO was able to produce the best results
among the treatments when analyzed in relation to the metrics Timeloss (reduction of up to
27.8%, on average); Trip Duration (up to 28.4% reduction on average); Jams (up to 73.9%
reduction on average) for high load conditions on the traffic system. It was also possible to verify
that the PPUMO presented a route replanning time 10000 times smaller compared to the serial
algorithms. Especially with regard to vehicle travel time, as it was the best choice in 80% of the
evaluated scenarios. Finally, with regard to route length, PPUMO achieved lower or close to
lower results compared to the base case and distanced itself from the approaches that performed
route replanning by up to 32.4%, on average.
This work contributes to the identification of strengths and weaknesses associated with the use
of dynamic routing based on deterministic or probabilistic, classical or bioinspired algorithms.
Here is also proposed a dynamic vehicular routing architecture that foresees the use of 5G V2X
networks for data transmission in an Intelligent Transport System. Finally, it is intended that the
implementations of this work serve as a software artifact for the development of solutions for the
maximization of urban mobility. A concentração da população mundial nas áreas urbanas tem imposto desafios à qualidade de
vida dos cidadãos. Congestionamentos, aumento da poluição atmosférica, desperdício de recursos
naturais e redução da produtividade dos cidadãos são alguns exemplos de prejuízos decorrentes
da mobilidade precária nas cidades. Simultaneamente, tecnologias aplicadas às cidades podem
ajudar na mitigação desses efeitos, melhorando a qualidade de vida da sociedade e fomentando
um ambiente mais sustentável ambiental e economicamente.
Processos e tecnologias de coleta, análise transmissão de dados compõem o ecossistema das
cidades inteligentes e podem auxiliar na tomada de decisão de forma a otimizar os recursos.
Contudo, ainda que a quantidade de dados a respeito a situação do tráfego urbano seja considerável,
o planejamento dinâmico de rotas veiculares que leve em consideração uma grande quantidade
de vias, veículos e cálculos sobre os dados em tempo real vê-se limitado em virtude do tempo de
computação envolvido.
Nesse contexto, este trabalho tem por objetivo avaliar experimentalmente o impacto de roteamento
veicular dinâmico sobre métricas relativas à mobilidade urbana e tempo de computação. Foram
avaliados algoritmos heurísticos, clássicos e bio-inspirados sob diferentes condições de fluxo
viário, com ênfase no PPUMO (Parallel and Pheromone-based Urban Mobility Optmization),
algoritmo para roteamento veicular proposto neste trabalho.
Ficou evidenciado nos Resultados deste trabalho que o PPUMO foi capaz de produzir os melhores
resultados dentre os tratamentos analisados com relação às métricas Timeloss (redução de até
27.8%, em média); Trip Duration (redução de até 28.4%, em média); Jams (redução de até 73.9%,
em média) para condições de elevada carga no sistema de tráfego. Foi possível constatar ainda
que o PPUMO chegou a apresentar um tempo replanejamento de rotas 10000 vezes menor se
comparado aos algoritmos seriais. Especialmente com relação ao tempo de viagem dos veículos,
pois apresentou-se como a melhor escolha em 80% dos cenários avaliados. Finalmente, com
relação ao comprimento de rota, o PPUMO alcançou resultados menores ou próximo do menor
se comparado ao caso base e distanciou-se das abordagens que realizaram replanejamento de
rotas em até 32.4%, em média.
Este trabalho contribui para: a identificação de pontos positivos e fraquezas associadas ao uso
de roteamentos dinâmicos baseados em algoritmos determinísticos ou probabilísticos, clássicos
ou bioinspirados. Aqui também é proposta uma arquitetura de roteamento veicular dinâmico
que prevê o uso de redes 5G V2X para a transmissão de dados em um Sistema Inteligente de
Transporte. Por fim, intenciona-se que as implementações deste trabalho sirvam como artefato de
software para o desenvolvimento de soluções para a maximização da mobilidade urbana. São Cristóvão