Multicriteria adaptive paths in stochastic, time-varying networks

详细信息    查看全文

• 作者：Sathaporn Opasanon and Elise Miller-Hooks
• 关键词：Multiple criteria analysis ; Shortest paths ; Stochastic ; time-dependent networks ; Transportation
• 刊名：European Journal of Operational Research
• 出版年：2006
• 出版时间：16 August 2006
• 年：2006
• 卷：173
• 期：1
• 页码：72-91
• 全文大小：300 K

文摘

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.