A directed hypergraph model for random time dependent shortest paths

详细信息    查看全文

• 作者：Pretolani ; Daniele
• 关键词：Network programming ; Random ; time-dependent ; shortest paths ; Directed hypergraphs
• 刊名：European Journal of Operational Research
• 出版年：2000
• 出版时间：June 1, 2000
• 年：2000
• 卷：123
• 期：2
• 页码：315-324
• 全文大小：167 K

文摘

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.