启发式路径规划算法（共5篇）
启发式路径规划算法 篇1
0引言
集成化物流管理ILM(integrated logistics management)是一种近年来才发展起来的新的物流战略管理模式,其主张将所有的物流活动整合在一起视为一个完整的系统,并在理想的客户服务水平下追求总成本最低[1]。
库存-路径问题IRP(inventory routing problem)是在如何联合优化配送和库存这两个往往被独立考虑的物流环节的现实需求推动下成为崭新的研究领域,是企业节能增效的重要途径。库存路径问题是对一系列已知需求量的客户,组织适当的行车线路进行服务,在不违反任何约束条件下,优化路线使得总成本达到最小。有效地解决该问题可以提高车辆的利用率,降低配送成本,提高配送时间的准确率,从而提高物流服务水平。由于库存路径问题是典型的NP难题,使用传统的优化方法很难得到问题的最优解或满意解,因此构造高质量的启发式算法成为研究该问题的主要发展方向[2]。
国外IRP研究最早出现在20世纪70年代。2000年以前的IRP文献主要研究单周期、一对多、单品种、确定需求情况,通常给定车辆数或不限,决策方式则集中在确定固定的配送频率,目标只考虑客户库存成本(一般不考虑中心库存成本)。求解时,采用“分区—路径” 分解问题或者沿用EOQ(Economic Order Quantity)思路占绝大多数,寻找合适的求解方法一直是研究热点、重点和难点。2000年以来,在继续构建高效率求解方法的同时,IRP本身的研究得到了深入,随机需求IRP、三层级IRP、取送结合IRP受到更多研究的重视[3]。
SPERANZA等运用实例证明了建立混合整数规划模型较建立纯整数规划模型的优越性[4]。
CHIEN等也讨论了单周期的IRP,他们所研究的配送系统包括一个有固定供应能力的中心仓库和多个有确定需求的客户,供方可以不满足部分客户的需求,但必须对未被满足的需求支付惩罚费用,建立了一个混合整数规划模型,采用基于拉格朗日松弛的求解过程来获得理想的上界[5]。
DROR等则研究了多周期IRP,侧重于如何将长时段(如每年)的多周期问题简化为短时段(如每天)的单周期问题。通过引入惩罚因子和激励因子来反映相邻周期决策的相互影响,并且建立了相应的混合整数规划模型[6]。
BLANCHINI等在建立随机动态规划模型时将单品种、多对多的物流系统看成是一个网络[7]。
国内IRP研究文献出现在2001年以后,但论文数不多,研究工作尚处于起步阶段。
奚飞等人通过综合考虑零售商订货周期与供应商订货周期之间的大小关系,最终寻求一种最优的IR策略,从而使整个供应链的成本最小[8]。
武秀焕等人将随机IRP描述为一个马尔可夫过程MDP(Markovian decision process),根据客户数量将问题分解成N个子问题进行MDP描述,接着对状态转移矩阵进行模拟,并对每一个MDP子问题进行求解,然后运用非线性背包问题的求解方法得到IRP的初始策略来构成直接配送路线,并在此基础上构造了一种基于搜索算法的启发式算法对初始策略进行优化,得到最终的优化解[9]。
沈飞等人将IRP问题分成两个子问题:一个能够使库存储存费用最小的线性规划和在基于模拟退火理论下生成并评估可选择性组合路线的分路线排除约束函数(the route perturbation routine)。一旦确定运货车的路线,混合整数规划(MIP)就转化为相对容易解决的线性规划,这样便能在给定的路线组合中寻找到解决库存问题的最优方案[10]。
目前国内对IRP的研究都是假设产品为单一品种。本文考虑多品种、多供应商对多客户的IRP问题,使用启发式算法选择最优的可选择的组合线路,逐步生成满意解。
1模型的建立
1.1模型假设
(1) 所有产品都能在1天内送到,即不考虑配送时间。
(2) 运输成本以整车为单位计算。通常运输成本包括:过路费、油费、人工工资、各种损耗。对于确定的运输线路和运输工具,则过路费、人工工资、其他损耗可以估算出来,油费与运输距离、货车自重、载货量成正比。
(3) 只考虑产品重量,忽略产品体积,是否易燃易爆等因素对运输费用的影响。
(4) 不考虑产品装卸费用和库存成本。
(5) 货车可以有多种类型,每种货车的自重、最大载货量、固定费用不同。
(6) 只考虑点对点运输,即货车到达目的地之后,必须将所有产品全部卸下。货车数量不受限制。
(7) 任意2节点之间存在直达线路。节点之间直达线路长度为最短,比经过任何节点中转都要短。
(8) 货车必须在当天返回出发点。即货车运输路线形成汉密尔顿圈。
1.2模型的建立
设有n个节点ai,m种产品Bj,节点之间直达距离为Dij,节点产品库存为Sij,节点产品需求为Eij。
设运输费用为:
其中,F为固定费用(与货车类型有关),d为运输距离,Z为货车自重,w为载货量,u为费用系数(需事先估计)。
每辆货车的运输路线形成汉密尔顿圈,设运输路线经过k个节点,则该运输线路可表示为:L(a1,a2,…,ak,a1)。
1.3目标函数
令恰好满足所有节点产品需求的货车运输路线集合为Q={L},相应的总运输费用为:
P=∑c(Li) Li∈Q (2)
则系统目标函数为求总运输费用最低的集合Q′,即:
P(Q′)=min{P(Q)} (3)
约定:
di,t=时间段t内配件i的需求量,i=1,2,…,m;
t=1,2,…,T;
K0=仓库和装配车间的距离;
K1=仓库和最近供应商间的距离;
K2=装配车间和供应商间的距离;
K=K0+1/2K1+1/2K2;
Ci,j=供应商i与j之间的行车距离,i和j=0,1,…,m+1;
hi=配件i的库存存储成本i=1,2,…,m;
Ii=配件i的初始库存量i=1,2,…,m;
C=货车的装运量;
L=线路的最大长度。
设:
qi,t=时间段t内在供应商i处的装运量;
si,t=时间段t内在配件i的库存水平。
于是有:
s.t
qi,t≥yi,t ∀i,∀t (5)
pi,t≤qi,t ∀i,∀t (6)
si,t+1=si,t+pi,t-di,t ∀i,∀t (10)
si,0=Ii ∀i∈{1,2,…,m} (11)
si,t≥0 ∀i,∀t (12)
yi,k,t,pi,k,t∈{0,1} ∀i,j∈{0,1,…,m+1},∀k,∀t (13)
因此,目标函数(4)包括的成本项目有访问供应商的成本之和,库存存储成本,出行设置成本。而约束条件式(5)至式(7)将变量yi,t与装运数量联系起来,约束函数(9)限定了每条线路都小于或等于最长线路L,约束条件式(10)为库存平衡等式,约束函数式(14)对一辆货车能够装运的载运量进行了限定。
2启发式求解算法
Q′为汉密尔顿运输路线集合,根据贪婪法则,总能找到当前单位运输成本最低的汉密尔顿运输路线,则有算法如下:
(1) 系统初始化。
(2) 根据需求计划及库存,找出所有可能的点对点运输线段。
(3) 找出使运输线段连接成汉密尔顿圈的所有组合。
(4) 对于p种货车,分别计算汉密尔顿运输线路及其成本。
(5) 找出运输成本最低的汉密尔顿运输线路,记录该线路。
(6) 根据该线路选择具体的运输方案,并在运输源节点的库存中减去已计划运输的产品,及在目标节点的需求中减去已计划运输的产品。
重复(2)—(6),直到没有任何可能的点对点运输线段。得到的配送方案集合即为最优运输方案。
3算例分析
为验证算法的可行性与有效性,编制程序验证本文所提出的模型与算法。
算例来源于模拟现实生活。基本数据为9个节点,9种货物,货车自重1500千克,最大载货量4000千克,固定费用200元,费用系数为4500,节点之间平均间距为153.3千米,每个节点存有多种产品,平均每个节点存有4.89种产品,节点平均库存量为4137.4千克。节点的产品需求数随机产生,多次运行算例结果如表1所示。
由表1可以看出:单位产品运输成本平均为0.06883元/千克,货车平均载货量为2416.99千克,平均货车运输效率为60.425%,空驶率平均为14.785%。而我国物流运输车辆的空驶率达37%[11]。
为验证算法的可行性与有效性,本文将应用所提出的模型与算法所得出的计算结果与其他启发式算法进行比较。
若利用集合覆盖型等式,由于该等式限制了路线的长度,能够最优解决的IRP 的最大容量是6 个供应商和7 个时间段。最优总成本是1354.70 元(存货成本=97.80 元,运输成本=1256.90 元)。
若利用本文所提出的启发式算法程序解决相同的问题,总的成本是1370.43元(存货成本=118.2 元,运输成本=1252.23元)。最优解和利用启发式解法得到的解的直接数值间隙是1.15%。同时即使供应商的数量大于100 和多个时间段的问题时也是有效的。因此本文提出的模型与算法不仅具有可行性而且在所求解问题的规模上具有先进性。
通过对比可知,本文提出的启发式多产品库存路径算法大大降低了货车的空驶率,有效地提高了货车运输效率,从而降低了运输成本。
4结语
(1) 本文重点介绍了库存路径问题的启发式算法研究,分析了关于库存路径问题的模型建立和解决过程。
(2) 探讨了以贪婪法为基础的启发式算法,采用的策略是每次选取平均运输成本最低的汉密尔顿运输路线。
(3) 模型仿真结果表明,本文提出的启发式多产品库存路径求解算法生成的物流运输方案高效,成本低廉,有广泛的应用前景。
参考文献
[1]Kenderdine D J,Larson P D.Quality and Lo-gistics:A Framework forStrategic Integration[J].International Journal of Physical DistributionandMaterials Management,1988,18(7):5-10.
[2]陈雪瑛.基于启发式算法的库存路径优化问题研究[D],北京交通大学,2008.
[3]傅成红,符卓.库存路径问题及其最新进展[J].计算机应用,2010(2):453-457.
[4]Speranza M G,Ukovich W.MinimizingTransportation and InventoryCosts for Several Products on A Single Link[J].Operations Re-search,1994,42(5):879-894.
[5]Chien W,Balakrishnan A,Wong R.An Integrated Inventory Alloca-tion and Vehicle Routing Problem[J].Transportation Science,1989,23(2):67-76.
[6]Dror M,Ball M.Inventory Routing:Reduction From an Annual to AShort-period Problem[J].Naval Research Logistics,1987,34(6):891-905.
[7]Blanchini F,Queyranne M,Rinaldi F,et al.A Feedback Strategy forPeriodic Network Flows[J].Networks,1996,27(1):25-34.
[8]奚飞,周永务.基于固定分割的库存路径问题最优策略[J].系统工程与电子技术,2009(10):2389-2993.
[9]武秀焕,李延晖.马氏过程的随机库存路径问题模型与算法[J].工业工程与管理,2009(1):66-70.
[10]沈飞,管小俊,于雅岑,等.基于模拟退火理论求解库存路径问题的模型与算法研究[J].物流技术,2009,(2):74-76.
[11]曲衍国.公路物流运输中的汽车利用效率问题[J].综合运输,2004(6):52-55.
启发式路径规划算法 篇2
基于Bellman-Ford算法的无人机路径规划研究
通过预先侦察和经验评估,给出了一种敌情信息未知环境中的.无人机路径规划方法.采用Bayes方法求取了给定规划区域内威胁存在的概率,构建了威胁概率分布图,并将其转化成权重为威胁概率的带权图,利用Bellman-Ford算法搜索该带权图,求取了一条从出发点到目标点的无人机最小威胁路径,根据无人机气动性能约束,对最小威胁路径进行了修正和优化,得到一条可飞的最优路径,最后给出了仿真结果,验证了方法的有效性.
作 者：张冲 朱凡 ZHANG Chong ZHU Fan 作者单位：空军工程大学工程学院,西安,710038刊 名：弹箭与制导学报 PKU英文刊名：JOURNAL OF PROJECTILES,ROCKETS,MISSILES AND GUIDANCE年，卷(期)：27(5)分类号：V279关键词：无人机 路径规划 威胁概率分布图 Bellman-Ford算法 最小威胁路径
启发式路径规划算法 篇3
关键词：多层多域光网络,组播,点到多点
0引言
分组业务需求的逐步提高促进了光网络技术的发展。随着网络用户数目的不断增长,人们对大容量P2MP(点对多点)业务的需求正在不断增加,如IPTV(网络电视)、视频点播以及虚拟专用网等。智能光网络与P2MP技术相互融合将极大地促进光组播业务的发展[1]。
P2MP中路径选择算法是光组播中的关键技术之一。组播算法要达到的目标是减少所占用的带宽和所使用的波长,尽量减少建立连接的时间和信号传输时延[2]。其业务路由建立的方式则是找到一棵路径树,这棵路径树的源节点是其根节点,而目的节点即为其叶子节点。目前有不少研究成果是关于最小代价树的P2MP算法[3,4,5],但是由于在多域光网络中不同域之间信息是相互隔离的,而且随着网络规模的不断扩大以及多域网络复杂的分布式计算,现有算法都很难有效地计算出最小代价组播树。
为了解决以上 问题,本文提出 一种MDMPH(基于分层PCE(路径计算元素)的多域最小代价路径启发式)算法,并在实验平台上对该算法进行了仿真,仿真结果表明,此算法能够计算出代价更小的P2MP路径树。
1多域网络基于 PCE的P2MP路径计算
PCE技术被认为是最适合计算多域网络最短代价树的方法。IETF(因特网工程任务组)提出了基于PCE的P2MP路径计算方案,而RSVP-TE(基于流量工程扩张的资源预留协议)也为P2MP在信令方面做出了相应的扩展。目前已有多个研究团队提出了一些多域P2MP算法,下面将对 三种基于PCE的多约束跨域的P2MP算法进行介绍和分析。这里我们假设源到宿节点的多域序列为已知。
1.1PDB(基于逐域路径)算法
在各个域序列都已知的情况下,PDB算法逐步在各个域中计算本域内的详细地址,而各个域间相邻的网关节点默认是已知的。
在PDB的P2MP算法中,以逐域的方式计算源节点到每一个宿节点的P2P(点到点)路径,并将这些路径整合成P2MP树,这是一种简单的P2MP算路方法。在具体实现过程中,域序列计算与P2P计算方法一致,而最短域序列的计算由GE(群引擎)完成。这些方式只是现有的比较可行的解决方法,但是对计算最小代价树并没有什么帮助。此外,该方法对域序列与跨域连接计算方法没有给出具体的定位,所以无法使计算出的路径最短,同样也无法使整棵路径树为最小代价。
1.2E-BRPC(基于扩展的反向回溯)算法
反向回溯路径作为一种可以有效计算最小代价树的算法,在已经知道域序列的情况下,可以计算一条跨域的最短 的P2MP路径。E-BRPC对BRPC(反向回溯)算法做了一些扩展。在P2MP链路计算过程中,首先利用基本算法计算源到宿节点的最短路径,并将数据库中其链路代价数值设置为0,然后计算下一宿节点。在计算完所有的宿节点之后,与PDB算法相似,将它们合并成一棵完整的最小代价树。
该算法计算花费时间短,可以灵活应对宿节点的变化,并将数据库进行更新以使不同宿节点路径相互聚合在一起,可以很大程度地减小P2MP路径树的代价。但在宿节点计算次序不同的时候,得到的P2MP路径树会有很大的不同,因此计算结果不稳定。
1.3CTB(基于核心树)算法
CTB算法可以计算出最短的P2P路径,但无法使所有最短路径聚合在一起也成为一棵最小代价树,因为不同路径之间缺少相关性。CTB算法通过链路数据库的更新使不同路径之间的相关性有一定增强,但仍然不能使结果最优。
核心树是满足下列条件的路径树:(1)其根节点为P2MP业务源节点;(2)其叶子节点为P2MP业务中各宿节点所在域中的边界节点;(3)各个分支节点与其中间节点是经过各个域的边界节点。
CTB算法分为两个阶段:(1)建立P2MPLSP(标记交换路径)的核心树;(2)完成对整个P2MP树的计算。
理论上可以利用CTB算法完成最小代价树的计算,因其对所有情况都比较了解,而当P2MP业务在宿节点所在域或者其所经过的域中有新的节点加入时,仅仅需要计算这个节点到核心树的路径,所花费的计算代价很小。但是,CTB算法消耗了很多计算资源,而且无法使域序列始终为最优,而在后续计算过程中域序列是无法被改变的。
通过对以上算法综合分析,我们提出一种新型的多域P2MP算法,即MDMPH算法。
2MDMPH算法
MPH(最小代价路径启发式)算法的思路如下:每计算一次源节点到宿节点的路径时,都把能够保证使组播树代价最小的路径添加进树里,这样在完成计算后,就能使P2MP树获得尽可能小的代价。在多域网络中,相互独立的域之间难以应用MPH算法,必须将关键节点之间的链路关系抽象出来,寻求分布式和集中式相结合的方式来解决。基于以上分析,我们提出了MDMPH算法。仿真中采用的网络拓扑如图1所示,采用46个有组播能力的节点,并将这些节点均匀分布在6个域里。
初始条件:
E = {待计算的宿节点};
SP = Φ:包含到达各个宿节点的稀疏路径;
V = {根节点}:P2MP业务的源节点;
T = Φ:包含每次计算出的从源节点到宿节点的路径。
算法流程如下:
步骤1:父PCE根据各个GE节点收集的各域边界节点间的TE信息,抽象出扩展的高层路由拓扑。其中,相邻域间的权重为域间链路的TE权重,域内各个边界节点为全互联拓扑,之间的连接权重根据域内的路径计算抽象而成 (如图1 (b)中黑色节点所示);
步骤2:在扩展的链路状态数据库中添加进源节点和宿节点 (如图1 (b)中浅灰色节点所示);
步骤3:计算V中节点到E中每个节点的最短路径,选择其中最短的一条,并将该路径作为新路径添加至SP中;
步骤4:将新路径经过的节点添加至V,其宿节点从E中删除;
步骤5:判断E = Φ?,若E不为空,则继续执行步骤3;
步骤6:从SP (图1 (b)中加粗链路所示)中选出一条路径,请求各个GE节点的PCE,完成各个域内的详细路径计算;
步骤7:将计算出的完整路径添加至T,并将之前的稀疏路径从SP中删除;
步骤8:判断SP = Φ?,若SP不为空,则继续执行步骤6。
由于MDMPH算法消除了域序列问题,使得结果不受其是否最优的影响,因此可以计算出代价更小的P2MP树。
3仿真及结果分析
本文基于实验室的DREAM平台,利用软件编码的形式实现了文中提到的四种多域P2MP算法,并对其性能进行了测试。在实现PDB、E-BRPC和CTB三种算法时没有将域序列计算问题考虑在内,而且在仿真中三种算法采取了利用GE计算P2P路径的策略,其中PDB算法在选取域间节点时采取了随机方式。
实验对最大时延(diameter)、总时延(delay)和总代价(cost)三种特性进行了测试。先求得10000次仿真业务的最大时延、总时延和总代价,再取平均,得到每次业务的最大时延、总时延和总代价。这三个参数的计算公式如下:
式中,ti为仿真第i个业务的时延;di、s分别为第i个业务的源节点、宿节点编号;n为总仿真次数。
我们将其分为两组,一组对比四种方案中将宿节点进行随机分布时的总性能;另一组为确定宿节点的数目时,这四种方案的性能变化趋势。
第一组:在测试过程中,分别对每种方 案进行10000次P2MP仿真,并将每次仿真业务的宿节点数目设置在2~10范围内,其平均结果如图2所示。
从图2可以看出,在总代价方面,相比于其他算法,MDMPH算法能够 得到明显 低的组播 树总代价,其次则为E-BRPC与CTB算法,代价最大的是PDB算法。而在总 时延方面,最差的是MDMPH算法 ,PDB算法其次 ,E-BRPC与CTB算法性能 最好。所以最短路径与最小代价这两者很难同时达到最优,当一项性能高时,另一项性能将偏低。
第二组:在测试过程中,我们将宿节点的个数设置在2~10范围内,并对其个数固定情况的性能进行比较。同样进行了10000次P2MP仿真,仿真结果如图3所示。
图3当宿节点数目递增时,各算法的不同性能比较
从图3中可以看出,随着宿节点数目的不断增多,四种算法的总代价也在不断增高,但MDMPH算法仍然保持在最低。MDMPH算法的时延性能比其他三种方案都差,所以在保证较低代价的同时时延不要过大,因此MDMPH方案适合应用在节点数目较小的P2MP业务中。
通过以上分析可以发现,PDB算法性能最差的原因是其有效策略的缺失。在理论上CTB算法得到的最小代价树应该最优,因为其对各种情况都有所了解,而这些“各种情况”是在完成域序列计算的情况下,域序列将对组播树的总代价有比较大的影响。E-BRPC算法优于CTB算法也是 由于此,EBRPC算法中并非一次性对域的序列进行计算,而有非常大的变化性。数据库更新策略一方面提高了不同路径的相关性,同时对其相关性也进行了优化。MDMPH算法则因其不必计算域序列,所以性能比较好。为了全方位考虑,本文提出的MDMPH算法因弱化了时延性而使得源到宿节点之间的平均距离有所增加。
4结束语
启发式路径规划算法 篇4
配电网络规划问题具有非线性、离散性、运行方式多样性、多阶段性的特点,其求解是相当复杂的[1]。
国内外学者研究和发展了各种配电网络规划的模型和算法,如支路交换法[2]是对辐射结构配电网络的支路在其邻域内重复进行交换,直到目标函数值最优,但这种方法只能实现局部最优,不能较好地解决实际问题。遗传算法[3]是求解全局优化问题的随机搜索算法,通过选择、杂交、变异等一系列算子的操作产生优良的迭代结果,其效果在配电网络规划中得到一定的认同,但是,遗传算法在计算过程中会产生大量的无用解[4]。进化策略[5]与遗传算法一样属于模拟进化算法,但更重视变异的作用。禁忌搜索算法[6]是一种单线随机搜索算法,同其他算法结合,具有强大的全局搜索性能,但局部搜索性能易受分散性的影响。模拟退火算法[7]利用概率突跳性在解空间中随机寻找目标函数的全局最优解,也与其他方法相结合应用到了配网规划中。但上述算法没有充分利用配电网络规划领域的相关知识,弱化了其在具体问题中的全局搜索能力,使搜索效率较低。
本文在给定变电站选址规划的基础上,根据规划区域的地理信息,对启发式蚁群算法[8]进行了改进,实现了以城区街道为配电网络基础结构的“辐射状”配电网络规划。这种算法是针对于全新的供电区域或开发区寻找辐射状网架规划方案,与以往的网络铺设方法[1,4,7,8,9,10,11,12]相比较,本文研究的基于启发式蚁群算法的中压配电网络规划方法对实际工作更具有指导意义。
1 中压配电网络规划的数学模型及约束条件
1.1 数学模型
中压配电网络规划的数学模型是以线路的规划年综合费用最小为目标函数,包括线路投资费用、网损费用。
其中:N为变电站的个数;Ji为构成第i个变电站辐射型线路的总数;lik为第i个变电站的第k条线路的长度;lm为变电站低压侧线路折旧年限;r0为贴现率;α为单位长度线路投资费用;Pik为第i个变电站第k条线路上的有功负荷;β为线路网损折算系数。
1.2 约束条件
(1)电压降必须在允许范围内
本文的电压降约束通过线路长度体现。根据负荷分布密度及大小,在电压降允许范围内,线路长度的取值范围可为2~10 km。
(2)每条线路容量不能超载
为了保证中压配电网的可扩展性,每条辐射出线均保留了50%的裕量,主干线路的导线均采用240电缆。
(3)配电网结构呈辐射状网络结构。
(4)网络规划线路必须沿城市街道铺设。
在进行线路铺设过程中,如果有违反上述约束条件的方案,则视为失败方案。
2 地理信息知识库的构建
2.1 知识库结构
本文以框架形式表示配网规划区域的地理信息,进而构建出适用于配网规划的地理信息知识库。街区及负荷分布如图1所示。
地理信息知识库的结构如下:(变电站供电范围
2.2 知识库实现
本文利用C语言对带有地理信息的负荷分布图(如图1)进行识别,提取所有街道段及其节点坐标、负荷坐标及负荷量等特征值,然后对这些特征进行分类编号,最后利用SQLServer数据库技术建立地理信息知识库,所建数据库的部分信息如表1~表4所示。
利用地理信息知识库框架建立GIS知识库,该库既能准确描述规划区域的街道信息、变电站供电范围及二者的相互关系,又便于程序调用、查询与更新。
3 基于蚁群算法的配电网络规划
3.1 蚁群算法的基本思想及特征
蚁群算法是受真实蚁群集体觅食行为的启发而提出的一种模拟仿生算法[6]。
蚁群算法具有正反馈、分布式计算以及运用贪婪启发式搜索等特征。其中,正反馈有助于快速发现问题的较好解;分布式计算可避免在迭代过程中出现早熟现象;而运用贪婪启发式搜索则可使搜索过程中较早地发现可接受解[13]。尽管蚁群算法具有上述特点,但基本蚁群算法依然存在收敛速度慢,易陷入局部最优解的缺点。
基于蚁群算法的配电网络规划方法,将负荷看作是蚂蚁所要寻找的“食物源”,蚂蚁在铺线时,根据具有启发信息的状态转移准则来决定其选择街道段。可有效地求得配电网络规划问题的优化解。
本文对启发信息的状态转移准则,即转移概率模型和信息素更新规则进行了改进设计,以适用于配电网络的优化规划问题。
3.2 变换状态转移准则
每只人工蚂蚁在第i个节点的运动方向,即从待选路径中选择哪条街道段是由状态转移准则决定,因此,合理的状态转移准则既要以一定的概率服从现有最优解,又要以一定的概率搜索新的可行解[14]。
3.2.1 启发信息状态转移准则
在蚂蚁j选择前进路经kselected时,由具有启发信息的状态转移函数引导选路。具有启发信息的状态转移函数表示如下:
其中:kmax为待选前进路径(街道段)中涉及待访问负荷数最多的街道段号;kshort为待选前进路径中街道段长度最短的街道段号;kprobe为由转移概率准则最终选择的街道段号。
按照街道段符合的条件,顺次选择且只以其中一种方式选择街道段。
3.2.2 转移概率准则
本文采用伪随机比率作为择路规则。设q是一个分布在[0,1]区间上的随机变量,q0是一个常数,0≤q0≤1。
如果q≤q0,则
否则
其中:Pj(i,k)为蚂蚁j在节点i处选择前进街道段k的转移概率;ρj(i,k)为蚂蚁j在节点i处选择前进街道段k上的信息素;dk表示前进街道段k的长度;α为常数,用来调节街道段长度对转移概率的影响程度;R j(i)为蚂蚁j在节点i处所有待选前进街道段的集合。
3.3 信息素更新原则
3.3.1 各街道段信息素的初始化
针对沿街铺设线路的特殊性,各条街道段上初始信息素τ(k,0)由公式(7)获得,即
其中:H为各街道段初始化的同等信息素,保证蚂蚁有均等的机会走到各街道上;dk为街道段k的长度;Kl街道段k两侧负荷总个数;Kl dk反映每条街道所含信息。
依据式(7)初始化各条街道段的信息素,有助于蚂蚁选择更有效的街道段前进,加快寻优速度。
3.3.2 局部信息素更新
局部信息素更新是指蚁群在线路铺设成功,而且铺设方案的目标函数小于给定阈值情况下,对所有街道段的信息素进行更新,否则线路铺设即使成功,所有街道段的信息素也不会更新。该信息素更新准则的设定,既能避免较差铺设方案对街道段信息素的影响,又能充分体现当前最优路径的优势。
(1)每条街道段信息素的更新
每当一只蚂蚁走过一条街道段后,为避免后续蚂蚁只在当前所走过街道段附近寻路,需对该街道段信息素进行立即调整。
设蚂蚁j走过街道段k后,街道段k的信息素调整公式如下:
其中:β为常数;τ(k,t)为街道段k第t时刻的信息素;dk为前进路径街道段k的长度。
(2)街道段信息素的局部更新
当某组蚁群中所有蚂蚁共同完成了一次成功的线路铺设方案后,街道段信息素按如下操作进行局部更新。
(1)当蚂蚁j未经过街道段k,街道段k的信息素不作改变,即:
(2)当蚂蚁j经过街道段k,则街道段k的信息素为
其中:t表示当前时刻,t+1为下一时刻;M表示成功铺设线路涉及到的蚂蚁数目;τ0表示信息素挥发量;Lj表示第j只蚂蚁所访问的负荷个数;lj表示第j只蚂蚁访问的某负荷值;rj表示第j只蚂蚁经过某街道段的长度,Rj表示第j只蚂蚁所经过街道段的个数。
3.3.3 全局信息更新
根据目标函数值最小,确定到迄今为止各组蚁群线路铺设的最好方案,并将此方案对街道信息素的影响按以下方式进行全局更新。
(1)当蚂蚁j未经过街道段k时
(2)当蚂蚁j经过的街道段k时
其中:(1-τ1)表示全局信息素更新后街道段k信息素的剩余程度;Δτbest为最好方案下信息素的变化量,其他量的含义与局部更新相同。
3.4 蚂蚁前进路径的搜索策略
真实蚂蚁在觅食过程由所处环境中的信息量来决定前进的方向,而人工蚂蚁是在平面的节点上运动,因此可把觅食过程抽象成构造解的过程。
对于配电网络线路铺设问题,每一节点通过人工蚂蚁感知以该节点为端点的街道段上的负荷值或信息素浓度,来选择前进的街道段。蚂蚁的巢穴为变电站站点,食物为负荷点,人工蚂蚁从巢穴节点按照启发函数选择下一节点,直至找到了足够的食物(达到了线路负荷量),便得到了所求问题的一个可行解。
本文线路铺设是在变电站供电范围确定的全新的供电区域或开发区下,进行辐射型线路的铺设。铺设方法的流程图如图2所示。
由于蚁群搜索算法是一种随机搜索方法,因此,通常的算法停止准则是预先设定足够多的搜索循环数量。当算法达到这个预设的循环总数时,搜索过程终止。
4 算例测试及结果分析
本文算例在变电站选址、供电范围以及负荷分布情况均已知,而且规划区域为全新的供电区域或开发区情况下,依据规划目标和技术原则,按照辐射状的接线模式对目标年进行配网规划。所有铺设线路的导线截面积均相同。
通过多个算例的多次运行,蚁群种群规模取200,迭代次数(循环搜索数量)为8。
算例的规划区域拥有1座2×40 MVA的变电站,74个负荷点,目标年预测年最大负荷为51.71 MW。负荷空间分布及变电站位置如图3所示。
依据本文算法对算例进行配网线路铺设,所得规划结果如图3所示,此规划方案相对应的规划线路长度及所带负荷信息如表5所示。
该算例的规划区域负荷空间分布及负荷量大小不均,从规划结果来看:该区域共铺设线路19条,总长为50.43 km,平均长度为2.654 km,平均每条线路所带负荷2 721.45 k W。布线方案合理,符合规划要求,且与实际规划情况接近。
5 结论
启发式路径规划算法 篇5
大规模风电并网后,由于风电出力的波动性会导致线路有功潮流与节点电压的频繁波动,这种特殊性使电网规划面临着新的挑战[1]。文献[2]建立了含风电的输电网机会约束规划模型,给出的求解算法可以降低常规Monte-Carlo方法的计算量,但是难以计及发电再调度环节,且没有考虑风电接入后的无功规划问题。文献[3]研究了输电网短期有功与无功综合扩展规划,但是没有计及风电接入的情况。鉴于风电场的建设周期较短[4],故将有功和无功综合规划,进而实现系统资源的整体优化配置具有重要意义。本文针对大规模风电并网后的输电网有功与无功综合扩展规划进行了研究。
为计及风电在多时间尺度上(天/月/季)的不同出力特性,根据风电与负荷全年每小时的时序数据,建立了输电网短期综合扩展规划的数学模型,取网络设备投资的年值成本与方案在全年所有不满足安全约束场景下的控制措施成本之和为目标函数。由于风电出力具有波动性,本文以发电成本最小为目标函数,考虑了安全约束发电调度环节。
1 数学模型
本文采用如下模型进行扩展规划:
式中:v为目标函数;rl和rc分别为线路与无功补偿设备投资的资金回收系数;cp,np,npmax分别为输电走廊新建线路成本、数目及其相应的最大允许数目;cq,nq,nqmax分别为节点新增无功补偿设备单组容量的投资成本、组数及其相应的最大允许组数;L(np,nq)为方案(np,nq)在全年所有不满足安全约束场景下采取控制措施的成本总和,这里的控制措施包括负荷削减和弃风,其中不考虑弃风的经济损失。计算公式如下:
式中:e为单位负荷削减电量的经济损失;h为场景的持续时间,如1h;Pcut(u)为方案(np,nq)在第u个场景下的最小负荷削减量,具体求解见文献[3],这里的场景是由系统某时段下的风电出力与负荷所定义,即一个时段对应于一个系统场景。
考虑到风电出力的波动性,在系统运行过程中需要发电再调度以实现系统的功率平衡[5,6],故在含风电的输电网规划研究中计及发电再调度是十分必要且合理的。因此,上述模型中计算L(np,nq)时,首先是在全年所有场景下进行安全约束发电调度,若某场景下调度成功,则无需采取任何控制措施(相应的控制成本为0),否则计算其控制措施成本。故式(4)最终计算结果为所有不满足安全约束场景下的负荷削减成本总和。需要说明的是:全年8 760h的电网运行优化是需要进行机组组合的,其组合方案对电网在线实时优化调度也是有影响的,这部分内容将另文表述。本文重点是研究如何减少规划中所需计及的场景,文中为简化计算未计及机组组合,但在计及机组组合时该方法同样适用。
2 求解算法
上述模型求解的复杂性体现在计算方案的L(np,nq)。对于方案(np,nq),由于每个场景下的最小负荷削减量需通过1次或2次最优潮流计算获得,全年有8 760个场景,采用常规的优化算法通常要评估上万个解,总计就需要进行上亿次最优潮流,故在计算负担上这将是难以承受的。
基于复杂问题分解协调的求解思想,将原问题分解为2个子问题:网络设备投资决策(子问题1)与方案的控制措施成本评估(子问题2)。前者用于获取方案集,而后者则评估各方案的控制措施成本,进而得到各方案的目标函数值,以确定最佳方案。其中的关键是如何求解子问题1,即如何获取所需的方案集,使其尽可能地包含优化的规划方案。为此,下面分别从分析目标函数与问题本身的特性出发,构造算法的优化求解策略。
2.1 目标函数特性分析
如式(1)所示,目标函数由方案的投资成本及其控制措施成本两部分构成。基于电力规划经验可知,在合理规划的前提下,若系统投资成本越高,那么相应的控制措施成本就越低;反之,如果系统投资成本越低,则其相应的控制措施成本就越高。图1给出了目标函数的特性示意,其中C,L,v分别表示方案的投资成本、控制措施成本及目标函数值。由此可以获得启发,若通过合理的规划方法逐步生成与图中目标函数特性曲线变化一致的各方案,则这些方案的全体即为子问题1所需的方案集,其中目标函数值vmin点对应的方案即为最佳方案。需指出,图1中给出的曲线仅示意了整体的变化趋势。
2.2 极端场景集
根据系统各风电场与节点负荷全年每小时的时序数据,可获得总的风电出力与总负荷的时序数据,在此2维尺度下即可确定由系统风电和负荷构成的场景集,如图2所示,其中的点代表相应的1个场景,共计8 760个。
考虑到系统在负荷或风电出力较大情况下运行条件更为苛刻,故本文将给出极端场景集的定义。为便于问题的清晰表述,这里借用多目标优化领域的相关概念[7]。假定存在多目标极值最大化问题,目标函数记为g(gl,gw),其中目标变量gl和gw分别为系统的总负荷与总风电出力。图2中每个场景对应的点皆为该问题的可行点,它们共同形成可行点集S0(8 760个场景),设第k层极端场景集为S(k),,Ω(k)表示第1层至第k-1层极端场景的并集,即
S(k)通过以下步骤确定。
1)在可行点集S0-Ω(k)中找到总风电出力最大的点(g*l_k,i,g*w_k,i),并设置i=1。
2)令i=i+1,在S0-Ω(k)中获取除点(g*l_k,i-1,g*w_k,i-1)之外,满足总负荷不小于g*l_k,i-1条件的所有点。
3)如果步骤2找到了满足条件的点,则在相应点集中找到风电出力最大点(g*l_k,i,g*w_k,i),然后转步骤2;否则,令Ik=i-1,为S(k)中极端场景的数目。
4)输出S(k)={(g*l_k,i,g*w_k,i)}(i=1,2,…,Ik)。
依次取k=1,2,…,Kmax,直至遍历完全部S0。图2中分别给出了第1层、第10层和第50层的极端场景集(由外到内),用圆圈标记。
2.3 优化策略
在获得了某层极端场景集S(k)后,通过求解满足该场景集下安全约束的输电网综合扩展规划模型即可获得相应投资成本最小的方案。依据单调变化的性质,这种分层能保障随着k值增大,对应层的投资成本最小方案的成本递减。通过调整极端场景集相应的层数,就可得到不同的方案。显然,极端场景集的层数越大,极端场景下的负荷或风电出力相对就越小,获得的优化方案的投资成本就越低,同时方案的控制措施成本也就越高,反之亦然。
通过上述分析,结合图1中模型目标函数的特性,为了获得较优的方案,同时提高计算效率,这里先采用全局搜索以定位较优解所处的区域,全局搜索可以不选极端场景集的全部层S(k),k=1,2,…,Kmax,如依次从中选,分别求解其相应的方案,共计l1+1个。这里Δ1为层数增加的步长,可取较大值。
在获得了此方案集后,再计算方案的控制措施成本,进而得到各方案的目标函数值(按顺序其一般的变化趋势是先逐渐减小后逐渐增大),由此确定目标函数值最小的方案所对应的极端场景层数t。令Δ2为层数调整步长,可取较小值,在前述工作基础上进行局部搜索,即依次对,分别求解其相应的方案(共计2l2个)。同样,计算求得方案集中各方案的控制措施成本,进而得到其目标函数值,并与全局搜索所得最佳方案比较,从而确定最终的优化方案。
2.4 基于极端场景集的输电网综合扩展规划的数学模型
根据上述的优化策略可知,在算法求解过程中,需要获得满足第k层极端场景集下安全约束的输电网综合扩展投资成本最小的方案,其目标函数如下:
约束如下:
式中:PGw(k_s),QGw(k_s),PLi(k_s),QLi(k_s)分别为第k层极端场景集第s场景下节点w的风电有功与无功出力、节点i的有功与无功负荷;PGw(u),QGw(u),PLi(u),QLi(u)分别为节点w的风电全年时序有功与无功出力、节点i的全年时序有功与无功负荷;F为由全体场景获取第k层极端场景集的提取函数;f(PGi)为安全约束发电调度的目标函数,取总的发电成本最小;n是系统的节点数;Sbfrom,Sbend,Sbmax分别为线路b首端、末端视在功率及其上限;PGimin,QGimin,PGimax,QGimax分别为发电机节点有功功率和无功功率的下限和上限;QGwmax和QGwmin可根据文献[8]中的规定加以确定。该模型的求解算法见文献[3]。
由图2可见,极端场景集中的场景数目相对仍较多。为了提高模型求解的计算效率,考虑到各极端场景之间的独立性,这里采用先放松部分约束,然后逐步加入并排除无效约束的求解方法,具体如下:首先求解满足若干少数极端场景安全约束的投资成本最小方案,然后将该方案在余下所有极端场景下进行安全约束校验,并排除满足安全约束的极端场景;然后再从剩下的不满足安全约束的极端场景中取出若干场景,在已获得的方案基础上再求解满足这些场景下安全约束的投资成本最小方案,直至得到满足所有极端场景下安全约束的最终优化方案。
3 算例分析
本文的求解算法在Intel(R)Pentium(R)双CPU E2180(主频2 GHz,内存2 GB)上利用MATLAB-R2010a进行编程实现。
算例系统如图3所示。
图3中,节点1和2为多个风电场的汇集升压站节点,风电场总的装机容量分别为2 000 MW和2 400MW,分别经由线路L1-3和L2-4并入系统,节点6的外送功率为3 000 MW。为了使外送线路保持较高的利用率,这里假定其传输功率为恒定值。规划年时序的风电出力与负荷曲线采用了文献[9]中的数据。系统相关数据见附录A,这里取e为0.7元/(kW·h)。
令Δ1=10,l1=5,可得以下各层极端场景集S(1),S(11),S(21),S(31),S(41),S(51),由此顺序得1号—6号方案。图4与图5给出了各方案的投资成本、控制措施成本与总成本,1号—6号方案用圆圈标记。
由此可见,1号—6号方案的投资成本逐渐减小,然而其代价是控制措施成本逐渐增大,总成本的变化趋势表现为先减少后增大。其中,1号方案的网络投资成本最高,它可满足系统所有场景下的安全约束,故总成本也较高;6号方案虽然投资成本最低,但是控制措施成本很高,其总成本也最高。通过大范围的全局搜索可以确定当前的最佳方案是3号,在此基础上还需进行局部搜索。
为此,令Δ2=2,l2=3,可得以下各层极端场景集S(15),S(17),S(19),S(23),S(25),S(27),由此顺序求得7号—12号方案,图4和图5中用星号标记。由图5可见,在3号方案附近进行局部搜索后得到的9号方案,其目标函数值最低,这表明经局部搜索获得了更好的解。
综上所述,通过结合全局搜索与局部搜索,只需求解和评估较少的方案(共计12个),就可以获得满意解,与采用常规的优化算法求解原模型相比,算法的优化效率大大提高。附录B给出了上述12个方案的具体信息。
以S(21)获取相应的规划方案为例,其极端场景数为49。在模型求解过程中,首先取其中的6个极端场景,获得满足这些场景下安全约束的初步方案,然后分别校验其是否满足余下43个极端场景中每个场景下的安全约束,结果仅不满足其中7个极端场景下的安全约束。进一步,在初步方案基础上再求解满足此7个场景下安全约束的方案,即可得出最终的优化方案。其他层数极端场景集情况也类似,通常只需2至3步即可得到最终方案。对本算例,求解计算的平均时间约为0.8h。这表明通过这种约束处理方法可以相对较快地得到优化方案。
本算例全部的优化计算时间约为15.6h。工程上,如果对计算时间有更快的要求,一种可行的手段是在获得各层极端场景集后,利用并行计算技术来求解相应的各方案及其后续的控制措施成本。
4 结语
大规模风电场接入系统后,输电网不仅需要进行网架(有功)扩展规划,同时也要考虑无功扩展规划,而且将此二者综合规划可实现系统资源的优化配置。为此,本文提出了一种启发式算法来求解含风电的输电网短期综合扩展规划问题。该算法充分挖掘问题本身的特性,在此基础上构造优化求解策略,优化过程物理意义清晰,易于理解。通过算例分析,结果表明所提算法显著地减轻了计算负担,能在工程可接受的计算时间内获得较优的规划方案,有效解决了大规模风电接入后的输电网扩展规划问题,具有工程实用价值。
摘要：提出了大规模风电接入下的输电网有功和无功扩展规划的解决方法。计及了风电与负荷的全年时序数据,并将网络设备投资的年值成本与方案在全年所有不满足安全约束场景下采取控制措施的成本之和最小作为规划目标。为了降低求解计算的复杂性,将原问题分解为网络设备投资决策与方案的控制措施成本评估2个子问题,二者借助原问题的规划目标进行总体协调。在此基础上,通过分析规划目标与问题本身的特性,设计了启发式的优化算法,明显地提高了计算速度。算例分析验证了所提方法的正确性和求解算法的有效性。
关键词：输电网扩展规划,风力发电,启发式算法,分解协调
参考文献
[1]雷亚洲.与风电并网相关的研究课题[J].电力系统自动化,2003,27(8):84-89.LEI Yazhou.Studies on wind farm integration into powersystem[J].Automation of Electric Power Systems,2003,27(8):84-89.
[2]于晗,钟志勇,黄杰波,等.考虑负荷和风电出力不确定性的输电系统机会约束规划[J].电力系统自动化,2009,33(2):20-24.YU Han,CHUNG C Y,WONG K P,et al.A chanceconstrained transmission network expansion planning methodassociated with load and wind farm variations[J].Automation ofElectric Power Systems,2009,33(2):20-24.
[3]周金辉,余贻鑫,王菲,等.计及静态安全风险的输电网短期综合扩展规划[J].电力系统自动化,2010,34(6):22-25.ZHOU Jinhui,YU Yixin,WANG Fei,et al.Short termintegrated expansion planning for transmission networkconsidering static security risk[J].Automation of ElectricPower Systems,2010,34(6):22-25.
[4]庾晋.风电发展直面三大问题[J].中国电力企业管理,2007(6):44-45.
[5]高宗和,滕贤亮,张小白.适应大规模风电接入的互联电网有功调度与控制方案[J].电力系统自动化,2010,34(17):37-41.GAO Zonghe,TENG Xianliang,ZHANG Xiaobai.Solution ofactive power dispatch and control scheme for interconnectedpower grids with large-scale wind power integration[J].Automation of Electric Power Systems,2010,34(17):37-41.
[6]张伯明,吴文传,郑太一,等.消纳大规模风电的多时间尺度协调的有功调度系统设计[J].电力系统自动化,2011,35(1):1-6.ZHANG Boming,WU Wenchuan,ZHENG Taiyi,et al.Designof a multi-time scale coordinated active power dispatchingsystem for accommodating large scale wind power penetration[J].Automation of Electric Power Systems,2011,35(1):1-6.
[7]雷德明,严新平.多目标智能优化算法及其应用[M].北京:科学出版社,2009.
[8]国家电网风电场接入电网技术规定[S].北京:国家电网公司,2009.