静态单点多目标危险货物运输路线优化算法研究

章良

[摘要]本文通过对道路危险货物运输研究背景的介绍，引出静态单点多目标危险货物运输路线优化问题，进而建立静态单点多目标危险货物运输路线优化模型，并介绍模型的算法过程。

[关键词]单点多目标；危险货物；路线优化；算法

[中图分类号]U11[文献标识码]A[文章编号]1005-6432（2014）49-0176-02

1研究背景

道路危险货物运输作为道路货物运输重要的组成部分，是一种技术业务复杂、安全条件要求高的特种运输。随着我省经济和道路运输的持续、快速发展，以及工农业生产和人民生活水平的提高，对危险货物的需求越来越大，通过道路运输的危险货物的种类、数量不断增长。

危险货物运输车辆在道路上行驶，就相当于“流动危险源”。然而我国对道路危险货物运输行业的管理还不尽如人意，行业内还存在各种问题，例如，从业人员的素质低、车辆技术状况差等，从而引发各种危险货物运输事故，并且造成的危害程度也越来越高。

道路危险货物运输路线优化可以有效地降低运输风险。通过合理地规划运输路线，选择事故发生概率较小的路线进行运输，这样就可以减少道路危险货物运输风险，确保高质量的提供运输服务。

2问题描述

无论是静态还是动态的危险货物运输路线优化，其根本问题都是从运输任务起点和终点之间所有可供选择的路线中选出最佳的运输路线，在满足一定的约束条件（如运输量、可接受风险标准等）下，达到一定的目标（如路程最短、费用最低、风险最小等）。这类问题又可以从两个方面考虑：首先，“单对单”运输路线问题，即单一起点，单一终点，单种危险货物、单一运输方式的路线优化。另外，还有一种道路危险货物运输路线优化问题是“多对多”的运输路线优化问题，即多个起点、多个终点、多种危险货物，可以用多种运输方式分别运输。从时间因素的角度出发，危险货物运输路线优化问题可以分为静态和动态道路危险货物运输路线优化两种。从优化目标数的角度出发，又可以分为单目标和多目标道路危险货物运输路线优化。其中，单目标道路危险货物运输路线优化问题已经有完善的解决方法，即经典的最短路线问题模型。

然而，在实际应用当中，仅仅考虑线路最短这一单一目标是不够的。危险货物运输企业都会面临经营成本增加和公共安全投入的双重压力。因此，道路危险货物运输路线优化问题也不再单纯追求运输风险最小或单纯追求经济效益（即选取最短路线、最低成本），而是同时考虑经济效益和运输安全，使其达到总效益最大。道路危险货物运输路线优化问题就演变成一个多目标优化决策问题，决策者可通过合理的规划选择能使多个目标同时最优或近似“最优”的路线，使得危险货物运输企业在确保运输安全的前提下，达到经济效益最优。然而，在危险货物运输路线优化过程中，我们所考虑的多个目标经常会相互矛盾，例如运输费用减少，运输时间就有可能延长；而运输时间变短，运输风险就可能变大。要使这些多目标同时达到最优往往是不可能实现的。在实际运输过程中，由于受到诸多因素的影响，很难兼顾所有方面来做出决策。也就是说，决策者应该综合比较分析应该考虑的多个目标，形成几种可行的方案，并加以权衡，最终选择一个令决策者较为满意的方案。

3模型构建

下面我们先研究一下静态“单对单”多目标道路危险货物运输路线优化，其模型可简化为：

假设G=（M，N）为一个道路危险货物运输网络图，其中M为节点集合，N为弧的集合，设i， j∈M，则网络中每条弧则可表示为（i，j）。任意两节点间的运输路线则可用Lij={i=i1， （i1， i2）， …， （ik-1， ik）， ik=j}，这个点、弧交错的序列来表示，假设弧段（i，j）上赋有S维目标向量uij=（u1ij， u2ij， …， usij），向量中的元素usij表示弧段（i，j）的第s个目标变量值。则可用s维目标向量uLod=（u1Lod， u2Lod， …， usLod）来评价从起点o到终点d的道路危险货物运输路线Lod的优劣程度。因此，从起点o到终点d间，考虑s维目标的道路危险货物运输路线优化问题的数学模型可表述为：

