[發(fā)明專利]一種基于全局啟發(fā)—兩層算法的電纜優(yōu)化分割的方法

無效

• 申請?zhí)枺?/td>: 201310327470.4
• 申請日: 2013-07-31
• 公開（公告）號: CN103425876A
• 公開（公告）日: 2013-12-04
• 發(fā)明（設(shè)計）人: 付文杰;王石;劉章;王清亮;栗軍;花新樂;張騫;張旭東;常征;周茜;張欣
• 申請（專利權(quán)）人: 國家電網(wǎng)公司;國網(wǎng)河北省電力公司
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 石家莊新世紀(jì)專利商標(biāo)事務(wù)所有限公司 13100
• 代理人: 楊欽祥;張素靜

1.一種基于全局啟發(fā)--兩層算法的電纜優(yōu)化分割的方法，其特征在于步驟如下：

步驟一、輸入下述初始參數(shù)：

①原料電纜長度的種類總數(shù)M；

②第i種原料電纜的長度L_i和數(shù)量P_i，L_i的單位為米，其中i為原料電纜長度種類的標(biāo)號，i=1、2、3……M；

③工程中需要的電纜長度的種類總數(shù)m；

④工程中需要的第j種電纜的長度l_j和數(shù)量p_j，l_j的單位為米，其中j為需要的電纜長度種類的標(biāo)號，j=1、2、3……m；

步驟二、預(yù)判斷原料電纜是否能滿足需要：

初步判斷所給原料電纜的長度L_i和數(shù)量P_i是否能滿足工程中需要的電纜的長度l_j和數(shù)量p_j，若出現(xiàn)以下兩種情況任何一種時，給出不滿足切割條件的提示并要求重新輸入初始參數(shù)：

情況一、所給原料電纜的總長度為????????????????????????????????????????????????，需求的電纜的總長度為，小于，即原料電纜不能全部切出需求的電纜；

情況二、所給原料電纜的長度L_i不能將工程中需求的電纜的長度l_j中最長的長度切出；

若上述兩種情況均沒出現(xiàn)，初步判定原料電纜能滿足需要的電纜，則進(jìn)入步驟三；

步驟三、依據(jù)全局啟發(fā)價值算法，利用下述公式（1）~（3）計算當(dāng)切割對象為第i種長度的原料電纜，切割成需要的第j種長度的需要電纜時，此時所對應(yīng)的全局價值：

????????????（1）

其中，為切割第i中長度的原料電纜制成第j種長度的需要電纜所對應(yīng)的啟發(fā)分量；

??????????????（2）

???????????????????（3）

其中，為計算中間值；

???????R為啟發(fā)參數(shù)，為常數(shù)，其值取范圍為0.1~1；

步驟四、當(dāng)?shù)?i>i種長度L_i的原料電纜能切割出的各種長度的所需電纜共有K種切割方案時，根據(jù)下述公式（4）和（5），利用剪枝回溯算法選取該長度電纜切割出的使原料價值之和最大的第k種切割方案：

_????????（4）

??其中，t_k為對應(yīng)的第k種切割方案下的余料，t_k≥0；?為第i種長度L_i的原料電纜按所對應(yīng)的切割方案切出的第j件需求的數(shù)量；

第k種切割方案分別對應(yīng)的總價值，k=1、2、……、K；

?????????????（5）

?????對每一種原料進(jìn)行上述求解，得出該長度電纜切割出的原料價值之和最大的切割方案和這種方案對應(yīng)的價值；

?????計算出所有電纜原料L_i利用剪枝回溯算法得出的?(i=1，2，...，M)，計算/L_i，選取/L_i最大的那根原料進(jìn)行切割；?????

步驟五、根據(jù)下述公式（6）計算步驟四所得切割方案的重復(fù)次數(shù)，即第i種長度L_i的原料電纜使用根數(shù)：?

??????????（6）

步驟六、根據(jù)下述公式（7）和（8）分別重新計算剩余需求電纜數(shù)量p_j＇和剩余原料電纜數(shù)量P_i＇：

?????????（7）

??_{???????????????????}（8）

?????同時，原料電纜和工程中需要電纜的種類也隨著消耗產(chǎn)生變化，用原料電纜的總種類數(shù)M減去其中用完的種類數(shù)，得到新的原料電纜種類數(shù)M＇，用工程中需要的電纜種類總數(shù)m減去其中用完的種類數(shù)，得到新的需要電纜種類數(shù)m＇；

步驟七、將更新后的原料電纜和工程中需要的電纜的種類數(shù)M＇、m＇以及數(shù)量P_i＇、p_j＇作為下一級優(yōu)化計算的初始參數(shù)；轉(zhuǎn)回步驟一依次向下執(zhí)行；若工程中需要的電纜數(shù)量p_j＇為零則停止計算；

步驟八、將得到的總體切割方案作為步驟三中R對應(yīng)的總體切割方案，命名為S1方案；

再在0.1~1范圍中分別取x次啟發(fā)參數(shù)R的值，分別重復(fù)x次執(zhí)行步驟一到步驟七，得到x種的總體切割方案，分別命名為S2、…、Sx，依次類推，其中x的范圍為5~10次；

步驟九、分別調(diào)用x次下述公式（9）得到x個F的值；

_?????????（9）

?????其中：N為每種總體切割方案中使用的原料根數(shù)，即每種總體切割方案中所有d_i的總和；

????為每種總體切割方案得出的余料總和，t_max為對應(yīng)的每種總體切割方案中的最長余料；

????比較x個F的值的大小，選取x種方案中使F最小時所對應(yīng)的R值，以此R作為為最優(yōu)切割方案的啟發(fā)參數(shù)，得出最終的電纜切割方案輸出。