1 Introduction

Risk assessment and hazmat shipment planning are two main fields widely researched in hazmat transportation. Researchers assess the risk by modeling probability distribution over given areas regarding the commodities, the transport modality (Abkowitz et al. 1984) and the environmental conditions (Patel and Horowitz 1994). Hazmat shipment planning involves two primary routing problems: the local route planning—the selection among alternative paths for a single-trip shipment of a single hazmat type from an origin to a destination, and the global route planning—the planning of multiple trips among multiple origin-destination pairs (O-D pairs) to mitigate and equalize the social risk of the whole road network. The former is mostly of interest to carriers, while the latter is usually the main concern of government and environmentalists. In this paper, we focus on the modeling of the risk of hazmat transportation and the minimization of the risk brought by a single-trip hazmat shipment.

Hazmat accidents are featured by their low probability and high consequence (LPHC). It is estimated that average 10−6 accidents occur on a trip along each kilometer (Harwood et al. 1993), which means it is hard for analysts to collect sufficient and precise data, or to assess the long-term environmental impact. The transit phase of hazmat transportation results in 3,885 accidents/incidents with damages costing $104,674,760 in 2011 (US Department of Transportation Pipeline and Materials Safety Administration 2012). Shifts of the road conditions and population over time further increase the uncertainty of the historical data sources of hazmat accidents. Hazmat accidents can, however, result in disastrous damage to the population and the environment. Decision-makers desire to consider both objective and subjective factors to make flexible route choices so that various uncertainty can be accommodated within the same decision-making framework. This requires flexible decision-making based on the current risk preference that provides the motivation for the work presented in this paper. Our model generates a route choice such that the probability of experiencing a greater risk than a specified cutoff value is less than a certain threshold. In order to obtain an appropriate formulation for our model, we utilize the Value-at-Risk (VaR) concept.

VaR is a powerful risk measurement tool that is widely applied in finance mathematics and financial risk management. It emerged in 1993 (McNeil et al. 2005), and has been established in the past 20 years as a standard benchmark to measure the potential loss in financial risk management given a certain confidence level (Linsmeier and Pearson 1996).

Many methodologies have been developed regarding VaR applications in finance and economics, such as historic, parametric or Monte Carlo methods. Though these methodologies are largely different from each other (Beder 1995), they share the same procedure to calculate VaR by estimating the combination and distribution of portfolio returns and computing the VaR value of the portfolio. Another common basis is the assumption of the leptokurtic financial return distribution, negatively skewed equity returns, and quasi-stable market volatilities (Mandelbrot 1963; Fama 1965). Variants of VaR models are designed to address various market units. The Component Value at Risk is proposed by Hallerbach and Menkveld (2004) based on the conventional VaR measure to compute the risk exposure of the breaking down of a firm to different market risks. The Conditional Value at Risk (Larsen et al. 2001) measures the possible losses in the tail of the distribution, to reduce the problem caused by the excessive risk measured in VaR. Cashflow at Risk (CFaR) (Stein et al. 2001) extends the measure to cover metrics other than value. In general, these methodologies are dependent on the distribution assumption of portfolio returns, given a certain confidence level, rather than a point estimate that may never actually occur.

In the last decade, VaR has ever begun to find acceptance in non-financial applications (Offutt et al. 2006) applied VaR and a distortion function to measure the risk of catastrophic events with low probability from shortfalls of military or security capabilities. In industrial and service areas, VaR is witnessed with its utilization everywhere. The former includes agricultural industry (Manfredo and Leuthold 1998) and power industry (Shebl and Berleant 2002). The latter involves IT services (Kauffman and Sougstad 2007, 2008) and supply chain planning (Sanders and Manfredo 2002; Lu et al. 2010). Additionally many large enterprises apply VaR in enterprise risk management system to qualify and derive aggregate risks (Nocco and Stulz 2006). As far as transportation application, some literatures discuss risk management in transportation investment (dePalma et al. 2012; Lu et al. 2010), market risk in freight rates (Angelidis and Skiadopoulos 2008), or shipping credit risk (Alizadeh and Nomikos 2009). But those models mainly focus on the risk or loss brought by financial or economic activities. Take Ju et al. (2002) as example, he introduced a VaR model for the revenue management of seat rates in civil aviation transportation, which belongs to the risk of operations. So far there is neither application of VaR in risk measurement or risk management pertaining to shipments or commodities yet, nor research has ever been done on measuring and controlling of consequence or loss caused by commodities to the neighborhood once accidents occur during the shipment.

Applying the VaR concept to hazmat routing allows us to measure a cut-off value for the risk of hazmat shipments. However, it’s helpful to keep in mind the differences between the model we proposed and those in finance. First of all, the VaR models in finance focus on the profit loss measurement faced by the investment and, the measurement units of both the investment and the measurement object are the same; our model focuses on the risk measurement of taking a certain route. The input is a candidate route, and risk brought by this route is the object to be measured. Because of this inconsistency of the measurement units, we could not directly apply the classic risk measurement methods of finance VaR. Secondly, the calculation of a path’s VaR value and the algorithm to solve the VaR model for hazmat transport risk is quite different from, and more complicated than those methodologies to solve VaR models in financial and economical problems.

In the next section, we collect nine popular risk models in hazmat transport. Section 3 presents the mathematical formulation of the VaR model for hazmat transport and develops several properties of the model. Section 4 develops an exact solution procedure to solve single-trip hazmat shipment problems. A numerical example is presented in Sect. 5 to compare the VaR model with the nine common risk models discussed in our literature review. In Sect. 6, we present our computational experience with a scenario around the Albany district of New York state. In the end, Sect. 7 concludes the meaning of our model to decision makers and discusses our solution method and future research suggestions.

2 Review of models to evaluate risk of hazardous material transportation

As stated earlier, the route planning element of hazmat transportation problems can be categorized into two groups: local and global. From the carrier’s perspective, a single-shipment hazmat routing problem can be classified as a local route planning problem. But governors care more about the entire road network, which belongs to the global route planning problem, mitigating the accumulative risk brought by multiple shipments between different O-D pairs. Literature on the subject proposes the formulation of the risk evaluation function of a hazmat shipment from different perspectives.

