基于改进NSGA-Ⅱ算法的危险品运输路径优化研究

李 立，邓雨桐，牟玲玲

(河北工业大学经济管理学院，天津 300401)

危险品运输的安全问题已受到许多学者的持续关注。危险品运输事故不仅会对承运商等企业自身造成一定的损失，还会对道路通行以及周围环境造成严重的影响，甚至危及道路周边人员的人身安全，所以对危险品运输路径进行优化，降低事故发生概率，减轻事故造成的危害具有重要的现实意义。

目前我国针对危险品运输路径优化问题的研究主要集中反映在优化目标的选择上，不同的研究者会采用不同的优化目标，而早期的一些研究主要针对单一目标对路径进行优化。如刘浩学等根据模糊综合评价法的思想，建立了一套危险品运输安全评价指标体系，并根据该评价体系确定危害最小的运输路线方案并进行模糊综合计算；任常兴等依据Pareto的最优化处理方法，对多个危险品道路运输风险指标进行分析，并选出了最小运输风险路线；王云鹏等为了降低危险品城市运输危害，利用GIS对特定地区建立道路网络，并分析影响危险品城市运输的因素，考虑了事故产生的危害、事故造成的风险以及对事故的补救能力，建立了基于GIS的危险品城市运输路径优化模型。

近些年，我国越来越多的学者在危险品运输路径优化的研究方面开始趋向于多目标，但是偏向于静态分析。如夏秋等将人口暴露和环境污染两个指标用于计算危险品道路运输过程中不同路径的风险指数，并依据该指数选择最优路径；叶炽球在考虑危险品运输风险时加入社会恐慌度，并利用标号法和启发式算法求解模型；孙文斐等考虑危险品需求、时间以及风险3个约束条件建立了危险品运输路径优化模型，并选择粒子群算法求解模型；柴获等考虑3个优化目标，分别为经过某一区域的运输车总数最小、起讫点之间的运输总距离最短以及行驶在人口众多地区的距离最短，建立了危险品运输车辆调度优化模型并在多目标进化算法的基础上考虑概率因素对模型进行求解；张萌等通过改进经典的

ε

-约束法，对建立的以最大事故后果和最小运输成本为目标的危险品运输车辆路径优化模型进行求解；Hu等考虑了减少危险品运输总风险、总成本以及最大化客户满意度3个优化目标，建立了危险品运输多目标定位路径模型，并设计一种自适应权重遗传算法来获得模型的Pareto解。

除了上述研究外，我国还有一些学者在危险品运输路径多目标的研究中考虑了时间因素的影响。如项前等设置最小运输时间、最小事故概率和最小暴露人群的危险系数3个优化目标，建立了交通路径优化模型并利用改进的蚁群算法计算最优路径；代存杰等针对危险品运输的风险分布问题，考虑了政府和承运商不同角度的优化目标，建立了运输风险分布情况模型对运输中的风险大小、运输费用和时间进行联合求解最优解，随后又将到达时间窗加入约束条件，并根据危险品的运输时间、运输风险的期望值以及标准差为优化目标建立模型，对危险品运输路径选线进行了优化；孙文霞等提出了基于时间、风险、费用综合阻抗最小化的时间依赖网络模型的计算方法，并依据该算法选择危险品运输的最优路径。

在国外，对于危险品运输路径优化的研究在21世纪初就开始倾向于利用多目标来处理危险品运输的选线问题。如Leonelli等将危险品运输网络看作由节点和电弧构成的图，节点为路径交叉点，电弧为路径，考虑个体风险和社会风险进而定义电弧成本，把危险品运输路径优化问题转换为“最小成本流”问题；Kara等提出了一个新的双层规划模型，该模型代表了政府和承运商在确定危化品运输风险和运输成本时做出的不同决策以及它们之间的相互作用，并依据该模型确定危化品最佳运输路段；Zografos等以风险最小化、成本最小化为双目标建立了危化品运输路径优化模型，并通过改进Solomon 开发的相应插入算法解决具有时间窗的双目标车辆路径的优化问题；Alumur等提出了一种新的多目标定位路径模型，以解决危险废物的处置中心定位问题和如何将危险废物低成本、低风险地运输到处置中心的问题；Erkut等建立比较风险和成本的模型，提出该模型的启发式解决方法；Zero等引入模糊逻辑建立危险品运输路径选择模型，并提出了基于标签设置算法的两种拓展算法对模型进行求解。

