# On the Use of Learnheuristics in Vehicle Routing Optimization Problems with Dynamic Inputs
## 4 Proposed Methodology
### Metaheuristic Algorithm  
There are plenty of metaheuristics that may be applied to address the DVRP. We propose a multi-start method [29], which is a highly popular and relatively simple-to-implement metaheuristic with a reduced number of parameters. It proposes to iteratively build solutions from scratch until a stopping criterion is satisfied, and then return the best one. The constructive heuristic of the proposed solving approach for building solutions is the Clarke and Wright's Savings (CWS) heuristic [30], which is a classical and fast heuristic for the VRP. In particular, the CWS is an iterative method that considers an initial base solution where each customer is served by a dedicated vehicle. Then, the heuristic starts an iterative process where route merges are applied so that vehicles can serve various customers. The merging criterion is based on the concept of savings. Given two customers, a savings value is assigned to the edge connecting them. This savings value represents the savings in cost generated by serving both customers with the same vehicle instead of using a dedicated vehicle for each customer. Thus, a list of edges ranked by their savings can be constructed. This is the so-called savings list. At each iteration of the process, the first edge on the list is taken as a candidate for merging the corresponding routes. There are two conditions that have to be satisfied to accept the merge: (_i_) the nodes defining the edge are adjacent to the depot; and (_ii_) the total demand of the customers in the new route does not exceed the capacity of the vehicle. The merging process continues until there are no more edges on the list to be considered, ending the heuristic method. The CWS heuristic usually provides good solutions for small and medium size problem instances [31]. Authors in reference [32] propose an improvement of the CWS heuristic. Their approach, biased randomized CWS (BR-CWS), introduces non-uniform randomness in the selection of edges to be considered from the savings list. While the classical heuristic considers iteratively each edge in the list (which is sorted from the edge with the highest savings to the one with the lowest savings), the BR-CWS algorithm reorders that list with a non-uniform or biased randomness. In particular, a random number is generated from a given probability distribution (either a theoretical or an empirical one). Then, the edge in the position of the random number is selected and deleted from the list of savings, and the merging of the corresponding routes is considered. Afterwards, a new random number is generated and the same steps are applied until the savings list is empty. A skewed probability distribution is required to follow the logic behind the CWS heuristic. In other words, the higher the savings associated with an edge, the higher its probability of being selected. By modifying the greedy behavior of the CWS heuristic, the randomized version may consider more solutions and return a better one. Obviously, building more solutions also means more computational time. However, since the CWS heuristic is fast, the BR-CWS heuristic may build hundreds or thousands of solutions in just a few seconds. Biased randomization techniques have been successfully applied to solve different VRPs [33; 34; 35; 36], arc routing problems [37], and even scheduling problems [38; 39; 40]. For a complete review on biased-randomization techniques, the reader is referred to [41].