一种WSRNs中机器人替换失效传感器的路径优化方法

本发明涉及无线传感器和机器人网络(WSRNs)中机器人修复传感器领域，特别是一种获得WSRNs中利用机器人从出发所携带的传感器或在行进中拾取的冗余传感器替换区域中无效传感器的最优路径的确定方法。

网络的完全覆盖对于完成已发布的传感任务非常重要，无效传感器必须及时修复或更换。利用机器人灵活和不受约束的运动特点，在其帮助下更换无效传感器是有效的。利用机器人解决WSRNs中的传感器替换问题的目标在于最小化机器人访问传感器节点的路径成本，即路径最短。WSRNs中部署了大量传感器，当机器人在整个环境中移动时，到一条最佳轨迹是一个十分复杂的问题。文献[Falcon R，Li X，Nayak A，et al.The one-commoditytraveling salesman problem with selective pickup and delivery：An ant colonyapproach[C]//IEEE Congress on Evolutionary Computation，CEC 2010，2010：1-8]将该问题建模为具有选择性取货和交货的单商品旅行推销员问题(1-TSP-SELPD)，采用蚁算法求解，仅适用于小规模传感器分布的情况。由于其算法本身的限制，随着问题规模的增加，算法容易陷入局部最优解，故该方法不能处理大规模分布的传感器替换问题。而本发明的动态构建算法更贴近1-TSP-SELPD问题的特点，容易搜索到全局最优方案，可有效地实现大规模传感器分布情况下机器人的路径规划。在现实问题中，问题往往是大规模的，本发明对此具有更好的应用适应性。

针对“无线传感器与机器人网络(WSRNs)”区域内利用冗余传感器或从携带的传感器替换无效传感器问题，本发明提供了一种获得机器人最优运行路径的方法，以使得机器人更高效地完成任务。发明提供了一个两阶段的解决方法：第一阶段，基于既有LKH(Lin-Kernighan heuristic)算法获得一条连接所有待替换的传感器(D点)的初始最短路径；第二阶段，利用发明的动态构建算法构建出一条连接所有D点和部分P点(被拾取的冗余传感器)的最优路径，选择路径上的冗余传感器，并将其携带至D点以逐一替换失效传感器。其目的在于，克服现有技术难以处理大规模传感器分布问题的不足，以迅速地获得更大规模的传感器分布条件下的机器人的最优路径。

所述初始最短路径是指通过经典的LKH算法得到的最短LKH路径。LKH算法以随机化方式产生的初始路径为基础，重复执行交换操作，将一种路径转换为另一种路径，直至交换不出改善的路径，此当前路径即为最短LKH路径。

所述机器人最优路径是指在此不完整的初始最短路径的基础上通过发明的动态构建算法将区域内有利的冗余传感器节点(P点)插入该路径，多次迭代后得到的路径成本最小的解。插入P点的具体实现包括两个过程：

(1)构建候选边集，在此集合中以赌法随机地选择一条边；

(2)在此边附近随机地选择一个P点。

所述具有选择性取货和交货的单商品旅行推销员问题(1-TSP-SELPD)模型为：

本方法用一个完全图G＝(V，E)表示传感器网络，其中V＝{v0，v1，...，vn}是顶点集，E＝{eij}是边集，eij是传感器顶点vi和vj之间的边，其中eij的成本等于其欧几里德长度d(eij)。V中的元素包含取货节点和交货节点，qi是节点属性(1代表取货节点，-1代表交货节点)。而且，v0是，且q0＝0。每个移动机器人最多可以携带Qmax个传感器(即容量为Qmax)，因此机器人的载重Q在经过eij时必须满足0≤Q≤Qmax。算法的目标函数是即到一条连接所有D点及部分P点的满足以下要求的最小成本且可行的路径

(1)机器人从开始并在结束；

(2)交货节点的入度与出度相等，为1，取货节点的入度与出度相等，小于或等于1；

(3)满足所有交货节点的需求；

(4)对于每次访问节点，机器人载重不超过其最大载重(容量)。

具有选择性取货和交货的单商品旅行推销员问题(1-TSP-SELPD)用以下数学公式表示：

xij∈{0，1} (6)

其中，VP为取货节点集；VD为交货节点集；cij为边eij的成本，大于零；为边eij的载重，如果边eij不属于路径，为0；如果边eij属于路径，xij为1，否则为0。等式1陈述了1-TSP-SELPD的目的，其将移动机器人的总路径成本最小化；约束2确保每个取货节点最多被访问一次；约束条件3要求每个交货节点和必须只被访问一次；约束4让每条边的载重足以满足需求并且不超过机器人的容量；约束5保证消除节点间的子路径。

所述的基于动态构建算法的路径优化方法，具体包括以下步骤：

步骤1：利用LKH算法生成包括所有D点的最短路径，用集合表示，其中Nd是所有D点的个数。此集合中的边是有序的，从边l1到边依次排列，此排列的方向是路径的前进方向。

步骤2：可行边集的动态构建。以LKH所构建的路径作为基础，利用动态构建算法沿着LKH路径不断地选边，插入P点，将这些点顺序地连接到所形成的路径，就是一个可行解。图2示例地展示了插入P点形成新路径的基本过程：D1，D2，D3，D4是待替换的D点，在边D2D3的附近(某个范围内)选择一点P1，删除D2D3边后，形成了路径D1D2P1D3D4；进而，在边P1D3的附近选择一点P2，删除P1D3边后，形成路径D1D2P1P2D3D4.

具体包括以下过程：

将LKH算法获得的LKH路径的各边依次纳入LKH集合，记为SLKH，集合中的元素称为LKH边。从该集合中取出的元素用于构建解的候选边集。候选边集是指这个集合中的边可以被选择用以构建椭圆点集(即以该边为椭圆的长轴，椭圆内的点构成的点的集合)，令当前路径的候选边集合为SCE＝{e1，e2，...，ei+K}，其中i是指已经从SLKH中取出的边的数量，即已经添加到SCE中的LKH路径上的前i条边，K是已插入到SCE中的P点的数量(添加一个节点即添加了一条边，K＝{1，2，.....，ND-q0}，其中ND是所有D点的数量，q0是从出发时携带的荷载数量)。SLKH集合中的边li(i＝1，2，...，ND)移入SCE后称为L-edge(如图1中的D2D3)；以L-edge为底边插入P点之后所形成的新的路径边，称为E-edge(如图1中的D2P1，P1D3)。这两类边的远离的那个端点的叫做该边的尾点(如图1中的D3是D2D3，P1D3和P2D3的尾点)。L-edge的尾点是D点，而E-edge的尾点则不一定是D点。

a)设定候选边集SCE的约束条件

