Finding the K shortest hyperpaths using reoptimization

Lars Relund Nielsen, Daniele Pretolani and Kim Allan Andersen ()
Additional contact information
Lars Relund Nielsen: Biometry Research Unit, Postal: Research Centre Foulum, P.O. Box 50, DK-8830 Tjele
Daniele Pretolani: Dipartimento de Matematica e Informatica, Postal: Universita di Camerino, Via Madonna delle Carceri, I-62032 Camerino (MC), Italy
Kim Allan Andersen: Department of Business Studies, Postal: The Aarhus School of Business, Fuglesangs Allé 4, 8210 Aarhus V, Denmark, http://www.asb.dk/staff/bs/kia.aspx?page=%7B803EFF10-69F7-4C0F-AEE3-F7F410E4B6F2%7D

No L-2004-04, CORAL Working Papers from University of Aarhus, Aarhus School of Business, Department of Business Studies

Abstract: The shortest hyperpath problem is an extension of the classical shortest path problem and has applications in many different areas. Recently, algorithms for finding the K shortest hyperpaths in a directed hypergraph have been developed by Andersen, Nielsen and Pretolani. In this paper we improve the worst-case computational complexity of an algorithm for finding the K shortest hyperpaths in an acyclic hypergraph. This result is obtained by applying new reoptimization techniques for shortest hyperpaths. The algorithm turns out to be quite effective in practice and has already been successfully applied in the context of stochastic time-dependent networks, for finding the K best strategies and for solving bicriterion problems.

Keywords: Network programming; Directed hypergraphs; K shortest hyperpaths; K shortest paths (search for similar items in EconPapers)
Pages: 15 pages
Date: 2004-11-15
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.hha.dk/afl/wp/log/L_2004_04.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to www.hha.dk:80 (No such host is known. )

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hhb:aarbls:2004-004

Access Statistics for this paper

More papers in CORAL Working Papers from University of Aarhus, Aarhus School of Business, Department of Business Studies The Aarhus School of Business, Fuglesangs Allé 4, DK-8210 Aarhus V, Denmark. Contact information at EDIRC.
Bibliographic data for series maintained by Helle Vinbaek Stenholt ( this e-mail address is bad, please contact ).