何 静，朱双凯，任 晔
（1. 昆明理工大学交通工程学院，昆明 650500；
2. 昆明地铁运营有限公司，昆明 650500）
近年来，我国对地铁突发事件应急处置的要求越来越高，因地铁运营具有客流集中、空间封闭等特点，一旦发生突发事件，社会影响巨大，有可能造成严重的生命财产损失[1]。由于突发事件通常无法提前预见，发生灾害的位置事先无法确定，物资需求数量、救援时间也不确定，因此极可能导致突发事件在第一时间内不能得到妥善处理，贻误了救援最佳时机，造成不必要的损失。目前，我国许多城市地铁应急储备点布局不合理，应急资源配置不均衡，这给地铁网络化运营以及应急处理等带来诸多挑战。其中，正确合理的地铁应急储备点选址布局是保证应急救援及时有效的重要前提，对于提高地铁应急处置水平具有重要意义。
目前学者们在该领域的研究多集中于应急物资储备点优化配置的问题，且较多是基于确定模型展开的[2-4]，而考虑不确定因素的研究相对较少。在考虑突发事件发生后多种不确定性下的LRP模型时，Rajali针对灾难发生后定位的不确定性，开发了一种用于救济物资供应和分配的多目标位置分配模型[5]；
Chawis在考虑洪水不确定的情况下，探讨以救援距离和避难风险指数为目标的避难所选址问题，提出了随机线性混合整数规划模型[6]；
孙华丽等针对需求点物资需求量和车辆运输时间的不确定，通过鲁棒优化方法，建立了以物资送达需求点救援时间之和最小为目标的应急设施选址-路径模型[7]；
李建光等通过离散场景来表达避难需求的不确定性，以建设总成本为目标，提出鲁棒随机规划模型，分析不同期望情形与最坏情形下的应急避难场所选址[8]；
在不确定条件模型处理方式上，Ye等运用改进的遗传算法和禁忌搜索算法，求解应急车辆定位模型和路网任意点的需求模型[9]。高飞针对不确定因素下的配送路径选择，设计了基于证据推理的不确定多因素路径选择方法，利用基于禁忌搜索的混合模拟退火算法来求解[10]。
综上所述，已有的研究基本集中在抢修物资不确定这一因素上，对应急储备点不确定这一因素展开的研究很少。此外，大多数研究缺乏系统性、整体性，基本都是将应急储备点选址和物资配送的路径分开研究，在求解算法上也将其分为两个问题单独求解。基于以上分析，本研究进行建模与求解算法的设计。考虑了应急救援需求点具有一定的时间窗，构建基于相关机会目标规划理论的地铁应急物资储备点带有时间窗的选址-路径模型，以应急物流总成本最小化和救援时间最短化为目标，并设计遗传算法(GA)对模型求解，以期为地铁应急物资储备点的选址决策提供借鉴。
2.1 问题描述
要从若干备选地铁应急物资储备点中选出合适的应急储备点，在满足需求点物资需求量的前提下，将应急物资快速准时地运到需求点。应急储备点的设置是不确定的，而需求点救援带有较高的时间限制。地铁应急物资储备点的选址受许多因素影响，如时间、成本、物资需求、速度、损毁情况等，考虑到地铁应急需求点对物资需求的紧迫性，故将时间作为第一个要考虑约束条件；
由于地铁前期建设费用较高，短期内筹集到的资金有限，合理利用资金至关重要，故将成本作为第二个要考虑的约束条件。
2.2 模型假设
1) 有潜在的若干个应急物资储备候选点，容量有限，从中选取部分应急物资储备点发货，要求每个应急储备点供应量超过一个需求点的货物；
2) 由于突发事件发生时道路情况不确定，所以车辆运输时间是随机变量，服从正态分布；
3) 每辆车从应急储备点出发，在运送完应急物资后，应回到该应急储备点；
4) 一个需求点仅由一个应急储备点供应；
5) 每个需求站都会被覆盖，且只能覆盖一次；
6) 建设空间能够满足建设需求。
2.3 模型参数
模型中的参数定义如下：P1、P2表示优先因子，表示各个目标的相对重要性，满足P1≥P2；
di-和di+（i=1，2）表示目标偏离目标值的正偏差和负偏差；
表示需求站集合；
表示应急物资储备候选点集合表示应急物流网络中所有节点的集合；
C表示单位距离车辆行驶成本；
Cj表示应急储备点j的固定建设费用；
dij表示节点i到j的距离；
qj表示应急储备点j的库存容量；
εi表示需求点i的随机需求；
tij表示配送车辆从i到j的行驶时间；
α表示目标约束的置信水平；
Xj表示{0，1}，如果应急储备点建立在位置j则为1，否则为0；
Yj表示{0，1}，如果需求点j由车辆配送则为1，否则为0；
Zij表示{0，1}，如果车辆是从应急储备点j到需求点i则为1，否则为0。
2.4 构建模型
机会目标规划理论的主要思想是：在不确定环境下，通过极大化事件成立的机会，从而给出最优决策[11]。机会目标规划模型允许在优化过程中决策不满足约束条件，但必须保证约束条件成立的概率满足置信水平要求。基于上述假设条件，构建不确定条件下的地铁应急物资储备点选址数学模型。
目标函数如下：
约束条件如下：
2.5 模型求解
本研究所建立的不确定条件下的地铁应急储备点选址模型为双约束条件选址决策模型，遗传算法可以将问题参数编码成染色体进行优化，不用针对参数本身，从而不受函数约束条件的限制，这样可大大减少陷入局部最优的可能性。具体求解步骤如下：
1) 步骤1，编码及种群初始化。染色体将需求点以及应急物资储备候选点进行编码，采用3层编码的方式，将编码序列分为3个编码段。第一段表示应急物资储备候选点编号，第二段表示需求点编号，第三段为应急物资储备候选点到需求点的配送路径。
举例说明，种群个体编码序列为1 2 4 | 1 1 2 2 4 2 1 4 |2 3 1 5 6 4 8 7，则第一段1 2 4表示应急物资储备候选点编号为1 2 4的3个点被选中。第二段1 1 2 2 4 2 1 4表示需求点1被应急储备点1负责配送，需求2被应急储备点1负责配送，需求3被应急储备点2负责配送，依次类推。第三段表示需求点被配送的顺序为2 3 1 5 6 4 8 7，同一个中心负责的需求点按次序列从左至右的顺序配送。采用随机生成的方式产生初始种群。
2) 步骤2，适应度函数。本研究所求解的目标函数为最小值，所以适应度函数应最大化。函数值越小的个体，适应度越大，个体越优。
3) 步骤3，选择操作。采用轮盘赌的方式，选择优秀的个体保留至下一代。具体操作如下：
① 计算出群体中每个个体的适应度f(i=1，2，…，m)，m为群体大小；
④ 从区间[0，1]随机产生一个均匀分布数r，若r
⑤ 最后重复步骤4)共m次。
4) 步骤4，交叉操作。将染色体分为三部分进行交叉。
① 假设交叉点为第二个随机产生的基因位，p1=[1 2 |4]，p2=[1 3|4]，交叉后得到 1p′=[1 3|4]，p2′=[1 2|4]，如果存在重复则去掉，然后随机补充，使得编码序列满足要求。
② 假设交叉点为第5个随机产生的基因位，p1=[1 1 2 2 4|2 1 4]，p2=[1 4 1 2 4|2 1 2]，交叉后得到 1p′=[1 4 1 2 4|2 1 4]，p2′=[1 1 2 2 4|2 1 2]。
③ 随机产生两个不相等的交叉点，并将两交叉点之间的基因进行互换，从而产生新的序列，然后将新序列中多余的基因去掉，缺失的基因补充完整，便可形成两个符合条件的新个体。
6) 步骤6，结果输出。采用遗传算法常用的终止判据，即当迭代次数到达人为规定的最大迭代次数时终止运算。
遗传算法流程如图1所示。
图1 遗传算法流程Figure 1 Flow chart of genetic algorithm
地铁应急物资储备点的选址范围可在地铁车站或附近区域内选择。考虑到昆明地铁线路的实际管理情况和快速救援等要求，将选址范围确定为同属于昆明地铁运营有限公司的1、2号线首期工程、3号线和6号线一期工程上的53个地铁车站。
在选择应急物资配送候选点时，主要考虑以下约束条件：
1) 选择换乘站。换乘站不仅承担一般车站乘客的进出站和上下车功能，还要具备乘客的中转换乘等功能，因此可实现3线换乘的东风广场站应给予考虑。
2) 对于毗邻汽车站、铁路车站等大型客流集散点的地铁站点，客流多且复杂，是应急抢修点的重点区域，应当予以考虑[12]，如昆明地铁1号线的昆明火车站、南部汽车站等。
3) 线路车辆段综合维修基地物资配备比较齐全，因此也应考虑将其当作一个应急物资储备候选点。
基于上述约束条件，初步确定了16个应急物资储备候选点。
3.1 基础数据情况
根据目前昆明地铁的应急物资安全库存现状以及应急响应的要求，结合综合代价值最小的原则，拟建立10个应急物资储备点，使其覆盖现有53个已运营的车站，如图2所示。
图2 地铁线网及站点情况Figure 2 Metro network and site information
本案例中的53个车站已经全部投入载客运营。这些车站的建设时序不同，初期的拆迁成本和建设成本各不相同，而设置应急储备点主要考虑充分利用现有车站的剩余空间，因此计算中仅考虑重新装修成本，不考虑拆迁成本以及建设成本。为了计算的简化，将每个固定抢修点的实施建设成本简化为5.0万～6.0万元/个，可供使用的面积为30～50 m2。每个应急物资储备候选点的固定建设成本Cj={5.0，5.5，6.0}万元，应急物资储备候选站容量qj={350，400，450}件，车辆单位运输成本为7元/km，置信目标α=95%，应急候选点的坐标和建设成本信息如表1所示，需求点的坐标和需求量信息如表2所示，其中各车站的救援时间窗为[0，15]min，各个站点之间的运输时间是在不同时间段内多次测试得到的。
表1 应急物资储备候选点信息Table 1 Candidate point information for emergency supplies
表2 需求点信息Table 2 Information about demand point
3.2 选址-路径优化
使用Matlab软件编程，对该模型进行求解，遗传算法中交叉概率的选择范围为0.5～1，变异概率的选择范围为0～0.2，初始染色体的数目无限制。本研究设置染色体数目为100，交叉概率为0.85，变异概率为0.15，对算例进行计算30次，得到的结果比较稳定。基于GA确定的应急储备点的最优选址位置和路径分配如表3所示，算法经过500次迭代，模型目标收敛如图3所示。
图3 目标收敛Figure 3 Target convergence graph
表3 应急储备点选址结果Table 3 Site selection results of emergency reserve points
由上述计算结果得出，昆明地铁需建立的10个应急物资储备点的站号依次为：1、6、9、14、23、24、28、32、41、48，满足需求站点均被选出的应急物资储备站点覆盖的要求。分析表3中的数据可知：以成本和时间作为约束条件，各应急储备点的容量也会存在差异，应急储备点对应的需求点是不均匀的，配送路线也就不同。依据时序性原则，结合潜在昆明地铁应急储备点在路上的实际位置，对实际配送路线进行微调。换言之，各个应急储备点在不确定条件下的工作量不同。例如，应急储备点41覆盖了2条线路10个站，而应急储备点1覆盖了同一条线路的2个站点。
3.3 现状结果讨论
由于种种原因，我国地铁既有线大多在规划设计阶段没有考虑应急储备点的选址规划。随着线路的增加，车站的性质会有所改变，中间站变成换乘站；
进入到网络化阶段，应急抢险的要求会变高。在此情况下，其应急设施的设置也需要进行相应改变，故可考虑以新建应急设施的建设成本与已设应急设施的改造成本之和最小为目标，以规定的救援时间最小、已有应急设施和覆盖所有的需求站点等为约束条件，建立动态发展的选址模型。对于既有线新增应急物资储备点共有3种方法：一是根据应急物资的类型不同，改造车站预留空间，达到储备部分物资的目的；
二是对于大中型应急物资，可以依靠设备供应商的场地，解决大型应急设备的供应问题；
三是最理想的状态，应该是在线路建设阶段甚至是在规划设计阶段，就预留应急物资储备点，待到时机成熟再行建设。
本研究针对地铁应急储备点选址优化存在的不确定性，在应急救援存在严格的时间限制下，以应急成本和救援时间作为约束条件，基于机会目标规划方法，建立地铁应急物资储备点选址模型，通过设计遗传算法对模型进行求解，并以昆明市地铁部分线路为例，对模型和算法进行了验证。结果表明，该模型能够解决昆明地铁决策和物资路径分配需求的问题，能够为城市轨道交通应急物资储备点选址研究提供新的依据和思路，同时也证明了遗传算法能够有效地解决函数约束条件限制下的选址问题，避免了仅针对参数本身减少陷入局部最优的可能性。未来的改善研究可以考虑多层级地铁应急物资配送点选址模型，以解决多重不确定条件下的应急配送点选址问题。
猜你喜欢 约束条件遗传算法储备 释放钾肥储备正当时粮食与饲料工业(2022年2期)2022-04-27基于遗传算法的高精度事故重建与损伤分析汽车工程(2021年12期)2021-03-08国家储备林：为未来储备绿色宝藏绿色中国(2019年19期)2019-11-26基于遗传算法的模糊控制在过热汽温控制系统优化中的应用电子制作(2019年16期)2019-09-27基于遗传算法的智能交通灯控制研究电子制作(2019年24期)2019-02-23外汇储备去哪儿了支点(2017年3期)2017-03-29复杂多约束条件通航飞行垂直剖面规划方法北京航空航天大学学报(2016年6期)2016-11-16论持续监控研究的假设前提与约束条件中国市场(2016年12期)2016-05-17基于改进多岛遗传算法的动力总成悬置系统优化设计汽车科技(2015年1期)2015-02-28