1 Introduction

The production and transportation of hazardous materials (hazmat) plays an important role in industrial development. Although the probability of hazmat transportation accidents is low, the vast majority of transporting hazmat and inadequate supervision by the government causes frequent hazmat transportation accidents, which arouses close national attention in China. At present, the total annual hazmat transport volume reaches about 400 million tons in China. Among them, about 95 % hazmat need to be transported from one place to another and road transportation accounts for approximately 82 % [1].

The hazmat transportation accidents are recognized as low probability-high consequence events and the risk is a significant ingredient which separates hazmat transportation problems from other transportation problems. It is not easy to estimate the risk on each arc exactly, since it depends on many unpredictable factors. There are several elements to influence the risk on each arc, such as human error, weather conditions, transport mode, vehicle type and road conditions involving people living around the road, road intersections, highway ramps and bridges where accidents happen frequently. The risk assessment is a basic research branch in the hazmat transportation research fields, involving qualitative or quantitative risk assessment. The qualitative risk assessment deals with the identification of possible accidents in the absence of data and the quantitative risk assessment uses historical accident frequencies and consequences to calculate the numerical assessment of risks. However, the past empirical data is not very reliable. There is no agreement on accident probabilities and conflicting numbers of edge risk reported by different researchers could induce different results. Furthermore, weather conditions, public perceived risk and hot spots, such as road intersection, highway ramps and bridges, may cause severe unpredictable accidents, and make the risk of road segments uncertain. When the risk changes on the road segments, the prior optimal network might not be an optimal network anymore, then the network lacks of robustness. To design a robust hazmat transportation network is reasonable and necessary.

1.1 The hazardous materials transportation network design problem

At present, most of the literatures on the hazmat transportation focuse on risk assessment, routing and scheduling, and facility location. The Hazardous Materials Transportation Network Design Problem(HTNDP) was first proposed by Kara and Verter (2004)[2] and received more attention recently. This problem assumes that the government can decide which road segments have to be closed to hazmat so as to minimize the overall risk of the shipments, and then the carriers choose the routes on the designated network to minimize their route costs. Government intends to find a sub-graph of the existing road network so that the total route risk selected by the carriers is minimized. A bi-level programming formulation is provided for this network design problem, but it may fail to find a stable solution when there exist multiple minimum cost routes with different risk value selected by the carriers in the follower model, which may result in much higher risk than the government expected. Erkut and Alp (2007) [3] modeled the HTNDP as a Steiner tree problem and formulated the problem as a single level integer programming with the objective of minimizing the total risk. Erkut and Gzara (2008) [4] considered a similar problem to generalize their model to the undirected case. In order to protect the government from the worst case when the problem becomes unstable, they proposed a heuristic algorithm to handle the bi-level model stability. Verter and Kara (2008) [5] provided a single level path-based formulation for the HTNDP, where a set of alternative paths for each hazmat commodity incorporate the carriers’ cost concerns in the government’s risk-reduction decisions. Amaldi and Bruglieri (2011)[6] proved that the HTNDP where a set of arcs can be forbidden is NP-hard even when a single commodity has to be shipped.

1.2 Robust shortest path problems

Soyster [11] first proposed a linear optimization model with uncertain data to construct a feasible solution. A significant step forward for developing a robust optimization theory was taken by Ben-Tal et al. [12] and Bertsimas and Sim [13, 14]. Specifically for discrete optimization problems, Kouvelis and Yu [16] proposed a framework for robust discrete optimization and showed that the robust counterparts of a number of polynomial solvable combinatorial problems are NP-hard. Zielinski [18] showed that the problem of minimizing the maximum regret criterion robust shortest path is NP-hard for directed graphs. Averbakh and Lebedev [19] proved that the problem of minimizing the maximum regret criterion robust shortest path is strongly NP-hard for non-directed graphs. Bertsimas and Sim [13] considered the interval model for cost uncertainty and showed that the problem can be solved by solving at most n + 1 nominal problems.

In particular, a model where an interval of possible values is associated with each arc has been studied [22–24]. The maximum regret criterion robust shortest path problem is defined on a directed graph \(G=(V,A)\) , where \(V\) is a set of vertices, and \(A\) is a set of arcs. A starting vertex \(s\in V\) , and a destination vertex \(t\in V\) are given and an interval \([l_{ij},u_{ij}]\) , with \(0\le l_{ij} \le u_{ij}\), is associated with each arc \((i,j)\in A\).

