Heuristic Multiobjective Search for Hazmat Transportation Problems

This paper describes the application of multiobjective heuristic search algorithms to the problem of hazardous material (hazmat) transportation. The selection of optimal routes inherently involves the consideration of multiple conflicting objectives. These include the minimization of risk (e.g. the exposure of the population to hazardous substances in case of accident), transportation cost, time, or distance. Multiobjective analysis is an important tool in hazmat transportation decision making. This paper evaluates the application of multiobjective heuristic search techniques to hazmat route planning. The efficiency of existing algorithms is known to depend on factors like the number of objectives and their correlations. The use of an informed multiobjective heuristic function is shown to significantly improve efficiency in problems with two and three objectives. Test problems are defined over random graphs and over a real road map.