# GIS-Based Route Planning for HAZMAT Transportation

Alexander Preda, Mauno Rönkkö, Stefan Pickl, Mikko Kolehmainen

► To cite this version:

Alexander Preda, Mauno Rönkkö, Stefan Pickl, Mikko Kolehmainen. GIS-Based Route Planning for HAZMAT Transportation. 10th International Symposium on Environmental Software Systems (ISESS), Oct 2013, Neusiedl am See, Austria. pp.357-366, 10.1007/978-3-642-41151-9_34. hal-01457466

HAL Id: hal-01457466

https://inria.hal.science/hal-01457466

Submitted on 6 Feb 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# GIS-based Route Planning for HAZMAT Transportation

Alexander Preda<fnref n="1" />, Mauno Rönkkö<fnref n="2" />, Stefan Pickl<fnref n="1" />, and Mikko Kolehmainen<fnref n="2" />

**Abstract.** In this article we discuss the route planning of Hazardous Materials (HAZMAT). For HAZMAT transportation, safety and security is of utmost importance. Because of this, the route planning needs to consider potential risks and costs to find an optimal route for the transportation. It has been shown that the route planning is an NP hard problem. In this article, we approach the problem from a novel point of the view. As the main contribution, we present in this article a GIS-based route planing method that has many complementary advantages to graph-based route planning methods. We also illustrate the use of the method with a simple case study.

**Keywords:** Hazardous Materials, HAZMAT Transportation, Route Planning, GIS

## 1 Introduction

Today's living standards and living comfort would not be possible without the use of HAZMAT in industry. For instance, medicine, paints, cleaning agents, and fuels require the use of HAZMAT for their production. Furthermore, the production of such goods creates hazardous waste. Consequently, there is an increasing need for methods to handle ever more complex HAZMAT transportation problems.

Graph-based algorithms are typically used for planning HAZMAT transportation routes. The problem, however, is shown to be NP-hard, whereby one can only hope for good enough solutions. Moreover, route planning involves risk assessment which is based on estimates at best because of the underlying complexities as well as ethical and political considerations.

Because of this evolving nature of the route planning, there is a need to compute alternative settings with varying valuations and factors. This, however, is not well supported by graph-based algorithms that typically require full computations if some of the factors change. To overcome this problem, and as the main contribution, we propose here a GIS-based route planning method. It supports

<footnote n="1">¹ Faculty of Computer Sciences, University of Federal Armed Forces Munich
{alexander.preda,stefan.pickl}@unibw.de</footnote>

<footnote n="2">² Department of Environmental Science, University of Eastern Finland,
PO Box 1627, 70211 Kuopio, Finland,
{mauno.ronkko,mikko.kolehmainen}@uef.fi</footnote>
integration of partial valuations, and thereby it also supports computations of
alternative scenarios with varying valuations.

We shall start by discussing HAZMAT transportation and risks in Section 2.
In Section 3, we introduce the route planning problem. In Section 4, we present
the proposed GIS-based route planning method. In Section 5, we illustrate the
use of the method with a simple case study. And finally, in Section 6, follows the
conclusion.

## 2 About HAZMAT Transportation and Risks

The research on HAZMAT transportation began already in the 1990's. A more
recent overview about HAZMAT transportation can be found, for instance, in
[1]. The need for HAZMAT transportation is a direct consequence of our mod-
ern society, where the amount goods produced by using hazardous materials has
increased. Consequently, HAZMAT transportations have increased especially in
urban areas. Partially because of this, the HAZMAT Transportation process is
planned and carried out by considering certain national and international stan-
dard procedures, like the "UN Recommendations on the Transport of Dangerous
Goods" [2].

In HAZMAT transportation, there is always a risk involved. According to [3],
risk in the context of HAZMAT transportation is a measure of the probability
and severity of harm to an exposed receptor due to potential undesired events.
In this sense, risk can be assessed either qualitatively or quantitatively. In a
qualitative assessment, the goal is to identify possible scenarios. In a quantitative
assessment, consequences are modeled and made explicit, so that the exposed
receptors can be identified. All of this information is then used to calculate
numerical risk evaluations.

An alternative approach to HAZMAT transportation risk assessment is given
by Current and Ratick [4]. They consider the location of facilities coping with
HAZMAT in the assessment of risks and costs. Consequently, their definition for
risk is based on the amount of transported waste, and not on the losses when
an incident exposes transported HAZMAT to the environment. The analysis
by Current and Ratick proves that minimizing a risk is highly sensitive to its
definition. In particular, minimizing one part of the risk can degenerate the other
parts. It could even turn out that there is no stable solution for minimizing a
risk for a given objective. As an example, Current and Ratick define "minimizing
the risk per population density" as the objective 1, and "minimizing the total
transportation risk" as the objective 2. When focusing on the objective 1, one
can easily find solutions that increase transportation costs disproportionally. In
contrast, when focusing on the objective 2, one can find a stable solution. Still,
minimizing the costs for the objective 2 does increase the costs for the objective
1. All in all, the analysis by Current and Ratick suggests that the costs are
relatively strongly correlated with the risk.
## 3 The Route Planning Problem

