變鄰域遺傳算法在車間物流調度中的應用①

楊海宴, 王淑營

(西南交通大學 信息科學與技術學院, 成都 611756)

隨著工業制造智能化的快速發展, AGV小車在智能制造車間得到越來越多的應用. AGV在車間中負責物流任務的轉運, 目前, 購買的AGV已具有安全避障、路徑規劃等功能. 但是, 不同AGV小車物流任務的選擇和每個小車運輸物流任務的順序會得到不同的總運輸路程和物流任務等待被轉運的時間, 進而影響車間的生產效率和經濟效益.

物流調度優化技術的關鍵是實現車間生產高效率、高靈活性和物流運輸成本最低. 即一方面降低工位等待運輸物流任務的時間, 保證物流任務運輸的及時性, 以可以充分利用車間的生產設備和保證生產車間高效平穩的工作. 另一方面優化物流任務配送路徑,使得轉運設備行駛最少的路程來滿足工位物流任務的運輸需求. 因此, 如何有效地使用調度優化算法, 以提高工位的滿意度, 并達到最低生產成本, 最大化運輸資源利用率, 是提高企業生產效率和經濟效益的重要方法.

制造車間物流調度通常會涉及多個優化目標, 如最小化單個物流任務配送成本[1]、最小化物流任務配送延遲時間[2]、最小化總能源消耗[3,4]等, 多個目標之間通常會存在競爭關系, 無法使多個目標同時達到最優, 即一個目標函數值的增加可能會導致其它目標函數值的降低. 對多目標問題進行優化時, 通常有兩種方式, 一是通過給每個目標函數設置一定的權值進行加權求和轉換為單目標問題, 二是求得Pareto最優解集[5].由于在優化過程中無法確定各目標函數的權值, 所以本文采用第二種方法進行多目標優化問題的研究.

近年來, 關于制造車間含AGV多目標調度優化已有大量的研究. 楊智飛等[6]基于遺傳算法, 融合差分進化算法同時優化完工時間、AGV數量和懲罰成本. 宋存利[7]提出了一種改進的NSGA-II算法實現了混合流水車間最小化能耗和最小化最大完工時間的求解.Mousavi等[8]設計了模糊混合遺傳粒子群算法, 以最小化最大完工時間和最小化AGV數量為目標函數構建模型, 對柔性制造系統(Flexible Manufacturing System,FMS)中的多目標AGV調度模型進行優化. Zhang等[9]提出一種基于實時多源制造數據的車間物料搬運動態優化方法, 設計開發了基于AGV小車、實時信息交換和物料搬運任務優化的動態優化模型, 根據小車的實時狀態, 將最優物流任務分配給最優小車. Zhang等[10]設計了基于變鄰域局部搜索策略的混合遺傳算法, 實現了包含最小化總加權拖期和最小化總能源消耗的作業車間調度問題求解. 張連超等[11]通過使用灰色理論來預測物料的需求時間, 并使用時間窗構建多模型交互機制以避免小車行駛過程中的碰撞問題. Umar等[12]設計了動態混合多目標進化算法, 研究FMS中作業和AGV的綜合調度, 制定作業調度計劃和確定AGV的行駛路徑. Lu等[13]提出一種混合多目標回溯搜索算法(Hybrid Multi-Objective Backtracking Search Algorithm,HMOBSA)實現置換流水車間最小化完工時間和最小化能耗的求解. 魏永來等[14]提出一種混合禁忌蝙蝠算法, 求解以AGV總行駛路程、總運輸時間和總配送成本為目標的多AGV作業車間調度優化問題. 劉二輝等[15]提出一種改進的花授粉算法實現車間最小化工件的最大完工時間和最大化AGV利用率的求解.

