时变条件下有害物品运输的路径选择与决策

李 飘，于影霞

（华东交通大学交通运输与物流学院，江西 南昌330013）

有害物品具有区别于其他一般物品的物理、化学、生物特性，是一种容易在生产、运输、储存等活动中发生爆炸、燃烧、中毒等灾害事故的某一类特殊物品[1]。根据有关研究[2-3]和数据发现，近年来，有害物品的生产和运输量都在逐年增加。 Wang N等[3]发现，在美国，在过去的十年中，每年有3 亿多吨与有害物质相关的运输；在我国，以2015 年为例， 有害物品运输的相关车辆和人员分别达到310 000 辆和120 万人，而有害物品运输的企业达到11 000 多家。 这些企业运输了约10 亿吨的有害物质，占所有有害物质运输方式的60%以上，在全球排名第二[2]。

由于有害物品运输车辆普遍呈现质心高、尺寸长、重量大和运载品危险性高等特点，导致其制动性能差， 碰撞和被追尾的概率高于一般物品运输车辆，且危害性大[4]。 另外，在实际行车过程中，驾驶员是能否保证安全运输的重要因素。 倘若驾驶员无法在行驶过程中获得及时、足量、合适的信息， 或受知识经验所限无法对所获信息做出正确的判断和分析，身临险境却无警告提示时，比较容易发生事故[5]。 因为这些危害特性及发展现状，使有害物品的运输成为研究的热点。 研究时变条件下有害物品运输的多目标路径选择问题， 找出符合各利益相关者的有效路径并进行综合评价优选，将有助于降低前者的运输成本和潜在风险，建构愈加完善的公共安全系统。

目前涉及到有害物品运输的路径选择问题，多集中在静态条件下的研究， 较少考虑到道路网络的时变特性等动态特征[6-7]。 动态条件下的但相对较近的研究是魏航[8-9]研究了有到达时间限制和允许在运输网络中等待的情况， 以及考虑了有害物品运输过程中有宵禁限制（curfews）的情况。 其次，需要同时考虑成本、风险等多个目标是有害物品运输区别于其他一般物品运输的重要特征[10]。近年来， 在多目标约束下的有害物品运输的研究几乎较少涉及到3 个目标， 几乎大部分都是双目标问题。 Pamucar 等[11]在城市道路网络有害物质运输路径多目标选择的问题上， 将成本和风险作为双目标进行考虑；Wei 等[12]将运输成本和受影响人数作为双目标，用基于模糊仿真的遗传算法（GA）来解决危险品运输路径问题。 另外，多目标最短路算法研究也多是在静态条件下进行的， 并且相当多的学者选择用线性加权的方式得到在有害物品运输的有效路径。

由上述研究成果可知：其一，目前对有害物的路径选择的研究，主要假设背景为静态环境，与现实复杂动态变化的情形有一定差距；其二，时变条件下的多目标优化问题中， 有害物品的运输大多集中在双目标的问题上，较少涉及到三个目标，不太能满足实际场景中多种多样的目标需求；其三，在处理多目标最短路的建模问题时， 一般考虑对多目标线性加权， 但实际上线性加权中的权重的确定比较困难， 因而会导致有效路径具有一定的主观性。

鉴于此，在时变条件下，同时考虑成本、环境风险和人口风险等因素，将动态规划的思想及扩展型Dijkstra 法、k-最短路径算法、逼近理想解排序法（technique for order preference by similarity to ideal solution，TOPSIS）运用到这篇论文中；构建多个不同出发时间且有到达时间限制的有害物品运输的多目标最短路径选择的数学模型；设计多目标最短路径选择和决策的算法；最后给出一个算例, 验证算法的可行性， 以期为复杂动态情景中的有害物品运输的多目标路径决策提供策略支持。

1 问题描述

一般地，在静态网络运输路径问题中，车辆被假定在0 时刻从车场出发，不考虑行驶成本、风险以及行驶时间的关系。 但在有害物品动态网络运输路径问题中， 现实生产生活中复杂多变的交通状况以及交通管制，往往导致行车时间、成本呈周期性变化。 在时变网络运输问题中，考虑将运输车辆的出发时间优化和路径优化结合起来， 才能得到比较有现实意义的优化方案。

