# A Learnheuristic Algorithm for the Capacitated Dispersion Problem under Dynamic Conditions
###### Abstract  
The capacitated dispersion problem, which is a variant of the maximum diversity problem, aims to determine a set of elements within a network. These elements could symbolize, for instance, facilities in a supply chain or transmission nodes in a telecommunication network. While each element typically has a bounded service capacity, in this research, we introduce a twist. The capacity of each node might be influenced by a random Bernoulli component, thereby rendering the possibility of a node having zero capacity, which is contingent upon a black box mechanism that accounts for environmental variables. Recognizing the inherent complexity and the NP-hard nature of the capacitated dispersion problem, heuristic algorithms have become indispensable for handling larger instances. In this paper, we introduce a novel approach by hybridizing a heuristic algorithm with reinforcement learning to address this intricate problem variant. capacitated dispersion problem; metaheuristics; reinforcement learning; supply chains; telecommunication networks +
Footnote †: journal: _Algorithms_  
0000-0001-9999-4000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-00000-0000-0000-00000-00000-00000-0000-00000-00000  
of options, thereby ensuring that a function reaches either a maximal or minimal value in the context of combinatorial optimization. Model (1) serves as a representation of such diversity problems. It aims to maximize the smallest distance between any two selected elements, which are otherwise termed as active facilities. In this model, we have the following definitions:  
* \(V\) represents the element set. * \(d_{ij}\) defines the distance between elements \(i\) and \(j\) within \(V\). * \(E\) signifies the number of elements chosen. * \(x_{i}\) is a binary variable that assumes a value of one when element \(i\) in \(V\) is selected, and it selects zero otherwise. \[ \begin{split}\text{max}&\min_{i,j\in V,i<j}\quad \{d_{ij}:x_{i}\cdot x_{j}=1\}\\ \text{s.t.}&\sum_{i\in V}x_{i}=E\\ & x_{i}\in\{0,1\}\quad\forall i\in V\end{split} \] (1)  
While the ubiquity of models like Model (1) is recognized in characterizing diversity problems, their applicability falters in specific strategic logistics scenarios. In particular, situations where a baseline servicing capacity is mandatory present challenges that are not addressed by such models. To solve this, the unique restriction of the model must be modified to include the capacity of each node \(c_{i}\geq 0\) and the minimum required capacity \(B\), as depicted in Model (2):  
\[ \begin{split}\text{max}&\min_{i,j\in V,i<j}\quad \{d_{ij}:x_{i}\cdot x_{j}=1\}\\ \text{s.t.}&\sum_{i\in V}c_{i}\cdot x_{i}\geq B\\ & x_{i}\in\{0,1\}\quad\forall i\in V\end{split}  \tag{2}\]  
Accordingly, this paper addresses a dynamic version of the CDP. In this version, the objective is to select a set of elements within a network. What sets this variant apart is the introduction of a dynamic element, since the service capacity of each node is subject to influence by a random Bernoulli component. This means that some elements may unexpectedly have zero capacity, which depends on an underlying black box mechanism that takes into account the environmental variables. To solve this dynamic version, a learnheuristic algorithm [11] is proposed. The novelty of the approach presented in this paper lies in the fusion of a heuristic algorithm with reinforcement learning. This hybrid methodology offers a promising solution to address the complexities introduced by the dynamic CDP. As discussed in [PERSON] et al. [12], combining heuristics with machine learning is an emerging research line with a vast potential with regard to optimization. The rest of this paper is structured as follows. Section 2 provides a review of related work on diversity problems. Section 3 offers a formal description of the problem being discussed. Section 4 introduces the novel learnheuristic approach that will be used to solve the aforementioned problem.