The multiobjective Dijkstra’s algorithm

  1. Antonio Sedeño-Noda 1
  2. Marcos Colebrook 1
  1. 1 Universidad de La Laguna
    info

    Universidad de La Laguna

    San Cristobal de La Laguna, España

    ROR https://ror.org/01r9z8p25

Actas:
European Conference on Operational Research. EURO2018. (29, 2018, Valencia)

ISBN: 978-84-09-02938-9

Año de publicación: 2018

Páginas: 68

Tipo: Aportación congreso

Resumen

We address the problem of determining all efficient solutions of theBiobjective Shortest Path (BSP) problem. We generalize Dijkstra’s algorithm to the Multiobjective Shortest Path (MSP) problem since theproposed methods keep only one candidate label per node in a priorityqueue of size n. The algorithm runs in O(Nlogn +mNmax2 ) time anduses O(N + m) space to solve the one-to-all BSP problem determiningall non-dominated points in the outcome space and one efficient pathassociated with each one of them. Here n is the number of nodes, m isthe number of arcs, N is the number of non-dominated points in outcome space for the one-to-all BSP problem and Nmax is the greatestnumber of non-dominated points in the outcome space for the one-toone s-i BSP problem for all node i =1,. . . ,n. For the case of the one-toone s-t BSP problem, we incorporate the classical Bidirectional Searchscheme in the proposed algorithms to reduce the number of iterationsin practice. Also, the proposed algorithms include pruning strategiesto avoid the computation of unnecessary dominated labels. The result is a fast algorithm to solve the BSP problem in large networks. Acomputational experiment comparing the performance of the proposedmethods and state-of-the-art methods is included.