Heuristic path selection in graphs with non-order preserving reward structure.

Abstract

The research presented in this dissertation is motivated by the problem of determining routes, from an origin to a destination through multiple intermediate stops, for vehicles transporting hazardous materials (HAZMAT). The reward structure considered is based on value assessments of multiple, non-commensurate and potentially competing attribute measures, such as risk to population, risk to the environment, distance, and travel time. Much of the HAZMAT routing research that incorporates value theory assumes that the reward structure is order preserving; i.e., all sub-paths of an optimal path are also optimal. However, in the context of HAZMAT routing, value representations of decision maker preferences will, in general, yield reward structures that are non-order preserving, and hence application of standard numerical techniques based on dynamic programming may not determine a most preferred path. We remark that the use of sub-optimal paths in transporting HAZMAT may pose significant liability concerns. Two iterative heuristic search algorithms, BU$\sp\*$ and DU$\sp\*$, are presented and analyzed for determining an optimal path in a digraph from a given start node, through a given set of intermediate nodes, to a given goal node set. It is assumed that the reward structure is not necessarily order preserving, bounds on the arc rewards are given a priori, and the determination of the actual arc rewards potentially requires significant computational effort. Further, it is assumed that for each node in the digraph, bounds are given on the rewards from that node to the goal node set. These assumptions reflect the fact that in routing a HAZMAT vehicle, there may be easily determined bounds on the rewards from the vehicle's current position to each intermediate stop (e.g., with regard to distance, bounds might be based on Euclidean distance). However, the determination of the exact arc rewards (e.g., the actual distance of an optimal route to an intermediate stop) may require significant numerical effort. We present analytical and computational results showing that exact solutions are guaranteed given upper bound on the rewards and conditions where improved bound information provides improved algorithm performance. The computational results are based on an analysis of a Northeast Ohio Highway Network.