A transportation network can be defined as \(G = (\mathcal{N},\mathcal {A})\), consisting of a node set \(\mathcal{N}\) to represent the road interactions, and a link set \(\mathcal{A}\) to represent the road segments. For each link \((i,j) \in\mathcal{A}\), there are two attributes, accident probability p ij and accident consequence C ij . Table 1 summarizes the mathematical notation used in this paper.

Table 1 Mathematical notation table
Full size table

Suppose a path l consists of an ordered set of links \(\mathcal{A}^{l} = \{(i_{k},j_{k})|i,j \in\mathcal{N}, k = 1,2,\ldots, m^{l}\}\) where (i k ,j k ) represents the k-th link in path l; the risk that this path generates can be measured using different kinds of indicators. It can be measured by single or multiple attributes, and formulated with additive or productive objective functions according to the definition of the problem and the assumption of the model.

Alp (1995) proposed a Traditional Risk (TR) model to minimize the expected value of the consequence of a hazmat vehicle traveling along path l:

(1)

which assumes that the shipment terminates once an accident happens on a link (i,j). Using this objective, Alp (1995) formulated the choice of the best route as a non-linear binary integer program. Furthermore, (1) can be approximated as an additive function and, further, a tractable shortest path problem formulation (Erkut and Verter 1998). According to North American data on hazmat transportation accident statistics, accident probabilities are generally extremely small, usually in the range of 10−8 and 10−6 per mile traveled (Abkowitz and Cheng 1988), which means that . Consequently, (1) can be approximated as follows (Jin and Batta 1997):

$$ R^{l}= \sum_{(i,j)\in\mathcal{A}^l} p_{ij}C_{ij} $$
(2)

The approximation (2) is easier to optimize than the function (1), with the resultant problem a shortest path problem with the cost of traversing a link (i,j) being set to the value p ij C ij .

Several other models have been developed by focusing on two link attributes. The Incident Probability (IP) model (Saccomanno and Chan 1985) and the Population Exposure (PE) model (ReVelle et al. 1991) can be viewed as two extreme cases of the Traditional Risk model. The former focuses on reducing the accident probability, and the latter focuses on the total consequence on the impacted region, measuring the consequence by how many people are exposed to risks during a transport activity. A similar model is the Perceived Risk (PR) model (Abkowitz et al. 1992), which uses alternative criteria and criteria weighting for route selection to balance safety and operating efficiency. A noticeable drawback of the TR model is its risk-neutral attitude, which might not appropriately reflect the public attitude towards hazmat transportation. The Perceived Risk model has taken this concern into consideration and adds a weight parameter on consequences to reflect the public preference on the risk. Both Traditional Risk model and Perceived Risk model can be viewed as single-attribute models though both of them contain two attributes probability and consequence. The two attributes have been preprocessed into a replaced risk attribute defined on each edge.

These four models are all single-attribute models with an additive objective function. In contrast with these four models, the Conditional Risk (CR) model is a multiplicative multi-attribute model with two attributes: expected risk and accident probability (Sivakumar et al. 1993a, 1993b, 1995). This model evaluates the expected consequence conditional on the occurrence of the first accident and it is suggested for the case of a necessary suspension of a path between an O-D pair after a catastrophic accident.

Erkut and Ingolfsson (2000) discuss three more catastrophe-avoidance modeling methods for hazmat transportation. The first model is the Maximum Risk (MM) model, which tries to avoid catastrophes by using a minimax objective instead of the minisum objective in the Traditional Risk model (i.e., its focus is to minimize the population exposure that is at risk on any link along the path rather than that on the entire trip). A similar maximin way to define risk is called a maximum capacity path problem, which is introduced in Pollack (1960). The Maximum Risk model measures the extensity of the tail of the consequence distribution. The second model, the Mean-Variance (MV) model, is widely used by financial analysts and researchers as the quantitative tradeoffs between return of an investment portfolio and the corresponding risk brought by it. Borrowing the term variance, this model assumes that the link attributes are stochastic and tries to find paths with minimal means and variances. The third model applies utility theory on hazmat transportation to model the risk problem and develops a Disutility (DU) model in the form of U(C)=exp(λC) where λ>0. This function assumes that the (i+1)-st life lost is more costly than the i-th life lost, for all i.

These models assume that the risk parameters, both the link accident probabilities and consequences, are already known. The Mean-Variance model includes the variances of those parameters in the model to simulate the stochastic risk attribute but assumes that the variances are already known. However, there may be some situations where no accident data is available at all, such as on a newly developed road. To address such situations, Bell (2007) proposes a mixed-route model (MM2) under completely uncertain accident probability. It aims to reduce the maximum risk by sharing shipments between routes. As an output, it generates the potential link usage probabilities and link accident probabilities utilizing game theory, assuming usage probabilities and accident probabilities are two non-cooperative and zero-sum players in the mixed strategy Nash equilibrium game.

Table 2 summarizes the risk evaluation models in our literature review. The first six models—TR, PE, IP, PR, MV and DU—can all be reduced to a shortest path problem with additive link attributes. The seventh model, MM, can be handled with different variant algorithms based upon the shortest path algorithms (Erkut and Ingolfsson 2000), while the MM2 model from Bell (2007) is basically a mixed route MM problem and can be converted to an additive linear program. The last risk model in our literature review, CR, is the most complex model to optimize due to its non-additive objective function.

Table 2 Classic path risk evaluation models
Full size table

Having discussed their properties, let us discuss the validity of these models on the application of the hazmat transport problem. The TR model has been criticized as inappropriate for hazmat transportation due to its risk-neutral attitude. In hazmat transportation, as we will see in Eq. (6), the distribution of accident consequence has a large probability for zero and very small probabilities for large consequences. Therefore the risk-neutral model puts too much weights in ‘zero’ consequence. Both the PE and IP models take only one parameter into consideration and might generate a biased output. The PR model has considered the issue of risk aversion and added a weight parameter q on the link consequence C ij , aiming to direct the shipment to those road segments of less populated areas so as to reduce the consequences caused by an accident. However, it cannot truly reflect the risk preference by simply adjusting the risk weight q on consequences. Besides, there is no specific mechanism as far how to select this weight parameter, and there is no obvious pattern to reflect the relationship between q and optimal solution. The same issue occurs in the DU model, which also measures the catastrophe aversion with a constant k>0. By contrast, the MV model tries to simulate the stochastic risk attribute by involving both the mean and variance of the risk parameters into the model. But it assumes that those means and variances are already known, which depend on large quantities of reliable and consistent data. However, since hazmat risk is a low-probability event, the data collection is usually a long-period effort, and the collected data are usually inconsistent because the road situation and population structure are inevitably subject to change. It is appropriate to apply the MM method when accident probabilities are unknown. But this method is too pessimistic, only taking an avoidance measure when accidents are very likely to occur. Bell assumes that the accident probability is completely uncertain and focuses on estimating the link accident probabilities with mixed routing strategies. It is quite a novel idea and is highly applicable in the situation when there is no reference to the accident probability, such as a newly constructed road segment. From another perspective, the CR model points out the necessity of reevaluating the routing policy after a catastrophic accident. Because this model is multi-attribute and has a multiplicative objective function, the problem takes much more effort to solve in comparison with the other models.

