[發明專利]基于快速離散煙花算法的電纜配送路徑規劃方法、裝置和計算設備

在審

• 申請號: 202011406975.6
• 申請日: 2020-12-04
• 公開（公告）號: CN112446548A
• 公開（公告）日: 2021-03-05
• 發明（設計）人: 戚遠航;黃戈文;楊亮;黃子峻;許暢
• 申請（專利權）人: 電子科技大學中山學院
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06N3/00
• 代理公司: 廣州國鵬知識產權代理事務所(普通合伙) 44511
• 代理人: 夏瓊瓊

1.基于快速離散煙花算法的電纜配送路徑規劃方法，包括：

將電纜配送車輛遍歷訪問每個接貨點編號的序列設置為煙花算法中的煙花個體以生成煙花原始種群；

計算煙花原始種群中所有個體適應度；

原始種群中每個煙花個體中一個隨機位置的接貨點編號插入在煙花個體中的另一個隨機位置來執行爆炸算子操作得到爆炸火花；

每個煙花個體按照高斯爆炸隨機數次高斯爆火花操作，生成一個高斯爆火花，其中，高斯爆火花操作是隨機選擇煙花個體中兩個接貨點編號，翻轉兩個接貨點的中間的序列生成高斯爆炸火花；

計算新產生的爆炸火花和高斯爆火花的適應度，根據新的爆炸火花和高斯爆火花的適應度在煙花、爆炸火花、高斯爆火花中選取下一代煙花；

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

迭代數達到最大預設次數，則將本次迭代結果作為最優電纜配送路徑。

2.根據權利要求1所述的方法，還包括：計算新產生的爆炸火花和高斯爆火花的適應度，在煙花、爆炸火花、高斯爆火花中選取下一代煙花，包括：在煙花種群、爆炸火花和高斯變異火花中選擇最優的個體作為下一代煙花種群，其余下一代煙花種群按照賭輪盤規則在原本煙花種群、爆炸火花和高斯變異火花中選出。

3.根據權利要求1所述的方法，其中，原始種群中每個煙花個體中一個隨機位置的接貨點編號插入在煙花個體中的另一個隨機位置來執行爆炸算子操作得到爆炸火花，包括：

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

第一預設公式為：

第二預設公式為：

其中，R為預設置的爆炸火花數，f_max與f_min分別為N個原始煙花群中的最大、最小適應度值，D為算法基本爆炸半徑，加入ε用于避免出現除零的情況。

4.根據權利要求1所述的方法，其中，隨機選擇煙花個體中兩個接貨點編號，翻轉兩個接貨點的中間的序列生成高斯爆火花，包括：

在當前煙花原始種群中隨機選擇一個煙花，假設為x_i，按第三預設公式計算g，然后在x_i解空間中進行g次高斯爆火花操作，最終結果生成一個高斯爆火花；

第三預設公式如下：

其中e～N(1,1),N(1,1)為均值方差均為1的高斯分布。

5.根據權利要求1所述的方法，其中，所有煙花原始種群以及爆炸火花、高斯爆火花中選出最優的個體作為下一代原始煙花，包括：

在所有煙花原始種群以及爆炸火花、高斯爆火花中選出最優的n個個體作為下一代原始煙花，剩余(N-n)個煙花根據第四預設公式分別計算其輪盤選擇概率，本文n取1，其中煙花之間的距離由公式第五預設公式計算；

第四預設公式如下：

其中，d(x_i-x_j)表示煙花x_i與x_j之間的距離，所以表示煙花x_i與其他煙花的距離之和；

第五預設公式如下：

其中x_ik為x_i的第k個接貨點編號，K為接貨點數量。