綜上所述, 制造車間中含AGV多目標調度優化已有大量研究, 但是已有研究中缺少對車間中一些實際因素的考慮, 建立的模型沒有同時考慮AGV的能耗、物流任務的優先級、物流任務間的物流成本和工位物流任務的滿意度對物流調度的影響, 與制造車間生產物流的實際情況不符. 此外, 目前混合變鄰域遺傳算法在車間物流調度優化問題方面的應用研究較少.

遺傳算法是一種基于自然進化和選擇機制的智能優化算法, 具有全局優化能力強、速度快、易于實現等優點, 但是其存在易早熟、早收斂等缺陷. 變鄰域搜索算法是基于鄰域結構集而非單個鄰域的局部搜索算法, 其基本思想是在搜索過程中系統地改變鄰域結構集來拓展搜索能力, 以提高算法局部搜索能力, 避免算法陷入局部最優, 比傳統的固定鄰域搜索的搜索能力更強[16], 已用于很多優化問題的求解.

因此, 本文結合遺傳算法全局搜索能力強的特點和變鄰域搜索算法局部搜索能力強的特點, 并添加保優記憶庫對精英個體進行保護, 設計了混合變鄰域搜索的改進遺傳算法VNSGA-II. 以最小化物流任務時間懲罰成本和最小化運載小車的總行駛距離為優化目標,構建離散化車間多目標物流調度優化模型. 由于初始種群的生成方式對算法的搜索效率和解質量有較大的影響, 本文改進了初始種群的生成方式, 以物流任務優先級從高至低排序和隨機生成相結合的方式生成初始種群. 在迭代過程中, 通過使用NSGA-II的虛擬適應度評估方法, 對種群中的個體進行非支配分層以及計算各層內個體間的擁擠距離, 以此評估個體的優劣. 并針對本文所構建模型的特點, 設計6個隨機搜索鄰域結構可有效提高解的質量, 促使種群快速跳出局部最優.由于在變鄰域搜索時會花費較多時間, 所以本文在種群最優解質量經過規定的迭代次數后沒有改進時, 才對當代最優解進行變鄰域搜索. 為了進一步降低物流成本和工位的滿意度, 提出了基于關鍵AGV小車的插入鄰域和基于關鍵物流任務的交換鄰域的調整策略以進一步優化模型.

1 問題描述與數學建模

1.1 問題描述

本文研究含多AGV的離散化車間物流調度優化問題, AGV在車間中負責物流任務的運輸. 某加工車間有k個工位, 根據生產作業排程結果和工件加工工藝的要求, 每個工件加工時間、加工刀具、工裝和所需物料已給定. 由于制造車間生產過程存在不確定性, 在物流配送環節, 隨著時間的推移, 各個工位的物流任務會發生變化.

每個工位有進料位和出料位, 車間中還額外設置一個公共緩沖區, 該公共緩沖區服務于所有加工工位.每個工位的進料位容量為cik, 出料位容量為cok, 當前一道工序的加工工位出料位容量達到上限, 需要將出料位的工件運走, 如果此時下一個工位的入料位已被占用, 則需要將工件運送到緩沖區. 當下一道工序的加工工位進料位有空閑時, 將工件從緩沖區運輸到下一個加工工位的進料位.

物料是裝在空載具中運輸的, 小車每次運輸一個載具的物料, 設有u種載具,nuy表 示載具u能 裝n個物料y. 本文的物流配送任務分為兩類: 主動物料配送是系統通過工位的生產加工實時數據, 計算工位原材料的消耗量, 進而得出加工工位進料位的剩余容量, 主動進行原材料的配送, 保證工位有合適數量的原材料, 又不會造成原材料到達工位沒有地方存放的死鎖情況, 確保了生產過程的正常運行； 準時化物料配送是根據工位的實時呼叫信息進行物料的配送, 包含了工件、刀具、工裝、成品和空載具. 物流調度目標為采用i輛小車根據需求將物料從物流起點運輸到物流終點, 使整個配送成本最低(由小車的行駛距離決定)和物流任務等待配送時間最短. 調度優化建模時做如下假設:

