劉躍強,宋佳佳,張守京

(西安工程大學(xué) 機電工程學(xué)院,陜西 西安 710048)

0 引 言

在制造業(yè)生產(chǎn)加工過程中,生產(chǎn)物流的管理和優(yōu)化起著重要作用。企業(yè)的多品種、小批量的生產(chǎn)制造模式使企業(yè)更加依賴對生產(chǎn)物流的管理,物料配送作為生產(chǎn)物流管理的重要環(huán)節(jié)之一,其關(guān)鍵在于如何合理地調(diào)度小車,使工位能夠在合適的時間、地點得到合適的物料。優(yōu)化物料管理、提高物料配送效率,不僅可以保證生產(chǎn)的連續(xù)性,還可以減少人力、財力、物力等不必要的浪費。

車輛路徑問題和裝箱問題是研究空間裝載約束下物料調(diào)度的兩個關(guān)鍵問題。在車輛路徑問題(vehicle routing problem,VRP)上,童傅嬌等人[1]研究了以工位為中心的優(yōu)先層級問題;但研究中結(jié)合實際問題的約束條件相對較少。ADEBAYO K J等人[2]研究了時間與數(shù)量優(yōu)先級的VRP問題;但其側(cè)重于理論和模型研究,缺少仿真和實驗的論證。郭玉潔等人[3]提出了改進的離散鯨魚優(yōu)化算法,采用k均值聚類算法進行分類,并引入了鄰域搜索策略;但該研究僅局限于算法的改進。胡小建等人[4]分析了物料倉儲區(qū)與工位之間的關(guān)系;但該研究僅提供了一種策略,對求解算法的有效性缺乏驗證。蔣增強等人[5]結(jié)合混流裝配生產(chǎn)線特點,設(shè)計了動態(tài)周期的物料配送策略;但未考慮到物料需求存在時間窗的變化。

<1)，且各件產(chǎn)品是否為不合格品相互獨立．

在考慮空間裝載約束的車輛路徑問題上,AYOUGH A等人[6]提出了兩階段的模擬退火(SA)算法與空間裝載算法,分別構(gòu)建了三維裝載車輛路徑問題、帶容量的三維裝載約束車輛路徑問題(three-dimensional loading capacitated vehicle routing problem,3L-CVRP),以及帶容量和時間窗的三維裝載約束車輛路徑問題(three-dimensional loading capacitated vehicle routing problem with time windows,3L-CVRPTW)的數(shù)學(xué)模型;但該研究僅考慮了三維裝載的經(jīng)典路徑優(yōu)化問題。REIL S等人[7]以最少車輛數(shù)目和最小行駛距離為優(yōu)化目標,解決了打包問題;但該研究側(cè)重于通過提高裝載率來降低成本,忽略了工位的需求。吳倩云等人[8]以最短配送路徑、最大載重率、最小車輛數(shù)目等為優(yōu)化目標,求解了3L-CVRP問題;但該研究未考慮實際生產(chǎn)過程中存在的緊急插單等擾動現(xiàn)象。KOCH H等人[9]考慮了取送貨一體、時間窗和空間裝載問題,并引入了先進后出策略(first in last out,LIFO);但該研究主要基于確定環(huán)境下的優(yōu)化問題。PACE S等人[10]設(shè)計了一種基于模擬退火和迭代局部搜索的啟發(fā)式方法;但該研究缺乏與車輛路徑問題的有機融合。胡蓉等人[11]研究了二維裝載車輛路徑問題,設(shè)計了天際線填充算法優(yōu)化裝箱;但研究對象僅為大件貨物,未考慮貨物的三維空間。

為此,筆者對空間裝載約束下智能車間物料調(diào)度優(yōu)化問題進行研究。首先,確定配送路徑,盡可能在規(guī)定服務(wù)時間窗內(nèi)按物料需求程度進行配送;然后,檢驗配送路徑上的物料是否能被裝載,選出最佳物料調(diào)度方案。

1 問題描述與模型構(gòu)建

考慮空間裝載約束的智能車間物料調(diào)度是指,鑒于車間生產(chǎn)過程中存在工序優(yōu)先、緊急產(chǎn)品插單等情況,在滿足時間窗、載重、物料需求緊急度、空間裝載等約束條件的基礎(chǔ)上,保證運輸工具(堆放空間有限)能夠裝載每一條配送路徑的全部物料。

1.1 假設(shè)條件

1.1.1 路徑約束

1)物料超市約束。只有一個物料超市,是小車出發(fā)點和返回點;

2)行程約束。一次配送服務(wù)中,小車行駛的總距離始終在最大行駛距離之內(nèi);

