謝潔明,陳慶新,毛 寧,張惠煜

(廣東工業(yè)大學(xué) 廣東省計(jì)算機(jī)集成制造系統(tǒng)重點(diǎn)實(shí)驗(yàn)室,廣東 廣州 510006)

0 引言

在有限能力物料儲(chǔ)運(yùn)系統(tǒng)(Finite Capacity Material Handling System,FCMHS)的單元流水式智能制造系統(tǒng)中,由于訂單的隨機(jī)到達(dá)和不同產(chǎn)品工藝路線(xiàn)的差異性,車(chē)間物流強(qiáng)度將會(huì)隨時(shí)間推移發(fā)生變化,而且在空間分布不均衡,必然導(dǎo)致?lián)矶卢F(xiàn)象,對(duì)于具有多可選物料運(yùn)輸路徑的自動(dòng)導(dǎo)引小車(chē)(Automated Guided Vehicle,AGV),還會(huì)出現(xiàn)繞道現(xiàn)象,增加了額外的運(yùn)輸成本,因此考慮擁堵與繞道成本的運(yùn)輸成本是評(píng)價(jià)一個(gè)制造系統(tǒng)規(guī)劃合理性的重要指標(biāo)。在FCMHS車(chē)間中,單元上料與下料(Pick-up/Drop-off, P/D)口位置與AGV數(shù)量均對(duì)運(yùn)輸成本產(chǎn)生影響。首先,車(chē)間單元P/D口布局是一種特殊的設(shè)施布局,P/D口是車(chē)間單元之間物料搬運(yùn)的終端設(shè)施,其位置決定了物料搬運(yùn)AGV的運(yùn)輸路徑,因此P/D口的位置布局直接影響車(chē)間的物料運(yùn)輸成本;其次,AGV在不同單元的P口與D口之間、單元與緩沖區(qū)之間搬運(yùn)物料,在物料運(yùn)輸需求較大的情況下,AGV數(shù)量影響車(chē)間物流強(qiáng)度的分布,從而間接影響車(chē)間的物料運(yùn)輸成本;最后,P/D口位置與AGV數(shù)量對(duì)車(chē)間物料運(yùn)輸成本的影響不是孤立的,P/D口位置在某種程度上改變了車(chē)間物流強(qiáng)度的分布,而AGV數(shù)量也對(duì)物流強(qiáng)度產(chǎn)生影響,兩者共同作用改變車(chē)間物流強(qiáng)度,而物流強(qiáng)度最終反映到運(yùn)輸成本上。同時(shí),考慮到運(yùn)輸設(shè)備資源配置成本、車(chē)間運(yùn)輸成本,尤其是各種等待成本,車(chē)間內(nèi)的AGV也要限制在一定數(shù)量;當(dāng)車(chē)間發(fā)生擁堵與繞道時(shí),物料運(yùn)輸設(shè)備數(shù)量也將對(duì)擁堵繞道產(chǎn)生影響,體現(xiàn)為運(yùn)輸路徑改變,最終影響車(chē)間的運(yùn)輸成本?；谏鲜鲅芯勘尘芭c動(dòng)機(jī),本文研究P/D口位置布局與AGV數(shù)量配置聯(lián)合優(yōu)化,經(jīng)過(guò)優(yōu)化的設(shè)施布局與資源配置使FCMHS車(chē)間的物料運(yùn)輸成本和AGV配置成本均最小化。

KIM等[1]在研究設(shè)施布局問(wèn)題中考慮了布局對(duì)物流路徑的影響,并提出一種求解最短物流路徑的方法;ERIK等[2]在設(shè)備布局中綜合了物料搬運(yùn)設(shè)備分配決策的影響,有效解決了設(shè)備布置與物料搬運(yùn)設(shè)備分配的集成決策問(wèn)題,不足的是采用傳統(tǒng)的設(shè)施中心點(diǎn)之間直角線(xiàn)加權(quán)距離計(jì)算設(shè)施間運(yùn)輸量的方式,在FCMHS車(chē)間的設(shè)施布局問(wèn)題中與現(xiàn)實(shí)結(jié)果有較大偏差;AHMADI-JAVID等[3]將物料運(yùn)輸路徑考慮進(jìn)非等面積設(shè)施布局問(wèn)題(Unequal Area Facility Layout Problem,UA-FLP),將物流距離作為優(yōu)化目標(biāo),尋找一種最短單環(huán)物流路徑應(yīng)對(duì)未來(lái)需求以及新技術(shù)與新產(chǎn)品帶來(lái)的挑戰(zhàn)。以上研究基于物流距離矩陣將物料儲(chǔ)運(yùn)系統(tǒng)納入設(shè)施布局設(shè)計(jì)階段,但尚未見(jiàn)到FCMHS車(chē)間中將有限物料儲(chǔ)運(yùn)設(shè)備的配置納入設(shè)施布局的研究。