In the planning of HAZMAT transportation routes, both local authorities and carriers need to interact. In effect, this means that the route planning problem is a two player game, as understood in game theory. In such a game, the local authority is interested in minimizing the risk of transportation, whereas the carrier is oriented, as pointed out by [1] and [5], to minimize the costs. In this process, diffuse information increases the difficulty for the local authority to determine a fix route. To date, the usual approach taken by the local authority is to design the whole transportation network and to allocate it to the carrier. In this way, the maximal transportation risk is to be kept below a certain threshold, while giving the carrier a choice to select the actual route within the network.

There are many route planning algorithms for the HAZMAT transportation. In particular, they involve explicitly risk assessment for the transportation, thus considering one or both of the following [6]: an incident probability during the transport and the scale of the impact on the population.

Route planning algorithms are typically based on graph theory. For instance, Dijkstra's Shortest Path algorithm [7] is one of the most famous algorithms that is used. In graph-based algorithms a directed graph models the transportation network. The usual coding is that the nodes represent crossroads or connection points, while the arcs represent streets or links in the transportation network. The weights for the arcs represent the "cost" for passing that link. The cost is an evaluation of, for instance, money, time, and risk factors.

As another example of a graph-based algorithm, Erkut and Alp formulate in [8] a method for designing a HAZMAT transportation network based on minimizing the total transportation risk. In the algorithm, heuristics are used for the cost optimization. The optimization is performed in two phases. Firstly, the optimization is done by the local authority to minimize the risks. Secondly, the carrier optimizes transportation costs by selecting the most convenient route. This process minimizes the probability that the route selected by the carrier increases the risk more than what is expected by the local authority. As in [4], Erkut and Alp distinguish between minimizing the total risk on the route and minimizing the selective risk on a certain road.

In later works [9], Erkut and Gzara propose a method for the HAZMAT transportation network design problem (HTNDP). The method yields stable solutions which are close to the optimal solutions. Their proposal is a bi-level model with an heuristic solution method, because the HTNDP may be ill-posed. In the center of their analysis is the trade-off between costs and risks.

Amaldi et al. [10] developed an improved mixed integer linear program with a bi-level inter-program based on the results of [9] and [8] for solving the HTNDP, and to guarantee the stability of the solution. Although Amaldi et al. deal with the HTNDP, the article concentrates on computational complexity. The conclusion is that the HTNDP with the option to forbid the use of certain arcs is NP-hard even when only a single commodity should be transported. Amaldi et al., however, point out that the HTNDP is often reduced to the shortest path problem extended with a heuristic. The heuristic consists of an iterative
elimination of allowed roads until the carrier is no longer able to use a different
route than the one with the minimal risk as expected by the local authority. As
emphasized in [4], this elimination method may not only increase the costs, but
also the lower bound of the minimal risk.

4 GIS-based Route Planning Method

There are many sources of information that needs to be considered for route planning. The data is either readily available as GIS data, or it can be converted into GIS data. Also, all the information is typically available for the local authority doing the route planning. For instance, information about buildings, occupants, and potential risk groups are typically maintained by city officials for a given city. Depending on the city, such city records may also indicate increased probability of accidents for specific crossroads and junctions. City records also maintain information about the central infrastructure, including water supplies, electricity, and maintenance resources. As for the actual roads, there are many services maintaining digital road data.

In practice, the local authority needs to consider several alternatives and variant scenarios. These "what if" cases provide a valuable insight into the robustness and vulnerability of the transportation network, which is critical when defining a valuation of risks for individual cases. This kind of analysis is not well supported by graph-based approaches, as changing some parameters leads to re-computation of the entire network. As discussed earlier, such a task may be computationally expensive and time consuming. To support the exploration, we shall now present an alternative GIS-based route planning method.

The overall workflow of the method is depicted in Figure 1. In the method, the local authority encodes all individual risk influence factors as separate map layers. Consequently, road maps and residential areas are captured as separate layers. There are also disjoint layers for each neuralgic points, such as hospitals, schools, super markets, and bridges. The layers may also contain some strategic factors, such as temporal traffic congestion. External and diffuse knowledge are encoded as fuzzy rules. Such rules consider, for instance, the risk of an explosion or a chemical dispersion with respect to the location of the incident. Fuzzy rules are then used reproduce a map representation of the diffuse knowledge. All the maps are then summed together cell-wise, to produce a cumulative risk map. The cumulative risk map is then analyzed for transportation routes having the minimal cumulated risk with respect to a transport list.

