## 3 Warehouse Delivery Problem
### Solution Quality  
In this section, we present two measures for the quality of a solution to the warehouse delivery problem. The first one is the makespan, where the quality of the solution is the duration of executing the solution, i.e., the maximum among all arrival time points at the last vertex in the timed walks. While makespan is an important quality measure, using makespan minimization as an optimization criteria is computationally expensive and can be impractical in a real-world setting that requires online planning over large warehouses. Instead we need to consider alternative, potentially cheaper, metrics. Here we provide a second quality measure that is an application driven metric that measures the maximum duration between the execution of task pairs that are given. **Makespan**. Given a solution \(((f_{T},f_{W}),P)\) to a warehouse delivery problem with warehouse \(W\) and a task execution graph \((T,D,f_{D},f_{V})\), we define the _makespan_\(q_{M}(f_{W}):\mathcal{W}_{W}\rightarrow\mathbb{N}\) as:  
\[q_{M}(f_{W})=\max\{a\ |\ \langle\ldots,(v,a,e)\rangle\in f_{W}\}\]  
Note that neither task assignment nor projections influence the makespan, therefore only the timed walks need to be an argument. For instance, the solution to our running example in Table 2 has the makespan \(q_{M}(f_{W})=405\) as this is the arrival at the final vertex of robot \(r_{1}\)'s walk, and is also the last arrival for all the robots. **Task-pair Distance**. Given a solution \(((f_{T},f_{W}),P)\) to a warehouse delivery problem with warehouse \(W\) and a task execution graph \((T,D,f_{D},f_{V})\), and a set of task pairs \(TP\subseteq 2^{T\times T}\), we define the _task-pair distance_\(q_{TP}(f_{W},P,TP):\mathcal{W}_{W}\times 2^{\mathcal{P}_{W}}\times 2^{T\times T }\rightarrow\mathbb{N}\) as:  
\[q_{TP}(f_{W},P,TP)=\max\{|a_{1}-a_{2}|\mid(v_{1},a_{1},e_{1})\in\vec{p}_{1},(v _{2},a_{2},e_{2})\in\vec{p}_{2},\{\vec{p}_{1},\vec{p}_{2}\}\in P,(t_{1},t_{2}) \in TP\}\]  
where \((v_{1},a_{1},e_{1})\) and \((v_{2},a_{2},e_{2})\) are the projection points of \(t_{1}\) and \(t_{2}\), respectively. For this quality measure, we need to determine the precise projection points for the task pairs, therefore both timed walks and projections are required. Note that we do not need to take task execution time into consideration, as the same time would be added to \(a_{1}\) and \(a_{2}\). We can now use the task-pair distance to evaluate solutions for the scenario in which pallets have to be replaced after a loading bay was emptied. In our example, we chose task-pairs \(TP=\{(t_{1},t_{4}),(t_{5},t_{8})\}\), which signify that we want to measure the time it takes from the pickup action at the loading bay and the putdown action of the new pallet on the same loading bay. Note that we can find such a task-pair set for arbitrary instance size with the same replacement pattern by merely having a task-pair for each loading bay and replacement event. The projections \(P\) are given by the triples that are marked with a task name in Table 2. Then, the task-pair distance \(q_{TP}(f_{W},P,TP)\) for our example is 283, which is the time it takes robot \(r_{2}\) to replenish the pallet at loading bay \(l_{2}\). In industry, there are often online settings in which new tasks arrive and plans have to be redone. Therefore, a makespan optimization cannot be exact and might be too costly from a performance point of view. The task-pair distance provides a more local means of evaluation that expresses in our example that a certain idle time has to be avoided. Using this measure, we can for instance express that a loading bay should not be idle for more than 5 min if we assume seconds as the time metric and only accept solutions with \(q_{TP}(f_{W},P,TP)\) smaller than 300. This establishes a fairness criteria by ensuring that there are no tasks that are ignored indefinitely. In Section 5, we evaluate these metrics and argue that the task-pair distance allows us to quickly find \"good-enough\" solutions in a setting where makespan minimization is impractical.