楊海宴, 王淑營(yíng)

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

隨著工業(yè)制造智能化的快速發(fā)展, AGV小車在智能制造車間得到越來(lái)越多的應(yīng)用. AGV在車間中負(fù)責(zé)物流任務(wù)的轉(zhuǎn)運(yùn), 目前, 購(gòu)買的AGV已具有安全避障、路徑規(guī)劃等功能. 但是, 不同AGV小車物流任務(wù)的選擇和每個(gè)小車運(yùn)輸物流任務(wù)的順序會(huì)得到不同的總運(yùn)輸路程和物流任務(wù)等待被轉(zhuǎn)運(yùn)的時(shí)間, 進(jìn)而影響車間的生產(chǎn)效率和經(jīng)濟(jì)效益.

物流調(diào)度優(yōu)化技術(shù)的關(guān)鍵是實(shí)現(xiàn)車間生產(chǎn)高效率、高靈活性和物流運(yùn)輸成本最低. 即一方面降低工位等待運(yùn)輸物流任務(wù)的時(shí)間, 保證物流任務(wù)運(yùn)輸?shù)募皶r(shí)性, 以可以充分利用車間的生產(chǎn)設(shè)備和保證生產(chǎn)車間高效平穩(wěn)的工作. 另一方面優(yōu)化物流任務(wù)配送路徑,使得轉(zhuǎn)運(yùn)設(shè)備行駛最少的路程來(lái)滿足工位物流任務(wù)的運(yùn)輸需求. 因此, 如何有效地使用調(diào)度優(yōu)化算法, 以提高工位的滿意度, 并達(dá)到最低生產(chǎn)成本, 最大化運(yùn)輸資源利用率, 是提高企業(yè)生產(chǎn)效率和經(jīng)濟(jì)效益的重要方法.

制造車間物流調(diào)度通常會(huì)涉及多個(gè)優(yōu)化目標(biāo), 如最小化單個(gè)物流任務(wù)配送成本[1]、最小化物流任務(wù)配送延遲時(shí)間[2]、最小化總能源消耗[3,4]等, 多個(gè)目標(biāo)之間通常會(huì)存在競(jìng)爭(zhēng)關(guān)系, 無(wú)法使多個(gè)目標(biāo)同時(shí)達(dá)到最優(yōu), 即一個(gè)目標(biāo)函數(shù)值的增加可能會(huì)導(dǎo)致其它目標(biāo)函數(shù)值的降低. 對(duì)多目標(biāo)問題進(jìn)行優(yōu)化時(shí), 通常有兩種方式, 一是通過給每個(gè)目標(biāo)函數(shù)設(shè)置一定的權(quán)值進(jìn)行加權(quán)求和轉(zhuǎn)換為單目標(biāo)問題, 二是求得Pareto最優(yōu)解集[5].由于在優(yōu)化過程中無(wú)法確定各目標(biāo)函數(shù)的權(quán)值, 所以本文采用第二種方法進(jìn)行多目標(biāo)優(yōu)化問題的研究.

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

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

遺傳算法是一種基于自然進(jìn)化和選擇機(jī)制的智能優(yōu)化算法, 具有全局優(yōu)化能力強(qiáng)、速度快、易于實(shí)現(xiàn)等優(yōu)點(diǎn), 但是其存在易早熟、早收斂等缺陷. 變鄰域搜索算法是基于鄰域結(jié)構(gòu)集而非單個(gè)鄰域的局部搜索算法, 其基本思想是在搜索過程中系統(tǒng)地改變鄰域結(jié)構(gòu)集來(lái)拓展搜索能力, 以提高算法局部搜索能力, 避免算法陷入局部最優(yōu), 比傳統(tǒng)的固定鄰域搜索的搜索能力更強(qiáng)[16], 已用于很多優(yōu)化問題的求解.

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

1 問題描述與數(shù)學(xué)建模

1.1 問題描述

本文研究含多AGV的離散化車間物流調(diào)度優(yōu)化問題, AGV在車間中負(fù)責(zé)物流任務(wù)的運(yùn)輸. 某加工車間有k個(gè)工位, 根據(jù)生產(chǎn)作業(yè)排程結(jié)果和工件加工工藝的要求, 每個(gè)工件加工時(shí)間、加工刀具、工裝和所需物料已給定. 由于制造車間生產(chǎn)過程存在不確定性, 在物流配送環(huán)節(jié), 隨著時(shí)間的推移, 各個(gè)工位的物流任務(wù)會(huì)發(fā)生變化.

