Coordenação de Múltiplos Veículos Autônomos de Entrega Usando K-Means e Algoritmos Bio-Inspirados

Coordination of Multiple Self-driving Cars of Delivery Using K-Means and Bio-Inspired Algorithms

dc.contributorAlves, Raulcézar Maximiano Figueira
dc.contributorhttp://lattes.cnpq.br/9271560213358590
dc.contributorSouza, Jefferson Rodrigo de
dc.contributorhttp://lattes.cnpq.br/1805897404307170
dc.contributorMartins, Luiz Gustavo Almeida
dc.contributorRocha Filho, Geraldo Pereira
dc.creatorSilva, Clênio Eduardo da
dc.date2020-09-01T21:25:45Z
dc.date2020-09-01T21:25:45Z
dc.date2020-07-29
dc.date.accessioned2023-09-28T20:25:12Z
dc.date.available2023-09-28T20:25:12Z
dc.identifierSILVA, 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.
dc.identifierhttps://repositorio.ufu.br/handle/123456789/29807
dc.identifierhttp://doi.org/10.14393/ufu.di.2020.563
dc.identifier.urihttps://repositorioslatinoamericanos.uchile.cl/handle/2250/9050469
dc.descriptionWith 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.
dc.descriptionDissertação (Mestrado)
dc.descriptionCom 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.
dc.formatapplication/pdf
dc.languagepor
dc.publisherUniversidade Federal de Uberlândia
dc.publisherBrasil
dc.publisherPrograma de Pós-graduação em Ciência da Computação
dc.rightsAcesso Aberto
dc.rightshttp://creativecommons.org/licenses/by-nc-nd/3.0/us/
dc.subjectAlgoritmos bio-inspirados
dc.subjectmTSP
dc.subjectPlanejamento de caminhos
dc.subjectSistema de escalonamento de rotas
dc.subjectVeículos autônomos
dc.subjectBio-inspired algorithms
dc.subjectPath planning
dc.subjectRoute scheduling system
dc.subjectAutonomous vehicles
dc.subjectComputação
dc.subjectK-means
dc.subjectComputing
dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
dc.subjectComputação
dc.titleCoordenação de Múltiplos Veículos Autônomos de Entrega Usando K-Means e Algoritmos Bio-Inspirados
dc.titleCoordination of Multiple Self-driving Cars of Delivery Using K-Means and Bio-Inspired Algorithms
dc.typeDissertação


Este ítem pertenece a la siguiente institución