摘要
有害物品是一种具有物理、化学或生物特性的物品，它容易在生产、储存、运输中引起泄漏、燃烧、爆炸等，造成灾害事故，对周围的人口、环境和财产会产生一定的危害。随着经济的发展，有害物品的运输量在大幅的增长，有害物品对环境和人类(潜在)的危害正在扩大和加深。在有害物品运输的路径的选择中，需要同时考虑风险和行车成本等因素，这样，就将传统单目标的运输路径问题转变成了多目标问题。同时，时间因素对有害物品运输的行车成本和风险等因素都会产生一定的影响，即有害物品运输的路径问题具有明显的时变特性。研究具有时变特性的有害物品运输的路径问题具有极强的社会背景和应用前景，有利于从社会经济可持续发展的角度解决资源紧缺、交通拥挤、保护人类和生态环境系统等诸多的社会问题。目前，在有害物品运输过程中，关于风险分析和路径选择方面，仍然存在很多问题有待于进一步的研究。本文较深入地研究了时变条件下有害物品运输中的风险度量和路径选择等一系列问题，主要研究内容如下：
论文第1章在大量相关文献进行总结的基础上，分别回顾了国内、外对于有害物品运输中的风险分析和路径选择问题、多目标最短路问题和时变条件下的路径选择问题的研究成果，并指出了目前有害物品运输中对于风险研究和路径选择研究的不足，然后对文章的基本内容进行了介绍。
第2章，探讨了论文的研究基础。讨论了时变条件下考虑成本(或风险)最小化的最短路问题与静态条件下问题的区别，对静态条件下的算法不适用于时变条件下最短路求解进行了证明，分别提出了时变条件下获得单目标和多目标最短路的最优条件，并给出了时变条件下不同路径之间比较原则。最后，对有害物品运输中，如何选择目标以及这些目标的时变特性进行了分析。
第3章，研究了有害物品运输中的风险度量。首先，考虑距离和人口分布对风险的影响，建立了该条件下风险度量模型，并对给出的模型进行了进一步改进，然后分别验证了风险模型的有效性；其次，考虑了时间因素对风险的影响，建立了时变条件下的风险度量模型，并验证了时变条件下风险模型的有效性。
第4章，研究了时变条件下单一运输方式有害物品运输的最短路问题。建立了时变条件下有到达时间约束和具有多个出发时间的有害物品运输的最短路模型，设计了时变条件下多目标最短路算法，获得了时变条件下有害物品运输有效路径的集合，并
As long as the development of economy, the quantity of hazardous materials grow rapidly. Hazardous material is the material with specially physical, chemical and biological character. It is easy to release, inflame, blast and so on in the manufacturing, inventory and transportation. Those releaseing, inflammation, blast will threat the population, environment and property. Today, the logistics management, people sruvival environment and environment protection became the mian issues in the society. Decreasing the cost and improving safty are the two main factors in the hazardous materials transportation. Compared the general transportation, in the hazardous materials transportation, there are tow objecitves should be comsidered. Thus, it becomes a multi-objective transportation problem. Furthermore, the time will effect the cost and risk in the hazardous materials transportation. Thus, the problem became the hazardous materials transportation with time-varying. This problem has a strong society background and expansive application perspective. It can solove the resource shortage, transportaton congestion, protection of human being and zoology environment by the continuous development. Untill now, few research was maken in the risk measurement and routing planning for the hazardous materials transportation with time-varying. In this dissertation, the risk with time-vaying was measured and the routing problems with time-vaying were analyzed, which has important theoretical significance and practical application value.
The main contents of this dissertation are as followed:
In chapter 1, based on the summary of relative reference, we Fetrospected domestic and foreign researchers on the hazardous materials transportation in the risk measurement and routing planning and the multi-objective shortest path problem. Then, we pointed out the shortcommings in the research on this problem and found some potential areas of the research.
In chapter 2, the fundational theory of the time-varying hazardous materials was discussed. It was divided into three parts. The first is the theory of the time-varying network. The differnece between the time-varying network and static network was discussed and the optimal condition to get the shortest path in time-varying was proved.
引文
[1] G. List, M. Abkowitz. Estimates of Current Hazardous Material Flow Patterns[J]..Trans. Quart, 1986,.Vol. 40: 483-502
[2] Philippe Cassini. . Road transportation of dangerous goods: quantitative risk assessment and route comparison[J].. Journal of Hazardous Materials , 1998,. Vol. 61:.133-138
[3] E. Iakvou, et al..A Maritime Global Route Planning Model for Hazardous Materials Transportation [J]. Transportation Science, .1999,. Vol. 33,.No.1:.34-48
[4] A. Ang, et al..Development of a Systems Risk Methodology for Single and Multimodel Transportation Systems[R]..1989.Final Report,. Office of University Research,. U.S. DOT. Washington, D.C
[5] T. S. Glickman..Benchmark Estimates of Release Accident Rates in Hazardous Material Transportation of Rail and Truck [J] . Trans. Res. Rec, 1988,. Vol. 1193:. 22-28
[6] F. Saccomanno, A. Chan..Economics Evaluation of Routing Strategies for Hazardous Road Shipments [J] .Trans. Res. Rec.,.1985,.Vol. 1020: 12.18
[7] F. F. Saccomanno, J. H. Shortreed.HAZMAT Transport Risk: Societal and Individual perspectives [J] Journal of Transportation Engineering, 1993,.Vol. 119,.No.2: 177-188
[8] B.Ashtakala, and Lucy A. Eno.Minimum risk route model for hazardous material [J].Journal of Transportation Engineering,.1996,.Vol. 122,.No.5:.350-357
[9] D. Joy, et al. Predicting Transportation Routes for Radioactive Wastes [J]. Proc. Symp. Waste Mamt. '81, 1981:416-425
[10] J. Brogan, J. Cashwell. Routing Models for the Transportation of Hazardous Material.State Level Enhancement and Modifications [J]. Trans. Res. Rec, 1985, Vol. 1020:19-22
[11] E. Barvber, L.Hildebrand. Guidelines for Applying Criteria to Designate Route for Transporting Hazardous Material[R]., Report No.FHWA-IP-80-15, 1985
[12] T.S. Clickman. Rerouting Railroad Shipments of Hazardous to Avoid Populated Areas[J], Accident Anal. Prevent, Vol. 15, 1983: 329-335
[13] F. Ivancie. Hazardous Material Routing Study[R]., Final Report prepared by Portland Office of Energy Management, Portland, Ore., 1984
[14] D. Pijawka, S.Foote, A. Soedilo. Risk Assessment of Transporting Hazardous Material: Route Analysis and Hazard Management [J]. Trans. Res. Rec, 1985, Vol. 1020: 1-6
[15] D. Kessler. Establishing Hazardous Materials Truck Routes for Shipments Through the Dallas.Fort Worth Area. In: Recent Advances in Hazardous Materials Transportation Research[J]. Transportation Research Board, 1986: 79-87
[16] R. Batta, S. Chiu. Optimal Obnoxious Path on a Network: Transportation of Hazardous ??Materials [J]. Operations Research, Vol. 36, 1988: 84-92
[17] D. Shorys. A Model for the Selection of Shipping Routes and Storage Location for a Hazardous Substance [D], Ph.D. dissertation, Johns Hopkins University, Baltimore, 1981
[18] J. Robbins. Routing Hazardous Material Shipment [D], Ph.D. dissertation, Indiana University, Bloomington, Ind., 1981
[19] J. R. Current et al. The Minimum-Covering Shortest-Path Problem [J], Decision Sci., 1988, Vol. 19: 490-503
[20] M. Abkowtiz, P. Cheng. Developing a Risk-Cost Framework for Routing Truck Movement of Hazardous Materials[J]. Accident Anal. Prevent, 1988, Vol. 20:39-51
[21] Martins. On a multicriteria shortest path problem[J]. European Journal of Operational Research, 1984, 16: 236-245
[22] Hansen. Bicriterion path problems, in G. Fandel and T. Gal, eds: Multiple Criteria Decision Making: Thoery and Applications [M]. Lecture Notes in Economics and Mathematical Systems 177, Springer-Verlag, Heidelberg: 109-127
[23] Tung, Chew. A bicriterion Pareto-optimal path algorithm[J]. Asia-Pacific Journal of Operations Research, 1988, 5:166-172
[24] K. G. Zografos. Modeling the Process of Hazardous Waste Transportation[C]., paper presented at the Joint National ORSA/TIMS Meeting, Miami Beach (October), 1986
[25] K. G. Zografos, C. F. Davis. Multiobjective Programming Approach for Routing Hazardous Materials [J], Trans. Engrg. J., 1989, Vol. 115: 661-673
[26] L. K. Nozick, G. F. List, M. A. Turnquist. Integrated Routing and Scheduling in Hazardous Materials Transportation [J], Transportation Science, 1997, Vol. 31, No. 3: 200-215
[27] E. Iakovou, et al. A Maritime Global Route Planning Model for Hazardous Materials Transportation [J], Transportation Science, 1999, Vol. 33, No.1:34-48
[28] B. Fabiano, F. Curro, E. Palazzi, R. Pastorino.A framework for risk assessment and decision-making strategies in dangerous good transportation.[J]. Journal of Hazardous Materials, 2002, Vol.93: 1-15
[29] E. Alp. Risk-based transportation planning pratice: overall methodology and a case example[J]. INFOR, 1995, 33: 4-19
[30] C. J. Revelle, J. Cohon, D. Shobrys, Simultaneous siting and routing in the disposal of hazardous wastes[J]., Transportation Science, 1991, 25:138-145
[31] M. Abkowitz, M. Lepofsky, P. Cheng. Selecting criteria for designating hazardous materials higway routes[J]., Transportation Research Records, 1992, 1333: 30-35
[32] Erhan Erkut, Armann Ingolfsson, Catastrophe avoidance models for hazardous materials route planning[J], Transportation Science, 2000, (2): 166-179
|[33] R. A. Sivakumar, R. Batta, M.H. Karwan, Establishing credible risk criteria for??transporting extremely dangerous hazardous materials[M]., in: F.F. Saccomanno, K. Cassidy (eds), Transportation of dangerous goods: assessing the risks, Institute for risk research, University of Waterloo, 1993
[34] R.A. Sivakumar, R. Batta, M.H. Karwan, A network-based model for transporting extremely hazardous materials[J]., Operations Research Letter, 1993, 13: 86-93
[35] Drummond, Ochi. Asynchronous parallel metaheuristic for the period vehicle routing problem[J]. Future Generation Computer Systems, 2001, -Vol.17, No.4: 379-386
[36] Dijkstra. A note on two problems in connection with graphs [J]. Numer Math, 1959, 1: 269-271
[37] Climaco, Martins. A bicriterion shortest path algorithm[J]. European Journal of Operational Research, 1982, 11: 399-404
[38] Lavler. A procedure fro computing the k best solutions to discrete optimization problems and its application to the shortest path problem[J]. Management Science, 1972, 18: 401-405
[39] Yen. Finding the K shortest loopless paths in a network[J]. Management Science, 1971, 17, 712-716
[40] Chen. An algorithm for finding the k quickest paths in a network[J]. Computers and Operations Research, 1993, 20: 59-65
[41] Azevedo et al. An algorithm for the ranking of shortest paths[J]. European Journal of Operational Research, 1993, 69: 97-106
[42] 魏航,蒲云,李军。一种求解双目标最短路的方法[J]. 系统工程, 2005, No.7: 113-117
[43] Mote, Murthy, Olson. A parametric approach to solving bicriterion shortest path problems[J]. European Journal of Operational Research, 1991, 53: 81-92
[44] Geoffrion. Solving bicriterion path mathematical programs[J]. Operatoins Research, 1967, 39-54
[45] B.-Smith, Shier. An empirical investigation of some bicriterion shortest path algorithms[J]. European Journal of Operational Research, 1989, 4: 3216-224
[46] Corley, Moon. Shortest paths in networks with vector weights[J]. Journal of Optimization Thoery and Application, 1985, 46: 79-86
[47] Daellenbach, D. Kluyve. Note on multiple objective dynamic programming[J]. Journal of Operational Research Society, 1980, 31: 591-594
[48] Skviver, Andersen. A label correcting approach for solving bicriterion shortest path problems[J]. 2000, Computers and Operations Research, 27: 507-524
[49] Current et al.. An interactive approach to identify the best compromise solution for two objective shortest path problems[J]. European Journal of Operational Research, 1990, 17: 197-208
[50]Coutinho-Rodrigues et al.. An interactive bi-objective shortest path approach: searching for ??unsupported nondominated solutions [J]. Computers and Operations Research, 1999, 26: 789-798
[51] List, Mirchandani, Turnquist and Zografos. Modeling and analysis for hazardous materials transportation: risk analysis, routing/scheduling and facility location [J]. Transportation Science, 1991, Vol.25, No.2:100-114 241-245
[53] Hail, R. J. An assessment of the risk of transporting Plutonium Dioxide and Liquid Plutomium Nitrate by train[R], Report BWWL-1996, Battelle Pacific National Laboratories, Richland, Wash, 1977
[54] B. Ashtakala, Lucy A. Eno. Minimum risk route model for hazardous material[J]. Journal of Transportation Engineering, 1996, Vol. 122, No.5, September/October: 350-357
[55] Martinez-Alegria, C. Ordonez, and J. Taboada. A conceptual model for analyzing the risks involved in the transportation of hazardous goods: implementation in a geographic information system [J]. Human and Ecological Risk Assessment, 2003, Vol. 9, No. 3: 857-873
[56] W.C. Frank, J-C Thill, R. Batta, Spatial decision support system for hazardous material truck routing[J]. Transportation research, Part C, 2000, 8: 337-359
[57] X. Cai, T. Kloks, C. K. Wong. Time Varying Shortest Path Problems Algorithm for Problems with Constraints [J], Networks, 1998, 31:193-204
[58] Pocard, J C,Queryranne M. The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling[J]. Operations Research 26: 86-110
[59] Abilio Lucens. Time-dependent traveling salesman problem-the deliveryman case[J]. Networks, 1990, Vol.20: 753-763
[60] Ahn, Byong-Hun, Shin, Jae-Yeong, Vehicle-routing with time windows and time-varying congestion, Journal of the Operational Research Society, 1991, 42(5): 393-400
[61] Malandraki, Chryssi, Daskin, Mark S., Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms [J]. Transportation Science, 1992, 26(3)
[62] Chryssi Malandraki, Robert B.Dial. A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem[J]. European Journal of Operational Research, 1996, 90:46-55
[63] Hill, Arthur V, Benton, W.C, Modeling intra-city time-dependent travel speeds for vehicle scheduling problems[J]. Journal of the Operational Research Society, 1992, 43(4): 343-351
[64] Jung Soojung. A genetic algorithm for vehicle routing problem with time dependent travel times[D]. Doctor Degree Dissertation 2000
[65] Jung, Soojung; Haghani, Ali, Genetic algorithm for the time-dependent vehicle routing problem[J]. Transportation Research Record, 2001, 1771: 164-171
[66] Ichoua, Soumia, Gendreau, Michel; Potvin, Jean-Yves. Vehicle dispatching with time-dependent travel times[J]. European Journal of Operational Research, 2003, 144 (2):379-396
[67] Alberto V. Donati, Luca M. ambardella, Norman Casagrande, Roberto Montemanni, Andrea E. Rizzoli, Time Dependent Vehicle Routing Problem with an Ant Colony System[C], Istituto Dalle Molle di Studi sull'Intelligenza Artificiale (IDSIA) Galleria 2, 6928 Manno, Switzerland, IDSIA-02-03
[68] Alberto V. Donati, Roberto Montemanni, Norman Casagrande, Andrea E. Rizzoli.Luca M. ambardella, Time Dependent Vehicle Routing Problem with an Multi Ant Colony System[C], Istituto Dalle Molle di Studi sull'Intelligenza Artificiale (IDSIA) Galleria 2, 6928 Manno, Switzerland, IDSIA
[69] Alberto V. Donati, Roberto Montemanni, Luca M. Casagrande, Andrea E. Rizzoli, Integeration of a robust shortest path algorithm with a time dependent vehicle routing model and applications[C]. CIMSA 2003-International Symposium on Computational Intelligence for Measurement Systems and Application Lugano, Switzerland, 29-31 July 2003
[70] Luis Gouveia, Stefan Vob. A classification of formulations for the (time-dependent) traveling salesman problem[J]. European Journal of Operational Research, 1995, 83:69-82
[71] Harilaos N.Psapaftis, John N.Tsitsiklis. Dynamic shortest paths in acyclic networks with Markovian arc costs[J]. Operations Research, 1993, 4, 1
[72] Yang-Byung Park. A solution of the bi-criteria vehicle scheduling problems with time and area-dependent travel speeds[J]. Computer & Industrial Engineering 38 (2000) 173-187
[73] Russ J.Vander Wielm, Nikolaos V.Sahinidis. Heuristic Bounds and Test problem generation for the time-dependent traveling salesman problem[J]. Transportation Science, 1995, Vol 29,No.2: 167-183
[74] 张得志,凌春雨.多种运输方式的组合优化模型及求解算法[J],长沙铁道学院学报, 2002, Vol.20, No.4: 71-75
[75] Angelica Lozano, Giovanni Storchi, Shortest viable path algorithm in multimodal networks[J]. Transportation Research, Part A, 2001, Vol.35: 226-241
[76] R. Gopalan, K. S. Kolluri, R. Batta, M. H. Karwan, Modeling equity of risk in the transportation of hazardous materials[J]. Operations Research, 1990, 38(6): 961-973
[77] L. Lindner-Dutton, R. Batta, M. H. Karwan, Equitable sequencing of a given set of hazardous materials shipments[J]. Transportation Science, 1991, 25(2): 124-137
[78] Erhan Erkut, Armann Ingolfsson, Catastrophe avoidance models for hazardous materials ??route planning[J]. Transportation Science, 2000, Vol. 34, No.2: 166-179
[79] Hanif D. Sherali et al, Low probability-high consequence considerations in routing hazardous materials shipments[J]. Transportation Science, 1997, Vol. 31, No.3: 237-251
[80] List, Mirchandani, Turnquist and Zografos. Modeling and analysis for hazardous materials transportation: risk analysis, routing/scheduling and facility location [J]. Transportation Science, 1991, Vol.25, No.2: 100-114
[81] Helander, Melachrinoudis. Facility location and reliable route planning in hazardous materials transportation[J]. Transportation Science, 1997, Vol.31, No.3: 216-226
[82] Watabe. Liability rules and hazardous materials transportation[J]. Transportation Science, 1991, Vol.25, No.2: 157-168
[83] List, Mirchandani. An integrated network/planor multiobjective model for routing and siting for hazardous materials and wastes[J]. Transportation Science, 1991, Vol.25, No.2: 146-1156
[84] Clickman. An expeditious risk assessment of the highway transportation of flammable liquids in bulk[J]. Transportation Science, 1991, Vol.25, No.2: 116-123
[85] Nembhard, White. Application of non-order-preserving path selection to Hazmat routing[J]. Transportation Science, 1997, Vol.31, No.3: 262-271
[86] Jin, Batta. Objectives drived from viewing Hazmat shipment as a sequence of independent Bernoulli trials[J]. Transportation Science, 1997, Vol.31, No.3: 252-261
[87] Verter, Erkut. Incorporating insurance costs in hazardous materials routing models [J]. Transportation Science, 1997, Vol.31, No.3: 227-236
[88] Wijeratne, Turnquist, Mirchandani. Multiobjecive routing of hazardous materials in stochastic networks[J]. European Journal of Operational Research, 1993, 65: 33-43
[89] 王刊良．有害危险物品后勤学的研究动态[J]．系统工程理论与实践．2000，No.7：112-117
[90] 王刊良，徐寅峰，汪应洛．一个支持有害物品填埋场选址的决策支持系统[J]．系统工程理论与实践，1997，17(11)：60-65
[91] 陈利秋．中国有害废物污染现状控制对策探讨[J]．环境科学，1995，15(5)：83-87，
[92] 王刊良，张朋柱．有害危险物品运输风险的量化模型[R]．第五届全国青年管理科学与系统科学论文集[C]，天津：南开大学出版社，1999
[93] Miller-Hooks, Mahmassani. Least possible time path in stochastic, time-varying networks[J], Computers and Operations Research, 1998, Vol.25, No. 12: 1107-1125
[94] Sung, et al. Shortest path in a network with time-dependent flow speeds[J]. European Journal of Operational Research, 2000, 121: 32-39
[95] Prertolani. A directed hypergraph model for radom time dependent shortest paths[J]. European Journal of Operational Research, 2000, 123: 316-324
[96] Davies, Lingras. Genetic algorithms for rerouting shortest paths in dynamic and stochastic??networks[J]. European Journal of Operational Research, 2003, 144: 27-38
[97] National Commission on Intermodal Transportation, Toward a National Intermodal Transportation System[R], Final Report to Congress, US DOT, Washington, DC, 1994
[98] Rawlings, One System, Many Partners: Reflections of the Chicago Area Transportation Study's Intermodal Advisory Task Force[R]., 1997:97-17
[99] Cox, Turquist. Scheduling truck shipment of Hazardous Materials in the present of curfews[J]. Transportation Research Record, 1063, 1986: 21-26
[100] Elise D. M., Hani S. M.. Path comparisons for a priori and time-adaptive decisions in stochastic, time-varying networks[J], European Journal of Operational Research, 2003, 146: 67-82
[101] Athanasiso Z., Dimitrios K., Hani S. M.. Design and implementation of parallel time-dependent least time path algorithm for intelligent transportation systems applications [J], Transportation Research, Part C, 1997, 5(2): 95-107
[102] Current J, Marsh M. Multiobjective transportation network design and routing problems: taxonomy and annotation[J]. European Journal of Operational Research, 1993, 65: 1-15
[103] E. Erkut, V. Verter. Modeling of transport risk for hazardous materials[J]. Operatioins Research, 46, 1998: 625-642
[104] Dreyfus. An appraisal of some shortest path algorithms[J]. Operations Research, 1969, 17: 395-412
[105] Kaufuman, Smith. Minimum travel time path in dynamic networks with application to intelligent vehicle/highway systems[J]. IVHS journal, 1993, 1(1): 1-19
[106] Orda, Rom. Shortest path and minimum-delay algorithms in networks with time-dependent edge-length[J]. J. ACM, 1990, (37)3:607-625
[107] Orda, Rom. Distributed shortest path protocols for time dependent networks[J]. Distributed computing, 1996, 10(1): 49-62
[108] 谭国真，高文．时间依赖的网络中最小时间路径算法[J]．计算机学报，2003，Vol．25，No．2：165-172
[109] 陈宝林．最优化理论与算法[M]．北京：清华大学出版社．1989：20-58
[110] M.R. Garey, D.S. Johnson, Computers and intractability[M]. W.H. Freeman, San Francisco, CA, 1979
[111] 魏航，李军．时变条件下的有害物品运输的人口风险分析[J]．中国安全科学学报，2004，Vol．14，No.10：95-98
[112] Hanif D. Sherali, Kaan Ozbay, S. Subramanian. The time-dependent shortest pair of disjoint paths problem: complexity, models, and algorithms[J], Networks, 1998, 31: 259-272
[113] WEI Hang, LI Jun, PU Yun. Risk Analysis of Hazardous Materials Transportation[C].??2004 International Symposium on Safety Science and Technology
[114] M. Desrochers, F. Soumis. A generalized permanent lableling algorithm for the shortest path problem with time windows[J]. INFOR, 1988, 26: 191-212
[115] M. Desrochers, F. Soumis. A reoptimization algorithm for the shortest path problem with time windows[J]. European Journal of Operational Research, 1988, 35: 242-254
[116] M. Dror. Note on the complexity of the shortest path medels for column generation in VRPTW[J]. Operations Research, 1994, 42: 977-978
[117] J. Enrique Fernandez L., Joaquin de Cea Ch., Alexandra Soto O., A multi-modal supply-demand equilibrium model for predicting intercity freight flows[J]. Transportation Research PartB, 2003, 37: 615-640