每個(gè)工位有進(jìn)料位和出料位, 車間中還額外設(shè)置一個(gè)公共緩沖區(qū), 該公共緩沖區(qū)服務(wù)于所有加工工位.每個(gè)工位的進(jìn)料位容量為cik, 出料位容量為cok, 當(dāng)前一道工序的加工工位出料位容量達(dá)到上限, 需要將出料位的工件運(yùn)走, 如果此時(shí)下一個(gè)工位的入料位已被占用, 則需要將工件運(yùn)送到緩沖區(qū). 當(dāng)下一道工序的加工工位進(jìn)料位有空閑時(shí), 將工件從緩沖區(qū)運(yùn)輸?shù)较乱粋€(gè)加工工位的進(jìn)料位.

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

(1) 當(dāng)小車被指派多個(gè)物流任務(wù)時(shí), 小車完成一個(gè)任務(wù)后直接執(zhí)行下一個(gè)任務(wù).

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

(3) 一個(gè)小車在同一時(shí)刻只能承擔(dān)一個(gè)物流任務(wù).

(4) 小車一次只能運(yùn)輸一個(gè)載具的物料.

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

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

1.2 數(shù)學(xué)建模

為了貼近生產(chǎn)物流實(shí)際情況, 模型參數(shù)變量定義如表1所示.

表1 模型變量參數(shù)定義

1.2.1 物流任務(wù)計(jì)算

由于一個(gè)工位加工任務(wù)對(duì)應(yīng)多個(gè)工件, 根據(jù)物流能力需要轉(zhuǎn)換為jk個(gè) 物流任務(wù). 式(1)是所有加工工位所需原材料載具的計(jì)算公式是計(jì)算工位k需要的所有原材料數(shù), 然后根據(jù)物料載具關(guān)系, 計(jì)算出該工位需要的原材料載具數(shù)jk. 小車每次運(yùn)輸一個(gè)載具, 一個(gè)載具是一個(gè)物流任務(wù). 式(2)為待運(yùn)輸?shù)奈锪魅蝿?wù)集合, 是需要轉(zhuǎn)運(yùn)的原材料和實(shí)時(shí)呼叫的物流任務(wù)的集合.

1.2.2 目標(biāo)函數(shù)

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

(1) 時(shí)間懲罰成本

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

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

小車的總行駛距離由運(yùn)輸物流任務(wù)的距離和完成上一個(gè)物流任務(wù)再去運(yùn)輸下一個(gè)物流任務(wù)所需的距離所組成.

1.2.3 約束條件

根據(jù)物流調(diào)度優(yōu)化的實(shí)際需求, 設(shè)定如下約束條件:

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

(2) 每個(gè)工位的出料位和進(jìn)料位容量大于等于1.

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

(4) 進(jìn)料位容量限制, 工位進(jìn)料位的實(shí)時(shí)存儲(chǔ)物料不超過其最大存儲(chǔ)量限制.

2 求解算法設(shè)計(jì)

針對(duì)制造車間物流調(diào)度問題, 設(shè)計(jì)的混合變鄰域搜索的改進(jìn)遺傳算法偽代碼如算法1所示, 算法流程圖如圖1所示.

2.1 編碼設(shè)計(jì)

常見的染色體編碼方式有二進(jìn)制編碼、自然數(shù)編碼、矩陣編碼和交叉編碼等. 由于本文研究問題為運(yùn)輸小車任務(wù)的指派, 以及運(yùn)輸小車任務(wù)的排序, 因此采用自然數(shù)編碼和交叉編碼相結(jié)合的方式. 染色體基因總數(shù)為偶數(shù), 奇數(shù)位為小車編號(hào), 偶數(shù)位為待運(yùn)輸?shù)奈锪魅蝿?wù), 每?jī)蓚€(gè)基因組成一個(gè)基因片段, 每個(gè)基因片段表示小車i負(fù)責(zé)物流任務(wù)p的運(yùn)輸. 例如: 待運(yùn)輸?shù)奈锪魅蝿?wù)編號(hào)為{2, 9, 3, 5, 7, 8}, 可供使用的AGV小車編號(hào)為{1, 2}, 則一個(gè)可能的染色體為: {2, 2, 1, 9, 1, 3,2, 5, 1, 7, 2, 8}. 表示2, 9, 3, 5, 7, 8物流任務(wù)分別由2,1, 1, 2, 1, 2運(yùn)輸. 即小車1按順序運(yùn)輸載具9, 3, 7, 小車2按順序運(yùn)輸載具2, 5, 8, 如圖2所示.

圖2 編碼設(shè)計(jì)

2.2 解碼方法和適應(yīng)度函數(shù)設(shè)計(jì)

按照2.1節(jié)編碼設(shè)計(jì)規(guī)則對(duì)種群中每個(gè)染色體進(jìn)行解碼, 解碼時(shí)根據(jù)物流任務(wù)編號(hào)找到其在車間所處對(duì)應(yīng)的位置、優(yōu)先級(jí)等相關(guān)信息.

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

式中,fiti表示群體中第i個(gè)體的適應(yīng)度值,Yi表示第i個(gè)體的目標(biāo)函數(shù)值,pop_size表示種群規(guī)模數(shù).

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

