# Dye Schedule Optimization: A Case Study in a Textile Industry
## 2 Brazilian Textile Sector
### Operational Research
#### 2.3.2 Traveling Salesman Problem  
The travelling salesman problem (TSP) is one of the most widely studied problems in the combinatorial optimization area [19]. TSP is interesting not only from a theoretical point of view but because of the various practical applications that can be modelled by the  
Figure 2: Hierarchical level of activities.  
problem or its variations, with the need to find an efficient algorithm to solve it, among the most valuable applications known from the TSP, stand out the sequencing of the machine operations in manufacturing, optimization of hole drilling in printed circuit boards and most vehicle routing problems [20]. According to [13], it can be an essential source of ideas for developing more efficient models and scheduling problems. Similarities between TSP and the sequencing problem allow for direct manufacturing, where the city would be a job. The distance between one city and another would be the time (cost) of moving from one job to another [21].  
We can describe the problem as follows: a travelling salesman has the task of visiting a set of cities, with each pair of cities \(i\) and \(j\) having an associated cost, representing the distance to travel from city \(i\) to city \(j\). The salesman must depart from an initial town, visit all other cities once and return to the city of departure, completing a Hamiltonian Cycle at the lowest possible cost or the shortest trajectory.  
There are several formulations for the TSP, and these formulations can be considered canonical because it is a classic optimization problem widely spread in the specialized literature and because they develop peculiar ways of characterizing the problem. To simulate the dye sequencing to obtain the shortest setup time, the TSP model was used, with the approach proposed by Miller-Tucker-Zemlim (MTZ) formulation, with the contribution of [22; 23], for the elimination of sub-routes, because according to the latter, the MTZ formulation is vulnerable to the relaxation of constraints. This model was chosen because it works with a limited number of restrictions.  
\[\text{Min }\sum_{j=1}^{n}\sum_{i=1}^{n}c_{ij}x_{ij} \tag{1}\]  
subject to:  
\[\sum_{i=1}^{n}x_{ij}=1;\;j=2,\ldots,n \tag{2}\]  
\[\sum_{j=1}^{n}x_{ij}=1;\;i=2,\ldots,n \tag{3}\]  
The formulation of elimination of subtours proposed by MTZ, can be expressed by:  
\[u_{i}-u_{j}+(n-1)x_{ij}\leq n-2;\;2\leq i\
eq j\leq n \tag{4}\]  
\[1\leq u_{i}\leq n-1;\;i=2,\ldots,n \tag{5}\]  
The formulation of elimination of sub tours proposed by MTZ can be strengthened using the elevation technique [22].  
\[u_{i}-u_{j}+(n-1)x_{ij}+(n-3)x_{ji}\leq n-2;\;2\leq i\
eq j\leq n \tag{6}\]  
Equation (1) represents the objective function to minimize the total cost of the salesman route, where \(c_{ij}\) is the cost or distance of the arc \(i,j\) and \(x_{ij}\) is the binary variable (0 or 1) that decides whether route \(i,j\) will be included in the problem's solution or not. Equations (2) and (3) refers to constraints that ensure that each node or vertex has only one input and only one output to the optimized graph.  
Moreover, Equations (4) and (5) prevent the travelling salesman, saw more than \(n\) cities on a trip (a trip we understand, as visiting all the cities without passing through the city origin). In addition, \(u_{i}\) and, \(u_{j}\) are non-negative variable, which represents the number of cities visited before returning to the city of origin. However, it still does not guarantee the existence of sub tours, that is, two or more graphs disconnected from each other. Thus, adding a set of constraints like Equation (6) on the possible sub tours of the problem does not contain enough edges to make them closed loops.