Scandinavian Working Papers in Business Administration
CORAL Working Papers,
University of Aarhus, Aarhus School of Business, Department of Business Studies
No L-2004-04: 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
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
15 pages, November 15, 2004
Full text files
L_2004_04.pdf
- University of Aarhus, Aarhus School of Business, Department of Business Studies
- Home page for this series
Questions (including download problems) about the papers in this series should be directed to Helle Vinbaek Stenholt ()
Report other problems with accessing this service to Sune Karlsson ().
RePEc:hhb:aarbls:2004-004This page generated on 2024-09-13 22:18:12.