分层路径搜索算法研究

2024-08-29

分层路径搜索算法研究（精选5篇）

分层路径搜索算法研究篇1

摘要：随着光纤逐步成为传输业务的主要载体, 越来越多的接入业务基于光路通道开放, 由于通信网络资源有限, 业务扩张带来的压力与日俱增, 如何通过有效的方法, 对现网业务进行调整优化, 实现更好的市场效应, 成为通信维护管理工作的一大挑战。本文尝试引入路径搜索算法, 对主干业务系统进行路径分析和优化, 找到基于资源现状且面向业务最优分配的调度方案, 在完成业务需求的同时, 实现最佳的资源配置, 并在现网中实践应用。

关键词：路径搜索,通信资源,业务优化

一、引言

在日常资源调度中, 由于现网业务的紧迫性, 需要及时根据资源情况调配业务需求。前期的调配本着快速完工形成市场效益, 在资源分配上并非最优, 甚至会使部分片区资源呈现不合理的紧缺。随着网络规模扩大和建设拓展, 维护管理中亟需对业务合理优化, 释放紧缺资源, 优化网络架构。

随着数年来资源数据信息化的建设, 已经实现了资源数据的平台化。在实际分配过程中, 不同的需求部门对业务分配方式有各自的侧重关注点, 如市场部门关注业务覆盖范围, 即资源的可达性;网络线条关注资源的提供和承载能力;业务维护部门关注开通和维护的便利性;建设部门关注建设和当前需求的均衡性等。此外, 还有业务的稳定性、后期的扩容性等等。

基于这种全局化的资源分配需求, 以及对后续拓展进行网络优化工作的探索, 必须有能够兼顾各方面需求的算法来进行资源调配, 本文将针对线路资源数据的特点, 采用搜索规划的算法解决优化问题。这种算法能够就对一定规模的网络节点和线段进行分析, 寻求具备合理性的最佳业务路线。

二、业务模型概述

当前网络基本建立在划分城区而成的网格上, 每个规划的网格中都存在相应的业务侧设备, 并通过中继段连通至接入侧设备。为了便于简化模型, 假定在一个较小的片区中进行传输业务规划, 在整个业务的流向中, 数据从源端设备到宿端设备所经过的承载载体进行遍历, 不难发现业务的走向是经由“始端设备→交接设施→中继段→交接设施→…→交接设施→中继段→末端设备”这种点线交替的形式。剔除首末端固定的设备, 该路径是由“点-线”间插交替的路径模型。

针对该业务模型, 可定义拟定优化方向的判定标准: (1) 总体和当前业务覆盖能力, (2) 交接设施成端的比率, (3) 局向纤芯使用率。

为简化模型计算的呈现, 对运算变量统一标识, 表述基础数据如下:

交接设施点集 (m为总节点数) :S={S1, S2, S3, …, Sm}

中继段集 (n为总线段数) :L={L1, L2, L3, …, Ln}

中继段长度集:Len={Len1, Len2, Len3, …, Lenn}

中继段纤芯占用率:Ф={Ф1, Ф2, Ф3, …, Фn}

中继段纤芯数:n={n1, n2, n3, …, nn}

vik代表规划路径所经交接设施, 第i条可达路径的第k个跳接点。有vik∈S。

lik代表规划路径经中继线段, 第i条可达路径的第k条线段。有lik∈L。

lenik代表第i条可达路径的第k条线段的长度, 有lenik∈Len。

所有规划出的路径集合 (Trace Route) :

如上, 则第i条可达业务路径的跳接次数为Ni, vi0=v0, viN i+1=vd。

假定某次业务优化路径数量为, 全程功率损耗为λi d B, 单位线长的损耗为λad B, 跳接点的熔接损耗为λbd B, 全程可供的最大损耗为λT, 则可以得出每条规划路径的全程损耗为:

对于第i条规划业务路径自至的跳接次数Ni, 假定有序集合TRi中的元素个数为Ri (Ri=CardiTRi) , 则:

在整个业务路径规划中, 路径损耗是业务开通的关键因素, 路径损耗必须在业务要求的功率范围内满足, 且取最小。损耗主要包括光路中的单位损耗和跳接点的接续损耗。而跳接点的数量也会在现场布线操作时产生人工消耗和业务不稳定因素, 所以确定路径规划的两个基本约束条件为:a.损耗最小, b.跳接点最少。

由此, 该模型可转变为:在有限的跳接次数以内, 使得功率损耗最小的路径, 即目标函数为:

其中U (Ni, λi) 为以目标优先的二元目标函数集, 也就是说在满足最少跳接次数Ni的前提下使得λi可控且最优的方案集合。

从函数的性质上看, 应该有U/Ni>0, U/λi>0。从目标优先的次序看, 有U/Ni>>U/λi。

规划路径的节点集:

规划路径的线路集:

路径损耗:

根据上述推演, 求解式 (1) - (7) 所形成基本约束条件。

三、算法求解思路

根据上述算法, 拟定求解思路如下:

(1) 根据业务点坐标确认覆盖该业务范围的业务设施位置, 拟定为通路起点P1, 确认设施P1的业务提供能力; (2) 从所选择业务点坐标确认覆盖范围内是否含有末梢光交接设施, 得出最近直线距离内交接设施点坐标, 拟为路径终点PNi; (3) 分别从P1、PNi点出发, 对比各中继段所能到达的交接设施, 追溯由P1至PNi的可达路径, 通过比较跳接次数和全程功率损耗来确定最优路径; (4) 从搜索算法来看, 需设定多个路线集和点集, 运算量会随网络规模和跳接次数的增加成级数增长, 为节约算法复杂度和计算成本, 需考虑限定措施。

具体算法设计如下:

A.先将起始点作为P1, 假定P1到目标点PNi存在直通通路 (直通缆段) , 则直接得出最优路径;

B.当直通缆段不存在时, 匹配经过节点P1的所有线路{QP1}和经过节点PNi的所有线路{QPNi}, 确认是否存在公共节点P2, 若存在, 则P1-P2-PNi为所求通路路径;

C.当{QP1}和{QPNi}中不存在公共节点P2时, 将问题转换为节点P2和节点PNi之间是否存在公共节点P3的问题求解, 以确定P1-P2-P3-PNi的通路路径;

D.以此类推, 考虑N次跳接的情况, 逐步追溯得出结果;

E.同步考虑功率损耗, 当最短路径已超出光功率限额范围时, 自动退出搜索并返回;

F.当结果TRi存在多个时, 通过对比各个结果的λi选择最优的业务规划路径。

不难看出, 对业务优化的模型可以转换为对点线模型路径规划的算法演绎。受到路径规划算法复杂度的限制, 算法的计算成本随着网络规模增长而加大, 在本文应用的模型中, 过多的跳接点会带来额外的路径损耗, 而路径损耗是业务规划模型的基本约束条件, 常规场景下, 布线跳接次数应有限限定, 因此, 在算法中也可通过减少或限定计算的跳接次数 (如Ni Max≤5) , 使算法的计算成本基本可控。

四、结论

经测试算法内容通过输入测试数据圆满实现业务优化。基于自动化算法的模拟资源调配方案, 可用于现网有限资源的调整, 为新增业务腾出空间, 同时也可推广应用到基于现网资源基础的工程预设计中, 从方案初期就介入方案合理性, 减少后期因资源优化带来的业务中断影响客户感知。

参考文献

[1]Santanu Saha Ray.Graph Theory with Algorithms and Its Applications[M].北京:Springer, India, PrivateLtd, 2013

[2]王海英.图论算法机器MATLAB实现[M].北京:北京航空航天大学出版社, 2010

用广度优先搜索算法实现路径搜索篇2

关键词：广度优先搜索,VC语言

路径搜索是许多游戏特别是即时战略游戏的核心组成部分, 玩过即时战略游戏 (如红色警报) 的朋友们对此一定都不陌生。在这类游戏中, 玩家不需要控制游戏主角的每一步移动, 只需用鼠标点击一下目的地, 游戏主角就可以自己移动到那里。那么游戏是如何实现路径搜索的呢?实现路径搜索的算法又是什么呢?下文就以一个简单的路径搜索为例, 说明上述问题, 并给出VC++的程序实现。

