## 4 Hybrid Genetic Algorithm to Search for Effective Item Assignments
### Equivalence to the TSP Problem  
First, we show that a special case of the proposed item assignment problem is equivalent to a symmetric traveling salesman problem when the layout is circularly linked. We prove this by transforming the symmetric traveling salesman problem into an item \begin{table}
\begin{tabular}{c c c c} \hline \hline  & **BASE_ASSIGN** & **PROFIT_ASSIGN** & **PROF_FRE_ASSIGN** \\ \hline Objective value & \(1.6+2.6+1.1+3.9\) & \(2.6+4.8+3.9+2.6\) & \(2.6+4.8+5.6+3.9+4.5+13.3=15\) & \(+4.5=18.4\) & \(4.5=21.4\) \\ \hline \hline \end{tabular}
\end{table} 
Table 6: _Relative profit_ increased by cross-selling items. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**(a)** & **A** & **B** & **C** & **D** & **E** & **F** \\ \hline A & - & 1 & 1 & 1 & 1 & 4 \\ B & 1 & - & 1 & 4 & 1 & 1 \\ C & 1 & 1 & - & 1 & 3 & 1 \\ D & 1 & 4 & 1 & - & 1 & 1 \\ E & 1 & 1 & 3 & 1 & - & 1 \\ F & 4 & 1 & 1 & 1 & 1 & - \\ \hline
**(b)** & **A** & **B** & **C** & **D** & **E** & **F** \\ \hline A & - & 1.6 & 0 & 2.6 & 0 & 4.8 \\ B & 1.6 & - & 1.1 & 5.6 & 0 & 3.9 \\ C & 0 & 1.1 & - & 2.6 & 4.5 & 0 \\ D & 2.6 & 5.6 & 2.6 & - & 0 & 1.3 \\ E & 0 & 0 & 4.5 & 0 & - & 1.3 \\ F & 4.8 & 3.9 & 0 & 1.3 & 1.3 & -assignment problem. Let \(I=\{I_{1},\,I_{2},\,\ldots,\,I_{n}\}\) be the set of cities and \(S=\{S_{1},\,S_{2},\,\ldots,\,S_{n}\}\) be the set of sites structured in a circularly linked form. In other words, the following site configuration in Figure 4a is considered. Now, we allocate \(n\) cities to \(n\) sites, with one city at each site, which represents a traveling sequence of the \(n\) cities. For example, for \(n=4\), the allocation of \(I_{2}\) at \(S_{1}\), \(I_{3}\) at \(S_{2}\), \(I_{1}\) at \(S_{3}\), and \(I_{4}\) at \(S_{4}\) represents a traveling sequence, \(I_{2}\to I_{3}\to I_{1}\to I_{4}\to I_{2}\). It is straightforward that a traveling sequence of the \(n\) cities is mapped to an allocation of the \(n\) cities to form the circularly linked layout, and the mapping is one-to-one. Now, we formulate a symmetric traveling salesman problem given a circularly linked layout \(S\). Suppose that \(c_{ij}\) is the distance between city \(i\) and city \(j\); \(x_{i,j}\) is 1 if city \(I_{i}\) is located at site \(S_{j}\) and 0 otherwise, and \(y_{ij}\) is 1 if site \(S_{i}\) is adjacent to \(S_{j}\) and 0 otherwise. For a given layout \(S\), \(y_{ij}\) is given, and \(x_{ij}\) is a decision variable. Since \(c_{ij}\times x_{i,k}\times x_{j,k+1}\) is a traveling cost from the \(k\)-th visiting city \((i)\) to the \((k+1)\)-th visiting city \((j)\), the total cost to minimize is given by  
\[\sum_{i=1}\,\sum_{j\
eq i}c_{ij}\times x_{i,1}\times x_{j,2}\,+\,c_{ij}\times x _{i,2}\times x_{j,3}+\cdots+c_{ij}\times x_{i,n-1}\times x_{j,n}+c_{ji}\times x _{j,n}\times x_{i,1}=\sum_{i\
eq j,k\
eq l}\,c_{ij}\times x_{j,k}\times x_{j,l }\times y_{k,l} \tag{4}\]  
with the constraints that each city \(i\) should be visited once, \(\sum_{k=1}^{n}x_{i,k}=1\), and each site k should be taken once, \(\sum_{i=1}^{n}x_{i,k}=1\). For example, a traveling sequence, \(I_{2}\to I_{3}\to I_{1}\to I_{4}\to I_{2}\), will have its objective value calculated by \(c_{23}\times x_{2,1}\times x_{3,2}+\,c_{31}\times x_{3,2}\times x_{1,3}+c_{14 }\times x_{1,3}\times x_{4,4}+c_{42}\times x_{4,4}\times x_{2,1}=c_{23}+c_{31} +c_{14}+c_{41}\) with only \(x_{2,1}=\,x_{3,2}\)\(=\,x_{1,3}=x_{4,4}=1\) among the decision variables. Thus, we rewrite the symmetric TSP as the following minimization programming:  
\[ \begin{array}{ll}\text{Minimize}&\sum_{i\
eq j,k\
eq l}\,c_{ij}\times x_{ ik}\times x_{jl}\times y_{kl}\\ \text{Subject to}&\sum_{i=1}^{n}x_{ik}=1,\,k\,=\,1,\,\ldots,\,n,\\ &\sum_{k=1}^{n}x_{ik}=1,i\,=\,1,\,\ldots,\,n,\\ &x_{ik}=\left\{\begin{array}{cc}1,&if\,\,item\,\,I_{i}\,\,is\,\,located\,\,at\, site\,S_{k}\\ &0,\,\,otherwise.\end{array}\right.\end{array}  \tag{5}\]  
Equation (5) has the same structure as Equation (3) except that TSP is a minimization problem.