Dynamic programming and minimum risk paths

doi:10.1016/j.ejor.2005.03.042

Return

Dynamic programming and minimum risk paths

2006-11-01

Paolo Serafini *

DOI：10.1016/j.ejor.2005.03.042

Original

Save

View PDF

Abstract

En 中文

This paper addresses the problem of computing minimum risk paths by taking as objective the expected accident cost. The computation is based on a dynamic programming formulation which can be considered an extension of usual dynamic programming models: path costs are recursively computed via functions which are assumed to be monotonic. A large part of the paper is devoted to analyze in detail this formulation and provide some new results. Based on the dynamic programming model a linear programming model is also presented to compute minimum risk paths. This formulation turns out to be useful in solving a biobjective version of the problem, in which also expected travel length is taken into consideration. This leads to define nondominated mixed strategies. Finally it is shown how to extend the basic updating device of dynamic programming in order to enumerate all nondominated paths. (c) 2005 Elsevier B.V. All rights reserved.

Keywords:

routing

risk analysis

dynamic programming

multiple objective programming

hazardous materials

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.