 A biobjective Dijkstra algorithmAntonio Sedeño-noda and Marcos Colebrook European Journal of Operational Research, 2019, vol. 276, issue 1, 106-118 Abstract: We generalize the Dijkstra algorithm to the Biobjective Shortest Path (BSP) problem. The proposed method keeps only one candidate label per node in a priority queue of size n. In this way, we introduce a novel algorithm to solve the one-to-all BSP problem determining all non-dominated points in the outcome space and one efficient path associated with each of them. For the case of the one-to-one BSP problem, we incorporate the classical bidirectional search scheme in the proposed algorithm to reduce the number of iterations in practice. The proposed algorithm also includes pruning strategies to avoid the computation of unnecessary labels. The result is a fast algorithm to solve the one-to-one BSP problem in large networks. A computational experiment comparing the performance of the proposed method and the state-of-the-art methods is included. Keywords: Network optimization; Biobjective path problems; Efficient paths; Dijkstra's algorithm (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:276:y:2019:i:1:p:106-118 DOI: 10.1016/j.ejor.2019.01.007 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.