Transportation Research Part E: Logistics and Transportation Review
Identifying geographically diverse routes for the transportation of hazardous materials
Introduction
The repetitive transportation of hazardous materials through a community often generates resentment in members of that community. For an excellent survey on hazmat transportation, see List et al., 1991, Current and Marsh, 1993, Erkut et al., 2006. As is observed in Linder-Dutton et al. (1991) if the shipper can be proactive in identifying routes that are equitable they are more likely engender trust in the communities through which they must pass and avoid some of the bitterness that can arise. Gopalan et al. (1990) develop a method to identify an equitable set of routes that minimize the total cost across the collection of routes while keeping the inequity across a predefined set of zones beneath some threshold. Linder-Dutton et al. (1991) extend the analysis in Gopalan et al. (1990) to optimize the order in which the routes developed by the analysis in Gopalan et al. (1990) are used.
The carrier is concerned with finding routes that minimize the economic cost as well as the risk consequences of a release stemming from an accident. Much of the economic cost to the carrier is proportional to the time taken for the shipment to travel from the origin to the destination. Thus we assume that cost minimization can be obtained through minimizing the total travel time. Defining public risk is more complex, but two characteristics – population exposure and accident rate – have gained wide acceptance. Population exposure and accident rate can be combined into a single consequence measure for a route by summing the product of accident rate and exposure across all links in the route. This is the measure of consequence we adopt in this analysis. Erkut and Verter, 1998, Erkut and Ingolfsson, 2000, Chang et al., 2005, among others, use the same measure in their hazmat routing studies.
Neither the travel time nor the consequence measures are deterministic. They are inherently uncertain since they depend on characteristics like visibility, traffic volumes and activity patterns. Further they vary with the time of the day since the traffic characteristics vary throughout the day. Using the expected values of the attributes ignores the variation resulting from these two causes and could lead to selection of routes that have acceptable expected values but perform “poorly” based on when they are actually used (Nozick et al., 1997). Hence, we represent the uncertainty for each attribute by a probability distribution which varies by the time-of-day.
In this application, we assume the carrier uses an objective that is a weighted sum of travel time and consequence, and that across multiple shipments, the carrier wants to be able to use a set of paths that are relatively distinct geographically. Of course, this creates the need for exploring different trade-offs. Paths that result in small changes in the value of the travel time/consequence measure are likely to vary only slightly from the shortest path geographically. To obtain nearly distinct paths geographically, much larger changes in the objective are likely to have to be tolerated. Our concern is to be able to identify the nature of this trade-off effectively in large networks.
In order to find sets of paths, we develop a two-step process: develop a “large” set of paths to choose from and an optimization model to select a subset of those paths to use that are “geographically distinct”. An algorithm to estimate the first K shortest paths in networks is developed where the routing attributes are random variables that vary according to the time of the day. To the best of our knowledge, Nielsen et al. (2005) is the only stochastic and dynamic K shortest path algorithm. They focus on problem instances for which the departure times are integer and the travel times on links are integer valued discrete random variables based on the departure time. We focus on the use of continuous distributions for link attributes because that is more appropriate to this application area. Also, their focus is on identifying the exact solution to the K shortest path problem. This leads to computational challenges in large networks. Our focus is on the development of a computationally efficient heuristic to estimate the solution in realistic networks. Therefore, we extend Yen’s (1971) deterministic and static K shortest path algorithm to accommodate stochastic and dynamic routing attributes. The new algorithm uses a convolution–propagation method to propagate the means and variances of the uncertain routing attributes along paths, and calculates the covariance between the routing attributes so that the quality of each path can be estimated. We extend Chang et al. (2005) to achieve this.
It is also important that the paths identified be geographically distinct in addition to performing well with respect to the objectives. For the purposes of this analysis, the performance of a path is measured by the mean of the distribution of the weighted objectives in this analysis. In other circumstances it may be more appropriate to focus on other percentiles of the distribution. From the set of K shortest paths identified, we want to identify a subset of paths that represent an acceptable trade-off between geographic diversity and performance. Therefore, the second step of the analysis involves the development of an integer program to identify this subset of paths. For this purpose, we define percentage overlap as the ratio of the number of miles two paths have in common to the actual length of one of the paths. Thus the lower the percentage overlap between a pair of paths, the more geographically diverse the two paths are. Notice that this definition implies that the percentage overlap is not symmetric, but depends on the path to which the comparison is made. Depending on the type of hazardous material to be moved and the motivation for using a variety of routes, other measures of geographic diversity could be more appropriate. While Akgün et al. (2000) use essentially the same metric as we use, they do note that sometimes using the number of people in the areas of overlap between the buffer zones of each route is more appropriate.
Carotenuto et al. (2004) develop a model with similar goals but use a different definition of geographic diversity and hence a different objective. They seek to select a subset of paths that minimize the total number of times multiple hazmat vehicles are on the same link at the same time and the total risk of the set of paths selected. Carotenuto et al. (2007) also focuses on selecting dissimilar paths using greedy add procedures. They enforce geographic diversity by limiting the maximum amount of risk any group of people can be exposed to. Our approach is similar to Kuby et al., 1997, Akgün et al., 2000 and the follow-up paper Thyagarajan et al. (2005). They pursue a minimax objective and consider a metric based on the number of miles in common between the paths selected. Kuby et al. (1997) also includes an ad hoc mechanism to analyze the trade-off between the length of the paths selected and the geographic variety. Akgün et al. (2000) focuses on only maximizing the minimum difference. Our model can be viewed as an extension of the models proposed in Akgün et al., 2000, Thyagarajan et al., 2005 for which trade-offs between geographic diversity and performance can be explored.
We illustrate the application of the entire analysis process on a realistic case study of the highway transportation of hazardous material. The origin and the destination of these shipments are assumed to be Jackson, Mississippi and Tallahassee, Florida, respectively.
The contribution of this paper is fourfold. First, we develop a computationally tractable K shortest path algorithm when the arc attributes are stochastic and dynamic and examine the computational performance of this algorithm on several test networks. This algorithm is useful in other contexts where there is a need to identify the K shortest paths in large-scale stochastic and dynamic networks. Second, we build on Akgün et al. (2000) to identify a subset of geographically distinct paths by allowing for the effective exploration of the trade-offs between geographic diversity and performance. Third, we develop an integrated analysis that illustrates how a large set of routes (and schedules) can be developed and a subset of those routes (and schedules) can be selected to facilitate the movement of hazardous materials when the routing attributes are stochastic and dynamic and geographic diversity in the routes selected is important. Fourth, we illustrate the application of this methodology to a realistic case study.
The next section describes the K shortest path (KSP) algorithm. The third section evaluates the computational performance and the quality of the solution produced by the algorithm. The fourth section develops an optimization model to select a subset of paths that represent an appropriate trade-off between path quality and geographic diversity. The fifth section develops a realistic case study to illustrate the analysis process. The sixth section describes key conclusions and opportunities for future research.
Section snippets
KSP algorithm
The KSP algorithm for stochastic and dynamic arc attributes is comprised of two key elements. The first element is a method to construct a probability distribution of the performance of a path. The second element is a method to compute shortest paths such that each successive shortest path generated performs slightly worse. The next subsection focuses on estimating the probability distribution for path performance. The second subsection focuses on the algorithm developed to generate successive
Solution quality and computational performance
To evaluate the computational performance and solution quality of this algorithm, we evaluate the use of the algorithm on nine sample networks. The objective is again to minimize the weighted average of travel time and the consequence measure. For the purposes of this analysis we assume the following:
- 1.
Link travel time is modeled as a sum of free-flow time plus an exponentially distributed random delay with a mean of 10% of the free flow travel time. Even though the random delay on a link is
Path selection
This section develops a mixed integer program to identify a fixed number of paths, N, which represent an acceptable trade-off between the geographic diversity in the routes and the distribution of the composite measure. Geographic diversity in the routes is measured by the largest overlap between any two paths in the set of N paths. The quality of the set of N paths with respect to the composite measure is given by the maximum value for the mean of the distribution. The MIP is then formulated
Case study
To illustrate the use of the algorithm described above on a complete analysis, we consider routing a hypothetical shipment from Jackson, Mississippi to Tallahassee, Florida over the highway network. We wish to identify five paths that represent an acceptable balance between geographic diversity and performance from a set of 10,000 paths.
The network is shown in Fig. 3 and has 1173 nodes and 1403 bidirectional links where the interstate roads are highlighted. It is roughly 10 times larger than
Conclusions and opportunities for further research
The objective of this paper was to develop a computationally efficient method to identify a small set of routes for use in the routing of hazardous materials shipments. In order to achieve this we develop a K shortest path algorithm where the arc attributes are stochastic and vary over time. This algorithm is based on the integration of the notion of propagating means and variances of attribute distributions across a path as developed in Chang et al. (2005) and the structure for generating K
Acknowledgments
The authors are grateful to two anonymous referees for their useful and valuable comments that helped improve this manuscript significantly.
References (21)
- et al.
On finding dissimilar paths
European Journal of Operational Research
(2000) - et al.
Finding minimum equitable risk routes for hazmat shipment
Computers Operations Research
(2007) - et al.
Multi-objective transportation network design: taxonomy annotation
European Journal of Operational Research
(1993) - et al.
A metaheuristic approach for hazardous materials transportation
- et al.
Multi-objective path finding in stochastic dynamic networks
Transportation Science
(2005) - et al.
Catastrophe avoidance models for hazardous materials route planning
Transportation Science
(2000) - et al.
Modeling of transport risk for hazardous materials
Operations Research
(1998) - Erkut, E., Tjandra, S., Verter, V., 2006. Hazardous materials transportation. In: Barnhart, C., Laporte, G. (Eds.),...
- et al.
Modeling equity of risk in the transportation of hazardous materials
Operations Research
(1990) - et al.
Procedure for developing truck accident release rates for hazmat routing
Journal of Transportation Engineering
(1993)
Cited by (56)
Hazardous material transportation problems: A comprehensive overview of models and solution approaches
2022, European Journal of Operational ResearchObjectives and methods in multi-objective routing problems: a survey and classification scheme
2021, European Journal of Operational ResearchCitation Excerpt :Liu, Mu, and Yang (2017) show that their suggested solution method can further improve the results on some of these test instances indicated by higher dissimilarity values and similar average distances. In Dadkar, Jones, and Nozick (2008), path performance is measured by the mean of the distribution of the weighted sum of travel time and risk exposure. The trade-off to a diversity index is analyzed that is computed as the ratio of the shared distance between two paths to the actual length of one of the paths.
A review on research in transportation of hazardous materials
2019, Socio-Economic Planning SciencesCitation Excerpt :For instance, Kazantzi et al. [112] use probability functions to model release likelihood. Other examples are the work given by Dadkar et al. [101] who assume that the probability of accidents varies following a gamma distribution; Milazzo et al. [18]; who use lognormal and normal distribution for the frequency of accidents on rail tracks; Bonvicini and Spadoni [97]; who use a uniform distribution for the population distribution in centers of aggregated population; and Kawprasert and Barkan [132]; who assume a Poisson distribution for modeling the occurrence of tank-car derailment. The difficulty of this approach is to being able to calibrate an appropriate probability function, which requires having available enough reliable information.
Hazardous materials truck transportation problems: A classification and state of the art literature review
2019, Transportation Research Part D: Transport and EnvironmentDesign of a reliable multi-modal multi-commodity model for hazardous materials transportation under uncertainty
2017, European Journal of Operational ResearchPlanning decisions for recycling products containing hazardous and explosive substances: A fuzzy multi-objective model
2017, Resources, Conservation and Recycling