Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/29807
ORCID:  http://orcid.org/0000-0002-6858-8037
Document type: Dissertação
Access type: Acesso Aberto
Title: Coordenação de Múltiplos Veículos Autônomos de Entrega Usando K-Means e Algoritmos Bio-Inspirados
Alternate title (s): Coordination of Multiple Self-driving Cars of Delivery Using K-Means and Bio-Inspired Algorithms
Author: Silva, Clênio Eduardo da
First Advisor: Souza, Jefferson Rodrigo de
First coorientator: Alves, Raulcézar Maximiano Figueira
First member of the Committee: Martins, Luiz Gustavo Almeida
Second member of the Committee: Rocha Filho, Geraldo Pereira
Summary: Com o surgimento de carros autônomos, várias tarefas podem ser automatizadas, além do transporte de pessoas, como a entrega de mercadorias. Para reduzir custos e esforços, essa tarefa pode ser atribuída a uma frota de carros que deve cobrir um conjunto de locais de entrega. Esta dissertação apresenta o desenvolvimento de uma abordagem híbrida como uma solução para o problema de múltiplos caixeiros viajantes, (do inglês, multiple Traveling Salesman Problem - mTSP) aplicado ao escalonamento de rotas para veículos autônomos. Inicialmente, usamos o K-means como um pré-processamento para gerar rotas que distribuem os locais de entrega entre os carros. Em seguida, essas rotas são definidas como população inicial para os algoritmos bio-inspirados: Algoritmo Genético (GA) e Colônia de Formigas em sua versão (ACS). Esses algoritmos executam um processo evolutivo para encontrar uma rota que minimize a distância geral, mantendo o equilíbrio das rotas individuais de cada carro. Os experimentos foram conduzidos em um sistema de escalonamento de rotas em ambientes virtuais (simulação) e em um estudo de caso no Campus 2 da Universidade de São Paulo. Nos experimentos, foram realizadas comparações das abordagens híbridas, K-means-GA e K-means-ACS com as suas versões sem pré-processamento, com a geração da população inicial de forma aleatória. Além das comparações com GA e ACS foram realizadas comparações com o algoritmo de Otimização por Enxame de Partículas (PSO). Os resultados apontam que à medida que o número de carros e locais de visita aumentam, as abordagens híbridas superam suas versões clássicas e o PSO. Para avaliação dos resultados foram aplicados um teste não paramétrico kruskal wallis seguido de um teste de comparações múltiplas Dunn-Bonferroni.
Abstract: With the emergence of self-driving cars, several tasks can be automated in addition to transporting people, such as delivering goods. To reduce costs and efforts, this task can be assigned to a fleet of cars that must cover a set of delivery locations. This dissertation presents the development of a hybrid approach as a solution for the multiple Traveling Salesman Problem (mTSP) applied to the route scheduling for self-drive cars. Initially, we used K-means as pre-processing to generate routes that distribute delivery locations between cars. Then, these routes are defined as the initial population for the bio-inspired algorithms: Genetic Algorithm (GA) and Ant Colony in its version (ACS). These algorithms perform an evolutionary process to find a route that minimizes the overall distance, maintaining the balance of the individual routes of each car. The experiments were conducted in the route scheduling system in virtual environments (simulation) and in a case study at Campus 2 of the University of São Paulo. In the experiments, comparisons of the hybrid approaches, K-means-GA and K-means-ACS were made with their versions without pre-processing, with the initial population generation at random. In addition, to comparisons were also made with Particle Swarm Optimization (PSO). The results show that as the number of cars and places increases, the hybrid approaches surpass their classic versions and also the PSO. To evaluate the results, a nonparametric test kruskal wallis followed by a test of multiple comparison test Dunn-Bonferroni were applied.
Keywords: Algoritmos bio-inspirados
mTSP
Planejamento de caminhos
Sistema de escalonamento de rotas
Veículos autônomos
Bio-inspired algorithms
Path planning
Route scheduling system
Autonomous vehicles
Computação
K-means
Computing
Area (s) of CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Subject: Computação
Language: por
Country: Brasil
Publisher: Universidade Federal de Uberlândia
Program: Programa de Pós-graduação em Ciência da Computação
Quote: SILVA, Clênio Eduardo da. Coordenação de Múltiplos Veículos Autônomos de Entrega Usando K-Means e Algoritmos Bio-Inspirados. 2020. 147 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Uberlândia, Uberlândia, 2020. Disponível em: http://doi.org/10.14393/ufu.di.2020.563.
Document identifier: http://doi.org/10.14393/ufu.di.2020.563
URI: https://repositorio.ufu.br/handle/123456789/29807
Date of defense: 29-Jul-2020
Appears in Collections:DISSERTAÇÃO - Ciência da Computação

Files in This Item:
File Description SizeFormat 
CoordenacaoMultiplosVeiculos.pdfDissertação19.73 MBAdobe PDFThumbnail
View/Open


This item is licensed under a Creative Commons License Creative Commons