TY - CONF
AU - Antonio Sedeño-Noda
AU - Marcos Colebrook
T1 - The multiobjective Dijkstra’s algorithm
LA - eng
PY - 2018
SP - 68
T2 - European Conference on Operational Research. EURO2018. (29, 2018, Valencia)
SN - 978-84-09-02938-9
AB - 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.
UR - https://portalciencia.ull.es/documentos/60800bfd4d9b1a5d4197cf22
DP - Dialnet - Portal de la Investigación
ER -