在有害物品运输的多目标路径选择问题中[11-15]，因有害物品运输具有低概率高风险特性， 故风险和成本作为主要影响因子一般要被考虑在内。 但是，在实际运输情景中，有害物品运输对人以及环境的风险大小程度是不一样的， 笼统的将其归于一类，不符合真实场景下的各利益方（承运商、运营商、终端用户、政府机构、监管机构等）的抉择。将风险划分为对人的风险以及对环境的风险，在这里将对人的风险量化为人口覆盖率 （即该时段的人口覆盖率越高，人口风险越高），而对环境的风险表现为可能造成的区域内基础设施、 自然因素等的危害。 最后，将成本、环境风险、人口覆盖率作为本文时变条件下多目标优化问题中的三大主要目标。

2 模型建立

建立时变条件下，关于有害物品运输的多目标最短路的数学模型（有到达时间限制），定义如下变量

3 算法

3.1 基本定义

为了获得时变条件下多目标最短路的算法，这里参考文献[10]并给出如下两个定义：

定义1 若r=（O=1，2，…，s=D）为从起点O 到终点D 之间的一条路径，令t1=s（O），令t1为到达节点i 的时间，t1=ti-1+t（i-1，i，ti-1），ti-1为到达节点i-1 的时间，2≤i≤s，u∈U（O）。

3.2 算法步骤

基于动态规划的思想分析时变条件下的多目标最短路：通过将每一到达时间的最短路不断迭代并向后推移，直到求得到达终点的最短路。 另外，这里将运用到标号法， 这是一种能在同一阶段状态下，同时给出不同因素、目标值的数学方法[10]。 由于这里探讨的是时变条件下的有害物品运输的最短路问题，故是在原始标号形式上进行扩展。 逼近理想解排序法（TOPSIS 法）是一种多指标多方案的综合评价方法，它的原理是根据待评价对象和理想化目标的接近程度，对其进行相对优劣排序，具有概念简单、易于操作的特点[16]。

算法步骤如下：

步骤1：将运输网络进行划分，得到阶段数Q，令初始阶段q=0。

步骤2：对各个节点的标号进行初始化，选取U（O）中的最小值u，并对起点以临时标号[（I，0，…，0，u），（-，-，-）]1，0。

步骤3：获得Nij，Nq为阶段q 的所有节点集合。步骤4：对所有i=Nij依次进行以下步骤。

1） 搜索所有的j∈FS（i），FS（i）为在节点的所有前向节点的集合，（i，j）∈E。

2） 通过计算分别获得tj，l和zkj，l

5） 将Nq中的所有节点的标号进行对比， 计算并得到不同到达时间的有效路径及永久标号。

6） 令q=q+1。

步骤5：若q＞Q，对比终点D 的所有标号，然后按照目标值的大小对这些标号进行排序，得到其中目标值最小的标号。 然后根据这些标号逆向推导，从而获得出发时间为的最短路；否则，转步骤3。

步骤6：若Q O=φ，结束；否则转步骤2。

步骤7：获得最短路径集合∏。

步骤8：分别求出目标q（q=1，2，…，Q）的最小值minAq，并给出目标q（q=1，2，…，Q）的上限；Aupqq（q=1，2，…，Q）。

步骤9：得到上限为Aupq（q=1，2，…，Q）的路径集合Ωq（q=1，2，…，Q）。

步骤13：运用TOPSIS 法求解各方案有效路径的贴近度。 通过计算各个有效路径与正、负理想解的欧氏距离，进而计算各个方案点的贴近度，并在此基础上进行贴近度的排序， 从而判断方案的优劣。 决策原则是贴近度越大越好。

1） 首先将决策矩阵化为规范化矩阵，由原始数据经归一化处理后得到

2） 构造加权的规范化矩阵Gij

其中Wj表示第j 个指标的权重。

3.3 算例

有害物品的运输风险受现实环境中各种外界因素的影响，其运输过程是动态变化的。 在现实情境中，运输有害物品的路线可能是复杂多变，运输途中也存在随时停靠的可能性（这就造成了对该区域潜在的风险），过于复杂而不便模拟，所以本文参考文献[10]中的经典运输网络模型。 另外，每个途径节点的人口覆盖率等数据将参考文献[8]中各时刻运输成本和风险，引用文献[10]中的人口覆盖率和运输时间，如表1 所示。

以图1 为例。 假设在时刻0 时， 车辆从起点O出发，同时，每隔一个小时整点出发一次，最终在24 时前到达终点D。求从起点O 到终点D 之间的最短路。

