Identifying geographically diverse routes for the transportation of hazardous materials

https://doi.org/10.1016/j.tre.2006.10.010Get rights and content

Abstract

Often, the carrier/shipper of hazardous materials is interested in a collection of routes with approximately the same performance so that they can switch between different routes to avoid exposing the same population and potentially as a security measure. We develop a K shortest path algorithm for which the performance of each highway facility, with respect to each objective, can be stochastic and can vary over time. We also devise a mixed integer program to identify a subset of paths, which represents an acceptable trade-off between geographic diversity and performance. These models are then applied to a realistic case study.

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)

  • V. Akgün et al.

    On finding dissimilar paths

    European Journal of Operational Research

    (2000)
  • P. Carotenuto et al.

    Finding minimum equitable risk routes for hazmat shipment

    Computers Operations Research

    (2007)
  • J. Current et al.

    Multi-objective transportation network design: taxonomy annotation

    European Journal of Operational Research

    (1993)
  • P. Carotenuto et al.

    A metaheuristic approach for hazardous materials transportation

  • T. Chang et al.

    Multi-objective path finding in stochastic dynamic networks

    Transportation Science

    (2005)
  • E. Erkut et al.

    Catastrophe avoidance models for hazardous materials route planning

    Transportation Science

    (2000)
  • E. Erkut 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.),...
  • R. Gopalan et al.

    Modeling equity of risk in the transportation of hazardous materials

    Operations Research

    (1990)
  • D.W. Harwood et al.

    Procedure for developing truck accident release rates for hazmat routing

    Journal of Transportation Engineering

    (1993)
There are more references available in the full text version of this article.

Cited by (56)

  • Objectives and methods in multi-objective routing problems: a survey and classification scheme

    2021, European Journal of Operational Research
    Citation 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 Sciences
    Citation 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.

View all citing articles on Scopus
1

Tel.: +1 607 254 2939.

2

Tel.: +1 505 284 4886.

View full text