Safety scheduling of hazardous materials transportation vehicle considering spatio-temporal dissimilarity
-
摘要: 为确保危险品运输车辆间的安全距离, 从时空角度优化了危险品运输车辆的行驶路径和发车时间间隔; 分析了危险品运输车辆发生事故对其他车辆的影响及其与时空距离的关系, 提出了危险品运输车辆间时空安全距离评价方法, 并以时空安全距离为约束, 提出了车辆安全出发时间间隔计算方法; 建立了满足时空相异约束的危险品运输车辆调度模型, 设计了用于生成车辆调度时刻表的两阶段求解方法, 第1阶段采用NSGA-Ⅱ算法优化车辆行驶路径, 第2阶段分别设计了遗传算法和基于插入思想的近似算法以优化发车时间间隔; 为了验证车辆调度模型与算法的有效性, 对比了每个阶段中不同算法的优劣, 并分析了危险品事故影响系数和事故影响接受度对车辆调度结果的影响。研究结果表明: 提出的方法可针对不同危险品事故影响系数获得危险品运输车辆调度时刻表, 生成的车辆调度时刻能够保证车辆在行驶过程中始终保持安全距离; 遗传算法和近似算法获得的平均运输总时间分别为2.45和2.49 h, 表明近似算法获得的解劣于遗传算法, 但运行时间仅为遗传算法的1/10 000~1/5 000;危险品事故影响系数或事故影响接受度越小时, 车辆发车时间间隔越大, 导致运输总时间变长; 考虑时空相异性的车辆调度可以弥补相异路径方法仅从空间上考虑相异性的不足, 同时能够避免采用相异路径方法可能遗漏最佳运输路径的问题。Abstract: To ensure a safety distance between the hazardous materials transportation vehicles, the travel routes and departure time intervals of hazardous materials transportation vehicles were optimized in term of space-time. The impact of hazardous material transportation vehicle accident on other vehicles and the relationship between the hazardous material transportation vehicle accident and the spatio-temporal distance were analyzed, an evaluation method of spatio-temporal safety distance between vehicles was proposed, and taking the spatio-temporal safty distance as a constraint, the calculation method of vehicle safety departure time interval was proposed. A scheduling model of hazardous material transportation vehicle satisfying the spatio-temporal dissimilarity constraint was established. A two-stage solution method was designed to generate the vehicle scheduling timetable. The NSGA-Ⅱ optimization algorithm was used to optimize the travel route of vehicle at the first stage. The genetic algorithm and approximation algorithm based on the inserting thought were designed to optimize the departure time interval at the second stage. To verify the effectiveness of vehicle scheduling model and algorithm, the advantages and disadvantages of different methods at each stage were compared, and the influences of hazardous material accident impact factor and accident impact acceptance on the scheduling results were analyzed. Research result shows that the proposed method can obtain hazardous material transportation vehicle scheduling timetables with different hazardous material accident impact factors, and always ensure the vehicles a safe distance during driving. The average total transportation times obtained by the genetic algorithm and approximation algorithm are 2.45 and 2.49 h, respectively, indicating that the optimal solution of approximation algorithm is inferior to that of genetic algorithm, but the run time is only 1/10 000-1/5 000 of that of genetic algorithm. The smaller the hazardous material accident impact factor or the accident impact acceptance, the larger the vehicle safety departure time interval is, which leads to a longer total transportation time. The vehicle scheduling considering the spatio-temporal dissimilarity can compensate for the deficiency of dissimilar routing method only considering the spatial dissimilarity. At the same time, using the dissimilar routing method can prevent the problem of missing the optimal transportation route.
-
图 2 带时间轴的三维坐标系中的车辆位置
Figure 2. Vehicle positions in 3D coordinate system with time axis
图 3 带时间轴的三维坐标系中不同出发时刻下的车辆位置
Figure 3. Vehicle positions under different departure times in 3D coordinate system with time axis
图 4 车辆1不同出发时刻下的时空距离投影
Figure 4. Space-time distance projections of vehicle 1 under different departure times
图 7 不存在共同节点或路段的2条路径上的车辆距离
Figure 7. Vehicle distance on two paths without common node or road segment
图 8 存在逆向经过共同路段的2条路径上的车辆间距离
Figure 8. Vehicle distance on two paths when passing through same road segment in reverse
图 12 第1阶段采用NSGA-Ⅱ算法获得的Pareto最优解集
Figure 12. Pareto optimal solution sets obtained by NSGA-Ⅱ algorithm at first stage
图 13 第2阶段采用不同算法获得的运输总时间比较
Figure 13. Comparison of total transportation times obtained by different algorithms at second stage
图 14 不同α下运输总时间对比
Figure 14. Comparison of total transportation times under different α
图 15 不同ε下运输总时间对比
Figure 15. Comparison of total transportation times under different ε
表 1 路段运输距离和运输风险
Table 1. Transportation distances and risks of road segments
路段 运输风险 运输距离/km 行驶速度/ (km·h-1) 1→4 0.001 8 17.09 45 1→3 0.001 5 8.00 30 1→2 0.001 1 5.66 35 4→8 0.004 0 20.88 40 4→6 0.000 8 10.00 45 3→4 0.000 3 10.00 30 3→6 0.003 5 16.00 30 2→3 0.000 2 5.66 30 2→5 0.000 9 12.37 40 5→7 0.001 2 16.28 40 6→8 0.003 5 12.00 30 6→7 0.000 5 8.94 30 7→8 0.002 2 8.94 35 
下载: 导出CSV
表 2 Pareto最优运输路径集
Table 2. Pareto optimal transportation path sets
路径编号 路径 运输风险 运输距离/km 1 1→2→3→4→6→7→8 0.005 1 49.20 2 1→2→3→4→8 0.005 6 42.19 3 1→2→5→7→8 0.005 4 43.24 4 1→3→6→8 0.008 5 36.00 5 1→4→6→7→8 0.005 3 44.98 6 1→4→8 0.005 8 37.97
下载: 导出CSV
表 3 选定运输方案30下的车辆出发时刻(近似算法)
Table 3. Vehicle departure times under selecting transportation programme 30 (approximation algorithm)
车辆编号 路径编号 出发时刻 车辆编号 路径编号 出发时刻 1 6 08:00 11 6 08:40 2 6 08:04 12 6 08:44 3 6 08:08 13 6 08:48 4 6 08:12 14 6 08:52 5 6 08:16 15 6 08:56 6 6 08:20 16 6 09:00 7 6 08:24 17 3 09:04 8 6 08:28 18 5 09:08 9 6 08:32 19 5 09:13 10 6 08:36 20 6 09:27
下载: 导出CSV
表 4 选定运输方案30下的车辆出发时刻(遗传算法)
Table 4. Vehicle departure times under selecting transportation programme 30 (genetic algorithm)
车辆编号 路径编号 出发时刻 车辆编号 路径编号 出发时刻 1 6 08:00 11 6 08:40 2 6 08:04 12 6 08:44 3 6 08:08 13 6 08:48 4 6 08:12 14 6 08:52 5 6 08:16 15 5 08:56 6 6 08:20 16 6 09:00 7 6 08:24 17 3 09:04 8 6 08:28 18 6 09:16 9 6 08:32 19 5 09:20 10 6 08:36 20 6 09:24
下载: 导出CSV
-
[1] 赵岩. 诊治危险品运输事故急症[J]. 中国公路, 2016 (3): 69-71. https://www.cnki.com.cn/Article/CJFDTOTAL-GLZG201603031.htmZHAO Yan. Diagnosis and treatment of emergency for dangerous goods transportation accident[J]. China Highway, 2016 (3): 69-71. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-GLZG201603031.htm [2] KEENEY R L. Equity and public risk[J]. Operations Research, 1980, 28 (3): 527-534. [3] AKGÜN V, ERKUT E, BATTA R. On finding dissimilar paths[J]. European Journal of Operational Research, 2000, 121 (2): 232-246. doi: 10.1016/S0377-2217(99)00214-3 [4] LOMBARD K, CHURCH R L. The gateway shortest path problem: generating alternative routes for a corridor location problem[J]. Geographical Systems, 1993, 1 (1): 25-45. [5] KUBY M, XU Z Y, XIE X D. A minimax method for finding the k best "differentiated" paths[J]. Geographical Analysis, 1997, 29 (4): 298-313. [6] 何瑞春, 李引珍. 最佳相异度相异最短路径的遗传算法[J]. 兰州交通大学学报(自然科学版), 2005, 24 (3): 116-119. https://www.cnki.com.cn/Article/CJFDTOTAL-LZTX200503032.htmHE Rui-chun, LI Yin-zhen. Genetic algorithms for finding dissimilar shortest paths based on best dissimilar measure[J]. Journal of Lanzhou Jiaotong University (Natural Science), 2005, 24 (3): 116-119. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-LZTX200503032.htm [7] DELL'OLMO P, GENTILI M, SCOZZARI A. On finding dissimilar Pareto-optimal paths[J]. European Journal of Operational Research, 2005, 162 (1): 70-82. doi: 10.1016/j.ejor.2003.10.033 [8] LI Yin-zhen, HE Rui-chun, LIU Lin-zhong, et al. Genetic algorithms for dissimilar shortest paths based on optimal fuzzy dissimilar measure and applications[C]//Springer. International Conference on Fuzzy Systems and Knowledge Discovery. Berlin: Springer, 2005: 312-320. [9] 李引珍, 何瑞春, 郭耀煌, 等. 多目标网络相异路径的Pareto解及其遗传算法[J]. 系统工程学报, 2008, 23 (3): 264-268. https://www.cnki.com.cn/Article/CJFDTOTAL-XTGC200803003.htmLI Yin-zhen, HE Rui-chun, GUO Yao-huang, et al. Pareto solution set and its genetic algorithm for multi-objective network dissimilar paths[J]. Journal of Systems Engineering, 2008, 23 (3): 264-268. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-XTGC200803003.htm [10] 马昌喜, 何瑞春, 熊瑞琦. 基于双层规划的危险货物配送路径鲁棒优化[J]. 交通运输工程学报, 2018, 18 (5): 165-175. http://transport.chd.edu.cn/article/id/201805016MA Chang-xi, HE Rui-chun, XIONG Rui-qi. Robust optimization on distributing routes of hazardous materials based on bi-level programming[J]. Journal of Traffic and Transportation Engineering, 2018, 18 (5): 165-175. (in Chinese). http://transport.chd.edu.cn/article/id/201805016 [11] 代存杰, 李引珍, 马昌喜, 等. 考虑风险分布特征的危险品运输路径优化[J]. 中国公路学报, 2018, 31 (4): 330-342. doi: 10.3969/j.issn.1001-7372.2018.04.038DAI Cun-jie, LI Yin-zhen, MA Chang-xi, et al. Transportation path optimization for hazardous materials considering characteristics of risk distribution[J]. China Journal of Highway and Transport, 2018, 31 (4): 330-342. (in Chinese). doi: 10.3969/j.issn.1001-7372.2018.04.038 [12] LIM Y, RHEE S. An efficient dissimilar path searching method for evacuation routing[J]. KSCE Journal of Civil Engineering, 2010, 14 (1): 61-67. doi: 10.1007/s12205-010-0061-4 [13] KANG Y Y, BATTA R, KWON C. Generalized route planning model for hazardous material transportation with VaR and equity considerations[J]. Computers and Operations Research, 2014, 43 (1): 237-247. [14] TALARICO L, SÖRENSEN K, SPRINGAEL J. the k-dissimilar vehicle routing problem[J]. European Journal of Operational Research, 2015, 244 (1): 129-140. doi: 10.1016/j.ejor.2015.01.019 [15] PUSHAK Y, HARE W, LUCET Y. Multiple-path selection for new highway alignments using discrete algorithms[J]. European Journal of Operational Research, 2016, 248 (2): 415-427. doi: 10.1016/j.ejor.2015.07.039 [16] YEN J Y. Finding the k-shortest loopless paths in a network[J]. Management Science, 1971, 17 (11): 712-716. doi: 10.1287/mnsc.17.11.712 [17] XU W, HE S, RUI S, et al. Finding the k shortest paths in a schedule-based transit network[J]. Computers and Operations Research, 2012, 39 (8): 1812-1826. doi: 10.1016/j.cor.2010.02.005 [18] LAWLER E L. A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem[J]. Management Science, 1972, 18 (7): 401-405. doi: 10.1287/mnsc.18.7.401 [19] LIU Lin-zhong, MU Hai-bo, YANG Ju-hua. Simulated annealing based GRASP for Pareto-optimal dissimilar paths problem[J]. Soft Computing, 2017, 21 (18): 5457-5473. doi: 10.1007/s00500-016-2137-7 [20] MARTÍ R, VELARDE J L G, DUARTE A. Heuristics for the bi-objective path dissimilarity problem[J]. Computers and Operations Research, 2009, 36 (11): 2905-2912. doi: 10.1016/j.cor.2009.01.003 [21] CONSTANTINO M, MOURÃO M C, PINTO L S. Dissimilar arc routing problems[J]. Networks, 2017, 70 (3): 233-245. doi: 10.1002/net.21763 [22] THYAGARAJAN K, BATTA R, KARWAN M H, et al. Planning dissimilar paths for military units[J]. Military Operations Research, 2005, 10 (1): 25-42. doi: 10.5711/morj.10.1.25 [23] YAN S Y, WANG S S, WU M W. A model with a solution algorithm for the cash transportation vehicle routing and scheduling problem[J]. Computers and Industrial Engineering, 2012, 63 (2): 464-473. doi: 10.1016/j.cie.2012.04.004 [24] BATTA R, CHIU S S. Optimal obnoxious paths on a network: transportation of hazardous materials[J]. Operations Research, 1988, 36 (1): 84-92. [25] 陆键, 刘禹杰, 马晓丽. 基于博弈论的危险品运输网络选线[J]. 中国公路学报, 2018, 31 (4): 322-329. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL201804038.htmLU Jian, LIU Yu-jie, MA Xiao-li. Game-theory-based hazardous materials transport network routing[J]. China Journal of Highway and Transport, 2018, 31 (4): 322-329. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL201804038.htm [26] 王磊, 华珺, 杨云峰, 等. 道路危险货物运输的系统动力学仿真研究[J]. 中国公路学报, 2018, 31 (8): 181-188, 196. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL201808021.htmWANG Lei, HUA Jun, YANG Yun-feng, et al. Study on system dynamics simulation of road dangerous cargo transportation[J]. China Journal of Highway and Transport, 2018, 31 (8): 181-188, 196. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL201808021.htm [27] CAROTENUTO P, GIORDANI S, RICCIARDELLI S. Finding minimum and equitable risk routes for hazmat shipments[J]. Computers and Operations Research, 2007, 34 (5): 1304-1327. [28] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6 (2): 182-197. [29] PULIDO F J, MANDOW L, DE LA CRUZ J L P. Multiobjective shortest path problems with lexicographic goal-based preferences[J]. European Journal of Operational Research, 2014, 239 (1): 89-101. [30] ALP E. Risk-based transportation planning practice: overall methodology and a case example[J]. INFOR: Information Systems and Operational Research, 1995, 33 (1): 4-19. [31] GARRIDO R A, BRONFMAN A C. Equity and social acceptability in multiple hazardous materials routing through urban areas[J]. Transportation Research Part A: Policy and Practice, 2017, 102: 244-260. [32] MACHUCA E, MANDOW L, DE LA CRUZ J L P, et al. Heuristic multiobjective search for hazmat transportation problems[C]//Springer. Conference of the Spanish Association for Artificial Intelligence. Berlin: Springer, 2011: 243-252. [33] DUQUE D, LOZANO L, MEDAGLIA A L. An exact method for the biobjective shortest path problem for large-scale road networks[J]. European Journal of Operational Research, 2015, 242 (3): 788-797. [34] GUO X L, VERMA M. Choosing vehicle capacity to minimize risk for transporting flammable materials[J]. Journal of Loss Prevention in the Process Industries, 2010, 23 (2): 220-225. -
点击查看大图
计量
- 文章访问数: 1038
- HTML全文浏览量: 192
- PDF下载量: 353
- 被引次数: 0
