Applications of non-order-preserving path selection to hazardous material routing

In this paper, we consider the problem of determining a path that maximizes a multi-attribute, non-order-preserving value function. The motivating application is the determination of a most preferred path for transporting hazardous materials based on transportation cost and risk to population. A sub-path of an optimal path may not be optimal for a non-order-preserving value function, implying that a traditional application of dynamic programming may intentionally or unintentionally produce sub-optimal paths. We consider two approximation procedures for two general cases, the q = 0 case and the q > 0 case, where q is the number of required intermediate stops between origin and destination. The first approximation procedure involves applying dynamic programming as if a sub-path of an optimal path were always optimal. The second approximation procedure involves determining a linear order-preserving criterion that approximates the non-order-preserving value function and then applying dynamic programming. We use the best-first search algorithm BU* to determine optimal routes for both the q = 0 and q > 0 cases. We examine the frequency and magnitude of the resulting sub-optimalities for a multi-attribute value model based on a six-county road network that includes Cleveland, Ohio. Numerical results show that if one of the two approximations is used, significant sub-optimalities can occur over a wide range of decision maker preferences. Both approximations can produce sub-optimality error magnitudes of over 50%.