INTRODUCTION

In this article, I will explain and implement the well-known Traveling Salesman Problem aka TSP with a special focus on subtour elimination methods. We will use python to implement the MILP formulation. The dataset contains the coordinates of various cities of India. The aim is to find the shortest path that covers all cities. We will cover the following points in this article

1. Input the data and visualize the problem
2. Model TSP as ILP formulation w/o Subtour constraints
3. Implement Subtour Elimination Method 1: MTZ’s Approach
4. Implement Subtour Elimination Method 2: DFJ’s Approach
5. Compare MTZ’s formulation and DFJ’s formulation
6. Conclusion

The…