1/2×(pop_size)//對(duì)種群進(jìn)行擾動(dòng), 保證迭代過程中個(gè)體的多樣性, 生成大小為的個(gè)體替換子代適應(yīng)度較低的個(gè)體 end if gen_no+=1 end while solution0循環(huán)最優(yōu)解 , 得到每個(gè)小車的物流任務(wù)及順序

2.3 初始種群的生成

初始種群以物流任務(wù)優(yōu)先級(jí)從高至低排序和隨機(jī)生成相結(jié)合的方式生成.

以隨機(jī)生成方式產(chǎn)生初始種群的具體步驟如下:

步驟 1. 根據(jù)可調(diào)用的小車編號(hào), 確定小車的集合I.

步驟 2. 用生成隨機(jī)數(shù)的方法從指定集合I中對(duì)染色體的每個(gè)基因產(chǎn)生隨機(jī)數(shù)xi∈I, 染色體基因個(gè)數(shù)等于待運(yùn)輸物流任務(wù)數(shù)X.

步驟 3. 在生成的染色體每一位基因后面隨機(jī)插入一位新的基因, 表示物流任務(wù)編號(hào), 染色體長(zhǎng)度擴(kuò)展為2P, 染色體擴(kuò)展方法如圖3所示.

圖3 初始種群的生成

步驟 4. 重復(fù)以上步驟, 產(chǎn)生大小為pop_size的初始種群.

以物流任務(wù)優(yōu)先級(jí)從高至低排序產(chǎn)生初始種群的具體步驟如下:

步驟 1. 將所有物流任務(wù)按照優(yōu)先級(jí)進(jìn)行降序排序(優(yōu)先級(jí)最高為4).

步驟 2. 隨機(jī)打亂小車編號(hào)的順序.

步驟 3. 循環(huán)小車編號(hào)列表和物流任務(wù)編號(hào)列表,當(dāng)循環(huán)至最后一個(gè)小車編號(hào)時(shí), 改變索引至第一個(gè)小車, 直至遍歷完所有的物流任務(wù), 每一次取出小車編號(hào)和物流任務(wù)編號(hào), 小車編號(hào)后面跟著物流任務(wù)編號(hào).

步驟 4. 染色體的大小為2倍物流任務(wù)長(zhǎng)度. 重復(fù)執(zhí)行上述操作pop_size遍 , 生成規(guī)模為pop_size的初始種群.

2.4 交叉算子

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

2.5 變異算子

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

圖5 變異操作

2.6 精英保留策略

傳統(tǒng)遺傳算法中交叉、變異算子的作用個(gè)體均來(lái)自于子代種群, 該方法有一個(gè)明顯缺點(diǎn): 種群進(jìn)化中優(yōu)秀的個(gè)體得不到保護(hù)以致在下一輪迭代中易破壞. 因此, 通過使用保優(yōu)記憶庫(kù)更新策略來(lái)解決這一問題, 在每一代迭代結(jié)束后, 將保優(yōu)記憶庫(kù)中的精英個(gè)體合并到當(dāng)代得到的新種群中, 合并的規(guī)則是若保優(yōu)記憶庫(kù)中的解和新種群的解兩個(gè)目標(biāo)函數(shù)均相同,則只選擇一個(gè). 然后通過精英選擇策略選擇規(guī)模為elite_size的個(gè)體加入庫(kù)中進(jìn)行保護(hù), 精英選擇策略是首先進(jìn)行帕累托分層得到每個(gè)個(gè)體的帕累托等級(jí)并計(jì)算每層個(gè)體之間的擁擠距離, 優(yōu)先選擇帕累托等級(jí)低的個(gè)體, 若多個(gè)個(gè)體帕累托等級(jí)相同, 則選擇擁擠距離較大的個(gè)體.

2.7 變鄰域搜索算法

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

圖6 變鄰域搜索流程

針對(duì)本文模型特點(diǎn), 設(shè)計(jì)6個(gè)隨機(jī)鄰域結(jié)構(gòu)搜索機(jī)制, 具體如下:

(1) 3種同一小車內(nèi)搜索策略, 即通過一定的規(guī)則改變同一個(gè)小車運(yùn)輸物流任務(wù)的順序.

① swap算子

任意交換同一個(gè)小車的物流任務(wù), 對(duì)同一個(gè)小車,隨機(jī)選取兩個(gè)節(jié)點(diǎn), 交換兩個(gè)節(jié)點(diǎn). 如圖7(a)所示.

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

② 2-opt算子

對(duì)某一個(gè)小車, 隨機(jī)選取兩個(gè)不相鄰的節(jié)點(diǎn), 然后翻轉(zhuǎn)兩個(gè)節(jié)點(diǎn)之間的節(jié)點(diǎn), 得到新染色體, 如圖7(b)所示.

