Computing shortest paths for transportation of hazardous materials in continuous spaces

This paper is concerned about the problem of locating a path for a shipment of dangerous goods between a pre-specified origin-destination pair on the plane. Minimization of risks during the transportation and cost of the path have been taken into account. The formulation of the main problem considered in this paper is the following: Given a source point a, a destination point b, a set S of demand sites (points in the plane) and a positive value 1, we want to compute a path connecting a and b with length at most I such that the minimum distance to the points in S is maximized. We propose an approximate algorithm based on the bisection method to solve this problem. Our technique reduces the optimization problem to a decision problem, where one needs to compute the shortest path such that the minimum distance to the demand points is not smaller that a certain amount r. To solve the decision task, we transform the problem to the computation of the shortest path avoiding obstacles. This approach provides efficient algorithms to compute shortest obnoxious paths under several kinds of distances. (c) 2004 Elsevier Ltd. All rights reserved.