dc.contributor.author |
Sedeño-Noda, A |
en |
dc.contributor.author |
Raith, Andrea |
en |
dc.date.accessioned |
2015-05-19T04:23:54Z |
en |
dc.date.issued |
2015-05 |
en |
dc.identifier.citation |
Computers & Operations Research, 2015, 57 pp. 83 - 94 |
en |
dc.identifier.issn |
0305-0548 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/25578 |
en |
dc.description.abstract |
We address the problem of determining all extreme supported solutions of the biobjective shortest path problem. A novel Dijkstra-like method generalizing Dijkstra׳s algorithm to this biobjective case is proposed. The algorithm runs in O(N(m+n log n)) time to solve one-to-one and one-to-all biobjective shortest path problems determining all extreme supported non-dominated points in the outcome space and one supported efficient path associated with each one of them. Here n is the number of nodes, m is the number of arcs and N is the number of extreme supported points in outcome space for the one-to-all biobjective shortest path problem. The memory space required by the algorithm is O(n+m) for the one-to-one problem and O(N+m) for the one-to-all problem. A computational experiment comparing the performance of the proposed methods and state-of-the-art methods is included. |
en |
dc.relation.ispartofseries |
Computers & Operations Research |
en |
dc.rights |
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. Details obtained from http://www.elsevier.com/about/policies/article-posting-policy#accepted-manuscript
http://www.sherpa.ac.uk/romeo/issn/0305-0548/ |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.rights.uri |
http://creativecommons.org/licenses/by-nc-nd/4.0/ |
en |
dc.title |
A Dijkstra-like method computing all extreme supported non-dominated solutions of the biobjective shortest path problem |
en |
dc.type |
Journal Article |
en |
dc.identifier.doi |
10.1016/j.cor.2014.11.010 |
en |
pubs.begin-page |
83 |
en |
pubs.volume |
57 |
en |
dc.description.version |
AM - Accepted Manuscript |
en |
pubs.end-page |
94 |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/OpenAccess |
en |
pubs.subtype |
Article |
en |
pubs.elements-id |
472116 |
en |
pubs.org-id |
Engineering |
en |
pubs.org-id |
Engineering Science |
en |
pubs.record-created-at-source-date |
2015-05-19 |
en |