Optimization Online


Targeted Multiobjective Dijkstra Algorithm

Pedro Maristany de las Casas(maristany***at***zib.de)
Luitgard Kraus(kraus***at***zib.de)
Sede˝o-Noda Antonio(asedeno***at***ull.edu.es)
Bornd÷rfer Ralf(borndoerfer***at***zib.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


Download: [PDF]

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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society