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

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.