A many-objective route planning benchmark problem for navigation

Abstract

Route planning is one of the key elements in logistics, mobile robotics, and other applications, where engineers face many conflicting objectives. However, most of the current route planning algorithms consider merely up to three objectives. In this paper, we propose a scalable many-objective benchmark problem covering most of the key features for routing applications based on real-world data. We define five objective functions representing distance, travelling time, delays, and two route-specific features such as curvature and elevation. We define one instance for this test problem and provide its true Pareto-front to analyse the problem difficulties. We apply three well-known evolutionary algorithms. Since this test benchmark can be easily transferred to real-world routing problems, we construct a routing problem from OpenStreetMap data. We evaluate the three optimisation algorithms and observe that we can provide promising results for such a real-world application. The proposed benchmark represents a scalable many-objective route planning optimisation problem enabling researchers and engineers to evaluate their navigation and routing approaches.