# On the Use of Learnheuristics in Vehicle Routing Optimization Problems with Dynamic Inputs
## 2 Problem Description  
The VRP is a well-known _NP_-hard problem. Accordingly, metaheuristic solving approaches have been developed to solve large-scale instances in reasonable computing times. Consider a complete and undirected graph \(G=\{V,E\}\), where \(V=\{0,1,2,...,n\}\) is a set of nodes composed of a depot \(0\) and \(n\) customers, and \(E\) is the set of edges connecting all nodes in \(V\). Each customer \(i\) has a positive demand, \(d_{i}>0\). Traversing an edge \((i,j)\) in \(E\) has an associated fixed cost \(c_{ij}=c_{ji}>0\). There is a fleet of homogeneous vehicles, each with a capacity \(Q\), with \(Q>>\max\{d_{i}\}\). A solution for this problem is a set of round-trip routes starting at the depot and connecting a set of customers. The total delivery in each route cannot exceed the capacity of each vehicle, \(Q\). All the demands have to be satisfied and a customer may only be visited once. Typically, the objective function minimizes the total distribution costs.  
The DVRP that we consider assumes that the costs are \(c_{ij}^{*}=f\left(c_{ij},S\right)\), where \(c_{ij}\) is the average cost associated with the edge \((i,j)\), and \(S\) is the current state of the problem. A key aspect is that \(f\left(c_{ij},S\right)\) is unknown, and can only be computed once we have defined a state \(S\). Thus, the costs are neither known in advance nor static. Indeed, they may depend on unpredictable factors (such as accidents) or predictable ones (such as the weather or the congestion level). We build a model (WB) that will estimate the behavior of \(f\) in order to generate accurate forecasts regarding the consequences of our  
Figure 1: Diagram of the learnheuristics methodology applied to construct a single solution for the DVRP.  
decisions. This approach is based on online statistical learning since new data is progressively used to update the model.  
For experimental purposes, the BB function \(f\), which is unknown for the solving approach, is defined as:  
\[c^{*}_{ij}:=f\big{(}c_{ij},S\big{)}=c_{ij}\Big{(}1+\beta_{1}Q^{k}_{i}+\beta_{2}+ \epsilon\Big{)}, \tag{1}\]  
where \(Q^{k}_{i}\) is the load of the vehicle at the moment of departure from node \(i\) in route \(k\), \(\beta_{1}\) and \(\beta_{2}\) are parameters of the model, and \(\epsilon\) is an error term which follows a uniform distribution. We use this model as the BB, and each time the solving approach evaluates one candidate solution, it provides data of a realization (i.e., after completing these routes). The WB is progressively updated and improved with this new data. Notice that Equation (1) represents the real-life (black box) dynamic behavior in our model. Thus, the real cost (e.g., traveling time) associated with traversing an edge is a function of the system status. For experimental purposes, we assume that this real-life cost can be modeled as a linear function of the vehicle load in the traversed edge. Of course, the exact value of this load will depend upon the customers already visited by the vehicle in its assigned route, i.e., these inputs are influenced by the decision variables.