当前路径上存在一个待替换的D点。SCE所对应的当前路径上的最后一边的尾点始终保留一个待替换的D点，即SCE中最后一个元素(边)的尾点是一个待替换的D点。因为每捡起的一个P点，即意味着一个D点被替换，因此，须使得SCE对应的路径上至少存在一个待替换的D点，以便将搜索到的P点上的荷载可替换此D点。

满足边的荷载约束。机器人不能携带超过其容量的荷载。令loadi来表示机器人经过边i时所携带的荷载数。当机器人在P点捡取一个荷载后，其随后各边的loadi将增加1。不断地捡取荷载必使得机器人经过某一条边时达到容量，因此，必须设定此容量限制。

b)构建候选边集SCE

SCE集合的初始化是构建集合SCE的第一步。拓展、生长和缩减边的三种操作被用来使这个候选边集合发生变化，以不断获取更多新的P点。

c)在候选边集SCE中选择边e

用赌法选择候选边集中的一边，作为构建椭圆点集的椭圆长轴。算法设置了参数M来控制边的长度对选择结果的影响，参数M是将候选边集的每个边的长度设置为长度的M次方。

d)在该边e上构建椭圆点集，并在构建的椭圆域中选择P点

以该边为椭圆的长轴建立椭圆区域，采用随机的方式在椭圆域中获得一个P点。选择P点的基本原则是尽可能地减少新路径的长度。椭圆区域的大小通过改变椭圆的短轴长度来调整。图3表示了椭圆形区域。