(1) 當小車被指派多個物流任務時, 小車完成一個任務后直接執行下一個任務.

(2) 車間中各站點之間的距離已知.

(3) 一個小車在同一時刻只能承擔一個物流任務.

(4) 小車一次只能運輸一個載具的物料.

(5) 一個載具只能裝載一個工位的物料.

(6) AGV行駛速度恒定, 其配送成本只和運行距離有關.

1.2 數學建模

為了貼近生產物流實際情況, 模型參數變量定義如表1所示.

表1 模型變量參數定義

1.2.1 物流任務計算

由于一個工位加工任務對應多個工件, 根據物流能力需要轉換為jk個 物流任務. 式(1)是所有加工工位所需原材料載具的計算公式是計算工位k需要的所有原材料數, 然后根據物料載具關系, 計算出該工位需要的原材料載具數jk. 小車每次運輸一個載具, 一個載具是一個物流任務. 式(2)為待運輸的物流任務集合, 是需要轉運的原材料和實時呼叫的物流任務的集合.

1.2.2 目標函數

為了實現制造車間生產效率的最大化, 并更好地控制配送成本. 車間物流調度需要滿足以下要求: ① 原材料按時配送, 使原材料的到達時間和需求時間之差最小. ② 實時呼叫的物流任務及時配送, 使物流任務等待運輸時間最小. ③ 運載小車的利用率高, 即運載小車行駛最少的路程滿足物流配送的需求. 基于此, 本文的目標函數由兩部分組成, 分別是最小化時間懲罰成本和最小化運載小車的總行駛距離.

(1) 時間懲罰成本

為避免加工設備出現停機等待物料這種情況, 通常要求物料的運輸時間早于或等于最遲運輸時間. 若物流任務的開始運輸時間早于或等于最遲運輸時間,則滿意度最高, 懲罰值為0. 若物流任務的開始運輸時間遲于最遲運輸時間, 則用延遲的時間和優先級的平方相乘, 得到時間懲罰成本. 因為, 優先級高的物流任務相較于優先級低的在實際生產中會帶來更大的損失.設小車運行速度為15 m/min, 根據該速度計算物流任務的運輸時間.

(2) 運載小車的總行駛距離

小車的總行駛距離由運輸物流任務的距離和完成上一個物流任務再去運輸下一個物流任務所需的距離所組成.

1.2.3 約束條件

根據物流調度優化的實際需求, 設定如下約束條件:

(1) 任意時刻小車使用數量不超過小車總數量.

(2) 每個工位的出料位和進料位容量大于等于1.

(3) 載具裝載的物料不大于載具的容量.

(4) 進料位容量限制, 工位進料位的實時存儲物料不超過其最大存儲量限制.

2 求解算法設計

針對制造車間物流調度問題, 設計的混合變鄰域搜索的改進遺傳算法偽代碼如算法1所示, 算法流程圖如圖1所示.

2.1 編碼設計

常見的染色體編碼方式有二進制編碼、自然數編碼、矩陣編碼和交叉編碼等. 由于本文研究問題為運輸小車任務的指派, 以及運輸小車任務的排序, 因此采用自然數編碼和交叉編碼相結合的方式. 染色體基因總數為偶數, 奇數位為小車編號, 偶數位為待運輸的物流任務, 每兩個基因組成一個基因片段, 每個基因片段表示小車i負責物流任務p的運輸. 例如: 待運輸的物流任務編號為{2, 9, 3, 5, 7, 8}, 可供使用的AGV小車編號為{1, 2}, 則一個可能的染色體為: {2, 2, 1, 9, 1, 3,2, 5, 1, 7, 2, 8}. 表示2, 9, 3, 5, 7, 8物流任務分別由2,1, 1, 2, 1, 2運輸. 即小車1按順序運輸載具9, 3, 7, 小車2按順序運輸載具2, 5, 8, 如圖2所示.

