基于多目标优化的应急设施选址配送模型
2021-07-14吉康，刘倩
吉 康，刘 倩
(1. 南京市城市与交通规划设计研究院股份有限公司，南京 210018；2. 常州工学院 经济与管理学院，常州 213001)
随着人类社会不断发展，自然环境遭受的破坏加重，社会矛盾逐渐突出，各类突发事件频发。面对突发事件，科学合理的应急设施选址与配送路径规划，对开展应急救援工作、减少突发事件损失具有极为重要的意义。
传统的应急设施选址模型，如P-中值模型、P-中心模型和覆盖模型等，已有较为成熟的研究应用。孙华丽等[1]基于P-中值模型进行不确定信息下的应急设施选址方案鲁棒优化，确保应急物流系统的风险应对能力。郗蒙浩等[2]以各个应急救援需求点到应急设施的加权距离和最小为优化目标，提出了一种考虑区域自然灾害风险区划的改进P-中值模型，并采用变邻域算法进行求解，可同步获得最优应急设施选址与分配方案。
应急设施选址是一个具有社会性、时效性和经济性的综合问题，部分研究在模型构建中以约束条件或目标函数的形式增加了对相关影响因素的考虑[3]。陈刚等[4]构建了一种考虑居民选择行为的应急避难所选址模型，基于竞争效用理论评价居民的避难所选择行为，并分别采用非线性整数规划与模拟退火算法进行求解。汪文文等[5]构建了一种多目标动态选址模型，分别以物资效用、灾区满意度和配送中心数量反映选址方案的时效性、公平性和均衡性，并基于NSGA-Ⅱ获取模型的局部最优解。Feng等[6]同时以最小化总旅行距离和最小化总运输成本为优化目标，进行城市应急设施选址，并设计了一种变权算法，采用不同的权重因子构建辅助函数对模型进行求解。
在配送路径规划方面，现有研究多基于带约束的车辆路径问题[7]。吕伟等[8]构建了一种考虑受灾点需求时间窗的应急物资配送模型，基于时间惩罚成本与物资满足状况设置软、硬两种时间窗约束，以确保路径规划方案的有效性。康斌等[9]建立了一种多目标应急救援物资配送路径规划模型，以最小化配送完成时间提高物资配送效率，以最小化需求未满足率保证配送公平性，进行物资配送方案制定。Li和Chung[10]探讨了需求不确定条件下的应急物资配送路径规划问题，并提出了一种混合启发式算法对问题进行求解。
应急设施选址与配送路径规划具有紧密的联系，应急设施选址决定了配送路径规划的输入条件，配送路径规划则是评价应急设施选址方案有效性最直接的指标。因此，将应急设施选址和配送路径规划联合考虑，具有重要意义。
本文构建了一种基于多目标优化的应急设施选址-配送模型，分别从时效、容量和成本的角度实现目标优化，以同步解决应急设施的选址-配送问题，并采用NSGA-Ⅱ对所提出的模型进行求解，从而为系统性的应急设施选址-配送方案的制定提供参考依据。
1 模型构建
1.1 基本假设
模型构建的基本假设主要包括：①道路网络情况已知，可形成网络任意两节点间的有效连接；具备先进的应急调度系统，各个应急设施服从系统联合调配。②各个应急设施的相应资源能够满足所有集散点的总需求；各个集散点基于公平性原则进行资源获取[11]。
1.2 参数和变量
模型构建参数如表1所示。变量如表2所示。
表1 模型构建参数
表2 变量
1.3 目标函数
模型目标函数见式(1)～式(3)。
(1)
(2)
(3)
式中，f1为要求最小化总物资运输时间成本，包括所有车辆在网络中进行物资配送的运输时间，以确保选址-配送方案的时效性；f2为要求最大化应急设施的设置容量，以确保应急设施物资储备；f3为要求最小化应急设施的设置数量，以尽可能降低应急设施设置成本。
1.4 约束条件
约束条件见式(4)～式(6)。
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
式(4)限制了变量的内在约束关系，即进行应急设施选址的同时，完成集散点分配。应急设施从网络中的备选点进行选择，因此式(5)要求应急设施设置数量不能超过网络中的备选点数量。式(6)确保网络中所有应急设施的总物资容量必须超过全部集散点的总物资需求。式(7)确保单个应急设施物资容量必须超过该应急设施所服务的全部集散点的总物资需求。式(6)和式(7)要求选址-配送方案的物资储存必须能够满足物资需求。式(8)确保所有集散点均分配应急设施。式(9)确保每个集散点仅被分配1个应急设施。即式(8)和式(9)要求集散点不遗漏、不重复地分配至应急设施，从而构成集散点全覆盖约束。式(10)为车辆运载容量约束，要求车辆在运输过程中的物资分发数量不得超过其最大装载容量。式(11)确保集散点获得物资数量不得超过其物资需求量。式(12)为网络流量平衡约束，确保任意节点的车辆抵达次数等于该节点的车辆出发次数。
2 算法设计
本文所构建的应急设施选址-配送模型为典型的多目标优化问题，通常难以使得各个优化目标同时达到最优，因此可寻找其Pareto(帕累托)最优解。遗传算法是求解多目标优化问题的有效方法，具有适应性强、搜索覆盖面大的优点[12-13]。根据赵星等[14]研究成果，本文结合快速非支配排序，设计了一种多目标遗传算法，以快速有效地获取最优选址-配送方案。算法流程如图1所示。
图1 算法流程
染色体编码规则为：采用实数编码，每个染色体由2个子串组成：子串1的基因数量为X，对应每一个集散点，基因值为1到nv的随机整数，表示集散点与应急车辆之间的服务关系；子串2的基因数量为Y，对应每一辆车，基因值为1到ns的随机整数，表示车辆与应急设施的归属关系。
步骤0：初始化。输入最大迭代次数nmax、交叉概率pc和变异概率pe[13](交叉概率和变异概率取值范围分别为0.1≤pc≤0.9和0 步骤1：令n=0，生成初始种群。根据染色体编码规则，在约束条件控制下，组合网络中的备选节点、车辆与集散点，形成选址-配送方案，并计算方案目标函数值f1、f2和f3。在此基础上，不断生成方案个体并将其纳入初始种群集合Pn中，直至初始种群中的个体数达到np。 步骤2：生成子代种群。不断从父代种群Pn中选择父代个体，根据交叉概率pc与变异概率pe，采用轮盘赌规则执行交叉和变异操作，生成子代个体，将满足模型约束条件的子代个体纳入子代种群中，得到子代种群Pg。 步骤4：修剪种群。根据序值将种群Pt中的所有个体进行排序，选择其中前np个个体形成新种群Pn，完成种群修剪。 步骤5：检验迭代终止条件。若n≤nmax，则令n=n+1，并重新进入步骤2；反之，进入步骤6。 步骤6：将种群Pn中全部序值为1的个体纳入Pareto解集F1。基于Pareto解集F1，引入各个优化目标的权重，计算模型综合目标函数，获取模型最优解。 (1) 基于离差标准化公式，见式(13)，将模型的各优化目标f1、f2、f3进行标准化。 (13) (2) 优化目标f1、f2、f3的权重值分别设置为μ1、μ2、μ3，μ1+μ2+μ3=1，模型综合目标函数见式(14)。此时，对应最小F′(u)的解即为模型最优选址-配送方案。 (14) 为了验证所提模型和求解算法的有效性，本试验基于苏尔福斯网络(Sioux Falls network)进行了案例分析[15]。 苏尔福斯网络如图2所示，网络中的各个节点与路段已进行编号。假设各路段均设有应急专用车道，应急车辆在各路段的通行时间如表3所示。 图2 苏尔福斯网络 表3 应急车辆在各路段的通行时间 以消毒液为例，假设集散点物资需求如表4所示，备选点库容如表5所示，应急车辆资源充足，最大装载容量为50箱，要求在网络所有备选点中进行一级应急设施选址，并获取二级物资配送方案。在此基础上，采用本试验方法对案例进行求解，模型相应参数设置如下：最大迭代次数nmax为100，交叉概率pc为0.9，变异概率pe为0.1，初始种群数量为10个。本案例中优先考虑应急设施设置成本(目标函数f3)，其次考虑方案时效性(目标函数f1)，再次考虑设施容量(目标函数f2)，因此各优化目标的权重μ1、μ2、μ3分别设置为0.3、0.2、0.5(各优化目标权重可根据实际需求进行调整)。 表4 集散点物资需求 表5 备选点库容 经过算法求解，获得应急设施选址-配送方案，如表6所示，应急设施选址为节点4、14、16，各个应急设施的库容均超过所分配的集散点物资需求总量。该方案的模型综合目标函数为0.62，总物资运输时间成本为276 min，应急设施总库容为500箱，应急设施设置为3个。 表6 应急设施选址-配送方案 基于相同的应急设施设置数量，本试验依据郗蒙浩等[2]研究结果，采用传统P-中值模型进行应急设施选址，采用插入算法进行配送方案设计，获得对照方案，如表7所示。该对照方案的总物资运输时间成本为282 min，应急设施总库容为500箱。将两种方案进行对比可以发现：两种方案均满足模型所提出的全部约束条件；但是相比于对照方案，模型方案的总物资运输时间成本有所降低，并且模型方案可少调用1辆应急车辆。结果表明，本试验所提出的模型与算法能够同步解决应急设施选址与配送路径规划问题，并且能够有效协助决策应急设施设置数量，相比于传统方法具有优越性。 表7 对照方案 本文主要研究突发事件下的应急设施选址-配送问题，构建了一种基于多目标优化的应急设施选址-配送模型，可实现应急设施选址方案与配送路径规划方案的同步求解。从时效、容量、成本的角度提出了3个优化目标，分别要求最小化总物资运输时间成本、最大化应急设施设置容量和最小化应急设施设置数量。为了求解所提出的模型，结合快速非支配排序，设计了多目标遗传算法以获取模型Pareto最优解。通过基于苏尔福斯网络的案例测试，可以发现所提出的模型与算法能够有效地解决应急设施选址-配送问题，相比于传统方法具有优越性，可为相关的应急管理提供参考与支撑。
3 案例分析
4 结论
