## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
#### 5.3.6 Solution Quality with Pallet Replacement Time Bounds

To this point in the experimental results we have been primarily interested in solver runtimes; identifying the path-based encoding variant Path + LB + Corr(S) + TskA \begin{table}
\begin{tabular}{c c c c c} \hline \hline \multirow{2}{*}{**Map**} & \multirow{2}{*}{**Robot Diamater**} & **Time** & **Mem** & **Runtime** \\  & & **Out** & **Out** & **Mean/Geo.Mean** \\  & & & **(Excl. Mem Out)** & **(Excl. Mem Out)** \\ \hline \multirow{2}{*}{**map0** (15 instances)} & Point size & 0 & 0 & 4.89/7.89 \\  & One meter & 0 & 0 & 24.46/52.26 \\  & Two meter & 0 & 0 & 64.53/141.11 \\ \hline \multirow{2}{*}{**map1** (30 instances)} & Point size & 0 & 0 & 47.87/215.63 \\  & One meter & 0 & 5 & 117.45/333.81 \\  & Two meter & 0 & 10 & 166.70/289.34 \\ \hline \multirow{2}{*}{**map2** (30 instances)} & Point size & 6 & 0 & 133.88/536.63 \\  & One meter & 6 & 0 & 133.51/535.30 \\  & Two meter & 4 & 10 & 302.63/576.09 \\ \hline \multirow{2}{*}{**map3** (25 instances)} & Point size & 0 & 0 & 21.42/62.63 \\  & One meter & 2 & 0 & 101.35/405.24 \\  & Two meter & 4 & 5 & 264.22/591.31 \\ \hline \multirow{2}{*}{**map4** (20 instances)} & Point size & 0 & 0 & 7.72/15.61 \\  & One meter & 0 & 0 & 78.78/249.63 \\  & Two meter & 0 & 6 & 125.92/239.33 \\ \hline \multirow{2}{*}{**map5** (20 instances)} & Point size & 0 & 0 & 71.26/229.29 \\  & One meter & 0 & 0 & 65.40/180.52 \\ \cline{1-1}  & Two meter & 5 & 0 & 314.24/684.35 \\ \hline \hline \end{tabular}
\end{table} 
Table 8: Comparison of solving for a point-sized robot vs. a circular one and two meter diameter robot, for the high performance path encoding variant Path + LB + Corr(S) + TskAcyc(W) + MyA + MyR + MVH. \(\textsc{cyc}(W)\) + MVA + MVR + MVH that solves the greatest number of benchmark instances in the shortest amount of time. In this section, we use this encoding variant but turn to examining the question of solution quality. Table 9 compares the makespan produced for computing a single solution with, and without, a given pallet replacement time constraint, and compares this to searching for the minimal makespan. The pallet replacement time is an application domain criteria and is highly sensitive to the specific warehouse graph. Therefore it only makes sense to evaluate this criteria with respect to the industry benchmarks consisting of real-world warehouse graphs, rather than the crafted benchmarks consisting of synthesized graphs. Note also, from Table 4, we know that the industry benchmarks consist of only satisfiable problem instances, which of course is a necessity for measuring solution quality. There are a number of points to highlight here. Firstly, searching for a provably optimal solution is unrealistic in a practical setting. In our evaluation, searching for the optimal solution failed to prove optimality, within the 7200 s (2 h) timeout, for every problem instance. In contrast finding a single solution took between a few seconds and a few minutes. Note, for clarity it is worth pointing out that finding an optimal solution and proving that that solution is indeed optimal are separate things. Once a solution is found the solver still needs to ensure that there are no better solutions, so it is possible to find an optimal solution within the time limit but not prove its optimality. It should also be pointed out that when returning the first solution, the makespan was typically around twice that of the makespan found for the optimality search, which in itself could be considered a good enough solution under some application settings. A primary reason for this relatively good solution quality is to do with the move heuristic and the difference logic solver. The move heuristic ensures that the paths are close to the shortest possible, while the algorithm for the difference logic solver returns the lowest possible integer value for each variable, which effectively minimizes any time delays on a given path. This means that any robot's moves along a path will always be close to optimal.