3)路況約束。小車在配送過程中勻速行駛,不考慮堵塞、排隊等待情況;

4)物料訂單約束。不進行訂單拆分配送;

5)需求緊急度約束。按照物料需求緊急程度來確定工位的優(yōu)先級;

6)時間窗約束。針對違反物料配送時間窗約束的行為,進行成本懲罰;

7)載重與體積約束。小車所裝載物料總重量和總體積均小于小車參數(shù)的最大上限。

1.1.2 空間裝載約束

1)箱體類型約束。小車配送箱規(guī)格只有一種,并且標準物料箱規(guī)格均已知;

2)方向性約束。物料箱體的邊界總是與配送箱體的邊界平行或垂直,且高度方向始終平行于水平面的垂直方向;物料箱體不可倒置,且只存在水平面90°旋轉(zhuǎn);

3)穩(wěn)定性約束。物料箱體的接觸面積必須達到80%,才能保證其穩(wěn)定性;

4)可行性約束。物料箱堆疊后所形成的不規(guī)則體始終在小車配送箱體內(nèi)。

1.2 模型構(gòu)建

筆者以車輛派遣數(shù)目最少、總配送成本最低為目標,建立物料調(diào)度優(yōu)化模型。

最少車輛派遣數(shù)目如下:

(1)

物料配送的總成本(包括小車派遣成本、行駛距離成本和時間成本)如下:

(2)

式中:C為總配送成本;c1為單輛小車派遣成本;ui為第i個工位的時間懲罰成本;xijk為小車k是否從工位i到達工位j;yik為小車k配送工位i所需物料時是否違反時間窗;dij為各工位間的曼哈頓距離,且dij=dji;η為單位距離的行駛成本。

從節(jié)約車間資源的角度出發(fā),筆者提出車輛數(shù)目優(yōu)化偏好型路徑規(guī)劃模型[12],即先優(yōu)化車輛派遣數(shù)目再優(yōu)化配送路徑。

1.2.1 路徑約束

針對所有工位進行一次配送服務(wù),表示如下:

(3)

保證到達和離開工位的小車相同,表示如下:

(4)

所有小車均從物料超市出發(fā),最后再返回出發(fā)點,表示如下:

x0ik=xi0k,?i∈N,?k∈K;

(5)

物料配送的次序按照工位對物料需求的緊急程度進行排序,表示如下:

(6)

式中:Ii為第i個工位對物料需求緊急度高低的優(yōu)先級參數(shù)。

若第i工位物料需求緊急程度Ii高于第j工位物料需求的緊急程度Ij,即i工位需求的最佳時間小于j工位需求的最佳時間,則先將物料配送至i工位,再配送至j工位。

針對違反時間窗的行為,進行成本懲罰,表示如下:

(7)

式中:α,β為早于或晚于工位服務(wù)時間窗到達的懲罰參數(shù);si為到達第i個工位的時間點;ati,bti為工位服務(wù)時間窗上限和下限。

1.2.2 裝箱約束

標準物料箱體邊界總是平行或正交于配送箱體邊界,表示如下:

(8)

標準物料箱可以進行水平方向90°旋轉(zhuǎn),但不可倒置,表示如下:

(9)

式中:hik為小車k上第i工位所需標準物料箱的高度。

堆疊后的標準物料箱尺寸不可超出箱體最大邊界尺寸,表示如下:

(10)

式中:Lk為小車k配送箱體的長度;Wk為小車k配送箱體的寬度;Hk為小車k配送箱體的高度。

筆者提出假設(shè):任意兩物料箱在同一車廂存在重疊擺放現(xiàn)象,即A(j,m)與物料箱Eikt放在同一配送箱中的其他箱子集合[13]。

標準物料箱在空間內(nèi)部是不重疊的,表示如下:

x1≤x2或y1≤y2或z1≤z2

(11)

式中:(x1,y1,z1)為標準物料箱的最小右后上角坐標;(x2,y2,z2)為標準物料箱的最大左前下角坐標。

重疊箱體平面投影圖如圖1所示。

圖1 重疊箱體平面投影圖

圖1中:兩個標準物料箱在X-Y水平面投影—陰影區(qū)域表示重疊部分;如果箱體不重疊,則水平面投影也無陰影區(qū)域。

標準物料箱的重疊存在支撐面約束,表示如下:

∑(x1-x2)(y1-y2)≥flikt·wikt·hikt,

x1>x2,y1>y2;

(12)

式中:f為支撐面約束的參數(shù)。

2 兩階段混合算法設(shè)計

