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. Model TSP as ILP formulation w/o Subtour constraints
  2. Implement Subtour Elimination Method 1: MTZ’s Approach
  3. Implement Subtour Elimination Method 2: DFJ’s Approach
  4. Compare MTZ’s formulation and DFJ’s formulation
  5. Conclusion

The…

Aayush Aggarwal

AI Reseacher | IIT Bombay Alumnus

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store