A new model for path planning with interval data

In this paper, we establish a new model for path planning with interval data which arises in a variety of applications. It is formulated as minimum risk-sum path problem  : given a source-destination pair in a network G=(V,E)G=(V,E), traveling on each link e in G   may take time xexe in a prespecified interval [le,ue][le,ue] and take risk (ue-xe)/(ue-le)(ue-xe)/(ue-le), the goal is to find a path in G from the source to the destination, together with an allocation of travel times along each link on the path, so that the total travel time of links on the path is no more than a given time bound and the risk-sum over the links on the path is minimized. Our study shows that this new model has two features that make it different from the existing models. First, the minimum risk-sum path problem is polynomial-time solvable, and second, it provides many solutions that vary with time bounds and risk sums and leaves the choice for decision makers. Therefore, the new model is more flexible and easier to use for the path planning with interval data.