Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Targeted multiobjective Dijkstra Algorithm

  • We introduce the Targeted Multiobjective Dijkstra Algorithm (T-MDA), a label setting algorithm for the One-to-One Multiobjective Shortest Path (MOSP) Problem. It is based on the recently published Multiobjective Dijkstra Algorithm (MDA) and equips it with A*-like techniques. For any explored subpath, a label setting MOSP algorithm decides whether the subpath can be discarded or must be stored as part of the output. A major design choice is how to store subpaths from the moment they are first explored until the mentioned final decision can be made. The T-MDA combines the polynomially bounded size of the priority queue used in the MDA and alazy management of paths that are not in the queue. The running time bounds from the MDA remain valid. In practice, the T-MDA outperforms known algorithms from the literature and the increased memory consumption is negligible. In this paper, we benchmark the T-MDA against an improved version of the state of the art NAMOA∗drOne-to-One MOSP algorithm from the literature on a standard testbed.
Author:Pedro Maristany de las CasasORCiD, Luitgard KrausORCiD, Antonio Sedeno-NodaORCiD, Ralf BorndörferORCiD
Document Type:Article
Parent Title (English):Networks
First Page:277
Last Page:298
Year of first publication:2023
ArXiv Id:http://arxiv.org/abs/2110.10978
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.