On finding dissimilar Pareto-optimal paths

https://doi.org/10.1016/j.ejor.2003.10.033Get rights and content

Abstract

The aim of the present paper is to provide a methodology for finding a set of alternative paths between an origin and a destination site on which routing one or a set of dangerous goods. Finding a set of paths allows one to equally distribute the total risk among the population exposed. The concept of equity of risk is here related to the concept of determining spatially dissimilar paths. We divide our approach into two phases. In the first phase we find a set of Pareto-Optimal paths between an origin and a destination, by implementing a multicriteria shortest path algorithm. In the second one, for each path previously found, and by using a geographical information system, we construct a Buffer Zone approximating the impact area of a material being released after an accident. Based on these Buffer Zones, a dissimilarity index between every pair of paths can be derived in order to find the most spatially different routes. We then compare our method with an iterative penalty method and discuss computational results based both on a real application and on test problems.

Introduction

Routing Hazardous materials is an important issue in modern industrialized societies. Hazardous materials comprise explosive, flammable, poisonous gases and radioactive materials. Then, evaluating and designing safe routes is necessary for reducing the risk associated to an accident. However, the consequences of an injury strictly depend both on the network status and on the material being transported. In the literature there are several papers that consider how to assess the potential risk imposed by shipments traversing each link in a network [1], [8], [9], [13], [17]. In [13] the authors draw a band of fixed width around each link and use the population living within this band to assign to the link a weight representing the risk of the arc. In [17] the authors consider a Gaussian point-source pollution dispersion model to determine a measure of the risk of the links in a transportation network when after an accident the material becomes airborne. Basically, all these papers focus on the risk to be associated to the arcs of the network and, for instance in [13], in finding a route which minimizes the total transportation risk. We focus our attention into the problem of finding a set of alternative paths between an origin and a destination site on which routing an hazardous or a set of hazardous materials. Finding a set of paths allows one to manage a fleet of vehicles and/or to equally distribute the total risk among the population exposed. Moreover, there may be instances where a decision maker is interested in developing back-up routes for a daily shipment in case the best route become infeasible due to road construction [2].

A similar approach is in [2] where the authors examined the problem of finding a set of spatially dissimilar paths between an origin and a destination. Indeed, they started from the consideration that in order to determine a set of alternative routes, efficient algorithms can be applied. This can be achieved, for instance, via a k-shortest path algorithm or by using an iterative penalty method (IPM). The problem is that by using such algorithms the obtained routes may be spatially very similar to one another and in some instances this may be unacceptable. Seeking for a set of dissimilar paths is a mandatory requirement to ensure spatial risk equity for multiple shipments of hazardous materials. In order to find a set of spatially dissimilar paths, they use the two previous methods to generate a set of candidate paths from which to extract the maximal dissimilar ones by applying a p-dispersion algorithm. In the classical p-dispersion problem, p out of n given points (1<p<n) are selected in some space when the objective is to maximize the minimum distance between any of the selected points. A description of the algorithm will be given in Section 3.1. In [2], the candidate points are the paths found with the two methods mentioned above. As a measure of distance the authors introduced a dissimilarity index between each pair of routes found in the first phase. However, this dissimilarity index between two paths is computed by only considering the lengths of the arcs or of the set of arcs shared by the two paths. There are two major drawbacks in their approach. Firstly, the methods employed for generating the set of initial paths consider only a single objective function, namely that of minimizing the risk or minimizing the cost or minimizing a linear combination between risk and cost. Indeed, by considering only one objective function or aggregating all the criteria in a single objective function (e.g. by linear combination) one cannot necessarily capture the trade-off between two or more conflicting criteria (e.g. risk and cost) (see also [14]) involved in the transportation of an hazardous material. The two methods employed have several “dimensions” in their implementation such as the structure of the penalty to be associated or the number k of paths to be generated. Secondly, the dissimilarity index computed by referring only to the lengths of the arcs of a pair of paths at a time, does not consider adequately the population exposure living near the paths.

