Abstract

Algorithm selection based on problem instance features is a common method to choose approaches for NP-hard combinatorial optimization problems. Features concerning the location of nodes for the Vehicle Routing Problem (VRP) are intensively studied. Although the dynamic version of the problem is gaining steadily in importance, there is a lack in research targeting problem features describing the dynamism of an instance. In our paper we translate known VRP features to features for the Dynamic Vehicle Routing Problem (DVRP). We investigate the suitability of them for algorithm selection. To this end, we explore the performance space of a Greedy and a Re-planning algorithm for various dynamic problem instances using simulation and an evolutionary algorithm. For the algorithm selection we investigate our features in combination with a supervised machine learning technique. The applicability of our features is demonstrated in a use case for autonomous algorithm selection of DVRP instances.