孙建峰
兰州交通大学 数理学院，甘肃 兰州 730070）
摘要：探究如何使交通规范化和交通合理化，对交通方面进行有效的管理，使危险品运输路径更加的合理和运输过程更加安全是我们现如今研究的一大难题。危险品不同于一般普通货物，如果在运输危险品时出现了不安全状况，不仅对沿线居民的生活造成威胁，而且对周围环境和设施也会带来不可恢复的污染与破坏。对于危险品运输路径优化算法也是现如今重要的一项研究问题，本文对现有相关研究进行整理和分类，把危险品运输路径优化算法的研究分为两大类，即传统的算法研究和群智能的算法研究。最后，在梳理相关研究优缺点的基础上，分析了现有研究中可以改进和完善的内容，并总结了未来研究的趋势和重要方向。
关键词：危险品运输；路径选择；算法分析；综述
Abstract: Exploring how to standardize and rationalize traffic, conduct effective management of traffic, and safer transportation process is a major problem in our research today. Dangerous goods are different from ordinary goods. If there are unsafe conditions when the transportation of dangerous goods, they will not only cause a threat to the lives of residents along the line, but also will bring irreparable pollution and damage to the surrounding environment and facilities. The dangerous goods transport path optimization algorithm is also an important research problem today. This paper arranges and classifies the existing relevant research, and divides the research of the dangerous goods transport path optimization algorithm into two categories, namely, the traditional algorithm research and the algorithm research of group intelligence. Finally, on the basis of sorting the advantages and disadvantages of related research, it analyzes the improvement and summarizes the trend and important direction of future research.
Key words: Dangerous goods transportation; risk analysis; algorithmic analysis; and a review
0 引言
危险品运输路分析的方法在危险品运输路径选择中占重要的地位，是影响其的一个重要因素，它对于危险品运输路径的最优化选择有了一个针对性和科学性的解决办法。
随着时代的发展和科技的进步，人们的生活水平越来越好。他们旅行时基本上都开私家车，但是这一情况造成了交通问题和出行安全问题，尤其是在危险品运输车辆在身边时，对于自身的生命安全也存在着威胁，对于自身与危险品运输者同时有着巨大的影响。事故一旦发生，还会造成许多人员伤亡和其他损失，直接或间接的经济损失也不计其数。
在运输网络中，道路危险货物运输是对人民生命财产安全的重要考验。在当今社会，对于危险品运输问题，不仅需要考虑运输时间和运输成本，最主要的还需要考虑运输风险的因素。传统的路径选择仅仅是以成本分析为基础，很少去关注危险品运输的风险因素，这样就导致路径选择存在了较大的缺陷与问题。介于以上情况，好多学者研究了交通网络中危险品运输中路径选择风险因素对于运输路径的选择影响，并且研究了危险品运输路径选择优化的算法，对于各种算法进行了总结和对比。
2 危险品运输路径优化算法分析研究现状
早期的学者运用传统的算法来研究路径运输选择问题，而随着时代的发展，人工智能领域的突破，各学者利用群智能算法研究路径择优问题越来越广泛。
2.1 传统的算法研究
Weiser Stephan[1]提出了一种基于Dijkstra算法的路径搜索算法。该算法的目的是在两个局部极小点之间找到近似最深的路径，从而获得关于目标函数特性的信息。丁浩等[2]研究了如何利用Dijkstra算法快速找到快递车辆配送过程中的最短路径。孟庆伟等[3]提出了一种Dijkstra算法的改进算法,通过减小算法中成功搜索的搜索范围使算法得到优化,提高了搜索效率。吴红波等[4]利用网络拓扑、地理编码和网络分析,基于Dijkstra算法优化对车辆行驶路线进行选择。刘文婧等[5]以供电网络架设路程最短为目标,建立了优化的数学模型,利用图论中的Dijkstra算法有效解决了该问题。
常晨[6]提出了一种基于扩展搜索邻域的A-star算法的路径规划算法。余博文[7]主要针对A*算法的搜索效率、剪枝等问题进行优化,并得出改进后的最短路径搜索算法。李善梅[8]构建了机场场面滑行路径优化模型,并提出基于变步长的滑动时间窗方法和A*算法相结合的模型求解算法。
王腾龙[9]对已有的社区发现算法——标签传播算法LPA（Label Propagation Algorithm）进行了改进,形成了一种新的结点影响力标签传播算法NFLPA（Node Influence Label Propagation Algorithm）。
Zhao等[10]提出一种基于Floyd算法的传导变换最优协调路径选择方法。王靖东[11]对Floyd的原算法进行了优化，并与Dijkstra算法的设计效果进行了比较。邱晓鹏[12]在不改变时间复杂度的情况下,对Floyd算法进行优化改进,提高运算速度,降低空间复杂度。
表2 传统的危险品运输优化算法研究
研究者 名称 优点 缺点
Weiser Stephan[1]
丁浩等[2]孟庆伟等[3]
吴红波等[4]刘文婧等[5] Dijkstra算法 可解释性强，容易理解，可以使用数据量较少的场景 时间复杂度高，计算的是单源最短路径，它不是两点之间的最短路径，因此赋权图可能是错误的。
常晨[6]
余博文[7]
李善梅[8] A*算法 关注点到点的最短距离，可以更轻松地用在诸如游戏地图寻路中，不但记录其到源点的代价，还计算当前点到目标点的期望代价。 当目标点很多事，计算会带入大量重复数据和复杂的估价函数。
丁浩等[2]
孟庆伟等[3] D*算法 在动态环境中，路径发现是非常有效的。当移动到目标点时，只检查最短路径中上下节点或相邻节点的变化，如机器人寻径。 对于距离远的最短路径上的发生的变化，则感觉不太实用。
王腾龙[9] LPA算法 它具有简单性和时间效率，并且算法不要求事先设定社区的数量和大小。 算法中节点总是选择邻居节点的主要标签，而忽略所有其他存在与邻居节点的结构信息。
Zhao等[10]
王靖东[11]
邱晓鹏[12] Floyd算法 容易理解，可以计算两节点间最短距离的算法，程序简单
复杂度是立方的，因此不适合计算大量的数据。利用邻接矩阵存储边缘是必要的。该算法通过考虑最佳此路径得到最佳路径。
2.2 群智能的算法研究
El Rassy Elissa等[13]通过与遗传算法( GA )的比较，对该算法的效率进行了实证分析。Park Jai Hoon等[14]采用遗传算法进化机器人结构作为外部优化，对每个候选结构应用强化学习算法训练其行为，并作为内部优化评估其潜在学习能力。王志强等[15]结合遗传算法使用MATLAB软件计算出最符合客户需求的配送方案。朱桐等[16]建立了以距离成本和惩罚成本为目标的配送路径优化模型，并用混合遗传算法求解。肖胜荣[17]设计了一种改进的遗传算法，使总运营成本最小化。
Paniri Mohsen等[18]提出了一种新的基于蚁群优化( ACO )的多标签特征选择方法。李佳盛[19]基于有时间约束的VRP模型,提出了一种改进的蚂蚁算法,以克服蚁群算法收敛速度慢、易出现局部最优的不足。张万通等[20]利用城市路径规划蚁群算法,解决物流运输路径规划方面的调度问题。杨婷等[21]创建了一个软窗和硬窗车辆交通优化模型，并使用改进的蚁群算法优化车辆轨迹。
邢维等[22]根据实际问题背景建立一个物流配送的优化模型,建立解决路径优化问题的粒子群算法。王红艳[23]对传统的PSO算法进行改进,引入遗传算法中的交叉操作与启发因子,避免PSO算法在迭代过程中陷入局部最优的现象,降低了算法迭代的次数。薛翔等[24]构建以道路安全系数为约束的双目标混合整数规划模型,并设计基于优先权重的粒子群算法求解模型,通过Matlab平台仿真实现。
Yan等[25]提出了一种状态转移模拟退火算法( STASA )，该算法利用模拟退火的大都市准则来求解旅行商问题( TSP )，并做出显著的改进。裴小兵等[26]基于传统模拟退火算法,通过引入记忆函数、结合GIS手段,运用SPSS聚类分析来确定初始化状态种群、多种群并行机制和新状态的产生。田昀等[27]针对不同的目标条件选择了最佳路径，并用模拟算法对计算结果进行了优化。査伟雄等[28]以UE模型为下级模型，建立了危险品道路运输优化的双层规划模型并通过模拟退火算法求解了双层规划模型。
Jeong Taikyeong[29]通过在时间序列数据中加入行为智能数据，提出了一种新的数据连接模型——深度神经网络反馈模型。童友波[30]利用传感器采集智能车行驶路径的图像信息，得到智能车行驶路径的完整信息，并利用神经网络协作，最终完成智能车行驶路径的记忆。
王晓东等[31]采用模拟退火算法，得到较有可能的神经网络反馈值，克服了不足，其中网络算法的hopfield算法容易陷入局部最优解，这一缺点也被克服。王爱民等[32]基于惩罚性打击功能，设计了一种用于机器人运动规划的神经网络算法。
表3 群智能的危险品运输优化算法研究
研究者 名称 优点 缺点
El Rassy Elissa等[13]Park Jai Hoon等[14]王志强等[15]
朱桐等[16] 遗传算法 它具有良好的全局搜索能力，能快速搜索解空间中的所有解而不陷入局部最优解；利用其固有的并行性，有助于执行分布式计算并加速解决方案。 局部搜索能力差，导致简单遗传算法在进化后期耗时，搜索效率低。在实际应用中，遗传算法容易产生早熟收敛的问题。
Paniri Mohsen等[17]
李佳盛[18]
张万通等[19]
杨婷等[20] 蚁群算法 在求解性能上具有很强的鲁棒性和搜索较好解的能力，它本质上是并行的，易于实现。它可以与多种启发式算法相结合，提高算法的性能。 算法运算的计算量大，时间长，速度慢，它容易陷入局部最优，且缺乏初始信息素。
邢维等[21]王红艳[22]
薛翔等[23] 粒子群算法 它具有较快的逼近最优解的速度，能有效地优化系统的参数。 很容易产生过早收敛和局部的较差寻优能力。
Yan等[24]
裴小兵等[25]
田昀等[26]
査伟雄等[27] 模拟退火算法 它具有描述简单、使用灵活、适用范围广、效率高、不受初始条件限制等优点，有可能摆脱局部最优解，利用随机搜索技术，可以在概率意义下找到目标函数的整体最低点 算法运算效率不高。模拟退火算法对初始温度等参数依赖性强，发展缓慢。
Jeong Taikyeong[28]童友波[29]王晓东等[30]王爱民等[31] 神经网络算法 具有较强的非线性映射，高度自学习和自适应，具有一定的容错能力 其往往会收收敛于不同的局部。收敛速度慢，学习复杂应用实例与网络规模的矛盾。
2.3 算法的应用
以算法中的蚁群算法为例，运算步骤如下所示，
3 值得进一步深入研究的方向
其中各研究的主要缺点是难以体现成本和风险之间的权衡，路径选择研究的主要缺点是均可决策第一辆车的路径，但车辆路径问题求解难度相对较大，结合多目标问题的发展、车辆路径问题和求解技术，研究了多目标运输和车辆问题识别的主要发展趋势。总的来说，危险品运输车辆路径优化，至今仍保持着一定热度和良好的发展趋势，现有研究存在诸多可改进和完善的空间，也有很多新的问题尚待解决。
随着我国经济越加繁荣，人民生活安居乐业，一些工业和研究也随之对危险品的需求越来越多，但是绝大多数危险品并非当地生产就地使用，由生产地到使用地往往需要经过很长的一段距离运输。而在危险品运输的时候是最容易发生意外情况的时候，一旦发生意外，对于国家来说，会造成巨大的经济损失；对于地区来说，可能会带来化学污染；对于个人来说，更是可能会对道路沿线的人们生产生活造成巨大影响。
学者们针对危险品运输路径优化问题的算法进行了大量研究工作，上文已对现有研究进行了整理和分类，总结各类危险品运输路径优化算法的优点和缺点。主要问题在于对于不同问题的研究，有多种研究的目标与深度，在选择算法时，应该根据所需要研究的问题来选择对于研究该问题具有优势的算法，而不是盲目的应用一种与该研究对象背道而驰的算法。在危险品运输路径选择中，首先要着重考虑运输风险，否则即使节省了成本，但一旦发生事故，则损失的更加巨大。因此，我们要研究的应该是如何找到一种可以更加准确更加简便的来研究运输风险的算法。未来研究可更深入的探索贴近实际的风险度量，更多的结合多样化的风险度量，研究危险品运输车辆路径优化问题。在以后的研究中，可以运用最优的风险分析算法来研究危险品运输路径选择优化问题。
4 结束语
针对危险品运输路径选择问题的算法研究，人们常常只会想到传统的算法分析或者近现代兴起的群智能的算法分析，但是忽略了二者都是有其优点和不足的，所以，在以后的研究中，我们应该将传统的算法和群智能算法相结合，计算危险品运输时能够更加的准确，更加的简便。另一方面，研究者应该理论联系实践，对于现实生活中存在的危险品运输，我们需要考虑多个方面，与理论中的理想状态是不一样的，所以在研究过程中，需要结合实际，不仅要考虑成本还有考虑运输风险；不仅要考虑运输收益，还要考虑运输时间。所以，未来的研究需要更加深入，更深层次去建立符合实际，多目标动态的优化算法。
参考文献：
[1]Weiser Stephan，Wulf Hans，Ihlemann J?rn.Characterization of the objective function landscape using a modified Dijkstra algorithm[J]. PAMM,2021,1(20).
[2]丁浩，苌道方.基于Dijkstra算法的快递车辆配送路径优化[J].价值工程,2014,33(03),15-18
[3]孟庆伟,张冬姣.基于Dijkstra最短路径算法的优化及应用研究[J].电子商务,2014,(12):60-61
[4]吴红波,王英杰,杨肖肖.基于Dijkstra算法优化的城市交通路径分析[J].北京交通大学学报,2019,43(04):116-121+130
[5]刘文婧,朱睿,林远劲.一种基于Dijkstra算法的供电网络架设路径优化方法[J].节能,2020,39(09):27-29
[6]常晨.基于改进A-star算法的路径规划的研究及应用[D].江苏：南京大学，2020
[7]余博文.基于A*算法的最短路径搜索的优化与研究[J].数码世界,2019,(08):35-38
[8]李善梅，高艺.基于改进A*算法的机场场面滑行路径优化[J].计算机仿真,2020,37(03):27-32+228
[9]王腾龙.LPA算法改进及多维社会网的强关系社区发现[D].云南：云南大学，2018
[10]Zhao Yanwei,?Wu Gengyu,?Gui Fangzhi,et al.Optimal Coordination Path Selecting Method for Conduction Transformation Based on Floyd Algorithm[J].Procedia Computer ScienceVolume ,2019,(162):227-234
[11]王靖东.基于优化Floyd算法的室内机器人路径规划研究[D].陕西：西北农林科技大学，2015.
[12]邱晓鹏,王丽君.基于Floyd算法的最短路径优化研究[J].太原师范学院学报(自然科学版),2019,18(02):53-56+67
[13]El Rassy Elissa;?Delaroque Aurélie;?Sambou Patrick;?Chakravarty Harish Kumar;?Matynia Alexis.On the Potential of the Particle Swarm Algorithm for the Optimization of Detailed Kinetic Mechanisms. Comparison with the Genetic Algorithm[J].The Journal of Physical Chemistry ,2021.
[14]Park Jai Hoon;?Lee Kang Hoon.Computational Design of Modular Robots Based on Genetic Algorithm and Reinforcement Learning[J].SymmetryVolume, 2021, 3(13): 471-471
[15]王志强,岑枝.基于遗传算法的末端配送路径优化[J].商场现代化, 2020,(24):43-45
[16]朱桐,江欢.基于遗传算法的外卖配送路径优化研究[J].轻工科技, 2020,36(12):51-53+93
[17]肖胜荣.基于改进遗传算法的越库车辆调度和路径优化研究[D].广东：广东工业大学，2019.
[18]Paniri Mohsen;?Dowlatshahi Mohammad Bagher;?Nezamabadi pour Hossein.Ant-TD: Ant colony optimization plus temporal difference reinforcement learning for multi-label feature selection[J].Swarm and Evolutionary Computation2021.
[19]李佳盛.基于改进蚁群算法的旅行商路径优化问题研究[J].中国物流与采购,2020(17):47-48.
[20]张万通，吴浩，徐其飞.基于蚁群算法的物流网络路径优化研究[J].成组技术与生产现代化， 2020,37(02)：32-35
[21]杨婷，韩冬桂，燕怒，等.基于改进蚁群算法的软硬时间窗车辆路径优化[J].物流科技, 2019,42(09)：1-6
[22]邢维，裴红梅.粒子群算法在配送路径优化问题中的应用[J].物流科技， 2019,42(09)：1-6
[23]王红艳.基于粒子群算法的物流路径优化方法研究[J].电子设计工程， 2020,28(17)：61-65
[24]薛翔，朱小林.基于优先权重粒子群算法的危险品运输路径优化建模[J].大连海事大学学报, 2016,42(04):112-118
[25]Yan Zhang;?Xiaoxia Han;?Yingchao Dong;?Jun Xie;?Gang Xie;?Xinying Xu.A novel state transition simulated annealing algorithm for the multiple traveling salesmen problem[J].The Journal of Supercomputing2021,1-26
[26]裴小兵，贾定芳.基于模拟退火算法的城市物流多目标配送车辆路径优化研究[J].数学的实践与认识, 2016,46(02):105-113
[27]田昀,梁海龙.基于模拟退火算法的物流配送路径优化问题分析[J].交通科技与经济, 2013,15(05):85-88
[28]査伟雄,孙敬.基于模拟退火算法的危险货物道路运输路径优化双层规划模型[J].公路交通科技， 2012,29(04):101-106
[29]Jeong Taikyeong.Deep Neural Network Algorithm Feedback Model with Behavioral Intelligence and Forecast Accuracy[J].SymmetryVolume, 2020, 9(12):1465-1465
[30]童友波.基于协同神经网络的智能车行驶路径记忆算法优化[J].太原学院学报(自然科学版), 2019,37(03):79-83
[31]王晓东,薛明,齐兴敏.基于神经网络的配送路径优化算法[J].物流技术, 2015,34(18):157-159
[32]王爱民，史庆国，吕晨亮.机器人路径规划的神经网络算法及优化[J].河北工业大学学报,1999,(06):13-16