Montemanni and Gambardella [22] gave the following definitions for the maximum regret criterion robust shortest path problem with interval data.

Definition 1

A scenario r is a realization of arc costs, i.e. a cost \(c_{ij}^{r}\in [l_{ij},u_{ij}]\) is fixed \(\forall (i,j)\in {A}\).

Definition 2

The robust deviation for a path p from s to t in a scenario r is the difference between the cost of p in r and the cost of the shortest path from s to t in scenario r.

Definition 3

A path p from s to t is said to be a robust shortest path if it has the smallest (among all paths from s to t) maximum (among all possible scenarios) robust deviation.

In this paper, we use the maximum regret criterion called the robust deviation in HTNDPUR, and the result is based on the following property, proposed by Karasan et al. [15].

Property 1

Given a path p from s to t, the scenario r which maximizes the robust deviation for p is the one where each arc \((i,j)\) on p has cost \(u_{ij}\) and each arc \((k,h)\) not on p has cost \(l_{kh}\), i.e. \(c_{ij}^{r}=u_{ij}\forall {(i,j)}\in {p}\) and \(c_{kh}^r=l_{kh}\forall {(k,h)}\notin {p}\).

In Fig. 1, an example of an interval graph is given.

Fig. 1
figure 1

Example of an interval graph

Full size image

Figure 2 depicts an example of the scenario induced by path \(p=\{1,3,4\}\) as the robustness cost of \(p\). The robustness cost of \(p\) is in this case \((10+4)-(3+1)=10\).

Fig. 2
figure 2

Scenario induced on the graph of Fig. 1

Full size image

In the robust shortest path problems where uncertain factors on arc values exist, two uncertainty models have been studied, which are the interval model and the discrete model. Many different approaches come from decision theory, multi-criteria analysis and mathematical programming. In decision theory, there are different criterions to model the concept of robustness, in which a solution that optimizes the worst case criterion is called an absolute robust solution and a solution that optimizes the maximum regret criterion is called a robust deviation solution. And another criterion of robustness which consists of normalizing the regret measure called a relative deviation solution [17]. In this work, we apply the minimax regret criterion methodology to deal with the edge risk uncertainty in HTNDP proposed by Kara and Verter (2004).

The paper is organized as follows. In Sect. 2, we present a bi-level network design formulation of the HTNDPUR, and the computational complexity is discussed in Sect. 3. In Sect. 4, we describe the robust heuristic solution procedure which guarantees a feasible and stable solution. In Sect. 5, we test our heuristic algorithm on the highway transportation network for the province of Guangdong, China, which involves 21 nodes and 30 edges. Four different classified hazmat data on this network are considered, including explosive solid product, flammable gas, toxic gas and corrosive substances. In Sect. 6, we provide some conclusions.

2 A bi-level network design formulation

Suppose that a hazmat transportation network is defined on a directed graph \(G=(V,A)\). There are \(n\) nodes where \(V\) is the node set corresponding to road intersections, and \(A\) is the set of arcs corresponding to road segments. There are \(K\) hazmat commodities which need to be transported from their origins \(s(k)\) to destinations \(t(k)\), and each hazmat commodity has its own risk on each arc in the transportation network. Let \(c_{ij}^k\) and \(r_{ij}^k\) be the cost and risk associated with a unit flow of commodity \(k\) transporting on arc \((i,j)\in {A}\) respectively, and \(d_k\) be the corresponding transporting amount. Government intends to find a sub-graph of the existing road network so that the total risk resulting from the carriers route choices is minimized. Each hazmat commodity has its own risk on each arc in the transportation network.

Let \(\underline{r}_{ij}^k\) and \(\overline{r}_{ij}^k\) refer to the interval risk associated with a unit flow of commodity on arc \((i,j)\in {A}\), denoted as \(r_{ij}^k\in [\underline{r}_{ij}^k,\overline{r}_{ij}^k]\) , this interval risk represents the set of possible values for each commodity \(k(k=1,2,3,\dots ,K)\) on arc \((i,j)\in {A}\). Different from the relative deviation criterion, we apply the absolute deviation criterion (minimax regret criterion) to deal with the HTNDPUR. We define the decision variables on the network below.

