[發(fā)明專利]基于快速離散煙花算法的電纜配送路徑規(guī)劃方法、裝置和計(jì)算設(shè)備

在審

• 申請(qǐng)?zhí)枺?/td>: 202011406975.6
• 申請(qǐng)日: 2020-12-04
• 公開（公告）號(hào): CN112446548A
• 公開（公告）日: 2021-03-05
• 發(fā)明（設(shè)計(jì)）人: 戚遠(yuǎn)航;黃戈文;楊亮;黃子峻;許暢
• 申請(qǐng)（專利權(quán)）人: 電子科技大學(xué)中山學(xué)院
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04;G06Q10/08;G06N3/00
• 代理公司: 廣州國(guó)鵬知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 44511
• 代理人: 夏瓊瓊

本發(fā)明是關(guān)于一種基于快速離散煙花算法的電纜配送路徑規(guī)劃方法、裝置和計(jì)算設(shè)備，本發(fā)明采用整數(shù)編碼的路徑表示方法來表示離散問題的解，對(duì)爆炸算子、高斯變異算子和選擇策略進(jìn)行離散化操作策略設(shè)計(jì)，其中爆炸算子改為inert?swap爆炸算子，高斯變異算子改為2?swap高斯變異算子，選擇策略采用基于適應(yīng)度的輪盤賭選擇。算法采用3?Opt局部搜索，引入固定半徑近鄰搜索加強(qiáng)3?Opt算法的鄰域搜索能力，采用不檢測(cè)標(biāo)識(shí)策略，提高電纜配送路徑規(guī)劃效率。

技術(shù)領(lǐng)域

本發(fā)明涉及物流調(diào)度技術(shù)領(lǐng)域，尤其涉及基于快速離散煙花算法的電纜配送路徑規(guī)劃方法、裝置和計(jì)算設(shè)備。

背景技術(shù)

相關(guān)技術(shù)中，為了滿足客戶的需求，電纜供應(yīng)商需要從電纜倉(cāng)儲(chǔ)點(diǎn)搬運(yùn)電纜，然后往多個(gè)電纜接貨點(diǎn)，最后車輛回到出發(fā)點(diǎn)。由于電纜型號(hào)眾多，客戶對(duì)產(chǎn)品的交付要求也越來越高，電纜企業(yè)有效地規(guī)劃電纜配送路徑，可提高客戶滿意度，使電纜企業(yè)的成本降低。煙花算法模擬煙花爆炸保持火花多樣性的機(jī)制，對(duì)問題解空間進(jìn)行兩種機(jī)制搜索，具有良好的全局搜索能力。在這種機(jī)制下，算法具有收斂快、尋優(yōu)能力強(qiáng)的特點(diǎn)，并且具有較好的全局搜索能力，而且控制參數(shù)少，實(shí)現(xiàn)容易。由于煙花算法的這些特點(diǎn)，可以將煙花算法運(yùn)用于劃電纜配送路徑的解決。

發(fā)明內(nèi)容

為克服相關(guān)技術(shù)中存在的問題，本發(fā)明提供一種基于快速離散煙花算法的電纜配送路徑規(guī)劃方法、裝置和計(jì)算設(shè)備，本方法采用整數(shù)編碼的路徑表示方法來表示離散問題的解，對(duì)爆炸算子、高斯變異算子和選擇策略進(jìn)行離散化操作策略設(shè)計(jì)，采用引入固定半徑近鄰搜索加強(qiáng)最優(yōu)路徑算法的鄰域搜索能力，采用不檢測(cè)標(biāo)識(shí)策略，提高電纜配送路徑規(guī)劃效率。

根據(jù)本發(fā)明實(shí)施例的第一方面，提供一種基于快速離散煙花算法的電纜配送路徑規(guī)劃方法，包括：

將電纜配送車輛遍歷訪問每個(gè)接貨點(diǎn)編號(hào)的序列設(shè)置為煙花算法中的煙花個(gè)體以生成煙花原始種群；

計(jì)算煙花原始種群中所有個(gè)體適應(yīng)度；

原始種群中每個(gè)煙花個(gè)體中一個(gè)隨機(jī)位置的接貨點(diǎn)編號(hào)插入在煙花個(gè)體中的另一個(gè)隨機(jī)位置來執(zhí)行爆炸算子操作得到爆炸火花；

每個(gè)煙花個(gè)體按照高斯爆炸隨機(jī)數(shù)次高斯爆火花操作，生成一個(gè)高斯爆火花，其中，高斯爆火花操作是隨機(jī)選擇煙花個(gè)體中兩個(gè)接貨點(diǎn)編號(hào)，翻轉(zhuǎn)兩個(gè)接貨點(diǎn)的中間的序列生成高斯爆炸火花；

計(jì)算新產(chǎn)生的爆炸火花和高斯爆火花的適應(yīng)度，根據(jù)新的爆炸火花和高斯爆火花的適應(yīng)度在煙花、爆炸火花、高斯爆火花中選取下一代煙花；

采用固定半徑近鄰搜索策略和不重復(fù)搜索策略的最優(yōu)路徑算法得到此次迭代的最優(yōu)解，如得到的最優(yōu)解優(yōu)于原最優(yōu)路徑算法的結(jié)果，則更新最優(yōu)解；

迭代數(shù)達(dá)到最大預(yù)設(shè)次數(shù)，則將本次迭代結(jié)果作為最優(yōu)電纜配送路徑。

所述方法還包括：計(jì)算新產(chǎn)生的爆炸火花和高斯爆火花的適應(yīng)度，在煙花、爆炸火花、高斯爆火花中選取下一代煙花，包括：在煙花種群、爆炸火花和高斯變異火花中選擇最優(yōu)的個(gè)體作為下一代煙花種群，其余下一代煙花種群按照賭輪盤規(guī)則在原本煙花種群、爆炸火花和高斯變異火花中選出。

其中，原始種群中每個(gè)煙花個(gè)體中一個(gè)隨機(jī)位置的接貨點(diǎn)編號(hào)插入在煙花個(gè)體中的另一個(gè)隨機(jī)位置來執(zhí)行爆炸算子操作得到爆炸火花，包括：

所述假設(shè)煙花個(gè)體為x_i，首先根據(jù)第一預(yù)設(shè)公式計(jì)算煙花的爆炸火花數(shù)R_i，根據(jù)第二預(yù)設(shè)公式計(jì)算爆炸半徑D_i，然后在煙花x_i解空間中進(jìn)行D_i次爆炸算子操作，得到一個(gè)爆炸火花，重復(fù)R_i次產(chǎn)生R_i個(gè)爆炸火花；

第一預(yù)設(shè)公式為：

第二預(yù)設(shè)公式為：