圖2 編碼設計

2.2 解碼方法和適應度函數設計

按照2.1節編碼設計規則對種群中每個染色體進行解碼, 解碼時根據物流任務編號找到其在車間所處對應的位置、優先級等相關信息.

以小車的總行駛距離、時間懲罰成本為優化目標建立的目標函數. 本文所優化問題為最小問題, 根據遺傳算法原理, 適應度函數值越高的個體越容易存活, 在迭代過程中適應度函數值低的染色體會被淘汰, 適應度函數值高的染色體被保留, 因此, 經過多次迭代, 染色體質量會越來越好. 因此, 適應度值采取目標函數值的倒數, 即目標函數值越小, 適應度值越大, 適應度函數與目標函數的關系表達式如式(9)所示:

式中,fiti表示群體中第i個體的適應度值,Yi表示第i個體的目標函數值,pop_size表示種群規模數.

算法 1. 混合變鄰域搜索的改進遺傳算法agv x distance輸入: AGV小車信息 , 待運輸物流任務信息, 車間中任意兩個位置之間的距離 .solution輸出: 每個AGV小車運輸的物流任務及順序 .agv_speed 參數: 為小車行駛速度.gen_no 變量: 初始為0.initialization() function1()function2() fast_sort() crowding_polution()save_elite() bi_cham() cross_over()mutation() compare_two_gen()var_nei_sear()select_chil()函數: 種群初始化 , 適應度值1 , 適應度值2, 種群非支配排序 , 擁擠度計算 ,精英個體保留 , 選擇操作 , 交叉操作 ,變異操作 , 兩個染色體優劣比較 , 變鄰域搜索 , 選擇子代個體.solution initialization(agv,x,pop_size) = //產生初始種群gen_no max_gen while ＜ do i=0 pop_size for to f1←function1(solutioni,x,distance,agv_speed) //計算種群個體適應度值1 f2←function2(solutioni,x,agv) //計算種群個體適應度值2 end for non_dominated_sort fast_sort(f1,f2) = //種群之間進行快速非支配性排序, 得到非支配性排序集合j non_dominated_sort for in do crowd_distance←crowding_polution(f1,f2,non_dominated_sortj) //計算非支配集合中每個個體的擁擠度 end for elite_indivi=save_elite(elite_size) //保留精英個體selected_solutioin=bi_cham(solution) //選擇操作selected_solutioin for 的每兩個元素 do cross_solution←cross_over(solution1,solution2) //交叉操作 end for n cross_solution for in do mutation_solution←mutation(cross_solutioni) //變異操作 end for solution←mutation_solution //父代、子代個體合并compare_two_gen(solution0,elite_indivi0) if not then //新種群的最優解相較于精英庫的最優解是否有改進noimpro+=1 end if noimpro＞noimpro_max noimpro_max if then //種群最優解已有 代沒有改進var_nei_sear(solution0) //對最優個體執行變鄰域搜索 end if solution=select_chil(solution,elite_indivi) //通過帕累托等級和擁擠距離選擇子代種群noimpro＞noimpro_max noimpro_max if then //種群最優解已有 代沒有改進solution=solution[0,pop_size/2]initialization(agv,x,pop_size/2) +

1/2×(pop_size)//對種群進行擾動, 保證迭代過程中個體的多樣性, 生成大小為的個體替換子代適應度較低的個體 end if gen_no+=1 end while solution0循環最優解 , 得到每個小車的物流任務及順序

2.3 初始種群的生成

初始種群以物流任務優先級從高至低排序和隨機生成相結合的方式生成.

以隨機生成方式產生初始種群的具體步驟如下:

步驟 1. 根據可調用的小車編號, 確定小車的集合I.

步驟 2. 用生成隨機數的方法從指定集合I中對染色體的每個基因產生隨機數xi∈I, 染色體基因個數等于待運輸物流任務數X.