As Table 2 illustrates, different researchers quantify hazmat transport risk from different perspectives. These models focus on different scenarios of the hazmat transport problem. But they share a common objective—to find an optimal route for the hazmat shipment to maximally reduce its impact on society. Generally speaking, those models can be characterized using the following six dimensions of problem definition and formulation:

  1. 1.

    Probability-known or probability-unknown problem. Most classic models assume that the accident probability has been determined according to the historical statistics. However, recently, more and more researchers have recognized the deficiency of this assumption because of the difficulty to obtain accurate hazmat accident data. Some researchers like Bell (2007) began to work on the situation when accident probabilities are completely unknown.

  2. 2.

    Single-attribute or multiple-attribute model. Researchers usually express the real-life problem in mathematical models with a limited number of factors and study the effect of single factor to the model objective. Models with more factors are usually more realistic but more complicated and difficult to solve. TR, IP and PE models tend to research hazmat problems of single risk attributes, i.e., accident probability or consequence or expected value of consequence. CR and MM2 consider multiple attributes that affect the decision of route choice.

  3. 3.

    Single-route or mixed-route strategy. Most classic models in our current literature aims to generate a single optimal route. PR and DU attempt to adjust the “perceived” consequences via a weight parameter q or k. By applying a different strategy, MM2 generates solutions of mixed route.

  4. 4.

    Risk-neutral or risk-averse attitude. Different models reflect the different risk preferences of decision makers toward the risk evaluation. For example, TR is a risk-neutral decision model. But because hazmat accidents cause severe consequences, decision makers usually tend to be risk-averse. Such kinds of models include MV, MM, DU and CR.

  5. 5.

    Minisum or minimax objective. According to the model objectives, the hazmat problems can be expressed with different forms of mathematical formulations. Generally speaking, the classic hazmat models in our literature can be summarized into two kinds, minisum or minimax problem.

  6. 6.

    Additive or non-additive objective function. TR, IP and PE models consider only single risk factors and have additive objective functions. PR, MV, MM and DU models have more complicated expressions of hazmat risk, but they can be preprocessed into determined single parameters. All those models can be converted into shortest path problem and solved with corresponding algorithms. But because CR has multiple attributes considered and own multiplicative objective function, it is more complicated to solve than other models.

Each of those models evaluates risk values from different aspects. But most of them rely greatly on the historical data sources of one or two risk parameters—probability and consequence—and often lead to the recommendation of a single route. However, in this paper, we prove that none of the models in Table 2 is absolutely valid under all confidence levels. When confidence level α is sufficiently small, each of above models is valid within a certain confidence level. Especially when α is sufficiently large (close to 1), MM model is valid more than any others. According to our analysis in later chapters, the valid confidence level of each model is associated with its probability of bringing the shipment safely to the target node. However, there are always certain confidence intervals that none of these models can guarantee an absolutely safe path for shipment. In that case, none of the models can provide a valid solution. Subsequently, a single-route solution generated by historical data is usually biased and easily criticized due to its lack of scalability and representation for real-time decision making. The purpose of the VaR model is to provide a more flexible and reliable alternative modeling approach for routing a hazmat shipment. Decision makers of different attitudes to risk can choose different routing decisions corresponding to their risk preferences. Again, rather than a single-route output, this is a two-dimensional decision framework with different solutions generated given different confidence levels. But the introduction of the other decision factor α causes the model to be more complicated and difficult to solve. Because the link parameters along a path are not independent from each other, we cannot measure the VaR value of a path by simply summing all the link parameters.

3 Value-at-Risk (VaR) modeling of hazmat transportation

This section aims to formulate a VaR risk model for hazmat transportation. We explain in detail the formulation of the VaR model and analyze its properties.

3.1 VaR definition of hazmat route

In finance and economics, VaR is defined as a threshold value to measure the maximum mark-to-market loss on an investment from normal market risk within a given time horizon and with a pre-set probability level (Jorion 2007).

We consider a single-trip risk optimization problem. Suppose that we are given a hazmat shipment with an origin (O) and a destination (D) in a transportation network \(G = (\mathcal{N},\mathcal{A} )\). This paper proposes a Value-at-Risk (VaR) framework based on a set of alternative paths for this shipment, denoted by \(\mathcal{P}\). Each path \(l \in\mathcal{P}\) stands for a choice to the carrier for routing a certain hazmat between an O-D pair. For a given risk probability level α∈(0,1) and a given path \(l \in\mathcal{P}\), we define the VaR as the minimal level β such that the probability that the risk R l exceeds β is less than or equal to 1−α:

$$ \mathit{VaR}_{\alpha}^{l} = \min \bigl\{ \beta: \Pr\bigl\{R^{l} > \beta\bigr\} \leq1-\alpha \bigr\} $$
(3)

Given a set of candidate paths \(\mathcal{P}\), the corresponding hazmat shipment optimization problem is to solve:

$$ \mathit{VaR}_{\alpha}^{*} = \min \bigl\{ \mathit{VaR}_{\alpha}^{l} : l \in\mathcal{P} \bigr\} $$
(4)

The problem (4) will generate an optimal path with the minimum value-at-risk among all available paths. For instance, we can use α=0.99 for the 99-percent confidence level. Then, VaR is the cutoff risk such that the probability that shipment s experiences a greater risk from the candidate route l is less than 1 percent. Naturally, the lower the VaR value of the candidate l, the more desirable the path is since it brings less “worst-case” risk compared with other routes with the same confidence level α. Here, we can see that VaR model is a multiple-attribute model. The route choice generated by HazMat VaR model depends on both objective and subjective risk factors and preferences. The route choice varies under different confidence levels α∈(0,1).