综上所述，所有学者的研究都不可避免地将危险品运输事故风险作为危险品运输路径选择的优化目标，不同的学者对其建立的模型不同，但大部分学者都是采用静态分析方法进行建模，缺少动态分析，少部分学者考虑了时间窗作为约束条件对其建模，但所选方法较为复杂且较难体现动态分析的过程。鉴于此，本文为了深入研究时空变化对于危险品运输路径选择的影响，首先通过构建时空矩阵存储道路数据，将该数据作为模型的修正因子用以模拟事故率和事故后果，并结合成本因素建立综合、动态、多目标的危险品运输路径优化模型；然后通过改进NSGA-Ⅱ算法的编码方式和求解目标函数的方式实现对模型的求解；最后以出入天津港的疏港公路为研究区域进行了实证研究。

1 危险品运输路径优化模型

危险品运输的过程是动态变化的，因此本文以建立时空矩阵的形式来实现对危险品运输动态过程的描述，并赋予时空矩阵中每个元素一个新的数值。将危险品运输事故率与事故后果相结合，利用时空矩阵对其进行重新模拟计算，并结合成本因素建立危险品运输路径优化模型。

1.1 问题描述

危险品运输路径优化问题的研究可以描述为危险品运输车辆在路网

G

=(

N

，

A

)中选择一条最优的路径行驶，其中

N

表示路网中连接点的集合，设

n

表示路网中的特定的连接点，即

n

∈

N

；

A

表示路网中不同路段的集合，设

a

表示路网中特定的路段，即

a

∈

A

。由于道路状况每时每刻都在变化，因此要确定一个路段的风险情况还需要知道该路段所处的时间段。假设以到达点特定连接点

n

的时间点所在的时间段表示运输车辆处于以

n

为起点的路段的时间段。将一天中危险品可运输的时间划分为若干个时间段，

T

表示时间段的集合，

t

表示若干时间段中的一个，即

t

∈

T

。

1.2 时空矩阵构建

建立一个由

i

×

j

个元素组成的矩阵，即：

(1)

矩阵中，

i

为路网中路段的总数;

j

为划分的时间段的总数;

φ

表示路段

a

在时间段

t

内时所对应的数值。下面介绍该数值的计算方法。该数值的计算方法借鉴高峰小时系数的计算方法。高峰小时系数是指这一天中在某一小时内通过某一路段车辆最多的一小时内的所有车辆数占全天通过该路段的全部车辆数的比重。该系数可以反映客流量在全天最集中时所占全天客流量的比值，某一小时内的客流量越大，则该系数越大。根据该思想，本文假设某一时间段内路段的交通量越大，该时间段内所对应的

φ

值越大。因此，把全天24 h分为23个均等的时间段，在路段

a

上时间段

t

内的交通量占全天交通量的比重作为

φ

值，以此类推即可确定矩阵中各个元素的值。

1.3 影响因素

1.3.1 事故率

事故是指由于意外造成的损失或灾祸。事故率则是可能发生事故的概率。事故率是危险品运输事故风险的一个重要指标，事故率越大，表明危险品运输发生事故的可能性越大。事故率的计算方法可以根据事故统计数据作为依据，通过一定的计算得到。通过参考Abkowitz等的文献，将危险品运输事故率的值设定为

l

×10，该值在许多研究中得以应用。其计算公式如下：

p

=

l

×10

(2)

式中：

p

表示路段

a

上的事故率；

l

表示路段

a

的长度(km)。

1.3.2 事故后果

危险品运输事故后果即是指发生事故后造成的影响。根据危险品运输事故类型，可将其划分为有毒气体扩散、火灾和爆炸3种类型。其中,火灾分为池火灾、山火灾和喷火灾;爆炸分为自由蒸汽云爆炸和沸腾液体扩散蒸汽爆炸。不同的事故类型造成的事故后果不同。

