土耳其市场清算问题的自适应禁忌搜索算法

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《An Adaptive Tabu Search Algorithm for Market Clearing Problem in Turkish
  Day-Ahead Market》
---
作者：
Nermin Elif Kurt, H. Bahadir Sahin, K\\\"ur\\c{s}ad Derinkuyu
---
最新提交年份：
2018
---
英文摘要：
  In this study, we focus on the market clearing problem of Turkish day-ahead electricity market. We propose a mathematical model by extending the variety of bid types for different price regions. The commercial solvers may not find any feasible solution for the proposed problem in some instances within the given time limits. Hence, we design an adaptive tabu search (ATS) algorithm to solve the problem. ATS discretizes continuous search space arising from the flow variables. Our method has adaptive radius and it achieves backtracking by a commercial solver. Then, we compare the performance of ATS with a heuristic decomposition method from the literature by using synthetic data sets. We evaluate the performances of the algorithms with respect to their solution times and surplus differences. ATS performs better in most of the sets.
---
中文摘要：
在本研究中，我们重点研究土耳其日前电力市场的市场清算问题。我们通过扩展不同价格区域的投标类型，提出了一个数学模型。在某些情况下，商业解决方案可能无法在给定的时间限制内找到任何可行的解决方案。因此，我们设计了一种自适应禁忌搜索（ATS）算法来解决这个问题。ATS将流量变量产生的连续搜索空间离散化。我们的方法具有自适应半径，并通过商业求解器实现回溯。然后，我们使用合成数据集，将ATS的性能与文献中的启发式分解方法进行了比较。我们评估了算法在求解时间和剩余差方面的性能。ATS在大多数情况下表现更好。
---
分类信息：

一级分类：Quantitative Finance        数量金融学
二级分类：Trading and Market Microstructure        交易与市场微观结构
分类描述：Market microstructure, liquidity, exchange and auction design, automated trading, agent-based modeling and market-making
市场微观结构，流动性，交易和拍卖设计，自动化交易，基于代理的建模和做市
--
一级分类：Mathematics        数学
二级分类：Optimization and Control        优化与控制
分类描述：Operations research, linear programming, control theory, systems theory, optimal control, game theory
运筹学，线性规划，控制论，系统论，最优控制，博弈论
--

---
PDF下载：
--> An_Adaptive_Tabu_Search_Algorithm_for_Market_Clearing_Problem_in_Turkish_Day-Ahe.pdf (471.59 KB)

2022-6-10 20:25:29 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：土耳其 Quantitative Mathematical Optimization performance

土耳其日前市场中市场清算问题的自适应禁忌搜索算法。kurt@epias.com.trH.Bahadir SahinOptimization SpecialistEnergy Exchange伊斯坦布尔，土耳其邮箱：Bahadir。sahin@epias.com.trK¨您必须遵守规定。工业工程系TOBB经济技术大学电子邮件：kderinkuyu@etu.edu.trAbstract-在本研究中，我们重点研究土耳其日前电力市场的市场清算问题。我们通过扩展不同价格区域的投标类型，提出了一个数学模型。在给定的时间限制内，商业解决方案可能无法在某些情况下为拟议问题提供充分可行的解决方案。因此，我们设计了一种自适应tabusearch（ATS）算法来解决这个问题。ATS将流量变量产生的连续搜索空间离散化。我们的方法具有自适应半径，并通过商业求解器实现回溯。然后，通过使用合成数据集，我们将ATS的性能与文献中的启发式分解方法进行了比较。我们根据算法的求解时间和剩余差来评估算法的性能。ATS在大多数情况下表现更好。一、 土耳其电力市场的自由化始于2001年颁布的第一部《4628电力市场法》。2013年，该法律被废除，取而代之的是第6446号法律。根据《新法》，土耳其市场运营商伊斯坦布尔能源交易所（EXIST）成立于2015年。现有的主要活动领域包括日前电力、日内电力和天然气批发市场。土耳其day AheadElectric市场（DAM）的参与者可以在实际交付日期前一天通过双边盲拍卖进行投标。