3.2 Modeling of hazmat VaR problem

There are many ways to measure the extensity of the tail of the consequence distribution. One available measure is the maximum accident consequence along a path l, i.e., \(C_{\max}{(P)} \equiv\max\{C_{ij}: (i,j) \in\mathcal{A}^{l}\}\). In this method, we consider only a kind of hazmat and assume that every accident on link (i,j) has the same accident consequence C ij . While we discuss the accident consequence on each link, our model is general enough to consider any type of consequence as long as it is constant and known. Since this model only measures the situation when the accidents are most likely to happen, it is too pessimistic and does not account for the low probability of accidents.

Suppose we assume a confidence level of the accident probability. On the basis of this probability, we can measure how far the tail of the cutoff risk distribution extends under this confidence level α, i.e., \(C_{\max}{(P)} \equiv\max\{C_{ij}: C_{ij} \leq \mathit{VaR}_{\alpha}, (i,j) \in\mathcal{A}^{l}\}\).

The key to the problem is the derivation of the cutoff risk—VaR, under a given confidence level α. As we analyzed in Sect. 2, a transportation route is composed of a set of ordered links; therefore, the risk parameters, p ij and C ij , are not additive. Jin and Batta (1997) have explained that hazmat shipment can be viewed as a sequence of independent Bernoulli trials. We start by developing some results related to the properties of the VaR model.

Lemma 1

Suppose each path l consists of an ordered set of links \(\mathcal{A}^{l}\) in which each link \((i,j) \in\mathcal{A}^{l}\) has accident probability p ij and consequence C ij . Let \(C^{l}_{(k)}\) denote the k-th smallest value among \(\{C_{ij}: (i,j) \in\mathcal{A}^{l}\}\). Let \(\overline{m}^{l}\) denote the cardinality of the collection \(\mathcal{C}^{l} = \{C^{l}_{(k)}: C^{l}_{(k)} < C^{l}_{(h)}, k < h\}\). Here, \(\overline{m}^{l}\) is not necessarily equal to m l —the size of \(\mathcal{A}^{l}\). Then, we have:

(5)

where α is the confidence level, and \(\pi^{l}_{(k)} = \Pr (R^{l} = C^{l}_{(k)} )\).

Proof

We first note that the risk will have a value from the set \(\{0, C^{l}_{1}, C^{l}_{2}, \ldots, C^{l}_{m^{l}}\}\) with the corresponding probability. In particular, we have:

(6)

Given R l in (6), the cumulative distribution function (CDF) of R l can be derived as follows:

(7)

where \(\pi^{l}_{(k)} = \Pr (R^{l} = C^{l}_{(k)} )\).

Since Pr(R l≤VaR l)>α, and based on the above CDF of R l, we get:

which completes the proof. □

Based on Lemma 1, we can provide a reformulation of the VaR problem. Lemma 1 gives us a set of probability segments: \((0,\alpha^{l}_{1}], (\alpha^{l}_{1}, \alpha^{l}_{2}],\ldots,(\alpha^{l}_{k},\alpha^{l}_{k+1}],\ldots,(\alpha^{l}_{\overline{m}^{l}},1)\), where \(\alpha^{l}_{k}=1-\sum_{i=k}^{\overline{m}^{l}}{\pi^{l}_{(i)}}\). If we let \(\beta^{l}_{\alpha}\) denote the value of the cutoff risk (VaR) and \(\bar{\alpha} \equiv1 - \alpha\), then we get from (5) that \(\beta^{l}_{\alpha} = C^{l}_{(k)}\) if and only if:

$$ \sum_{i=k+1}^{\overline{m}^l}{ \pi^{l}_{(i)}} \leq \bar{\alpha} < \sum _{i=k}^{\overline{m}^l}{\pi^{l}_{(i)}} $$
(8)

Then, from the definition of π l, we have:

(9)
(10)

and consequently, the inequalities in (8) become:

(11)

Thus, the following conclusion can be reached.

Corollary 1

Under the same assumptions of Lemma 1, β l is the solution of the VaR model (3), i.e., \(\beta^{l}_{\alpha}= VaR^{l}_{\alpha}\) if and only if β l satisfies the following two conditions:

Therefore, the original problem (4) is equivalent to solve:

$$ \min_{l}{\beta_{\alpha}^{l}} $$
(12)

subject to:

(13)
(14)

where \(\bar{\alpha} = 1 - \alpha\). The objective of the model (12) is to find a path \(l \in\mathcal{P}\) to minimize the cutoff risk \(\beta^{l}_{\alpha}\) over the trip while keeping the cumulative probabilities of the cutoff risks within a certain threshold \(\bar{\alpha}\).

3.3 Reformulation of hazmat VaR model

Obviously, the hazmat VaR model (12) is unsolvable for exact solutions since the constraints are non-linear. However, we know that the VaR value \(\beta^{*}_{\alpha}\) is located between the smallest and largest link consequences. Supposing we can find \(\beta^{*}_{\alpha } = C^{*}_{(k)}\), then we have the following conclusions:

  1. 1.

    For optimal path l ∗, the sum of the probabilities corresponding to links with link consequences greater than \(\beta^{*}_{\alpha}\) is less than or equal to 1−α.

  2. 2.

    For any other path l t where \(\beta_{\alpha}^{t} > \beta_{\alpha}^{*}\), the sum of the probabilities corresponding to links with link consequences greater than \(\beta^{*}_{\alpha}\) is greater than 1−α.

Let us assume that we have sorted the links of the network G according to the ascending order of the link consequences: \(\mathcal{C} = \{0, C_{(1)}, \ldots, C_{(\bar{m})} :C_{(1)}<C_{(2)}<\cdots<C_{(\bar {m})}\}\). The value of \(\beta^{*}_{\alpha}\) should exist among the set \(\mathcal{C}\). Then, searching from the lowest consequence upwards, we can find the optimal VaR path by repetitively evaluating a least probability model at each consequence level. Furthermore, we convert this problem into a bi-level formulation and solve it with a two-staged solution procedure.

Before we reformulate this problem, we need to do a series of preprocesses. First, given each consequence level β α , we modify the link probabilities according to the corresponding link consequences:

(15)

for all \((i,j) \in\mathcal{A}\). Here, \(\beta_{\alpha} \in\mathcal {C}\). Second, suppose that for consequence level β α , we solve a least probability model with the objective function value f. Then, let us define an indicator function:

(16)

Let x ij be a binary decision variable equal to 1 if link (i,j) is used on the shipment s and 0 otherwise. Given a confidence level α, the VaR model is equivalent to solving the following mathematical program:

(17)

subject to:

(18)
(19)

where:

(20)

The problem (17)–(18) represents the outer problem—a gap closing function. The constraint (18) restricts that the expected maximum cutoff risk β α comes from the sorted consequence set \(\mathcal{C}\). The cumulative probabilities f must be an optimal function value of the inner problem (19). Here, we need to note that the inner problem generates a least accident probability path in which only links with consequences C ij >β α have regular cost while links with consequences C ij ≤β α have zero cost. The modification of \(\overline{p}_{ij}\) ensures that the links with lower consequences than β α are being considered in the route choice with higher priority than others with consequences more than β α . Coming back to the outer problem, we compare the value of f with the set threshold \(\bar{\alpha}\) and then close the gap between f and α gradually until f falls within the set threshold \(\bar{\alpha}\). At this point, we found the desired optimal solution under the given confidence level α. The constraints in the set (20) are flow-balance constraints on the binary variables x ij . Together, they ensure that the solution describes a path from origin (O) to destination (D).

3.4 VaR model properties analysis

We now establish a series of properties for the VaR model with extreme values of α.

Theorem 1

There exists a scalar α min such that \(\mathit{VaR}_{\alpha}^{*} = 0 \ \mbox{\textit{for all} } \alpha\in(0, \alpha_{\min}]\).

Proof

First, we have observed that for each path \(l \in\mathcal{P}\), there exists a scalar α l such that \(\mathit{VaR}_{\alpha}^{l} = 0 \ \forall\alpha\in(0,\alpha^{l}]\). To show this, let \(\alpha^{l} = 1 - \sum_{i=1}^{m^{l}}{\pi^{l}_{(i)}}\) in Lemma 1. It is obvious that \(\mathit{VaR}_{\alpha}^{l} = 0 \ \forall\alpha\in (0, \alpha^{l}]\). Therefore, for all \(l \in\mathcal{P}\), there exists a scalar α l such that \(\mathit{VaR}_{\alpha}^{l} =\nobreak 0\) ∀α∈(0,α l]. Let \(\alpha_{\min} = \min_{l \in\mathcal{P}}{\alpha^{l}}\). Then, we can see \(\mathit{VaR}_{\alpha}^{l} = 0 \ \forall\alpha\in(0, \alpha_{\min}], \ \forall l \in \mathcal{P}\). Therefore, \(\mathit{VaR}_{\alpha}^{*} = \min_{l \in\mathcal {P}}{\mathit{VaR}_{\alpha}^{l} = 0}, \ \forall\alpha\in(0, \alpha_{\min }]\). The theorem follows. □

Theorem 1 illustrates that when α is very small, the VaR values at all paths are zero. Therefore, in this case, one may choose the path based on another criterion such as minimum transportation cost.

Theorem 2

There exists a scalar \(\alpha^{\mathit{MM}}_{\max}\), such that \(l_{(\alpha -\mathit{VaR})}^{*} \equiv l_{\mathit{MM}}^{*} \ \mbox{\textit{for all} } \alpha\in(\alpha^{\mathit{MM}}_{\max}, 1)\), where \(l_{\mathit{MM}}^{*}\) is the optimal path determined by the Maximum Risk model.

Proof

First, we have observed that for each path \(l \in\mathcal{P}\), there exists a scalar α l such that \(\mathit{VaR}_{\alpha}^{l} = \max_{(i,j) \in\mathcal{A}^{l}}{C_{ij}} \ \forall \alpha\in(\alpha^{l}, 1)\). To show it, let \(\alpha^{l} = 1 - \pi^{l}_{(m^{l})}\) in Lemma 1. It is obvious that \(\mathit{VaR}_{\alpha}^{l} = \max_{(i,j) \in \mathcal{A}^{l}}{C_{ij}} \ \forall\alpha\in(\alpha^{l}, 1)\). Consequently, \(\forall l \in\mathcal{P}\), there exists a α l such that \(\mathit{VaR}_{\alpha}^{l} = \max_{(i,j) \in\mathcal{A}^{l}}{C_{ij}} \ \forall\alpha\in(\alpha^{l}, 1)\). Let \(\alpha^{\mathit{MM}}_{\max} = \max_{l \in\mathcal{P}}{\alpha^{l}}\), and we can see \(\mathit{VaR}_{\alpha}^{l} = \max_{\alpha_{i}^{l}}{C_{i}^{l}} \ \forall \alpha\in(\alpha^{\mathit{MM}}_{\max}, 1), \ \forall l \in\mathcal{P}\). Further, we have \(\mathit{VaR}_{\alpha}^{*} = \min_{l \in\mathcal {P}}{\mathit{VaR}_{\alpha}^{l}} = \min_{l \in\mathcal{P}}{\max_{(i,j) \in \mathcal{A}^{l}}{C_{ij}}} \ \forall\alpha\in(\alpha^{\mathit{MM}}_{\max}, 1)\). Therefore, \(l_{(\alpha-VaR)}^{*} \equiv l_{\mathit{MM}}^{*}\). The theorem follows. □

Theorem 2 says that for a sufficiently large α level close to 1, especially \(\alpha\in(\alpha^{\mathit{MM}}_{\max}, 1)\), the optimal VaR path is the same as the optimal MM risk path. This reflects the extreme risk-averse attitude of the Maximum Risk model.

Theorem 3

For any interval \((\alpha_{k^{\mathcal{P}}}, \alpha_{k^{\mathcal {P}}+1}] \subset(0,1)\), the optimal path determined by the VaR model (17)–(18) remains the same within the interval.

Proof

Suppose that a shipment has a set of candidate paths \(\mathcal{P}\). Each candidate path \(l \in\mathcal{P}\) has a set of consequences \(\mathcal{C}^{l}\).

