We consider routing problems in dynamic networks where arc travel times are both random and time dependent. The problem of finding the best route to a fixed destination is formulated in terms of shortest hyperpaths on a suitable time-expanded directed hypergraph. The latter problem can be solved in linear time, with respect to the size of the hypergraph, for several definitions of hyperpath length. Different criteria for ranking routes can be modeled by suitable definitions of hyperpath length. We also show that the problem becomes intractable if a constraint on the route structure is imposed.

A directed hypergraph model for random time dependent shortest paths / Pretolani, Daniele. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - STAMPA. - 123:2(2000), pp. 315-324. [10.1016/S0377-2217(99)00259-3]

A directed hypergraph model for random time dependent shortest paths

PRETOLANI, Daniele
2000

Abstract

We consider routing problems in dynamic networks where arc travel times are both random and time dependent. The problem of finding the best route to a fixed destination is formulated in terms of shortest hyperpaths on a suitable time-expanded directed hypergraph. The latter problem can be solved in linear time, with respect to the size of the hypergraph, for several definitions of hyperpath length. Different criteria for ranking routes can be modeled by suitable definitions of hyperpath length. We also show that the problem becomes intractable if a constraint on the route structure is imposed.
2000
123
2
315
324
A directed hypergraph model for random time dependent shortest paths / Pretolani, Daniele. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - STAMPA. - 123:2(2000), pp. 315-324. [10.1016/S0377-2217(99)00259-3]
Pretolani, Daniele
File in questo prodotto:
Non ci sono file associati a questo prodotto.
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/585398
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 76
  • ???jsp.display-item.citation.isi??? 63
social impact