## 5 R-DPAP: Resource-Constrained Directed Path Allocation Problems
### Framework Definition  
**Definition 7**. : _A Resource-Constrained Directed Path Allocation Problem (R-DPAP) is a DPAP \(\langle\mathcal{A},\mathcal{G},\mu,\phi\rangle\) where function \(\phi\) is defined by:_  
* _a set of disjunctive resources_ \(\mathcal{R}=\{r_{1},\ldots,r_{p}\}\)_;_
* _for each graph_ \(g\in\mathcal{G}\)_, a triple_ \((\mathit{ws}_{g},\mathit{ws}_{g},c_{g})\) _such that:_
* \(\mathit{ws}_{g}:V_{g}\to\mathbb{N}\) _and_ \(\mathit{ws}_{g}:V_{g}\to\mathbb{N}\) _associate a start date and an end date, respectively, that together define a time window for each item;_
* \(c_{g}:V_{g}\to\mathcal{R}\cup\{r_{\mathcal{O}}\}\) _returns the resource required for each item. For any vertex_ \(v\in V_{g}\)_,_ \(c_{g}(v)=r_{\mathcal{O}}\) _indicates that_ \(v\) _does not require any resource in_ \(\mathcal{R}\)_. In particular, the source and sink nodes do not consume any resource. Moreover, we assume that for two items_ \(v\) _and_ \(v^{\prime}\) _belonging to the same graph and requiring the same resource in_ \(\mathcal{R}\)_, the time windows of_ \(v\) _and_ \(v^{\prime}\) _do not overlap;_
* \(d_{g}:V_{g}\to\mathbb{N}\) _associates a duration with each item; resource_ \(c_{g}(v)\) _must be used during_ \(d_{g}(v)\) _time units within time window_ \([\mathit{ws}_{g}(v),\mathit{ws}_{g}(v)]\) _without any interruption (non-preemptive consumption)._  
_From this, function \(\phi\) returns a value of \(1\) for a path allocation if and only if, given the items selected by the paths, there exists a way to schedule the consumptions over the disjunctive resources in \(\mathcal{R}\) (see Definition 8)._  
**Definition 8**. : _In an R-DPAP \(\langle\mathcal{A},\mathcal{G},\mu,\phi\rangle\), an allocation \(\pi\) is valid if and only if for each graph \(g\in\mathcal{G}\), there exists a function \(\tau_{\pi,g}:\ \pi(g)\ \to\ \mathbb{N}\) that assigns a start date to each node \(v\) in \(\pi(g)\) such that:_  
* _for all graphs_ \(g\in\mathcal{G}\)_, for all nodes_ \(v\in\pi(g)\)_,_ \(\tau_{\pi,g}(v)\geq\mathit{ws}_{g}(v)\) _and_ \(\tau_{\pi,g}(v)+d_{g}(v)\leq\mathit{w}_{g}(v)\)_;_
* _there is no conflict for nodes in_ \(\pi(g)\) _with respect to resource consumption. Formally, for each pair of distinct graphs_ \(g\) _and_ \(g^{\prime}\)_, for each node_ \(v\in\pi(g)\) _and each node_ \(v^{\prime}\in\pi(g^{\prime})\) _such that_ \(c_{g}(v)=c_{g^{\prime}}(v^{\prime})\) _and_ \(c_{g}(v)\
eq\tau_{\mathcal{O}}\) _(i.e.,_ \(v\) _and_ \(v^{\prime}\) _consume the same resource in_ \(\mathcal{R}\)_), either_ \(\tau_{\pi,g}(v)+d_{g}(v)\leq\tau_{\pi,g^{\prime}}(v^{\prime})\) _or_ \(\tau_{\pi,g^{\prime}}(v^{\prime})+d_{g^{\prime}}(v^{\prime})\leq\tau_{\pi,g}(v)\) _holds._  
**Example 4**. : _We reuse the orbit slot allocation problem whose graph is given in Figure 1, and where two requests a and b are involved. We assume here that each request requires two observation slots of duration 2. For both requests, the first slot must occur around time 3 and the second slot around time 9. We consider two satellites \(\mathit{sat}_{1}\) and \(\mathit{sat}_{2}\). For request a, there are two time windows around time 3 during which satellites pass over the target area of a: time window \(\mathtt{a}_{1}=[1,4]\) for satellite \(\mathit{sat}_{1}\) and time window \(\mathtt{a}_{3}=[2,4]\) for satellite \(\mathit{sat}_{2}\). Around time 9, only satellite \(\mathit{sat}_{1}\) passes over the target area, which results in time window \(\mathtt{a}_{2}=[7,10]\). Similarly, for request b, time windows \(\mathtt{b}_{1}=[2,5]\) and \(\mathtt{b}_{3}=[1,4]\) allow the target area to be observed around time 3 with satellites \(\mathit{sat}_{1}\) and \(\mathit{sat}_{2}\), respectively. Time windows \(\mathtt{b}_{2}=[8,10]\) and \(\mathtt{b}_{4}=[9,12]\) are available for observing around time 9. Such a problem can be represented through the R-DPAP illustrated in Figure 5. Each satellite can be seen as a resource. Each request is represented through a graph: graph \(g_{\mathtt{a}}\) for request a and graph \(g_{\mathtt{b}}\) for request b.