# On the Use of Learnheuristics in Vehicle Routing Optimization Problems with Dynamic Inputs
## 4 Proposed Methodology
### Hybridization of the Metaheuristic Algorithm and the Statistical Learning Model  
The pseudo-code of our approach for building a single solution is shown in Algorithm 1 and explained next. In the (static) VRP, the savings list is generated once at the beginning of the execution, and it remains constant throughout the resolution. The savings associated with an edge is the benefit from merging the corresponding routes. When two routes are merged, the total cost of the new route cannot be greater than the sum of the individual separated routes (i.e., the saving cannot be negative when the cost is based on the Euclidean-distance metric due to the triangle inequality). This statement is no longer true in general for dynamic inputs due to the change of the state of the problem. Thus, the savings must be computed with the total cost of the routes. In the DVRP, we know the current state of the problem and, as a consequence, the cost of the two separate routes to merge. However, we do not know the total cost of the merged route before actually merging it. Thus, it is needed to predict this cost based on historical data, and then recompute the savings (see pseudo-code of Algorithm 2).  
The static approach for this problem does not present this nuance because the cost of a route is always known, while in our case it is only revealed once the merge is done. A key difference with respect to the static approach is the update of the savings list by means of the predictive model at each new state due to the dynamic nature of the problem. The hybridization of the metaheuristic and the statistical learning model is necessary to perform the task of keeping the list updated when new information is available. Generally, training a statistical learning model is an expensive task. The choice of implementing a multiple linear regression model was favored mainly for its fast execution times. Notice that the metaheuristic-based framework would not change if another statistical learning model was considered.  
```
1:procedureBuildDVRPsol(\(inputs\))
2:\(solution\leftarrow\) generateBaseSolution(\(inputs\))\(\triangleright\)\(inputs\): coordinates, demands and vehicles' capacity
3:\(savings\leftarrow\) computeSavings(\(solution\), \(whiteBox\))\(\triangleright\) edges list decreasingly sorted by savings
4:while(\(savings\) is not empty) do
5:\(index\leftarrow\) generate random number\(\triangleright\) given probability distribution
6:\(edge\leftarrow\) get edge from \(savings\) by index
7:\(savings\leftarrow\) delete\(edge\) from \(savings\)
8:if(mergeFeasible(\(edge\))) then
9:\(route\leftarrow\) emptyRoute
10:\(route\leftarrow\) mergeRoutes(\(edge\), \(solution\))
11:\(realCost\leftarrow\) blackBox.getRealCost(\(route\))
12: solution.update(\(realCost\))\(\triangleright\) update solution with the real cost of the route
13: whiteBox.update(\(route\), \(realCost\))\(\triangleright\) update White Box
14:\(savings\leftarrow\) computeSavings(\(solution\), \(whiteBox\))\(\triangleright\) update savings
15:endif
16:endwhile
17:return\(solution\)
18:endprocedure
```  
**Algorithm 1** Procedure to build a DVRP solution using the BR-CWS heuristic.  
```
1:procedureComputesavings(\(solution\), \(whiteBox\))
2:\(savings\leftarrow\) emptyList
3:\(exteriorNodes\leftarrow\) getExteriorNodes(\(nodes\))
4:for\(i=1\) to \(exteriorNodes.size-1\)do
5:for\(j=i+1\) to \(exteriorNodes.size\)do
6:\(iRout\leftarrow\) getRoute(\(exteriorNodes(i)\))
7:\(iRout\leftarrow\) getRoute(\(exteriorNodes(j)\))
8:\(mergedRoute\leftarrow\) mergeRoutes(\(iRoute\), \(jRoute\))
9:\(iRealCost\leftarrow\) getCost(\(iRoute\))\(\triangleright\) Black Box
10:\(jRealCost\leftarrow\) getCost(\(jRoute\))
11:\(mergedPredictedCost\leftarrow\) whiteBox.predictCost(\(mergedRoute\), solution)
12:\(routeSamples\leftarrow\) iRealCost + \(jRealCost\) - \(mergedPredictedCost\)
13:add\(routeSamples\) to \(savings\)
14:endfor
15:endfor
16:\(savings.sort\)\(\triangleright\) Sort in descending order
17:return savings
18:endprocedure
```  
**Algorithm 2** Procedure to compute the savings list.