Multicriteria adaptive paths in stochastic, time-varying networks

In this paper, exact algorithms are proposed for addressing multicriteria adaptive path problems, where arc attributes are stochastic and time-varying. Adaptive paths comprise a set of path strategies that enable the traveler to select a direction among all Pareto-optimal solutions at each node in response to knowledge of the arrival time at the intermediate nodes. Such paths can be viewed as hyperpaths and are referred to in this way herein. The first algorithm generates all Pareto-optimal hyperpaths with respect to the expected value of multiple criteria from all origins to a specified destination for all departure times in a period of interest. The generation of all such Pareto-optimal hyperpaths may require enormous computational effort. Thus, two computationally efficient variations of an additional algorithm are proposed that rely on the use of a preference function in the form of a linear utility function to produce only a single hyperpath, i.e. the one that minimizes the expected disutility. Problems requiring the selection of such paths are encountered in a variety of applications, including selection of routes for hazardous materials transport, emergency response operations (medical, police, fire), intelligent transportation systems (ITS), and data networks.