Towards Automated Innovization for Route Planning: Innovized Heuristics and Problem Class Bounds

This paper proposes a novel concept for automating innovization for route planning through the extraction and reuse of knowledge from route feature distributions. The resulting so-called innovized heuristic is applicable to an entire class of routing problems. Innovized heuristics offer a flexible stochastic structure that is still intuitively understandable in the context of vehicle routing. Concerning the bounds of problem classes, our case study on route planning in central Berlin versus Manhattan indicates that innovized heuristics are not transferable between cities with different layouts.