單元P/D口位置直接影響FCMHS單元流水式車(chē)間的物料運(yùn)輸成本,在制造系統(tǒng)規(guī)劃設(shè)計(jì)中占有重要地位。只有少部分研究單獨(dú)針對(duì)P/D口的布局優(yōu)化[4-5],這是因?yàn)榛谖锪骶嚯x矩陣的設(shè)施布局不考慮物料儲(chǔ)運(yùn)系統(tǒng)的有限性,沒(méi)有充分體現(xiàn)P/D口位置對(duì)車(chē)間的影響。傳統(tǒng)的大多數(shù)設(shè)施布局研究集中在設(shè)施(包括加工設(shè)備、物流路徑、P/D口等)的集成布局優(yōu)化[6-9],即同時(shí)對(duì)設(shè)備、物流路徑、P/D口等設(shè)施的集成規(guī)劃,然而這類(lèi)研究將P/D口作為輔助設(shè)施,只考慮預(yù)先設(shè)定P/D口位置而不考慮可選位置。PARK等[8]研究了以最小化總物料搬運(yùn)成本的UA-FLP問(wèn)題,其中總物料搬運(yùn)成本為所有P口和D口之間的直線(xiàn)距離與物流量的乘積之和;FRIEDRICH等[9]研究帶P/D口的設(shè)施布局問(wèn)題,其中P/D口的距離根據(jù)P口和D口沿設(shè)施邊界的最短距離計(jì)算;KIM等[10]注意到P/D口在布局中的重要性,研究了以最小化P口和D口之間的直角線(xiàn)距離為優(yōu)化目標(biāo)的設(shè)備布置問(wèn)題;LIN等[11]針對(duì)設(shè)施形狀規(guī)則的UA-FLP問(wèn)題,以物流量與P/D口之間距離的乘積和計(jì)算總運(yùn)輸成本進(jìn)行優(yōu)化。傳統(tǒng)的設(shè)施布局研究大多數(shù)以設(shè)施之間的總運(yùn)輸成本為優(yōu)化目標(biāo),基于設(shè)施之間的物流距離矩陣,考慮物流量的權(quán)重,計(jì)算得到布局的總運(yùn)輸成本。然而在FCMHS車(chē)間中,由于隨機(jī)性因素的影響,車(chē)間物流不可避免地發(fā)生擁堵與繞道現(xiàn)象,使傳統(tǒng)的基于距離矩陣的設(shè)施布局結(jié)果與實(shí)際結(jié)果有一定差異,而擁堵繞道現(xiàn)象與P/D口的布局和AGV的配置緊密相關(guān),研究FCMHS車(chē)間的P/D口布局具有重要的現(xiàn)實(shí)意義,目前尚未見(jiàn)到針對(duì)FCMHS單元流水式車(chē)間單元P/D口布局與AGV配置聯(lián)合優(yōu)化的研究。

設(shè)施布局問(wèn)題研究的目標(biāo)集中在設(shè)施間的物流加權(quán)距離。近期,AHMADI-JAVID等[3]研究了具有單環(huán)封閉物流路徑的UA-FLP問(wèn)題,其以最小化單環(huán)物流路徑長(zhǎng)度為優(yōu)化目標(biāo);PARK等[8]研究了以總物料搬運(yùn)成本(Total Material Handling Cost,TMHC)為目標(biāo)函數(shù)的、帶P/D口的UA-FLP問(wèn)題;KLAUSNITZER等[12]研究了同時(shí)設(shè)計(jì)區(qū)塊布局、P/D口和通道的設(shè)施布置問(wèn)題,其中任意兩個(gè)P/D口之間的距離由通道上的最短路徑?jīng)Q定;ZHA等[13]以最小化物料搬運(yùn)成本和重新安排成本之和為目標(biāo)函數(shù),研究模糊隨機(jī)需求下的非等面積動(dòng)態(tài)設(shè)施布局問(wèn)題,其物料搬運(yùn)成本為設(shè)施間物料搬運(yùn)成本的距離加權(quán)之和。上述研究均以設(shè)施間的物流加權(quán)距離為目標(biāo),限制了其結(jié)果在實(shí)際中的應(yīng)用。在FCMHS系統(tǒng)中,物流隨時(shí)間的推移不斷變化,由于隨機(jī)性因素的影響,FCMHS車(chē)間不可避免地會(huì)產(chǎn)生擁堵和繞道現(xiàn)象,因此AGV擁堵、繞道產(chǎn)生的成本是制造系統(tǒng)設(shè)計(jì)優(yōu)化中不可忽視的重要因素。在目前現(xiàn)有研究中,常見(jiàn)的約束條件為設(shè)施之間的幾何形狀和位置約束[13-15],如單元間彼此不重疊、單元與路段彼此不重疊、單元至少有一個(gè)邊與路段平行、單元上料與下料口位置必須在其與路段接壤的邊上、所有單元和所有路段都必須在車(chē)間范圍內(nèi)等。然而,在制造系統(tǒng)規(guī)劃設(shè)計(jì)階段,設(shè)施布局與資源配置方案必須滿(mǎn)足系統(tǒng)預(yù)期要求,但幾乎沒(méi)有將FCMHS車(chē)間運(yùn)行性能指標(biāo)(產(chǎn)出率、生產(chǎn)周期等)作為設(shè)施布局和資源配置問(wèn)題的約束條件的報(bào)道。

綜上所述,本文考慮FCMHS單元流水式智能車(chē)間中的P/D口布局與AGV配置均對(duì)車(chē)間性能有重要影響,研究單元P/D口布局與AGV配置的聯(lián)合優(yōu)化問(wèn)題。在具有多可選路徑、多AGV的FCMHS前提下,已知AGV路徑網(wǎng)絡(luò)結(jié)構(gòu)及各單元位置,建立了以最小化平均運(yùn)輸總成本和最小化AGV配置成本為優(yōu)化目標(biāo),以在制品平均逗留時(shí)間和平均產(chǎn)出率為主要約束條件的數(shù)學(xué)模型;考慮沒(méi)有封閉的數(shù)學(xué)表達(dá)式對(duì)目標(biāo)函數(shù)和約束條件中的車(chē)間運(yùn)行性能指標(biāo)進(jìn)行描述,本文基于Plant Simulation仿真平臺(tái)建立P/D口布局與AGV配置模型,計(jì)算車(chē)間運(yùn)行性能指標(biāo)并獲取仿真問(wèn)題信息。針對(duì)該聯(lián)合優(yōu)化問(wèn)題,提出一種嵌入粒子群優(yōu)化(Particle Swarm Optimization,PSO)的改進(jìn)網(wǎng)格自適應(yīng)直接搜索(PSO-Mesh Adaptive Direct Search,PMADS)算法,通過(guò)增強(qiáng)粒子群的全局搜索能力,提高PMADS的全局搜索能力;提出一種基于問(wèn)題信息的啟發(fā)式規(guī)則和線(xiàn)搜索的共軛優(yōu)化法(Conjugate Optimization Method,COM),當(dāng)搜索到新解時(shí),利用該方法提高算法的聯(lián)合優(yōu)化能力和搜索效率。最后通過(guò)實(shí)際案例應(yīng)用驗(yàn)證算法的有效性,以及所提COM法提高聯(lián)合優(yōu)化算法效率的優(yōu)越性。

