# Open Competency Optimization: A Human-Inspired Optimizer for the Dynamic Vehicle-Routing Problem
## 2 Dynamic VRP  
In this section, we will discuss the second test chosen in this study (dynamic VRP) to demonstrate the effectiveness of the OCO algorithm. The vehicle-routing problem can be described as a process of distributing a quantity of a product or a service in good condition and in a suitable amount of time. The vehicle-routing problem (VRP) is a generalization of the traveling salesman problem with several travelers, who will be called vehicles. The goal is to visit all customers using a fleet of vehicles that leave and all arrive at the depot (Figure 1). Let \(V=\{v_{0},v_{1},\ldots,v_{n}\}\) correspond to \(n\) customers, where \(v_{0}\) represents the depot. Each customer \(i\) in \(V-\{0\}\) presents an order for a product. \(d_{i}\) corresponds to the quantity of delivered products. A fleet of \(M\) vehicles \((1,2,\ldots,M)\) is available in identical capacity \(Q\). Similarly, for all customers, \(c_{ij}\) is the direct transport cost between customer \(i\) and \(j\). \(c_{ij}\) is proportional to the travel distance. The objective of the VRP is to find \(M\) tours (departing and returning to the depot) so that all customers are visited once while minimizing the total cost of transport and respecting the storage capacity of vehicles. As the VRP generalizes the famous traveling salesman problem, it is an NP-Hard problem. [PERSON] and [PERSON] [10] gave the following formulation of this problem: there is a binary variable \(x_{kij}\) where \(i\) denotes the customer \(i\), \(j\) designates the customer \(j\), and  
\[X_{ji}^{k}= \begin{cases}1,&\text{if $j$ is visited after $i$ with vehicle $k$}\\ 0,&\text{else}\end{cases}  \tag{1}\]  
There is another binary variable \(\gamma_{i}^{k}\) where \(i\) designates the customer \(i\) and \(k\) designates the vehicle  
\[\gamma_{i}^{k}= \begin{cases}1,&\text{if $k$ vehicle visits customer $k$}\\ 0,&\text{else}\end{cases}  \tag{2}\]  
The goal is to minimize the following function:  
\[z=\sum_{k=1}^{M}\sum_{i=0}^{n}\sum_{j=0}^{n}d_{ij}X_{ji}^{k} \tag{3}\]  
Figure 1: The VRP for serving 9 customers on 3 tours. with the following constraints:  
\[\forall k\in\{1,\ldots,n\},\sum_{i=1}^{n}d_{i}Y_{i}^{k}\ \leq Q \tag{4}\]  
\[\forall i\in\{1,\ldots,n\},\sum_{k=1}^{M}Y_{1}^{k}=M \tag{5}\]  
\[\forall i\in\{1,\ldots,n\},\sum_{k=1}^{M}Y_{i}^{k}=1 \tag{6}\]  
* Constraint 4 requires that the loading capacity of each vehicle is respected;
* Constraint 5 requires a unique passage for each customer;
* Constraint 6 allows one to check the construction of M tours. Several metaheuristics are used to solve the vehicle-routing problem. They include simulated annealing [11], tabu search [12; 13], the ant colony algorithm [14; 15], and genetic algorithms [16; 17]. A detailed study of several approaches to solving the VRP can be found in [18; 19; 20; 21] (see Table 1). However, many real problems are not static but have a dynamic character. A new customer can occur at the last minute, a road can become impassable, road congestion can occur, or a vehicle can break down. In these cases, vehicle planning must be changed in response to these changes that may arise over time [23; 24; 25; 26]. Figure 2 presents a silhouette to mark this dynamism. Several metaheuristics have been presented in the literature to solve the the dynamic VRP (see Table 2). To mark the dynamic character of the problem, [PERSON] et al. [27] proposed a memetic ant colony optimization algorithm with an adaptation for the evaporation of pheromones. Likewise, in another work based on the ant colony system, [PERSON] et al. also gave a panoply of ideas with the insertion of random immigrants, elitism-based immigrants, or memory-based immigrants [28; 29]. [PERSON] et al. proposed a genetic algorithm with PMX crossover and swaps or 2-opt mutations [30]. The Evolutionary Hyper-Heuristics proposed by [PERSON] et al. evolved and utilized constructive, perturbation, and noise heuristics to solve the dynamic VRP [31]. To maintain the diversity of the population,