然后，市场运营商根据提交的标书宣布市场结算价格（MCP）和标书匹配。土耳其大坝的投标类型与欧洲电力交易所（PXs）的投标类型相似。土耳其大坝有三个不同的层，即小时标、分段标和浮动标。每小时的出价由每个时段的多个价格和数量级别表示。在一个时期内，这些量价对形成分段线性需求和供给曲线。整体投标包含单个价格、数量、开始期和持续时间（一定数量的连续期）。它将在所有时期匹配或完全拒绝。区块出价之间可能存在链接关系，因此接受一个出价（称为子出价）取决于接受另一个出价（称为母出价）。灵活投标的价格和数量信息仅在一个时期内有效。灵活投标的起始期限由灵活投标的间隔期限内各期限之间的清算机制决定。在不久的将来，EXIST计划扩展模块和灵活投标的功能，以满足参与者的需求。可能的延期是每个时段内针对Block和flexible投标的不同数量，并允许flexible投标的持续时间超过一个时段。[1] 将块投标定义为非凸投标。在这项研究中，我们将非凸投标定义扩展到灵活投标和大宗投标。电力传输受到传输元件容量的限制。当负荷超过一定限制时，就会发生容量拥塞。这种拥塞可以通过各种方式进行管理。大坝市场分割是拥堵管理策略之一。这里，系统运营商将大坝划分为不同的区域，市场清算模型考虑了这些区域之间的传输约束。

该模型假设在实际的电力输送过程中，区域内没有严重的阻塞。由此产生的水流不一定满足Kirchhoff\'slaws。目前的土耳其大坝没有积极利用市场分割；然而，自2009年以来，它已被《电力市场条例》合法化。EXISTis中使用的土耳其电力日AheadMarket优化软件（TE-DAMOS），能够解决多区域市场清算问题。土耳其大坝的市场清算是一个盈余最大化问题。它考虑了投标和流量的投标执行条件、输电限制和定价约束。每天，EXIST都会在10分钟内解决问题，并向市场参与者通告市场结算价格、接受的出价和最佳流量。因此，应该解决这个问题，以便不管问题的计算复杂度如何，至少得到一个好的、可行的解决方案。为市场清算问题提出解决方法是文献中一个突出的研究领域。[2] 在其公式和基于提议分解的精确和启发式解决方案中考虑块和柔性投标。[3] 仅针对大宗投标，引入了比[2]更强的削减。除了分块和灵活投标外，欧洲大坝中还有不同类型的投标，如西班牙葡萄牙语和意大利PXs中分别使用的最低不符合条件（MIC）订单和prezzo unico Nationale（PUN）订单。这些标书包含在【4】–【6】中。https://www.epias.com.tr/en/announcements/market/day-ahead/day-aheadmarket-phase-ii-new-order-typeshttps://www.epias.com.tr/en/day-领先市场/匹配。该文档解释了EXIST如何解决该问题。978-1-5386-1488-4/18/$31.00摄氏度2018年IEEE在本研究中，我们关注的是现有的市场清算问题。

我们将问题陈述扩展为不同价格区域的扩展bidtypes，并提出了一个新的数学模型，即混合整数二次约束二次规划问题（MIQCQP）。我们设计了一种自适应禁忌搜索（ATS）算法来解决所提出的问题。我们使用ATS和文[2]中提出的启发式方法创建合成数据集来解决MIQCQP问题。我们根据求解时间和相对差距来评估这两种启发式方法的性能。我们提出了一种算法，该算法能够在10分钟内找到至少一个解决方案，这是找到土耳其大坝可行解决方案的一个关键时间限制。此外，与文献[2]中的方法相比，我们提出的算法提供了有竞争力的剩余值。本文的组织结构如下。第二节构建了土耳其大坝市场清算问题的数学模型。第三节提出了一种自适应ABU搜索算法（ATS）来解决定义的问题。第四节介绍了数值研究及其结果。我们在第五节第二节总结了我们的论文。市场清算模型非凸电力市场是文献中广泛使用的一个概念，其中二元决策变量创建一个非凸可行区域。[7] –[9]提出了几个明确的规则来处理此类非凸性。由于这些非凸性，接受的投标有负盈余，拒绝的投标有正盈余。这种现象被称为价格匹配不兼容。为了消除这些不兼容性，PXs允许以正余数拒绝投标或以负余数接受投标。土耳其大坝中的价格匹配兼容性约束迫使其接受非凸投标，前提是除子块投标外，非凸投标具有正盈余。