1 P/D口布局與AGV配置的聯(lián)合優(yōu)化

1.1 問(wèn)題描述

在智能車(chē)間規(guī)劃設(shè)計(jì)中,假設(shè)經(jīng)過(guò)了功能區(qū)塊布局階段,單元流水式車(chē)間內(nèi)各個(gè)單元間、單元與每條路段均彼此不重疊,單元至少有一條邊與某條路段平行,而且單元P/D口的位置在該路段邊上。車(chē)間內(nèi)單向封閉的AGV路徑網(wǎng)絡(luò)已確定,多輛具有多可選路徑的AGV沿物流路徑執(zhí)行不同單元P口與D口之間的物料搬運(yùn)任務(wù),車(chē)間內(nèi)功能區(qū)塊之間的大工藝路線(xiàn)為流水式,每個(gè)功能區(qū)塊處理一道工序(如剪板、折彎、沖壓、裁切、清洗等),區(qū)塊內(nèi)放置有若干制造單元。各單元內(nèi)機(jī)器布局業(yè)已經(jīng)確定,根據(jù)P/D口布局選用不同的機(jī)器布局方式。圖1所示為一種典型的含多工序、多單元、多物料搬運(yùn)AGV、具有封閉物料運(yùn)輸網(wǎng)絡(luò)結(jié)構(gòu)的單元流水式智能車(chē)間。

在AGV系統(tǒng)中,AGV沿單元邊界移動(dòng),每個(gè)單元的P/D口可以放置在單元邊界與AGV路徑交界上的任意位置,然而為了降低問(wèn)題的復(fù)雜性,許多研究往往將其離散化為有限多個(gè)可能的位置[16-17]。在FCMHS車(chē)間中,P/D口位置影響物料運(yùn)輸設(shè)備的運(yùn)輸路徑,而且由于訂單隨機(jī)到達(dá)和產(chǎn)品工藝的差異性,車(chē)間將會(huì)發(fā)生擁堵與繞道現(xiàn)象,物料運(yùn)輸設(shè)備數(shù)量也將對(duì)擁堵繞道產(chǎn)生影響,體現(xiàn)在運(yùn)輸路徑改變,最終影響車(chē)間的運(yùn)輸成本。另外,車(chē)間內(nèi)的AGV數(shù)量直接影響物料等待運(yùn)輸、擁堵繞道等成本。同時(shí)考慮運(yùn)輸設(shè)備資源配置成本和車(chē)間運(yùn)輸成本,尤其是各種等待成本,車(chē)間內(nèi)的AGV也要限制在一定數(shù)量。因此,在考慮有限物料儲(chǔ)運(yùn)能力的智能車(chē)間規(guī)劃設(shè)計(jì)問(wèn)題中,單元P/D口布局與AGV配置對(duì)車(chē)間性能指標(biāo)均有重要影響,本文研究已知各單元內(nèi)的詳細(xì)布局、各單元的具體位置以及各單元P/D口的若干可選位置,經(jīng)過(guò)優(yōu)化設(shè)施布局與資源配置,獲得合理的車(chē)間P/D口布局方案和AGV最優(yōu)配置。

傳統(tǒng)的布局優(yōu)化大多僅考慮AGV的負(fù)載成本,很少考慮AGV的空載成本,也未考慮擁堵帶來(lái)的各種等待成本。而在具有訂單工藝差異性、訂單到達(dá)不確定性等特點(diǎn)的FCMHS智能車(chē)間中,車(chē)間物流強(qiáng)度隨時(shí)間和空間持續(xù)變化,從而在一段時(shí)期內(nèi),當(dāng)物流強(qiáng)度由低到高變化時(shí),將會(huì)產(chǎn)生擁堵與等待現(xiàn)象。車(chē)間內(nèi)的AGV數(shù)量越多,發(fā)生擁堵與等待現(xiàn)象越普遍;AGV數(shù)量越少,在制品逗留時(shí)間越長(zhǎng)。本文以最小化平均運(yùn)輸總成本E{Q}和最小化AGV配置成本C為優(yōu)化目標(biāo),通過(guò)優(yōu)化P/D口布局與AGV配置,最小化車(chē)間平均運(yùn)輸總成本和AGV數(shù)量配置成本,即:

minE{Q}=E{Q1}+E{Q2}+E{Q3};

(1)

minC=cγ。

(2)

式中:E{Q1}為AGV的負(fù)載與空載運(yùn)行成本;E{Q2}為在制品平均等待運(yùn)輸成本;E{Q3}為擁堵或繞道的成本;c為單價(jià)成本;γ為配置數(shù)量。

約束條件如下:

E{T}≤t;

(3)

E{Θ}≥θ;

(4)

Zk∈Pk,k=1,2,…,Nc。

(5)

