基于改進(jìn)粒子群算法的車間物料配送方法研究

楊 倩，陳再良

（蘇州大學(xué)機(jī)電工程學(xué)院，江蘇 蘇州 215137）

1 引言

物料配送作為車間這一生產(chǎn)單元的重要活動(dòng)，選擇合適的搬運(yùn)設(shè)備將正確的物料以所需的數(shù)量在正確的時(shí)間送至目標(biāo)工位將成為首要考慮問(wèn)題，對(duì)此進(jìn)行研究對(duì)提高生產(chǎn)效率與控制成本具有重要意義。

目前，國(guó)內(nèi)外不少學(xué)者對(duì)車間物料配送問(wèn)題展開了相關(guān)研究，研究?jī)?nèi)容主要集中在兩方面：?jiǎn)蝹€(gè)物料搬運(yùn)設(shè)備的物料配送問(wèn)題和單種多個(gè)物料搬運(yùn)設(shè)備的物料配送問(wèn)題。如文獻(xiàn)［1］考慮了機(jī)器人（Mobile robot）的配送能力約束，研究了單個(gè)移動(dòng)機(jī)器人物料配送方法；文獻(xiàn)［2-4］則對(duì)單個(gè)可移動(dòng)機(jī)器人的物料配送順序進(jìn)行決策；文獻(xiàn)［5］以線邊庫(kù)存最低為優(yōu)化目標(biāo)研究了裝配線中單個(gè)Tow Train的準(zhǔn)時(shí)制送料問(wèn)題；文獻(xiàn)［6］研究了含時(shí)間窗和容量約束的多ATV（Automated Transport Vehicles）運(yùn)輸調(diào)度問(wèn)題；文獻(xiàn)［7］則考慮了帶線邊緩存容量約束的多個(gè)搬運(yùn)車準(zhǔn)時(shí)化物料供應(yīng)調(diào)度問(wèn)題；文獻(xiàn)［8］研究了以能耗和加權(quán)延遲時(shí)間為目標(biāo)函數(shù)的多AGV混流裝配線送料問(wèn)題，并提出禁忌粒子群算法對(duì)其進(jìn)行求解。

綜上，現(xiàn)有文獻(xiàn)多集中于研究單個(gè)物料搬運(yùn)設(shè)備或同種多個(gè)物料搬運(yùn)設(shè)備的物料配送問(wèn)題，暫未發(fā)現(xiàn)考慮多種多個(gè)物料搬運(yùn)設(shè)備協(xié)同調(diào)度的車間物料配送情況；而在實(shí)際生產(chǎn)中因物料規(guī)格、型號(hào)、重量不一，車間物料搬運(yùn)設(shè)備是多種多樣的［9］?；?，在分析上述文獻(xiàn)的基礎(chǔ)上，以搬運(yùn)成本和線邊庫(kù)存成本最小化、平均裝載率最大化為優(yōu)化目標(biāo)建立物料配送模型，并設(shè)計(jì)改進(jìn)粒子群算法對(duì)其優(yōu)化求解，在保證高效、準(zhǔn)時(shí)送料的同時(shí)最小化投入成本和最大化搬運(yùn)設(shè)備利用率。

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

2.1 問(wèn)題描述

一個(gè)采用物料超市的裝配單元，物料超市暫存來(lái)自中心倉(cāng)庫(kù)的不同規(guī)格大小的料箱，因料箱體積、重量各不相同，本單元采用多種物料搬運(yùn)設(shè)備，并根據(jù)裝配物料清單（Bill of Material，BOM）和裝配計(jì)劃對(duì)目標(biāo)工位進(jìn)行物料配送，如圖1所示。

圖1 裝配單元布局圖Fig.1 The Layout of Assembly Part

為了有效描述該物料配送問(wèn)題，作如下假設(shè)：

（1）裝配單元采用裝配線節(jié)拍作為基本時(shí)間單位；

（2）車間依裝配計(jì)劃進(jìn)行裝配，且裝配BOM事先已確定；

（3）各料箱的物料類型和數(shù)量已知；