Furthermore, suppose that there are \(\overline{m}^{\mathcal{P}}\) sorted consequences for all paths in set \(\mathcal{P}\). Let \(C^{\mathcal {P}}_{(k)}\) denote the k-th smallest value among \(\{C_{ij}: (i,j) \in \mathcal{A}^{l}, l \in\mathcal{P}\}\). That is, we assume:

$$C^{\mathcal{P}}_{(1)} < C^{\mathcal{P}}_{(2)} < \cdots< C^{\mathcal {P}}_{(k)} < \cdots< C^{\mathcal{P}}_{(\overline{m}^{\mathcal{P}})}, \quad \mbox{with} \ \pi^{\mathcal{P}}_{(k)} = \Pr\bigl(R = C^{\mathcal {P}}_{(k)}\bigr). $$

Then, the optimal VaR is:

(21)

The function (21) shows that for each confidence interval:

$$\bigl(\alpha^{\mathcal{P}}_{k}, \alpha^{\mathcal{P}}_{k+1}\bigr] = \Biggl(1 - \sum_{i = k}^{\overline{m}^{\mathcal{P}}}{\pi^{\mathcal{P}}_{(i)}}, 1 - \sum_{i = k+1}^{\overline{m}^{\mathcal{P}}}{\pi^{\mathcal{P}}_{(i)}} \Biggr] $$

there exists the same optimal \(\mathit{VaR}_{\alpha}^{*}\); therefore, the optimal route choice is the same in this confidence interval. The theorem follows. □

Theorem 3 uncovers an important property of the VaR model. No matter how the confidence level α varies, we can always find the ranges of confidence intervals so that within each confidence range there is only one optimal solution. In fact, the function (21) tells us other important information about hazmat shipment. From Lemma 1, we know that each candidate path in \(\mathcal{P}\) may have different risk value when α falls into different confidence intervals labeled:

$$\Biggl(1 - \sum_{i = k}^{\overline{m}^{\mathcal{P}}}{\pi^{\mathcal {P}}_{(i)}}, 1 - \sum_{i = k+1}^{\overline{m}^{\mathcal{P}}}{\pi^{\mathcal{P}}_{(i)}} \Biggr] $$

Therefore, under different confidence intervals, there may be a different least risk path. Thus, in a realistic size network (with many available route choices), a shipment is likely to have different optimal solutions when the α level changes.

The theorems dictate that for most networks, no shipment follows the same optimal path under all confidence levels α∈(0,1). But because a road network has a finite number of links, the possible risk values of a path are finite, too. Consequently, the confidence levels can be segmented into a series of traceable intervals, each with an optimal solution. Once we determine the thresholds of these solutions, i.e., the upper and lower limits of the corresponding confidence intervals, we can generate a decision matrix of route choices. Later, in Numerical Example Sect. 5, we illustrate that when α varies among (0,1), the VaR value for each candidate path varies too, subsequently with the corresponding route choice, as shown in Fig. 3. No paths bring any risk to the neighborhood especially when confidence level α is extremely small and close to 0. In such a case, we can decide the optimal path according to other criteria like transportation cost. When α becomes larger, different risk preference generates different route choices. The VaR model equals to MM model especially when α becomes extremely large and close to 1.

4 Solution procedure

In this section, we provide an algorithm for solving the reformulation (17) and its computational complexity.

4.1 Description of the algorithm

In formulation (17)–(18), the inner problem is a typical shortest path problem with modified link costs. The outer problem is a loop procedure to select the minimal β α from the ordered consequence set \(\mathcal{C}\) that satisfies the condition that the objective function value of the inner problem reaches the given confidence level α.

We propose an exact solution procedure for the model (17)–(20) as follows. We first sort the link consequences in ascending order. We then search β α from the lowest value of \(\mathcal{C}\) upwards. For each consequence level β α , we modify the link properties p ij according to C ij , and solve the sub problem with the corresponding objective function value f. Next, we compare the values of f and \(\bar{\alpha }\). If \(f \leq\bar{\alpha}\), we are done; otherwise, we raise β α to the next lowest value of \(\mathcal{C}\), and solve the sub problem again to get a new f. We repeatedly compare the value of f and \(\bar{\alpha}\) until \(f \leq\bar{\alpha}\), or all links in the network G have been visited.

Let us explain the validity of Algorithm 1. At iteration n, the modified link probabilities with \(\beta^{n}_{\alpha}\) are

(22)

for all \((i,j) \in\mathcal{A}\). Then we obtain the following equivalence

(23)

where \(\mathcal{A}^{n}\) is the set of links in the solution path l n of the subproblem at iteration n. The right-hand-side of (23) is the sum of link probabilities on this path with consequence greater than \(\beta^{n}_{\alpha}\). Further, if the value of \(\beta_{\alpha}^{n}\) is same as the k-th smallest consequence in the path l n, i.e., \(\beta_{\alpha}^{n} = C_{(k)}^{l^{n}}\), then from (9) we can express (23) as

(24)
Algorithm 1
figure 1

VaRHazmat

Full size image

To show the validity of the stopping test in Algorithm 1, let \(\mathit{VaR}_{\alpha}^{*}\) denote the solution. If the current \(\beta_{\alpha}^{n}\) is the solution, i.e., \(\beta_{\alpha}^{n} = \mathit{VaR}_{\alpha}^{*} = C_{(k)}^{l^{n}}\), we have from (8)

$$\sum_{i=k}^{\overline{m}^{l^n}}{\pi^{l^n}_{(i)}} > \bar{\alpha} \geq \sum_{i=k+1}^{\overline{m}^{l^n}}{ \pi^{l^n}_{(i)}} $$

and consequently, from (24), \(f^{n} \leq\bar{\alpha}\). On the other hand, if the current \(\beta_{\alpha}^{n}\) is not the solution, i.e., \(\beta_{\alpha}^{n} < \mathit{VaR}_{\alpha}^{*}\), we obtain \(f^{n} > \bar{\alpha}\). To show this, suppose \(\beta_{\alpha}^{n} = C_{(h)}^{l^{n}}\) where C (h)<C(k). Then we have

$$\sum_{i=h+1}^{\overline{m}^{l^n}}{\pi^{l^n}_{(i)}} \geq\sum_{i=h+1}^{k-1}{\pi^{l^n}_{(i)}} + \sum_{i=k}^{\overline{m}^{l^n}}{\pi^{l^n}_{(i)}} \geq\sum_{i=k}^{\overline{m}^{l^n}}{\pi^{l^n}_{(i)}} > \bar{\alpha} $$

