Info4

Project carried out as part of my studies at Polytech Lyon, with Maxime Antoine, Jules Ginhac, and Pablo Verchère under the supervision of M. Bonnevay Stéphane. The goal of the project was to develop a Python program to find the shortest path between 100 points on a map. This project was a version of The Salesman problem (TSP).

The program allowed the user to choose between 1 truck to deliver all of the points or multiple trucks. The program was developed using the Python library Turtle, and the algorithm used was the nearest neighbor algorithm for the initial solution, and 2-opt, relocate and swap for the local search. All of the algorithms were developed by us.

The program had a GUI that showed in real time the current best path. All of the data was saved in .xlsx files to allow us to analyze the results. For this project, we were ranked 1 out of 40 groups, with a grade of 19/20.