其中:式(3)和式(4)為FCMHS車(chē)間的運(yùn)行性能指標(biāo)約束;式(5)為單元P/D口位置約束;E{T}為在制品平均逗留時(shí)間;E{Θ}為在制品平均產(chǎn)出率;t為在制品平均逗留時(shí)間的預(yù)期上限值;θ為產(chǎn)品產(chǎn)出率的預(yù)期下限值;Zk為單元k的P/D口位置向量;Pk為單元k的可選位置向量集;Nc為單元數(shù)。

與傳統(tǒng)的車(chē)間布局規(guī)劃問(wèn)題相比,該問(wèn)題有兩個(gè)主要特點(diǎn):①多變量的單元P/D口布局優(yōu)化問(wèn)題可能是多峰優(yōu)化問(wèn)題,而單變量的AGV配置優(yōu)化是具有單調(diào)優(yōu)化曲線(xiàn)的優(yōu)化問(wèn)題,兩者具有不同的優(yōu)化特征,為了提高求解效率,有必要考慮該特征;②該優(yōu)化問(wèn)題將在制品平均逗留時(shí)間和平均產(chǎn)出率等車(chē)間運(yùn)行性能指標(biāo)作為約束條件,并將擁堵繞道成本作為優(yōu)化目標(biāo)的一部分,屬于隨機(jī)混合整數(shù)非線(xiàn)性規(guī)劃模型。該問(wèn)題的求解有兩方面難點(diǎn):①P/D口布局優(yōu)化與AGV配置優(yōu)化所具有的不同優(yōu)化特征,給求解P/D口布局與AGV配置的聯(lián)合優(yōu)化問(wèn)題帶來(lái)了困難,難以得到整體上較優(yōu)的聯(lián)合方案;②由于約束條件中的車(chē)間運(yùn)行性能指標(biāo)無(wú)法用決策變量的封閉形式表示,該優(yōu)化問(wèn)題不屬于傳統(tǒng)優(yōu)化問(wèn)題,無(wú)法獲得連續(xù)變量對(duì)約束函數(shù)和目標(biāo)函數(shù)的導(dǎo)數(shù),基于梯度類(lèi)函數(shù)獲得尋優(yōu)方向的傳統(tǒng)非線(xiàn)性規(guī)劃求解方法在此無(wú)法使用[18-21]。

1.2 系統(tǒng)性能指標(biāo)的計(jì)算

傳統(tǒng)布局規(guī)劃與資源配置問(wèn)題的差異在于本問(wèn)題基于物料儲(chǔ)運(yùn)系統(tǒng)的有限能力進(jìn)行設(shè)施布局與運(yùn)輸資源配置,物料儲(chǔ)運(yùn)系統(tǒng)的有限能力包括有限的AGV數(shù)量、有限的物料緩存區(qū)容量、有限的AGV行駛速度等。而由于FCMHS隨機(jī)性因素的影響,基于物流距離矩陣計(jì)算得到的結(jié)果與實(shí)際相差較大,通過(guò)建立反映真實(shí)系統(tǒng)的仿真模型可以最大程度地描述系統(tǒng)的各種細(xì)節(jié),得到的在制品平均逗留時(shí)間和平均產(chǎn)出率等系統(tǒng)性能指標(biāo)更能反映真實(shí)情況。本文通過(guò)建立車(chē)間單元P/D口布局與AGV配置的仿真黑箱模型,利用計(jì)算機(jī)仿真計(jì)算優(yōu)化模型中的性能指標(biāo)與仿真過(guò)程中的問(wèn)題信息。

上述優(yōu)化模型與傳統(tǒng)車(chē)間布局優(yōu)化問(wèn)題的最大差異在于將車(chē)間運(yùn)行性能指標(biāo)作為約束條件,然而目標(biāo)函數(shù)與約束條件中的系統(tǒng)性能指標(biāo)均無(wú)法用決策變量的封閉形式表示,而使用仿真法則有以下優(yōu)點(diǎn):

(1)可以計(jì)算出精確的系統(tǒng)性能指標(biāo)。

(2)能夠獲得更多系統(tǒng)問(wèn)題信息,本文所提算法需要用仿真獲取的信息幫助搜索,例如AGV擁堵隨時(shí)間推移會(huì)出現(xiàn)漂移現(xiàn)象,仿真法則能精確描述這一現(xiàn)象,可在優(yōu)化中提高搜索效率。

本文將通過(guò)建立車(chē)間單元P/D口布局與AGV配置的仿真黑箱模型,計(jì)算車(chē)間運(yùn)行性能指標(biāo)并獲取仿真問(wèn)題信息。利用仿真模型獲取問(wèn)題信息和系統(tǒng)性能指標(biāo)進(jìn)行聯(lián)合優(yōu)化的技術(shù)路線(xiàn)如圖2所示。

2 優(yōu)化算法

本文針對(duì)FCMHS車(chē)間單元P/D口布局與AGV配置聯(lián)合優(yōu)化問(wèn)題的特點(diǎn)和求解難點(diǎn),將上述混合整數(shù)非線(xiàn)性規(guī)劃模型中的連續(xù)變量離散化,并將該模型近似轉(zhuǎn)化為隨機(jī)非線(xiàn)性整數(shù)規(guī)劃模型,將問(wèn)題近似轉(zhuǎn)化為可求解的優(yōu)化問(wèn)題[22-24]后,提出一種不依賴(lài)梯度函數(shù)的PMADS算法;針對(duì)P/D口布局與AGV配置所具有的不同優(yōu)化特征為聯(lián)合優(yōu)化帶來(lái)的困難,提出一種基于問(wèn)題信息的啟發(fā)式規(guī)則和線(xiàn)搜索的 COM,使聯(lián)合方案在整體上最優(yōu)化。

2.1 PMADS算法

