Bicriterion shortest hyperpaths in random time-dependent networks

In relevant application areas, such as transportation and telecommunications,there has recently been a growing focus on random time-dependentnetworks (RTDNs), where arc lengths are represented by time-dependentdiscrete random variables. In such networks, an optimal routingpolicy does not necessarily correspond to a path, but ratherto an adaptive strategy. Finding an optimal strategy reducesto a shortest hyperpath problem that can be solved quite efficiently. The bicriterion shortest path problem, i.e. the problem offinding the set of efficient paths, has been extensively studiedfor many years. Recently, extensions to RTDNs have been investigated.However, no attempt has been made to study bicriterion strategies.This is the aim of this paper. Here we model bicriterion strategy problems in terms of bicriterionshortest hyperpaths, and we devise an algorithm for enumeratingthe set of efficient hyperpaths. Since the computational effortrequired for a complete enumeration may be prohibitive, we proposesome heuristic methods to generate a subset of the efficientsolutions. Different criteria are considered, such as expectedor maximum travel time or cost; a computational experience isreported.