通过核搜索和局部分支算法改进热力单元配置问题的数学规划方法

《Computers & Operations Research》：Enhancing matheuristics for a thermal unit commitment problem through kernel search and local branching

针对阶梯成本结构的热力单元承诺问题，提出两阶段混合元启发式算法，结合构造启发式和局部分支、内核搜索等优化机制，实验表明其在中大规模问题上优于传统方法及现有启发式算法。

　　

Uriel I. Lezama-Lope|Roger Z. Ríos-Mercado|Diana L. Huerta-Mu?oz

独立研究员，墨西哥库埃尔纳瓦卡

摘要

机组承诺问题是电力系统运营规划和优化中的一个重要问题。该问题的核心在于确定发电机的最优调度方案，以满足波动的需求同时最小化生产成本。在本研究中，我们探讨了在阶梯式成本结构下的热力机组承诺问题。尽管对数学模型进行重新表述后取得了令人鼓舞的结果，但该问题仍面临诸多挑战。我们提出了一种新颖的两阶段启发式框架：首先使用构造性启发式方法生成高质量的初始解，然后通过局部分支和核搜索等机制进行优化。所提出的方法是一种混合式方法，与现成的求解器结合使用，以加速搜索过程并获得接近最优的解。在具有高挑战性的实例上的实验结果证明了每种启发式组件的有效性和价值，特别是对于大规模实例而言，这种混合方法的表现始终优于单独使用的求解器及现有的启发式方法。

引言

本研究旨在提高解决热力机组承诺问题（UCP）的效率，这是电力系统规划中的一个关键挑战。UCP涉及关于发电机运行的决策，例如开启或关闭机组以及确定最优功率输出水平，以满足消费者需求，同时满足运营、技术和经济约束。作为一项日常优化任务，它旨在在遵守电力系统、发电机特性和市场要求的前提下最小化生产成本。通常，UCP是通过构建适当的混合整数线性规划（MILP）模型来解决的。

尽管在模型和算法方面取得了最新进展，但在有限的时间内解决UCP仍然是一个挑战。为此，本研究旨在提供一个混合启发式框架，试图利用核搜索和局部分支等组件的优势，在规定的时间内实现最优或接近最优的解。

所提出的解决方案算法包括两个阶段：构建阶段和改进阶段。在第一阶段，我们开发了一种称为HARDUC的放松-适应启发式方法来构建问题的可行解；在第二阶段，我们采用局部分支（Fischetti和Lodi，2003年）和核搜索（Angelelli等人，2010年）机制来改进解。

该通用算法及其各个组件在Kazarlis等人（1996年）提供的三组实例中进行了全面评估。实证评估还包括与Harjunkoski等人（2021年）的HGPS启发式方法和Knueven等人（2020年）提出的热力UCP MILP模型的CPLEX求解器的比较。

观察到，虽然分支定界求解器在小型问题实例中表现优异，但我们的方法在规定的时间内始终能为中型和大型实例获得更好的结果。特别是，我们的方法在所有情况下都能可靠地生成解，而求解器在中型和大型实例中经常无法找到可行解。

本文的结构如下：第2节回顾了与UCP相关的算法（包括启发式方法）的最新研究，并概述了本文的具体贡献；第3节介绍了问题、其假设和数学建模；第4节详细描述了所提出的解决方案框架及其各个组件；第5节对算法进行了实证评估，并与现有方法进行了比较；第6节给出了结论和未来研究方向的讨论。

文献综述

UCP模型分为确定性和随机性两种。在我们的工作中，我们处理的是确定性模型，因此文献综述重点关注确定性模型和方法。对于随机性UCP，建议读者参考H?berg（2019年）的相关工作，该工作回顾了用于处理UCP不确定性的模型和算法。

关于UCP模型的文献非常丰富（Montero等人，2022年）。几十年来，UCP模型已被广泛用于能源生产管理。

问题定义和假设

机组承诺问题（UCP）的目标是在规划时段内最小化一组发电机的总运营成本。$g\in G$。目标函数考虑了多种成本组成部分：生产成本$c_{gt}^{\text{p}}$、固定成本$C_{\text{R}}^{}$、启动成本$c_g^{\text{SU}}$以及停机成本$c_g^{\text{SD}}$。实现这一目标需要遵守反映系统物理和运营限制的约束条件，以确保发电机调度的可行性和优化。这些约束条件涵盖了各个方面

提出的启发式方法

所提出的热力UCP解决方案方法包括两个阶段：构建阶段，用于构建初始可行解；改进阶段，对构建的解应用五种程序，包括KS和四种定制的LB版本。本节的其余部分将进一步解释这些组件。

计算实验

在本节中，我们展示了所提算法的评估结果。所有方法均使用Python 3.10.0版本和Pyomo 6.6.1代数建模语言编写，优化求解器采用IBM(R) ILOG(R) CPLEX(R) 22.1.0.0版本。测试在配备64 GB RAM和2.50 GHz Intel(R) i7(R) 11700 CPU（65 W）的64位平台上进行，操作系统为Linux Ubuntu 20.0。

对于所有测试，相对最优性差距（ROG）的计算方法如下：$\text{ROG}=\frac{|Lobund?z\text{\_}b\mathrm{es}t|}{}$

结论

我们开发了五种方法来解决热力UCP问题，其中四种基于局部分支，一种基于核搜索。此外，还开发了一种构造性启发式方法（HARDUC）来为启发式方法提供初始解。

在基于LB的方法中，LB3最接近原始的局部分支算法，而LB1、LB2和LB4则是实现了软固定概念和受限候选列表的变体。

CRediT作者贡献声明

Uriel I. Lezama-Lope：撰写——原始草稿、可视化、验证、软件开发、方法论设计、调查、形式分析、数据整理。Roger Z. Ríos-Mercado：撰写——原始草稿、验证、监督、资源协调、项目管理、方法论设计、资金获取、形式分析、概念构思。Diana L. Huerta-Mu?oz：撰写——原始草稿、验证、方法论设计、形式分析。

致谢

我们感谢两位匿名审稿人的宝贵意见，他们的批评有助于提高本文的质量。Uriel Lezama-Lope获得了墨西哥人文、科学和技术委员会（CONAHCYT）的博士研究奖学金。Roger Ríos-Mercado的研究由CONAHCYT资助（项目编号：CF-2023-I-880）。Diana Huerta-Mu?oz的研究得到了CONAHCYT的博士后奖学金支持。