筆者設(shè)計了一種鯨魚算法(WOA)和SA相結(jié)合的兩階段混合算法,即改進鯨魚優(yōu)化算法(WOA-SA)。

兩階段混合算法求解流程圖如圖2所示。

圖2 兩階段混合算法求解流程圖

第一階段,以WOA為基本框架求解路徑優(yōu)化問題;第二階段,利用裝箱算法檢驗物料的可裝載性,以確保路徑是可行的。

2.1 改進鯨魚優(yōu)化算法設(shè)計

筆者對鯨魚算法中包圍獵物、發(fā)起泡泡網(wǎng)攻擊獵物、再捕食獵物等行為進行適當刪改和再定義。

2.1.1 編碼與解碼

將鯨魚算法中連續(xù)性變量轉(zhuǎn)換成離散化變量,即對工位進行整數(shù)編碼。假設(shè)某車間工位為n={1-1*,2-2*,3-3*,4-4*,5-5*,6-6*,7-7*,8-8*,9-9*,10-10*}。其中,*表示工位所需的物料。某一次工位配送順序為1-2-3-4-5-6-7-9-8-10,按照重量、容積等約束的限制可能需要3輛小車進行配送,則解碼成0-1-1*-2-2*-3-3*-4-4*-0,0-5-5*-6-6*-7-7*-0,0-9-9*-8-8*-10-10*-0。其中,0為物料超市。

2.1.2 鯨魚位置更新

2)泡泡網(wǎng)捕食。該過程是鯨魚針對獵物的局部搜索過程。發(fā)起泡泡網(wǎng)攻擊的捕食行為存在兩種方式:收縮包圍機制和螺旋吐泡機制,即鯨魚以一定概率選擇捕食方式,從而更新鯨魚個體位置。假設(shè)現(xiàn)有工位配送順序為x={x1,x2,x3,x4,x5,x6,…,xn},則鯨魚個體位置更新的操作,如下:

(13)

式中:xn為第n個工位;p為捕食方式的概率;

3)隨機搜索捕食。鯨魚以反轉(zhuǎn)、插入操作方式更新位置,從而靠近獵物。若更新后的種群適應(yīng)度值C2低于原種群適應(yīng)度值C1,則保留更新后的工位配送順序;反之,則工位配送順序保持不變,如下:

(14)

式中:C2為種群更新后的個體適應(yīng)度值;C1為種群更新前個體適應(yīng)度值。

2.1.3 鄰域搜索策略

為了增強算法的空間搜索能力,筆者將模擬退火接受劣質(zhì)解思想與鄰域搜索策略相結(jié)合,提出了隨機交換算子(Exchange)、2-opt算子、隨機插入算子(Insert)相結(jié)合的鄰域搜索策略。

1)Exchange。隨機選擇兩個工位點進行點對點交叉操作;

2)Insert。隨機選擇兩個工位點進行前后的插入操作;

3)2-opt。隨機選擇兩個工位點,并對兩工位點之間所有工位進行反轉(zhuǎn)操作。

2.1.4 接受劣質(zhì)解準則

Metropolis接受準則是模擬退火算法的核心,旨在篩選出優(yōu)質(zhì)解,并控制接受劣質(zhì)解可能性。準則表示如下:

(15)

式中:P為接受劣質(zhì)解的概率;T為模擬退火的溫度;f1為鄰域操作前的個體適應(yīng)度值;f2為鄰域操作后的個體適應(yīng)度值。

關(guān)于P值求解涉及退火過程,表示如下:

Tgen+1=Tgen×s

(16)

式中:gen為算法迭代次數(shù);Tgen為第gen代的模擬退火溫度;s為冷卻因子。

2.2 裝箱檢驗算法設(shè)計

2.2.1 物料裝載策略

假設(shè)所有物料只能從箱體正上方進入,在不超出配送箱體尺寸的情況下,優(yōu)先對尺寸完全相同的標準物料箱進行打包,然后將包裝后的物料箱與未包裝的物料箱按照擺放策略統(tǒng)一裝箱。

2.2.2 空間擺放策略

1)“先左后右”優(yōu)先級策略。將標準物料箱擺放在配送箱體的最左下端位置,然后進行選擇性堆疊。當左側(cè)空間不足時,進行右側(cè)空間擺放;

2)“自下而上”優(yōu)先級策略。將第一個標準物料箱擺放至最左側(cè)空間后,優(yōu)先考慮第二個標準物料箱擺放其上層空間。

2.2.3 擺放規(guī)則

如1.1節(jié)假設(shè)條件已描述空間可行性、支撐面穩(wěn)定性、旋轉(zhuǎn)方向性等約束,故筆者不再贅述。

