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

为了求解模型P，我们放松了（8）-（12）中定义的约束，以便每个区域仅通过流量变量（f）压缩另一个区域。我们假设这些流量固定为预定值，然后将问题转换为N个子问题。每个子问题代表不同的价格区域。我们使用具有自适应半径的TS来解决这些子问题，并确定每个区域的非凸投标组合。我们使用一个商业解算器，通过将积分变量与TS中的值进行组合，找到最佳流量。由此产生的价格流量问题是一个QP模型，由（1）-（5）中的曲面最大化定义。根据[2]，任何价格流问题的最优解也满足（8）-（12）。然后，我们使用来自解算器的流作为后向跟踪，并重复该过程，直到目标函数不再改善。重复之后，我们修复解决方案以满足（8）-（12）中定义的要求。通过这种设计，我们提出了一种快速、多线程的算法，以保持次优性。我们提出的算法的流程图如图1所示。图1：。算法流程图。每个区域的算法在本节中，我们给出了解决每个区域子问题的TS算法的详细信息。我们从禁忌解决方案、禁忌移动、自适应迁移、禁忌列表（TL）、吸气标准和停止条件的设计决策开始。我们将子问题的禁忌解定义为非凸投标的起始期集，其中0表示投标的拒绝。我们将禁忌移动称为改变禁忌解中非凸出价的起始周期之一。在lustrate中，存在一个具有两个非凸bidsi的禁忌解。e、 ，Sa={b→ 5，b→ 0}.

禁忌解表明，非凸投标在第5阶段开始，而bis拒绝了。然后，通过禁忌移动b→ 0，我们创建一个新的tabu解决方案b={b→ 0，b→ 0}，其中两个非凸投标都被拒绝。通过每个禁忌解和固定的流量值，我们可以找到相应区域的MCP。禁忌解S周围的邻域表示为拒绝接受具有正盈余的非凸投标或接受具有arandom起始期的具有负盈余的非凸投标。我们还通过随机更改已接受的非凸投标的起始期来扩展邻域。当我们都陷入局部最优时，邻域的大小会减小，因为我们预计正盈余的拒绝投标和负盈余的接受投标的数量将很低。如果拒绝/接受移动创建了一个违反约束（4）的禁忌解决方案，我们将更改相应出价子/母的决定，直到结果解决方案不再违反约束（4）。因此，每个邻居都感到满意（4）。邻国可能会有一些投标，因为这些投标被拒绝，因此无法满足价格匹配兼容性约束。在这种情况下，我们接受其中一个违反的非凸出价，并验证兼容性约束是否满足。该过程将继续，直到邻居中没有违反（6）或（7）的出价。我们保留一个本地TL和一个全局TL。本地TL保持禁忌在先进先出队列中移动。全局TL保持每个禁忌解的剩余，直到TS停止。它可以防止在每次迭代中获得相同的盈余。每个分区TS（Cond-1）中的停止条件受迭代次数的限制。我们在约束（1）-（4）定义的区域和（1）-（4）和（6）（7）定义的区域周围执行搜索。我们采用具有最佳目标值的解决方案。

每个搜索都由自己的TL组成。因此，在另一个搜索的TL中具有移动的解决方案可以成为下一次迭代的候选解决方案。它创建了抱负标准。初始解是一个禁忌解，其中所有非凸投标都在一个随机周期内被接受。达到停止条件（Cond-1）后，算法跳转到找到的最佳解。该过程重复进行，直到第四次跳跃，或者最佳解决方案没有得到改进。每个区域使用的整体算法如表I所示，其中g（S）表示从TABU解决方案S表中获得的总盈余。对于具有自适应半径的每个区域，表ITS步骤1：从解决方案S开始。步骤2：如果停止条件（Cond-1）不成立。搜索S：-通过考虑约束（1）-（4）。通过考虑约束条件（1）-（4），（6）-（7），（12）-（13），取最佳解S。采取最佳解决方案步骤3：将Sto Sif g（S）>g（S）指定为Sto，反之亦然。步骤4：更新全局解决方案执行步骤2。四、 数值研究在本节中，我们将解释如何生成我们在实验中使用的数据。然后，我们给出了实验装置和结果。A、 数据我们通过考虑土耳其与其邻国可能的市场耦合情况来创建数据。土耳其电网与8个国家相连。土耳其与其邻国之间的最大输电容量为1000 MW，但系统运营商可能会将其限制在100 MW，以维护电网安全。我们构建了9个数据集，每个数据集有50个案例。每个集合都有不同的分区拓扑和流量场景。我们假设分区拓扑在每个数据集中的情况下都不会改变。每个分区拓扑由2个、4个或8个分区组成。图2显示了用于数据创建的拓扑。（a） （b）（c）图2。

