疫情期间生活物资集散点选址问题的降阶回溯算法.pdf

收稿日期：；修回日期：基金项目：国家自然科学基金资助项目（）；上海市“管理科学与工程”高原学科建设项目作者简介：储旭（），男，安徽安庆人，硕士研究生，主要研究方向为算法、系统工程；宁爱兵（），男（通信作者），湖南邵东人，副教授，硕导，博士，主要研究方向为算法设计、系统工程（）；胡开元（），男，浙江绍兴人，硕士研究生，主要研究方向为算法、系统工程；代苏玉（），女，安徽滁州人，本科，主要研究方向为管理科学；张惠珍（），女，山西人，副教授，硕导，博士，主要研究方向为优化算法疫情期间生活物资集散点选址问题的降阶回溯算法储旭，宁爱兵，胡开元，代苏玉，张惠珍（上海理工大学 管理学院，上海 ）摘要：疫情爆发后，封控区内居民的生活物资发放问题成为亟待解决的焦点问题之一，该问题可抽象为疫情期间生活物资集散点选址问题，其实质为组合优化中的 问题。基于疫情封控期间的应急生活物资集散点选址问题的精确算法进行研究，首先得出一些可以降低问题规模的数学性质并证明利用这些性质可以减小问题规模，降低问题的求解难度；然后设计出分配子算法、上下界子算法以及降阶子算法；基于这些子算法提出一种可以减小问题规模同时得到最优解的降阶回溯算法；最后通过分析和求解若干个示例进一步阐述该算法的原理和执行过程，结果表明该算法能通过减小问题规模来降低问题求解的难度。关键词：生活物资集散点选址问题；数学性质；分配算法；上下界算法；降阶回溯算法中图分类号：文献标志码：文章编号：（）：，（，）：，：；引言近年来，自然灾害、事故灾难、公共卫生事件和社会安全事件等突发事件在世界各地频发，严重危害了受灾地区居民的生命安全。自 年以来新冠疫情肆虐全球，由于疫情爆发的高度不确定性和高度破坏性，造成的人员伤亡和经济损失无法估量。疫情爆发后，封控区内的居民面临物资供给不足的问题，尤其是食物、饮用水和医疗物资的不足使居民生命安全受到威胁，及时有效地将应急物资运往各封控区并合理有序地分配给居民，是保障居民生命安全以及应对疫情的有力措施。疫情期间应急物资储备设施的选址是保障封控所需各种物资供应的基础工作，科学的应急物资储备设施选址方案才能高效合理地调运和分配应急物资。非特殊的设施选址是 问题 ，除非 ，否则不存在多项式时间内的解。国内外学者对应急物资储备设施选址问题进行了大量的研究。袁颖 研究了重大疫情下应急医疗服务设施选址问题，构建了以医疗设施物理成本和心理成本最小化为目标的双目标优化模型，并使用非支配排序遗传算法求解。宋英华等人 研究了常态化疫情防控背景下区域应急医疗物资选址分配问题，构建以医院储备点需求未满足率加权和最小化及物资购买点物资分配公平性最大化为目标的选址模型，并使用非支配排序遗传算法求解。王紫岩 研究了新冠疫情背景下的防疫物资储备中心选址分配问题，并使用遗传算法求解。郗蒙浩等人 研究了国家级应急物资储备设施选址优化布局问题，考虑了地区人口分布、经济条件、交通状况和多重覆盖关键地区等综合因素，并使用变邻域算法求解。朱莉等人 研究了考虑区域异质性的应急物资选址分配优化问题，将反映时间因素纳入应急总成本决策考量时的最优选址和物资分配优第 卷第 期 年 月计 算 机 应 用 研 究 化问题，并使用遗传算法求解。于冬梅等人 研究了共享不确定需求和中断情景下服务能力有限的应急设施多级覆盖选址鲁棒优化模型，并使用灰狼优化算法求解。丛雯婧 研究了台风灾害情景下的区域应急物资储备库选址问题，设计了带精英策略的非支配排序遗传算法进行求解。郑夏等人 构建了应急物资储备中心多目标优化选址模型，并设计引入局部搜索机制的免疫非线性算法进行求解。刘博等人 研究了政企协同视角下应急物资储备库选址问题，构建以加权时间最小化和政府初始成本最小化为目标的应急物资储备库选址模型，并使用非支配排序遗传算法求解。彭大江等人 研究了基于模糊需求的应急物资中心选址路径问题，并使用基于 学习的超启发式算法求解；他们还研究了应急资源中心选址问题，并提出了一种改进的多目标离散粒子群优化方法求解 。等人 针对灾害中临时应急服务中心选址问题提出了一种多目标选址分析模型，并使用具有目标规划的综合迭代分支和定界算法求解。研究了同时考虑到随机性和不确定性的应急商品的灾前选址和储存模型，并使用改进的列和约束生成方法求解。宋英华等人 考虑动态需求的应急物资配送中心选址问题，并使用耦合 算法的分层序列法求解。胡少龙等人 研究了考虑应急物资需求的不确定性的应急物资配置问题，并设计了基于机器学习的样本均值近似算法进行求解。谭正园等人 研究了新冠肺炎疫情下应急物资储备仓库选址问题，构建应急物资配送仓库选址的最大覆盖模型，并使用层次分析法求解。张敏等人 研究了基于失效情景下新增中央储备库选址问题，并选取处理多输入多输出问题具有优势的评估方法 数据包络法进行评估，最终得出选址方案。目前求解应急物资储备设施选址问题的算法主要分为四类：）评估方法，如层次分析法、数据包络法，评估方法的缺点在于其带有一定的主观性；）近似算法，它可以保证在多项式时间内获得一个常数近似比的解，但是无法得到问题的最优解；）启发式算法，如遗传算法、粒子群优化算法、灰狼优化算法等，启发式算法的优点是可以快速得到问题的一个可行解，但是此类算法所获得的解的质量无法保证；）精确算法，如分支定界法、列和约束生成法，此类算法能保证得到全局最优解，但是由于没有研究问题本身的数学性质来加快算法的执行速度，求解速度较慢。本文以 年以来全国范围内多次较大规模区域性疫情爆发为背景，对封闭式管理期间衍生的应急生活物资集散点选址问题构建数学模型，并提出了求解该问题的一种精确算法。在该算法中，首先探究了该问题的数学性质，其中某些性质可以批量地确定某些设施备选点必须开设或者必须不开设；然后给出上界和下界子算法，并结合降阶子算法设计了一个降阶回溯算法，它与单纯的回溯算法相比通过降阶子算法减小了问题的规模，通过上下界子算法加快了求解的速度；最后对该算法的时间复杂度与特点进行分析，并通过分析和求解若干个示例来验证该降阶回溯算法可以减小问题规模并剪枝，从而加快问题的求解速度，最终得到问题的最优解。问题描述 问题介绍当疫情出现区域性爆发时，对相关社区采取封闭式管理是快速扑灭疫情的有效方式，针对大量、分散的居家隔离人员实现统一化管理成为新的难点问题。相关数据分析表明，在疫情期间政府完全有能力调动足够数量的生活物资，只是生活物资发放给社区居民的渠道不畅 。为了解决这个问题，可在城市中建造一定数量的生活物资集散点，各集散点向上接收物资储备库的物资，向下负责若干个居民点的生活物资的有序发放，所以生活物资集散点的科学选址成为了至关重要的问题。数学符号与解释数字符号与解释如表 所示。表 数学符号与解释 集合符号解释表示所有居民点的集合，其中 为居民点数量表示所有物资集散备选点的集合，其中 为物资集散备选点数量（，）物资集散备选点集合 和居民点集合 构成的二分图，其中 （，）原始二分图 的某个点导出子图，分别表示在算法中一定不开设、开设、不确定是否开设的备选点集合，初始化为 ，始终成立，均为全局变量，分别表示在算法中假设不开设、开设、不确定是否开设的备选点集合，初始化为 ，始终成立，均为全局变量当 时，物资需求全部被满足的居民点构成的集合，为全局变量 当 时，物资需求全部被满足的居民点构成的集合，为全局变量 需求未被完全满足的居民点集合，为全局变量该问题的可行解对应的开设备选点的集合，为局部变量 表示算法在当前状态下已知最好的目标函数值对应的开设设施集合，为全局变量该问题的最优解对应的开设设施集合，为全局变量（，）表示节点 在图 中的邻点集服务集，用于存储物资集散点与居民点的服务关系参数取值范围符号解释?物资集散点的最大选址数量?各物资集散备选点的最大覆盖半径?每人每天所需物资总量?居民点 到备选点 的距离?居民点 的人口数量?物资集散备选点 的最大容量?表示居民点 未满足的需求量，（，）?表示物资集散 备 选 点 的 剩 余 容 量，（，）（，）?居民点 在图 中的最短服务距离 （，）?居民点 在图 中的次短服务距离?表示算法在当前状态下已知最好的目标函数值，为全局变量?算法在某一状态下的目标函数值上界，为全局变量?算法在某一状态下的目标函数值下界，为局部变量?回溯算法的当前搜索层数，为局部变量 下界子算法无解时的返回值，为常量 变量取值范围符号解释 ，若备选点 被选为物资集散点则 ，否则?居民点 被分配到备选点 的需求量为了描述方便，本文声明以下集合更新规则：规则 始终成立，始终成立，始终成立。规则 若通过数学性质判断出某个备选点 必须开设，则更新 ，。规则 若通过数学性质判断出某个备选点 必须不开设，则更新 ，。计 算 机 应 用 研 究 第 卷规则 若假设某个备选点 开设，则更新 ，。规则 若假设某个备选点 不开设，则更新 ，。数学模型本文用二分图来表示疫情期间生活物资集散点的选址问题：将 和 中的元素分别作为二分图的两个顶点子集 和，对于给定的各物资集散备选点的最大覆盖半径 ，若 中 与 中 的距离 不超过 ，则 与 之间存在路径，将所有路径放入集合 中，处理后得到一个二分图（，），其中 ，显然图 是一个二分图。基于上文中定义的数学符号，该问题的数学模型可描述如下：（）（），（），（）（），；，（），；，（），（）目标函数式（）表示最小化备选点和居民点之间的加权距离和；约束式（）表示最多开设 个物资集散点；约束式（）表示每个居民点的所有需求均要被全部满足；约束式（）表示每个开设的物资集散点所覆盖居民点的物资总需求量不能超过该备选点的容量；约束式（）表示所有物资集散备选点的总容量应不小于所有居民点的总需求量；约束式（）表示居民点和物资储备点之间的距离不超过物资集散备选点的最大覆盖半径 ，应结合实际地理信息和交通状况，并根据居民能容忍的最大响应时间而综合确定；约束式（）描述了居民点 被分配到设施备选点 的需求量的取值范围；约束式（）为 变量约束。数学性质性质 若图 为非连通图，则可对图 的各连通分量看做独立的子问题分别求解。证明因为子问题之间不存在通路，求解时相互独立，互不影响，所以可以分别求解。性质 算法执行过程中，若 ，则当 时，该问题无解；当 时，该情况下无解。证明此时开设的备选点数量已经超过了 ，当 时，该问题无解；当 时，此时得出的结论基于假设，故该情况下无解。性质 算法执行过程中，若存在 （，）孤立节点，则当 时，该问题无解；当 时，该情况下无解。证明此时没有备选点能为居民点 提供服务，当 时，该问题无解；当 时，此时得出的结论基于假设，故该情况下无解。性质 算法执行过程中，若满足 ，则当 时，该问题无解；当 时，该情况下无解。证明此时所有可能开设的备选点的总剩余容量小于所有需求点的总未满足需求量，当 时，该问题无解；当 时，此时得出的结论基于假设，故该情况下无解。性质 当 时，若存在 （，）的节点，（，）中唯一的备选点为，若 ，则物资集散备选点 一定开设且为居民点 提供服务，此时将 加入，将 加入，并将边 加入服务集 。证明用反证法。（，）表示仅有一个物资集散备选点可以为居民点 提供服务，表示备选点 的剩余容量足以容纳居民点 的剩余需求量；若未开设该备选点，则没有备选点可以为居民点 提供服务。性质 当 时，若存在 （，）的节点，（，）中唯一的备选点为，若，则物资集散备选点 一定开设且为居民点 提供服务，此时将 加入 ，将 加入 。证明用反证法。（，）表示仅有一个物资集散备选点可以为居民点 提供服务，表示备选点 的剩余容量足以容纳居民点 的剩余需求量，若未开设该备选点，则没有备选点可以为居民点 提供服务。由于 ，此时得出的结论基于假设，所以将 （，）加入 ，将 加入 。性质 在导出子图 中，令集合 表示以最短距离 （，）为 中各居民点 提供服务的备选点构成的集合，若 ；且 ，有 （，）且 （，），则 即为当前情况下最优解对应的开设备选点的集合。证明此时开设集合 中的备选点可使得所有居民点均以其最短服务距离被覆盖，并且集合 中的每个备选点 以最短距离覆盖的居民点的总物资需求量均不超过其剩余容量。此时得到的目标函数值最小，故结论正确。性质 对于 中任意物资集散备选点 和，若满足 （，）（，），且（，），有 ，并且（，），则称备选点 相对于严格劣势，备选点 必须不开设。当 时，将 加入，当 时，将 加入 ；然后删除 及其关联边。证明因为此时 起到的覆盖作用完全可以由 来代替且连接距离更短，而且 的剩余容量也能够容纳 （，）中所有居民点的剩余需求量，所以结论正确。性质 算法执行过程中，对于备选点 和居民点，当 时，若 （，），有 ，且（，），即此时就居民点 而言，相对于 严格劣势，则可以删除边。证明由于此时物资集散备选点 的剩余容量足以覆盖其所有邻接居民点的需求，此时居民点 可以不由 覆盖（）的这部分需求，而是由 覆盖其全部未满足需求，并且连接距离更短，所以结论正确。性质 当 时，若假设某个备选点 在最优解中，如果此时的下界 或者 大于上界 ，则 一定不在最优解中，应将 加入；判断结束后恢复 。证明当假设某个节点 在最优解中时，若下界 或者 大于上界 ，此时不可能获得最优解，所以备选点 必不在最优解中。性质 当 时，若假设某个备选点 不在最优解中，如果此时的下界 或者 大于上界 ，则 一定在最优解中，应将 加入，判断结束后恢复 。证明当假设某个节点 不在最优解中时，若下界第 期储旭，等：疫情期间生活物资集散点选址问题的降阶回溯算法 或者 大于上界 ，此时不可能获得最优解，所以备选点 必在最优解中。性质 当 时，若假设某个备选点 不在 最 优 解 中，此 时 ，如 果 此 时 ，则，也即 一定在最优解中，应将 加入，判断结束后恢复 。证明当假设某个节点 不在最优解中，如果此时 中所有备选点的剩余容量小于 中所有居民点的剩余需求量，则该问题无解，故 必须在最优解中，应将 加入。算法设计与分析 分配子算法在生活物资集散点选址问题中，首先要从所有备选点中选取开设的备选点，然后将居民点的需求分配给这些备选点。由于本文研究的生活物资集散点选址问题中各备选点都有容量限制，居民点需求的不同分配方式会得到不同的目标值，所以需要在多项式时间内找到一种最优分配方案，进而得到该情况下的最优目标值。本文使用最小费用最大流算法 来实现最优分配。分配子算法的具体步骤如下：）初始化集合 。）若 （，），也即 中的备选点无法覆盖所有需求未被完全满足的居民点，则分配子算法无解，结束分配子算法。）删除集合 和 之间满足性质 的边。）采用最小费用最大流算法进行分配，算法内部使用 算法 求解含有负权边的单源最短路径问题，具体操作步骤如下：（）设立一个超级源点 和一个超级汇点 ；（）将超级源点 连向 中所有的居民点，各边的容量为各居民点的未满足需求量，各边的距离为 ；（）将 中所有备选点连向超级汇点 ，各边的容量为各备选点的剩余容量，各边的距离为 ；（）将各备选点与居民点连接边上的容量设置为 ，各边的距离为原始图 中各边之间的距离；（）计算从超级源点 到超级汇点 的最小费用最大流，由于本文研究的问题要求居民点的需求量实现全覆盖，所以若算法结束后超级源点 到各居民点之间存在非饱和弧，则分配子算法无解；否则得到 对应的最优分配方案，求得的最小费用即为当前 对应的最优目标值。为了更清晰地说明分配子算法的执行过程，下面给出一个简单的示例说明。例 如图 所示的分配问题，居民点集合 ，备选点集合 ，各居民点下方标注的数字为其需求量，各备选点上方标注的数字为其容量，各边上标注的数字为居民点和备选点之间的距离。假设 ，此时该如何分配才能使得各居民点的需求被完全覆盖，同时使得目标函数值最小。图 例 中待分配的居民点和设施备选点 对例 的分配过程可描述如下：），且该示例不满足分配子算法中 ）和 ）的条件。）使用最小费用最大流算法求解该分配问题：（）按照分配子算法 ）中的（）（）构建如图 （）所示的网络图。（）求解最小费用最大流：取初始可行流为零流，构造如图 （）所示的有向赋权图，求出 到 的最短路径，对应原网络中的增广链为 ，流量调整量 ，调整后的网络如图 （）所示。基于图 （）所示的可行流，构造如图 （）所示的有向赋权图，求出 到 的最短路径，对应原网络中的增广链为 ，流量调整量 ，调整后的网络如图 （）所示。基于图 （）所示的可行流，构造如图 （）所示的有向赋权图，求出 到 的最短路径，对应原网络中的增广链为 ，流量调整量 ，调整后的网络如图 （）所示。基于图 （）所示的可行流，构造如图 （）所示的有向赋权图，求出 到 的最短路径，对应原网络中的增广链为 ，流量调整量 ，调整后的网络如图 （）所示。基于图 （）所示的可行流，构造如图 （）所示的有向赋权图，此时超级源点 只有入边，没有出边，无法求出从 到 的最短路径，最小费用最大流算法结束。注意到此时超级源点到各居民点之间均为饱和弧，分配可行，最优目标值为 。图 例 中使用最小费用最大流算法求解最优分配方案 上界子算法对于该问题，任意一个可行解对应的目标函数值均能作为该问题的上界。本文在充分利用数学性质并结合贪心思想的基础上给出的该问题上界比大部分可行解要好，在回溯子算法中，若出现更优的目标函数值则更新上界。上界子算法的具体步骤如下：）由性质 找出一定不开设的备选点加入集合，然后由性质 和 判断该问题是否无解，由性质 判断是否能直接得到该问题的最优解。计 算 机 应 用 研 究 第 卷）由性质 找出所有一定开设的备选点 加入集合，由性质 判断该问题是否无解；否则将对应的居民点加入，并更新 中各备选点的剩余容量。）初始化 ，始终成立，始终成立。）将 中各居民点 的剩余需求量 分配给其 （，）对应的备选点，并将各 加入集合 。）若 且，均有 ，则已经得到最优解，整个算法结束；否则转至 ）对超出的选址点数量进行调整。）将此时满足性质 的备选点加入集合 ，并将对应的居民点加入集合 。）若 且 ，则上界子算法无解，返回 作为上界，上界子算法结束；若 且 ，则转至 ）对超出的选址点数量进行调整；若 ，判断，是否成立，若成立则 ，上界子算法结束，若不成立则转至 ）对过载的备选点进行调整。）对于 中各备选点，假设 以最短距离服务的 中的居民点集合为 （），计算 （）中各居民点 的 （，）（，）值并求和，其值记为 （），该值的含义为：若删去备选点，其以 （，）服务的所有居民点 转接至 中其他备选点至少增加的目标函数值。假设 为 中 （）值最小的备选点，执行 ，并将 所辖的各居民点转接至 中次短距离对应的备选点上，转回 ）。）将 中所有的过载备选点加入集合 ，然后按照如下步骤执行：（）遍历 中各备选点，令 （）（，）。（）对于 （）中各居民点，计算 （，）（，）值，记为 （），该值的含义为居民点 的单位需求量转接至 中其他备选点至少会增加的目标函数值；将 （）中各居民点按照 （）值从小到大排序。（）假设 （）表示过载备选点 的过载量，遍历经过排序后集合 （）中的各居民点，定义本轮调整量为 ，若 （），则 ；若 （），则 （），定义变量 。（）将 （，）中各备选点按照连接距离 从小到大排序，然后遍历排序后该集合中各备选点，若 ，则当前备选点 可以完全容纳 ，将 与 连线，执行 并退出循环；若 ，则当前备选点 可以容纳 的一部分，将 与 连线，执行 ，继续遍历（，）中下一个元素；若 ，则当前备选点无法容纳 ，继续遍历 （，）中下一个备选点。（）（）中循环结束后，若仍有 ，则上界子算法无解，返回 作为上界，上界子算法结束，否则执行 （）（）；此时若 （），则当前过载点 已调整完毕，退出（）中循环并继续调整其他过载点，若 （），则转至（）继续调整当前过载点。）集合 中所有过载备选点调整完毕后，计算 ，。例 如图 所示的物资集散点选址问题，当 时，试根据上界子算法求出该问题的一个上界。图 例 的初始状态 对例 求解上界的过程可描述如下：）由性质 ，将 加入（如图 （）中细虚线）。）由性质 ，将、加入，并将、加入（如图（）粗虚线）。）初始化 ，。）将 中各居民点 的剩余需求量 分配给其 （，）对应的备选点（如图 （）中粗实线），并将各 加入集合 。图 例 上界子算法的执行过程 ），转至 ）。）根据性质 ，。）此时 且 ，转至 ）对超出的选址点数量进行调整。），。（），（），（），（）；（），（）；（），（）；中 （）值最小的备选点为，执行 ，并将 转接至，转回 ）。）根据性质，（图（）中粗虚线）。）此时 且 ，转至 ）继续调整。第 期储旭，等：疫情期间生活物资集散点选址问题的降阶回溯算法），（），（）；（），（）；中 （）值最小的备选点为，执行 ，并将 转接到 上，转接到 上，转回 ）。）根据性质 ，（图 （）中粗虚线）。）此时 ，但备选点 和 的负载量超出容量限制，转至 ）进行调整。），。对于过载点，有 （），（），（），将 （）中各元素按照 （）值从小到大排序后为，；（），遍历集合 （），对于居民点，有 （），则 （），令 ；（，）中各备选点按照连接距离从小到大排序后为 ；此时有 ，则备选点 可以完全容纳 ，将 与 连线，执行 ，退出循环；此时有 ，故执行 （）（），过载点 已调整完毕。同理可调整过载点，调整结果如图 （）所示。）计算上界，。下界子算法基于上文的数学性质，设计一个下界子算法，求在、已知情况下目标函数值的下界。在下界子算法中，考虑原问题中去掉容量约束式（）后的松弛问题。基于此，在下界子算法中，先利用数学性质进行降阶，然后根据贪心策略计算下界。下界子算法的具体步骤如下：）由性质 找出 中一定不开设的备选点加入集合，然后由性质和判断该情况下是否无解，若无解则返回 ，下界子算法结束。）由性质 找出 中一定开设的备选点 加入集合 ，由性质 判断该情况下是否无解，若无解则返回 ，下界子算法结束；否则将对应的居民点加入 ，更新 中各备选点的剩余容量，此时若 中存在剩余容量小于 的备选点，则该情况下无解，下界子算法结束，否则转至 ）。）初始化集合 ，始终成立，始终成立。）将 中各居民点 的剩余需求量 分配给其 （，）对应的备选点，并将 加入集合 。）若 ，下界 ，下界子算法结束。）对于 中各备选点，假设 以最短距离服务的 中的居民点集合为 （），计算 （）中各居民点 的 （，）（，）值并求和，其值记为 （），该值的含义为：若删去备选点，其以 （，）服务的所有居民点 转接至 中其他备选点至少会增加的目标函数值。）若 ，下 界 （）；若 ，将 中各元素按 （）值从小到大排序，取排序后前 个元素构成的集合为 ，执行 （）。降阶子算法降阶子算法主要通过数学性质判断某些备选点一定开设或者一定不开设，从而减小问题的规模；调用降阶子算法之前，需先调用上界子算法计算出问题的初始上界，且上界子算法中已经利用数学性质对该问题进行了部分降阶操作。降阶子算法的具体步骤如下：）利用性质 对问题进行降阶，若处理完毕后 发生变化，则由性质 和 判断该问题是否无解，由性质 判断是否能直接得到该问题的最优解，再由性质 对问题进行降阶，由性质判断该问题是否无解；）利用性质 对问题进行降阶，若处理完毕后 发生变化，则由性质 判断该问题是否无解；）利用性质 对问题进行降阶，若处理完毕后发生变化，则由性质 判断该问题是否无解；）利用性质 对问题进行降阶。回溯子算法本文的回溯子算法从根节点出发，以深度优先的方式对解空间二叉树进行搜索。搜索到任意节点先利用数学性质进行处理，然后计算当前节点的下界 ，如果此时的下界 或者 大于上界 ，则进行剪枝，否则对 中编号最小的备选点 分成两种情况处理：假设备选点 开设，对应搜索左子树；假设备选点 不开设，对应搜索右子树。回溯子算法 （）的具体步骤如下：）若 ，返回上一层；若 ，则到达叶子节点，调用分配子算法，若分配子算法有解，则得到可行解（），若 的目标函数值 则更新上界及最优解 ，然后返回上一层。）假设备选点 开设，判断此时是否满足性质 的条件，若满足则该情况下无可行解，左子树剪枝；否则调用下界子算法计算下界 ，若 且 ，则此时可能存在比当前上界更优的解，调用 （）继续搜索，若 或者 ，左子树剪枝，转至 ）。）返回上一层前执行 ，。）假设备选点 不开设，判断此时是否满足性质 和 的条件，若满足则该情况无可行解，右子树剪枝，转至 ）；否则再判断此时是否满足性质 的条件，若满足则得到可行解 （），若 的目标函数值 则更新上界及最优解 ，；若不满足性质 的条件，则调用下界子算法计算下界 ，若 且 ，则此时可能存在比当前上界更优的解，由性质 得出加入 中的备选点集合为 ，再由性质 得出加入 中的备选点集合为 ，并将对应的居民点加入 ，执行 ，调用 （）继续搜索，若 或者 ，右子树剪枝，转至 ）。）返回上一层前执行 ，。算法结束时，即为该问题的最优目标值，为对应的物资集散备选点集合。主算法）根据居民点集合 和物资集散备选点集合 构建二分图 （，），其中 。）初始化集合，初始化 。）由性质 判断该问题是否需要分为若干个子问题分别求解。）由性质 、判断该问题是否无解。）判断 （，）是否满足性质 的条件，若满足则直接得到最优解，主算法结束。计 算 机 应 用 研 究 第 卷）删除图 （，）中符合性质 条件的边。）调用上界子算法，获取问题的上界 。）调用降阶子算法，对问题进行降阶，若降阶子算法结束后（）发生变化，则转至 ）重新计算上界，否则转至 ）。）调用回溯子算法 （），获取问题的最优解 及最优目标函数值 。算法时间复杂度分析对于设施选址问题，一般的回溯算法中需要逐个判断每个设施备选点是否开设，问题的解空间为二叉树，时间复杂度为（）。而经过降阶子算法降阶处理后，不确定是否开设的备选点集合为，令 ，该算法在最坏情况下的时间复杂度为 （），其中 。对于求解设施选址问题的评估方法、近似算法和启发式算法均无法保证解的最优性，本文提出的算法为精确算法，所得到的解为全局最优解。相较于求解设施选址问题的一般精确算法，本文算法主要在以下三个方面提高了求解速度：）在进入二叉树搜索之前，通过数学性质确定了某些设施备选点必须开设或者必须不开设，之后仅需处理余下的部分设施备选点，降低了算法的时间复杂性；）利用上下界子算法在二叉树搜索过程中进行剪枝，从而仅对部分解空间进行搜索，加快了算法的求解速度；）在二叉树搜索过程中，还可以利用某些数学性质来剪枝或是成批地确定某些设施开设或者不开设从而降阶，进一步加快了算法的求解速度。示例分析 小规模示例分析为了更清晰地说明算法的执行过程，下面通过求解一个小规模示例进行说明，示例中相关常量的设置说明如下：）以平原地区的大中型城市为例，综合考虑地理信息和交通状况以及居民能容忍的最大响应时间，将 设置为 ；）综合考虑人体每天所需蔬菜水果蛋白质等的总量，将 设置为 （人天）。例 继续求解例 中的疫情期间生活物资集散点的选址分配问题。调用主算法对该问题进行求解：）构建二分图 （，）如图 所示。）初始化集合 ，。）该问题无须分为若干个子问题分别求解。）该问题不满足性质 和 的条件，故该问题有解。）该问题不满足性质 的条件，无法直接得到最优解。）图 （，）中没有满足性质 的边。）调用上界子算法，获取问题的上界 ，其具体求解过程参见例 中上界的求解过程。）调用降阶子算法，其具体求解过程如下：在上界子算法中，已经确定 必须不开设，和 必须开设，也即 ，。（）利用性质 对问题进行降阶，：将 加入 ，调用下界子算法求得下界 ，上界 ，满足 ；将 加入 ，调用下界子算法求得下界 ，上界 满足 ；将 加入 ，调用下界子算法求得下界 ，上界 ，满足 ；将 加入 ，调用下界子算法求得下界 ，上界 ，满足 。处理完毕后 未发生变化。（）利用性质 对问题进行降阶，：将 加入 ，调用下界子算法，此时 只能由覆盖，只能由 覆盖，而 的剩余容量仅为 ，小于的需求量 ，所以假设 不开设会导致该情况下无解，返回下界 ，从而 必须开设；将 加入 ，调用下界子算法求得下界 ，上界 满足 ；将 加入 ，调用下界子算法求得下界 ，上界 ，满足 ；将 加入 ，调用下界子算法求得下界 ，上界 ，满足 。处理完毕后 发生变化，由性质判断此时该问题是否无解，由于 ，故该问题有解。（）利用性质 对问题进行降阶，中居民点的总需求量为 ：将 加入 ，此时 中所有备选点总容量为 ；将 加入 ，此时 中所有备选点总容量为 ；将 加入，此时 中所有备选点总容量为 ；将 加入 ，此时 中所有备选点总容量为 。处理完毕后 未发生变化。（）利用性质 对问题进行降阶，此时图 （，）中没有满足性质 的边。降阶子算法结束后，故（）发生变化，转回 ）重新计算上界，此时得到的上界仍为 ，转至 ）继续尝试降阶，降阶子算法结束后（）未发生变化，故转至 ）进入回溯子算法。）调用回溯子算法 （），此时 ，。回溯子算法的求解过程如图 所示，其中序号 瑐瑠表示解空间二叉树的搜索过程。图 例 解空间二叉树的搜索过程 最终，回溯子算法结束后，该问题的最优解 ，最优目标值为 ，对应的分配方案如图 所示。图 例 最优解对应的分配方案 第 期储旭，等：疫情期间生活物资集散点选址问题的降阶回溯算法 随机算例测试为验证该降阶回溯算法在求解本文模型时的有效性，采用 在 机上实现该算法，相关代码可在 ：上查看。采用随机策略生成 个数据集，各居民点人口 ，各备选点容量 ，和 的取值同 节。使用本文设计的降阶回溯算法求解各数据集，测试结果如表 所示，其中 为居民点数量，为备选点数量，为最大选址数量，为降阶后问题的规模。由表 可以看出，本文设计的算法能够通过数学性质在搜索解空间二叉树之前就对问题进行部分降阶，在回溯搜索过程中，又能通过性质 和 实现降阶；并且在回溯搜索过程中还可以通过其他某些数学性质、上下界及问题本身的约束大量剪枝进一步加快算法的求解速度。表 各随机数据集的测试结果 数据集编号（，）降阶率 二叉树理论搜索次数 二叉树实际搜索次数理论叶子节点总数量 实际搜索叶子节点数量剪枝率 回溯搜索时性质 触发次数回溯搜索时性质 触发次数（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）（，）真实案例分析为进一步验证本文提出问题的现实意义及求解算法的可行性，本节求解一个 年上半年长春市高新区疫情封控期间的案例，该案例包括 个生活物资集散备选点以及 个居民点。表 展示了各居民点人口，表 展示了随机生成的各备选点容量 ，。由于篇幅限制，表 仅展示了部分居民点到各备选点的距离（单位：），案例中相关常量的设置说明如下：考虑到长春市是省会城市，综合考虑其地理信息和交通状况以及居民能容忍的最大响应时间，将 设置为 ；取 为 （人天）；取 。使用本文提出的降阶回溯算法对该问题进行求解，计算结果如表 所示。由表 可知，通过降阶子算法在进入回溯搜索前将问题规模从 个降低至 个，降阶率为 ，回溯搜索时又通过性质 实现降阶；通过性质 、及问题本身的约束剪枝，剪枝率为 。综上，该案例再次验证了本文设计的算法可以减小问题规模并剪枝，从而加快问题的求解速度，最终得到问题的最优解。表 各居民点序号及人口数量 序号人口数序号人口数序号人口数序号人口数 计 算 机 应 用 研 究 第 卷表 各备选点的序号及容量 序号 容量 表 各备选点与部分居民点之间的距离矩阵 表 长春市高新区案例的求解结果 （，）降阶率 理论叶子节点总数量 实际搜索叶子节点数量剪枝率 回溯搜索时性质 触发次数回溯搜索时性质 触发次数最优目标值选址结果（，），结束语本文针对疫情期间生活物资集散点选址问题，首先得出一些可以降低问题规模的数学性质并证明，其中某些性质可以批量地确定某些备选点必须开设或者必须不开设从而降阶；然后设计出上下界子算法；最后在上下界子算法的基础上设计出能减小问题规模且能求出最优解的降阶回溯算法。从理论分析可以看出，采用本文设计的算法求解时，在回溯搜索之前和回溯搜索过程中均可以降低问题的规模。在例中，通过降阶子算法将待判断备选点数量从 个降低到 个，时间复杂度由 下降到，同时也将待处理居民点数量从个降低到 个；在搜索解空间二叉树过程中又通过性质 进行降阶，加快了求解速度。在随机算例测试中，各测试数据集都能通过降阶子算法部分减小问题规模，并且在回溯搜索时又能实现降阶或剪枝，进一步加快算法的求解速度。在未来的研究中，一方面考虑继续探索求解应急生活物资集散点选址问题的高效准确的启发式算法，以应对中大规模问题；另一方面考虑将应急生活物资集散点选址问题与其上游问题，即应急生活物资储备库选址问题相融合，构建一个双层选址模型，探究该问题的数学性质并提出高效的求解算法。参考文献：王非，徐渝，李毅学离散设施选址问题研究综述 运筹与管理，（）：（，（）：）刘勇，马良，宁爱兵给定限期条件下应急选址问题的量子竞争决策算法 运筹与管理，（）：（，（）：）袁颖重大疫情下的应急医疗服务设施选址研究 重庆：重庆邮电大学，（：，）宋英华，裴俊龙，方丹辉，等常态化疫情防控背景下区域应急医疗物资选址分配模型 中国安全生产科学技术，（）：（，（）：）王紫岩新冠疫情背景下的防疫物资储备中心选址分配研究 上海：东华大学，（：，）郗蒙浩，张静，赵秋红，等基于 问题的国家级应急物资储备设施选址优化布局研究 自然灾害学报，（）：（，（）：）朱莉，丁家兰，计梦婷考虑区域异质性的应急物资选址分配优化 系统管理学报，（）：（，（）：）于冬梅，高雷阜，赵世杰可靠性应急设施选址多级覆盖鲁棒优化模型 中国矿业大学学报，（）：（，（）：）丛雯婧台风灾害情景下的区域应急物资储备库选址研究 杭州：杭州电子科技大学，（：，）郑夏，马良应急物资储备中心多目标优化选址的仿真研究 计算机仿真，（）：（，第 期储旭，等：疫情期间生活物资集散点选址问题的降阶回溯算法 ，（）：）刘博，徐晓敏政企协同视角下应急物资储备库选址优化研究 北京信息科技大学学报：自然科学版，（）：（，：，（）：）彭大江，叶春明，万孟然基于模糊需求的应急物资中心选址路径问题的算法研究 计算机应用研究，（）：（，（）：），（）：，（）：，（）：宋英华，苏贝贝，霍非舟，等考虑动态需求的应急物资配送中心快速选址研究 中国安全科学学报，（）：（，（）：）胡少龙，范婷睿基于机器学习的样本均值近似算法求解应急物资配置问题 管理现代化，（）：（，（）：）谭正园，李嘉丽，唐琳婕，等新冠肺炎疫情下应急物资储备仓库选址研究 以南宁市为例 中国物流与采购，（）：（，：，（）：）张敏，黄钧考虑关键交通路段失效情景的中央储备库选址评估 运筹与管理，（）：（，（）：）姜凯凯，高尘，孙洁依托便利店构建生活物资应急配送终端体系 以日本便利店的灾后救援经验为例 国际城市规划，（）：（，：，（）：）运筹学 教材编写组运筹学 版北京：清华大学出版社，：（“”：，：），（）：（上接第 页），（）：，（）：，（）：，：，（）：，：（），（）：，（）：，（）：贺毅朝，王熙照，赵书良，等基于编码转换的离散演化算法设计与应用 软件学报，（）：（，（）：），（）：，（）：，（）：王泽昆，贺毅朝，李焕哲，等基于新颖 型转换函数的二进制粒子群优化算法求解具有单连续变量的背包问题 计算机应用，（）：（，（）：），（）：计 算 机 应 用 研 究 第 卷