步驟 3. 在生成的染色體每一位基因后面隨機插入一位新的基因, 表示物流任務編號, 染色體長度擴展為2P, 染色體擴展方法如圖3所示.

圖3 初始種群的生成

步驟 4. 重復以上步驟, 產生大小為pop_size的初始種群.

以物流任務優先級從高至低排序產生初始種群的具體步驟如下:

步驟 1. 將所有物流任務按照優先級進行降序排序(優先級最高為4).

步驟 2. 隨機打亂小車編號的順序.

步驟 3. 循環小車編號列表和物流任務編號列表,當循環至最后一個小車編號時, 改變索引至第一個小車, 直至遍歷完所有的物流任務, 每一次取出小車編號和物流任務編號, 小車編號后面跟著物流任務編號.

步驟 4. 染色體的大小為2倍物流任務長度. 重復執行上述操作pop_size遍 , 生成規模為pop_size的初始種群.

2.4 交叉算子

選擇操作采用二元錦標賽選擇的方法按照概率選擇適應度值較高的染色體參與遺傳操作. 為了產生不同小車物流任務的分配方案, 通過交叉操作來增大物流任務分配解空間的搜索范圍. 首先從種群中選出兩個染色體, 對于偶數位, 將染色體的某一個位置切斷,將交叉位置前的染色體片段加到對方染色體個體前面,并刪除對方染色體中偶數位與交叉位置前染色體片段偶數位相同的值及對應前一位的奇數位. 對奇數位, 為每個奇數位生成一個隨機數, 根據隨機數的大小決定哪個父染色體貢獻哪些奇數位的基因, 即隨機數大的貢獻給子染色體1, 隨機數小的貢獻給子染色體2, 如圖4所示.

2.5 變異算子

為了維持種群的多樣性以防止算法過早收斂, 采用變異操作提高算法的局部搜索能力. 傳統的變異算子是選擇若干個基因位, 然后隨機修改基因的值, 變異后會出現非法解. 本文采用改進的變異算子, 如圖5所示. 改進的變異算子是對偶數位進行變異操作, 獲取染色體奇數位的基因值, 記為a, 尋找基因值與a相等的奇數位基因, 將該奇數位基因后一位與變異基因交換, 并將已變異的基因標記, 以不再進行第二次變異. 這一操作是改變同一個小車執行物流任務的順序.

圖5 變異操作

2.6 精英保留策略

傳統遺傳算法中交叉、變異算子的作用個體均來自于子代種群, 該方法有一個明顯缺點: 種群進化中優秀的個體得不到保護以致在下一輪迭代中易破壞. 因此, 通過使用保優記憶庫更新策略來解決這一問題, 在每一代迭代結束后, 將保優記憶庫中的精英個體合并到當代得到的新種群中, 合并的規則是若保優記憶庫中的解和新種群的解兩個目標函數均相同,則只選擇一個. 然后通過精英選擇策略選擇規模為elite_size的個體加入庫中進行保護, 精英選擇策略是首先進行帕累托分層得到每個個體的帕累托等級并計算每層個體之間的擁擠距離, 優先選擇帕累托等級低的個體, 若多個個體帕累托等級相同, 則選擇擁擠距離較大的個體.

2.7 變鄰域搜索算法

由于遺傳算法求解過程中容易陷入局部最優解,因此采用變鄰域搜索策略來解決這一問題. 其思想是首先從最小鄰域開始搜索解空間得到一個局部最優解.然后通過系統地改變鄰域結構, 基于該局部最優解, 重新從最小鄰域開始搜索得到下一個局部最優解. 變鄰域搜索算法是基于鄰域結構集而非單一鄰域結構, 因此, 比固定鄰域結構的算法搜索能力更強. 變鄰域搜索算法偽代碼如算法2所示, 流程如圖6所示.

圖6 變鄰域搜索流程

