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 PDF-file 

Download statistics

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 ().

This page generated on 2018-02-07 11:42:50.