Description
An optimization algorithm by QCentroid
The TSP or Travelling Salesperson Problem is a classic optimization problem. The problem is, essentially, the following:
We are a Salesperson and we must visit several cities in order to sell all our products to as many people as possible. The cities are distant from each other, so we cannot sell anything in the middle of the travel. In addition, the travel makes us lose money since there are some expenses, manteinance and accomodation, to defray. Thus, we are interested in finding the route with the less possible travel time.
This problem is known to be NP-Complete, that is, it is really hard to find the optimal solution to it. If we want to visit N cities, then we must find the optimal path among N! possible itineraries. Comparing one solution to another one is easy, but finding the best one is similar to looking for a needle in a haystack.
In this example, we need to determine a list of cities to visit. These cities should be the capitals of any country in the world. There are some additional calculations to extract the distances between all different pairs of cities. Then, a matrix with distances is introduced into the QCentroid API, who looks for the optimal solution in an easy way. The solution is showed afterwards.
Take into account that the hardest piece of this problem is finding the optimal solution. This step is completely addressed by the QCentroid, while the users / cabin boys and girls do not have to worry about it.