The heart of the method is the algorithm that takes as an input a map, where each cell indicates the summed risk of all the factors at that location, and produces as an output a list of transportation routes with minimal cumulated risk. For such routes, the total risk is the sum of the risk values of all the individual cells in the route.

The algorithm was implemented as an application of the Distance Transform Path Planning algorithm suggested by Zelinsky et al. [11] for robotics. In short, the algorithm initializes the map with obstacle comfort weights (here summed
<figure><img src="image_2.png" /><figcaption>Fig. 1. The workflow of the GIS-based route planning method.</figcaption></figure>

prepare r as the risk map
prepare c as the initial cumulated risk map
repeat
    compute m, such that for each cell
        $m_{i,j} = \min(c_{i-1,j}, c_{i+1,j}, c_{i,j-1}, c_{i,j+1})$
    recompute c_{i,j} as $\min(r_{i,j}+m_{i,j}, c_{i,j})$
until c does not change

<caption>Fig. 2. Risk cumulation propagation algorithm.</caption>

risk values). It then computes a distance transform on the map with respect to a fixed starting and ending location. The distance transform is practically a function that returns the cumulated comfort weights (here summed risk values) along a chosen path. The algorithm then minimizes the transform function, yielding a set of paths that have the minimal cumulated comfort weights (here summed risk values).

Our implementation of the algorithm by Zelenski et al. [11] has two phases. In the first phase, the risk value cumulation is propagated from the fixed starting location throughout the entire map. The propagation of risk values was implemented as an iterative update, where each cell is updated as the sum of its value and the minimal risk value of its neighboring cells. For the iteration to work, the cumulated risk map was initialized with large values except for the starting point which is initialized with value 0. The propagation algorithm is presented in Figure 2, and the iteration is illustrated in Figure 3. In the second phase, the routes with minimal cumulated risks are computed for a fixed ending point by using the steepest path of decent as in [11].
<figure><img src="image_3.png" /><figcaption>**Fig. 3.** Illustration of risk cumulation propagation; the two top tables show the initial matrices and the rightmost table on last row shows the obtained route with the minimal cumulated risk.</figcaption></figure>

# 5 Case Study

The purpose of this case study is to illustrate how the GIS-based route planning method works. Therefore, we consider here only a simple street map, as shown in Figure 4. In the street map, the risk level of each street cell is initialized to zero.

As the first test, we consider only one layer, which is the population layer. It is created and initialized with a random population density. Thus, the risk cumulation is computed only with respect to the population layer. The starting point is set to be the street cell at the bottom left corner and the ending point is set to be the street cell at the top right corner. The risk cumulation for the population layer is shown in Figure 5. Note that, as the map shows the cumulated risk, the highest risk value is actually found at the ending point from where it decreases towards the starting point. After running the route planning algorithm, the route with the minimal cumulated risk is found, as plotted in Figure 5. The found route goes from the starting point to the ending point as straight as possible. The found route avoids the bottom right corner which has higher risk values.

In the second test, we create a layer with two neuralgic points having diffuse risk values. The layer is associated with transportation of class-1 HAZMAT (explosives), and the neuralgic points represent buildings that could be severely damaged by such materials. The associated risk values, however, do not localized
<figure><img src="image_4.png" /><figcaption>Fig. 4. Street map of the case study.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 5. A population layer showing the cumulated risk and the plotted route with the minimal risk cumulation.</figcaption></figure>

just to these buildings, but also to their surroundings. Therefore, the actual risk value varies depending on the distance between the incident location and the buildings. Because of this, fuzzy logic is used to construct a risk layer that captures the described diffuse knowledge. In the construction, the membership functions for the input variable "distances", as depicted in Figure 6, are used. For instance, if the distance between the incident location and a building is about 400 meters, it is mostly considered to be "intolerable"; however, as indicated in Figure 6, such a distance could also fall into classes "close" and "tolerable" depending on the case. Similarly to the variable "distances", the membership functions for the variable "risk values" are constructed, as shown in Figure 6. By applying these membership functions, we can compute how the risk values spread on the map. The result of such a computation is shown in Figure 7 for a neuralgic point located at coordinates (5,7) having the maximal risk value of 10.

By using the technique described above, we can construct a risk layer for transportation of class-1 HAZMAT with two neuralgic points located at the coordinates (3,5) and (10,9) with highest risk values 50 and 40, respectively. As in the first test, we consider in this second only one layer, which is the layer
<figure><img src="image_6.png" /><figcaption>Fig. 6. Fuzzy membership functions.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 7. Risk values computed using a fuzzy realization of the diffuse knowledge.</figcaption></figure>