图1 运输网络Fig.1 Transportation network

表1 各条有向边在不同时间条件下的运输成本、环境风险、人口覆盖率和运输时间Tab.1 Transportation costs, environmental risks, population coverage and transportation time of each article with directional edges under different time conditions

运用动态规划和扩展的Dijkstra 标号法，可以获得从不同时间点出发的各个节点的相关标号，如表2所示。

接着，选取不同的出发时间，在上文所给算法和表2 的基础上分别求得不同出发时间下的最短路，结果如表3 所示。

表2 各个节点的标号Tab.2 Labels of each node

表3 考虑成本、环境风险和人口覆盖率3 个目标的最短路Tab.3 Considers the short-circuit of the three objectives of cost, environmental risk and population coverage

由表3 可知，考虑3 个目标时，一方面不同的出发时间对应有多条有效路径可供选择。 另一方面，各个有效路径各个目标值亦会随出发时间的不同而不同。 倘若出发时间超过13 时，则到达时间超过24 时，不符，则此时无可行路径。

在考虑3 个目标时，每一个时间点（0≤T≤13）出发情况下的有效路径的数量大于等于2 条，这使得决策者具有符合自己实际需求的多种选择。 但也增加了决策者决策的困难。 这里假设决策者决策具有偏好性，即每个目标在决策者进行决策时分别占有不同的重要程度，设3 个目标：

目标1 为成本；

目标2 为环境风险；

目标3 为人口覆盖率。

假设根据决策者的需求偏好，3 个目标对应的权重分别为0.2，0.3，0.5。

由表3 得出各个目标的k-最短路径及目标值见表4。

表4 与目标对应的不同出发时间下的k-最短路径及相应的目标取值Tab.4 K-shortest paths corresponding to different departure times and corresponding target values

由表4 可以得到目标1，2，3 在不同出发时间下的最短路径以及对应的最小目标值分别为110，50，130。 接着取不同的目标上限，得到集合，见表5。 当

表5 不同目标的上限下的有效路径集Tab.5 Effective path sets under the upper limit of different targets

根据式（10）建立规范化决策矩阵Zij

根据式（11）建立加权的规范化决策矩阵Gij

由于上述3 个指标都为成本型指标，则加权的规范化决策矩阵可得D+和D-：

理想点D+=0.055，0.098，0.0163；

负理想点D-=0.075，0.128，0.185。

由式（12）式（13）可分别求得：

A1和A2的环境风险和人口覆盖率最小，且这2个指标所占权重也最大；虽然成本指标排序较为靠后，按数值大小排第3 位，但因由于其权重不大，并且成本排第2 的数值与排第3 的数值相差不大，所以综合评价后排在第1 位。 方案A3和A4的环境风险和A1、A2相同， 但其权重最大的人口覆盖率比A1、A2大；虽然其成本A1、A2略小，但由于其所占权重较小，因此综合评价后排在第2 位。 方案A6和A7的成本和环境风险都比A3、A4大， 且上述两个指标的权重之和达到0.5， 虽然人口覆盖率同样比重也达到0.5，但与方案A3、A4数值相差不大，故综合评价后排在第3 位。 方案A5的环境风险和人口覆盖率都比A6、A7大，并且以上两个指标的权重最大；虽然成本比A6、A7略小，但因其比重最小，故综合评价后排在第4 位。 A8的环境风险和人口覆盖率最大，这两个影响因子所占的比重也最大，虽然其成本最小，但由于其所占比重最小，因此综合评价后排在第5 位。

4 结论

1） 通过动态规划的思想和扩展型的Dijkstra法，根据不同的运输阶段和状态，给出不同的因素和目标值，算出不同出发时间下的多目标限制条件下的有效路径集。 有效地克服了时变条件下用线性加权解决有害物品运输的多目标路径选择问题具有主观性的局限， 能得出更为客观的有效路径集。同时，将风险细分为环境风险和人的风险，是对有害物品运输过程中人的因素的重视。

2） 综合运用k-最短路径和TOPSIS 法的综合评价算法对多目标有效路径集进行比较和优选，有效的克服了决策环境的复杂度以及决策者理性的有限性的问题，最终得到符合决策者的意志的满意路径。

3） 从动态的角度研究时变条件下的有害物品运输问题， 能更真实模拟现实情境中受交通事故、天气变化、交通管理等因素影响，使路网中各路段的安全性、运行成本等具有差异性的情景。