（a）2、（b）4和（c）8区的区域拓扑我们假设每个耦合区的投标人与土耳其投标人具有相似的投标行为。为了创建每个案例，我们在2016年6月1日至2018年3月20日期间随机选择| N |个真实土耳其DAMdata，假设每个日期代表不同区域的投标。忽略线上的倾斜限制。通过使用0和α之间的均匀分布生成每个周期的线路容量和反向容量。在每个数据集中，α值等于0、100或1000 MW。表II给出了α为0、100和1000 MW且分区数为2、4和8时每天的平均投标数量。表中的第一个和第二个数字分别表示每小时平均投标和非凸投标。表II分区2 4 80 31245-311 62373-618 124725-1217100 31286-307 62531-606 124662-12261000 31192-306 62354-623 124431-1216B每个数据集XXXXXXXXα的每小时和非凸投标的日平均数量（#）。实验设置在我们的实验中，我们将我们提出的ATS算法应用于上一节中描述的数据集。我们将我们的算法与文献[2]中提出的精确解和启发式解方法进行了比较。我们在10分钟内执行每种方法，其中EXIST必须宣布市场清算解决方案。我们比较了启发式方法在时间和盈余方面的结果。我们假设每个区域都有与土耳其大坝相同的投标规则。测试在Intel Core i7-4790 CPU上进行，处理器为3.60GHz，内存配置为32 GB。我们使用IBM ILOGCPLEX 12.8来解决优化问题。为了将[2]提出的解决方法应用到我们的问题中，我们将主问题定义为max g s.t.（1）（4），将子问题定义为为为约束（7）-（15）找到可行的解决方案。

然后，如果分枝定界树中的整数可行解不满足（7）-（15），则对问题添加一个割集。[2]提出的精确切割也适用于我们的问题，因为它只切割当前的整数解。然而，[2]提出的启发式切割允许被拒绝的投标具有正盈余，这违反了土耳其大坝规则。因此，我们修改了启发式切割，这样就不应该有正盈余的拒绝投标。在我们的配置中，我们将启发式切割定义为至少改变违反（6）或（7）的投标拒绝决定。在本研究的其余部分，我们将此方法定义为启发式分解。C、 结果当我们用文献[2]中提出的精确解方法求解模型时，我们观察到存在一些在10分钟内没有可行解的情况。因此，我们关注ATS和启发式分解的结果。表III和表IV分别显示了盈余差额和时限。表III由ATS发现的剩余值与分区的启发式分解XXXXXXXXα#的平均差异2 4 80 1911 6763 10482100-3686-1392 405091000-18747-39212-76071表III显示了AT与启发式分解算法之间的剩余差异。正差异反映出ATS的性能优于另一种。当α=100且区域数为4时，存在启发式分解无法在时间限制内找到解决方案的情况。我们仅在至少找到一个解的情况下比较这两种算法。结果表明，ATS在连续系统中提供更好的剩余值，而启发式分解算法在高传输容量下工作得更好。

随着分区数量的增加，ATS的并行设计结构为我们的方法提供了优势。表IV ATS的平均运行时间（秒）和区域2 4 80 8-106 16-513 37-600100 10-107 19-421 54-5921000 19-217 43-426 85-5900的启发式分解XXXXXXXα。表IV显示了ATS的求解时间和启发式分解方法。ATS在所有配置中的解决方案时间方面表现更好。当区域数增加时，两种算法的平均执行时间都会增加。ATS受到α的负面影响，即当α增加时，ATS需要更多的时间来收敛到解决方案。然而，启发式分解对于α变化更为稳健。五、 讨论和结论在本研究中，我们对土耳其大坝清理问题进行了建模，该问题包括每小时、区块和浮动投标以及网络约束。我们提出了一种ATS算法来求解生成的模型。由于不存在真实的分区大坝数据，我们在几个假设下生成随机数据集。我们通过将其结果与文献中使用的启发式分解方法在时间和目标值方面进行比较，来展示算法的性能。自年以来，提出的ATS算法是文献[2]中讨论的启发式分解的一个竞争替代方案；（1） 在某些配置中，启发式分解无法在时间限制内找到任何解决方案，但ATS算法可以在所有数据集中找到至少一个可行的解决方案，（2）ATS更快地解决所有数据集的问题，以及（3）ATS在较低容量下比启发式分解提供更好的附加值。致谢作者感谢土耳其科学技术研究理事会技术和创新资助项目理事会（T¨UB˙ITAK-TEYDEB）对3161185号项目的支持。