In our approach we solve the problem in two phases too. We determine the set of initial paths by formulating the problem as a multicriteria shortest path problem (MSPP), in this way we can better distinguish the “effects” of the conflicting criteria involved, thus avoiding the dependence of the solution from “suitable” weights to be associated to the criteria in order to find a linear combination of them. The algorithm also does not involve any other decision in its implementation. In addition, a multicriterion approach leads to an exact method while with IPM, as stated in [2], a specific penalty strategy may eliminate a great viable paths from consideration. In a second phase, for finding the set of spatially dissimilar paths we refer to the notion of Buffer Zones of a path, that can be thought of as the zone determined by moving a circle along the path whose center is the vehicle on the path itself and whose radius is proportional to the impact area due to a possible accident. This definition is similar to the one used in [13]. The problem in considering such a zone is that we assume that all the persons within the band will be impacted equally and no one outside of the zone will be impacted at all. However, this can be realistic when the material being transported is not airborne when released, like explosive or flammable materials. The Buffer Zones associated to each path are defined by using a geographical information system (GIS), this also allows to tailor the impact area to the topology of a path. After having defined the impact area, that is the Buffer Zones, of all the paths found in phase one, we compute an index representing the dissimilarity between two paths referring to the areas shared by the two paths. In this way we can take into account the population exposure during a shipment. Then, by using a p-dispersion method we find the subset of maximal spatially dissimilar paths [2]. Since there exists an inverse relation between the number p of selected points and their dissimilarity, the parameter p is chosen by referring to a preferred threshold of dissimilarity evaluated by preliminary tests.

The remainder of the paper is organized as follows. In Section 2 we review previous works on multicriteria shortest path algorithms. In Section 3 we introduce our method and present a real application to the road transportation network of Rome which is used as test to compare our method with an IPM similar to the one described in [2]. Moreover, to perform a more thorough comparison of such methods, in Section 4 we provide additional experimental results based on test problems where the underlying networks are directed rectangular grid graphs. Finally, in Section 5 discussions and further researches are depicted.

Section snippets

Previous researches on multicriteria shortest path algorithms

One of the first systematic studies on the bicriteria path problem was reported by Hansen [6]. Later, Clı́maco and Martins [3], Martins [10], Hartley [7] presented exact dynamic-programming-based vertex labeling algorithms for generating the entire set of Pareto-Optimal paths. Since the problem is NP-complete, these algorithms are non-polynomial and even a moderate sized networks may require considerable computational effort because the set of non-dominated paths may be too large. Warburton [15]

Our method, and the application

In this section we describe our method based on a Martins and Santos-like algorithm for the MSPP for finding the set of the candidate paths on which we will apply a p-dispersion algorithm, and then we compare the results so obtained by implementing an IPM for the generation of another initial set of paths. As an example network we use the transportation road network of Rome, from which we have excluded the historical center, obtaining a subnetwork of 699 vertices and 1754 arcs. We also supposed

Experimental results

As previously stated, the results obtained in this research area are often problem-dependent and it can be very difficult to compare different methods on different networks. For this reason, we believe that it could be useful to the research community to have some benchmark instances easy to generate on which apply different methods and analyze solutions. Hence, in this section we design some computational tests in order to compare the effectiveness of the two proposed methods. These tests are

Discussion and conclusions

Searching for a set of alternative paths seems to be a better approach for designing safe routes for the transportation of hazardous materials. Although there are in the literature several papers facing the problem of how to assess the risk associated to the links of a transportation network, for the specific problem of routing, the solution methods are mainly based on the identification of a route which minimizes the total risk, or a combination of risk and cost of the path. As noted, these

Acknowledgements

This research has been supported by grants from the Italian National Research Council (CNR, Contract N. 00.00605.PF/37) and by the Italian Civil Protection. We also thank Dr. Paolo Fantini for his technical support. We are also grateful to the referees for their valuable comments and suggestions.

References (17)

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

Cited by (0)

View full text