椭圆是在局部坐标系统UO′V下构造的，交货节点D点和取货节点P点的位置是在全局坐标系XOY下确定的，需将椭圆方程从局部坐标系转换到全局坐标系，以判断取货节点P(x，y)是否在椭圆内。若点P满足等式(7)，则表示该点在椭圆区域内。

b＝a·R (9)

式中a，b分别为椭圆的长半轴和短半轴，R是二者的比值，α是坐标系UO′V旋转到全局坐标系XOY的角度，(S，T)是边e的中点(坐标系UOW的原心)在坐标系XOY的坐标。

对于椭圆内存在不止一个P点的情况，采用随机策略选择一个P点。对于在椭圆区域内没有P点的情况，则重新选择另外一边e，再进行选点操作。如果一定次数(通常取10次)的选边之后，仍然选不到点就直接插入等式(7)所计算的Loc(x，y)值中最小的点P。

步骤3：重复步骤2，直至达到指定迭代次数(根据问题规模，选择实验结果中能达到稳定结果的次数)。其中路径成本最小的可行解即为所求连接所有D点和部分P点的机器人最优路径。

所述步骤2中步骤b)的候选边集SCE的构建过程如下：

(1)SCE集合的初始化

如果没有荷载可以提供，即q0＝0。将LKH路径上的第一条l1边纳入集合SCE，并保留1个D点，以便边l1附近的P点(基于该边所构建的椭圆点集中的点)被捡起来后能替换该D点，如图4。

如果提供荷载，即q0≠0，则先将从携带的荷载就近替换到从开始的LKH路径上的q0个D点。因为此路径本身就是最短路径，也就是将SCE初始的q0个L-edge的尾点由携带的q0个荷载替换。为了获得这q0个尾点，需将q0中排在前面的1+q0条边添加至SCE，此时t＝q0+2。如图5，q0＝2，添加OD1、D1D2至SCE，并用携带的荷载替换D1和D2。

除了添加q0条LKH边用于提供q0个D点以便被这q0个携带的荷载替换外，还考虑到沿这些点构成的路径的附近捡取一个荷载后，尚需存在1个D点作为此捡起的荷载的替换位置。如图5，D1D2被替换后，尚应添加边D2D3至SCE。

图4和图5中，实线表示LKH路径中移入SCE的边，空心圆表示未被替换的D点，实心圆表示已经被替换的D点，O点表示，low，up表示指向当前SCE集合的上下界的指针，t是当前已经移入SCE的SLKH中的最后一边的下一边，叫做LKH当前边，作为下一次准备移入SCE的边。

(2)SCE集合的拓展

替换L-edge的尾点的荷载的来源有两种：①来自于的荷载，由机器人来替换SCE集合的开始的q0个边；②由L-edge和E-edge的拓展后获得的荷载，去替换当前SCE集合的最后一边的尾点。“拓展”是指在L-edge上构建椭圆点集并允许在其中选择P点，由此所选择的P点连接而成的E-edge被增加在SCE中，SCE中任何一个边(L-edge或E-edge)可以被选择以构建椭圆点集，并且该椭圆点集被用于选点。

L-edge和E-edge是在SCE中选择的，具体方法是：首先，按赌法从SCE中选择一边，如图6中的e；然后，基于这条边，构建椭圆点集，在椭圆点集中，按步骤d的方法获得点P。