1 路径搜索的实现方法

路径搜索是一个寻径问题, 所谓寻径问题, 就是在地图上的起始点A和目的点B之间寻找一条可通行的路径。显然, A和B之间可以有很多条路径, 目的就是用最短的时间找到一条最佳路径。寻找最佳路径, 其本质就是搜索, 是一个从初始节点出发, 沿着与之相连的边试探前进, 寻找目标节点的过程。

路径搜索的基本算法主要有盲目搜索和启发式搜索两种, 进行盲目搜索时, 扩展节点不估计路径代价, 是比较常用的方法, 下文采用一种盲目搜索算法——广度优先搜索算法来实现即时战略游戏中的路径搜索。

1.1 广度优先搜索算法简介

广度优先搜索算法把起点作为初始节点, 从初始节点开始, 应用算法生成第一层节点, 检查目标节点是否在这些后继节点中。若没有, 再用算法将所有第一层的节点逐一扩展, 得到第二层节点, 并逐一检查第二层节点中是否包含目标节点。如此依次扩展、检查下去, 直至发现目标节点为止。这里采用的原则是先生成的节点先扩展, 为满足这一要求, 采用“队列”这一数据结构来存储节点, 队列设置两个指针:open指针和closed指针, open指针指向扩展得到的节点, closed指向已检查过的节点。当open=closed时, 表示队列空, 当open大于队列长度时, 表示队列溢出, 如图1所示。

1.2 路径搜索的实现过程

为了具体说明广度优先搜索算法在即时战略游戏中的应用, 以一个简单的路径搜索为例, 构造一个二维地图, 如图2所示, 把地图均匀划分为若干个小方格, 在图2中共3*3个方格, 游戏主角位于一个方格中, 我们选中其他任一个方格作为目的地, 点击鼠标, 游戏主角自动选路移动到目的方格。为了更加逼近现实情况, 可以设置某些方格为障碍物, 即游戏主角必须绕过障碍才能前进。例如, 方格编号如图2所示分别为1、2、……、9, 游戏主角位于方格1中, 方格5为障碍物, 玩家要使主角移动到方格9中, 那么广度优先搜索算法把1加入队列, 此时队列包含{1}, 检查1是否目标节点, 不是目标节点则继续搜索, 从1开始搜索相邻节点, 这是第一层搜索, 得到方格2和4, 检查2和4, 不是目标节点, 则2、4进入队列, 队列包含{1, 2, 4};进行第二层搜索, 由2搜索相邻节点得到3, 也搜索到了5, 但是方格5是障碍物, 不能加入队列, 由4搜索到7, 检查3和7, 不是目标节点, 于是3、7进入队列, 队列包含{1, 2, 4, 3, 7};继续第三层搜索, 由3得到6, 由7得到8, 检查6和8, 不是目标节点, 于是6、8进入队列, 队列包含{1, 2, 4, 3, 7, 6, 8};继续第四层搜索, 由6得到9, 检查9是目标节点, 于是结束搜索。为了记住搜索的路径, 在搜索过程中, 设计数据结构记录每一个节点的前趋节点, 如2的前趋节点是1, 这样, 在找到9之后, 可以根据前趋节点回溯到节点1, 回溯过程是9、6、3、2、1。可以用“栈”这一数据结构保存回溯过程, 压栈顺序为9、6、3、2、1, 这时, 游戏主角可以按路径移动, 移动按出栈顺序进行, “栈”是后入先出的数据结构, 于是, 主角就按1-2-3-6-9的顺序完成移动。

2 程序实现

下面给出广度优先搜索的程序实现。选用VC++6.0作为程序开发平台, 建立基于对话框的工程。程序设计的关键是: (1) 编写广度优先搜索类, 用于随机生成二维地图, 并且实现路径搜索。 (2) 实现游戏主角在地图中移动。

2.1 实现广度优先搜索的类CBfs Map

下面依次介绍CBfs Map类的成员函数。

函数void Init Map () 用于初始化地图, 并随机设置障碍物。

函数void Search Path () 用于路径搜索:

2.2 实现主角在地图中移动

创建一个基于对话框的类CBfs Dlg, 在类中添加按下鼠标左键的消息响应函数On LButton Down () , 该函数根据鼠标左键点击的位置, 进行路径搜索, 代码如下:

程序运行情况如图3所示, 界面中红色栅格表示障碍, 白色部分表示通路, 当玩家点击任意空白处, 游戏主角能够自行移动到该位置。

3 结语

介绍了一种采用广度优先搜索算法实现路径搜索的方法, 并给出了原理及关键数据结构。虽然代码不多, 却实现了一个较为完整的路径搜索实例, 希望能对游戏编程爱好者们起到积极的参考作用。

参考文献

分层路径搜索算法研究篇3

多车场车辆路径问题 (Multi-depot Vehicle Routing Problem, MDVRP) 是由车辆路径问题 (Vehicle Routing Problem, VRP) 衍生而来, 其将经典车辆路径问题中单个车场扩展为多个车场。MDVRP所要解决的是确定顾客由哪个车场服务及被访问的路径, 使总行驶路径最短。MDVRP广泛存在于多个行业之中[1], 对其研究不仅具有实际的应用价值, 更是研究供应链集成与协调的基础。由于MDVRP是NP难问题, 只有在顾客数目较小的时候才能得到精确解, 更多时候需要借助于启发式算法[2,3,4,5]求解, 如何有效求解该问题成为关注的焦点。目前国外学者对该问题研究相对较多, Chao等采用多阶段启发式来求解, 其首先使用简单启发式生成初始解, 然后通过将顾客移动到不同车场对初始解进行改进[6]。Renaud等采用4-opt*、λ交换等交换技术设计了三种基本搜索过程在禁忌搜索算法的各个阶段组合使用, 求解带能力约束及路径长度约束的多车场车辆路径问题, 该算法采用Benchmark问题测试, 部分结果为目前最好解[1]。Pisinger等提出了自适应大规模邻域搜索启发式, 求解包括MDVRP在内的五种不同车辆路径问题, 该算法更新了采用Benchmark问题测试得到的十五个目前最好解[7]。尽管如此, 不同的求解算法仍在不断地被尝试, 如何有效求解MDVRP依然是研究该问题的重要方向。国内学者针对该问题研究相对较少, 仅少数几个算法如遗传算法[8,9]、禁忌搜索[10]和蚁群算法[11]被提出, 且大部分文献只对随机生成的小规模问题进行测试, 很少采用Benchmark问题数据集测试, 不能很好地反映算法的求解效果。

分散搜索算法 (Scatter Search, SS) 是新近应用于求解组合优化和非线性优化问题并取得较好效果的亚启发式算法[12]。一些学者已经成功地将该算法应用到求解VRP问题中[13,14]。分散搜索算法框架灵活, 很容易和其他算法结合, 使得对解空间搜索更加有效。文献[14]的实验结果也证明该算法可以和目前求解该问题的最好亚启发式相媲美。但国内外采用分散搜索算法求解不同类型的VRP问题非常少见, 有鉴于国内目前对MDVRP的研究现状及分散搜索算法求解VRP相关问题的研究进展, 本文尝试采用分散搜索算法求解MDVRP。

1 MDVRP数学模型

1.1 问题描述及假设

在一个分销网络中, 某供货商拥有M个仓库为 N个零售商供应某一种商品, 每个仓库拥有一定数目的车辆, 被称为车场;零售商则可以看成要被服务的顾客点。若采用图来进行描述, 则假设G= (V, A) 为该分销网络, 其中顶点集V包括Vc和Vd两个集合, Vc={v1, v2, …, vN}表示顾客点集;Vd={vN+1, vN+2, …, vN+M}表示车场集合;弧集A={ (vi, vj) |vi, vj∈V, i≠j}为任意两点间的边。距离

矩阵D= (Dij) 为边 (vi, vj) 的长度, 假设D对称, 并且任意三点之间的距离满足三角不等式, 距离单位为公里。每个车场具有K辆同样型号、载重量为Q 吨的车辆, 每个车场的车辆数目都足够满足运输需求。每个顾客的需求为Qi吨 (i=1, 2, …, N) 且假设 Qi<Q.

