Travelling Salesman Problem
Miguel Casquilho · 2012
With optimization in mind, the “travelling salesman problem”, frequently denoted by the initials TSP, is a fundamental subject related to travelling and transportation, with several generalizations and with insertion in more complex situations, and also akin to others apparently unrelated, resoluble by the techniques used for the typical case. The TSP is known for the striking contrast between the simplicity of its formulation and the difficulty of its resolution, some even saying that it still does not have a solution. It is a so-called NP-hard problem (its difficulty increasing more than polynomially with its size). Anyway, something substantial can be presented about the problem. The problem arises from the typical situation of a salesman who wants to visit his clients in a given set of cities and return to his own city, thus performing a cycle. The problem can be envisaged in this large scale, but also exists in any other scales, such as within a factory or on a microchip. An asymmetrical TSP can also be the search for the optimum ordering of paint manufacturing or the preparation of fruit juices in a common plant, because, in these cases, setup costs (washing, etc.) depends significantly on the “vicinity” of the colours or of the flavours. The mathematical formulation of the problem can be as in Eq. {1}.