The K shortest paths problem has been extensively studied for many years. Efficient methods have been devised, and many practical applications are known. Shortest hyperpath models have been proposed for several problems in different areas, for example in relation with routing in dynamic networks. However, the K shortest hyperpaths problem has not yet been investigated.In this paper we present procedures for finding the K shortest hyperpaths in a directed hypergraph. This is done by extending existing algorithms for K shortest loopless paths. Computational experiments on the proposed procedures are performed, and applications in transportation, planning and combinatorial optimization are discussed.

Finding the K shortest hyperpaths / K. A., Andersen; L. R., Nielsen; Pretolani, Daniele. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - STAMPA. - 32:6(2005), pp. 1477-1497. [10.1016/j.cor.2003.11.014]

Finding the K shortest hyperpaths

PRETOLANI, Daniele
2005

Abstract

The K shortest paths problem has been extensively studied for many years. Efficient methods have been devised, and many practical applications are known. Shortest hyperpath models have been proposed for several problems in different areas, for example in relation with routing in dynamic networks. However, the K shortest hyperpaths problem has not yet been investigated.In this paper we present procedures for finding the K shortest hyperpaths in a directed hypergraph. This is done by extending existing algorithms for K shortest loopless paths. Computational experiments on the proposed procedures are performed, and applications in transportation, planning and combinatorial optimization are discussed.
2005
32
6
1477
1497
Finding the K shortest hyperpaths / K. A., Andersen; L. R., Nielsen; Pretolani, Daniele. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - STAMPA. - 32:6(2005), pp. 1477-1497. [10.1016/j.cor.2003.11.014]
K. A., Andersen; L. R., Nielsen; Pretolani, Daniele
File in questo prodotto:
File Dimensione Formato  
KSBT-CaOR.pdf

Accesso riservato

Tipologia: Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione 317 kB
Formato Adobe PDF
317 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/457155
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 58
  • ???jsp.display-item.citation.isi??? 46
social impact