2.2.4 坐標確定方法

坐標點的確定是通過保留每個標準物料箱的3個關(guān)鍵頂點以選擇出合適的擺放點。

空間擺放策略如圖3所示。

圖3 空間擺放策略

圖3中:擺放第一個物料箱,并記錄1、2、3號點共3個關(guān)鍵點坐標,且存在優(yōu)先級關(guān)系依次為:1-2-3;擺放完成后,記錄4、5、6號點循環(huán)上述操作。

如果配送路徑上的物料不能夠被完全裝載,則選取次優(yōu)配送路徑進行裝箱檢驗,直至選出滿足條件的配送路徑。

2.3 WOA-SA混合算法實現(xiàn)步驟

根據(jù)上述設(shè)計的WOA-SA和空間裝載算法可知,兩階段算法的主要步驟如下:

1)鯨魚種群初始化,種群規(guī)模為N、最大迭代次數(shù)MAXGEN等參數(shù);

2)計算鯨魚種群的個體適應(yīng)度值;

3)泡泡網(wǎng)捕食行為,通過兩種泡泡網(wǎng)捕食行為來更新鯨魚群的位置。當p<0.5時,鯨魚個體螺旋吐泡攻擊獵物;當p≥0.5時,鯨魚個體進行收縮包圍攻擊獵物;

4)隨機捕食行為,通過反轉(zhuǎn)和插入操作再次更新鯨魚群位置并計算適應(yīng)度值,選出較優(yōu)的鯨魚群位置;

5)鄰域搜索策略,通過Exchange、Insert和2-opt操作增加鄰域結(jié)構(gòu)和鄰域解;

6)模擬退火接受劣質(zhì)解策略,計算鄰域搜索操作后的個體適應(yīng)度值并以一定概率接受劣質(zhì)解,更新鯨魚種群的位置;

7)空間裝載檢驗算法,對優(yōu)化后鯨魚種群個體按優(yōu)劣順序逐一進行檢驗,篩選出符合約束條件的最優(yōu)解;

8)判斷gen是否滿足最大迭代次數(shù)MAXGEN,如果滿足條件,則跳出此次循環(huán);反之,跳轉(zhuǎn)至Step3,繼續(xù)迭代;

9)輸出全局最優(yōu)解,記錄最優(yōu)物料調(diào)度方案。

3 實例仿真與分析

筆者實現(xiàn)兩階段算法的仿真環(huán)境如下:操作系統(tǒng)為Windows 10家庭中文版,計算機內(nèi)存為4 GB,CPU型號為Intel Core i5-7200U,算法編程軟件為MATLAB 2019a。

3.1 實例數(shù)據(jù)與參數(shù)設(shè)置

筆者以文獻[2]1469中車間數(shù)據(jù)及算法參數(shù)選擇為基礎(chǔ),結(jié)合某車間物料信息并對物料重量(G)進行調(diào)整。

考慮裝載約束的車間物料配送過程示意圖如圖4所示。

圖4 考慮裝載約束的車間物料配送示意圖

已知配送小車配送箱體的長度為0.75 m、寬度為0.8 m、高度為0.75 m、最大負載為100 kg,標準物料箱規(guī)格有8種。

標準物料箱規(guī)格及需求工位如表1所示。

表1 標準物料箱規(guī)格及需求工位

工位所需物料重量如表2所示。

表2 工位所需物料重量表

WOA-SA參數(shù)設(shè)置:種群規(guī)模N=100,最大迭代次數(shù)MAXGEN=500,模擬退火溫度為1 000 ℃;早于時間窗到達工位的懲罰系數(shù)為60,晚于時間窗到達工位的懲罰系數(shù)為900;小車的行駛速度為5 km/h,小車的固定使用成本為250元,單位距離的行駛成本為1.5元/km。

綜合以上數(shù)據(jù),筆者將通過實例來驗證改進算法的有效性,并分析不同約束條件下求解帶時間窗有能力限制的車輛路徑問題(CVRPTW)的結(jié)果。例如,工位滿意度是指按物料需求程度進行配送,且在規(guī)定時間窗內(nèi)送達工位的數(shù)量占總工位數(shù)量的比率。

3.2 模擬退火算法參數(shù)分析

模擬退火算法接受劣質(zhì)解的概率影響著WOA的尋優(yōu)能力,冷卻因子是關(guān)鍵參數(shù)之一,故筆者針對模擬退火算法冷卻因子取值進行對比分析。

經(jīng)調(diào)研可知,冷卻因子s在[0.7,0.99]范圍內(nèi)進行不等距取值,以最佳配送成本(bestC)、平均配送成本(avC)為衡量指標并運行算法10次,模擬退火算法參數(shù)對比分析如表3所示。

