The Multiple Traveling Salesman Problem is an extension of the classic Traveling Salesman Problem, which seeks to find the shortest possible route that visits each city in a given set and returns to the starting city. In the MTSP, there are multiple salesmen who start from a central depot, visit a subset of cities, and return to the depot. The goal is to minimize the total distance traveled by all salesmen while ensuring that every city is visited exactly once. Genetic Algorithms are a type of optimization technique inspired by natural selection and evolution. They work by creating a population of candidate solutions, evaluating their fitness, selecting the fittest individuals, and applying genetic operators such as crossover and mutation to generate new offspring. This process repeats until a satisfactory solution is found or a predetermined number of generations have been produced. In this implementation we have developed a GA in order to face this problem and see how it performs.

Please refer to the pdf in order to read our full implementation.

git clone https://github.com/pepe-olivert/GA_competition.git

Once you have it downloaded just execute GA.py and check it out!

Add into your GA.py the following code in order to make it run:

if __name__ == '__main__':
    a = GA(time_deadline=180,problem_path='instances/instance1.txt')
    try:print(a.run(),1/a.best_fitness)
    except:print(a.get_best_solution(),1/a.best_fitness)

And then just execute it:

python3 GA.py

Please note: Make sure to have python installed in your machine.

Pull requests are welcome. For major changes, please open an issue first to discuss what you would like to change.

Please make sure to update tests as appropriate.