Linear, non-approximated models for optimal routing in hazardous environments
- PDF / 438,314 Bytes
- 8 Pages / 595 x 842 pts (A4) Page_size
- 68 Downloads / 205 Views
#1998 Operational Research Society Ltd. All rights reserved. 0160-5682/98 $12.00
Linear, non-approximated models for optimal routing in hazardous environments V Marianov1 and C ReVelle2 1
Catholic University of Chile and 2 The Johns Hopkins University, USA
A linear optimisation model is presented for the routing of vehicles through hazardous environments or for routing vehicles carrying hazardous materials. The model seeks to ®nd the route with the minimum cost and the minimum probability of accident. As opposed to previously published models, the formulation is linear and no approximations are needed, even in the case of high risk. Several forms of considering risk are presented, as well as a simple method of solution in polynomial time. An example is shown and solved. Keywords: accidents; optimisation; risk; road transport; vehicle routing
Introduction Finding the best route for a vehicle in a hazardous environment means ®nding a route with a low probability of accident. The goal is to protect the vehicle from the environment, or from some speci®c danger, which may depend on the route taken by it. Finding the best route for a hazardous material (HAZMAT) is a related problem, in which the environment is to be protected from the vehicle, specially if an accident happens in which the MAZMAT is spilled, or released in some fashion. In both cases, the route is better if the cost of routing the vehicle through it is low. Furthermore, we show in this paper that the mathematical models for both problems are essentially the same. Several models have been presented in the recent literature for the routing of vehicles carrying hazardous materials,1±3 which, under special conditions (very low risk) can be applied to the routing of vehicles through hazardous environments. Although exact models for minimising the probability of an accident are non-linear, in almost all of the existing literature,4±6 these models are approximated by linear versions, by assuming very small probabilities of an accident on each arc of the route. There are some high-risk cases, however, in which this approximation is not possible, because it leads to large errors. Finding the best route between two points for military vehicles during war is one such example, because the probability of disruption of any arc on a route is not in®nitesimal. Another example, is the routing of passenger buses through rural environments, such as those existing in developing countries (an extreme example is the Amazon jungle), in which the arcs of the route have a high probability of not being usable because of Correspondence: Dr V Marianov, Department of Electrical Engineering, Catholic University of Chile, VicunÈa, Mackenna 4860, Santiago, Chile. E-mail, [email protected]
¯oods caused by heavy storms, accidents, insurgencies, etc. In support of the fact that the highway system itself constitutes a hazardous environment in developing nations, the reader is referred to Saaty,7 where the scale of and strategy for investment necessary to bring the highway system of th
Data Loading...