for class-1 HAZMAT. The starting and ending points are kept as in the first
test. After computing the risk cumulation for the starting and ending points,
a cumulated risk map is obtained. It is shown in Figure 8. Note that, as the
map shows the cumulated risk, the risk value is at highest at the ending point
and not around the neuralgic points. For the map, the route planning algorithm
yields now a different route than in the first case. The route is plotted in Figure
8. As expected, the route goes along the neuralgic point having the smallest risk
value.

As the last test, we combine the two previously introduced layers by summing
them up. Thus, there is no need for recomputations, as the new map reuses the
earlier computation results. The resulting combined map is shown in Figure 9.
This time, when the route with the minimal cumulated risk is computed, it takes
the same route as for the first test. The randomly generated risk layer for the
population density, although having much smaller values than the layer for the
neuralgic points, is sufficient to redirect the route away from the neuralgic point
with the smallest risk value.

6 Conclusion

In this article we discussed route planning for HAZMAT transportation. It is an
NP hard problem, and as the main contribution, we presented here a GIS-based
<figure><img src="image_8.png" /><figcaption>**Fig. 8.** The risk cumulation map for two neuralgic points and the plotted route with the minimal risk cumulation. The neuralgic points are indicated with stars.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>**Fig. 9.** Risk cumulation with combined layers and the plotted route with the minimal risk cumulation. The neuralgic points are indicated with stars.</figcaption></figure>

route planning method that is complementary to graph-based route planning methods. At the heart of the method is the route planning algorithm that we implemented as an application of the Distance Transform Path Planning algorithm suggested by Zelinsky et al. [11] for robotics

The proposed method exhibits several advantages that are critical for the decision maker. Firstly, each risk factor is encoded as a separate layer, whereby each risk factor and its evaluation can be considered in isolation. Secondly, the decision maker can provide several alternative valuations for the same risk factor, to analyze the overall effect of that specific risk. Thirdly, the method merges for consideration any subset of the risk layers that the decision maker is interested in. This supports the "what if" analysis that is of utmost importance for the decision maker. Fourthly, the risk assessment computation is split into a preprocessing phase and into a path analysis phase, whereby the computational results for an individual risk assessment can be reused. This, in turn, lowers the overall computational costs. Lastly, as the computation is performed on maps, it fully
supports the distribution of the computation among parallel processes. Thus, the
computational complexity can be tackled simply by introducing more parallel
processes working on disjoint portions of the same maps.

The research presented in this article is at early stages. The method is cur-
rently implemented by using MATLAB. For repeated use in varying scenarios, it
has to be wrapped as a computational service. This requires some consideration,
as such a service also requires dataset management along with sufficient data
security measures.

As for the future research, we also plan to study the use of the presented
method for analyzing not only HAZMAT transportation, but also correlation
between traffic infrastructure and occurrences of traffic accidents.

Acknowledgements

Mauno Rönkkö and Mikko Kolehmainen would also like to thank European Re-
gional Development Fund and TEKES for support to continue research in coop-
eration with Amphion Loudspeakers Oy, Genelec Oy, Mediatuotanto Mindcom
Oy, Observis Oy, and Defence Forces Technical Research Centre.

References

1. Erkut, E., Tjandra, S., A., Verter, V.: Hazardous Materials Transportation. Chapter 9, in Barnhart C., Laporte G. (Eds.) Transportation, 14, 539 – 621 Elsevier (2007).

2. United Nations: Recommendations on the Transport of Dangerous Goods. United Nations, 2007.

3. Erkut, E.: Special issue: Hazardous materials transportation - Introduction. Computers and Operations Research 34(5), 1241–1242 (2007).

4. Current, J., Ratick, S.: A Model to assess Risk, Equity and Efficiency in Facility Location and Transportation of Hazardous Materials. Location Science 3(3), 187–201 (1995).

5. Gumus, A., T.: Evaluation of hazardous waste transportation firms by using a two step fuzzy-AHP and TOPSIS methodology. International Journal of Expert Systems with Applications 36, 4067 – 4047 (2009).

6. Kara, B. Y.: Accurate calculation of hazardous materials transport risks. Operations Research Letters 31, 285–292 (2003).

7. Dijkstra, E., W.: A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1, 269–271 (1959).

8. Erkut, E., Alp, O.: Designing a road network for hazardous materials shipments. Computers and Operations Research 34, 1389 – 1405 (2007).

9. Erkut, E., Gzara, F.: Solving the HAZMAT transport network design problem. Computers and Operations Research 35, 2234 – 2247 (2008).

10. Amaldi, E., Bruglieri, M., Fortz, B.: On the Hazmat Transport Network Design Problem. In the proceedings of the International Network Optimization Conference (INOC)2011, LNCS 6701, 327 – 338 (2011).

11. Zelinsky, A., Jarvis, R., A., Byrne, J., C., Yuta, S.: Planning paths of complete coverage of an un structured environment by a mobile robot. In the Proceedings of International Conference on Advanced Robotics, 533 – 538 (1993).