TY - JOUR

T1 - Computing shortest paths for transportation of hazardous materials in continuous spaces

AU - Díaz-Báñez, J. M.

AU - Gómez, F.

AU - Toussaint, G. T.

N1 - Funding Information:
The first author is partially supported by Project MCYT BFM2000-1052-C02-01 and BFM2003-04062.

PY - 2005/10

Y1 - 2005/10

N2 - 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 l, we want to compute a path connecting a and b with length at most l 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.

AB - 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 l, we want to compute a path connecting a and b with length at most l 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.

KW - Analysis of algorithms: Computational complexity

KW - Extensive facility location

KW - Hazardous material transportation

UR - http://www.scopus.com/inward/record.url?scp=17944369869&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=17944369869&partnerID=8YFLogxK

U2 - 10.1016/j.jfoodeng.2004.05.076

DO - 10.1016/j.jfoodeng.2004.05.076

M3 - Article

AN - SCOPUS:17944369869

SN - 0260-8774

VL - 70

SP - 293

EP - 298

JO - Journal of Food Engineering

JF - Journal of Food Engineering

IS - 3

ER -