我们还要感谢Mustafa Kayirici、Birol Karatay和Ozan G¨urler对这项工作的支持。参考文献[1]R.P.Oneill、P.M.Sotkiewicz和M.H.Rothkopf，“非凸投标电力交易中的均衡价格”，工作文件，2007年7月修订，技术代表。[2] A.Martin、J.C.M¨uller和S.Pokutta，“非凸欧洲日前电力市场中的严格线性价格”，优化方法和软件，第29卷，第1期，第189-2212014页。[3] M.Madani和M.Van Vyve，“欧洲日前电力市场拍卖的计算效率mip公式和算法”，《欧洲运筹学杂志》，第242卷，第2期，第580–5932015页。[4] A.G.Vlachos和P.N.Biskas，“平衡多地区电力市场中的供需混合定价规则”，IEEE Transactions on Power Systems，第26卷，第3期，第1444–1453页，2011年。[5] R.Fern'andez Blanco、J.M.Arroyo和N.Alguacil，“通过双层编程实现收入和网络约束的市场清算”，电力系统计算会议（PSCC），2014年。IEEE，2014，第1-7页。[6] M.Madani和M.Van Vyve，“非对流价格日前电力拍卖的mip框架”，《欧洲计算优化杂志》，第5卷，第1-2期，第263-2842017页。[7] R.P.O\'Neill、P.M.Sotkiewicz、B.F.Hobbs、M.H.Rothkopf和W。R、 Stewart Jr，“非凸市场中的有效市场清算价格”，《欧洲运筹学杂志》，第164卷，第1期，第269-2852005页。[8] C.Ruiz、A.J.Conejo和S.A.Gabriel，“电力池中的非凸性定价”，IEEE电力系统交易，第27卷，第3期，第1334-13422012页。[9] M.Van Vyve等人，《非凸电力市场的线性价格：模型和算法》，核心讨论文件2011/502011。[10] F。

Glover，“整数规划的未来路径和艺术智能的链接”，《计算机与运筹学》，第13卷，第5期，第533-5491986页。[11] -，“禁忌搜索第一部分”，ORSA计算杂志，第1卷，第3期，第190-206页，1989年。[12] -，“禁忌搜索第二部分”，ORSA计算杂志，第2卷，第1期，第4-32页，1990年。[13] R.Battiti和G.Tecchiolli，“反应性禁忌搜索”，《ORSA journalon computing》，第6卷，第2期，第126-140页，1994年。[14] W.-C.Chiang和R.A.Russell，“带时间窗的车辆路径问题的反应式禁忌搜索元启发式”，通知Journalon computing，第9卷，第4期，第417–4301997页。[15] T.G.Crainic、M.Toulouse和M.Gendreau，“走向并行禁忌搜索启发式的分类法”，通知《计算杂志》，第9卷，第1期，第61-72页，1997年。[16] 例如，Talbi、Z.Ha fidi和J.-M.Geib，“并行自适应禁忌搜索方法”，并行计算，第24卷，第14期，第2003-2019页，1998年。[17] A.Attanasio，J.-F.Cordeau，G.Ghiani和G.Laporte，“动态多车辆拨号-乘坐问题的并行tabusearch启发式”，并行计算，第30卷，第3期，第377-387页，2004年。[18] E.Nowicki和C.Smutnicki，“作业车间问题的高级禁忌搜索算法”，《调度杂志》，第8卷，第2期，第145-1592005页。[19] D.Zhang、Z.Fu和L.Zhang，“大型配电系统中最小损耗重构的改进ts算法”，《电力系统研究》，第77卷，第5-6期，第685-6942007页。[20] F.Glover，“混合整数程序的参数禁忌搜索”，计算机与运筹学，第33卷，第9期，第2449-24942006页。[21]J.Xu、S.Y.Chiu和F.Glover，“电信网络设计的概率禁忌搜索”，组合优化：理论与实践，第1卷，第1期，第69-941996页。[22]Y.A.Kochetov和E.N。

Goncharov，“多阶段无容量限制设施选址问题的概率禁忌搜索算法”，运营研究论文集。斯普林格出版社，2001年，第65-70页。【23】D.Ghosh等人，《广义最小生成树问题的概率禁忌搜索算法》。印度管理学院，2003年。【24】T.K.Sarawut SUJITJORN、D.Puangdownleong和K。AREERAK，“工程设计中的自适应禁忌搜索和应用”，工程设计集成智能系统，第149卷，第233页，2006年。[25]D.Puangdownreong，K.-N.Areerak，A.Srikaw，S.Sujitjorn和P.Totarong，“通过自适应禁忌搜索进行系统识别”，工业技术，2002年。IEEE ICIT\'02。2002年IEEE国际会议，第2卷。IEEE，2002，第915–920页。【26】Z.Miao、S.Cai和D.Xu，“应用自适应禁忌搜索算法优化crossdock管理系统中的卡车停靠点分配”，专家系统与应用，第41卷，第1期，第16-222014页。[27]J.Xie，Y.Mei和A.Song，“存储位置分配问题的进化自适应禁忌搜索算法”，发表于2015年遗传与进化计算年会的配套出版物。ACM，2015年，第779-780页。【28】A.Suyapan、K.Areerak和K.Areerak，“采用自适应禁忌搜索算法的Morelectric飞机电力系统控制器设计”，电气工程大会（iEECON），2017年国际。IEEE，2017，第1-4页。【29】T.Ketthong、S.Tunyasirut和D.Puangdownreong，“通过自适应禁忌搜索设计和实现直流电机速度控制系统的i-pd控制器”，《国际智能系统与应用杂志》，第9卷，第9期，第69页，2017年。