$$\begin{aligned} x_{ij}^k&= \left\{ \begin{array}{ll} 1 &{} \quad \text {if} \quad \text {arc} \,(i,j) \,\text {is chosen by the commodity} \,k, \\ 0 &{} \quad \text {otherwise.} \end{array}\right. \\ y_{ij}&= \left\{ \begin{array}{ll} 1 &{} \quad \text {if} \quad \text {arc}\, (i,j) \,\text {is available for hazmat transportation}, \\ 0 &{} \quad \text {otherwise}. \end{array}\right. \end{aligned}$$

The bilevel multi-commodity hazmat network design integer formulation is

$$\begin{aligned} \min _{y_{ij}\in {\{0,1\}}}&\sum _{k\in {\{1,\dots ,K\}}}\sum _{(i,j)\in {A}}d_{k}r_{ij}^kx_{ij}^k \end{aligned}$$
(1)
$$\begin{aligned} \mathrm s.\textit{t}. \ \ \ y_{ij} = y_{ji} \ \ \ \qquad \qquad \quad \quad \quad (i,j),(j,i)\in {A} \end{aligned}$$
(2)
$$\begin{aligned}&r_{ij}^k \in [\underline{r}_{ij}^k,\overline{r}_{ij}^k] \end{aligned}$$
(3)
$$\begin{aligned}&x_{ij}^k \in arg \min \sum _{k=1}^K\sum _{(i,j)\in {A}}d_{k}c_{ij}^kx_{ij}^k\end{aligned}$$
(4)
$$\begin{aligned} \mathrm s.\textit{t}. \ \ \ \sum _{i\in {V}}x_{ij}^k - \sum _{i\in {V}}x_{ji}^k&= \left\{ \begin{array}{ll} -1 &{} \hbox { if } \quad j = s(k) \\ 1 &{} \hbox { if } \quad j = t(k) \\ 0 &{} \hbox { otherwise} \end{array}\right. \ \ \ j\in {V},k\in {1,\dots ,K} \end{aligned}$$
(5)
$$\begin{aligned} x_{ij}^k&\le y_{ij} \ \ \ \ \ \ \ (i,j)\in {A}, k\in {1,\dots ,K} \end{aligned}$$
(6)
$$\begin{aligned} x_{ij}^k&\in {\{0,1\}} \ \ \ \ \ \ (i,j)\in {A}, k\in {1,\dots ,K} \end{aligned}$$
(7)

It is worth pointing out that, this formulation differs from the formulation presented in [4] by the constrains (3), which represents the interval risk value. Similar to [4], the objective (1) represents the government minimizing the total risk chosen by the carriers, each commodity of risk can vary in the interval on the arc of the network, while that of the carriers (4) is to minimize the cost. Constraints (2) state that both arcs \((i,j)\) and \((j,i)\) can be traversed in both directions used by any of the shipments. Constraints (5) ensure the flow of commodity \(k\) from its origin to the destination. Constraints (6) ensure that only edges selected by the government can be used by the carriers. Constraints (7) are binary requirements on the variables.

3 Computational complexity

In [6], it was shown that HTNDP is strongly NP-hard. Obviously, the next conclusion is natural.

Lemma 1

The HTNDPUR is strongly NP-hard even for a single commodity.

The natural way to handle NP-hard problems are approximation solutions or FPT algorithms.

Fixed-Parameter Tractable Algorithm (FTP) Let \((I,k)\) be an instance of parameterized problem. An FPT algorithm decides \((I,k)\) in time \(O(f(k)\cdot n^{c}\), where \(f\) is an arbitrary computable function that only depends on \(k\) and \(c\) is a constant. We often use the notation \(O^{*}(f(k))\) to suppress the polynomial term.

However, the following result can be proved.

Theorem 1

The HTNDP does not admit any polynomial time approximation (regardless of its approximation factor), unless P = NP.

Proof

The HTNDP is a minimization problem, then the result in [6] implies that deciding whether \(OPT=0\) is NP-hard. Let \(A\) be any approximation algorithm for HTNDP with factor \(\alpha \). By definition \(A\) returns an approximation solution value \(APP\), with \(APP\le \alpha \times OPT\).

When \(OPT=0\), clearly \(APP\) must also satisfy \(APP=0\). In other words, \(A\) would be able to solve the instance in[6] in polynomial time. This, however, contradicts with the corresponding NP-hard result, unless \(P=NP\). \(\square \)

Theorem 2

The HTNDP does not admit any FPT algorithm, unless P = NP.

Proof

The HTNDP is a minimization problem, then the result in [6] implies that deciding whether \(OPT=0\) is NP-hard. Let \(B\) be any algorithm for \(FPT\) which runs in \(O(f(k)\cdot n^{c})\) time. When \(OPT=k=0\), \(B\) solves HTNDP in \(O(f(0)\cdot n^{c})=O(n^c)\) time. In other words, \(B\) would be able to solve the instance in [6] in polynomial time. Again, it contradicts with the corresponding NP-hard result, unless \(P=NP\). \(\square \)

From \(Lemma 1\), we know that the HTNDPUR is also NP-hard problem. Similar to the HTNDP, the following conclusion can be proved.

Corollary 1

The HTNDPUR does not admit any approximation, neither any FPT algorithm, unless P = NP,

4 A robust heuristic approach

In this section, we will adopt a robust heuristic algorithm that always finds a solution of the HTNDPUR with stability and robustness. The main idea of the heristc algorithm is as follows.

Firstly, we employ the minimax regret criterion to find the robust risk shortest path for each commodity \(k\), and then we construct the subnetwork formed by \(k\) robust risk shortest routes. Let the resulting network be \(G\) with an associated risk value of \(R\), which is the sum of minimax regret risk value of each commodity \(k\).

Secondly, the carriers choose their own path with an objective of minimum cost on \(G\), where each path corresponds to a minimax regret risk value, and then the carriers reconstruct a new subnetwork \(G'\) formed by minimum cost routes. When there are multiple minimum cost routes with different minimax regret risk value for each commodity, we always use the maximum value of total minimax regret risk value of each commodity, with an associated total risk value of \(R_{max}\). If \(R=R_{max}\), then a solution is obtained. Otherwise, there is at least one commodity \(k\) using a different path designated by the government under the robust minimum risk objective.

Finally, in order to eliminate the difference of the total risk value between \(G\) and \(G'\), we remove the maximum upper bound of interval risk arc not used by the government solution but used in the solution of the carriers for some commodity \(k\). The algorithm does this iteratively on the residual network until it stops, and then we can obtain a robust stable subnetwork.

One of the challenges of designing a hazmat transportation network is the use of common road links for different shipments. Apparently, the number of links used for multiple shipments will have to increase as the number of shipments increases. According to the above character, we present the following selection rule: The common links for different shipments will be removed from the original network, and it guarantees that after a number of iterations, the algorithm stops with a feasible stable solution for the residual network. Figure 3 describes above rule as follows.

Fig. 3
figure 3

An example demonstrating how to eliminate the arc(\(v_1,u_1\))

Full size image

In Fig. 3, we assume that the commodity 1 adopts the route \(s_1\)-\(v_1\)-\(u_1\)-\(t_1\) which is designated by government. But the commodity 2 chooses the route \(s_2\)-\(v_2\)-\(v_1\)-\(u_1\)-\(u_2\)-\(t_2\) instead of the designated route \(s_2\)-\(v_2\)-\(u_2\)-\(t_2\). If the upper bound of the interval risk value of the commodity \(2\) on arc (\(v_1\),\(u_1\)) is too high, we should eliminate arc (\(v_1\),\(u_1\)) from the selection rule. The commodity 1 has to use the route \(s_1\)-\(v_1\)-\(v_2\)-\(u_2\)-\(u_1\)-\(t_1\) alternatively, and that means, node \(v_1\) and \(u_1\) cannot be unconnected directly for lack of arc (\(v_1\),\(u_1\)). The above principle is alternately applied to the transportation network, finally there must exist at least one route which connects the origin node to the destination node.

The detailed steps of designing a robust network algorithm are given as follows.

Initialization \(t=0\), \(G^t=G\).

Iteration \(t\):

Step 1: Solve \(K\) robust-risk shortest path problem on \(G^t\)

$$\begin{aligned} min \sum _{(i,j)\in {A(G^t)}}d_{k}r_{ij}^kx_{ij}^k&\end{aligned}$$
(8)
$$\begin{aligned} \mathrm s.t. \ \ \ \sum _{i\in {V}}x_{ij}^k - \sum _{i\in {V}}x_{ji}^k&= \left\{ \begin{matrix} -1 \quad &{} \hbox { if } \quad j = s(k) \\ 1 \quad &{} \hbox { if } \quad j = t(k) \\ 0 \quad &{} \hbox { otherwise } \\ \end{matrix}\right. \end{aligned}$$
(9)
$$\begin{aligned}&\displaystyle r_{ij}^k \in [\underline{r}_{ij}^k,\overline{r}_{ij}^k] \end{aligned}$$
(10)
$$\begin{aligned}&\displaystyle x_{ij}^k \in {\{0,1\}} \ \ \ \ \ \ (i,j)\in {A} \end{aligned}$$
(11)

To handle the constrains (10), which is the interval risk value, we use the minimax regret criterion to find the robust risk shortest path for each commodity \(k\), and then we obtain the subnetwork of the original \(G^t\) formed by \(k\) risk robust shortest routes. According to the property 1, we establish the mixed integer programming formulation to solve \(K\) robust-risk shortest path problems on \(G^t\) as follows.

$$\begin{aligned} min \sum _{(i,j)\in {A(G^t)}}d_k\overline{r}_{ij}^kx_{ij}^k-d_kx_n^k&\end{aligned}$$
(12)
$$\begin{aligned} \hbox {s.t.} \quad \sum _{i\in {V}}x_{ij}^k-\sum _{i\in {V}}x_{ji}^k&= \left\{ \begin{matrix} -1 &{} \hbox { if } \quad j = s(k) &{}\\ 1 &{} \hbox { if } \quad j = t(k) &{} \quad j\in {V} \\ 0 &{} \hbox {otherwise } &{} \end{matrix}\right. \end{aligned}$$
(13)
$$\begin{aligned}&\displaystyle x_j^k \le {x}_i^k+\underline{r}_{ij}^k+(\overline{r}_{ij}^k-\underline{r}_{ij}^k)x_{ij}^k \ \ \ \quad (i,j)\in {A} \end{aligned}$$
(14)
$$\begin{aligned}&\displaystyle x_{s(k)} = 0 \end{aligned}$$
(15)
$$\begin{aligned}&\displaystyle x_{ij}^k \in \{0,1\} \quad \quad (i,j)\in {A} \end{aligned}$$
(16)
$$\begin{aligned}&\displaystyle x_j^k \ge 0 \quad \quad j\in {V} \end{aligned}$$
(17)

Let \(R_k^t\) represent the corresponding minimal risk value for commodity \(k\), and \(R^t=\sum _{k\in \{1,\ldots ,K\}}\) \(R_k^t\) represents the total optimal risk for network \(G^t\).

Step 2: The carriers select the minimum cost routes on \(G^t\), and the total risk of \(G^t\) depends on the routes chosen by the carriers. If there exist multiple routes with the same cost but different minimax regret risk value, we sort the total minimax regret risk value as \(<R_{min}^t,\dots ,R_i^t,\dots ,R_{max}^t>\).

Solve \(K\) minimum-cost path problems on \(G^t\).

$$\begin{aligned}&\min \sum _{(i,j)\in {G^t}}d_{k}c_{ij}^kx_{ij}^k \end{aligned}$$
(18)
$$\begin{aligned}&\qquad \qquad s.t. \ \ \ \sum _{i\in {V}}x_{ij}^k-\sum _{i\in {V}}x_{ji}^k = \left\{ \begin{matrix} -1 \quad &{} \hbox { if j=s(k) } &{}\\ 1 \quad &{} \hbox { if j=t(k) } &{} j\in {V}\\ 0 \quad &{} \hbox {otherwise} &{} \end{matrix}\right. \end{aligned}$$
(19)
$$\begin{aligned}&\qquad \qquad x_{ij}^k \in \{0,1\} \ \ \ (i,j)\in {A} \end{aligned}$$
(20)

Step 3: If \(\frac{R_{max}^t-R^t}{R^t} \le \varDelta \), then a heuristic solution of a robust network is determined by \(G^t\), otherwise \(G^t\)is not a stable network. Go to Step 4.

Step 4: We remove the maximum upper bound of interval risk arc from the routes in \(R_{max}^t\) that is not used in the solution of the government but used in the solution of the carriers for some commodity \(k\). Let \((i,j)\) be an arc found according to the selection rule, which remove arcs \((i,j)\) and \((j,i)\) from the network, update \(t=t+1\), \(G^{t+1}=G^t-{\{(i,j),(j,i)\}}\).

Step 5: Go to step 1.

figure a

Remark:

In step 3, \(\varDelta =0\) implies that the subnetwork is the same with original network. If \(\varDelta \) is a very small positive value, it indicates that the carriers choose the routes which are different from the arcs designated by the government. Obviously, \(\varDelta \) depends on the routes chosen by the government and the carriers respectively. If there are multiple minimum cost solutions with different associated minimax regret risk values, we use the maximum sum of the total risk \(R_{max}\) to check the stable condition. The inequality in step 3 always helps us find a stable solution.

5 Application on guangdong province

In this section, we test the above algorithm on the network of Guangdong province, China, which has 21 nodes and 30 edges. We adopt four different classified hazmat data on this network, including explosive solid product, flammable gas, toxic gas and corrosive substances. We first describe the problem data in detail, and then give the numerical analysis, and finally some interesting findings are discussed.

5.1 The problem data

The primary source of our data is from Statistics China, State Administration of Work Safety and Ministry of Transportation of the Peoples Republic of China, respectively. The data contains actual distance between two connecting nodes, the population exposure around the edges, the locations where potential high risk exist such as buildings, bridges and road intersections and population concentration points, such as schools, factories and commercial centers, etc. Our research focuses on shipments of explosive solid product, flammable gas, toxic gas and corrosive substances, these four materials account for about 67 % of all the hazmat transported through Guangdong highways. The Guangdong highway system is composed of China-highway (Gao Su Gong Lu) and national highways (Guo Dao), contains 21 vertices and 31 edges, as depicted in Fig. 4. In order to see the original network directly, we simply draw the routes between each two nodes with straight line in right side of Fig. 4.

Fig. 4
figure 4

The highway system of Guangdong province in China

Full size image

According to the 2010 population census, our model represents the spatial distribution of 93.87 million people, which covers 90 % of the total population of Guangdong province. The data set includes the frequency of four hazmat in the Guangdong highway system, as depicted in Table 1.

Table 1 The frequency of four hazmat in the Guangdong highway system
Full size table

We assume that each truck is fully loaded with up to 8 tons and can transport the same kind of hazardous material. Because of the scale of the network of Guangdong highway system, we set the number of origin-destination pairs \(K=4, 8, 12, 16\). For each value of \(K\), we generate 4 random instances and fix the number of distinct origins and distinct destinations, as depicted in Table 2. The \(K\) different kinds of hazmat transporting from their distinct origins to their distinct destinations are generated randomly. Each edge transportation risk is computed by multiplying the probability of an undesirable event by the population figure within 1,600 meters of the edges and the actual road distance between two nodes. The transportation cost is given by the actual distance for each kind of commodity, i.e., each kind of commodity has the same cost value on the same arc of network. Based on the deterministic risk on each arc for each kind of commodity, we make a full consideration of detailed factors which may cause high consequence in accidents to give an interval risk for each commodity on each arc.

5.2 Numerical analysis

In Table 2, the cities’ names are substituted by the number from 1 to 20 respectively. For example, the number 1 represents Shaoguan.

Table 2 Random instances from origin to destination
Full size table

We perform our test on randomly generated pairs. We investigate the significance of robust network and compare to the deterministic risk network. Table 2 shows the detailed results on the random instances. For example, for 4 commodities originating points \(<\)6,3,16,4\(>\) to destination points \(<\)4,16,17,9\(>\). All tests are performed using the aggregate risk measure and the maximum interval risk upper bound as arc selection rules. The results obtained by the deterministic risk scenario network and interval risk scenario network for the different commodities with instances are described in Table 3. Firstly, we calculate the total risk of the heuristic solution network on the deterministic bi-level model, and then calculate the total risk when the risk changes on arcs. Secondly, we obtain a robust network, use the same deterministic risk on each arc to calculate the total risk on the robust network, and then use the same changing risk value on the robust network. The deterministic risk of each arc for each commodity belongs to the interval risk of each commodity on each arc.

Table 3 Deterministic and interval risk scenario network for the different commodities with instances
Full size table

In Table 3, the first column indicates the number of commodities \(K\), the second column identifies the instance generated for each value of \(K\), the third column is devoted to analyze the behavior of the total risk of network under deterministic risk, and the fourth column presents the total risk under changed arc risk. The fifth column reports the total risk of the robust network using the same arc risk in the first column. The sixth column indicates the total risk of robust network using the same changing arc risks in the second column. The seventh column indicates the arcs whose risk value is changed. The eighth column shows the arc risk value before changing, while the ninth column shows the arc risk value after changing. The tenth column of \([\underline{r}_{ij},\overline{r}_{ij}]_{(k)}\) shows the commodity \(k\) interval risk on arc \((i,j)\), \(k=Null\) indicates no transport on that corresponding arc \((i,j)\).

This section shows the computational results achieved by the deterministic risk hazmat transportation network and the robust hazmat transportation network. We can see from the Table 3, the robust heuristic finds good quality solutions, especially when the risk changes on the network comparing to the deterministic solution method. The robust network always gives a robustness and stable solution and always avoids the arcs to have a higher upper bound of the interval risk. Because of the total risk of the resulting transport network is decided by the carriers’ route choices, the routes selected by carriers in deterministic network and robust network have four different cases, as depicted in Table 4.

Table 4 The arc risk change on the network
Full size table

Case I : If some arcs’ risk change in the deterministic network but not in the robust network, the change increases on the deterministic network and has no influence to the robust network. For example, in 4{1,2,3}, 8{1,2,4}, 12{1},16{1}. Because the robust network does avoid selecting the routes with a high potential changing risk, as shown in 4{1,2,3}, when some commodity’s interval risk upper bound is not that high, the robust network may select this link, as shown in 4{4}. So when commodity 1’s risk changes on arc (2,4), the same increase occurs to the robust network. But the changing level is not high.

Case II : If some arcs’ risk change in the robust network but not in the deterministic network, the change increase on the robust network and has no influence on the deterministic network. But the margin of the changing risk is not high. For example, in 8{4}, 16{3}.

Case III: If some common arcs’ risk change, which are both selected by carriers in the deterministic and robust network, and then the same additon occurs in both deterministic and robust network. For example, in 4{6},8{3},12{3},16{2,4}.

Case IV : \(\varDelta >0\) in step 3 indicates the government allows carriers to choose some links which are not exactly the links the government designated for some commodities. So some arcs’ risk change from the external factors in the network, but they are not selected by carriers, so have no influence to both the deterministic network and the robust network. For example, in 8{2},12{2,4}. When \(\varDelta =0\), the Case IV does not happen.

We find that if the margin of the interval risk of each commodity on each arc is not that high, the deterministic network and the robust network are almost the same.

Generally speaking, the robust interval scenario network performs not too bad compared with the deterministic scenario network under deterministic risk on each arc for each commodity. But it performs really better when the risk changes since the robust interval scenario network avoids selecting the potentially high risk arcs.

6 Concluding remarks

In this paper, we prove that the HTNDP under edge risk uncertainty does not admit any approximation, neither any FPT algorithm, unless P = NP. We present a bi-level formulation for the HTNDPUR and design a simple heuristic algorithm. It shows that the heuristic algorithm can give a robustness and stable solution, and always avoid the arcs with higher interval risk upper bound. When some of the common links for different shipments are removed from original network, we guarantee that after a number of iterations the algorithm stops with a feasible stable solution for the residual network.

In order to evaluate the effectiveness of the proposed model and algorithm, we concentrate our analysis on a real-world case study. We consider the road network of the Guangdong province in China which contains 21 vertices and 31 edges. Compared to the solutions of the bi-level model with the results coming from two scenarios, called deterministic risk scenario network and interval risk scenario network respectively, we find that the robust network performs not bad compared to the deterministic network under deterministic risk on each arc for each commodity. But it performs really better when the risk changes since the robust network avoid selecting the potential high risk arcs. The robust optimization for hazmat transportation network design is more reasonable and performed good quality in robustness.

The solutions depend on the input data, in particular, which include the origin-destination flows, the topology of the original road network, the spatial distribution of population centers, the location of the origin-destination pairs, and the type of hazmat being shipped. In general but not absolutely, we find that when the number of hazmat grows, the iteration times and CPU requirement are increasing. Due to the scale of our original road network, the heuristic algorithm performs only several times to obtain a stable network, which fully depends on the input data of the original network.