Data-driven operators for a hybrid evolutionary algorithm to solve multi-trip rich vehicle routing problem

Abstract

Vehicle routing problems have been the subject of intensive research due to their di culty as a combinatorial optimization problem and their importance in real life operations. Heuristics are widely preferred to solve VRPs especially in large scale realworld applications. With the growth of data storage and development of ML tools, data mining has started to be used to enhance heuristics. However, there is not much work involving a general learning scheme within VRP heuristics because of the complicated nature of multi-attribute variants. Most common features of a VRP instance such as routing sequence, vehicle capacity, time windows, unit costs of travel contain valuable information about the quality of the solution. In this study, we propose to gather the aforementioned characteristics of every past solution during the search and build a dynamic predictive model on it. A novel removal operator based on the predictions of this model is integrated into the heuristic. Population-based heuristics are suitable for this task because of their inherent solution pool hence we chose a hybrid evolutionary algorithm designed for a Multi-Trip Rich VRP. We discuss the marginal e ects of adding this simple and fast data-driven removal operator into the base method. Moreover, we de ne modi cations of this new operator focusing on di erent features of the sample and try to interpret their performance. Our experiments on the benchmark instances have shown that this straightforward and adaptable framework generates promising results.