MDVRP中车辆运行路径需要满足:①从某个车场出发的每辆车, 服务一些顾客点后, 必须回到出发车场;②每个顾客点都必须仅被一辆车访问且只访问一次;③每辆车的载重量不能超过该车的容量限制;④车辆不能从一个车场到另一个车场, 且路径中不能出现回环。

MDVRP需要解决的是如何将顾客划分到合适的车场并安排其访问路径, 使整个网络的运输距离最小。其中xpkij为决策变量, 当满足车场p的车辆k存在从i到j的路径 (i, j∈V) 时取1, 其他情况取0。

1.2 数学模型

本文基于文献[8]中的数学模型, 对MDVRP问题进行描述。该模型的目标函数如下:

$\min d i s = \sum_{i = 1}^{Ν + Μ} \sum_{j = 1}^{Ν + Μ} D_{i j} \sum_{p = 1}^{Μ} \sum_{k = 1}^{Κ} x_{i j}^{p k} (1)$

其约束条件具体如下:

$\begin{array}{l} \sum_{i = 1}^{Ν} Q_{i} \sum_{j = 1}^{Ν + Μ} x_{i j}^{p k} \leq Q, \\ p \in {1, 2, \dots, Μ}, k \in {1, 2, \dots, Κ} (2) \\ \sum_{j = 1}^{Ν + Μ} \sum_{p = 1}^{Μ} \sum_{k = 1}^{Κ} x_{i j}^{p k} = 1, i \in {1, 2, \dots, Ν} (3) \\ \sum_{i = 1}^{Ν + Μ} \sum_{p = 1}^{Μ} \sum_{k = 1}^{Κ} x_{i j}^{p k} = 1, j \in {1, 2, \dots, Ν} (4) \\ \sum_{j = 1}^{Ν} x_{i j}^{p k} = \sum_{j = 1}^{Ν} x_{j i}^{p k} \leq 1, \\ i \in {Ν + 1, Ν + 2, \dots, Ν + Μ}, \\ k \in {1, 2, \dots, Κ}, p \in {1, 2, \dots, Μ} (5) \\ \sum_{j = Ν + 1}^{Ν + Μ} x_{j i}^{p k} = \sum_{j = Ν + 1}^{Ν + Μ} x_{i j}^{p k} = 0, \\ i \in {Ν + 1, Ν + 2, \dots, Ν + Μ} \\ k \in {1, 2, \dots, Κ}, p \in {1, 2, \dots, Μ} (6) \\ \sum_{i \in S} \sum_{j \in S} x_{i j}^{p k} \leq | S | - 1, \forall S \subseteq V_{c}, 2 \leq | S | \leq n \\ p \in {1, 2, \dots, Μ}, k \in {1, 2, \dots, Κ} (7) \\ x_{i j}^{p k} = {0, 1}, \forall i, j \in {1, 2, \dots, Ν + Μ}, \\ p \in {1, 2, \dots, Μ}, k \in {1, 2, \dots, Κ} (8) \end{array}$

式 (1) 为目标函数, 最小化总的行驶距离;式 (2) 为车辆的容量限制;式 (3) 、式 (4) 保证每个顾客点只能被一辆车访问一次;式 (5) 确保任何车场的任一从该车场出发的车辆, 服务结束后返回该车场;式 (6) 使得车场与车场之间不存在路径;式 (7) 为排除子环约束;式 (8) 为决策变量的取值约束。

2 求解MDVRP的分散搜索算法

2.1 分散搜索算法框架及执行过程

分散搜索算法是由Glover于1977年提出的, 直到近些年该算法才被应用于求解车辆路径问题、图着色问题、调度问题等组合优化和非线性优化问题中。分散搜索算法基础源于最初用来求解组合决策规则和约束的策略, 属于一种通过组合其他解来构造解的基于种群的算法[15]。分散搜索算法具有统一的框架, 便于算法设计与实现, 框架中包括五种方法[16]:

①多样性产生方法:采用任意的一个临时解作为输入, 产生一个多样性的待选解集。

②改进方法:将一个待选解变换为一个或多个改进解。在分散搜索算法中无论是待选解还是改进解都可以是不可行解。若一个待选解没有被改进, 那么认为改进解为该待选解。

③参考集更新方法:建立和维持由b个 (通常b的取值很小, 例如b不超过20) “最好”解组成的参考集。从目标值来看, 一个“最好”解需要具有较高的质量;从多样性角度看, 即使该解的目标值较差, 但其具有较好的多样性, 那么该解仍然作为“最好”解。

④子集产生方法:作用在参考集上, 用来构建不同类型的参考集子集, 所有子集作为产生新待选解集的基础。

⑤解组合方法:将采用子集产生方法生成的子集通过设计的规则组合成一个或者多个新解。

分散搜索算法的求解过程如图1所示, 首先采用多样性产生方法生成待选解集并采用改进方法对待选解集中的解进行改进;其次在改进后的待选解集中选择一些高质量的和具有较好多样性的解建立参考集;然后在参考集的基础上采用子集产生方法生成子集;接下来将子集中的解采用解组合方法进行组合, 生成新解并采用改进方法改进新解;最后按照参考集更新方法判断改进后的新解能否更新参考集, 如果参考集被更新, 则进行新的搜索, 否则搜索过程结束。

分散搜索算法框架中的五种方法需要根据问题进行设计与实现, 这使得分散搜索算法具有很好的灵活性。不同于遗传算法等其他种群算法, 分散搜索算法种群规模即参考集中解的个数相对较小, 并且分散搜索算法以系统的方法选择解进行组合生成新解, 而不同于遗传算法对随机性有较强的依赖性。

2.2 分散搜索算法解编码

与其他基于种群的算法一样, 分散搜索算法首先需要对解进行编码, 然后按照算法实现步骤进行计算。在文献[8]的基础上设计了基于顾客的编码方式, 如图2所示。每个解包含n项, 对应于n个顾客点;其中每一项包含四个部分:顾客点号;服务顾客的车辆所属的车场号;服务顾客的车辆号;顾客在每条路径中的访问顺序。当解确定后, 一个顾客点i被访问的信息则可根据这四部分确定, 如图2中顾客点1被第4个车场的第2辆车第3个服务。该编码方式没有显性地给出路径, 但是通过依次对解的车场、车辆号及访问顺序进行排序, 则能得到路径。

2.3 多样性产生方法

分散搜索算法通过具有较好多样性的解来进一步扩大对解空间的搜索。为了提高待选解的质量及多样性, 基于扫描算法和最优划分过程设计了多样性产生方法产生待选解集。

该方法包括四步:①将顾客点分配给距离该顾客点最近或次近的车场, 即先设定一个顾客点与最近车场及次近车场距离的比值γ, 若超过该比值则随机分配到最近车场或次近车场, 若小于该比值则分配到最近车场;②令每个车场生成一个初始访问顺序, 即首先从划分到该车场的顾客点中随机选取一个作为起始点, 然后采用扫描算法进行排序, 生成一个初始的访问顺序;③分别对不同车场的初始访问顺序进行最优划分[17], 生成该访问顺序的最优车辆分配方案;④将所有车场生成的访问方案组合生成一个包含所有顾客点的初始解。

由该方法生成的初始解均为可行解, 将该过程重复运行p次 (p为待选解集的大小) , 其中保证每次随机初始点的选取均不重复, 以满足多样性要求, 将生成的待选解集记为P.

2.4 解改进方法

算法的解改进方法可以处理可行解及不可行解, 并产生一个改进解。

定义1 结构可行解:满足路径约束:①每个顾客点都必须仅被一辆车访问且只访问一次;②车辆起始于同一车场;③车辆不能从车场到车场, 且路径中不能出现回环;的解称为结构可行解。

本分散搜索算法中多样性产生方法生成的解均为可行解, 而通过组合方法生成的解中可能存在部分路径违反车辆能力约束仅为结构可行解。因此解改进方法对不可行解的可行化过程是对违反能力约束路径中的点作移出插入操作, 使每条路径满足能力约束。移出插入操作基于启发式, 其主要思想是从违反能力约束的路径中顺序移出插入代价最大的点, 直到满足能力约束为止。然后将这些移出的点插入到不违反能力约束前提下插入代价最小的位置。若不存在这样的位置, 则将所有不能插入的点采用最优划分方法构成新的路径。

