Travelling Salesman Problem (TSP) is one of the most popular data science and operational research problems. The problem seeks the shortest path of visiting every given destination at least once without any interruption.
TSP is an NP-hard problem, a problem without any polynomial-time exact approach, widely used for testing algorithms and methods because of its simple formulation and high practical relevance. We provide a simple example of the problem.
You are planning to go on a road trip and visit three cities along the way: A and B. To save up fuel, you want to know which sequence of cities should you take to minimize the distance. The table below provides information of distances between each city and your home.
The objective of TSP is minimizing the total traveled distance; Hence, it could be expressed as:
The objective function simply means minimize the sum of all distances from location I to location j. Moreover, TSP has three main constraints to satisfy: Predecessor constraint, successor constraint, and sub-cycle constraint.
Predecessor constraints prevent a location to be visited more than once, and successor constraints prevent leaving from the same place more than once.
Predecessor Constraints:
The constraint means the sum of the path chosen from all location I to location j is exactly one. In other words, only one path with a destination of location j is chosen.
Successor Constraints:
Opposite to predecessor constraint, this constraint means the sum of the path chosen from location I to all location j is exactly one. In other words, only one path from location i is chosen.
For our example we could express the model mathematically:
min 𝑥0 = 100𝑥𝐻𝐴 + 30𝑥𝐻𝐵 + 80𝑥𝐴𝐻 + 170𝑥𝐴𝐵 + 160𝑥𝐵𝐻 + 120𝑥𝐵𝐴
Predecessor Constraints:
𝑥𝐻𝐴 + 𝑥𝐵𝐴 = 1
𝑥𝐻𝐵 + 𝑥𝐴𝐵 = 1
𝑥𝐴𝐻 + 𝑥𝐵𝐻 = 1
Successor Constraints:
𝑥𝐻𝐴 + 𝑥𝐻𝐵 = 1
𝑥𝐴𝐻 + 𝑥𝐴𝐵 = 1
𝑥𝐵𝐻 + 𝑥𝐵𝐴 = 1
Many approaches are available for solving Travelling Salesman Problems. The branch and Bound method is the popular exact method for solving TSP by breaking the problem into several smaller problems.
Heuristics approaches are also viable for Travelling Salesman Problems such as Naïve or Greedy Heuristics for construction heuristics and Tabu Search or Genetic Algorithms for improvement heuristics.
Comments