在前人的许多研究中，危险品运输事故后果的严重程度主要采用事故波及的人口数来衡量。危险品运输事故无论是危险气体扩散，还是危险品发生燃烧甚至爆炸，都可能会对事故发生地周围的人员造成一定的影响，严重时甚至威胁生命安全。因此，本文对事故后果的研究中，也同样着重于危险品事故影响人数的计算。

本文研究的危险品运输事故影响的总人数由事故发生路段的内部人口数和该路段的周围人口数共同组成。假设路段周围的人口数固定不变，路段内部人口数随时间变化，其计算方法如下：

POP

,=

pop

,,in+

pop

,out

(3)

pop

,,in=

m

×

V

,

(4)

V

,=

T

×

φ

(5)

pop

,out=

S

×

λ

(6)

式中:

POP

,表示路段

a

在时间段

t

内发生事故受影响的总人数(人)；

pop

,,in表示在时间段

t

内路段

a

内部的总人数(人)；

pop

,out表示路段

a

外部受事故影响的总人数(人)；

m

表示平均一辆车所承载的人数(人)；

V

,表示路段

a

在时间段

t

内通过的车辆数(辆)；

T

表示路段

a

一天内通过的车辆数(辆)；

φ

表示时空矩阵中相应的修正系数；

S

表示危险品运输发生事故所影响周边地区的总面积(km)；

λ

表示路段

a

周边地区的人口密度(人/km)。

1.3.3 运输成本

由于人力成本是个固定值，油耗成本是与路程长短相关的线性函数，所以危险品的运输成本

C

可表示为与运输距离相关的线性函数。设

ε

表示每公里油耗成本，危险品的运输成本可表示如下：

(7)

1.3.4 车辆到达时间

不同时间段内道路的交通量不同，而最适合描述路段通行时间与路段交通量之间关系的函数是路阻函数。本文采用BRP路阻函数模型来计算危险品运输车辆在路段

a

上处于时间段

t

内的实际通行时间。该函数模型的计算方法为

f

,=

l

[1+

α

(

V

,/

C

)]/

v

(8)

式中：

f

,表示危险品运输车辆在路段

a

上处于时间段

t

内的实际通行时间(min)；

l

表示路段

a

的长度(km)；

C

表示路段

a

的通行能力；

v

表示车辆在该路段交通量为零时自由行驶的速度；

α

和

β

为待标定系数。根据时间段

t

以及路段

a

的不同可由公式(8)计算出相应路段的实际通行时间。车辆到达路段

a

时所用的通行时间表示为该车辆经过之前

n

个连接点的通行时间之和。

1.4 危险品运输路径优化模型建立

传统的危险品运输风险的确定方法为事故率和事故影响人数的乘积，该方法只是分析静态运输网络的运输风险。然而在危险品实际运输过程中，考虑到受时间因素的影响，不同的时间段内发生事故的概率以及受影响的人数是不同的。因此，依据本文构建的时空矩阵，模拟真实的危险品运输事故率和事故后果，并结合成本因素，建立了危险品运输路径优化模型如下：

(9)

(10)

(11)

式中:

TR

(

P

)表示危险品运输过程起讫点之间所有路径的风险值之和；

p

表示路段

a

发生事故的概率。

2 模型求解算法设计

通过比较Deb等在文章中介绍的NSGA-Ⅱ算法和NSGA-Ⅲ算法可知，前者更适用于双目标模型的求解，而后者适用于3个及以上的多目标模型的求解。因此，本文采用NSGA-Ⅱ算法，并对该算法进行了改进。

首先，在算法模块中，传统的NSGA-Ⅱ算法采用二进制编码方式，虽然该编码方式直观、方便，但在解码过程中生成的路径往往不能连通成一个完整的行驶路径，从而导致在求解每一条染色体的目标函数值时，出现不满足约束矩阵的情况。因此，本文采用基于优先级的编码方式来代替传统的二进制编码方式。

基于优先级的编码方式是一种间接编码方式，该编码方式的特点是染色体的每一位元素互不相等，拥有其独有的编码和解码规则。编码需要构造编码函数，加入路径中连接点的数据并随机生成个体完成实例化。编码成的每条染色体不直接表示路径，需要有独特的解码方式进行解码得到路径。该编码方式采用的是自然数排列编码，简单易懂。解码需要一个解码矩阵，用于存储以各个连接点为起点的有向边的终点，即该连接点可到达的下一个连接点。无论如何编码，依据道路的连通规则设置的解码矩阵均可翻译出一条合理的路径。因此，本文自行设计了编码矩阵和解码矩阵。

