Bicriterion shortest hyperpaths in random time-dependent networks

Bicriterion shortest hyperpaths in random time-dependent networks

0.00 Avg rating0 Votes
Article ID: iaor20062892
Country: United Kingdom
Volume: 14
Issue: 3
Start Page Number: 271
End Page Number: 303
Publication Date: Jul 2003
Journal: IMA Journal of Management Mathematics (Print)
Authors: , ,
Keywords: programming: multiple criteria
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.