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-dependent networks (RTDNs), where arc lengths are represented by time-dependent discrete random variables. In such networks, an optimal routing policy does not necessarily correspond to a path, but rather to an adaptive strategy. Finding an optimal strategy reduces to a shortest hyperpath problem that can be solved quite efficiently.The bicriterion shortest path problem, i.e. the problem of finding the set of efficient paths, has been extensively studied for 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 bicriterion shortest hyperpaths, and we devise an algorithm for enumerating the set of efficient hyperpaths. Since the computational effort required for a complete enumeration may be prohibitive, we propose some heuristic methods to generate a subset of the efficient solutions. Different criteria are considered, such as expected or maximum travel time or cost; a computational experience is reported.