（4）由于物料裝卸時(shí)間較短，故運(yùn)輸過(guò)程中不予考慮；

（5）物料的搬運(yùn)成本與其搬運(yùn)量成正比；

（6）各工位物料的消耗量與節(jié)拍時(shí)間線性相關(guān)。

2.2 數(shù)學(xué)模型

（1）問(wèn)題參數(shù)：i為搬運(yùn)設(shè)備類型；j為搬運(yùn)物料種類；k為配送批次；n為搬運(yùn)設(shè)備編號(hào)；w工位索引；τ為裝配線生產(chǎn)節(jié)拍；qin為第i類搬運(yùn)設(shè)備索引；αi為第i類單個(gè)搬運(yùn)設(shè)備的固定成本；βi為第i類搬運(yùn)設(shè)備的搬運(yùn)成本系數(shù)；γjw為w工位儲(chǔ)存j類物料的成本系數(shù)；Fjw為單位生產(chǎn)節(jié)拍工位w需要消耗物料j數(shù)量；sk為第k批物料出發(fā)時(shí)間；為初始時(shí)刻工位w物料j初始庫(kù)存；為在第k次配送中運(yùn)到工位w的物料j數(shù)量；Vij為第i類運(yùn)輸設(shè)備對(duì)物料j的運(yùn)量；Sjw為工位w對(duì)物料j的最大線邊緩存能力；TD為運(yùn)輸成本；TI為線邊庫(kù)存成本；η為平均裝載率。

（2）決策變量：tk為第k批物料到達(dá)時(shí)間為第k次搬運(yùn)中是否用到搬運(yùn)設(shè)備為在第k次搬運(yùn)中是否用搬運(yùn)設(shè)備qin搬運(yùn)物料j；在第k次配送中搬運(yùn)設(shè)備qin運(yùn)輸?shù)焦の粀的物料j數(shù)量；Qki第k次運(yùn)輸中第i種運(yùn)輸設(shè)備數(shù)量。

（3）數(shù)學(xué)模型：目標(biāo)函數(shù)為：

其中，式（1）為目標(biāo)函數(shù)，式（2）和式（3）分別為物料搬運(yùn)成本和線邊庫(kù)存成本；式（4）為平均裝載率；式（5）為運(yùn)量約束，即每次運(yùn)輸?shù)目偽锪狭坎荒艹^(guò)該批次所使用的運(yùn)輸設(shè)備總運(yùn)量；式（6）為生產(chǎn)需求約束和緩存約束，即到達(dá)前k批物料應(yīng)滿足第k+1批物料消耗需求，且當(dāng)?shù)趉批物料到達(dá)時(shí)，總物料應(yīng)小于最大線邊緩存量；式（7）表示單批次各運(yùn)輸設(shè)備運(yùn)力之和應(yīng)至少大于一個(gè)節(jié)拍內(nèi)各工位零件所需數(shù)量；式（8）和式（9）分別表示第1批或第k批物料到達(dá)時(shí)間應(yīng)小于或等于物料消耗最快的工位的要料時(shí)間；式（10）為變量約束。

3 算法構(gòu)建

由問(wèn)題描述可知多種搬運(yùn)設(shè)備協(xié)同調(diào)度問(wèn)題屬于多目標(biāo)多約束優(yōu)化問(wèn)題，目前PSO（Particle Swarm Optimization）算法已廣泛應(yīng)用于求解TSP［10］、VRP［11-12］、物料配送［13］等多目標(biāo)多約束優(yōu)化問(wèn)題，然而經(jīng)典PSO算法雖然易于實(shí)現(xiàn)，卻容易陷入局部最優(yōu)；文獻(xiàn)［14］提出的綜合學(xué)習(xí)粒子群算法（Comprehensive Learning Particle Optimization，CLPSO）雖在一定程度上解決這個(gè)問(wèn)題，但仍很難擺脫局部最優(yōu)；故參考文獻(xiàn)［15-16］，構(gòu)建了改進(jìn)粒子群算法，即在CLPSO算法的基礎(chǔ)上增加轉(zhuǎn)移算子，設(shè)計(jì)粒子轉(zhuǎn)移策略，使搜索粒子能更有效跳出局部收斂區(qū)域，進(jìn)而搜索全局最優(yōu)，其算法流程，如圖2所示。

