Travelling salesman problem (TSP) implementation: IBM OPL vs Genetic Algorithm

Research project to explore exact and metaheuristic approaches to solve the TSP. Project developed using IMB OPL and Python.

Description

The project explores the implementation of an exact optimization algorithm and a heuristic algorithm (genetic algorithm) to solve the travelling salesman problem. The exact algorithm was implemented in IMB OPL while the genetic algorithm was implemented in Python using the deap library. Parameter exploration and tuning was done with the Python library hyperopt. Both models were run on 80 instances with different number of points, using different time constraints: 0.1s, 1s, 10s, 30s, 80s and the results were compared. A final report was generated, summarising the results achieved in the project.

Project structure

• 001-generate-points.py Contains the logic for generating the point distributions, the script previews the generated distribution and stores it inside the respective /points folders after user approval;
• 002-optimize.py Runs the optimization process through a batch script that calls the OPL solver, this is done on all instances created at the previous step. The OPL model is stored inside the /opl-model folder;
• 003-extract-results.py Extracts the results from the files generated by OPL at the previous step and stores them in a convenient way in the results.json file;
• The files genetic_model.py and helpersGeneticAlgo.py contain the implementation of the genetic algorithm using the deap python library and some custom functions for crossover and mutation;
• 004-hypspace-exploration.py Performs the parameter space exploration for the genetic algorithm using the hyperopt python library;
• 005-parameter-exploration-analysis.ipynb Is a jupyter notebook performing the analysis on the results of the parameter space exploration;
• 006-optimize-genetic.py Runs the optimization process with the genetic algorithm, this is done on all instances created at the first step;
• 007-genetic-algo-animation.ipynb Generates an animation showing the evolution of the individuals across the various generations of the genetic algorithm;
• 008-analysis.ipynb Is a jupyter notebook performing the analysis on the performances of the exact and genetic algorithms.

Additional info on using the project files

Some additional information may be found in the pdf report.

License

Use as you wish. This project is licensed under the MIT License.