## 4 Solving the Warehouse Delivery Problem
### Task Assignment and Sequencing
#### 4.3.2 Conflict Detection and Resolution
So it is only within the allocation and ordering of tasks, and not the moves themselves, that the main improvements in makespan can be made. \begin{table}
\begin{tabular}{c l c c c} \hline \hline \multirow{2}{*}{**Map**} & **Decision** & **Time** & **Makespan** & **Runtime** \\  & **Problem** & **Out** & **Mean/Geo.Mean** & **Mean/Geo.Mean** \\ \hline \multirow{2}{*}{**map0** (30 instances)} & Minimal & 30 & 345/422 & 7200.00/7200.00 \\  & Pallet Rpl. 200 s & 0 & 653/734 & 5.60/10.15 \\  & First Soln & 0 & 771/896 & 4.82/7.88 \\ \hline \multirow{2}{*}{**map1** (50 instances)} & Minimal & 50 & 1891/2734 & 7200.00/7200.00 \\  & Pallet Rpl. 400 s & 5 & 2443/2884 & 49.60/325.60 \\  & First Soln & 0 & 3241/3919 & 28.84/136.39 \\ \hline \multirow{2}{*}{**map2** (50 instances)} & Minimal & 50 & 1660/2627 & 7200.00/7200.00 \\  & Pallet Rpl. 200 s & 6 & 2060/2333 & 87.70/354.24 \\  & First Soln & 6 & 3007/3545 & 60.85/278.82 \\ \hline \multirow{2}{*}{**map3** (45 instances)} & Minimal & 45 & 413/575 & 7200.00/7200.00 \\  & Pallet Rpl. 200 s & 0 & 665/789 & 20.38/106.45 \\  & First Soln & 0 & 810/1009 & 15.51/40.97 \\ \hline \multirow{2}{*}{**map4** (20 instances)} & Minimal & 20 & 412/481 & 7200.00/7200.00 \\  & Pallet Rpl. 200 s & 0 & 611/695 & 12.69/40.73 \\  & First Soln & 0 & 716/804 & 7.83/15.73 \\ \hline \multirow{2}{*}{**map5** (20 instances)} & Minimal & 20 & 4916/6876 & 7200.00/7200.00 \\  & Pallet Rpl. 800 s & 8 & 6206/6958 & 446.19/1078.63 \\ \cline{1-1}  & First Soln & 0 & 9064/10,747 & 64.60/180.25 \\ \hline \hline \end{tabular}
\end{table} 
Table 9: Comparison of makespan by map and decision problem for the high performance path encoding variant Path + LB + Corr(S) + TsKacyc(W) + MVA + MvR + MVH. When the pallet replacement time constraints were added, the solving time for finding the first solution increased by up to a factor of 3. So for example, with map0  the geometric mean of the runtimes increased from 7.88 to 10.15 s, while for map4  it increased from 15.73 to 40.73 s. It should also be observed that enforcing the pallet replacement time bound also improved the makespan. The makespan often improved significantly, roughly halving the difference between the first and best solutions. Finally, whether or not the pallet replacement time metric provides good-enough solutions will depend on the requirements of the given warehouse application. There are also further possibilities that could be explored in the future to determine a good-enough criteria for a given application. For example, when optimization is enabled, the solver returns the solutions as they are found. This allows the solver to be used in an anytime setting, returning the best solution up to some fixed timeout. So it could be interesting to compare the quality of the solutions for makespan minimimization as they are produced over time. It could be the case that the search gets close to an optimal solution quite quickly, even if it is ultimately not practical to wait for the provably optimal solution to be found. ## 6 Related Work

The warehouse delivery problem considered in this paper can be viewed as a specialized instance of the multi-agent path finding (MAPF) problem that has attracted a lot of attention in recent years due to its widespread applicability. Introductory materials on MAPF can be found in the papers [12; 16] and several tutorials at AAAI, IJCAI, or ICAPS. Challenges and opportunities in MAPF and its extensions have been described by [17]. The present paper considers weighted graphs and robots that have a size that can place complex constraints on possible movements, e.g., a robot can block more than one vertex at a time and travel time between vertices is different. As MAPF is essentially a planning problem, search-based approaches to solving MAPF are frequently used. Indeed, a plethora of MAPF solvers have been proposed [18; 19; 20; 21; 22; 23; 24; 25; 26; 27].