Heuristic path selection in OR-graphs with application to HAZMAT routing

Considers the problem of path selection for a generalized HAZMAT routing problem where there are multiple destinations and where there are multiple and nonseparable objectives. This problem may be modeled as an OR-graph where the authors assume that arc cost estimates are given but actual arc cost determination requires some computational effort. To solve this problem the authors use two related algorithms, BU* and DU*, which are guaranteed to terminate with the optimal path given an admissible heuristic set. Computational results indicate that the algorithms´ graph-pruning power significantly reduces both the number of arc cost determination steps and node expansion steps