第一个表达式表示寻找满足s维目标向量非劣的道路危险货物运输路线；第二个表达式则是确保危险货物运输的流向是从起点到终点；第三个表达式则是限定判断变量yij的取值范围，当yij=1则表示节点i和节点j间存在运输任务，当为yij=0则表示节点i和节点j间不存在运输任务。

4算法过程

危险货物运输路线多目标优化一般情况下包括一组不能同时达到最优的目标或冲突的目标，找到能使全部目标同时最优的最优路线是几乎不可能实现的，往往只存在一组有效路径解集。解决多目标路线优化问题时，常见的解决方法是利用权重将多目标路线优化问题经过加权调整转化为单目标最短路问题求解。权重的确定带有很大主观性，因此，最后确定的最优路线往往带有很强的主观性，会随着决策者的意愿发生改变。为了尽量消除主观因素对路线抉择的影响，引用灰色关联度理论，利用启发式算法，在无法获得绝对最优路线的条件下，构建虚拟的绝对最优路线目标向量，找出接近该虚拟最优路线来获得满意解。其具体步骤可分为：

第一步，构建特征值矩阵。

把多目标问题转换为单目标问题，分别将单目标最短路问题一一解决，则S个不同目标函数需要连续进行S次。假设利用最短路算法求得S个目标所对应的最短路线共有N条，则可以构建N个路线方案的S个目标的特征值矩阵X。

第二步，确定虚拟的绝对最优路线的目标向量。

由于所追求的目标不同，路线的S维目标变量可划分为越小越好型和越大越好型两大类。顾名思义，对于越小越好型目标，其值越小越好，反之则越大越好。假设X0为灰色关联分析的绝对最优目标向量，即X0=（x01， x02， …， x0P）。在第一步里构建的特征值矩阵X中加入向量X0，构造（N+1）×S阶目标特征值矩阵。

第三步，进行规范化处理。

在目标特征值矩阵中的各个目标的物理意义不同，导致数据的量纲也不全相同，这就导致比较时较难获得正确的结果。要保障所求各目标具有等效性和同序性，这就需要处理原始目标特征值矩阵，也就是将原始目标特征值矩阵无量纲化和归一化。原始目标特征值矩阵经过规范化处理则可相应地转化为T=（tij）（N+1）×S，向量X0则转化为靶心T0=（1， 1， …， 1）。

第四步，确定差异信息空间。

通过公式Δij=1-tij处理规范化后的目标特征值矩阵T=（tij）（N+1）×S，就可得到新的（N+1）×S阶差异信息矩阵。新构建的差异信息矩阵的所有元素中，最大值称为两极最大差Δmax；反之则称为两极最小差Δmin。由此，其差异信息空间可以表示成ΔCR=（Δ， ρ， Δmax， Δmin）， 上述公式中：Δ为全体差异信息，ρ为分辨系数，ρ∈（0，1），通常情况下为0.5。

第五步，计算灰色关联度。

假设我们把xij和x0j在第j个目标上的靶心系数表示为ζ0i（j），就可以得到：

第六步，将各方案按照灰色关联度大小进行排序。关联度越大，则相应的运输路线方案越好。

参考文献：

[1]任常兴，吴宗之.危险品道路安全运输路径优化方法探讨[J].中国安全科学学报，2006，6（16）：129-134.

[2]郭晓琳，李军.基于事故分级的有害物品运输路径风险度量模型研究[J].中国安全科学学报，2006，16（6）：35-39.

[3]沈小燕.道路危险货物运输风险分析及路线优化研究[D].西安：长安大学，2009.