約束最優(yōu)化問(wèn)題常采用內(nèi)點(diǎn)罰函數(shù)法[26]求解極小點(diǎn),令罰函數(shù)在可行域邊界上取無(wú)窮值,則罰函數(shù)在可行域內(nèi)可求得問(wèn)題的極小值,從而得到問(wèn)題的優(yōu)化解。定義內(nèi)點(diǎn)罰函數(shù)

(6)

式中fΩ(x)為可行解空間Ω內(nèi),聯(lián)合優(yōu)化方案x的目標(biāo)函數(shù)值,即式(1)中的平均運(yùn)輸總成本E{Q}。PMADS算法步驟如下:

步驟0初始化。

(1)初始化網(wǎng)格大小參數(shù)δk和框大小參數(shù)Δk,Δk≥δk>0,令終止精度ε=1,迭代器k=0。

步驟1全局搜索(S步)。

(3)PSO進(jìn)行全局搜索得到可行解t。

(4)若有fΩ(t)

步驟2局部搜索(P步)。

(7)如果?t∈Pk,有fΩ(t)

步驟3算法終止。

(8)如果Δk+1≥ε,則k←k+1,返回步驟1,否則終止算法。

2.2 嵌入粒子群優(yōu)化算法

PSO算法是一種并行算法,該算法模擬鳥(niǎo)群的覓食行為,鳥(niǎo)群個(gè)體利用鳥(niǎo)群集體的信息共享機(jī)制使其在問(wèn)題的可行解空間不斷演進(jìn),從而獲得最優(yōu)解。該算法首先給空間中的所有粒子隨機(jī)分配初始位置和初始速度,然后根據(jù)每個(gè)粒子的速度、問(wèn)題空間中已知的全局最優(yōu)位置和粒子已知的最優(yōu)位置依次推進(jìn)每個(gè)粒子的位置。隨著計(jì)算的推移,粒子群體通過(guò)探索并利用搜索空間中已知的有利位置,最終聚集在一個(gè)或多個(gè)最優(yōu)位置周?chē)?/p>

PSO算法規(guī)則簡(jiǎn)單,其通過(guò)追隨當(dāng)前搜索到的最優(yōu)值來(lái)尋找全局最優(yōu),能夠較快找到新解,但其局部搜索能力較差,易使搜索過(guò)程陷入局部極值。該算法保留了最優(yōu)全局位置和粒子已知的最優(yōu)位置兩個(gè)信息,對(duì)提高收斂速度和避免過(guò)早陷入局部最優(yōu)解效果較好。粒子群的慣性因子ω反映了PSO的全局尋優(yōu)能力,其值越大,全局尋優(yōu)能力越強(qiáng),但局部尋優(yōu)能力越弱,通過(guò)設(shè)置粒子群的慣性因子強(qiáng)化算法的全局搜索能力,并將其嵌入PMADS算法S步中負(fù)責(zé)全局搜索任務(wù),能夠有效提高PMADS算法的全局搜索能力。本文將PSO嵌入MADS算法用于負(fù)責(zé)全局搜索新可行解,而局部尋優(yōu)由MADS負(fù)責(zé),因此PSO局部搜索能力差的缺點(diǎn)可以由主算法彌補(bǔ)。類(lèi)似于PMADS,PSO算法搜索到比當(dāng)前解更好的解之后,利用COM優(yōu)化P/D口布局和AGV配置,最終得到新的聯(lián)合方案。PSO算法的步驟如下:

步驟0初始化。

(1)迭代器i←1。

(3)計(jì)算初始種群的目標(biāo)函數(shù)值f(x0)。

步驟1確定全局最優(yōu)粒子。

(4)獲取初始粒子的個(gè)體極值和群體極值:

(7)

(8)

步驟2粒子群搜索。

(5)更新加慣性權(quán)重的粒子速度

vi=ω×vi+c1×rand()×(pbesti-xi)

+c2×rand()×(gbesti-xi)。

(9)

(6)更新粒子位置

xi=xi+vi。

(10)

(7)計(jì)算新粒子目標(biāo)函數(shù)值f(xi)。

步驟3更新種群。

(8)更新個(gè)體極值和群體極值

(11)

(12)

步驟4終止判斷。

(9)如果找到新解,則結(jié)束PSO;否則i←i+1,返回步驟2。

2.3 共軛優(yōu)化法

(4)地質(zhì)災(zāi)害是自然與人為因素共同作用下引發(fā)的，包括地質(zhì)背景、自然地理?xiàng)l件、水系等，而本文中只考慮到了害點(diǎn)密度、坡度、坡高、坡型、巖土類(lèi)型、凍土、植被、降雨、斷層和人類(lèi)工程活動(dòng)10項(xiàng)因素。在今后的其他地區(qū)評(píng)價(jià)工作中可選取更多與地質(zhì)災(zāi)害發(fā)育相關(guān)的因素作為分析指標(biāo)，在此基礎(chǔ)上再做易發(fā)性分區(qū)和危險(xiǎn)性評(píng)價(jià)，其結(jié)果會(huì)更準(zhǔn)確和全面。

步驟0初始化。

(2)初始化聯(lián)合方案數(shù)n,以及AGV配置方案γi∈I,i=1,2,…,n,i=1。

步驟1優(yōu)化聯(lián)合方案。

(3)利用問(wèn)題信息優(yōu)化新解,得到P/D口布局方案集Ψ={φ1,φ2,…,φn}。

步驟2優(yōu)化AGV配置。

步驟3終止算法。

(8)如果fΩ(τ*)

改進(jìn)的嵌入PSO算法和COM的PMADS算法流程圖如圖3所示。

3 案例應(yīng)用與分析

3.1 應(yīng)用案例背景