therefore \(f^{n} = \sum_{i=h+1}^{\overline{m}^{l^{n}}}{\pi^{l^{n}}_{(i)}} > \bar{\alpha}\). We can apply the same argument to all other paths to show the validity of the stopping test.

4.2 Complexity of the algorithm

Now let us analyze the complexity of this algorithm. The prerequisite problem is a sorting problem. There are many popular sorting algorithms. The typical ones like Mergesort and Heapsort algorithms (Knuth 1998) provide average \(O(|\mathcal{A}|\log|\mathcal {A}|)\) time complexity. Other sorting algorithms are also developed with better time complexity with additional constraints like algorithms of Han (2004) and Thorup (2002). The best case for a sort so far is MSD RadixSort (McIlroy et al. 1993) which is specialized for strings, with \(O(|\mathcal{A}|)\) time linearly proportional to the number of items.

Subsequently, the main body of our algorithm is composed of two steps. The outer loop body takes \(O(|\mathcal{A}|)\) runs. As for the inner shortest path problem, it can be solved by search algorithms. Currently no “best” algorithm exists for every kind of transportation problem, but several algorithms focus on finding the optimal path with either efficiency or accuracy in mind. The enumeration algorithm searches the shortest path by scanning all possible solutions. It ensures to get the exact solution within a constant computational time. However the computational effort and required space increases exponentially with the growth of the size of the input data. The Dijkstra’s labeling method (Dijkstra 1959) is a classic solution in most shortest path algorithms. It generates the shortest path from origin (O) to destination (D) by iteratively constructing the shortest out-tree originating from (O) to a set of permanently labeled nodes. This algorithm terminates when D is permanently labeled and does not need to search all the nodes within a road network. However, since its search space relies on the depth of the optimal path and the branching size, the search speed increases exponentially in the number of nodes explored. This is the main obstacle for shortest path search in large networks. To overcome this effect, Pohl (1971) proposes a bi-directional method by searching from both forward and backward. This method decreases the size of the search space effectively. Hart et al. (1968) also formalized a heuristic named the A∗ Algorithm, choosing nodes based on the cost from the start node (O) with a likely proximity to the destination (D). This method effectively reduces the search space by reducing the number of node expansions, and reduces the effect of combinatorial exploration by reducing the size of the base in the complexity term. But the most efficient way till now to eliminate or minimize the effects of the combinatorial explosion in a large-scale network, is a Hierarchical Search method suggested in Smith et al. (1998), which works by classifying and exploring the roads in the network into smaller, more manageable networks. This Hierarchical method offers the prospect of greatly reducing the size and complexity of any search by simplifying the search through a series of levels. There is an empirical time/performance trade-off between these algorithms. Dijkstra’s and Pohl’s Symmetric algorithms guarantee optimality, which are suitable for small-sized road networks. While for a large-scale road network, the A∗ Algorithm, and especially the Hierarchical algorithm can significantly reduce the search time while sacrificing accuracy.

For our model, if we employ Dijkstra’s algorithm, the whole procedure has a \(O(|\mathcal{A}|^{2}\log(|\mathcal{A}|))\) time requirement. This is reasonable for hazmat shipments as they are usually transported on national highway systems, like U.S. and interstate routes. According to the statistics from the Federal Highway Administration, there are altogether 499 Interstate routes (Federal Highway Administration 2007) and 1001 US routes (Droz 2009) for all states, with an average of 30 national highways traversing each State. So the road network for hazmat transportation is relatively sparse. For small and middle sized networks, we can apply the Dijkstra’s algorithm or Pohl’s algorithms in our procedure to find the optimal VaR solutions. For large-scale networks, the Hierarchical algorithm provides an efficient heuristic route choice method.

5 Numerical example

Take the network shown in Fig. 1 as example. It consists of 9 nodes and 12 arcs, offering 6 available paths from Origin 1 to Destination 9 (see Table 3).

Fig. 1
figure 2

A test network for hazmat VaR problems

Full size image
Table 3 Candidate paths
Full size table

Let us take l 1, for example; we have the CDF of risk as follows:

The corresponding VaR of path l 1 is:

If we set confidence level α=95 %, the corresponding VaR value is 3. That means, we have at least 95 % probability to control the consequence brought by path l 1 under value 3 once an accident occurs. Or, in other words, the possibility of the path risk being larger than 3 is less than 0.5 %. But under α=50 %, the corresponding VaR value for path 1 is 1.

Similarly, we can get the different VaR values for each of the 6 paths under different confidence levels. The corresponding VaR values of each candidate path are as displayed in Fig. 2. For α=95 %, with the VaR values of paths displayed in Table 4, we see that path l 1 gives the optimal solution for O-D pair (1,9) at confidence level 95 %.

Fig. 2
figure 3

VaR path choices under different confidence level α

Full size image
Table 4 VaRs under confidence level 95 %
Full size table

Table 5 generates the VaR decision matrix for the six candidate routes under different α levels. We can see that under different confidence levels, the worst risk route varies too. This is different from the MM2 model proposed in Bell (2007), which gives a one-dimensional route choice vector using the random sampling principle. Table 6 gives the optimal paths generated by the nine classic risk models collected in our literature review.

Table 5 VaR decision matrix for the six routes under different α levels
Full size table
Table 6 Alternative risk model comparison for the six routes
Full size table

The results of this numerical example illustrate that the optimal path choice should vary according to different confidence levels, as shown in Fig. 3. Actually VaR turns out to be a function of α and varies with different α values as displayed in Fig. 2. Therefore, the optimal route solution varies under different α values too. This provides the shipment dispatchers broader route choices according to their risk preferences, which may vary according to their judgment to the up-to-date road situation as well as the public risk allowance. A risk-averse decision maker would prefer a high confidence level, however, an optimistic decision maker may consider it good enough to control risk within allowable confidence level. Speaking from a more strictly practical point of view, the confidence level should respect the up-to-date road situation and public preference. This is another problem of multi-discipline views involving social science, humanities, environmental science, etc. In our problem, we suppose that a rational confidence level can be determined by dispatchers or governors when making routing decisions.

Fig. 3
figure 4

Path choice under different α values

Full size image

6 Case study

