# A Learnheuristic Algorithm for the Capacitated Dispersion Problem under Dynamic Conditions
## 2 Related Work on Diversity Problems  
The diversity problem arose with the idea of maximizing the distance between individuals, where the definition of the distance between elements is customized to specific applications. Once the combinatorial optimization problem was defined by [PERSON] et al. [13], multiple objective functions with different approaches to the concept of diversity were explored by [PERSON] et al. [14]. Additionally, the latter work demonstrates that the diversity problem is NP-hard. Therefore, for larger instances, it is advisable to consider heuristic algorithms.  
In the beginning of this century, [PERSON] et al. [10] introduced the capacitated diversity problem, thus adding capacity to each node and constraints of minimal capacity. In their work, these authors also proposed the first heuristic approach to the problem with a heuristic algorithm called T1. [PERSON] et al. [15] proposed a new heuristic for the CDP. In their work, these authors proposed a GRASP algorithm [16], thus taking into account the distance between the solution and the capacity of the node to be selected. The algorithm is completed by combining GRASP with a variable neighborhood descent (VND) framework [17] and a strategic oscillation (SO) [18], which involves removing and adding nodes in solutions with capacities that are very close to the limit. The work of [PERSON] et al. [19] outperformed the aforementioned SO algorithm. This work proposes three phases to achieve a solution. First, the diversification generation method (DGM) aims to initialize a solution by picking nodes one by one until the capacity restriction is satisfied. The difference from the GRASP phase of the SO algorithm is that the node chosen depends on the distance and an \(\alpha\) parameter, which shortens the candidate list to pick the node with the largest capacity. Then, the solution is improved using a method that differs from VND in the SO algorithm by taking into account more than one node to replace others. Finally, it employs a multiple path relinking approach [20]. More recently, [PERSON] et al. [21] employed a solution based on a tabu search algorithm [22] using hash functions to identify the tabu status of the candidate solutions created by a greedy algorithm.  
On the other part, reinforcement learning [23] is a machine learning paradigm that focuses on training agents (entities that interact with the environment) to make sequential decisions in an environment to maximize a cumulative reward. It is inspired by behavioral psychology and is commonly used in fields such as artificial intelligence, robotics, game playing, and autonomous systems. This technique plays a relevant role in the current paradigm of optimization problems as described in [PERSON] et al. [24]. During the last years, some studies have successfully forged a synergy between reinforcement learning and heuristic algorithms to construct solutions for dynamic problems [25]. This symbiotic relationship not only enhances the robustness of heuristic algorithms when confronted with dynamic scenarios, but also allows them to continually improve over time and adapt to changes in the environment. An instance of this is detailed in reference [9]. To the best of our knowledge, our work is the first study to incorporate dynamic conditions into the CDP, which requires the combination of a heuristic algorithm with reinforcement learning.