Info4
Python
Projet réalisé dans le cadre de mes études à Polytech Lyon, avec Maxime Antoine, Jules Ginhac et Pablo Verchère, sous la supervision de M. Bonnevay Stéphane. L’objectif était de développer un programme Python pour trouver le plus court chemin entre 100 points sur une carte. Ce projet est une version du problème du voyageur de commerce (TSP).
Le programme permettait de choisir entre 1 camion pour livrer tous les points ou plusieurs camions. Il a été développé avec la bibliothèque Turtle de Python. Les algorithmes utilisés étaient : plus proche voisin pour la solution initiale, puis 2-opt, relocate et swap pour la recherche locale. Tous ces algorithmes ont été développés par notre équipe.
Le programme possédait une interface graphique affichant en temps réel le meilleur trajet courant. Toutes les données étaient sauvegardées en fichiers .xlsx pour permettre l’analyse des résultats. Pour ce projet, nous avons terminé 1ers sur 40 groupes, avec la note de 19/20.
English version
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.