## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
However, this heuristic does not specify any additional heuristic behavior for moves that are on the shortest path. The second heuristic extends the first heuristic by enforcing a weak preference for setting moves on the shortest-path to true. Results of these two variants for a number of configurations are shown in Table 6.

For each configuration there was only margin differences in performance between the MVH and MVH(P) variants. However, in all cases the simpler MVH variant performed slightly better. Consequently, for all remaining experiments we only report on the MVH results. \begin{table}
\begin{tabular}{l l c c c} \hline \hline \multirow{2}{*}{**Configuration**} & \multirow{2}{*}{**Benchmark**} & \multirow{2}{*}{**Solved**} & **Time** & **Runtime** \\  & & & **Out** & **Mean/Geo.Mean** \\ \hline Path + LB + Corr(S) & Crafted & 49 & 1 & 1.21/39.59 \\ + MVH & Industry & 207 & 8 & 24.79/148.78 \\  & Total & 256 & 9 & 14.03/128.18 \\ \hline Path + LB + Corr(S) & Crafted & 49 & 1 & 1.19/39.45 \\ + MVH(P) & Industry & 208 & 7 & 24.40/154.62 \\  & Total & 257 & 8 & 13.81/132.89 \\ \hline Path + LB + Corr(S) & Crafted & 49 & 1 & 1.16/38.85 \\ + MVH + TSkAcyc(W) & Industry & 210 & 5 & 22.05/116.99 \\  & Total & 259 & 6 & 12.65/102.25 \\ \hline Path + LB + Corr(S) & Crafted & 49 & 1 & 1.13/38.62 \\ + MVH(P) + TSkAcyc(W) & Industry & 210 & 5 & 22.62/128.49 \\  & Total & 259 & 6 & 12.86/111.54 \\ \hline Path + LB + Corr(S) & Crafted & 49 & 1 & 1.17/38.75 \\ + MVH + TSkAcyc(W) & Industry & 210 & 5 & 21.58/114.00 \\ + MVA & Total & 259 & 6 & 12.44/99.80 \\ \hline Path + LB + Corr(S) & Crafted & 49 & 1 & 1.13/38.23 \\ + MVH(P) + TSkAcyc(W) & Industry & 210 & 5 & 21.97/122.41 \\ + MVA & Total & 259 & 6 & 12.56/106.52 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Comparison of path encoding configurations for two variants of the move heuristics. #### 5.3.4 Runtime with Increasing Number of Tasks

Table 7 highlights the scalability of the encoding as the number of tasks increases for each graph. As expected the runtime increases as the number of tasks increase. For each of the six graphs, solving for 10 jobs (i.e., 40 tasks) was relatively easy, with a maximum geometric mean of 32.35 s for the largest map (map5). For context the geometric mean of the makespans in this case was 8079 s; so it took approximately 30 s to generate a plan for more than 2 h of robot operations. In this case the warehouse is very large (480 m \(\times\) 85 m) so the plans typically span relatively long distances for the robots to complete their tasks. If we hypothetically consider a maximum runtime of 60-90 s as an expectation for operating in a semi-realtime environment, then for most of the graphs the solver could comfortably plan for up for 20 jobs. The two exceptions to this being the two biggest graphs, map2 and map5. map5 could only solve for 10 jobs before breaching this limit, while map2 could solve for 15 jobs, the latter generating solutions with a 3873 s makespan (approx. 1 h). Unfortunately, for map2 the solver could not solve any instances containing 40 jobs within the 30 minute time limit. #### 5.3.5 Runtime with Differing Robot Diameters

Table 8 shows the effect of the diameter of the robot on solver performance. In Listing 14, Lines 5 to 13, the encoding generates conflict constraints for pairs of paths and vertices that can potentially interfere with each other. This is one of the main sources