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 -