在E-edge边选点存在比在L-edge边附近选点所形成的路径的总长度更短的可能性。如图7b和7c，基于D2D3拓展出P3而生成D1P1D2P3D3(图7b)和基于P1D2拓展出P2而生成D1P1P2D2D3(图7c)两种情况中，前者的路径长度比后者更长一些。因此，E-edge应当被不断地拓展，即可以继续基于添加的E-edge边构建椭圆点集并选点，如图7c，D1D2D3是原始的LKH路径，在D1D2上拓展得到P1后，在P1D2上继续拓展得到P2。这种不断拓展E-edge的方式，拓宽了P点的搜索范围，增加了解的多样性。通过重复使用这种在不同的E-edge上选P点的方式可连续地获得大量的可行解。其终止条件是，SCE内某边的荷载达到了边的容量。

捡起一个荷载将引起插入点之后的各边荷载数变化。如图6，插入取货节点P点后，loade2＝loade1+1，且e2随后各边loadi＝loadi+1(i＝e2+1，e2+2，.....，up-1)。图6b显示了拾取P点后各边荷载的变化情况(图6中加圈的数字表示loadi)。

机器人不断地捡取与替换传感器，经过各边时，其每条边上的loadi不断变化。然而，任何一边的loadi都不允许超出机器人容量的限制，因此，当达到容量时(loadi＝Qmax)，拓展就停止了。

(3)SCE集合的生长

SCE中最后一边的尾点总是保留了一个待替换的D点，当拓展一次(即获得了一个P点的荷载)后，此孔即被替换了。为了能继续拓展，需在SCE中的终边增加一个待替换点作为补充。所谓“边的生长”就是指在SCE集合的最后一边之后添加SLKH的当前边，其目的在于通过增加新边来提供L-edge的尾点。

如图8b中，q0＝2，在P点处捡起一个荷载后，D3将被替换，此时将SLKH的当前边延伸到集合的下界，即在SCE集合中生长出边D3D4。该边的荷载为：

loadup＝loadup-1-1。

(4)SCE集合的缩减

SCE集合中的各边须满足边荷载容量的约束。如果在任意一个E-edge的椭圆点集中获得一个P点，那么机器人经过此点后的各边时，在这些边上的荷载数均增加，因为这个原因，经过SCE集合中的某一条边k所携带的荷载数loadk将会被累加到容量Qmax。此时，在SCE中的边k及其之前的各边不能再被用于构建椭圆点集。因为一旦以这些边所构建的椭圆点集内的点被捡起，那么，当机器人经过边k时，loadk≥Qmax。结果，边k及其之前的各边从SCE集合被删减，这就是SCE集合的缩减。如图8c中，设Qmax＝3，经过P1D2边的那么，P1D2及其前面的各边被从SCE中去掉。

有益效果

本发明提供了一种基于动态构建算法的路径优化方法，针对“无线传感器与机器人网络(WSRNs)”区域内利用冗余传感器或从携带的传感器替换失效传感器的问题。通过对不同规模问题的算法测试结果分析可知：应用本发明提出的理论和方法能快速高效地到机器人最优路径，算法可避免陷入局部最优，且在大规模问题中能获得较好的路径，该方法有助于高效与经济地完成传感器更换的工作。

①分阶段优化、效率高。分两阶段生成多个机器人路径方案，最终比较得到最优路径。第一阶段采用经典高效的LKH算法生成只包含交货节点的最短路径，第二阶段采用动态构建算法生成最优路径。总的计算时间即使是对于较大规模问题也用时很少(一般不超过10s)，算法得到的最终结果在大规模问题中明显较传统的蚁算法优。

②适用于大规模的WSRNs问题，是一种全局优化搜索方法。所发明的动态构建算法与1-TSP-SELPD问题的特点结合紧密：第一阶段获得D点的TSP最短路径，而第二阶段利用了此最短路径，降低了第二阶段中路径搜索的代价，从而更较有效地避免陷入局部最优。正因为如此，所发明的方法能在大规模问题中表现出优异的性能。

图1为动态构建算法流程图；

图2为插入P点形成新路径图；

图3为椭圆形区域图；

图4为q0＝0时SCE的初始化图；