以某定制化五金精密制造企業(yè)的智能工廠(chǎng)規(guī)劃為背景,分別針對(duì)原生產(chǎn)車(chē)間和新生產(chǎn)車(chē)間的單元P/D口隨機(jī)柔性布局優(yōu)化和車(chē)間內(nèi)AGV數(shù)量的最優(yōu)配置需求,應(yīng)用所提算法解決車(chē)間P/D口布局和AGV配置的聯(lián)合優(yōu)化問(wèn)題。該五金制造企業(yè)的產(chǎn)品具有多品種、小批量且產(chǎn)品工藝路線(xiàn)不同的特點(diǎn),由于采用單元式生產(chǎn)方式,大多數(shù)產(chǎn)品在車(chē)間功能區(qū)域之間形成流水式工藝路線(xiàn)。在該智能工廠(chǎng)的規(guī)劃設(shè)計(jì)階段,新工廠(chǎng)除了原有產(chǎn)品的生產(chǎn)線(xiàn)外,還對(duì)新產(chǎn)品的生產(chǎn)線(xiàn)進(jìn)行規(guī)劃與設(shè)計(jì),原生產(chǎn)車(chē)間有5個(gè)功能區(qū)域,新生產(chǎn)車(chē)間擬劃分為4個(gè)功能區(qū)域,每個(gè)功能區(qū)域可放置2～4個(gè)數(shù)量不等的非同等并行制造單元。受機(jī)床設(shè)備、自動(dòng)化搬運(yùn)設(shè)備和路徑網(wǎng)絡(luò)的限制,每個(gè)單元的P/D口只有2～12種可選布局方案,單元內(nèi)機(jī)器布置可根據(jù)優(yōu)化的P/D口位置選擇合適的方案。AGV負(fù)責(zé)不同功能區(qū)域單元P/D口之間、P/D口與車(chē)間物料緩存區(qū)之間的物料搬運(yùn)任務(wù),其沿著單向封閉的路徑網(wǎng)絡(luò)行駛。由于車(chē)間柱網(wǎng)結(jié)構(gòu)及非生產(chǎn)區(qū)域(緩沖區(qū)、辦公區(qū)、模具區(qū)等)的限制,制造單元所在生產(chǎn)區(qū)域的形狀往往不規(guī)則,形成了復(fù)雜的AGV路徑網(wǎng)絡(luò)。

因?yàn)閱卧腜/D口沿著單元邊界和AGV路徑布置,而且AGV在單元P/D口之間進(jìn)行物料運(yùn)輸,所以各單元P/D口布局和AGV配置的聯(lián)合方案將對(duì)生產(chǎn)車(chē)間的運(yùn)輸成本產(chǎn)生較大影響。在已確定各單元的位置、各單元P/D口的可選布局方案以及AGV路徑網(wǎng)絡(luò)的單元流水式車(chē)間內(nèi),應(yīng)用所提算法解決車(chē)間單元P/D口位置布局與AGV資源配置的聯(lián)合優(yōu)化問(wèn)題。表1所示為所規(guī)劃的智能工廠(chǎng)單元流水式車(chē)間的主要系統(tǒng)參數(shù)。

表1 智能制造車(chē)間的系統(tǒng)參數(shù)設(shè)計(jì)

3.2 對(duì)比算法的選取

本文選取設(shè)施布局文獻(xiàn)中與問(wèn)題接近的幾種常見(jiàn)算法作為對(duì)比算法,通過(guò)從是否利用問(wèn)題信息、搜索能力、聯(lián)合優(yōu)化能力等方面與對(duì)比算法進(jìn)行比較與分析,驗(yàn)證所提算法優(yōu)化P/D口位置布局與AGV數(shù)量配置的有效性、高效性和優(yōu)越性。本文選取的對(duì)比算法分別為嵌入遺傳算法的網(wǎng)格自適應(yīng)直接搜索(Genetic Mesh Adaptive Direct Search,GMADS)算法、遺傳算法(Genetic Algorithm,GA)、蟻群優(yōu)化(Ant Colony Optimization,ACO)算法,其說(shuō)明和算法特征如表2所示,其中符號(hào)“*”表示本文所提的聯(lián)合優(yōu)化算法,Y表示較強(qiáng)或有,N表示較弱或無(wú)。

表2 對(duì)比算法

3.3 結(jié)果與分析

案例實(shí)驗(yàn)的算法部分在MATLABR2018a平臺(tái)上編程實(shí)現(xiàn),仿真部分在PlantSimulation 12.1平臺(tái)上建模實(shí)現(xiàn),采用TCP/IP協(xié)議實(shí)現(xiàn)兩者間的數(shù)據(jù)傳輸,包括P/D口布局與AGV配置方案、目標(biāo)函數(shù)值、問(wèn)題信息等數(shù)據(jù)。系統(tǒng)配置為Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz,16.0 GB RAM。

