In this project we shall discuss on the Travelling Salesman Problem (TSP) a very famous NP-hard problem and will take a few attempts to solve it, using Dynamic programming, or by using approximation algorithms (GVNS) and work on the corresponding python implementations.
- Clone the project on your machine with :
git clone https://github.com/zakariamejdoul/tsp_solving_dp_gvns.git
- Run all cells in Jupyter Notebook file named main-app.ipynb.
- Put the instance path (you can use the instances provided in the folder named instances).
- Put your choice : 1 for dynamic programming method and 2 for GVNS metaheuristic method.
- Put your source city (the numbering order of cities starts with 1).
- If you have selected the choice 2 (GVNS method) you must provide the maximum execution time
of the program in minutes. - Enjoy the results !
Results include the optimal path, the optimal distance and the target plot.
Your matrix :
0, 12, 10, 19, 8
12, 0, 3, 7, 2
10, 3, 0, 6, 20
19, 7, 6, 0, 4
8, 2, 20, 4, 0
TSP solver
******* Menu *******
Please choose one of these methods :
(1) Solve with dynamic programming
(2) Solve with GVNS
OPTIMAL POLICY : [3, 1, 5, 4, 2, 3]
OPTIMAL VALUE : 32
Generated coordinates of cities :
[[32 33]
[23 32]
[38 21]
[16 21]
[10 32]]