Targeted Multiobjective Dijkstra Algorithm

Pedro Maristany de las Casas(maristanyzib.de)
Luitgard Kraus(krauszib.de)
Sedeño-Noda Antonio(asedenoull.edu.es)
Borndörfer Ralf(borndoerferzib.de)

Abstract: 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.

Keywords: Multiobjective Shortest Path, Label Setting Algorithm, Dijkstra's Algorithm, Heuristic Search, Dynamic Programming, Multicriteria Optimization

Category 1: Other Topics (Multi-Criteria Optimization )

Category 2: Network Optimization

Citation:

Download: [PDF]

Entry Submitted: 12/22/2021
Entry Accepted: 12/22/2021
Entry Last Modified: 12/22/2021

Modify/Update this entry