在这种情况下，子块BID的决定必须遵循其母亲的相同决定。土耳其大坝也存在【2】中讨论的价格流动条件。如果一条线上的流量不等于给定时期内的某个极限值，则该时期内该线连接的区域之间没有价格差异。如果流量在一段时间内处于上/下边界，则该行的源节点的价格必须低于/高于该时间段内汇节点的价格。在本研究中，我们在模型中使用分段小时出价曲线和非凸出价。我们假设非凸投标具有相同的属性，例如（1）每个非凸投标可以像在块投标中一样链接到另一个投标，（2）非凸投标的持续时间小于或等于区间限制的长度。我们对输电线路上的可用输电能力（ATC）约束和爬坡限制进行建模，这限制了两个连续周期之间的流量差异。我们还考虑了模型中的价格流动条件。A.

指数、集合、参数和决策变量在本节中，我们提供了指数、集合、参数和决策变量，以构建一个模型，其中逐件逐时出价、非凸出价和传输约束得到处理。索引和集合T，T索引和时间段集合，T={1，2，…，24}。n、 n索引和区域集。l、 l线l、l的传输线SSL、elSource和sink zone的索引和集合∈ 五十、 Lsn，从n区开始和结束的传输线透镜组∈ N，L=长度∪ Lsn。i、 时段t中节点n中的Is、t、Idn、tIndex和供需段集，其中，t=Is，t∪ Idn，t.b，BnIndex和区域n中的非凸标集∧b可以接受的非凸标集如果bλ∈ 接受∧bis。t b可以启动的时段集ParametersPMIN、PmaxMinimum和maximum price limits。第i段的Pi、t、Pi、t起止价格，在第i段的t、Qi、t期间， 我∈ 英寸，t，n∈ N，t∈ T时段t内非凸标书b的Pb、Qb、t、t价格和体积如果标书在时段t内被接受， b∈ B t型∈ Tb，t∈ Tτl、t、τl、tUpper和t期间l线输电量的下限。～τl，t期间l线的践踏限制。每小时投标由一组量价对确定。这些对表示投标人提供的购买/出售数量的最高/最低价格。我们通过分别汇总该时期每小时投标对的购买量和销售额来构建每个时期的供需曲线。虽然供给曲线是数量的非递减函数，但需求曲线具有非递增特性。成对之间的每个区域称为段。如果这些对属于需求（供应）曲线，则该段称为需求段（供应段）。

对于供应段，Pi，t<Pi，t对于所有i∈ IS，t，t∈ 对于需求段，Pi，T<Pi，T对于所有i∈ Idn，t，t∈ T，n∈ N、 段i的体积是创建段的对的体积之差。我们假设Qi，t≤ 0对于供应段i，对于所有i∈ Is，tand Qi，t≥ 0表示阿德曼段i，表示所有i∈ Idn，t，t∈ T，n∈ N分段的指示符号按递增顺序排列。指数最小的供应部门是最低价格水平的部门，指数最小的需求部门是最高价格水平的部门。决策变量xi，段i的t接受分数， 我∈ 管线l处的In、t.fl、t流量， l∈ 五十、 t型∈ Tyb，t1，如果非凸投标b在t期内被接受，否则为0， b∈ Bn，n∈ N，t∈ Tb。pn，t周期t内n区的价格， n∈ N，t∈ Tul，t，ul，t0如果线路l上的流量不等于时段t内输电量的上限或下限，则容量拥挤的影子价格o.w。 l∈ 五十、 t型∈ Tρl，t，ρl，t0，如果周期t内l线上的流量不受爬坡限制或爬坡限制的影子价格的限制。 l∈ 五十、 t型∈ T对于线l，flt>0表示从SLT到ELAN的流量，flt<0表示反向流量。常数fl，0等于前一天最后一段时间的fl。B、 数学模型在本节中，我们对土耳其大坝的市场清算问题建模，我们称之为模型P。