首先分析案例中AGV數(shù)量對(duì)系統(tǒng)性能的影響,圖4所示為在布局1和布局2兩種P/D口布局方案下,AGV配置這一單變量因素對(duì)系統(tǒng)性能指標(biāo)的影響曲線(xiàn)。如圖4b所示,平均擁堵成本隨著AGV數(shù)量的增加呈現(xiàn)先升高后降低的趨勢(shì),這是因?yàn)锳GV數(shù)量增加,車(chē)間發(fā)生擁堵的概率增大,當(dāng)車(chē)間運(yùn)力滿(mǎn)足要求時(shí),由于車(chē)間總擁堵成本不再增加,平均擁堵成本隨AGV數(shù)量的增加而下降。如圖4c所示,在制品等待運(yùn)輸成本隨著AGV數(shù)量的增加而逐漸降低,到一定數(shù)量后保持不變,這是因?yàn)槲锪线\(yùn)輸資源不足時(shí)在制品等待運(yùn)輸時(shí)間較長(zhǎng),隨著運(yùn)輸資源逐漸滿(mǎn)足運(yùn)輸需求,在制品等待運(yùn)輸成本降低;但當(dāng)運(yùn)輸資源過(guò)剩時(shí),物料運(yùn)輸設(shè)備不再成為瓶頸,在制品等待運(yùn)輸?shù)倪呺H效益大大降低,而且產(chǎn)生較大的運(yùn)輸資源配置成本。另外可以發(fā)現(xiàn),在制品平均運(yùn)輸成本與平均擁堵成本均隨AGV數(shù)量增加到一定程度后基本同步達(dá)到穩(wěn)定。因此,本案例解決P/D口布局與AGV配置問(wèn)題的核心在于如何平衡車(chē)間平均總運(yùn)輸成本與AGV數(shù)量配置成本。

實(shí)驗(yàn)分為原有車(chē)間與新建車(chē)間兩部分進(jìn)行,每部分有多種單元配置方案,每個(gè)配置方案進(jìn)行多種對(duì)比算法實(shí)驗(yàn),每次仿真實(shí)驗(yàn)時(shí)長(zhǎng)180天。應(yīng)用案例實(shí)驗(yàn)獲得的平均總運(yùn)輸成本、算法運(yùn)行時(shí)間、單次仿真平均用時(shí)與仿真評(píng)估次數(shù)等如表3所示。其中:C表示平均運(yùn)輸總成本(單位:h/d);A表示AGV配置成本;T表示算法運(yùn)行時(shí)間(單位:h);ST表示單次仿真平均用時(shí)(單位:min);Ns表示仿真評(píng)估次數(shù)。

表3 智能車(chē)間P/D口布局與AGV配置優(yōu)化案例結(jié)果

為了更直觀(guān)地展示算法效果,將實(shí)驗(yàn)結(jié)果繪制成折線(xiàn)圖,如圖5所示,其中PM,GM-Ⅰ,GM-Ⅱ分別表示PMADS,GMADS-Ⅰ,GMADS-Ⅱ算法。從圖5可以知道,嵌入PSO的PMADS算法比GMADS能夠更快地搜索到最優(yōu)解,仿真評(píng)估次數(shù)比利用了問(wèn)題信息的GMADS-Ⅱ少,而且PMADS得到了質(zhì)量更好的解。從中可見(jiàn),雖然PMADS算法由于COM的線(xiàn)搜索步驟增加了算法的仿真評(píng)估次數(shù),但是該步驟也增強(qiáng)了P/D口布局與AGV配置的協(xié)同優(yōu)化能力,從而更快獲得問(wèn)題的解,使PMADS算法能夠以較小的額外計(jì)算資源為代價(jià),更快、更好地獲得問(wèn)題的優(yōu)化解。

對(duì)于未利用問(wèn)題信息的GMADS-Ⅰ,其搜索能力與利用了問(wèn)題信息的GMAMS-Ⅱ和PMADS算法相比較弱,優(yōu)化時(shí)間較長(zhǎng)且得到的解質(zhì)量較差。對(duì)比GMADS-Ⅱ和PMADS可以發(fā)現(xiàn),后者收斂更快且解的質(zhì)量更好,主要有兩個(gè)原因:①PMADS算法中,PSO在產(chǎn)生均勻的初始解后,每個(gè)解都獨(dú)立進(jìn)行搜索,而且增大慣性因子提高了算法的全局搜索能力,使其比GMADS-Ⅱ在全局搜索方面更有優(yōu)勢(shì),可見(jiàn)S步全局搜索算法的選擇對(duì)MADS算法性能起重要作用;②PMADS中嵌入COM提高了算法在搜索P/D口布局與AGV配置方案時(shí)的協(xié)同性,從而提高了解的質(zhì)量。

通過(guò)對(duì)比分析PMADS與傳統(tǒng)GA,PSO,ACO算法等智能算法,可以發(fā)現(xiàn)GA搜索效率較低,這是因?yàn)樵诼?lián)合優(yōu)化問(wèn)題上,由于遺傳操作方向的隨機(jī)性,GA同時(shí)優(yōu)化P/D口布局與AGV配置的效果較差,無(wú)法協(xié)調(diào)好兩者的關(guān)系,不但較難得到穩(wěn)定的結(jié)果,而且極易陷入局部最優(yōu)。PSO,ACO等算法求解聯(lián)合優(yōu)化問(wèn)題的效率也比較低,表現(xiàn)在ACO收斂速度慢,PSO易陷入局部最優(yōu),且解的質(zhì)量不高,即使利用了問(wèn)題信息,加快了GA-Ⅱ,PSO-Ⅱ,ACO-Ⅱ等對(duì)比算法的收斂速度,仍然無(wú)法獲得比PMSDS質(zhì)量更高的結(jié)果。

本文研究的P/D口布局問(wèn)題屬于多變量多峰值問(wèn)題,而AGV配置則是單變量單峰問(wèn)題。值得注意的是,文中所有對(duì)比算法都不針對(duì)具有單峰和多峰的聯(lián)合優(yōu)化問(wèn)題,因此得到的解無(wú)法有效保證P/D口布局與AGV配置聯(lián)合方案的合理性。有些算法如GA-Ⅱ,GMADS-Ⅱ,PSO-Ⅱ,ACO-Ⅱ等利用問(wèn)題信息加快了算法的收斂速度,但在求解AGV配置方面效果不好,表現(xiàn)在解的質(zhì)量較差以及算法極易陷入局部最優(yōu)。本文所提PMADS算法采用COM雖然增加了仿真評(píng)估次數(shù),占用了計(jì)算資源,但是從圖5可見(jiàn),以較小的計(jì)算資源為代價(jià)的COM不僅極大地提高了算法的收斂速度,而且為優(yōu)化的P/D口布局方案配置了一個(gè)比較合理的AGV數(shù)量方案,提高了解的質(zhì)量。

