# A Learnheuristic Algorithm for the Capacitated Dispersion Problem under Dynamic Conditions
## 4 Solution Approaches for the Dynamic Capacitated Dispersion Problem
### A Constructive Heuristic
Our evaluations took into account three sets of instances as proposed by [PERSON] et al. (2019), i.e. :

* GKD instances: This is a dataset formed using Euclidean distances with node coordinates generated within a uniform distribution ranging from 0 to 10. Initially proposed in [PERSON] et al. (2019), it is divided into two subsets: the GKD-b, which includes instances with 50 and 150 nodes, and the GKD-c subset, which includes instances harboring 500 nodes. * MDG instances: This dataset encompasses real numbers arbitrarily chosen between 0 and 1000 that originate from a uniform distribution. It was introduced by [PERSON] and [PERSON] (2017) and comprises instances with a sizable 500 nodes. For each instance, it is important to include all the required data to conduct the experiments, as was done by [PERSON] et al. (2019) and [PERSON] et al. (2018) using the parameter \(b\) to determine the percentage of the total capacity obtained by summing the capacities of all facilities. In this case, the parameter was set at either 0.2 or 0.3, which represents 20% or 30% of the total capacity, respectively. One of the main goals of this section is to conduct a comparison between the learnheuristic algorithm introduced in this study and its static counterpart. To achieve this, we compared the results of 1000 iterations of the algorithm using identical scenarios in each algorithm. In our experiments, we utilized three distinct seeds to create the environment of the instances. ### Black Box Parameters

In the context of this study, the black box works as a mechanism that predicts whether a particular node will be operational or not. It is essential to include the black box in our solution in order to obtain these predictions. Utilizing specific beta coefficients, this function provides a probability of a node having capacity. Subsequently, we generate a random number from a uniform distribution to determine whether the node indeed possesses the predicted capacity. The black box is only utilized to predict a node's operational status once that node has been specifically incorporated into our solution. We have assumed that the black box follows a logistic regression for its predictions. We have defined three types of dynamism, i.e., we have built three sets of parameters, with one for each type of dynamism. The parameters used for the black box in the Formula (6) for each type of dynamism are the following:

Table 1 details the probability of a node being operational and offering capacity when it is opened, which is based on different scenarios combining weather, congestion, and the configuration of nodes already included in the solution. Notice that congestion has a great influence on this probability for all nodes. ### Analysis of Results

Table 2 shows the results obtained with the static and learnheuristic approaches for all benchmark instances. Moreover, with the objective of comparing the quality of our methods, we also report three different types of dynamism. Since we used three different seeds, Table 2 shows two columns of results for each heuristic strategy: a column with the average result of the objective function and a column with the average nodes included in the solution (Nodes). The last four columns in Table 2 show the percentage gaps between some of the tested solution approaches. Hence, if we denote as a learnheuristic the average objective function obtained with our learnheuristic approach, then the percentage gap between the learnheuristic and static solutions is computed using the formula \(\text{Gap}=\frac{learnheuristic-static}{Static}\). In this context, a negative performance gap implies that the static algorithm yields a better solution, while a positive performance gap suggests that the learnheuristic algorithm outperforms its static counterpart. As can be seen in Table 2, the average of our objective function obtained by our learnheuristic algorithm usually outperformed the static algorithm, sometimes by a noticeable percentage gap.