基于政府管制的危险品运输的双层规划设计

文/姜嘉艳



基于政府管制的危险品运输的双层规划设计

文/姜嘉艳

摘 要：本文基于危险品运输和双层规划的特点，对特定的危险品在特定路段采取禁止通行的方式来实现道路危险品运输网络设计。上层政府监管部门以危险品在运输过程中总期望风险最小化为目标，下层运输企业以期望运输成本最小化为目标，构建基于政府管制的危险品运输的双层规划模型。如果上层与下层的结果不一致，则通过反复修改网络图的方法，权衡风险值和成本，直到使双方都满意。最后通过数据模拟（c-free 3．5）验证了算法的而有效性。

关键词：危险品运输；网络设计；双层规划；数值模拟

1.研究背景

近年来，伴随着国民经济的发展，公路运输事业和化学工业均取得了长足的发展和进步，从而对社会大多数成员来说，生活已越来越离不开危险品。不可回避的是，大多数危险品不是在生产地被使用，而是需要经过相当长距离的运输到达使用地。据统计，我国95%以上的危险品涉及异地运输问题，其中80%左右是通过道路运输的，每天危险品的运输量超过100万吨[1]。由于危险品道路运输量大、运行车辆事故率高和运输企业安全管理水平落后，近年来灾难性事故频发，后果极其严重，受到了各国政府和公众的极大关注。因此，不管在国内还是在国际上，危险品在运输中的事故、风险、路径选择等问题，引发着许多学者的研究。

2.危险品运输的特点

由于运输货物本身的特殊性，危险品具有易燃、易爆、毒性、腐蚀性和放射性等对人类生活生产具有危害的属性。危险品在运输过程中，其危险性本就高于其他运输货物[2]。其主要特点表现在：①品类繁多，性质各异——现今，在《危险货物品名表》中的危险品已达2700多个品名；②危险性大——运输中如防护不当，极易发生事故，造成人员伤亡和财产损失；③运输管理的规章制度多——作为整个道路货物运输的重要组成部分，危险品道路运输不仅要遵守道路货物运输共同的规章，而且要遵守很多特殊规定；④专业性强——危险品运输要满足一般货物的运输条件，还要根据货物的物理和化学性质，满足其特殊的运输条件；⑤安全至上——这里安全运输是区别于其他普通运输的标志，它是危险品运输的基点所在，要把安全工作放在首位[3]。

3.危险品运输问题描述及模型设计

（1）问题描述

在本文对危险品运输网络设计中，涉及两个角色：当地政府和运营商。当地政府指派网络，运营商选择路线。政府代表第一层，限制路段的通行以控制路网上的风险；运营商代表第二层，在可行的路网上选择成本最小化的路径。一旦政府决定了路网，运营商将在此路网上，选择在始发地和目的地之间成本最小的路线，政府通常不对运营商规定路线，因此政府在设计中加入运营商选择成本最低路线的自由。这种情况引起了双层规划问题[4]。

（2）假设条件及相关参数

危险品网络设计问题是一个定义在图形理论问题G=（V，A），其中V是定点集合，A是路段集合。一个顶点对应一个交叉口，一个路段对应网络上的一个路段。网络设计问题找到一个网络服务危险品运输从起点到终点的路线。每个商品对应一对OD。记（s，t）为运输车辆的一对OD。参数rijk和cijk分别表示第k种危险品在路段（i，j）上相关的风险和成本，pijk表示第k种商品在路段（i，j）上发生运输事故的概率。如果（i，j）是危险品k在网络中的最佳路段，记xijk=1。如果（i，j）或（j，i）是政府决策的网络中的解，记yij=1，同时本文仅考虑一类危险品，即k=1。

（3）模型设计

目标（1）是政府最小化网络上的总风险，而（3）为运营商最小化成本。约束（2）表示如果（i，j）或（j，i）中有任何一个路段用于货物运输，则两个路段均开放使用。约束（4）确保危险品k从起点运达终点。约束（5）确保运营商选择的路径是由政府选定的。约束（6）是二进制要求的变量。

4.求解双层规划的算法设计

（1）求解双层规划的基本思想

双层模型是一个NP～Hard问题[5]，它集政府决策和运营商决策于一体，当单独考虑政府决策或运营商决策时，问题可以很容易得到解决。本文鉴于Erkut和Gzarais[6]采用一个启发式算法进行求解。政府部门对每个运输任务求最小风险路径，形成网络记作N，相应风险为R。运营商在网络上按成本最小化选择路径，实际风险记为Act_R。如果R=Act_R，则认为已经找到最优结果。否则，至少有一个运输任务没有按照政府部门设想的路线运输。为了兼顾政府部门和运营商路径选择的目标，不断迭代删除某些风险较大的路段。通过删除路段，政府指定网络的总风险R不断增加，而运营商选择的网络所对应的Act_R不断的减小，最终达到平衡。

（2）算法设计

初始化：t=0，At=A，best_R=∞。迭代t。

第一步在At上找到运输车辆的最小风险的路径。

记xt和Rt分别为危险品k对应的最优解和风险值。如果x=1 或x=1，则设置y=1。

第二步在At上找到运输车辆的第二条最小风险路径。

在找到的最小风险路径中，删除最大风险的路段，然后在新的路网中，找出最小风险路径，这条路径即为原路网的次风险路径。

第三步在At上找到运输车辆的第三条最小风险路径。

