×

On finding dissimilar Pareto-optimal paths. (English) Zbl 1132.90303

Summary: 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.

MSC:

90B06 Transportation, logistics and supply chain management
90C27 Combinatorial optimization
Full Text: DOI

References:

[1] A. Ang, J. Briscoe, et al., Development of a system risk methodology for single and multimodal transportation systems, Final report, Office of University Research, US DOT, Washington, DC, 1989; A. Ang, J. Briscoe, et al., Development of a system risk methodology for single and multimodal transportation systems, Final report, Office of University Research, US DOT, Washington, DC, 1989
[2] Akgün, V.; Erkut, E.; Batta, R., On finding dissimilar paths, European Journal of Operational Research, 121, 232-246 (2000) · Zbl 0951.91050
[3] Clı́maco, J. C.N.; Martins, E. Q.V., A bicriterion shortest path problem, European Journal of Operational Research, 11, 399-404 (1982) · Zbl 0488.90068
[4] R.G. Cox, Routing and scheduling of hazardous materials shipments: Algorithmic approaches to managing spent nuclear fuel transportation, Ph.D. dissertation, Cornell University, Ithaca, NY, 1984; R.G. Cox, Routing and scheduling of hazardous materials shipments: Algorithmic approaches to managing spent nuclear fuel transportation, Ph.D. dissertation, Cornell University, Ithaca, NY, 1984
[5] Erkut, E.; Verter, V., Modeling of transport risk for hazardous materials, Operations Research, 46, 625-642 (1998) · Zbl 0987.90529
[6] Hansen, P., Bicriterion path problems, (Fandel, G.; Gal, T., Multiple Criteria Decision Making: Theory and Applications. Multiple Criteria Decision Making: Theory and Applications, Lecture Notes in Economics and Mathematical Systems, vol. 177 (1980), Springer-Verlag: Springer-Verlag Berlin), 109-127 · Zbl 0444.90098
[7] Hartley, R., Vector optimal routing by dynamic programming, (Serafini, P., Mathematics of Multiobjective Optimization (1985), Springer-Verlag: Springer-Verlag Berlin), 215-224
[8] Lepofsky, M.; Abkowitz, M.; Cheng, P., Transportation hazard analysis in integrated GIS environment, Journal of Transportation Engineering, 119, 239-254 (1993)
[9] List, G. F.; Mirchandani, P. B.; Turnquist, M. A.; Zografos, K. G., Modeling and analysis for hazardous materials transportation: Risk analysis, routing/scheduling and facility location, Transportation Science, 2, 100-114 (1991)
[10] Martins, E. Q.V., On a multicriteria shortest path problem, European Journal of Operational Research, 16, 236-245 (1984) · Zbl 0533.90090
[11] E.Q.V. Martins, J.L.E. Santos, The labeling algorithm for the multiobjective shortest path problem, 1999 (downloadable from website http://www.mat.uc.pt/ eqvm/cientificos; E.Q.V. Martins, J.L.E. Santos, The labeling algorithm for the multiobjective shortest path problem, 1999 (downloadable from website http://www.mat.uc.pt/ eqvm/cientificos
[12] Nozick, L. K.; List, G. F.; Turquist, M. A., Integrated routing and scheduling in hazardous materials transportation, Transportation Science, 31, 200-215 (1997) · Zbl 0887.90063
[13] ReVelle, D. J.; Cohon, C.; Shobrys, J., Simultaneous siting and routing in the disposal of hazardous wastes, Transportation Science, 25, 138-145 (1991)
[14] Sancho, N. G.F., A new type of multiobjective routing problem, Engineering Optimization, 14, 115-119 (1988) · Zbl 0641.90040
[15] Warburton, A., Approximation of Pareto optima in multiobjective shortest path problems, Operations Research, 35, 70-79 (1987) · Zbl 0623.90084
[16] Wijeratne, A. B.; Turnquist, M. A.; Mirchandani, P. B., Multiobjective routing of hazardous materials in stochastic networks, European Journal of Operational Research, 65, 33-43 (1993) · Zbl 0775.90159
[17] Zhang, J.; Hodgson, J.; Erkut, E., Using GIS to assess the risk of hazardous materials transport in networks, European Journal of Operational Research, 121, 316-329 (2000) · Zbl 0951.91031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.