我们使用带互补约束的数学规划问题（MPCC）方法建立了类似于[2]的模型。（P型）最大g=Xn∈NXt公司∈Txi∈In，tQi，tPi，txi，t+Qi，t（Pi，t- Pi，t）xi，t+Xb∈Bn，t∈TbQb、t、tPbyb、t受试者毒性∈In、tQi、txi、t+Xb∈Bn，t∈TbQb、t、tyb、t+Xl∈Lsnfl，t-Xl码∈Lenfl，t=0，t型∈ T、 n个∈ N、 （1）xi，t≤ 1.我∈ In，t，t∈ T、 n个∈ N、 （2）Xt∈Tbyb，t≤ 1.b∈ Bn，n∈ N、 （3）Xt∈Tbyb，t≤Xt公司∈Tλ乘以λb，T，λb∈ ∧b，b∈ Bn，n∈ N、 （4）-τl，t≤ fl，t- fl，t-1.≤ ^1τl，t，l∈ 五十、 t型∈ T、 （5）（1）-Xt公司∈Tbyb，t）Xt∈T（Pb- pn，t）Qb，t，t≤ 0,t型∈ Tb，b∈ B、 ∧B=, （6） （Xt）∈Tλ乘以λb，T-Xt公司∈Tbyb，t）Xt∈T（Pb- pn，t）Qb，t，t≤ 0,t型∈ Tb，λb∈ ∧b，b∈ B、 ∧b6=, (7)(-τl，t+fl，t）ul，t=0，l∈ 五十、 t型∈ T、 （8）（τl，T- fl，t）ul，t=0，l∈ 五十、 t型∈ T、 （9）(-τl，t- fl，t-1+fl，t）ρl，t=0，l∈ 五十、 t型∈ T、 （10）(-τl，t+fl，t-1.- fl，t）ρl，t=0，l∈ 五十、 t型∈ T、 （11）ul，T- ul，t+ρl，t- ρl，t- ρl，t+1+ρl，t+1=pel，t- psl，t，l∈ 五十、 t型∈ 24，（12）ul，T- ul，t+ρl，t- ρl，t=pel，t- psl，t，l∈ 五十、 t=24，xi，t（1- xi-1，t）=0，i、 我- 1.∈ In，t，t∈ T、 n个∈ N、 （13）pt，N=Pmin+Pi∈Is，t（Pi，t- Pi，t）xi，t，t型∈ T、 n个∈ N、 （14）xi，t≥ 0, 我∈ In，t，t∈ T、 n个∈ N、 （15）yb，t∈ {0, 1} b∈ Bn，n∈ N、 t型∈ T、 fl，T∈ [τl，t，τl，t]，ul，t，ul，t，ρl，t≥ 0, l∈ 五十、 t型∈ T、 pn，T∈ [Pmin，Pmax]，n∈ N、 t型∈ T、 约束条件（1）确定了每个区域每个时段的供需平衡。（2） 确保一个分段的可接受分数不超过1，非凸投标在一个周期内可接受（3），（4）满足非凸投标的链接关系。（5） 满足直线上的爬坡限制。（6） （7）是价格匹配兼容性约束条件，（8）（12）显示价格流动条件。（13） -（14）确保所有负/正盈余部分都必须被完全拒绝/接受。变量、非负性和完整性约束的界限在（15）中定义。由此产生的模型是一个MIQCQP问题。

商业解算器无法解决我们提出的模型对实际问题的适应性。在文献中，有像Bender分解这样的精确解技术，但它们可能无法在10分钟内找到可行解。因此，出于实际原因，需要一种神经论方法来找到至少一种解决方案。三、 自适应禁忌搜索算法禁忌搜索（TS）是一种邻域搜索算法，用于找到优化问题的解决方案。TS算法与其他邻域算法的主要区别在于能够摆脱局部最优解的陷阱【11】、【12】。有不同版本的TS专注于智能逃生和探索技术。反应性TS通过自动学习最优tabulist大小来防止循环的发生【13】、【14】。并行TS方法旨在利用计算资源来解决大规模优化问题【15】–【17】。[18] 将路径重链接技术中的大山谷现象添加到TS中【19】将遗传算法的变异操作引入到原始TS中【20】提出了基于TS的参数分枝定界过程，而不是树搜索。虽然先前的研究主要是确定性的，但文献中也有TS的概率扩展【21】–【23】。自适应禁忌搜索（ATS）是一种TS技术，其中多样性和强度是平衡的。TS增加了两个新特性：自适应搜索半径和回溯机制。与常规搜索半径不同，[24]和[25]讨论了自适应半径，以实现更快的强度，并使用反馈跟踪实现其多样化策略。ATS被广泛应用于分配问题[26]、[27]和控制器设计问题[28]、[29]等领域。由于土耳其大坝的时间限制，我们将修改后的ATS应用于我们的问题。