Innovization for Route Planning Applied to an Uber Movement Speeds Dataset for Berlin

Multi-objective route planning is a prominent but computationally expensive optimisation problem of everyday life. Reusing knowledge from similar route planning problems could enhance the performance and the sustainability of routing algorithms. The goal of this paper is to adapt the concept of innovization to route planning and in this way extract knowledge from Pareto-optimal solutions. As part of the adaptation, we design a multi-objective evolutionary algorithm for routing and introduce a novel local search for routing problems called Perimeter Mutation Local Search. We evaluate our proposed approach on multi-objective time-dependent routing problems to see what knowledge can be gained and whether this knowledge can improve a multiobjective evolutionary algorithm. Our results show that we can extract knowledge using the introduced innovization for route planning. This knowledge is used to improve a multiobjective evolutionary algorithm by reducing computational effort. With only about 40 % of previously necessary function evaluations, we manage to produce similar optimisation results. This is particularly beneficial for mobile applications with limited available computational resources.