針對本文模型特點, 設計6個隨機鄰域結構搜索機制, 具體如下:

(1) 3種同一小車內搜索策略, 即通過一定的規則改變同一個小車運輸物流任務的順序.

① swap算子

任意交換同一個小車的物流任務, 對同一個小車,隨機選取兩個節點, 交換兩個節點. 如圖7(a)所示.

算法 2. 變鄰域搜索算法輸入: 初始解ori_gen vns_gen 輸出: 變鄰域搜索后的解k,m變量: ,初始值為1 compare()函數: 比較新解和初始解的目標函是否相等k≤k_max while do vns_gen=select_vns(ori_gen,m) Vm ori_gen vns_gen //按照鄰域結構 對解 進行變鄰域搜索, 隨機產生新解compare(ori_gen,vns_gen) ori_gen vns_gen if //若 的目標函數1和目標函數2均小于ori_gen=vns_gen //替換解m=1 //基于當前局部最優解重新從最小鄰域開始搜索找到下一局部最優解 else m＜m_max m if //若 未達到最大鄰域結構數m+=1 else m=1 end if end if end while

② 2-opt算子

對某一個小車, 隨機選取兩個不相鄰的節點, 然后翻轉兩個節點之間的節點, 得到新染色體, 如圖7(b)所示.

③ or-opt算子

將同一個小車相鄰的兩個物流任務一起移動到其他位置. 即隨機選取同一個小車的兩個相鄰的位置, 隨機選擇該小車的一個物流任務作為一個插入節點, 并在移動后保持相鄰, 如圖7(c).

圖7 同一小車內搜索策略

(2) 3種不同小車間搜索策略, 即通過一定的規則改變兩個小車的物流任務.

① swap算子

隨機選擇兩個小車, 在小車1和小車2分別隨機選取兩個小車的一個物流任務, 交換這兩個節點, 如圖8(a)所示.

② relocate算子

隨機選取兩個小車, 隨機選取小車1的一個物流任務m, 隨機選取小車2的一個物流任務n, 將小車1的物流任務m移動到小車2物流任務n后的位置, 如圖8(b)所示.

③ or-opt算子

將其中一個小車的相鄰兩個物流任務移動到另一個小車, 如圖8(c)所示.

圖8 不同小車間搜索策略

為了進一步降低物流成本和提高工位滿意度, 設計基于關鍵AGV小車的插入鄰域、基于關鍵物流任務的交換鄰域的調整策略, 具體如下:

(1) 基于關鍵AGV小車的插入鄰域

將總行駛距離最大的AGV定義為關鍵AGV小車, 表示為Imain, 最大距離記為L. 通過將Imain的物流任務分配給其它AGV, 可以均衡每輛AGV的任務量, 同時會降低運輸所有物流任務的最大完成時間. 該鄰域結構具體描述為: 遍歷選擇Imain中的物流任務插入到其它AGV的物流任務序列中, 若插入后L和兩個目標函數值均降低了, 則接受該物流任務移動, 否則重新選擇Imain中的物流任務插入序列, 直到選擇Imain中的所有物流任務.

(2) 基于關鍵物流任務的交換鄰域

將小車i運輸完物流任務p再去運輸物流任務q的空載行駛距離sipq最大的物流任務定義為關鍵物流任務, 表示為Qmain. 通過將Qmain和其它物流任務進行交換, 可降低AGV的空載行駛距離, 使AGV的利用率最大. 該鄰域結構具體描述為: 將Qmain與其它物流任務依次交換, 若所有AGV的總空載距離和兩個目標函數值均降低了, 則接受該物流任務的交換, 否則重新選擇其它物流任務, 直到選擇了所有的物流任務.

3 數值實驗與分析

3.1 實驗相關數據

(1) 案例設計

