Traveling Salesman

Traveling Salesman(TSP) is a standard problem and have seen a huge progress over the years. This is an NP Hard. Various algorithms have been used for both exact methods and heuristics to solve the TSP.

How to run

1. python envrionment: python3.7
2. pip install -r requirements.txt
3. python main.py

Note about gurobi: If you just pip install gurobi or follow the above pip install -r requirements.txt, you cannot activate gurobi through license. The detailed things on website: https://support.gurobi.com/hc/en-us/articles/360044290292-How-do-I-install-Gurobi-for-Python-

conda install -c gurobi gurobi

since if you don't activate gurobi, you cannot run 50 cities test since it have size-limited license.

After install by conda, you can input license like this way:

Objective

I am always eager to learn and explore. I am recently learning more about metaheuristics, better programming, using solvers. The objectives of my this project are:

1. Compare the computational time for Genetic Algorithm, Using Gurobi's CallBack functions to add Subtour Elimination Constraints (SEC), adding SEC using graphs, Gurobi's Start Method.
2. Second objective is to learn better coding practices using PyCharm and Python. Objective was to build the code from software building perspectives.
3. Learning Gurobi's features.

Work In Progress

Current Status: I have built the models, set up the model execution. Following image shows the comparison for SEC and MTZ models for 10 instances with a maximum cities of 50. Further, I will need to perform the experiment considering the CallBacks.

Folder and script Details

• Models Folder
  • city.py: Randomly generates the cities of given size and then calculates the distance between those cities.
  • secFormulation.py: This is the main class which builds the model and has methods to add SEC constraints on the fly using different methods.
  • mtzFormulation.py: Inherits from the secFormulation.py and adds the MTZ constraints with an option of initial starting solution.
  • usingCallBacks.py: Inherits from the secFormulation.py and adds the Gurobi's CallBack features.
  • geneticAlgorithm.py: A metaheuritic to build the initial solution which is then used in mtzFormulation.py
  • executeModels.py: This module sets up the experimentation and visualization of results.
• main.py: This uses the executeModels.py to execute the experiments.