图5为q0＝2时SCE的初始化图；

图6为SCE的拓展及荷载变化图；

图7为在不同的边拓展形成的路径长度图；

图8为集合的生长及缩减图；

图9 30规模问题下参数M和R值的影响图；

图10 500规模问题下参数M和R值的影响图；

图11三种算法最优值和平均值的比较图。

下面结合附图和实施例对本发明做进一步说明：

一种基于动态构建算法的路径优化方法，针对于“无线传感器和机器人网络(WSRNs)”区域内机器人利用冗余传感器或从携带的传感器替换失效传感器的问题。本发明可获得机器人最优运行路径，以使机器人更高效地完成任务。该发明将该问题建模为具有选择性取货和交货的单商品旅行推销员问题(1-TSP-SELPD)，无线传感器和机器人网络中的失效传感器对应于1-TSP-SELPD问题中的交货节点，即D点；无线传感器和机器人网络中的冗余传感器对应于1-TSP-SELPD问题中的取货节点，即P点。该方法提供一个两阶段的解决方法：第一阶段，利用既有LKH(Lin-Kernighan heuristic)算法获得一条连接所有待替换的失效传感器(D点)的初始最短路径；第二阶段，利用发明的动态构建算法构建出一条连接所有D点和部分P点(被拾取的冗余传感器)的最优路径，选择路径上的冗余传感器，并将其携带至D点以逐一替换失效传感器。

所述初始最短路径是指通过经典的LKH算法得到的最短LKH路径。LKH算法以随机化方式产生的初始路径为基础，重复执行交换操作，将一种路径转换为另一种路径，直至没有交换不出改善的路径，此当前路径即为最短LKH路径。

所述机器人最优路径是指在此不完整的初始最短路径的基础上通过发明的动态构建算法将区域内有利的冗余传感器节点(P点)插入该路径，多次迭代后得到的路径成本最小的解。插入P点的具体实现包括两个过程：

(1)构建候选边集，在此集合中以赌法随机地选择一条边；

(2)在此边附近随机地选择一个P点。

所述具有选择性取货和交货的单商品旅行推销员问题(1-TSP-SELPD)模型为：

本方法用一个完全图G＝(V，E)表示传感器网络，其中V＝{v0，v1，...，vn}是顶点集，E＝{eij}是边集，eij是传感器顶点vi和vj之间的边，其中eij的成本等于其欧几里德长度d(eij)。V中的元素包含取货节点和交货节点，qi是节点属性(1代表取货节点，-1代表交货节点)。而且，v0是，且q0＝0。每个移动机器人最多可以携带Qmax个传感器(即容量为Qmax)，因此机器人的载重Q在经过eij时必须满足0≤Q≤Qmax。算法的目标函数是即到一条满足以下要求的最小成本且可行的路径

(5)机器人从开始并在结束；

(6)交货节点的入度与出度相等，为1，取货节点的入度与出度相等，小于或等于1；

(7)满足所有交货节点的需求；

(8)对于每次访问节点，机器人载重不超过其最大载重(容量)。

具有选择性取货和交货的单商品旅行推销员问题(1-TSP-SELPD)用以下数学公式表示：

xij∈{0，1} (6)

其中，VP为取货节点集；VD为交货节点集；cij为边eij的成本，大于零；为边eij的载重，如果边eij不属于路径，为0；如果边eij属于路径，xij为1，否则为0。等式1陈述了1-TSP-SELPD的目的，其将移动机器人的总路径成本最小化；约束2确保每个取货节点最多被访问一次；约束条件3要求每个交货节点和必须只被访问一次；约束4让每条边的载重足以满址需求并且不超过机器人的容量；约束5保证消除节点间的子路径。

基于动态构建算法的路径优化方法流程图如图1所示；

