# On the Use of Learnheuristics in Vehicle Routing Optimization Problems with Dynamic Inputs
###### Abstract
Although it might not be possible to accurately compute the effect of each decision on the cost of the emerging solution, we assume that it might be possible to estimate this impact by using statistical learning methods. The main challenge of our approach relies on being able to learn from new data (observations) obtained by checking our estimated cost with the real-life cost associated with our routing plan. Thus, we propose a hybrid approach integrating statistical learning [11] into a metaheuristic-based framework [12]. The metaheuristic component constructs new candidate solutions while the statistical learning component, based on the data gathered, makes predictions of the traveling time associated with each edge under the current system status. Some preliminary work can be found in [13; 14], which offers a comprehensive review on this hybrid framework and presents it as a novel methodology. However, in their application, both components are not dependent but separate entities combined to solve a VRP where customers' demands depend on the visiting order. In contrast, in our methodology, both components work together at each step while building solutions. This is done by generating data based on the decisions made so far, which is fed to the statistical learning model to make predictions regarding future decisions. Thus, we create an interdependence of both components to construct high-quality solutions. Figure 1 represents the basic idea behind the learnheuristics methodology applied to the dynamic VRP. In our approach, we will consider a 'black box' (BB) and a 'white box' (WB). The BB is an emulator of a real-life system that modifies the cost of a route based on its structure. The WB represents the statistical learning model, which aims at predicting the behavior of the BB. Figure 1 illustrates two approaches considering dynamic inputs: (_i_) the static approach (upper line), where the dynamism is ignored; and (_ii_) the dynamic approach (solid line) where the WB is used to predict the inputs at each step of the constructive methodology for building a solution. In the static approach, the BB is used to compute the real cost (RC) of the solutions, but no predictions are made. Also in the static approach, the model for the forecasted cost (FC) considers that the cost does not change throughout the construction of the solution. On the contrary, in the dynamic approach, data from the system and the outputs provided by the BB are gathered to generate FCs with the WB. Given a WB able to reproduce the behavior of the BB, we will be able to plan near-optimal routes by considering accurate input estimates. The solutions for the static and the dynamic approaches may be different since the decision-maker receives different information in each case. In this context, the main contributions of this work are: (_i_) to describe a more realistic version of the VRP, which includes dynamic traveling times; (_ii_) to introduce a hybrid solving methodology based on statistical learning techniques and a metaheuristic algorithm; and (_iii_) to build a set of benchmark instances, which allow other researchers to replicate our computational experiments and/or to compare their methodologies with ours. The rest of this paper is organized as follows: Section 2 provides a description of the problem addressed. Afterwards, Section 3 reviews related works, considering works on dynamic VRPs, as well as works on hybridizing metaheuristics and statistical learning to deal with combinatorial optimization problems. Section 4 presents the learnheuristics-based methodology proposed to solve the problem. Section 5 explains the computational experiments carried out to illustrate both the problem and the approach, while Section 6 analyzes the results obtained. Finally, Section 7 draws some conclusions and identifies some potential lines for future research.