一种多电框业务盘装载规划方法、装置、设备及存储介质与流程 专利技术说明

电子通信装置的制造及其应用技术1.本发明涉及智慧光网设备自动规划技术领域，具体涉及一种多电框业务盘装载规划方法、装置、设备及存储介质。背景技术：2.设备自动规划指根据网络业务路由波道规划设计结果，自动仿真规划设计出满足业务需求的业务盘及其在机框上的装载槽位。3.当单个电框槽位个数无法支持装载全部业务盘时，需要使用多个电框来装载。电框上的支路盘与线路盘通过电框背板交叉信号，发生汇聚的支路盘与线路盘务必装载在同一个电框上。如何高效最优地分配支路盘与线路盘装载至多个电框，需要选择一种合适的算法来规划设计。4.然而，现有的贪心求解方法分配支路盘与线路盘装载至多个电框时存在以下问题：5.(1)每次选择占用槽位个数最少的交叉汇聚业务盘，直到电框装载不下为止，容易造成电框部分槽位闲置，从而结果不是最优；6.(2)分配不合理，即使支路盘与线路盘所需槽位总数≤多个电框槽位总数，却装载不下。技术实现要素：7.针对现有技术中存在的缺陷，本发明第一方面提供一种多电框业务盘装载规划方法，其可以高效最优地分配支路盘与线路盘装载至多个电框，避免过多电框槽位闲置或装载不下的问题。8.为达到以上目的，本发明采取的技术方案是：9.一种多电框业务盘装载规划方法，该方法包括以下步骤：10.基于剪枝回溯法，将多个电框中的前n-1个电框装载尽可能多的业务盘，其中n为大于等于2的自然数；11.将剩余的业务盘装载在最后一个电框中。12.一些实施例中，所述基于剪枝回溯法，将多个电框中的前n-1个电框装载尽可能多的业务盘，包括：13.将第一个电框的业务盘槽位尽可能装满的解空间转化为一个子集树，搜索整个解空间，当搜索至子集树的一节点时，使用剪枝函数判断该节点是否存在可行解；14.若不存在可行解，则跳过对该节点为根的子树的搜索，逐层向其父节点回溯；若存在可行解，则进入该子树，继续搜索可行解，并在遍历的过程中记录和寻找最优解；15.依次获取其余电框的业务盘槽位的解空间最优解。16.一些实施例中，所述将第一个电框的业务盘槽位尽可能装满的解空间转化为一个子集树，搜索整个解空间，当搜索至子集树的一节点时，使用剪枝函数判断该节点是否存在可行解，包括：17.将第一个电框的业务盘槽位尽可能装满的解空间等价于选取交叉汇聚组业务盘的一个子集，使得该子集中交叉汇聚组业务盘所需电框槽位个数之和最接近第一个电框可装载业务盘槽位个数；18.记解空间为n元向量{x1，x2，…，xn}，xi∈{0，1}，其中n为交叉汇聚组的组数；19.将发生交叉汇聚的支路盘与线路盘分入同一组，记该交叉汇聚组全部业务盘所需电框槽位个数为wi，0≤i≤n-1；20.定义第一个电框当前最优装载业务盘槽位数bestw、当前节点已装载业务盘槽位个数cw、以及剩余交叉汇聚组业务盘槽位个数总和rw；21.利用可行性约束函数：cw+w[i]≤c1，0≤i≤n-1，c1为第一个电框的业务盘槽位个数，剪去不满足约束条件的子树；[0022]利用上界限界函数cw+rw＞bestw剪去不含最优解的子树。[0023]一些实施例中，定义递归函数backtrack(i)，从第0层开始递归搜索子集树至第n-1层叶子节点；[0024]当i≥n时，算法搜索至叶子节点，若cw》bestw则表示当前解优于已记录的最优解，更新bestw；[0025]当i《n时，算法搜索至非叶子节点，当cw+wi≤c1时进入左子树，对左子树递归搜索，并直接进入右子树递归搜索。[0026]本发明第一方面提供一种多电框业务盘装载规划方法，其可以高效最优地分配支路盘与线路盘装载至多个电框，避免过多电框槽位闲置或装载不下的问题。[0027]为达到以上目的，本发明采取的技术方案是：[0028]一种多电框业务盘装载规划装置，包括：[0029]计算模块，其基于剪枝回溯法，将多个电框中的前n-1个电框装载尽可能多的业务盘，其中n为大于等于2的自然数，并将剩余的业务盘装载在最后一个电框中。[0030]一些实施例中，所述计算模块基于剪枝回溯法，将多个电框中的前n-1个电框装载尽可能多的业务盘，包括：[0031]将第一个电框的业务盘槽位尽可能装满的解空间转化为一个子集树，搜索整个解空间，当搜索至子集树的一节点时，使用剪枝函数判断该节点是否存在可行解；[0032]若不存在可行解，则跳过对该节点为根的子树的搜索，逐层向其父节点回溯；若存在可行解，则进入该子树，继续搜索可行解，并在遍历的过程中记录和寻找最优解；[0033]依次获取其余电框的业务盘槽位的解空间最优解。[0034]一些实施例中，所述计算模块将第一个电框的业务盘槽位尽可能装满的解空间转化为一个子集树，搜索整个解空间，当搜索至子集树的一节点时，使用剪枝函数判断该节点是否存在可行解，包括：[0035]将第一个电框的业务盘槽位尽可能装满的解空间等价于选取交叉汇聚组业务盘的一个子集，使得该子集中交叉汇聚组业务盘所需电框槽位个数之和最接近第一个电框可装载业务盘槽位个数；[0036]记解空间为n元向量{x1，x2，…，xn}，xi∈{0，1}，其中n为交叉汇聚组的组数；[0037]将发生交叉汇聚的支路盘与线路盘分入同一组，记该交叉汇聚组全部业务盘所需电框槽位个数为wi，0≤i≤n-1；[0038]定义第一个电框当前最优装载业务盘槽位数bestw、当前节点已装载业务盘槽位个数cw、以及剩余交叉汇聚组业务盘槽位个数总和rw；[0039]利用可行性约束函数：cw+w[i]≤c1，0≤i≤i-1，c1为第一个电框的业务盘槽位个数，剪去不满足约束条件的子树；[0040]利用上界限界函数cw+rw＞bestw剪去不含最优解的子树。[0041]一些实施例中，所述计算模块用于：[0042]定义递归函数backtrack(i)，从第0层开始递归搜索子集树至第n-1层叶子节点；[0043]当i≥n时，算法搜索至叶子节点，若cw》bestw则表示当前解优于已记录的最优解，更新bestw；[0044]当i《n时，算法搜索至非叶子节点，当cw+wi≤c1时进入左子树，对左子树递归搜索，并直接进入右子树递归搜索。[0045]本发明第三方面提供一种设备，所述设备包括处理器、存储器、以及存储在所述存储器上并可被所述处理器执行的计算机程序，其中所述计算机程序被所述处理器执行时，实现上述中任一一种多电框业务盘装载规划方法的步骤。[0046]本发明第四方面提供一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，其中所述计算机程序被处理器执行时，实现上述中任一一种多电框业务盘装载规划方法的步骤。[0047]与现有技术相比，本发明的优点在于：[0048]本发明中的多电框业务盘装载规划方法，其基于剪枝回溯法，将多个电框中的前n-1个电框装载尽可能多的业务盘，然后将剩余的业务盘装载在最后一个电框中。将电框的业务盘槽位尽可能装满的解空间转化为一个子集树，使用深度优先搜索策略搜索整个解空间，当搜索至解空间树的某一节点时，使用剪枝函数判断该节点是否可行有解。如果不可行，则跳过对该节点为根的子树的搜索，逐层向其父亲节点回溯；如果可行，则进入该子树，继续按照深度优先策略搜索可行解，遍历的过程中记录和寻找最优解。从而可以获取最优装载方案，降低电框中闲置槽位数，避免支路盘与线路盘所需槽位总数小于等于多个电框槽位总数而装载不下问题。附图说明[0049]图1是本发明实施例中多电框业务盘装载规划方法的流程图；[0050]图2是本发明实施例中贪心求解法和剪枝回溯法的对比示意图；[0051]图3是本发明实施例中解空间子集树的示意图。[0052]图4是本发明实施例中涉及的计算机设备的结构示意框图。具体实施方式[0053]为使本技术实施例的目的、技术方案和优点更加清楚，下面将结合本技术实施例中的附图，对本技术实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本技术的一部分实施例，而不是全部的实施例。基于本技术中的实施例，本领域普通技术人员在没有做出创造性劳动的前提下所获得的所有其他实施例，都属于本技术保护的范围。[0054]参见图1所示，本发明实施例公开了一种多电框业务盘装载规划方法，其特征在于，该方法包括以下步骤：[0055]s1.基于剪枝回溯法，将多个电框中的前n-1个电框装载尽可能多的业务盘，其中n为大于等于2的自然数。[0056]在本发明实施例中，步骤s1具体包括：[0057]s11.将第一个电框的业务盘槽位尽可能装满的解空间转化为一个子集树，搜索整个解空间，当搜索至子集树的一节点时，使用剪枝函数判断该节点是否存在可行解；[0058]s12.若不存在可行解，则跳过对该节点为根的子树的搜索，逐层向其父节点回溯；若存在可行解，则进入该子树，继续搜索可行解，并在遍历的过程中记录和寻找最优解；[0059]s13.依次获取其余电框的业务盘槽位的解空间最优解。[0060]值得说明的是，回溯算法本质上是一种递归算法，基本上是用于解决对于某种集合的遍历枚举搜索，可以使用预先排序的方式按照某种规则来进行剪枝，以减少搜索路径。一般情况下是对于一颗树的搜索，从根节点出发，向符合条件的第一个子节点出发搜索，然后以当前子节点作为根节点继续搜索，如果找到符合题意的解则记录下来，如果找不到则从当前子节点返回上一级父节点，从父节点的第二个可行子节点进行搜索。[0061]s2.将剩余的业务盘装载在最后一个电框中。[0062]下面以两个电框为例，对上述步骤做出进一步说明：[0063]首先将发生交叉汇聚的支路盘与线路盘分入同一组，记该交叉汇聚组全部业务盘所需电框槽位个数为wi，记两个电框可装载业务盘槽位个数为c1与c2，[0064]当时，对于一个给定的装载有解的问题，采用下面的策略可得到最优装载方案。[0065](1)先将第一个电框的业务盘槽位尽可能装满；[0066](2)将剩余的交叉汇聚组业务盘装载至第二个电框。[0067]将第一个电框尽可能的装满等价于选取全体交叉汇聚组的一个子集，使得该子集中交叉汇聚组业务盘所需电框槽位个数之和最接近c1。由此，可以将该问题等价于以下特殊的0-1背包问题：[0068][0069][0070]xi∈{0,1},1≤i≤n[0071]将第一个电框的业务盘槽位尽可能装满的解空间转化为一个子集树(从n个元素的集合s中找出满足某种性质的子集时，相应的解空间称为子集树)，使用深度优先搜索策略从根节点(每个节点记录了从根节点沿路径遍历至当前深度时的已知解集，根节点代表当前已知解集为空)开始搜索整个解空间，当搜索至解空间树的某一节点时，使用剪枝函数判断该节点是否可行有解。如果不可行，则跳过对该节点为根的子树的搜索，逐层向其父亲节点回溯；如果可行，则进入该子树，继续按照深度优先策略搜索可行解，遍历的过程中记录和寻找最优解。[0072]记解空间为n元向量{x1,x2,…,xn},xi∈{0,1}，其中n为交叉汇聚组的组数。[0073]wi,0≤i≤n-1:交叉汇聚组全部业务盘所需电框槽位个数[0074]bestw:第一个电框当前最优装载业务盘槽位数[0075]cw：当前节点已装载业务盘槽位个数[0076]rw:剩余交叉汇聚组业务盘槽位个数总和[0077]用可行性约束函数剪去不满足约束条件子树。搜索至子集树某个节点处，当cw》c1时，以该节点为根的子树中所有节点都不满足约束条件，不存在可行解，因此可直接剪去该子树。与此同时，引入上界限界函数剪去不含最优解的子树，搜索至子集树某个节点处，以该节点为根的子树中任意叶子节点的可行解均不超过cw+rw，因此当cw+rw《bestw时不存在最优解，可直接剪去该子树。[0078]递归实现回溯搜索，定义递归函数backtrack(i)，从第0层开始递归搜索子集树至第n-1层叶子节点。[0079]当i≥n时，算法搜索至叶子节点，其相应的已装载业务盘槽位个数为cw。如果cw》bestw则表示当前解优于已记录的最优解，更新bestw。[0080]当i《n时，算法搜索至非叶子节点。其拥有xi＝1和xi＝0一左一右两个儿子节点。当cw+wi≤c1时进入左子树，对左子树递归搜索。由于可行节点的右儿子节点总是可行的，因此可直接进入右子树递归搜索。[0081]上述描述给出了本发明实施例中的具体处理流程，下面以一个具体的实例来做出进一步说明：[0082]参见图2所示，其给出了贪心求解法和剪枝回溯法的对比示例。图2中共有4组交叉汇聚业务盘，每组需要的槽位个数分别为6、7、9、10，两个电框的业务盘槽位个数c1与c2分别为16、16。从图2中可以看出基于贪心求解法并不能获得最优解，第一个电框未装满，而第二个电框又装载不下。[0083]对于剪枝回溯法的具体过程，下面介绍如下：[0084]从4组交叉汇聚业务盘集合中找出满足第一个电框的业务盘槽位尽可能装满的子集，相应的解空间如图3所示。[0085]定义：[0086]w[i]＝{6,7,9,10},0≤i≤3:交叉汇聚组全部业务盘所需电框槽位个数[0087]bestw:第一个电框当前最优装载业务盘槽位数[0088]cw：当前已装载业务盘槽位个数[0089]rw:剩余的交叉汇聚组业务盘槽位个数总和[0090]最优装载方案(第一个机框)[0091]当前装载方案(第一个机框)[0092]backtrack(depth),0≤depth≤4:递归函数[0093]cw+w[i]≤16,0≤i≤3:可行性约束函数[0094]cw+rw》bestw:上界限制函数[0095]初始化rw＝32，cw＝0，bestw＝0[0096]递归实现回溯搜索，按照深度优先遍历解空间搜索满足要求的子集。[0097]求解最优装载方案流程如所示，求解过程详情如下：[0098](1)访问节点a‑‑‑backtrack(0)[0099]depth＝0，小于等于3，节点a为非叶子节点，其拥有左儿子节点b，右儿子节点o；[0100]w[0]＝6，假设当前交叉汇聚组可以装入，更新rw＝26(rw＝32-w[0])；cw+w[0]≤16，满足可行性约束函数，搜索左子树；[0101]x[0]＝1，标记选择装入，更新cw＝6(cw＝0+w[0])[0102]递归进入左儿子节点b。[0103](2)访问节点b‑‑‑backtrack(1)[0104]depth＝1，小于等于3，节点b为非叶子节点，其拥有左儿子节点c，右儿子节点h；[0105]w[1]＝7，假设当前交叉汇聚组可以装入，更新rw＝19(rw＝26-w[1])；[0106]cw+w[1]≤16，满足可行性约束函数，搜索左子树；[0107]x[1]＝1，标记选择装入，更新cw＝13(cw＝6+w[1])；[0108]递归进入左儿子节点c。[0109](3)访问节点c‑‑‑backtrack(2)[0110]depth＝2，小于等于3，节点c为非叶子节点，其拥有左儿子节点d，右儿子节点e；[0111]w[2]＝9，假设当前交叉汇聚组可以装入，更新rw＝10(rw＝19-w[2])[0112]cw+w[2]》16不满足可行性约束函数，剪枝左子树；[0113]cw+rw》bestw(bestw＝0)满足上界限制函数，搜索右子树；[0114]x[2]＝0，标记选择不装，cw＝13；[0115]递归进入右儿子节点e。[0116](4)访问节点e‑‑‑backtrack(3)[0117]depth＝3，小于等于3，节点e为非叶子节点，其拥有左儿子节点f，右儿子节点g；[0118]w[3]＝10，假设当前交叉汇聚组可以装入，更新rw＝0(rw＝10-w[3])；[0119]cw+w[3]》16，不满足可行性约束函数，剪枝左子树；[0120]cw+rw》bestw(bestw＝0)，满足上界限制函数，搜索右子树；[0121]x[3]＝0，标记选择不装，cw＝13；[0122]递归进入右儿子节点g。[0123](5)访问节点g‑‑‑backtrack(4)[0124]depth＝4，大于3，节点g为叶子节点[0125]cw》bestw(bestw＝0)，更新最优解bestw＝13(bestw＝cw)[0126]更新最优装载方案bestx[i]＝{1,1,0,0}。[0127](6)回溯返回至(4)访问节点e中递归进入右儿子节点g[0128]depth＝3；[0129]返回还原rw＝10(rw＝0+w[3])。[0130](7)回溯返回至(3)访问节点c中递归进入右儿子节点e[0131]depth＝2；[0132]返回还原rw＝19(rw＝10+w[2])。[0133](8)回溯返回至(2)访问节点b中递归进入左儿子节点c[0134]depth＝1；[0135]返回还原cw＝6(cw＝13-w[1])。[0136]cw+rw》bestw(bestw＝13)满足上界限制函数，搜索右子树[0137]x[1]＝0，标记选择不装，cw＝6,rw＝19；[0138]递归进入右儿子节点h。[0139](9)访问节点h‑‑‑backtrack(2)[0140]depth＝2，小于等于3，节点h为非叶子节点，其拥有左儿子节点i，右儿子节点l；[0141]w[2]＝9，假设当前交叉汇聚组可以装入，更新rw＝10(rw＝19-w[2])；[0142]cw+w[2]≤16满足可行性约束函数，搜索左子树；[0143]x[2]＝1，标记选择装入，更新cw＝15(cw＝6+w[2])；[0144]递归进入左儿子节点i。[0145](10)访问节点i‑‑‑backtrack(3)[0146]depth＝3，小于等于3，节点i为非叶子节点，其拥有左儿子节点j，右儿子节点k；[0147]w[3]＝10，假设当前交叉汇聚组可以装入，更新rw＝0(rw＝10-w[3])；[0148]cw+w[3]》16不满足可行性约束函数，剪枝左子树；[0149]cw+rw》bestw(bestw＝13)满足上界限制函数，搜索右子树；[0150]x[3]＝0，标记选择不装，cw＝15；[0151]递归进入右儿子节点k。[0152](11)访问节点k‑‑‑backtrack(4)[0153]depth＝4，大于3，节点g为叶子节点；[0154]cw》bestw(bestw＝13)，更新最优解bestw＝15(bestw＝cw)；[0155]更新最优装载方案bestx[i]＝{1,0,1,0}。[0156](12)回溯返回至(10)访问节点i中递归访问右儿子节点k[0157]depth＝3；[0158]返回还原rw＝10(rw＝0+w[3])。[0159](13)回溯返回至(9)访问节点h中递归访问左儿子节点i[0160]depth＝2；[0161]返回还原cw＝6(cw＝15-w[2])；[0162]cw+rw》bestw(bestw＝15)满足上界限制函数，搜索右子树；[0163]x[2]＝0，标记选择不装，cw＝6,rw＝10；[0164]递归进入右儿子节点l。[0165](14)访问节点l‑‑‑backtrack(3)[0166]depth＝3，小于等于3，节点l为非叶子节点，其拥有左儿子节点m，右儿子节点n；[0167]w[3]＝10，假设当前交叉汇聚组可以装入，更新rw＝0(rw＝10-w[3])；[0168]cw+w[3]≤16满足可行性约束函数，搜索左子树；[0169]x[3]＝1，标记选择装入，更新cw＝16(cw＝6+w[3])；[0170]递归进入左儿子节点m。[0171](15)访问节点m‑‑‑backtrack(4)[0172]depth＝4，大于3，节点m为叶子节点；[0173]cw》bestw(bestw＝15)，更新最优解bestw＝16(bestw＝cw)；[0174]更新最优装载方案bestx[i]＝{1,0,0,1}。[0175](16)回溯返回至(14)访问节点l中递归进入左儿子节点m[0176]depth＝3；[0177]返回还原cw＝6(cw＝16-w[3])；[0178]cw+rw≤bestw(bestw＝16)不满足上界限制函数，剪枝右子树；[0179]返回还原rw＝10(rw＝0+w[3])。[0180](17)回溯返回至(9)访问节点h中递归访问右儿子节点l[0181]depth＝2；[0182]返回还原rw＝19(rw＝10+w[2])。[0183](18)回溯返回至(8)回溯返回至(2)访问节点b中递归进入右儿子节点h[0184]注：(8)中先后完成进入节点b的左儿子节点与右儿子节点；[0185]depth＝1；[0186]返回还原rw＝26(rw＝19+w[1])；[0187](19)回溯返回至(1)访问节点a中递归进入左儿子节点b[0188]depth＝0；[0189]返回还原cw＝0(cw＝6-w[0])；[0190]cw+rw》bestw(bestw＝16)满足上界限制函数，搜索右子树[0191]x[0]＝0，标记选择不装，cw＝0,rw＝26；[0192]递归进入右儿子节点o。[0193](20)访问节点o‑‑‑backtrack(1)[0194]depth＝1，小于等于3，节点o为非叶子节点，其拥有左儿子节点p，右儿子节点w；[0195]w[1]＝7，假设当前交叉汇聚组可以装入，更新rw＝19(rw＝26-w[1])；[0196]cw+w[1]≤16满足可行性约束函数，搜索左子树；[0197]x[1]＝1，标记选择装入，更新cw＝7(cw＝0+w[1])；[0198]递归进入左儿子节点p。[0199](21)访问节点p‑‑‑backtrack(2)[0200]depth＝2，小于等于3，节点p为非叶子节点，其拥有左儿子节点q，右儿子节点t；[0201]w[2]＝9，假设当前交叉汇聚组可以装入，更新rw＝10(rw＝19-w[2])；[0202]cw+w[2]≤16满足可行性约束函数，搜索左子树；[0203]x[1]＝1，标记选择装入，更新cw＝16(cw＝7+w[2])；[0204]递归进入左儿子节点q。[0205](22)访问节点q‑‑‑backtrack(3)[0206]depth＝3，小于等于3，节点p为非叶子节点，其拥有左儿子节点r，右儿子节点s；[0207]w[3]＝10，假设当前交叉汇聚组可以装入，更新rw＝0(rw＝10-w[3])；[0208]cw+w[3]》16不满足可行性约束函数，剪枝左子树；[0209]cw+rw》bestw(bestw＝16)不满足上界限制函数，剪枝右子树；[0210]返回还原rw＝10(rw＝0+w[3])。[0211](23)回溯返回至(21)访问节点p中递归进入左儿子节点q[0212]depth＝2，小于等于3；[0213]返回还原cw＝7(cw＝16-w[2])；[0214]cw+rw》bestw(bestw＝16)满足上界限制函数，搜索右子树；[0215]x[0]＝0，标记选择不装，cw＝7,rw＝10；[0216]递归进入右儿子节点t。[0217](24)访问节点t‑‑‑backtrack(3)[0218]depth＝3，小于等于3，节点t为非叶子节点，其拥有左儿子节点u，右儿子节点v；[0219]w[3]＝10，假设当前交叉汇聚组可以装入，更新rw＝0(rw＝10-w[3])；[0220]cw+w[3]》16不满足可行性约束函数，剪枝左子树；[0221]cw+rw《bestw(bestw＝16)不满足上界限制函数，剪枝右子树；[0222]返回还原rw＝10(rw＝0+w[3])。[0223](25)回溯返回至(23)回溯返回至(21)访问节点p中递归进入右儿子节点r[0224]注：(23)中先后完成进入节点p的左儿子节点与右儿子节点[0225]depth＝2；[0226]返回还原rw＝19(rw＝10+w[2])。[0227](26)回溯返回至(20)访问节点o中递归进入左儿子节点p[0228]depth＝1；[0229]返回还原cw＝0(cw＝7-w[1])；[0230]cw+rw》bestw(bestw＝16)满足上界限制函数，搜索右子树；[0231]x[0]＝0，标记选择不装，cw＝0,rw＝19；[0232]递归进入右儿子节点w。[0233](27)访问节点w‑‑‑backtrack(2)[0234]depth＝2，小于等于3，节点w为非叶子节点，其拥有左儿子节点x，右儿子节点aa；[0235]w[2]＝9，假设当前交叉汇聚组可以装入，更新rw＝10(rw＝19-w[2])；[0236]cw+w[2]≤16满足可行性约束函数，搜索左子树；[0237]x[2]＝1，标记选择装入，更新cw＝9(cw＝0+w[2])；[0238]递归进入左儿子节点x。[0239](28)访问节点x‑‑‑backtrack(3)[0240]depth＝3，小于等于3，节点x为非叶子节点，其拥有左儿子节点y，右儿子节点z；[0241]w[3]＝10，假设当前交叉汇聚组可以装入，更新rw＝0(rw＝10-w[3])；[0242]cw+w[3]》16不满足可行性约束函数，剪枝左子树；[0243]cw+rw《bestw(bestw＝16)不满足上界限制函数，剪枝右子树；[0244]返回还原rw＝10(rw＝0+w[3])；[0245](29)回溯返回至(27)访问节点w中递归进入左儿子节点x[0246]depth＝2；[0247]返回还原cw＝0(cw＝9-w[2])；[0248]cw+rw《bestw(bestw＝16)不满足上界限制函数，剪枝右子树；[0249]返回还原rw＝19(rw＝10+w[2])。[0250](30)回溯返回至(26)回溯返回至(20)访问节点o中递归进入右儿子节点w[0251]注：(26)中先后完成进入节点o的左儿子节点与右儿子节点[0252]depth＝1；[0253]返回还原rw＝26(rw＝19+w[1])。[0254](31)回溯返回至(19)回溯返回至(1)访问节点a中递归进入右儿子节点o[0255]注：(19)中先后完成进入节点a的左儿子节点与右儿子节点；[0256]depth＝0；[0257]返回还原rw＝32(rw＝26+w[10])。[0258](32)结束遍历，输出最优解bestw＝16，最优装载方案bestx[i]＝{1,0,0,1}。[0259]故此，便通过剪枝回溯法，得到了所需要的最优解。[0260]综上所述，本发明中的多电框业务盘装载规划方法，其基于剪枝回溯法，将多个电框中的前n-1个电框装载尽可能多的业务盘，然后将剩余的业务盘装载在最后一个电框中。将电框的业务盘槽位尽可能装满的解空间转化为一个子集树，使用深度优先搜索策略搜索整个解空间，当搜索至解空间树的某一节点时，使用剪枝函数判断该节点是否可行有解。如果不可行，则跳过对该节点为根的子树的搜索，逐层向其父亲节点回溯；如果可行，则进入该子树，继续按照深度优先策略搜索可行解，遍历的过程中记录和寻找最优解。从而可以获取最优装载方案，降低电框中闲置槽位数，避免支路盘与线路盘所需槽位总数小于等于多个电框槽位总数而装载不下问题。[0261]同时，本发明实施例还公开了一种多电框业务盘装载规划装置，包括计算模块。[0262]其中，计算模块基于剪枝回溯法，将多个电框中的前n-1个电框装载尽可能多的业务盘，其中n为大于等于2的自然数，并将剩余的业务盘装载在最后一个电框中。[0263]一些实施例中，所述计算模块基于剪枝回溯法，将多个电框中的前n-1个电框装载尽可能多的业务盘，包括：[0264]将第一个电框的业务盘槽位尽可能装满的解空间转化为一个子集树，搜索整个解空间，当搜索至子集树的一节点时，使用剪枝函数判断该节点是否存在可行解；[0265]若不存在可行解，则跳过对该节点为根的子树的搜索，逐层向其父节点回溯；若存在可行解，则进入该子树，继续搜索可行解，并在遍历的过程中记录和寻找最优解；[0266]依次获取其余电框的业务盘槽位的解空间最优解。[0267]一些实施例中，所述计算模块将第一个电框的业务盘槽位尽可能装满的解空间转化为一个子集树，搜索整个解空间，当搜索至子集树的一节点时，使用剪枝函数判断该节点是否存在可行解，包括：[0268]记解空间为n元向量{x1，x2，…，xn}，xi∈{0，1}；[0269]将发生交叉汇聚的支路盘与线路盘分入同一组，记该交叉汇聚组全部业务盘所需电框槽位个数为wi，0≤i≤n-1；[0270]定义第一个电框当前最优装载业务盘槽位数bestw、当前节点已装载业务盘槽位个数cw、以及剩余交叉汇聚组业务盘槽位个数总和rw；[0271]利用可行性约束函数：cw+w[i]≤c1，0≤i≤i-1，c1为第一个电框的业务盘槽位个数，剪去不满足约束条件的子树；[0272]利用上界限界函数cw+rw＞bestw剪去不含最优解的子树。[0273]一些实施例中，所述计算模块用于：[0274]定义递归函数backtrack(i)，从第0层开始递归搜索子集树至第n-1层叶子节点；[0275]当i≥n时，算法搜索至叶子节点，若cw》bestw则表示当前解优于已记录的最优解，更新bestw；[0276]当i《n时，算法搜索至非叶子节点，当cw+wi≤c1时进入左子树，对左子树递归搜索，并直接进入右子树递归搜索。[0277]本发明实施例还提供一种设备，所述设备包括处理器、存储器、以及存储在所述存储器上并可被所述处理器执行的计算机程序，其中所述计算机程序被所述处理器执行时，实现上述多电框业务盘装载规划方法的步骤。[0278]具体的参见图4所示，本发明实施例中的设备为计算机设备，其包括通过系统总线连接的处理器、存储器和网络接口，其中，存储器可以包括非易失性存储介质和内存储器。[0279]非易失性存储介质可存储操作系统和计算机程序。该计算机程序包括程序指令，该程序指令被执行时，可使得处理器执行任意一种多电框业务盘装载规划方法。[0280]处理器用于提供计算和控制能力，支撑整个计算机设备的运行。[0281]内存储器为非易失性存储介质中的计算机程序的运行提供环境，该计算机程序被处理器执行时，可使得处理器执行任意一种多电框业务盘装载规划方法。[0282]该网络接口用于进行网络通信，如发送分配的任务等。本领域技术人员可以理解，图4中示出的结构，仅仅是与本技术方案相关的部分结构的框图，并不构成对本技术方案所应用于其上的计算机设备的限定，具体的计算机设备可以包括比图中所示更多或更少的部件，或者组合某些部件，或者具有不同的部件布置。[0283]应当理解的是，处理器可以是中央处理单元(central processing unit，cpu)，该处理器还可以是其他通用处理器、数字信号处理器(digital signal processor，dsp)、专用集成电路(application specific integrated circuit，asic)、现场可编程门阵列(field-programmable gate array，fpga)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件等。其中，通用处理器可以是微处理器或者该处理器也可以是任何常规的处理器等。[0284]本发明实施例还提供一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，其中所述计算机程序被处理器执行时，实现上述的多电框业务盘装载规划方法的步骤。[0285]以上所述仅是本技术的具体实施方式，使本领域技术人员能够理解或实现本技术。对这些实施例的多种修改对本领域的技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本技术的精神或范围的情况下，在其它实施例中实现。因此，本技术将不会被限制于本文所示的这些实施例，而是要符合与本文所申请的原理和新颖特点相一致的最宽的范围。









图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!




内容声明：本文中引用的各种信息及资料（包括但不限于文字、数据、图表及超链接等）均来源于该信息及资料的相关主体（包括但不限于公司、媒体、协会等机构）的官方网站或公开发表的信息。部分内容参考包括:(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供参考使用,不准确地方联系删除处理！本站为非盈利性质站点,发布内容不收取任何费用也不接任何广告!




免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理，本文部分文字与图片资源来自于网络，部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理!的,若有来源标注错误或侵犯了您的合法权益，请立即通知我们，情况属实，我们会第一时间予以删除，并同时向您表示歉意,谢谢!