该算法采用C++编码，所有计算实验均采用2.27GHz的Intel Xeon CPU-E5507和Windows 7下的2GB内存。本方法的基准实例来自文献“Falcon R，Li X，Nayak A，et al.Theone-commodity traveling salesman problem with selective pickup and delivery：An ant colony approach[C]//IEEE Congress on Evolutionary Computation，CEC2010，1-8”，位于(0，0)，该节点的节点属性为q0＝0。

n是每个数据样本中所有传感器(包括)的数量，n-1个传感器的随机2D坐标是在|-500，500|2中生成的。令交货节点和取货节点的比例为1∶3，移动机器人的容量为传感孔总数的四分之一。路径成本xij是节点i和j之间的欧几里德距离。测试根据传感器数量(包括)n和机器人容量Q分成两大类：n∈{20，30，40，50，60}的小规模实例和n∈{100，200，300，400，500}的大规模实例。

步骤1：利用LKH算法生成包括所有D点的最短路径，用集合表示，其中Nd是所有D点的个数。此集合中的边是有序的，从边l1到边依次排列，此排列的方向是路径的前进方向。

步骤2：可行边集的动态构建。以LKH所构建的路径作为基础，利用动态构建算法沿着LKH路径不断地选边，插入P点，将这些点顺序地连接到所形成的路径，就是一个可行解。图2示例地展示了插入P点形成新路径的基本过程：D1，D2，D3，D4是待替换的传感器孔(D点)，在边D2D3的附近(某个范围内)选择一点P1，删除D2D3边后，形成了路径D1D2P1D3D4；进而，在边P1D3的附近选择一点P2，删除P1D3边后，形成路径D1D2P1P2D3D4.

具体包括以下过程：

将LKH算法获得的LKH路径的各边依次纳入LKH集合，记为SLKH，集合中的元素称为LKH边。从该集合中取出的元素用于构建解的候选边集。候选边集是指这个集合中的边可以被选择用以构建椭圆点集(即以该边为椭圆的长轴，椭圆内的点构成的点的集合)，令当前路径的候选边集合为SCE＝{e1，e2，...，ei+K}，其中i是指已经从SLKH中取出的边的数量，即已经添加到SCE中的LKH路径上的前i条边，K是已插入到SCE中的P点的数量(添加一个节点即添加了一条边，K＝{1，2，.....，ND-q0}，其中ND是所有D点的数量，q0是从出发时携带的荷载数量)。SLKH集合中的边li(i＝1，2，...，ND)移入SCE后称为L-edge(如图1中的D2D3)；以L-edge为底边插入P点之后所形成的新的路径边，称为E-edge(如图1中的D2P1，P1D3)。这两类边的远离的那个端点的叫做该边的尾点(如图1中的D3是D2D3，P1D3和P2D3的尾点)。L-edge的尾点是D点，而E-edge的尾点则不一定是D点。

a)设定候选边集SCE的约束条件

当前路径上存在一个待替换的D点。SCE所对应的当前路径上的最后一边的尾点保留一个待替换的D点，即SCE中最后一个元素(边)的尾点是一个待替换的D点。因为每捡起的一个P点，即意味着一个D点被替换，因此，须使得SCE对应的路径上至少存在一个待替换的D点，以便将搜索到的P点上的荷载可替换此D点。

满足边的荷载约束。机器人不能携带超过其容量的荷载。令loadi来表示机器人经过边i时所携带的荷载数。当机器人在P点捡取一个荷载后，其随后各边的loadi将增加1。不断地捡取荷载必使得机器人经过某一条边时达到容量，因此，必须设定此容量限制。

b)构建候选边集SCE

SCE集合的初始化是构建集合SCE的第一步。拓展、生长和缩减边的三种操作被用来使这个候选边集合发生变化，以不断获取更多新的P点。

c)在候选边集SCE中选择边e

用赌法选择候选边集中的一边，作为构建椭圆点集的椭圆长轴。算法设置了参数M来控制边的长度对选择结果的影响，参数M是将候选边集的每个边的长度设置为长度的M次方。解决不同的问题时，在算法运行前设置不同的M值，以获取最优路径。

