# On the Use of Learnheuristics in Vehicle Routing Optimization Problems with Dynamic Inputs
###### Abstract  
Freight transportation is becoming an increasingly critical activity for enterprises in a global world. Moreover, the distribution activities have a non-negligible impact on the environment, as well as on the citizens' welfare. The classical vehicle routing problem (VRP) aims at designing routes that minimize the cost of serving customers using a given set of capacitated vehicles. Some VRP variants consider traveling times, either in the objective function (e.g., including the goal of minimizing total traveling time or designing balanced routes) or as constraints (e.g., the setting of time windows or a maximum time per route). Typically, the traveling time between two customers or between one customer and the depot is assumed to be both known in advance and static. However, in real life, there are plenty of factors (predictable or not) that may affect these traveling times, e.g., traffic jams, accidents, road works, or even the weather. In this work, we analyze the VRP with dynamic traveling times. Our work assumes not only that these inputs are dynamic in nature, but also that they are a function of the structure of the emerging routing plan. In other words, these traveling times need to be dynamically re-evaluated as the solution is being constructed. In order to solve this dynamic optimization problem, a learnheuristic-based approach is proposed. Our approach integrates statistical learning techniques within a metaheuristic framework. A number of computational experiments are carried out in order to illustrate our approach and discuss its effectiveness. vehicle routing problem; dynamic traveling times; learnheuristics +
Footnote †: journal:  
0000-0001-4500-3999-1000-0000-0000-0000-0000-00000-00000-00000-00000-00000-00000-00000-00000-00000-00000-00000-00000-00000-00000-00000-000000-00000-000  
During the last few years, the research community has been prolifically delivering new formulations and solving methods for the vehicle routing problem (VRP). Thus, review works on rich and real-life VRPs that can be found [8]. Some of the most popular categories are: asymmetric cost matrix VRP, heterogeneous fleet VRP, multiple depots VRP, periodic delivery VRP, VRP with time windows [9], VRP under dynamic conditions [10], and green VRP including the use of electric vehicles in smart cities [4], among others. However, there are plenty of open research lines in this field since most works tend to use strong assumptions in order to simplify the underlying optimization problem. In particular, a common assumption is that all the problem inputs are known in advance and that they do not change over time. This paper, however, considers a more realistic scenario in which some of the optimization inputs (the traveling times in our case) are dynamic, and they depend on the structure of the emerging solution, i.e., they are influenced by the decisions made while constructing a routing plan. Since we are considering time-based costs, these costs will depend upon the specific values of these traveling times. Thus, in this work, we introduce a version of the dynamic VRP (DVRP) which considers the \"state of the problem\". This state comprises a number of variables describing the particular configuration of the partial or complete solution, which includes the decisions made so far. Some examples are: the number of customers visited in a given route, the total cost or total demand in a route, and the load of a vehicle when visiting a given customer. The decisions of the planners may change the state of the problem and some inputs, which affect the quality of the solution. For instance, if a long route is designed, it may affect both the driver's capabilities and the resting time required by them, resulting in a longer traveling time. Similarly, the vehicle load may change the traveling time between customers and the emissions released (i.e., the order in which the customers are visited might affect the total traveling time as well as the greenhouse gas emissions).