In this paper, we introduce the Targeted Multiobjective Dijkstra Algorithm (T-MDA), a label setting algorithm for the One-to-One Multiobjective Shortest Path (MOSP) Problem. The T-MDA is based on the recently published Multiobjective Dijkstra Algorithm (MDA) and equips it with A*-like techniques. The resulting speedup is comparable to the speedup that the original A* algorithm achieves for Dijkstra's algorithm. Unlike other methods from the literature, which rely on special properties of the biobjective case, the T-MDA works for any dimension. To the best of our knowledge, it gives rise to the first efficient implementation that can deal with large scale instances with more than two objectives. A version tuned for the biobjective case, the T-BDA, outperforms state-of-the-art methods on almost every instance of a standard benchmark testbed that is not solvable in fractions of a second.
翻译：在本文中,我们引入了目标多目标Dijkstra Algorithm(T-MDA),这是一对一多目标最短路径(MOSP)问题的标签设置算法。T-MDA基于最近出版的多目标Dijkstra Algorithm(MDA), 并配有类似A* 的技术。 由此产生的速度与原A* 算法为Dijkstra的算法所实现的加速率相当。 与文献中其他方法不同, T-MDA依赖双目标案例的特殊性。 T- MDA为任何层面工作。 据我们所知, 它产生了第一个有效的实施, 能够处理大型案例, 有两个以上的目标。 一种版本针对双目标, T- BDA, 超越了几乎每个标准基准测试台的状态方法, 而在第二小部分中是无法解决的。
相关内容
微信扫码咨询专知VIP会员