d)在该边e上构建椭圆点集，并在构建的椭圆域中选择P点

以该边为椭圆的长轴建立椭圆区域，采用随机的方式在椭圆域中获得一个P点。选择P点的基本原则是尽可能地减少新路径的长度。椭圆区域的大小通过改变椭圆的短轴长度来调整。图3表示了椭圆形区域。

椭圆是在局部坐标系统UO′V下构造的，交货节点D点和取货节点P点的位置是在全局坐标系XOY下确定的，需将椭圆方程从局部坐标系转换到全局坐标系，以判断取货节点P(x，y)是否在椭圆内。若点P满足等式(7)，则表示该点在椭圆区域内。

b＝a·R (3)

式中a，b分别为椭圆的长半轴和短半轴，R是二者的比值，α是坐标系UO′V旋转到全局坐标系XOY的角度，(S，T)是边e的中点(坐标系UO′V的原心)在坐标系XOY的坐标。

对于椭圆内存在不止一个P点的情况，采用随机策略选择一个P点。对于在椭圆区域内没有P点的情况，则重新选择另外一边e，再进行选点操作。如果一定次数(通常取10次)的选边之后，仍然选不到点就直接插入等式(7)所计算的Loc(x，y)值中最小的点P。

步骤3：重复步骤2，直至达到指定迭代次数(根据问题规模，选择实验结果中能达到稳定效果的次数)。其中路径成本最小的可行解即为所求连接所有D点和部分P点的机器人最优路径。

所述步骤2中步骤b)的候选边集SCE的构建过程如下：

(1)SCE集合的初始化

如果没有荷载可以提供，即q0＝0。将LKH路径上的第一条l1边纳入集合SCE，并保留1个D点，以便边l1附近的P点(基于该边所构建的椭圆点集中的点)被捡起来后能替换该D点，如图4。

如果提供荷载，即q0≠0，则先将从携带的荷载就近替换到从开始的LKH路径上的q0个D点。因为此路径本身就是最短路径，也就是将SCE初始的q0个L-edge的尾点由携带的q0个荷载替换。为了获得这q0个尾点，需将q0中排在前而的1+q0条边添加至SCE，此时t＝q0+2。如图5，q0＝2，添加OD1、D1D2至SCE，并用携带的荷载替换D1和D2。

除了添加q0条LKH边用于提供q0个D点以便被这q0个携带的荷载替换外，还考虑到沿这些点构成的路径的附近捡取一个荷载后，尚需存在1个D点作为此捡起的荷载的替换位置。如图5，D1D2被替换后，尚应添加边D2D3至SCE。

图4和图5中，实线表示LKH路径中移入SCE的边，空心圆表示未被替换的D点，实心圆表示已经被替换的D点，O点表示，low，up表示指向当前SCE集合的上下界的指针，t是当前已经移入SCE的SLKH中的最后一边的下一边，叫做LKH当前边，作为下一次准备移入SCE的边。

(2)SCE集合的拓展

替换充L-edge的尾点的荷载的来源有两种：①来自于的荷载，由机器人来替换补SCE集合的开始的q0个边；②由L-edge和E-edge的拓展后获得的荷载，去替换当前SCE集合的最后一边的尾点。“拓展”是指在L-edge上构建椭圆点集并允许在其中选择P点，由此所选择的P点连接而成的E-edge被增加在SCE中，SCE中任何一个边(L-edge或E-edge)可以被选择以构建椭圆点集，并且该椭圆点集被用于选点。

L-edge和E-edge是在SCE中选择的，具体方法是：首先，按赌法从SCE中选择一边，如图6中的e；然后，基于这条边，构建椭圆点集，在椭圆点集中，按步骤d的方法获得点P。