下面举例说明基于优先级的编码方式。编码形成的染色体见表1，路径连接图见图1，行驶方向为从编号小的连接点到编号大的连接点，则该条染色体所表示的路径为1-4-7-8-9。可见，该编码方式一定可以翻译出一条连通的路径。

表1 染色体编码

图1 路径连接图Fig.1 Path connection diagram

其次，针对自定义问题模块，传统的NSGA-Ⅱ算法只能解决静态的双目标问题，而本文所设计的模型中的数据需要依据时间路段的不同而动态地发生变化。因此，本文在设计NSGA-Ⅱ算法自定义问题模块时，采取加入判断跨越时间段语句，如果跨越则调用下一时间段数据，否则，就不需要调用，以求解不同时间段不同路径的函数值。同时，在数据输入部分输入各个时间段的全部数据。

本文设计的模型求解算法的步骤如下：

Step1:设计自定义问题模块，在该模块中输入上文建立的模型及相应数据，并加入判断跨时间段语句。

Step2：设置编码规则，采用基于优先级的编码方式对染色体进行编码，构造编码、解码矩阵。

Step3：生成初始种群，对初始种群进行非支配型排序。

Step4：进行选择、交配、变异等操作产生第一代子代种群。

Step5：将父代和新产生的子代合并。

Step6：将合并后的种群快速非支配型排序，并计算它们的拥挤度。

Step7：根据非支配关系和拥挤度筛选出合适的个体组成新的父代。

Step8：进行选择、交配、变异等操作产生子代。

Step9：重复上述Step5～8，直到满足条件。

3 实证研究

本文以天津港为例，验证该模型及算法。天津港位于天津市的滨海新区，是海河的入海口。天津港所处的地理位置独特，其既属于京津冀城市群，又处在环渤海经济圈的范围内，因此天津港是我国北方的一个重要港口，其对于我国北方的贸易往来有着重要的影响。天津港占地面积为132 km，虽然其占地面积较小，但天津港的腹地可延伸至东北、华北甚至是西北地区，包含了14个省(区、市)，总面积约500万km，同时可连接东北亚和中西亚，未来面积将会更大。

往返天津港的危险品运输路线以天津港为中心点向内陆延申，其中高速公路有京津高速、京津塘高速、滨石高速、京台高速、荣乌高速、海滨高速、津滨高速、长深高速等，国道有103，省道有106、217、312、105、206等。这些路线势必要经过天津市滨海新区，而滨海新区是天津市一个重要市辖区，其人口密度较大，再加上天津港的货物运输量大，尤其是危险品运输频繁，安全风险大。在经历天津港“8·12”危险品仓库爆炸事件后，不仅天津港危险品仓储问题需要得到重视，来往天津港的危险品运输车辆也同样需要关注。因此，在危险品运输的过程中必须要保证该过程的安全性，以避免发生事故威胁到周边人民的安全。故本文利用上述建立的模型及算法，针对出入天津港的主干线进行分析，选择出一条最优的危险品运输路径。

3.1 建立危险品运输网络

本文利用GIS建立了天津港危险品运输网络模型，其过程如下：①在GIS中导入包含天津港的天津市滨海新区地图，并选择合适的地理坐标系和投影坐标系；②新建Shapefile文件，将出入天津港的主干线路径图在GIS中标识出来，包括国道、省道和高速公路，并选择与上文相同的地理坐标系和投影坐标系建立了天津港危险品运输网络，见图2。

图2 天津港危险品运输网络Fig.2 Dangerous goods transportation network of Tianjin Port

本文利用空间配准矢量化对天津港危险品运输网络进行操作，设计相应的电子地图作为后续研究使用，并将其导入个人地理信息数据库。对该地图建立拓扑图层，设置拓扑规则即不能有悬挂点、不能重叠，并根据规则检验路径之间连接的正确性。

3.2 道路属性数据表设计

建立天津港危险品运输网络电子地图后，需要对其道路属性建立相应的数据表以存储相应的数据，所建立的道路属性数据表见表2。

表2 道路属性数据表