③ or-opt算子

將同一個(gè)小車相鄰的兩個(gè)物流任務(wù)一起移動(dòng)到其他位置. 即隨機(jī)選取同一個(gè)小車的兩個(gè)相鄰的位置, 隨機(jī)選擇該小車的一個(gè)物流任務(wù)作為一個(gè)插入節(jié)點(diǎn), 并在移動(dòng)后保持相鄰, 如圖7(c).

圖7 同一小車內(nèi)搜索策略

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

① swap算子

隨機(jī)選擇兩個(gè)小車, 在小車1和小車2分別隨機(jī)選取兩個(gè)小車的一個(gè)物流任務(wù), 交換這兩個(gè)節(jié)點(diǎn), 如圖8(a)所示.

② relocate算子

隨機(jī)選取兩個(gè)小車, 隨機(jī)選取小車1的一個(gè)物流任務(wù)m, 隨機(jī)選取小車2的一個(gè)物流任務(wù)n, 將小車1的物流任務(wù)m移動(dòng)到小車2物流任務(wù)n后的位置, 如圖8(b)所示.

③ or-opt算子

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

圖8 不同小車間搜索策略

為了進(jìn)一步降低物流成本和提高工位滿意度, 設(shè)計(jì)基于關(guān)鍵AGV小車的插入鄰域、基于關(guān)鍵物流任務(wù)的交換鄰域的調(diào)整策略, 具體如下:

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

將總行駛距離最大的AGV定義為關(guān)鍵AGV小車, 表示為Imain, 最大距離記為L(zhǎng). 通過將Imain的物流任務(wù)分配給其它AGV, 可以均衡每輛AGV的任務(wù)量, 同時(shí)會(huì)降低運(yùn)輸所有物流任務(wù)的最大完成時(shí)間. 該鄰域結(jié)構(gòu)具體描述為: 遍歷選擇Imain中的物流任務(wù)插入到其它AGV的物流任務(wù)序列中, 若插入后L和兩個(gè)目標(biāo)函數(shù)值均降低了, 則接受該物流任務(wù)移動(dòng), 否則重新選擇Imain中的物流任務(wù)插入序列, 直到選擇Imain中的所有物流任務(wù).

(2) 基于關(guān)鍵物流任務(wù)的交換鄰域

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

3 數(shù)值實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)相關(guān)數(shù)據(jù)

(1) 案例設(shè)計(jì)

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

圖9 車間布局示意圖

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

(2) 算法相關(guān)參數(shù)設(shè)置如表3所示.

表3 算法相關(guān)參數(shù)設(shè)置

(3) 物流任務(wù)的實(shí)時(shí)信息模型

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

在優(yōu)先級(jí)的定義中, 1 代表“普通任務(wù)”, 2 代表“重要任務(wù)”, 3代表“緊急任務(wù)”, 4代表“更緊急任務(wù)”.

為了驗(yàn)證本文模型和算法的有效性, 隨機(jī)構(gòu)造一個(gè)實(shí)驗(yàn)案例, 如表4和表5. 最晚運(yùn)輸時(shí)間在區(qū)間[0,60]中隨機(jī)產(chǎn)生.

表4 待運(yùn)輸物流任務(wù)信息

表5 AGV小車信息

3.2 實(shí)驗(yàn)結(jié)果分析

與單目標(biāo)優(yōu)化算法不同, 多目標(biāo)優(yōu)化結(jié)果通常不是單個(gè)最優(yōu)解, 而是一個(gè)Pareto最優(yōu)解集. 根據(jù)本文車間物流調(diào)度需求, 算法需要確定每個(gè)AGV小車運(yùn)輸?shù)奈锪魅蝿?wù), 及運(yùn)輸每個(gè)物流任務(wù)的順序. 本文是從最優(yōu)解集中根據(jù)兩個(gè)目標(biāo)函數(shù)的和選取最優(yōu)解.

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

圖10 不同算法Pareto前沿分布

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

表6 算法結(jié)果對(duì)比

表7 運(yùn)行結(jié)果對(duì)比

4 結(jié)束語(yǔ)

本文以制造車間物流調(diào)度為實(shí)際背景, 建立多目標(biāo)優(yōu)化模型, 針對(duì)該問題設(shè)計(jì)了求解多目標(biāo)的VNSGA-II算法, 該算法包含遺傳算法的基本操作, 并對(duì)最優(yōu)解集進(jìn)行變鄰域搜索. 通過實(shí)驗(yàn), 結(jié)果表明:

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

(2) 與兩種多目標(biāo)經(jīng)典優(yōu)化算法NSGA-II和SPEA2的實(shí)驗(yàn)結(jié)果對(duì)比表明, VNSGA-II算法在求解質(zhì)量上均優(yōu)于NSGA-II和SPEA2.