從圖5b所示的AGV配置成本上看,GM,GA,PSO,ACO等對(duì)比算法能夠獲得比PMADS算法更低的AGV配置成本,但平均總運(yùn)輸成本均比PMADS高,如圖5a所示。從企業(yè)的運(yùn)營(yíng)實(shí)際看,智能工廠(chǎng)的規(guī)劃設(shè)計(jì)階段更加關(guān)注能夠反映企業(yè)長(zhǎng)期運(yùn)營(yíng)成本的指標(biāo)。車(chē)間平均總運(yùn)輸成本反映了較長(zhǎng)時(shí)間段內(nèi)的運(yùn)輸成本,運(yùn)輸成本往往是一個(gè)制造型企業(yè)運(yùn)營(yíng)成本的主要部分,而AGV配置成本只在前期階段對(duì)生產(chǎn)經(jīng)營(yíng)產(chǎn)生影響,因此車(chē)間平均總運(yùn)輸成本應(yīng)在最終決策時(shí)占更大的權(quán)重。結(jié)合圖5a和圖5b,雖然對(duì)比算法能夠得到較低的AGV配置成本,但是AGV配置方案與PMADS方案的結(jié)果相差不大(≤3),且其得到的平均總運(yùn)輸成本較高,而PMADS在獲得較低的AGV配置成本和合理的運(yùn)輸資源配置的同時(shí)也獲得了比其他對(duì)比算法更低的平均總運(yùn)輸成本,因此可以認(rèn)為PMADS獲得的P/D口位置布局與AGV數(shù)量配置的結(jié)果比較合理且符合規(guī)劃的預(yù)期,聯(lián)合優(yōu)化的效果優(yōu)于其他算法。

綜合上述分析可知,本文所提PMADS算法在求解P/D口布局與AGV配置聯(lián)合優(yōu)化問(wèn)題上是有效且高效的。雖然COM額外增加了目標(biāo)函數(shù)的仿真評(píng)估次數(shù),但是以較小代價(jià)獲得了巨大的收益,其通過(guò)少量的額外仿真評(píng)估時(shí)間為代價(jià)提高了算法搜索的方向性,加快了算法收斂并提高了解的質(zhì)量。

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

本文針對(duì)考慮物料儲(chǔ)運(yùn)系統(tǒng)有限能力的單元流水式車(chē)間制造單元P/D口位置布局與AGV數(shù)量配置的聯(lián)合優(yōu)化問(wèn)題,建立了以最小化總運(yùn)輸成本和AGV配置成本為多目標(biāo)的整數(shù)非線(xiàn)性規(guī)劃模型,將物料運(yùn)輸過(guò)程中的擁堵成本作為目標(biāo)函數(shù)的一部分,而且為了滿(mǎn)足制造系統(tǒng)的能力要求,將產(chǎn)出率、生產(chǎn)周期等性能指標(biāo)作為約束條件,提出一種改進(jìn)的嵌入PSO算法的MADS算法進(jìn)行求解,接著提出一種基于問(wèn)題信息的啟發(fā)式規(guī)則和線(xiàn)搜索的COM,在PMADS算法搜索到新解時(shí),利用問(wèn)題信息和線(xiàn)搜索聯(lián)合改變P/D口布局和AGV配置方案,從而改善新解,提高算法的搜索效率并改善解的質(zhì)量。將所提算法應(yīng)用到某智能工廠(chǎng)制造單元P/D口布局與AGV配置案例中表明,與已有算法相比,所提算法在求解聯(lián)合優(yōu)化問(wèn)題上具有更高的效率,得到了更好的解,驗(yàn)證了在車(chē)間單元P/D口位置布局與AGV數(shù)量配置聯(lián)合優(yōu)化問(wèn)題中,所提算法利用COM能夠提高算法效率,而且該算法在性能與效率上具有優(yōu)越性。

本文有以下創(chuàng)新點(diǎn)及貢獻(xiàn):

(1)研究有限能力物料儲(chǔ)運(yùn)系統(tǒng)的單元流水式車(chē)間單元P/D口位置布局與AGV數(shù)量配置聯(lián)合優(yōu)化問(wèn)題。

(2)提出一種結(jié)合啟發(fā)式規(guī)則與線(xiàn)搜索的COM解決設(shè)施布局與運(yùn)輸資源配置的聯(lián)合優(yōu)化問(wèn)題,而且提高了算法的效率。

(3)在優(yōu)化模型中將產(chǎn)出率、生產(chǎn)周期等車(chē)間運(yùn)行性能指標(biāo)作為約束條件,使結(jié)果滿(mǎn)足制造系統(tǒng)規(guī)劃設(shè)計(jì)的預(yù)期生產(chǎn)能力。

雖然仿真模型能夠精確描述制造系統(tǒng),但是速度慢、效率低,而排隊(duì)網(wǎng)模型具有快速求解的優(yōu)勢(shì)。后續(xù)將針對(duì)單元P/D口布局問(wèn)題建立相應(yīng)的排隊(duì)網(wǎng)模型,快速求解車(chē)間性能指標(biāo)值,然后結(jié)合優(yōu)化算法得到合理的初始方案,再利用本文方法對(duì)其進(jìn)一步優(yōu)化得到更精細(xì)的布局方案,同時(shí)還將對(duì)P/D口容量進(jìn)行優(yōu)化。