在E-edge边选点存在比在L-edge边附近选点所形成的路径的总长度更短的可能性。如图7b和7c，基于D2D3拓展出P3而生成D1P1D2P3D3(图7b)和基于P1D2拓展出P2而生成D1P1P2D2D3(图7c)两种情况中，前者的路径长度比后者更长一些。因此，E-edge应当被不断地拓展，即可以继续基于添加的E-edge边构建椭圆点集并选点，如图7c，D1D2D3是原始的LKH路径，在D1D2上拓展得到P1后，在P1D2上继续拓展得到P2。这种不断拓展E-edge的方式，拓宽了P点的搜索范围，增加了解的多样性。通过重复使用这种在不同的E-edge上选P点的方式可连续地获得大量的可行解。其终止条件是，SCE内某边的荷载达到了边的容量。

捡起一个荷载将引起插入点之后的各边荷载数变化。如图6，插入取货节点P点后，loade2＝loade1+1，且e2随后各边loadi＝loadi+1(i＝e2+1，e2+2，.....，up-1)。图6b显示了拾取P点后各边荷载的变化情况(图6中加圈的数字表示loadi)。

机器人不断地捡取与替换传感器，经过各边时，其每条边上的loadi不断变化。然而，任何一边的loadi都不允许超出机器人容量的限制，因此，当达到容量时(loadi＝Qmax)，拓展就停止了。

(3)SCE集合的生长

SCE中最后一边的尾点总是保留了一个待替换点(D点)，当拓展一次(即获得了一个P点的荷载)后，此孔即被替换了。为了能继续拓展，需在SCE中的终边增加一个待替换孔作为补充。所谓“边的生长”就是指在SCE集合的最后一边之后添加SLKH的当前边，其目的在于通过增加新边来提供L-edge的尾点。

如图8b中，q0＝2，在P点处捡起一个荷载后，D3将被替换，此时将SLKH的当前边延伸到集合的下界，即在SCE集合中生长出边D3D4。该边的荷载为：

loadup＝loadup-1-1。

(4)SCE集合的缩减

SCE集合中的各边须满足边荷载容量的约束。如果在任意一个E-edge的椭圆点集中获得一个P点，那么机器人经过此点后的各边时，在这些边上的荷载数均增加，因为这个原因，经过SCE集合中的某一条边k所携带的荷载数loadk将会被累加到容量Qmax。此时，在SCE中的边k及其之前的各边不能再被用于构建椭圆点集。因为一旦以这些边所构建的椭圆点集内的点被捡起，那么，当机器人经过边k时，loadk≥Qmax。结果，边k及其之前的各边从SCE集合被删减，这就是SCE集合的缩减。如图8c中，设Qmax＝3，经过P1D2边的那么，P1D2及其前面的各边被从SCE中去掉。

该算法中有两个参数M和R：M是中用来选择边的边长的M次方，R是确定椭圆曲率的比例因子，它等于椭圆的短半轴与椭圆的长半轴的比值。在两个参数组合的基准实例上运行了200次迭代程序，结果如下所示：测试参数M对结果的影响时将R固定为0.5，M的范围取为1至11，步长取为2；测试参数R对结果的影响时将M固定为10，R范围取为0.1至1.1，步长取为0.2。表1展示了参数M对算法结果的影响。表2展示了参数R对算法结果的影响。

表1参数M对结果的影响

表2参数R对结果的影响

如图9和图10：在小规模问题中，参数M的取值对结果影响不大。参数R对结果有重要的影响，当R值较大时，所得路径较优。然而，随着问题规模的增加，参数R对结果影响不大，参数M逐渐成为影响结果的主要因素，当M取值为7至11时，所得路径较优。

为了对算法的运行效率进行测试，将该算法与用于解决的1-TSP-SELPD的上述文献提出的两种算法IMSA和MMAS进行了比较，具体的结果数据对比见表3。

表3与IMSA、MMAS算法的比较结果

从上表和图11可以看出，本算法花费的时间远远少于IMSA和MMAS，且在大规模问题中，获得了较IMSA和MMAS算法更好的结果，效率较高。在WSRNs修复过程中，问题是大多是大规模的，因此，本算法有更好的适应性。