表3 模擬退火算法參數(shù)對比分析

由表3分析可知:當s=0.80時,算法求解的最佳配送成本和平均配送成本均為最優(yōu)。s值過大,不易接受劣質(zhì)解;s值過小,會出現(xiàn)淬火現(xiàn)象,錯失優(yōu)質(zhì)解。故取0.80為最佳值。

3.3 對比實驗與分析

為了更好地驗證WOA-SA混合算法求解CVRPTW的能力,筆者將其與引入交叉變異算子的SA[14]、WOA、遺傳算法(genetic algorithm,GA)[15]和引入精英策略的混合粒子群算法[16](particle swarm optimiz-ation and genetic algorithm,PSO-GA)進行實例求解的橫向比較(算法參數(shù)如第3.1節(jié)、第3.2節(jié)中的表述所示);以最佳配送成本(bestC)、平均配送成本(avC)和平均耗時(avT)為衡量指標,采用不同算法分別運行10次。

算法求解情況對比結(jié)果如表4所示。

表4 算法求解情況對比

不同算法求解的成本曲線圖如圖5所示。

圖5 不同算法求解的成本曲線圖

從表4中可看出:WOA-SA求解的成本最優(yōu),相對其他算法,其計算消耗的時間是可以接受的。

圖5中:筆者設(shè)計的改進算法求解CVRPTW問題的成本最低,且曲線收斂速度較快,相對其他算法具有一定的優(yōu)越性。

筆者研究不同約束條件的CVRPTW問題,以車輛派遣數(shù)目(num)、最佳配送成本、平均配送成本、工位滿意度(JS)、平均工位滿意度(avJS)為衡量指標進行10次仿真實驗。

不同約束的CVRPTW問題結(jié)果對比如表5所示。

表5 不同約束的CVRPTW問題結(jié)果對比

筆者選取10次仿真實驗的最優(yōu)解進行對比分析,采用混合算法求解不同約束CVRPTW問題,結(jié)果如圖6所示。

圖6 混合算法求解不同約束CVRPTW問題

圖6(a)中:分析曲線波動可知,WOA收斂速度較快,但易陷入局部最優(yōu);WOA-SA混合算法收斂速度相對緩慢,但可得出全局較優(yōu)解。

表5中:兩者最佳配送成本相差172元,工位滿意度相差6%。就平均結(jié)果而言,WOA-SA混合算法的平均成本相對節(jié)約了6%,平均工位滿意度提高了5%,證明了混合算法求解多約束問題仍具有較好的尋優(yōu)能力。

由于WOA-SA混合算法擁有較好的尋優(yōu)性,筆者研究了空間裝載約束條件對求解考慮物料需求緊急度的CVRPTW問題的影響。

圖6(b)中:采用WOA-SA改進算法求解3L-CVRPTW問題時,曲線收斂速度較快,但最優(yōu)配送成本略高。

從表5中可以看出:3L-CVRPTW問題的求解結(jié)果無論是最佳配送成本、平均配送成本,還是平均工位滿意度都差于CVRPTW問題的求解結(jié)果。因此,當路徑上的所有物料不能被完全裝載,將改變物料配送次序,增加了配送成本。

由改進后的WOA-SA混合算法求3L-CVRPTW問題的最優(yōu)配送路徑可知:配送過程的行駛成本為1 256元,車輛使用成本為1 250元,時間懲罰成本為20元。

最優(yōu)物料配送結(jié)果如表6所示。

表6 最優(yōu)物料配送結(jié)果

4 結(jié)束語

在生產(chǎn)過程中,裝配制造車間會受到多種因素干擾,因此,筆者建立了多約束物料調(diào)度數(shù)學(xué)模型,并采用兩階段混合算法得出了物料調(diào)度優(yōu)化方案。

研究結(jié)果表明:

1)將裝載問題與車間物料配送問題有機融合,提出了WOA-SA混合算法,并驗證了模型的可行性及算法的有效性;

2)考慮車輛空間裝載能力和物料需求緊急度等約束條件,提高了工位服務(wù)滿意度及配送的準確度;

3)構(gòu)建了以總配送成本為次目標的車輛數(shù)目偏好型車輛路徑問題,利用兩階段混合算法使成本降低了172元,工位服務(wù)滿意度提高了6%。

在目前的研究中,尚未考慮LIFO原則。今后,筆者將結(jié)合裝載問題,探究小車電量限制、車間道路堵塞以及不確定環(huán)境下物料的調(diào)度問題。