基于随机模拟的遗传算法求解随机双层规划的思想可以表达为，在上层规划可行集中随机产生初始种群，种群中的各个个体对应不同的危险物品运输网络设计方案
文／高清平 吴海虹
危险物品是一类具有物理、化学或生物特性的物品，容易在生产、贮存和运输中引起泄漏、燃烧、爆炸和中毒等灾害事故，往往对影响范围内的人口、财产和环境造成严重伤害。为了尽量减小危险物品的运输风险，实践中常采取强化驾驶员培训、规定危险物品容器规格、规范危险物品的运输车辆标志和安全技术条件等措施。
在已有的研究中，考虑了运输管理者和运输者的相互作用和不同决策目标。但是，尚未考虑路段风险和费用参数的随机性，尚未评价参数随机性对运输管理者和运输者决策行为的可能影响，也未研究其对危险物品运输网络设计的影响，难以保证危险物品运输网络的稳健性。鉴于此，笔者在已有研究的基础上，构建了在随机性风险和费用参数条件下，运输管理者和运输者相互作用的随机双层规划模型，上层模型描述运输管理者规划危险物品运输网络使风险最小，下层模型描述运输者在运输管理者规定的危险物品运输网络中选择路径使运输费用最小。设计了基于随机模拟的遗传算法求解该随机双层规划模型。
为便于研究，本文作如下假设：假设在危险物品运输网络的设计中，运输管理者仅考虑使运输风险最小，运输者选择运输路径仅考虑使运输费用最小。采用事故率风险模型测度危险物品的运输风险，以事故率表示路段的单位运输风险值，即每十亿车·公里发生的事故次数。假设运输网络中路段运输费用和风险具有随机性，服从对数正态分布，忽略动态性。因此本文模型属于静态模型，适用于中长期危险物品交通规划和政策评价。忽略路段上危险物品交通量对路段行程费用和风险的影响，危险物品的交通分配服从最短路分配原则。
模型求解
双层规划问题是一个NP-hard问题。其求解算法主要有极点搜索方法、罚函数方法、分枝定界法、进化逼近方法等。随机双层规划问题由于参数具有随机性，增加了问题的复杂性。对随机变量为连续型随机变量的情形，可以采用以抽样为基础的分解和近似策略，用一系列抽样点的积分值表达期望值，从而将其转化为确定型规划。其中，蒙特卡洛积分策略可以描述为：设
机模拟的遗传算法求解随机双层规划的思想可以表达为，在上层规划可行集中随机产生初始种群，种群中的各个个体对应不同的危险物品运输网络设计方案；根据上层规划的随机种群，求解下层规划对应的随机规划问题，并将计算结果反馈给上层规划。上层规划根据反馈结果计算上层规划种群中个体的适应度，并对种群进行选择、交叉和变异等操作。循环迭代上述过程，直至满足中止条件。
基于随机模拟的遗传算法的具体步骤如下：
Step1：随机抽样。随机产生服从相应概率密度函数的个样本。
Step2：输入参数。输入种群规模，交叉概率，变异概率和迭代次数。
Step3:产生初始种群。在可行集中随机产生规模为pop_size的初始种群。
Step4:适应度计算。根据蒙特卡洛积分策略，计算个体的目标函数值和适应度。
Step5:遗传操作。对种群进行选择、交叉、变异和重插入等遗传操作。
Step6:中止条件判断。如果群体中的最优适应度在规定的进化代数内没有改善，或者迭代达到规定代数，停止迭代。此时具有最优适应度的个体作为最优解。否则转Step4。
算例分析
设有如图1所示的运输网络，共有8个节点和15条路段。路段事故率和费用值均服从对数正态分布，概率密度函数的均值和均方差见表1所示。为简化计算且不失一般性，设路网中危险物品有2个OD对交通量，第1类危险物品从节点1到节点8的交通量为1，第2类危险物品从节点2到节点8为的交通量为1，其中路段6-7、6-8和7-8上两类危险物品的事故率和费用概率密度函数不相同。
为了研究危险物品运输网络规划问题，分析三种情景。第一种情景是忽略运输管理者的管理行为，假设管理者不规定危险物品运输网络，运输者可以选择任意路径通行危险物品运输车辆。此时，危险物品运输网络规划问题，本质是运输者选择运输路径使运输费用最小，对应的规划模型是模型式(1)～(6)忽略上层规划的情形。第二种情景是忽略运输者的路径选择行为，认为运输者必须选择运输管理者指定的风险最小路径。此时，危险物品运输路径规划问题，本质是运输管理者规划运输路径使运输风险最小，对应的规划模型是模型式(1)～(6)忽略下层规划的情形。第三种情景是同时考虑运输管理者和运输者的决策行为，认为运输管理者和运输者相互作用。运输管理者的决策影响运输者的决策，运输者是在运输管理者规定的危险物品运输网络中选择运输模式和路径，作出出行决策，从而使运输费用最小；同时，运输者的决策又反过来可以影响运输管理者的决策行为。此时，危险物品运输路径规划问题，本质是运输管理者和运输者相互作用的双层规划模型，对应的规划模型是模型式(1)～(6)的情形。根据双层规划模型式(1)～(6)，不同情景下的求解结果见表1。
表1中的数据表明，三种情景的求解结果和目标值并不一致。在事故率和费用值忽略随机性（取点估计值）情形下，最小费用路径是1-3-8和2-5-6-8，最小风险路径是1-3-8和2-5-7-8，考虑管理者和运输者相互作用时的最有路径是1-3-8-7-5-2，此路径具有最小的风险值92.1801，但是费用值87.5093远大于最小费用值22.9930。在考虑参数随机性条件下，具有类似的结论。结果表明，危险物品运输网络规划中，采用不同的规划主体和规划目标，会产生不同的规划方案，为保证网络规划的科学性，应该考虑运输管理者和运输者决策行为的相互作用。
考虑参数随机性与忽略随机性两种情景在三种规划目标下的结果均不相同。客观上运输费用和风险具有随机性的情况下，规划中忽略其随机性可能导致规划方案的重大错误。同时，在考虑参数随机性条件下，不仅管理者的决策影响运输者，而且运输者的出行决策也会反过来影响管理者的决策。例如，如果将最小风险路径1-3-6-8和2-5-6-7-8确定为允许危险物品通行的运输网络，那么运输者根据费用最小选择的路径将是1-3-6-7-8和25-6-8，此时风险值急剧增加到6.71 x107，并非风险最小，远大于5.1182 x102。因此，在规划中不仅应该考虑风险和费用参数的随机性，而且应该同时考虑运输者和管理者决策行为的相互作用。
本文受浙江省教育厅科研项目基金(Y201329142)和浙江省社科联研究课题(20142074)资助。
（高清平：浙江师范大学工学院、浙江大学管理学院；吴海虹：浙江东晶电子股份有限公司）