解改进方法对可行解进行改进的主要思想是将2-交换[18]、2-交换*[18]及最坏移出-预测插入启发式[7]三种局部搜索策略相结合构成迭代下降算法对解进行改进。局部搜索策略速度快, 具有良好的局部寻优能力, 可以使分散搜索算法在不同搜索空间中获得更满意的解, 且三种算法均简单易行, 降低了算法的复杂性。

2.5 参考集更新方法

参考集更新方法包括建立初始的参考集和更新参考集两部分。

(1) 初始参考集构建

通常参考集Refset包括两个子集, 具有b1个高质量解的子集Refset1和具有b2个较好多样性的子集Refset2。首先从p个待选解中选择b1个目标函数值最好的解构成Refset1。其次根据问题拓征定义两个解之间的距离, 选择多样性解构建Refset2。

定义2 两个解之间的距离:设解X1含有E1条边, X2含有E2条边, 两个解共有Ec条公共边, 则两个解之间的距离公式为 $1 - \frac{2 E_{c}}{E_{1} + E_{2}}$ 。

从定义2可以得出两个解之间的距离分布在[0, 1]区间内, 当两个解完全不同时, 它们之间的距离为1, 此时距离最大;当两个解完全相同的时候, 他们之间的距离最小为0。计算目前不在参考集中的其他初始解, 即P-Refset集合中的解与参考集中解之间的距离。首先将P-Refset集合中的每一个解与参考集中解之间距离的最小值选择出来, 得到|P-Refset|个最小值, 然后从这些最小值中选出一个最大值, 该最大值对应的解为选择出的多样性解[15], 将此过程重复b2次, 完成初始参考集的构建。

(2) 更新参考集

更新参考集的方法很多, 本算法采用基本的静态更新方法[19]更新参考集, 即在参考集中的解和通过组合方法产生的新解中选取b1+b2个目标函数值最好解作为新参考集。

2.6 解组合方法

在求解MDVRP时, 子集采用四种类型的子集[15], 即二元组、三元组、四元组及包含最好r个元素 (5≤r≤b) 的子集。在基本分散搜索算法中, 通过组合方法可以产生一个或者多个解, 在本算法中组合方法使每个子集产生唯一解。该解组合方法基于弧组合方法, 通过选择公共弧和高质量弧来将不同解进行组合。

为了计算方便, 解组合方法将一个解转化成与其唯一对应的 (M+N) × (M+N) 0-1矩阵A= (aij) , i, j∈1, …, M+N, 当aij为1时表示存在从i行所代表的顶点到j列所代表的顶点间的弧, 否则aij为0。如图3所示, 假设3个车场, 10个顾客点得到的访问路径如图3 (a) , 则其对应的矩阵如图3 (b) 所示, 其中矩阵左上角框中的1′, 2′, 3′代表车场。路径与矩阵的转换方法则以图3 (a) 中路径0-8-3-0为例说明。在路径0-8-3-0中, 0表示车场3, 相应的图3 (b) 中a3, 11, a11, 6, a6, 3为1, 解中的其他路径也按此方法进行转换。

解组合算法的过程可以描述如下:

步骤1. 将子集中的所有解转化成矩阵Al= (aij) , l ∈[1, num], 其中num为子集中解的个数