建立道路属性数据表后，道路的实际长度即为Length字段所表示的长度，该字段可利用计算几何选项计算得到。不同路段的风险值和通过该路段所需的时间需要依据模型计算得出。

3.3 道路数据收集

对天津港危险品运输网络建模后，需要收集道路有关数据，本文中道路相关数据取自一项对天津市公路网机动车起讫点调查的交通分析研究报告。该研究结果指出，一天24 h内的车辆数在全市范围内的分布是有一定规律的，并分析了不同路段的交通适应性，即一天24 h内的折算交通量，还列出了调查过程中得到的一天24 h中每一小时内的折算交通量，通过综合分析即可根据各路段数据建立相应的时空矩阵。本文假设各个路段不同时间段内的车辆数比例相同，该比例仅与时间段有关，并根据该数据，综合整理出各时间段车辆数比例如表3所示,将该数据代入时空矩阵，即可列出完整的时空矩阵。

表3 各时间段车辆数比例

3.4 危险品运输事故后果建模

本文利用风险建模软件ALOHA对危险品运输事故后果进行评定。

ALOHA软件是由美国环保署化学制品突发时间和预备办公室、美国国家海洋和大气管理响应和恢复办公室共同开发的应用程序。该软件中的风险建模程序可以根据化学制品事故发生地点、当时天气情况以及化学物质从容器中的逸出方式来判断威胁区域。ALOHA软件评判威胁区域的方法是依据应急响应计划指南(ERPG)，该指南根据人体暴露在有毒气体环境中约1 h的受害程度分为三个等级：ERPG-1、ERPG-2、ERPG-3，该等级越高表示人体受害程度越大。

本文以满载的液苯运输车发生爆炸事故为例，该运输槽车的储罐为容积1.81 t、直径1.22 m的卧式储罐，设定液苯爆炸的假设条件见表4。

表4 液苯爆炸假设条件

利用ALOHA软件模拟得到的数据显示，液苯运输车爆炸产生的火焰直径为68 m，来自液苯爆炸产生的热辐射影响范围直径为640 m，模拟生成的影响范围如图3所示，同时列举了液苯运输车爆炸发生时在几条路径上可能造成的影响区域见图4。

图3 液苯爆炸的影响范围Fig.3 Influence range of liquid benzene explosion

图4 天津港液苯运输车发生爆炸时的实际影响区域Fig.4 Possible actual influence area of liquid benzene transportation vehicle explosion in Tianjin Port

3.5 结果分析

对天津港危险品运输路径各连接点进行编码，以方便进行路径描述,具体运输路径编码图如图5所示。

图5 天津港危险品运输路径编码图Fig.5 Code map of dangerous goods transportation path in Tianjin Port

假设危险品运输车辆从图5中点1于上午9时出发，目的地为点13，利用上述数据收集以及事故后果建模得出的数据代入模型，并利用改进的NSGA-Ⅱ算法进行求解，求得的结果见表5。

表5 运行结果

由表5可知，路径1-2-9-7-8-13的风险值较低而成本值较高，路径1-2-3-5-6-7-8-13的风险值较高而成本值较低，虽然两条路径各有优劣，但是第一条路径的风险值更小而成本比较接近第二条路径，且该路径适应度更高，因此路径1-2-9-7-8-13更适合天津港危险品运输。

4 结 论

本文首先以构建时空矩阵的方式存储数据信息，对危险品运输的事故率和事故后果进行真实模拟，结合运输成本建立综合、动态、多目标危险品运输路径优化模型，并利用BRP函数模型求得不同路段的通行时间;然后设计并改进了NSGA-Ⅱ算法模块中的编码方式和自定义问题模块中求解目标函数的方式，使其更适用于本文模型的求解；最后以出入天津港的主干线为研究区域进行实证研究，通过收集道路相应数据并结合天津港危险品事故情景建模得到的事故威胁区域，利用本文建立的模型及算法选出了一条最优的危险品运输路径，证明了研究的可行性。

但本研究还存在一定的不足，如所选取的危险品运输路径较短，导致运输时间不长，时变风险的变化幅度较小，后续可以延长危险品运输路径，使时变风险变化幅度加大，以探讨危险品运输路径的动态优化问题。