Route planning also known as pathfinding 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 only up to three objectives. In this paper, we propose a scalable many-objective benchmark problem covering most of the important features for routing applications based on real-world data. We define five objective functions representing distance, traveling time, delays caused by accidents, and two route specific features such as curvature and elevation. We analyse several different instances for this test problem and provide their true Pareto-front to analyse the problem difficulties. We apply three well-known evolutionary multi-objective 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 are able to 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 many-objective approaches.
翻译:路径规划也称为路由探测,是物流、移动机器人和其他应用中的关键要素之一,工程师们面临许多相互冲突的目标。然而,目前路线规划算法大多只考虑三个目标。在本文件中,我们提出了一个可扩展的多目标基准问题,涵盖基于真实世界数据的路径应用的大部分重要特征。我们界定了代表距离、旅行时间、事故造成的延误和两个路途特定特征的五个客观功能,如曲线和高度。我们对这一测试问题分析了几个不同的实例,并提供了他们真实的Pareto前方来分析问题。我们采用了三个众所周知的进化多目标算法。由于这一测试基准可以很容易地转移到真实世界的路径问题,我们从OpenStreetMap数据中构建了一个路径问题。我们评估了三种选择算法,并观察到我们能够为这种真实世界应用提供有希望的结果。拟议的基准代表着一种可扩展的多目的路径规划优化问题,使研究人员和工程师能够评估其多目的方法。