[發(fā)明專利]一種基于耦合算法的多林區(qū)航線調(diào)度規(guī)劃方法

有效

• 申請?zhí)枺?/td>: 202110555186.7
• 申請日: 2021-05-21
• 公開（公告）號: CN113222264B
• 公開（公告）日: 2022-03-18
• 發(fā)明（設(shè)計）人: 茹煜;方樹平;劉洋洋;李建平;劉彬;陳旭陽;夏達(dá)明
• 申請（專利權(quán)）人: 南京林業(yè)大學(xué)
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/02;G06N3/12;G01C21/20
• 代理公司: 蕪湖市昌強(qiáng)專利代理事務(wù)所(特殊普通合伙) 34203
• 代理人: 周渭銘

1.一種基于耦合算法的多林區(qū)航線調(diào)度規(guī)劃方法，其特征在于：包括如下步驟：

S1、算法開始，設(shè)置模擬退火算法的降溫速率q、初始溫度T₀、結(jié)束溫度T_end以及鏈長L；

S2、采用產(chǎn)生隨機(jī)排列的方法產(chǎn)生一個初始作業(yè)路徑順序S₁，將該順序作為模擬退火算法的一個初始解；

S3、計數(shù)器count＝0；

S4、將k＝1；

S5、采用解變換、變異、逆轉(zhuǎn)三種方式得到3個新解，以3個新解的作業(yè)順序路徑長度最小者作為新解S₂；

S6、根據(jù)Metropolis準(zhǔn)則判斷是否接受新解；作業(yè)順序路徑采用片區(qū)之間的距離鄰域表進(jìn)行計算，以各片區(qū)進(jìn)出入點(diǎn)連線的中點(diǎn)為計算基準(zhǔn)點(diǎn)；記當(dāng)前作業(yè)順序路徑長度為f(S),新解的作業(yè)順序路徑長度為f(S₂),路徑差為df＝f(S₂)-f(S₁),則Metropolis準(zhǔn)則為

若df 0，則以概率1接受新的作業(yè)順序路徑；否則以概率exp(1-df/T)接受新的路徑；

S7、得到新解S₁，并將k＝k+1；

S8、判斷kL，如果是，將進(jìn)行S9，否則返回S5；

S9、執(zhí)行count＝count+1，T＝qT；利用降溫速率q進(jìn)行降溫；

S10、判斷T是否小于T_end，如果是，就執(zhí)行S11，否則執(zhí)行S4；

S11、輸出作業(yè)順序路徑解集；

S12、設(shè)置第二層遺傳算法種群大小、交叉概率、變異概率，第二層算法最大迭代次數(shù)GENMAX，并將迭代次數(shù)初值置1，即gen＝1；

S13、第二層遺傳算法初始化種群Chrom2，采用二進(jìn)制編碼的方式；

S14、計算第二層算法的適應(yīng)度值，將飛機(jī)起降點(diǎn)看成2個點(diǎn)，但將坐標(biāo)定為同一數(shù)值，以方便快速利用鄰域表計算適應(yīng)度值，從飛機(jī)起降點(diǎn)出發(fā)的考慮各片區(qū)進(jìn)出點(diǎn)的全局區(qū)域間調(diào)度航線；適應(yīng)度f2設(shè)計為針對每一種進(jìn)出入狀態(tài)下第一層算法得到的所有全局區(qū)域間調(diào)度航線的最短距離的倒數(shù)；

S15、對種群Chrom2中進(jìn)行選擇、交叉、變異操作；然后重新插入后得更新后種群Chrom2；

S16、檢測迭代次數(shù)是否超過最大迭代次數(shù)GENMAX，當(dāng)?shù)螖?shù)未超過最大迭代次數(shù)時，返回步驟S14，否則進(jìn)行步驟S17；

S17、輸出最短的全局區(qū)域間調(diào)度路徑，該最短調(diào)度路徑即為多林區(qū)航線調(diào)度規(guī)劃的最佳調(diào)度方案。

2.如權(quán)利要求1所述基于耦合算法的多林區(qū)航線調(diào)度規(guī)劃方法，其特征在于：所述步驟S9中的遺傳算法種群中的種群大小設(shè)置為林區(qū)數(shù)與飛機(jī)起降點(diǎn)之和的4～6倍，代溝設(shè)置為常數(shù)，交叉概率P_c和變異概率P_m均設(shè)計為動態(tài)變化概率。

3.如權(quán)利要求2所述基于耦合算法的多林區(qū)航線調(diào)度規(guī)劃方法，其特征在于：代溝設(shè)置為0.9～0.95。

4.如權(quán)利要求1所述基于耦合算法的多林區(qū)航線調(diào)度規(guī)劃方法，其特征在于：交叉概率隨迭代次數(shù)增大而減小，變異概率隨迭代次數(shù)增大而減小；其計算公式為：

5.如權(quán)利要求1所述基于耦合算法的多林區(qū)航線調(diào)度規(guī)劃方法，其特征在于：P_cmin＝0.6，P_cmax＝0.9，P_m0＝0.1。