递归法在变电站选址定容运输模型中的应用

金义雄，崔德义

（上海电力学院电力与自动化工程学院，上海 200090）

随着城市的不断建设和改造，对其进行良好的电网规划越来越重要.这主要是因为城市的电网规划能够直接影响低压配电网结构和未来系统线路走向，从而影响供电的可靠性和运行的经济性［1-5］.

电网规划中，变电站地址的选择是影响城市配电网运行结构的主要因素之一，其建设和改造对整个电力部门的经济效益有重要影响.本文着重描述了在变电站选址定容中，将递归方法和重心算法相结合并进行应用的过程，提出了将遗传算法与这两种方法相结合的新设想.

1 变电站数学模型和组合过程

1.1 数学模型

变电站选址定容的目的是在确定负荷分布的情况下，确定各个变电站的容量、位置，以及供电范围，以达到投资最小和年运行费用最低.

决定变电站选址定容投资的适应度函数为：

1.2 组合过程

表1 变电所主变压器单组容量

2 运输模型及其递归过程

变电站选址定容过程中，如何在确定了变电站的个数后，根据变电站的供电能力大小、负荷大小，以及供电距离之间的关系，合理地进行电能分配和供电是一个值得探讨的问题.我们可以首先利用运输模型的线性规划法对现有的已知条件通过编程进行安排，然后结合重心法对结果进行不断的调整和校正.与人工算法相比，编程的优点是速度快、精度高、效率好，但由于计算机对图形不敏感，难以实施路径搜索，笔者利用计算机对数字较敏感的特点，运用递归算法很好地解决了这一难题［5-8］.

2.1 运输模型

运输模型的工作过程如下：首先根据随机分配的n个变电站和已知条件列出一个矩阵，矩阵的内容包括变电站的个数、供电能力、负荷大小，以及各变电站与各负荷之间的距离，利用运输模型算法得到初始矩阵，并利用位势法产生检验表，通过检验表负数值的位置确定初始方案表的起始搜索位置;然后进行闭合路径搜索，找出路径中最小的非负值a，对每一个路径上的点进行交叉加a或减a的操作，再利用位势法产生检验表，看表中是否有负值;最后以此类推，直到检验表中没有负值为止.此时，整个运输模型过程结束［6］.运输模型流程见图1.

图1 运输模型流程

2.2 递归过程

我们发现，在搜索闭合路径的过程中，用计算机实现很困难，这会对程序的衔接和进一步计算带来很大的阻碍.这是由于计算机对图形不敏感所造成的，而笔者运用递归算法很好地解决了路径搜索问题.递归算法分为递推和回归两个步骤.递推表示搜索到下一节点时该节点可再次调用此函数进行类似的函数操作.回归表示当一次递归不满足要求时，返回上一层调用，并重新进行搜索.另外，在搜索过程中，不能终止程序，需要一直返回，直到跳出函数为止.

具体的递归过程如下：首先对于每一个矩阵的元素都设定一个结构体，结构体包含了每一个矩阵元素值所需要的信息，包括一个能代表矩阵元素的上、下、左、右4个方向信息的数组值，用1表示此方向已搜索过，0表示未搜索过.对于第一个元素设置一个node元素，然后对于每一个下次搜索得到元素的node值递加1.这样在最后显示结果时可以清楚地显示路径的搜索顺序［7-9］.整个递归模型的流程如图2所示.

图2 递归模型流程

图2中，“确定搜索方向”这一步是指搜索方向分为横向搜索和纵向搜索交叉进行，进行到下一次递归时搜索方向需要变向.另外，初始方向可自定义，例如当此次搜索是横向搜索时，可以设定初始方向搜索为左边搜索，则第2种方向即为右边搜索.纵向搜索采用类似方法.

3 算例分析

为了验证运输模型及递归算法应用的正确性，笔者进行了算例分析.在此算例中，假设由3个变电站A1，A2，A3及4个负荷区块B1，B2，B3，B4组成的产销平衡运输模型，其供电距离见表2.

表2 变电站负荷产销平衡供电距离km

利用运输模型和位势法，得出初始方案和检验表，如表3和表4所示.

表3 初始方案MW

表4 检验方案MW

从表4的负值所在位置确定表3的递归开始位置，将表3的矩阵输入计算机，形成矩阵，并设置起始搜索点为（1，3）（注意，计算机中数组的起始位是从零开始的）.开始搜索后，第一个值只能横向搜素（初始搜索方向），先搜索左边，遇到1值，然后判断此值是不是起点.当判断为否时，则转换搜索方向，向上方搜索，发现4值，继续判断此值是否为起点.不是，则继续搜索，这个不断进行搜索的过程就是递归过程.通过不断递归，最后可以找到（0，3）位置的3值，往下搜索，即可搜索到起始点0值，递归过程开始返回.搜索顺序依次为0－1－4－3.每搜索一次，其节点数增加1.在返回过程中，需要不断地使用return语句，逐层返回，直到返回至第一层，整个递归算法结束.程序的运行结果为：

闭合路径矩阵的数字1到4表示的是搜索路径的顺序，当搜索到第4个节点时，向下搜索会又碰到第1个节点.此时并没有把第1个节点标记为7，仍然保持为1.然后在闭合回路中找到最小值，按闭合回路的路径依次加上和减去这个最小值，以形成新的方案表.最后再利用位势法形成检验表，发现表中所有值为正，则表明该初始方案为最优方案.确定变电站的分配方案以后，再根据式（1）和式（2）计算出C1和C2，从而可以最终确定变电站的容量和位置.

4 结语

递归算法很好地解决了计算机对图形不敏感的问题，并且可以一次搜索出所有的闭合路径.

遗传算法是目前广为使用的一种现代启发式寻优方法.考虑到使用遗传算法能解决计算问题，递归算法能解决路径搜索问题，可以将两者有效地结合起来，这为解决变电站选址定容问题提供了一条新思路.

［1］段刚，余贻鑫.电力系统NP难问题全局优化算法的研究［J］.电力系统自动化，2001，25（5）：14-18.

［2］胡纯德，祝延军，高随祥.一种求解旅行商问题的新型单亲遗传算法［J］.计算机工程与应用，2004，35（1）：37-40.

［3］陈慧琴，刘刚.用整数编码的单亲遗传求解组合优化问题［J］.武汉理工大学学报，2004，27（2）：241-243.

［4］张崇见，余贻鑫，严雪飞.中压配电变压器优化规划［J］.电力系统自动化，1999，23（1）：27-30.

［5］李茂军，朱陶业，童调生.单亲遗传算法和传统遗传算法的比较研究［J］.系统工程，2001，19（1）：61-65.

［6］《运筹学》教材编写组.运筹学［M］.北京：清华大学出版社，2005：78-91.

［7］王成山，魏海洋，肖峻.变电站选址定容两阶段优化规划方法［J］.电力系统自动化，2005，29（4）：62-66.

［8］王成山，刘涛，谢莹华.基于混合遗传算法的变电站选址定容［J］.电力系统自动化，2006，30（6）：30-34.

［9］闫丽梅，许爱华，任爽，等.一种变电站选址的新方法［J］.高电压技术，2007，33（9）：75-79.

（编辑苏娟）