在找到的第二条最小风险路径中，删除最大风险路段，然后在新的路网中，找到最小风险路径，这条路径即为原路网的第三条最小风险路径。

第四步在At上找到运输车辆的第四条最小风险路径。

在前三步找到的两条路径中，分别删除其最大风险的路段，在新路网中再次找出最小风险路径。记以上四步找到的路径组成的路网为A（yt）。第二步到第四步的路段的删除是暂时的，仅限于本次循环的找寻路径，不影响其他步骤风险值的比较和计算。在本文中，选取以上四条最小风险路径作为政府选择的有效路网。

第五步在A（yt）上解决最小成本问题：

记zt和ct分别为对应的最优解和成本值，Act_Rt是与zt相关联的风险。更新找到的最佳解决方案：如果Act_Rt＜Best_R那么Best_R=Act_Rt。

第六步如果Act_Rt=Rt，那么一个风险水平为Act_Rt的候选路径zt确定，进入第七步。否则，进入第六步。

图5　-1 模拟网络

图5　-2 最优解

第七步记（i，j）是删除规则找到的一条路段，从路网中删除（i，j）和（j，i），t=t+1，At+1=At-{（i，j）（j，i）}，进入第一步。

第八步稳定性检查

表5　-1 结果分析表

如果不只一条，那么进入第七步。

在第三步中，条件Act_Rt=Rt，意味着实际风险不能通过删除路径来改善。当这个条件成立，有着最小成本ct和最优解zt是一个候选解决方案。当路网中存在闭合的回路，可能有多个有着不同风险值的最小成本方案。要检查解是否稳定，只需检查路网上最小成本路径是否存在多种不同风险值的方案。为了验证这种情况（步骤七），本文通过比较风险值来解决问题。若找到的解不稳定，意味着路网上存在至少一条路径使成本相同，但风险更高。因此，某条路段的风险是否过高，取决于运营商的选择。在这种情况下，为了不使路径的风险过高，本文持续删除高风险路段，直到获得一个稳定的解。

5.数值模拟及结果分析

（1）数值模拟

本文模拟一辆危险品运输车辆穿过拥有20个节点的城市进行算法测试，并用c～free3.5编程实现路径的选择。测试的路网如下：（见图5-1）

道路网由20个节点和48条边组成。其中路段间的成本根据行驶里程以及路段情况计算，路段间的风险值根据危险品道路运输风险分类中的风险因素得到。本文利用双层规划模型方案，分两阶段进行测试。第一阶段找到风险最小的四条路径，形成一个新路网。

Route1=（1，5）（5，14）（14，18）（18，19）（19，20），风险值R1=8，成本值C1=21；

Route2=（1，5）（5，9）（9，14）（14，18）（18，19）（19，20），风险值R2=10，成本值C2=21；

Route3=（1，3）（3，6）（6，12）（12，17）（17，20），风险值为R3=11，成本值C3=20；

Route4=（1.9）（9，14）（14，18）（18，19）（19，20），风险值R4=13，成本值C4=19；

Rt=8，运行结果显示其中（1，9）路段为第一次循环形成的路网中的最高风险路段。

第二次循环中，加入成本指标再次寻找路径，即在新路网中找到最小成本路径：（1，9）（9，14）（14，18）（18，19）（19，20），计算风险值Act_Rt=13。由于Act_Rt=13不等于第一个阶段的解中的最小风险值Rt=8，所以要删除路段精心权衡。找到新路网中的最大风险的路段（1，9），并将其删除。删除后重新执行第一步，直到找到Act_Rt=Rt的路径。经过多次循环找到Act_Rt=Rt的路径：（1，5）（5，14）（14，18）（18，19）（19，20），风险值为8，成本为21。这条路径成为最优解的候选路径。要想将候选路径确定为最佳路径，需要检查最优解是不是唯一。（见图5-2）

经过搜索，发现本文Act_Rt=Rt的路径只有一条，候选路径稳定，于是确定其为最优解。算法得到了最优解，验证了它的有效性。

（2）结果分析

本文共通过四次循环，找到了最优路径，即找到最小成本路径的实际风险值Act_Rt=Rt的路径，如表5-1所示：

第四次循环后，最小成本路径有三条，即1～5～1 4～1 8～1 9～2 0，1～5～9～1 4～1 8～1 9～2 0，1～2～3～6～12～17～20；其实际风险值分别为8，10，15，而目标风险值R=8，所以Act_Rt=Rt的路径为1～5～14～18～19～20。找到了最优路径。

（作者单位：中国民航大学）

参考文献：

[1]储庆中，张家应，谢之权．基于双层规划的危险品道路运输网络设计[J]．重庆交通大学学报(自然科学版)，2010，04：597～603．

[2]孙敬．危险货物道路运输路径优化双层规划模型研究[D]．华东交通大学，2012．

[3]曾意．国内危险品物流现状调查[J]．中外物流，2007，04：33～35．

[4]宋杰珍，丁以中，孟林丽．基于双层规划的危险品运输网络设计[J]．上海海事大学学报，2006，02：56～59．

[5]Jeorslone R G． The polynomial hierarchy and simple m od le for competitive analysis[ J] ． Mathematical Programming， 1985，32：146 ～ 164．

[6]Erhan Erkut， Fatma Gzara． Solving the hazmat transport network design problem[R]，Science Direct，2007．