步骤2. 将子集中所有解转化成的矩阵相加, $A^{'} = \sum_{l = 1}^{n u m} A_{l}$

步骤3. Fori=A′的第m+1行 toA′的第m+n行

将i行中aij值最大的列选出来, 保存在变量list中

If 同时存在多个最大值 then

选择具有最大值且弧长度dij最小的列, 更新变量list

End if

将该行list中记录的列置为1, 该行其他列置为0

End For

步骤4. Forj=A′的第m+1列 toA′的第m+n列

Ifj列中任何一位都没有被设定 then

将j列中aij值最大的行选择出来, 保存在变量row中

If 同时存在多个最大值 then

选择具有最大值且弧长度dji最小的行, 更新变量row

End if

将该列row中记录的行置为1, 该列其他行置为0

Else

保持该列中已被置1的行不变, 将该列的其他行置为0

End if

End For

步骤5. Fori=A′的第1行 toA′的第m行

If $\sum_{j = m + 1}^{m + n} a_{i j} \neq \sum_{j = m + 1}^{m + n} a_{j i}$ then

If $\sum_{j = m + 1}^{m + n} a_{i j} > \sum_{j = m + 1}^{m + n} a_{j i}$ then

Do 从i行中选择弧长度最大的aij, 将该弧移动到ai+1, jWhile $(\sum_{j = m + 1}^{m + n} a_{i j} \neq \sum_{j = m + 1}^{m + n} a_{j i})$

Else

Do 从i列中选择弧长度最大的aij, 将该弧移动到ai, j+1While $(\sum_{j = m + 1}^{m + n} a_{i j} \neq \sum_{j = m + 1}^{m + n} a_{j i})$

End if

End For

步骤6. Fori=A′的第1行 toA′的第m行

Forj=A′的第m+1列 toA′的第m+n列

Ifaij=1 then

遍历路径, 并记录访问过的顾客点

If 路径的结束车场与起始车场不同 then

将路径的结束车场改为起始车场

End if

End For

步骤7. 将没有访问到的顾客点之间的弧除去, 并分别构成这些点与其距离最近的车场的路径

该解组合方法过程首先将一个子集中的所有解转化成相应的矩阵 (对应于过程中的步骤1) , 再将这些矩阵相加 (对应于过程中的步骤2) , 然后对相加后的结果矩阵采用启发式规则选择弧来产生新解。启发式规则考虑了公共边及距离因素。首先对表示顾客点的行进行操作, 使每个顾客点的出度为1, 即每行只有一个位置值为1, 其他为0 (对应于过程中的步骤3) ;其次对表示顾客点的列进行操作, 使每个顾客点入度为1即每列只有一个位置值为1, 其他为0 (对应于过程中的步骤4) ;再次调整车辆与车场的所属关系 (对应于过程中的步骤5、步骤6) ;最后确保路径中不存在子环 (对应于过程中的步骤7) 。

解组合方法得到的解具有结构可行性。在上述过程中的步骤3、步骤4保证每个顾客点只能被一辆车访问一次;步骤5、步骤6确保任何车场任一从该车场出发的车辆, 服务结束后返回该车场;步骤7使得该解不包含子环。由于子集中的解都是可行解, 显然对相加后的矩阵来说必然满足车场与车场之间不存在路径, 即图3 (b) 中方框中的元素均为0。

3 实验及分析

测试环境:采用JAVA语言对算法进行编码, 在MS windows XP;CPU:Core (TM) 2, 1.83GHz;1GB内存环境下测试。

3.1 小规模数据测试

选取近几年国内求解MDVRP问题的文献[8,9,10]数据进行测试, 其测试数据均为随机产生的小规模数据。其中M表示车场的数目, N为顾客点的数目, C为车辆的载重量。分散搜索算法中待选解集的大小为10, 参考集大小为5, b1为3, b2为2。顾客点与最近车场及次近车场距离的比值γ=1, 迭代下降算法的迭代次数为10, 结果如表1、表2所示。

* 该结果是在PⅣ2. 0上运行得到。

* 表2中文献[10]数据结果的最优路径中的A、B、C分别对应于原文献中的车场16、17、18。

表1结果显示, 采用分散搜索算法得到的解均优于文献中的解, 其在解质量方面具有一定的优势, 具体路径列于表2。文献[8]与文献[9]采用不同的遗传算法求解同一组数据的MDVRP, 得到同样的结果。由于文献[8]、[9]、[10]中未明确给出算法的计算时间, 故无法精确衡量算法的速度差异, 但是从分散搜索算法的计算时间上看, 对于15个顾客点的小规模数据其计算时间不超过2秒, 与文献[10]中所述计算时间小于10秒相比, 其计算速度相对较快。

3.2 Benchmark问题测试

为了进一步验证分散搜索算法的有效性, 从http://neo.lcc.uma.es/radi-aeb/WebVRP/中选取中大规模的Benchmark问题进行测试。该Benchmark包括11个由Christofides、Eilon[20]及Gillett、Johnson[21]提出的经典问题, 12个由Chao[6]提出的新问题。在这23个实例中有11个仅有能力约束, 另外12个为能力和距离约束。本文选取具有能力约束的11个实例进行测试, 问题参数如表3所示。算法中参数γ在[0.5, 1]范围内取值, 其他参数与小规模数据测试相同。

* GAP= (分散搜索算法最优解-Benchmark目前最优解) /Benchmark目前最优解。

从表4可以看出, 分散搜索算法得到的最优解与目前最优解之间的差距均小于5%, 大部分测试算例均稳定在1.5%左右, 其中对于数据P01和P12求得的最优解与目前Benchmark最优解相同。本文选取了多阶段启发式[6]、禁忌搜索[1]及分治蚁群算法[11]与分散搜索算法进行比较, 结果表明分散搜索算法存在等于或优于前三种算法的结果。对于P15、 P18、 P21三个大规模数据, 分散搜索算法的结果要优于多阶段启发式和分治蚁群算法。对于P04、P05、P06、P07四个中等规模的数据, 分散搜索算法的结果要优于分治蚁群算法;与多阶段启发式算法相比, 虽然分散搜索算法的解并不具优势, 但是它们之间相差并不大。对于小规模问题, 分散搜索结果要差于其他三种算法, 其中仅在P03问题上与其他三种算法结果的差距为1.28%, 而在P02问题上与其他三种算法结果的差距为0.28%。总的看来, 任何一种算法都不可能完全优于其他算法, 包括Benchmark的目前最优解也是由多种算法求得。每种算法通常只对算例中的几组数据非常有效, 这与顾客点的分布状况, 车辆的载重能力及问题的规模有很大的关系。

由于上述三种算法其最优解的求解时间并未给出, 因此并未对时间进行比较, 仅给出分散搜索算法的求解时间。从求解的时间上看, 当问题规模增大时, 其求解时间增加较快, 对于大规模问题分散搜索求解时间较长, 但该时间通常也在可以接受的范围之内;对于小规模问题其求解速度相对较快。

4 结论

设计高效的MDVRP求解算法一直是MDVRP的重要研究方向。本文提出一种分散搜索算法求解MDVRP。该分散搜索算法中各部分均采用简单启发式, 使分散搜索算法较其他算法容易理解并便于实现, 为求解多车场车辆路径问题提供了一种新的求解思路。从计算结果来看, 分散搜索算法在合理的时间内获得的解质量较好, 证明了算法对MDVRP求解的有效性。与此同时, 该分散搜索算法框架中各部分的设计思想为采用分散搜索算法求解其他类型车辆路径问题提供了参考。

分层路径搜索算法研究篇4

由于电网故障或设备检修经常会造成一些负荷的停电,其中包括一些重要的负荷,如何为停电的负荷搜索其他可用的供电恢复路径,以快速恢复供电是调度人员工作中经常遇到的问题,即供电路径搜索的问题[1]。因此,有必要针对失电负荷恢复供电路径搜索算法进行研究。

与失电负荷恢复供电研究相关的是配电网故障恢复控制,目前有很多关于配电网故障恢复研究的文献。文献[2]指出地区电网的故障恢复问题是一个多目标、多约束、复杂的优化问题。目前研究故障恢复的方法较多,人工智能技术得到了广泛关注,如专家系统[3,4]、遗传算法[5,6,7,8]、蚁群算法[9]、Petri网[10]、多代理系统[11,12]和差分进化算法[13,14]等。然而上述方法针对特定网络结构分析各有其特点,但不能有效适应地区电网故障在线快速恢复,难以为调度员提供实时、合理的故障恢复控制策略。文献[1]提出电气岛划分的概念,通过拓扑分析将电网分解为若干电气岛,利用“电气岛+边界条件”的概念搜索失电孤岛的供电路径,基于树搜索法中的宽度优先搜索法进行分层搜索。但对于环形网络,这种搜索方法容易漏掉潜在的供电路径;而且由于是从失电孤岛出发去搜索带电岛,这样搜索到的供电路径顺序不符合调度操作规程,即送电时应从电源侧逐级向负荷侧闭合开关。为解决这一问题,文献[1]对电气岛增加了两个新的属性,来记录由带电岛返回失电孤岛的路径,但这样处理增加了内存开销,不利于程序处理的简洁与快速。电气岛划分的概念可以避免在为失电孤岛寻找电源时大量搜索节点链接支路,而是采用直接搜索对侧电气岛的带电性质,因而大大提高了搜索速度。为此针对失电孤岛供电路径搜索算法的研究还有进一步的发展空间。

本文在文献[1]的基础上,受因特网路由选择协议的启发,利用电气岛之间的边界联系,提出一种基于距离向量的供电路径搜索算法。通过建立各个电气岛之间的路由表,将失电孤岛的供电路径搜索问题转换为路由表更新问题,利用各个电气岛最终的路由表项目便可以直观、快速地找到失电孤岛的最短供电路径,并且供电路径的顺序满足调度操作规程。

1 距离向量算法

在信息通信领域,路由器作为网络拓扑中的一种中间结点,在推动计算机网络互联方面扮演了重要角色。路由选择算法分为交互协议和本地计算,其本质是在交互协议的基础上,通过选择适当的标准和有效的选择策略进行本地计算,最终获得最优路由。路由选择定义为把消息从信息源经过网络传送到目的地的行为,主要进行协议交互和本地计算两个基本动作。其中协议交互主要完成网络中距离向量、路径向量和链路状态的查找和传送;本地计算则是根据协议交互获得的距离向量、路径向量和链路状态进行路由表的更新处理,确定数据发送的最优路径[15]。

路由选择协议中的内部网关协议RIP(routing information protocol)是一种基于距离向量的分布式路由选择协议,根据RIP,网络中每一个路由器都要维护从它本身到达其他任意一个目标网络的路由信息。定义路由器到达直接相连的网络的距离为1;定义路由器到达非直接相连的网络的距离为路径上所经过的路由器数加1。RIP中的“距离”也被称为“跳数”(hop count),把信息的传递比作在路由器之间的跳跃,规定每经过一个路由器,跳数就加1。这里的“距离”实际上指的是“最短距离”。RIP中将从源头到达目的地所经过的路由器数目最少的路由定义为最优路由,即跳数最少。

更新路由表时,每个路由器只与相邻的路由器进行协议交互,也就是交换各自的路由信息,交换的路由信息是本路由器当前所知道的所有路由信息[16]。初始化的路由器仅仅知道与其直接相连的网络的距离,将这个距离定义为1。在此之后,每一个路由器只和数目有限的相邻的路由器进行协议交互,并更新各自的路由表项目。经过若干次的更新之后,网络中的每一个路由器最终都会知道从它本身到达本网络中任意一个网络的最短距离和下一跳的路由器地址。RIP的收敛过程较快,即在自治系统中所有结点都得到正确的路由选择信息的过程。RIP令互联网中的所有路由器都与自己的相邻路由器不断交换路由信息,并不断更新其路由表,使得从每一个路由器到每一个目的网络的路由都是最短的。虽然所有的路由器最终都拥有了整个自治系统的全局路由信息,但由于每一个路由器的位置不同,它们的路由表自然也不同。本文按照该协议的思路,提出一种基于距离向量的失电孤岛搜索算法。

2 供电路径搜索

根据文献[17-20]中的拓扑分析方法,相互连接的无阻抗设备汇聚成一个等值节点,通过等值节点相连的有阻抗设备汇聚成一个电气岛。电气岛内部设备彼此连通,即内部各处带电状态一致;电气岛之间彼此不连通。当系统发生负荷失电时,利用拓扑分析程序,将电网划分为若干彼此不连通的电气岛,通过判断岛内设备带电状态,将全部电气岛分为带电岛和不带电岛两大类。根据电气岛划分规则可见,带电岛内部有电源,可作为失电负荷恢复供电的电源。对于不带电岛,有3 种情况:第1 种是故障岛,这种电气岛由于岛内设备故障或检修致使设备不可用;第2种是无源岛,这种电气岛内既无电源又无失电负荷,但其岛内设备正常,可以通过投入运行来为失电负荷供电,如备用设备可划归并入这种电气岛;第3种是失电孤岛,这种岛内无电源,但有失电负荷,需要为其恢复供电。某地区电网经过拓扑分析之后形成的电气岛之间的联系图如图1所示。

定义电气岛边界为不同电气岛之间呈断开状态的无阻抗设备,相当于电气岛间的备用通路,边界一经操作合上,两电气岛即合并形成同一个电气岛。需要说明的是,并不是呈断开状态的无阻抗设备就是边界,只有两端是不同电气岛的无阻抗设备才是边界。

为了说明本文的搜索算法,将故障岛之外的每个电气岛看成一个路由器,各自有一张初始路由表,表示该电气岛与相邻电气岛之间的连接关系,然后根据距离向量算法进行路由表更新,最终获得所有电气岛的全网路由表,进而从中选出失电孤岛的供电路径。路由表结构分为目标岛、距离和路径,以孤岛1的路由表为例,路由表信息如表1所示。

路由表中第1行表示:失电孤岛1 至带电岛2距离为1的路径A;路由表中第2 行表示,失电孤岛1至无源岛3距离为1的路径C。

2.1 初始路由表形成规则

电气岛的初始路由表表示该电气岛与相邻电气岛之间的联系,初始路由表的形成可以根据电气岛边界来确定。依次处理电气岛的边界,按照路由表的结构形成初始路由表的项目。在处理边界的过程中需要注意,若一个电气岛仅和故障岛相连,或者一个电气岛所有的边界只和故障岛相连,则该岛不会在恢复路径中体现,于是将该岛排除在更新列表之外,更新列表中的所有电气岛均要进行下一步路由表更新处理。将所有除故障岛以外的电气岛处理完毕后,各个电气岛的初始路由表也就最终形成。

初始路由表的具体形成流程如图2所示。

2.2 路由表更新规则

路由表的更新处理是为了获取每个电气岛到网络中任意一个电气岛的最短路径,当然从中可以获取失电孤岛到达各个带电岛的最短路径,即为失电孤岛搜索若干条恢复供电的最短路径。更新过程中,每一个电气岛只和数目有限的相邻电气岛交换并更新路由信息。当电气岛获取到相邻电气岛的路由表信息后,根据距离向量算法,在原来的距离上加1,路径之前加上相应的边界。若本电气岛的路由表中没有目标岛,会将新的目标岛加入本路由表项目中;若目标岛在本岛路由表中,则判断距离是否更短,如果比本岛路由表项目中的距离更短,则更新距离和相应的路径,如果相等则把该条路由信息加入路由表,原路由信息不变,否则返回处理下一条路由信息。经过若干次更新后,所有的电气岛最终都会知道到达本电网系统中任何一个电气岛的最短距离和相应的最短路径。

路由表更新的具体流程如图3所示。所有电气岛路由表更新结束后,失电孤岛的路径就可以直接从孤岛路由表中查找,查找方法为:在孤岛路由表项目中查找目标岛为带电岛的路由表项目,其路径即为该失电孤岛的供电路径。在调度操作规程中规定,送电时从电源侧逐级向负荷侧闭合开关,则可以通过从带电岛的路由表中查找失电孤岛,方法同上。然后再根据约束潮流模型针对所有供电路径进行筛选,并计算网损,根据网损和操作步骤进行恢复方案排序,为调度员恢复操作提供辅助决策功能。

针对配电网中多为树状的结构,部分会采用“手拉手”多电源的方式。本文算法基于对网络进行拓扑分析结果进行处理,经过网络拓扑分析,无阻抗设备汇聚为等值节点,由等值节点连接的有阻抗设备汇聚为一个电气岛,拓扑分析方法不仅适用于链式网络和环网,而且对于“手拉手”多电源供电方式的环网同样适用,避免了在为失电孤岛寻找电源时大量搜索节点链接支路,然后根据本文搜索算法进行处理。如果和分布式电源(DG)带电源孤岛电源之间多电源连接,存在不同电源之间的联系,则必须要考虑同期,本文方法在给出的恢复方案中检测到多电源连接时,会生成同期检查报告提示调度员。本文的搜索算法给出的是恢复策略,具体实现由现场操作人员在操作时进行同期检查。

3 恢复方案校验

针对搜索得到的失电孤岛供电方案,首先进行校验排序,每个负荷属性都有对应的等级和大小。等级较高的负荷对应的恢复方案优先校验,相同等级的负荷按其负荷大小进行排序校验。之后依次检验岛内功率平衡和最优潮流。

3.1 电源配置校验

边界合上后会出现电气岛合并,此时无需再重新对全网进行拓扑分析,而是进行动态拓扑分析,即直接修改恢复方案中所涉及的电气岛内设备属性。对新形成的电气岛首先进行电源配置校验,即有功功率配置和无功问题。按式(1)和式(2)进行校验,对恢复方案进行初筛,并生成相应问题报告。

式中:PGmax为岛内有功电源容量;QGmax为岛内无功电源总容量;PD为岛内有功负荷;QD为岛内无功负荷;K1为有功平衡可靠系数;K2为无功平衡可靠系数。

对满足功率配置要求的恢复方案再进行最优潮流计算,校验其电压质量和线路传输容量是否满足规定要求。不满足的不再进行最优潮流校验。

3.2 最优潮流校验

由于常规的潮流计算只是完成某一种具体运行方式下的计算功能,并不能有效验证供电方案是否合理,因此采用最优潮流验证方案的可行性。一种供电方案可理解为一种网络拓扑结构,在给定机组出力约束和负荷条件下,利用最优潮流可以验证某一种供电方案是否满足设备安全运行,这是常规潮流计算无法达到的功能。

本文以系统网损最小为目标函数,所采用的最优潮流数学模型如下所示:

式中:nbr为支路数;SB为系统所有节点集合;SG为发电机节点集合;SC为无功补偿节点集合;SL为支路集合;Gij和Bij为节点导纳矩阵中的元素,Yij=Gij+Bij;θij为节点i,j之间的相角差;Pi和Qi分别为节点有功和无功注入;PGi,PmaxGi,PminGi分别为发电机有功出力及其上、下限;QGi,QmaxGi,QminGi分别为发电机无功出力及其上、下限;QCi,QmaxCi,QminCi分别为无功补偿装置出力及其容量限制;Pl和Pmaxl分别为支路有功功率及其传输上限;Vi,Vmaxi,Vmini分别为节点电压及其上、下限。

内点法在收敛性、计算速度等方面具有无可替代的优势,已广泛应用于研究各种大规模、复杂的线性规划问题,以及各种二次规划和非线性规划问题。原对偶内点法是按照目标函数的导数信息确定搜索方向的,因此收敛速度较快。该算法较为成熟,应用广泛,解析过程清晰,结果的可信度高,并且这种算法对初始点的选择不敏感,可以直接采用非内点来启动算法。原对偶内点法虽然其方法本身需要大量的求导、求逆运算,但是采用导纳稀疏阵进行存储,对计算机的存储量要求降低,可以大大提高程序运行的效率。考虑原对偶内点法所具有的以上特点,本文在计算最优潮流问题上选择原对偶内点法。

其基本思想是:引入松弛变量将函数不等式约束转化为等式约束及变量不等式约束,用拉格朗日乘子法处理等式约束条件,用内点障碍函数法及制约步长法处理变量不等式约束条件,导出引入障碍函数后的库恩—图克最优化条件,并用牛顿—拉夫逊法对其进行求解。

4 算例分析

采用IEEE 14节点标准测试系统对本文算法进行验证测试。将线路6-12和线路13-14设置为热备用。本文对IEEE 14节点标准测试系统的可调措施选择为发电机有功、无功出力和无功补偿装置,基准功率为100MVA,其中发电机有功、无功出力数据如表2所示,无功补偿装置所在节点为节点9,最大补偿容量为0.5(标幺值)。表中:Gi为发电机序号;Bus为发电机所在母线号;Pmax和Pmin分别为发电机有功出力上、下限(标幺值);Qmax和Qmin分别为发电机无功出力上、下限(标幺值)。

在线路6-13故障情况下进行拓扑分析,得到如图4所示的电气岛联系图。

采用本文算法,故障岛不会出现在恢复方案,所以故障岛不在初始化列表内。初始化后各电气岛路由表如表3所示。

所有电气岛经过一次路由表更新,便可以得到各个电气岛最终的路由表信息,可见距离向量算法收敛较快,如表4所示。

由电气岛最终路由表可以得到失电孤岛4的供电方案由两个:方案1,由带电岛1经过开关A和D获得供电;方案2,由带电岛1经过开关C和F获得供电。而采用深度优先树形搜索,如果先从失电孤岛1经无源岛2搜索,则搜索到带电岛1停止,带电岛1标记为已处理,之后在经由无源岛3搜索时不会再搜索带电岛1,这样就漏掉了可能的供电路径CF,反之亦然。

之后分别对两种供电方案进行最优潮流验证,采用MATLAB编程,平均值启动,最大迭代次数为50,结果用标幺值表示,如表5所示。

根据最优潮流结果,选择方案2,依次合上开关C和开关F,由备用线路6-12向负荷节点12和13进行供电。

5 结语

本文受因特网路由选择协议算法的启发,提出一种基于距离向量的失电孤岛供电路径搜索算法。该算法与其他基于图论的搜索算法不同,更侧重于各电气岛之间的联系,通过路由表的更新,找到失电孤岛恢复供电的多种可能路径。

经IEEE 14节点标准测试系统验证分析,该方法高效可行,编程简单,而且针对环形结构的网络收敛速度更快。在路由表的更新过程中即可判断各个路径的长短,供电路径与树形搜索相比更加完整,可直接得到符合调度规程的供电方案,缩短了恢复供电时间。该算法可以应用在目前的操作票系统上,为调度员执行事故或检修后恢复操作提供辅助决策功能。

摘要：由于电网故障或设备检修造成负荷失电,为失电负荷寻找供电路径成为目前许多电网分析软件的必备功能。通过拓扑分析程序将电网划分为若干电气岛,传统的根据树搜索法的孤岛恢复供电路径搜索算法,在路径的搜索上存在不足。文中受因特网路由选择协议算法的启发,将各类电气岛看成路由器,提出一种基于距离向量的搜索算法,通过对各电气岛初始路由表的形成和对路由表的更新处理,最终获得电气岛的全网路由表,通过该路由表可以得到所有可能并且符合调度规程的失电孤岛供电路径。利用内点法最优潮流对搜索得到的供电方案进行可行性验证。以IEEE 14节点标准测试系统为例,验证了该算法的可行性。

分层路径搜索算法研究篇5

在应用传统的导向局部搜索算法解决VRPSDP问题时由于采用的惩罚策略在迭代过程中并无变动,就可能导致一些必然经过的长路径被作为惩罚边而被惩罚,从而导致了算法在逃离局部最优时经历了大量的无用计算。因此提出一种新的变惩罚函数的导向局部搜索算法 ( improved guided local search) ,采用多惩罚函数从而降低了单一惩罚函数惩罚有效边的可能性,扩大了邻域搜索范围。同时通过反复搜索来减少初始解对算法的影响。最后通过对28个算例的求解,表明了该算法的有效性和稳定性,为求解装卸一体化车辆路径问题提供了新的求解思路。

1问题描述

1.1问题描述

装卸一体化车辆路径问题可以定义为: 设定有向带权图G = ( V,A,C) ,其中V = { i | i = 0,1,…, n} 是节点集合,节点0为出发地节点,( 1 ~ n) 为客户地节点; A = { i,j | i,j ∈ V} 表示弧集,C = { cij| ; ( i,j) ∈ A} 为权重矩阵,cij表示节点i到节点j的距离。设定每个客户节点i都有卸货需求di和装货需求pi,运输车辆的最大载货量为Q。VRPSDP则可以描述为: 1每辆车都从0点出发,服务若干客户后返回0点,形成一个解S; 2每个客户都仅被服务一次,而且只能由某一车辆提供服务; 3每个车辆的载重量都不超过Q; 4所有客户的装卸货需求都不超过Q; 5总的运输距离f( S) 最小。

1.2解的可行性定义

对于VRPSDP的解S = { rj| j = 1,…,k} ,其中rj= { i | i ∈[1,n]} ,表示车辆j的路径,k为解中最大的车辆数。对于解S是强可行解的充分必要条件是: 解S中的任意车辆路径rj需要满足约束: 运输车辆在访问过rj上所有客户后载重都不超过Q。对于解 S,不满足约束条件,则解S是一个弱可行解,否则解S是一个强可行解。

2多邻域导向局部搜索算法

2.1导向局部搜索算法概述

导向局部搜索算法( guided local search,GLS) 是由Chris Voudouris等在1995年提出的,具有通用性好、结构紧凑的特点,已经被多次应用于解决经典的TSP问题和其他NP组合优化问题。其基本原理是保持搜索过程中的解结构和邻域结构不变,而将目标函数进行动态修改,从而使得当前的局部极值不再具有局部最优性。GLS采用的目标函数修改机制以解特征为基础,解特征可用于区分不同解的若干性质或特点,在VRP问题中通常采用弧的长度作为解特征。GLS主要通过惩罚策略惩罚近似最优解中的某些解特征来实现局部搜索。而惩罚策略则主要包括初始成本( 两地点之间的间距) 和惩罚次数( 即某特征被惩罚的次数) 。

这里将惩罚特征定义为m,对一个解S其特征指标函数定义为Im( S) ,惩罚效用函数定义为Um( S) ,目标函数定义为h( S) 。

特征指标函数Im( S) 表示解S是否具有惩罚特征m:

如果出现该特征则该特征被惩罚一次,这里使用惩罚系数Pm进行计数。同时为了避免过度惩罚某些重要特征,需要对该特征的惩罚次数进行有效评价,因此需要惩罚效用函数Um( S)[9]

式( 2) 中cm通常为惩罚特征的弧长度。

从解S中选择惩罚效用函数值最大的特征进行惩罚,惩罚后的目标函数h( S) 为

式( 3) 中g( S) 表示解S的原始目标函数值,这里为总的弧长。λ 为规范化系数,通常取0. 01 ~ 0. 10[10]。通过惩罚具有惩罚特征的解,保证了较好特征的可行解进行邻域搜索,通过目标函数的不断修改,使得当前局部极值不再具有局部最优性,从而不断迭代找到最优解。

2.2惩罚效用函数设计

由于传统的惩罚效用函数Um( S) 寻找的是解中的最长边,以图1路径所示为例

图1中虚线边为最长边,也同时为惩罚边,但实际虚线边1—2明显为必经的有效边,因此文献[8] 提出了平均的惩罚效用函数

式( 4) 中cavg为和惩罚特征边m邻近的所有边的平均弧长度。以图1路径为例,此时的惩罚边则变为4-5。

但是在最优解( 1,2,4,3,5,6) 中,就式( 4) 得到的惩罚边而言,边2-3应该优先被惩罚,因此这里提出新的惩罚效用函数

式( 5) 中i和j分别为和惩罚特征边m的起点和终点,c( i,j)表示边m的弧长度,表示存在有距离i比j点更近的点k ,选择解中的第一条满足式( 5) 的边为惩罚边,以图1路径为例,此时的惩罚边则变为2—3。di为该惩罚边的控制参数: 当在连续无改进迭代次数内时,di= 1; 当到达连续无改进迭代次数且陷入局部最优解时di= 0。此时寻找第二条惩罚边,即图2所示的边45。

2.3变换惩罚策略

这里提出变换惩罚效用的惩罚策略: 当连续无改进迭代次数到达上限时仍找不到一个更好解,则从当前解出发,变换惩罚效用函数,重新开始局部搜索,看能否找到更好解,如果找到更好解,则从这个解出发,采用第一个惩罚效用函数重新开始搜索。

2.4改进的导向局部搜索算法

多邻域导向局部搜索算法步骤如下。

初始化: 客户规模n,各客户地理坐标( xi,yi) , 客户需求di和装货需求pi,车辆运输容量限制Q,连续无改进迭代次数d = 0,最大连续无改进迭代次数dmax。

输出: 车辆行驶路径

STEP1: 设置相关参数并构造初始可行解S0;

STEP2: 从初始解S0出发在邻域内开始局部搜索过程,当解陷入局部最优时产生局部最优解S0best;

STEP3: 选择惩罚效用函数,对局部最优解按照惩罚效用函数公式进行计算,将解中能够最大化惩罚效用函数Um( S0best) 的解特征的罚系数Pm+ 1,然后对每个解得目标函数按照式( 3) 进行修改;

STEP4: 选择目标函数最优的解Sbest0作为当前局部最优解

STEP5: 从当前局部最优解Sbestnow出发,重复STEP2 ~ STEP4的过程,求得当前局部最优解Sbest1,如果且连续无改进迭代次数d = 1,否则d = d + 1;

STEP6: 如果算法到达最大连续无改进迭代次数d = dmax,则变换惩罚策略,从出发重复STEP2 ~ STEP5的过程;

STEP7: 如果算法变换完所有惩罚策略且到达最大连续无改进迭代次数时,算法终止。

下面对算法的构造初始可行解和局部搜索内容进行详细描述。

2.5构造初始可行解

这里采用最近邻法构造初始可行解,步骤如下:

STEP1: 从未被选择的客户节点集合中选择距离出发节点最近的节点,开始一条新路径;

STEP2: 从未被选择的客户节点集合选择距离路径上最后一个节点最近的节点;

STEP3: 如果加入节点后的路径满足强可行解的约束条件,则返回STEP2,否则返回STEP1。

这样构造的初始可行解同时也是一个强可行解。

2.6搜索局部最优解

将从节2. 4中获得的强可行解作为初始解,选择一种邻域结构进行局部搜索,当到达迭代次数上限或者连续无改进迭代次数到达上限时结束搜索。这里选择2-opt邻域结构:

2-opt: 2-opt是对于解S中的同一路径上位于li和lj( li< lj) 上的两个客户,将li+ 1位置上的节点与位于lj上的节点交换位置,并将li+ 1到lj之间的节点按逆序排列,从而产生邻域解。

3实验结果及分析

3.1IGLS算法在VRP问题上的有效性验证

为了测试改进的导向局部搜索算法在VRP上的有效性,在Christofides等人提出的14个benchmark问题[9]上进行仿真验证,并和传统的GLS方法的求解结果进行比较。Christofides算例中的客户数为50 ~ 199,其中问题C1 ~ C10的客户位置为随机分布,问题C11 ~ C14的客户位置为聚集分布。算法采用c#在 . net平台下实现,运行环境为win2003 64x,CPU为G3220 3. 0 GHz,内存为2 G,参数设置为算法总体最大连续无改进迭代次数max _ noimprove = 200,惩罚策略3中的最大连续无改进迭代次数max_no3 = 100。传统GLS的最大迭代次数为600。下表描述了两种算法计算结果的比较( L为最优路径长度,t为计算消耗时间,单位为min) , 仿真比较结果如表1所示。

通过对表1的14个测试用例进行计算,其中的已知最好解用黑体标出。从表1的仿真结果可以看出,本文提出的改进的导向局部搜索算法在Christofides算例上均得到了比传统GLS算法更优的解, 同时在C4、C5、C10问题上得到了已知最好解,说明本文的改进方法在VRP问题上是有效的。由于本文算法采用了三种惩罚策略,在计算时间比传统GLS方法较多是正常的。在算法求得的迭代变化方面,以C10为例,记录每次迭代的当前最优值,IGLS和GLS的比较如图4所示。

从图4中的迭代结果可以清楚地看出每次更换惩罚策略即相对与扩展了搜索的邻域,避免算法陷入局部最优,从而获得更好的结果。

3.2IGLS算法在VRPSDP问题上的有效性和稳定性验证

为了测试改进的导向局部搜索算法在VRPSDP上的有效性,这里采用在Salhi和Nagy算例[11]上进行仿真并和Zachariadis提出的利用禁忌搜索结合Guided Local Search的混合算法TS_GLS[8]的结果进行比较,Salhi和Nagy算例的问题规模在[50,199] 之间,每个问题包含两个算例,其中CMTx X为在原有benchmark的算例CMTx基础上增加了装卸货需求的算例,CMTx Y为和CMTx X的装卸货需求相反的算例。CMTx的问题规模分别为 ( 50,75,100, 100,120,150,199) ,CMTx X和CMTx Y的规模相同。参数设置同节3. 1中的参数设置。由于算法的随机性,因此每次的计算结果可能不同,记录每个算例运行20次后的最优解Lmin、最差解Lmax、标准差sd和平均时间,并和TS_GLS算法的最优解进行比较。

通过TS_GLS算法和IGLS算法的计算结果比较可以看出: 在平均路径长度方面,IGLS算法较TS_GLS算法减少了1. 81,在最优解的质量上,IGLS算法较TS_GLS算法最大提高了2. 2% ,最小提高了0. 09% ,说明本文算法在解决VRPSDP上是有效的。 IGLS的运行时间受迭代次数的影响较大,在Salhi和Nagy算例上平均运行时间为4 min,时间上是可以接受的。在算法的稳定性方面,尽管在CMT12算例上的标准差偏大,但总体的平均方差5. 12仍然在可接受的范围内,说明在大多数情况下都能得到一个问题的接近最优解,说明本文算法是具有稳定性的。

4结论

卸装一体化车辆路径问题是一个有着实际应用需要且广泛存在的问题,针对这一问题本文设计了一种基于变惩罚函数的导向局部搜素算法,使用多种惩罚策略来扩大导向局部搜素算法的搜索能力。通过对Christofides算例和Salhi和Nagy算例共28个算例的求解,Christofides算例的仿真结果验证了本文提出的改进导向局部搜素算法在解决VRP问题时是优于传统导向局部搜素算法的,Salhi和Nagy算例的仿真结果验证了本文算法在解决VRPSDP问题时的有效性和稳定性,为解决卸装一体化车辆路径问题提供了新的解决思路和方法。但就运算时间而言,本文算法耗时较多,如何改进并提高算法的搜索效率是下一步需要研究的内容。

摘要：针对卸装一体化车辆路径问题,提出一种变惩罚函数的导向局部搜索算法(IGLS)。在传统导向局部搜索算法的基础上加入了新的惩罚效用函数,当传统导向局部搜索算法陷入局部最优时,变换惩罚策略后重新搜索,从而扩展搜索的邻域。通过和传统导向局部搜索算法以及TS_GLS算法在不同算例上的仿真结果比较,验证了所提算法在解决卸装一体化车辆路径问题上的有效性和稳定性。

关键词：卸装一体化车辆路径问题,变惩罚函数,导向局部搜索,惩罚策略

参考文献

[1] Cordeau J F,Gendreau M,Hertz A,et al.New heuristics for the vehicle routing problem.Springer US,2005

[2] Gajpal Y,Abad P.An ant colony system(ACS)for vehicle routing problem with simultaneous delivery and pickup.Computers&Operations Research,2009;36(12):3215—3223

[3] Ai T J,Kachitvichyanukul V.A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery.Computers&Operations Research,2009;36(5):1693—1702

[4] Tasan A S,Gen M.A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries.Computers&Industrial Engineering,2012;62(3):755—761

[5] Alfredo Tang MontanéF,Galvao R D.A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service.Computers&Operations Research,2006;33(3):595 —619

[6] Ganesh K,Narendran T T.CLOVES:a cluster-and-search heuristic to solve the vehicle routing problem with delivery and pick-up.European Journal of Operational Research,2007;178(3):699—717

[7] Crispim J,Brando J.Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls.Journal of the Operational Research Society,2005;56(11):1296—1302

[8] Zachariadis E E,Tarantilis C D,Kiranoudis C T.A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service.Expert Systems with Applications,2009;36 (2):1070—1081

[9] Christofides N,Mingozzi A,Toth P.State‐space relaxation procedures for the computation of bounds to routing problems.Networks,1981;11(2):145—164

[10] Voudouris C,Tsang E P K,Alsheddy A.Guided Local Search.Handbook of Metaheuristics.Springer US,2010:321—361

【分层路径搜索算法研究】推荐阅读：

多路径算法06-09