# A Sequence-Based Hyper-Heuristic for Traveling Thieves
## 2 Fundamentals
### Optimization Problem
#### 2.1.3 Traveling Thief Problem  
As in the TSP, the problem formulation considers a set of \(T\) cities where the information about the distance between each pair of cities (\(\forall\ d_{ij}\in\textbf{D}\)) is contained within a known matrix \(\textbf{D}\). Moreover, every city \(i\) contains a finite set of items \(\mathcal{M}_{i}=\{k_{1},k_{2},\ldots,k_{M_{i}}\}\), where \(M_{i}=\#\mathcal{M}_{i}\) can vary from one city to the next, and each item has a profit \(p_{ik}\in\mathbb{R}_{+}\) and a weight \(w_{ik}\in\mathbb{R}_{+}\), \(\forall k\in\mathcal{M}_{i}\). For the sake of simplicity, we define \(N\triangleq\max\{M_{1},M_{2},\ldots,M_{T}\}\) as the maximum number of items from at least one city; this quantity is obviously linked with the knapsack problem. Thus, it is straightforward to introduce the \(T\times N\) matrices \(\textbf{P}\) and \(\textbf{W}\) containing the profits and weights, respectively, for each item from any city; \((\textbf{P},\textbf{W})\in\mathbb{R}_{+}^{T\times N}\). Moreover, let us say that we currently have a tour of ordered cities \(\mathcal{C}=\{c_{1},c_{2},\ldots,c_{T}\}\) where each city in the tour represents one of the cities available in the TTP instance since \(T=\#\mathcal{C}\). In this way, \(c_{i}\in\mathcal{C}\) represents the starting city, and \(c_{j}\in\mathcal{C}\) is the next city that will be visited (\(j=i+1<T\)), even if it is not the closest one or does not represent the second city in the problem instance. Hence, \(d_{c_{i}c_{j}}\
eq d_{ij},\forall\ (c_{i},c_{j})\in\mathcal{C}\) and \(\forall\ d_{ij}\in\textbf{D}\). Now, we can lay out a profit function \(Z(\mathcal{C},\textbf{X})\) by incorporating a \(T\times N\) binary matrix \(\textbf{X}\in\mathbb{Z}_{2}^{T\times N}\) representing the packing plan for each city. Recall that each element from this matrix \(x_{ik}\in\textbf{X}\) becomes one if an object \(k\) is taken from city \(i\) and is zero otherwise. Additionally, the _thief_ rents a knapsack with a capacity \(K\) for a rate of \(R\) cost units per time unit. Lastly, the _thief_ moves with a velocity \(v\) that decreases linearly from \(v_{max}\) to \(v_{min}\) as the knapsack gains weight, such as  
\[v(c_{i})=v_{min}\bar{w}(c_{i})+v_{max}(1-\bar{w}(c_{i})), \tag{3}\]  
since \(\bar{w}(c_{i})\in[0,1]\) is the percentage of the total knapsack capacity after leaving the city \(c_{i}\). This factor corresponds to the rescaled version of the total weight of the items within the knapsack using \(K\), which is determined as follows:  
\[\bar{w}(c_{i})=\frac{1}{K}\left(\sum_{j=1}^{i}\hat{e}_{c_{j}}\right)^{\top}( \textbf{W}\odot\textbf{X})\overline{1}, \tag{4}\]  
where \(\hat{e}_{l}\) is the \(l\)th standard unit vector in the Euclidean space \(\mathbb{R}^{T}\), and \(\overline{1}\) is a vector with \(N\) elements equal one. Therefore, the objective function targets the tour \(\mathcal{C}\) and the packing plan \(\textbf{X}\), seeking to maximize the profit \(Z\) given by:  
\[Z(\mathcal{C},\textbf{X})=\text{tr}(\textbf{1}(\textbf{P}\odot\textbf{X}))-R \sum_{i=1}^{T}\frac{d_{c_{i}(i\mid\text{mod}\,T)+1}}{v(c_{i})} \tag{5}\]  
Note that the first right-hand side term sums the profit of all packed items, while the second term is the cost associated with renting the knapsack.