## 3 The Picking Problem
### The Open Traveling Salesman Problem  
An Open Traveling Salesman Problem (TSP) is an NP-hard problem in the field of combinatorial optimization that asks the following question: 'Given a list of customers to whom some products have to be transported, what is the shortest route that connects a start depot (at which products are loaded) and an end depot (where the vehicle is parked after the tour) while visiting all customers?'  
The problem can therefore be represented by a weighted directed graph \(G=(V,E)\), where \(V\) is the set of customers/depots that needs to be visited, and \(E=\{(i,j)|i,j\in V\}\)  
\begin{table}
\begin{tabular}{c c c c c c c c c c c c c c c} \hline \hline \(t_{ij}\) & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline
1 & & 15.58 & 39.84 & 49.84 & 44.20 & 40.67 & 37.14 & 40.67 & 44.20 & 47.73 & 51.26 & 70.33 & 65.96 & 74.83 & 77.18 \\
2 & 15.58 & & 24.26 & 34.26 & 28.62 & 25.09 & 21.56 & 25.09 & 28.62 & 32.15 & 35.68 & 54.75 & 50.39 & 59.25 & 61.60 \\
3 & 39.84 & 24.26 & & 24.06 & 29.07 & 31.76 & 28.24 & 31.76 & 35.29 & 38.82 & 42.35 & 61.42 & 57.06 & 65.92 & 68.28 \\
4 & 49.84 & 34.26 & 24.06 & & 21.91 & 25.44 & 28.97 & 32.50 & 36.02 & 39.55 & 43.08 & 62.15 & 57.79 & 66.65 & 69.01 \\
5 & 44.20 & 28.62 & 29.07 & 21.91 & & 16.47 & 20.00 & 23.53 & 27.06 & 30.59 & 34.12 & 53.18 & 48.82 & 57.69 & 60.04 \\
6 & 40.67 & 25.09 & 31.76 & 25.44 & 16.47 & & 16.47 & 20.00 & 23.53 & 27.06 & 30.59 & 49.66 & 45.29 & 54.16 & 56.51 \\
7 & 37.14 & 21.56 & 28.24 & 28.97 & 20.00 & 16.47 & & 16.47 & 20.00 & 23.53 & 27.06 & 46.13 & 41.76 & 50.63 & 52.98 \\
8 & 40.67 & 25.09 & 31.76 & 32.50 & 23.53 & 20.00 & 16.47 & & 16.47 & 20.00 & 23.53 & 29.66 & 25.29 & 34.16 & 36.52 \\
9 & 44.20 & 28.62 & 35.29 & 36.02 & 27.06 & 23.53 & 20.00 & 16.47 & & 16.47 & 20.00 & 26.13 & 21.76 & 30.64 & 32.99 \\
10 & 47.73 & 32.15 & 38.82 & 39.55 & 30.59 & 27.06 & 23.53 & 20.00 & 16.47 & & 16.47 & 22.60 & 18.24 & 27.11 & 29.46 \\
11 & 51.26 & 35.68 & 42.35 & 43.08 & 34.12 & 30.59 & 27.06 & 23.53 & 20.00 & 16.47 & & 19.07 & 14.71 & 23.57 & 25.92 \\
12 & 70.33 & 54.75 & 61.42 & 62.15 & 53.18 & 49.66 & 46.13 & 29.66 & 26.13 & 22.60 & 19.07 & & 13.77 & 22.64 & 29.69 \\
13 & 65.96 & 50.39 & 57.06 & 57.79 & 48.82 & 45.29 & 41.76 & 25.29 & 21.76 & 18.24 & 14.71 & 13.77 & & 17.59 & 14.26 \\
14 & 74.83 & 59.25 & 65.92 & 66.65 & 57.69 & 54.16 & 50.63 & 34.16 & 30.64 & 27.11 & 23.57 & 22.64 & 17.59 & & 7.20 \\
15 & 77.18 & 61.60 & 68.28 & 69.01 & 60.04 & 56.51 & 52.98 & 36.52 & 32.99 & 29.46 & 25.92 & 29.69 & 14.26 & 7.20 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Approximate travel time (s) between different zones in the reference store.  
Figure 1: Layout of a real store with numbers corresponding to areas containing products of different categories.  
is the set of edges connecting all the vertices pairs. To each edge \(e\in E\) a cost \(c_{ij}\) is associated, which can be the distance or the time required to travel from customer/depot \(i\) to customer/depot \(j\). The objective is to find the set \(S\) of edges that connects the start and end points in such a way that each vertex in \(V\) is considered one and only one time, all the edges are adjacent, and the sum of the costs \(\sum_{(i,j)\in S}t_{ij}\) is minimized.  
The TSP can be formulated and solved easily since it has been well studied by many approaches [23; 24; 25].  
As in-store logistics is one of the main cost drivers, it has been proven that sequencing the orders by the TSP solution can effectively improve the picking time performance [18]. However, as mentioned earlier, the lack of consideration in item placement inside bags can lead to potential product damage, thus, an extra time cost is expected for rearrangements. Therefore, a constraints based on product attributes should be considered [19] with respect to the shortest route analysis. The problem is then solved as a Sequential Ordering Problem in the following section.