23rd EANN / EAAAI 2022, 17 - 20 June 2022, Greece

Route Scheduling System for multiple self-driving cars using K-means and bio-inspired algorithms

Clenio E. Silva, Tiago S. César, Junior A. R. Silva, Iago P. Gomes, Denis F. Wolf, Raulcézar Alves, Jefferson R. Souza


  This paper presents the development of a hybrid approach as a solution to the multiple Traveling Salesman Problem (mTSP) applied to the route scheduling for self-drive cars. First, we use k-means to generate routes that equality distribute delivery locations among the cars. Then, these routes are set as the initial population for bio-inspired algorithms, such as Genetic Algorithm (GA) and Ant Colony System (ACS), that perform an evolutionary process in order to find a route which minimizes the overall distance while keeping the balance of individual tours of each car. The experiments were conducted with our route scheduling system in real and virtual environments. We compared our hybrid approaches using k-means in conjunction with GA and ACS against GA, ACS and Particle Swarm Optimization (PSO) initialized with random population. The results showed that, as the number of cars and target locations increase, the hybrid approaches outperform GA, ACS and PSO without any pre-processing.  

*** Title, author list and abstract as seen in the Camera-Ready version of the paper that was provided to Conference Committee. Small changes that may have occurred during processing by Springer may not appear in this window.