# A Learnheuristic Algorithm for the Capacitated Dispersion Problem under Dynamic Conditions
## 4 Solution Approaches for the Dynamic Capacitated Dispersion Problem
### A Constructive Heuristic  
Algorithm 1 shows the main procedure of the constructive heuristic, which extends the algorithm proposed by [PERSON] et al. [19], thus considering the predictions provided by the white box to deal with the uncertainty of the problem. It starts from a hypothetical scenario where all facilities are initially closed, i.e., the algorithm starts with an empty initial solution (line 1). Next, a list of potential candidates for the first two nodes is generated. This list includes the edges that connect each pair of facilities and is sorted in descending order based on a combination of the distances between them and their respective capacities. This combination is weighted by the likelihood of successfully covering the capacity of a node (line 2). Equation (8) shows the edge value, where \(\pi(n_{i})\) is the probability of \(n_{i}\) covering the capacity. \[edge(n_{i},n_{j})=\delta\cdot d_{i,j}+\frac{(1-\delta)}{2}\cdot\left(\pi(n_{i })\cdot c_{i}+\pi(n_{j})\cdot c_{j}\right) \tag{8}\]  
Next, the algorithm selects the element at the top position of the described _edge_list_ (line 3). Subsequently, the pair of facilities that compose the selected edge are included in the solution (line 4). Then, the simulation of the black box with the environment condition is performed, and the capacity of the solution is updated (line 5). Later, the objective function (_of_) is computed for the first time, thus considering the distance between these two facilities (line 6). To construct a feasible solution, the heuristic generates a preference list of candidate facilities (_node_list_) to be included in the solution in order to decide the most suitable ones to add in each iteration (line 8). To select the best nodes, a candidate list to evaluate them is implemented, with an evaluation function employed to sort the preference. The evaluation value associated with each element of the list is defined in Equation (9). It considers both the calculated distance from the new facility (_distance_to_solution_), i.e., the minimum distance between the node and each of the facilities currently selected, and the capacity of the candidate facility (\(c_{i}\)), which is weighted by the predicted probability of successfully covering the node capacity, \(\pi(n_{i})\). Both of these factors are adjusted to fit within a common scale by dividing them by the maximum distance between nodes and the maximum capacity in the set of candidates \(V\backslash S\), where \(S\) represents the current solution. To properly adjust the importance of each of the terms, a \(\delta\in(0,1)\) is added. Later on, the meaning of this parameter will be explained in more depth. \[eval(n_{i})=\delta\cdot\frac{distance\_to\_solution(n_{i})}{max\_distance(V \backslash S)}+(1-\delta)\cdot\frac{\pi(n_{i})\cdot c_{i}}{max\_capacity(V \backslash S)} \tag{9}\]The list of facilities is sorted in descending order, and then a modified version of the semigreedy algorithm introduced by [PERSON] et al. (2019) is performed. This variation involves selecting a subset of the candidate list based on the parameter \(0\leq\alpha\leq 1\). The subset is described in (10):  
\[CL:=\{i\in V\backslash M:eval(n_{i})\geq\alpha\cdot(eval(n_{0})-eval(n_{m}))\}, \tag{10}\]  
where \(n_{0}\) and \(n_{m}\) are the nodes with best evaluation value and the worst in the list, respectively. Finally, unlike the deterministic algorithm, the node \(n_{i}\) with the highest \(\pi(n_{i})\cdot c_{i}\) in the subset is chosen. The parameter \(\alpha\) enables the algorithm to make choices among various candidates and avoid those facilities with a low probability of successfully providing the required capacity. Once the facility has been selected, the simulation under the environment condition is performed to determinate the success of the node (line 9). Finally, the _of_ and the \(node\_list\) are updated to consider the new facility in the solution. This procedure is repeated until the capacity constraint is met (line 7).