We develop a case study in a transportation network around Albany and its nearby highway (Fig. 4). Albany, New York connects many major interstates and is a heavy hub for hazmat transportation. There are eight major interstate and US routes traversing the Albany area and its neighborhoods: I-90, I-890, I-87, I-88, I-787, US-20, US-9 and US-9W. 304,204 residents are located in the 10 towns, 3 cities and 6 villages (US Census Bureau 2010) with variant population density. All those form a dense transportation network along those routes.

Fig. 4
figure 5

Albany area highway roadmap

Full size image

We built a transportation network composed of 90 intersections and 148 road segments. The link accident probabilities are calculated according to road segment lengths. The function (25) refers to the investigation summary of Abkowitz and Cheng (1988):

$$ p = 10^{-6} \times l. $$
(25)

The link consequences are calculated according to population density within the neighborhood around the links. Assuming the radius λ of spread of HM is 1 mile, the endangered area can be described with a whole λ-neighborhood which is a concept developed by Batta and Chiu (1988). Here the link consequence is calculated according to the function 26:

$$ C = \bigl(\pi\lambda^{2} + 2 \times\lambda\times l \bigr) \times\rho, $$
(26)

where ρ represents the population density in the neighborhood along the road segment (persons per mile-sq). We collect the population data of the town where the road segment is located and distribute the risk uniformly to the area. The road lengths and population statistics come from Department of Transportation and Department of Commerce websites.

Based on Dijkstra’s algorithms, our two-stage solution is coded in Java 1.6.16 and run on a Intel Core2 Quad CPU Q6600 2.40 GHz computer system. Our computational experience reveals that our procedure is of high efficiency and the computing time is within 5 seconds. We now discuss our results.

We take O-D pair (1,22) as an example to illustrate the VaR model and compare its difference from classic models. The same data sets are collected and tested under different confidence levels to verify the accuracy of the classic models compared with the VaR model and to illustrate the effectiveness of our algorithm. Tables 7, 8 and 9 contain results from three representative runs; they each provide a comparison with the eight hazmat risk models contained in our literature review section. Here in our example, we only display the result of PR model with parameter q=2, and MV model with parameter k=0.5, and DU model with parameter k=0.001. As shown in our result, TR, PE, PR, MV, and CR models generate routes along Route US-20; while the IP model chooses a less accident probability route along NY-5; by contrast, the extremely risk-averse MM model generates a least consequence route far from I-90 and US-20.

Table 7 A representative run of hazmat VaR model for a given value of confidence level, α—round 1
Full size table
Table 8 Representative run—round 2
Full size table
Table 9 Representative run—round 3
Full size table

Round 1 proves that for a certain small confidence level α=0.00, no risk models are effective since all paths are risk-indifferent paths. The VaR values for all paths in Table 7 are zero, and the algorithm for the VaR model happened to choose the same path as the IP model. In this case, we can ignore the risk factor considered and follow other criteria such as population exposure, economic loss, effects on commerce, and delays in transportation, for route choice. Another phenomenon that caught our eyes is that, when confidence level α is relatively small, the VaR solution tends to generate the similar result as the risk-neutral model like TR model. It accords to our expectation that the decision maker intends to be optimistic and have more risk tolerance. With stricter α, it is witnessed that our solution begins to predict the more risk-averse preference. The solutions from the VaR model are comparative to the risk-averse models like PE, MV, and DU. When confidence level α approaches to 1, our VaR model simulates the MM model, which represents the extreme risk-averse preference. For the OD pair (1,22), while the confidence level α=0.9999999, our VaR model solution has the same risk as that of the MM model.

Another noticeable phenomenon is that, combining considerations of both risk analysis and confidence level, the VaR model can generate different routes which represent the risk preference of decision makers. Take Round 2 as example, where α=0.999982, our VaR model generates a route detour from the major routes I-90, I-890 and US-20, and the Albany City, to avoid the high population density area. At the same time, it does not detour too much like the DU and MM model which consume the transportation cost to an extent hardly acceptable for carriers. It turns out to be a more reasonable route with less cutoff risks than other risk models under α=0.999982. The result of Round 3 is illustrated in Fig. 5.

Fig. 5
figure 6

Route comparison from origin 1 to destination 22

Full size image

Subsequently, we output the difference between VaR and the classic models under all confidence intervals. The VaR performances of the classic models for the OD pair (1,22) are provided in Table 10. Each of the above models predicts a certain risk preference under a certain confidence level. As Table 10 displays, when the confidence level α is sufficiently small, all risk models behave similar since the circumstance is optimistic enough to cause no risk at all to the shipment. But when α>0.9999706, those routes tend to bring various risk levels to the neighborhood. In the LPHC case like Hazmat transport when historical data can not be totally relied on, we take advantage of the uncertainty tolerance of the VaR model to simulate the various risk preferences and generate flexible and valid route choices for decision makers.

Table 10 VaR comparison between α—VaR model and classic models
Full size table

7 Conclusions and future research

This paper proposes a new hazardous material transportation model based on the risk measurement commonly used in financial application, Value-at-Risk (VaR). This model is developed on a strategy that controls the social risk carried by the shipment. It is more general than the traditional deterministic risk models. The VaR model introduces a new factor of confidence level α which represents the decision maker’s risk preference. The objective of the VaR model is to control the worst risk experienced by a shipment within a certain confidence interval. The optimal VaR path varies under different α and is not necessarily the optimal expected risk path. The VaR calculation method and the optimal path algorithm are provided and demonstrated in this paper.

For each shipment, the decision maker can find the upper and lower bounds of a series of confidence intervals (α k ,α k+1]⊆(0,1), and create a decision matrix for route choices. The VaR values become zero for all paths when the confidence level α is close to 0, and the maximum risk model when α is close to 1. This model provides decision makers a more flexible tool to decide the optimal path according to their judgment of the real-time road situation and its subsequent risk level by adjusting the confidence level α. Further the VaR model may be used in combination with other models. One may list several paths with better VaR values, and choose a path satisfying a certain criteria based on other hazmat routing models. We will provide an algorithm to provide such better paths based on VaR in our subsequent research article.

While this paper emphasizes the single-trip hazmat shipment problem, further development of the VaR model should consider the mitigation of the social risk for the multiple-trip hazmat transportation problem, combined with broader decision factors like costs or schedules of shipments, or constraints like risk equity among different geographical zones.