[發(fā)明專利]求解矩陣制造車間多自動軌道小車上料調(diào)度問題的人工蜂群算法

有效

• 申請?zhí)枺?/td>: 202010881510.X
• 申請日: 2020-08-27
• 公開（公告）號: CN112149876B
• 公開（公告）日: 2023-07-18
• 發(fā)明（設(shè)計(jì)）人: 潘全科;鄒溫強(qiáng);王玉龍
• 申請（專利權(quán)）人: 上海大學(xué)
• 主分類號: G06Q10/047
• 分類號: G06Q10/047;G06Q10/0631;G06Q10/083;G06N3/006
• 代理公司: 上海上大專利事務(wù)所(普通合伙) 31205
• 代理人: 何文欣

1.一種求解矩陣制造車間多自動軌道小車上料調(diào)度問題的人工蜂群算法，其特征在于，操作步驟如下：

（1）采用新的解的表示方法：

假設(shè)矩陣制造車間有n個(gè)任務(wù)單元和m輛AGV，將用長度為n+m-1的向量來表示解；在此向量中，1和n之間的n個(gè)自然數(shù)表示任務(wù)單元的編號，○表示倉庫點(diǎn)，m-1個(gè)○表示每條AGV路線的起點(diǎn)，也是終點(diǎn)；任意兩個(gè)相鄰的AGV路線由○隔開；

（2）采用改進(jìn)的最近鄰啟發(fā)式算法：

首先設(shè)定倉庫點(diǎn)為AGV出發(fā)的起點(diǎn)和終點(diǎn)，然后選擇一輛編號為1#的AGV，以倉庫點(diǎn)為當(dāng)前點(diǎn)搜索一個(gè)距離它最小的任務(wù)單元i，并將它插入到1#AGV路線的最前端，接下來以任務(wù)單元i為當(dāng)前點(diǎn)尋找距離它最小的任務(wù)單元j，并將它插入到1#AGV路線的第二個(gè)位置；

以此類推，直到滿足AGV的載重約束和任務(wù)單元的時(shí)間窗約束為止，將結(jié)束1#AGV路線的任務(wù)單元分配，并立即開始2#AGV路線的任務(wù)單元分配工作；當(dāng)所有的任務(wù)單元分配到AGV們時(shí)，將得到一個(gè)解，即任務(wù)單元到AGV的分配方案；

（3）采用人工蜂群算法：

步驟31：從平衡初始解的優(yōu)質(zhì)性和多樣性角度出發(fā)，利用改進(jìn)的最近鄰啟發(fā)式算法，生成一個(gè)高質(zhì)量初始解，利用隨機(jī)生成的方法，生成剩余的初始解；

步驟32：在雇傭蜂階段提出5個(gè)有效的鄰域算子：合并鄰域算子、路線內(nèi)插入鄰域算子、路線間插入鄰域算子、路線內(nèi)交換鄰域算子和路線間交換鄰域算子，鄰域算法在雇傭蜂階段隨機(jī)采用合并鄰域算子、路線內(nèi)插入鄰域算子、路線間插入鄰域算子、路線內(nèi)交換鄰域算子和路線間交換鄰域算子中的一種進(jìn)行鄰域搜索，來生成高質(zhì)量的解；

步驟33：提出了一個(gè)基于隨機(jī)插入的局部搜索方法，利用該方法使當(dāng)前解在偵查蜂階段進(jìn)入一個(gè)更有希望的解空間搜索中，生成一個(gè)好的解來替換偵查蜂階段中未改進(jìn)次數(shù)最多的解，從而節(jié)約經(jīng)典人工蜂群算法中隨機(jī)生成的解進(jìn)化成優(yōu)質(zhì)解的運(yùn)算時(shí)間；

基于隨機(jī)插入的局部搜索算法為：

每一步都會隨機(jī)選擇一個(gè)任務(wù)單元，將其插入到當(dāng)前AGV路線的最佳位置，當(dāng)當(dāng)前AGV路線不能接受新的任務(wù)單元時(shí)，算法將結(jié)束當(dāng)前AGV路線的任務(wù)單元分配工作，并以相同方法開始一條新的AGV路線的任務(wù)單元分配工作，直到所有任務(wù)單元分配完成為止。

2.如權(quán)利要求1所述求解矩陣制造車間多自動軌道小車上料調(diào)度問題的人工蜂群算法，其特征在于：所述的步驟（1）中，用長度為n+m-1的向量來表示解，來區(qū)分各條AGV路線，進(jìn)行各條AGV路線間的任務(wù)單元的鄰域優(yōu)化操作。

3.如權(quán)利要求1所述求解矩陣制造車間多自動軌道小車上料調(diào)度問題的人工蜂群算法，其特征在于：所述的步驟（2）中，所有AGV都是從倉庫出發(fā)，最后完成任務(wù)返回倉庫；對于每個(gè)AGV來說，都是通過將距離當(dāng)前任務(wù)單元最近的任務(wù)單元作為下一個(gè)服務(wù)的任務(wù)單元，如果符合AGV載重約束和任務(wù)單元的時(shí)間窗約束，則將其插入到AGV路線中，直到所有任務(wù)單元分配完成為止。