圖2 改進(jìn)粒子群算法流程圖Fig.2 Flowchart of the Improved PSO

3.1 適應(yīng)度函數(shù)

由上述可知，該模型為多目標(biāo)函數(shù)模型（運(yùn)輸成本、線邊庫(kù)存成本、平均裝載率），因此為了使目標(biāo)函數(shù)同質(zhì)化，現(xiàn)將適應(yīng)度函數(shù)調(diào)整為：

式中：個(gè)體x—一個(gè)可行解（即被選方案）。

3.2 粒子編碼設(shè)計(jì)

物料搬運(yùn)設(shè)備的協(xié)同調(diào)度問(wèn)題，其實(shí)質(zhì)是確定物料運(yùn)輸次數(shù)、搬運(yùn)設(shè)備類型及數(shù)量、搬運(yùn)物料種類及數(shù)量、所至工位等，故對(duì)優(yōu)化算法的粒子采取三層變長(zhǎng)編碼方式，即x={K，X，P} ，式中K為物料運(yùn)輸次數(shù)；X={n，i，k} ，表示使用索引為qin的搬運(yùn)設(shè)備；P={k，i} {n，j，w} ，表示使用索引為qin的搬運(yùn)設(shè)備送至w工位的物料j數(shù)量。

3.3 初始種群生成設(shè)計(jì)

改進(jìn)粒子群算法是對(duì)群體進(jìn)行進(jìn)化的操作，需要初始化群體數(shù)據(jù)構(gòu)造初始解，其步驟為：

（1）根據(jù)約束式（5）和式（6）中的緩存約束確定最少運(yùn)輸次數(shù)Kmin，定義：

（2）根據(jù)約束式（8）和式（9）確定下一批次物料到達(dá)時(shí)間，定義：

式中：i—消耗最快的物料種類編號(hào)；Δt1—與times1對(duì)應(yīng)的物料運(yùn)送時(shí)間間隔；Δt2—與times2對(duì)應(yīng)的物料運(yùn)送時(shí)間間隔。

（3）初始化運(yùn)送物料量，根據(jù)需要運(yùn)送的物料量確定搬運(yùn)設(shè)備類型、數(shù)量及運(yùn)量，若滿足約束（6）中的需求約束，則輸出配送結(jié)果，否則返回（2）。

3.4 粒子轉(zhuǎn)移策略

當(dāng)Tu＞0 時(shí)，隨機(jī)選擇一個(gè)較差的粒子，使其以Pm的概率跳出局部收斂區(qū)域并將其轉(zhuǎn)移到較優(yōu)的位置；定義局部收斂區(qū)[μj-σj，μj+σj]N，而粒子轉(zhuǎn)移的概率由粒子位置上的方差、粒子速度以及粒子與gbest的距離等動(dòng)態(tài)因素決定［13］，計(jì)算的公式如下：

式中：μj和σj—所有粒子在第j維的位置均值和標(biāo)準(zhǔn)差；vji—第i個(gè)粒子在第j維的速度；gbestj—所有粒子在第j維上的最優(yōu)位置；σj，|vji|和|μj-gbestj|越小，則Pmji越大，即粒子越有可能在第j維跳出局部收斂區(qū)。

4 仿真分析

這里算法和實(shí)驗(yàn)均在內(nèi)存為8GB、處理器為Intel（R）Core（TM）i7-865U CPU @1.80GHz 2.00 GHz 的計(jì)算機(jī)上進(jìn)行，采用MATLAB（2018a）編程實(shí)現(xiàn)。

4.1 參數(shù)設(shè)置

