## 5 R-DPAP: Resource-Constrained Directed Path Allocation Problems
### Relationship between \(R\)-DPAP and V-DPAP  
An R-DPAP combines a path selection problem and a scheduling problem over the resources used by the selected items. In the following, we show that it is possible to transform an R-DPAP into an equivalent V-DPAP by generating a set of item selection conflicts that is equivalent to the set of selections forbidden by the scheduling problem. To illustrate this point, let us consider the example given in Figure 8, that involves four requests: \(a,b,c,d\). It is first possible to decompose the scheduling problem of the R-DPAP into a set of subproblems containing items that may be in competition for using a given resource (gray rectangles depicted in the figure). For example, items \(a_{4}\) and \(b_{5}\) belong to the same subproblem because their time windows overlap, and items \(b_{5}\) and \(c_{1}\), whose time windows do not overlap, also belong to the same subproblem because the presence of items \(a_{4}\) and \(d_{1}\) creates an indirect interaction between \(b_{5}\) and \(c_{1}\). More formally, to compute the content of these scheduling subproblems, we can build, for each resource \(r\), the graph \(G_{r}\) containing one node per item and one edge between item \(i\) and item \(j\) if and only if the time windows of \(i\) and \(j\) overlap. Then, the scheduling subproblems to consider correspond to the connected components of graph \(G_{r}\). In Figure 8, we obtain three connected components for resource \(sat_{1}\), namely, \(\{a_{1},b_{1}\}\), \(\{a_{2},b_{2}\}\), and \(\{a_{4},b_{5},c_{1},d_{1}\}\), and three connected components for resource \(sat_{2}\), namely, \(\{a_{3},b_{3}\}\), \(\{b_{4}\}\), and \(\{a_{5},b_{6},c_{2},d_{2}\}\). After these steps, for each component \(\Gamma\) obtained, we can compute the set of _minimal scheduling conflicts_ associated with \(\Gamma\). This set contains all the sets \(S\subseteq\Gamma\) such that, (1) there is no feasible schedule performing all the tasks in \(S\) while respecting their time window and duration constraints, and (2) set \(S\) is minimal for inclusion, that is, for every set \(S^{\prime}\subset S\), there exists a way to schedule all the tasks in \(S^{\prime}\). To compute these minimal conflicts, we proceed as follows. * We consider the non-empty subsets \(S\) of \(\Gamma\) one by one, following an increasing cardinality order. For a given set \(S\), if there exists a subset \(S^{\prime}\subset S\) of size \(|S|-1\) such that \(S^{\prime}\) is a conflict, \(S\) is marked as being a conflict but is not added to the set of minimal  
Figure 8: Orbit slot allocation problem involving two satellites \(sat_{1}\) and \(sat_{2}\) and four requests \(a\), \(b\), \(c\), \(d\) posted by four agents \(A\), \(B\), \(C\), \(D\); the duration associated with each item is also indicated (e.g., a duration of 2 time units for item \(a_{1}\) and a duration of 3 time units for item \(c_{1}\)). conflicts. Otherwise, we test whether there exists a schedule containing all the tasks in \(S\). If not, \(S\) is marked as a conflict and added to the set of minimal conflicts. * To determine whether there exists a schedule containing all the items in a set \(S\), we use a dynamic programming algorithm. More precisely, we consider the subsets \(S^{\prime}\) of \(S\) following an increasing cardinality order and we determine, for each subset \(S^{\prime}\subseteq S\), the minimum time \(mt(S^{\prime})\) at which all items in \(S^{\prime}\) can be served in a feasible schedule. To do this, we start from \(mt(\emptyset)=-\infty\) and apply recursive formulas. If item \(i\in S^{\prime}\) belongs to graph \(g\) and is the last item visited, the minimum time at which the visit of \(i\) can end is given by \(mt(S^{\prime},i)=\max(mt(S^{\prime}\setminus\{i\}),ws_{g}(i))+d_{g}(i)\), and visiting \(i\) at the latest position among the items in \(S^{\prime}\) is feasible if and only if \(mt(S^{\prime},i)\leq w_{g}(i)\).