本文以某離散車間為例驗證算法的有效性. 車間中任意兩個位置之間的距離值如表2所示, 車間布局如圖9所示, AGV小車的物流路徑在圖中已用實線標明, 每條路徑同時可有兩輛AGV小車通行, 其中共有8個加工工位、1個原材料庫、1個緩沖區、1個成品庫、1個刀具庫和1個工裝庫, 在程序中依次從左向右轉換為0至12的編號. 物流任務在車間中的流轉均由AGV小車運輸.

圖9 車間布局示意圖

表2 車間中任意兩個位置之間的距離值(m)

(2) 算法相關參數設置如表3所示.

表3 算法相關參數設置

(3) 物流任務的實時信息模型

為了更好地進行管理和數據交換, 模型的輸入一共包含兩部分. 第一部分是運載小車的信息, 分別是可調用小車編號和小車完成當前正在執行任務后的位置. 第二部分是待物流任務的信息, 每個物流任務的信息包括:任務id、任務起始位置、任務終止位置、任務優先級、任務最晚運輸時間.X個任務的信息存儲在矩陣X中, 如式(10)所示, 其中idp表 示物流任務的編號,fp表示物流任務的起始位置,ep表示物流任務的終止位置,ap表 示任務的優先級,stp表示任務的最晚運輸時間.

在優先級的定義中, 1 代表“普通任務”, 2 代表“重要任務”, 3代表“緊急任務”, 4代表“更緊急任務”.

為了驗證本文模型和算法的有效性, 隨機構造一個實驗案例, 如表4和表5. 最晚運輸時間在區間[0,60]中隨機產生.

表4 待運輸物流任務信息

表5 AGV小車信息

3.2 實驗結果分析

與單目標優化算法不同, 多目標優化結果通常不是單個最優解, 而是一個Pareto最優解集. 根據本文車間物流調度需求, 算法需要確定每個AGV小車運輸的物流任務, 及運輸每個物流任務的順序. 本文是從最優解集中根據兩個目標函數的和選取最優解.

為了驗證本文設計的VNSGA-II算法求解的有效性, 在本文設計的案例條件下與兩種經典的多目標優化算法NSGA-II, SPEA2的優化結果進行實驗分析.3種算法實驗條件及參數相同, 采用Python語言完成上述算法的編程, 3種算法分別運行20次, 生成的Pareto最優解集如圖10所示, 算法優化結果分析如表6和表7所示, 其中在表6中f1和f2分別表示時間懲罰成本和運載小車的總行駛距離.

圖10 不同算法Pareto前沿分布

由表6可知, VNSGA-II的優化結果在兩個目標函數: 時間懲罰成本和運載小車的總行駛距離上在最優解和平均解上均優于NSGA-II和SPEA2. 因本文研究的問題是最小問題, 即兩個目標函數值越小越好, 由圖10可以看出, 本文設計的VNSGA-II算法得到的Pareto最優解更多, 在解的質量上總體比NSGA-II和SPEA2更好. 表7是3個算法運行的最優解AGV的物流任務分配情況及轉運順序和每個行駛小車的總空載距離. 因此, 從以上實驗可以看出本文設計的算法在保持運輸物流任務延遲時間較低的情況下, 有效降低了運載小車的總行駛距離和空載距離, 既縮短了物流任務的搬運時間又節省了車間的物流成本.

表6 算法結果對比

表7 運行結果對比

4 結束語

本文以制造車間物流調度為實際背景, 建立多目標優化模型, 針對該問題設計了求解多目標的VNSGA-II算法, 該算法包含遺傳算法的基本操作, 并對最優解集進行變鄰域搜索. 通過實驗, 結果表明:

(1) 模型考慮物流任務的時間懲罰成本和AGV小車的總行駛距離兩個方面, 有效地平衡了車間的生產效率和車間的生產成本, 具有較強的實用性.

(2) 與兩種多目標經典優化算法NSGA-II和SPEA2的實驗結果對比表明, VNSGA-II算法在求解質量上均優于NSGA-II和SPEA2.