以某公司助力器裝配車間中的某四個(gè)工位為例，驗(yàn)證多種物料設(shè)備調(diào)度模型，產(chǎn)品-物料BOM、工位-初始庫(kù)存、工位-最大線邊緩存以及工位-物料儲(chǔ)存系數(shù)，如表1 所示。某日生產(chǎn)計(jì)劃2000件，生產(chǎn)節(jié)拍為15s。車間有3種物料搬運(yùn)設(shè)備，分別為腳輪車、手推車和平臺(tái)車，每種運(yùn)輸設(shè)備各有3輛，每種搬運(yùn)設(shè)備的固定成本分為3、4、5，其搬運(yùn)成本系數(shù)分別為0.01、0.01、0.015；其中腳輪和平臺(tái)車僅運(yùn)輸小料和大料，運(yùn)量（按物料箱計(jì)算）分別為10和5；手推車可運(yùn)輸小料和中料，運(yùn)量分別為15和10；小料、中料、大料料箱容量分別為100、50、25；優(yōu)化參數(shù)分別為：初始粒子群數(shù)30，循環(huán)迭代次數(shù)100。

表1 工位-物料BOM/初始庫(kù)存/最大線邊緩存/儲(chǔ)存系數(shù)Tab.1 Station-Bill of Material/initial Inventory/Maximum Line-Side Buffer/Storage Coefficient

4.2 仿真結(jié)果

算法運(yùn)行時(shí)間對(duì)比圖，如圖3所示。根據(jù)以上數(shù)據(jù)，利用改進(jìn)PSO算法計(jì)算的總成本為547.875，平均裝載率55.4%；每次配送的搬運(yùn)設(shè)備類型與數(shù)量、搬運(yùn)物料種類和運(yùn)量、所至工位到達(dá)時(shí)間具體，如表2所示。限于篇幅，僅列出前三次物料搬運(yùn)方案。

表2 物料搬運(yùn)設(shè)備協(xié)同調(diào)度方案Tab.2 Scheme of Co-Scheduling of Material Handling Equipment

圖3 算法運(yùn)行時(shí)間對(duì)比圖Fig.3 Comparison Chart of Runtime

為驗(yàn)證改進(jìn)PSO 算法的適應(yīng)性以及效率性，將其與自適應(yīng)PSO 算法進(jìn)行對(duì)比，利用自適應(yīng)PSO 算法計(jì)算的總成本為569.530，平均裝載率為53.6%；同時(shí)更改粒子群數(shù)目與迭代次數(shù)大小，對(duì)比其算法運(yùn)行時(shí)間，其中，實(shí)驗(yàn)組別1，3，5，7粒子群數(shù)目為30，迭代次數(shù)為100、200、500、800；實(shí)驗(yàn)組別2，4，6，8的粒子群數(shù)目為50，迭代次數(shù)同上。

從圖3可知，改進(jìn)PSO算法的運(yùn)行時(shí)間總是低于自適應(yīng)PSO算法，當(dāng)粒子群數(shù)目和迭代次數(shù)都比較大時(shí)，這一差別尤為明顯。結(jié)果表明，改進(jìn)PSO算法的解優(yōu)于自適應(yīng)PSO算法，且計(jì)算時(shí)間短。

5 結(jié)論

針對(duì)含多種物料搬運(yùn)設(shè)備的車間送料問(wèn)題，提出多種物料搬運(yùn)設(shè)備協(xié)同調(diào)度物料配送模型，并設(shè)計(jì)改進(jìn)粒子群算法尋求最優(yōu)解，得到具體物料配送方法。所得研究成果可幫助企業(yè)合理安排物料搬運(yùn)設(shè)備，為企業(yè)提供一種準(zhǔn)時(shí)化物料供應(yīng)方法，避免企業(yè)為防止缺貨而頻繁送貨，可有效降低企業(yè)成本。然而，文總在研究多種搬運(yùn)設(shè)備協(xié)同調(diào)度物料配送模型時(shí)未考慮多種搬運(yùn)設(shè)備在車間的并行可能性以及車間突發(fā)性因素，如搬運(yùn)設(shè)備故障、裝配計(jì)劃變更等；后續(xù)將進(jìn)一步研究并行可能性以及不確定因素對(duì)模型的影響。