彭慧杰 ，李成松 ，李景彬 ，朱新月

（1.石河子大學(xué)機(jī)械電氣工程學(xué)院，新疆 石河子 832000；2.農(nóng)業(yè)部西北農(nóng)業(yè)裝備重點(diǎn)實(shí)驗(yàn)室，新疆 石河子 832003）

1 引言

在穩(wěn)步推進(jìn)精準(zhǔn)農(nóng)業(yè)發(fā)展背景下，作為先進(jìn)生產(chǎn)力的示范區(qū)，2017 年新疆生產(chǎn)建設(shè)兵團(tuán)農(nóng)作物精量半精量播種面積達(dá)955.6 千公頃[1]。穴播器是精量播種的關(guān)鍵設(shè)備之一，其多品種、小批量的混流裝配模式成為播種機(jī)制造企業(yè)發(fā)展趨勢。保證物料配送準(zhǔn)確響應(yīng)裝配線動態(tài)物料需求變化，是提高企業(yè)裝配效率的關(guān)鍵。

目前，國內(nèi)外車間物料配送研究主要集中在配送策略、控制方法和路徑優(yōu)化等方面。文獻(xiàn)[2]針對不確定環(huán)境下混裝特點(diǎn)，提出一種和配送區(qū)間相匹配的動態(tài)周期物料配送策略。文獻(xiàn)[3]針對混裝線內(nèi)部零件供應(yīng)問題，提出基于線邊超市的物料及時(shí)供應(yīng)策略。文獻(xiàn)[4]研究電梯零部件的物料管理與跟蹤問題，提出一種基于無線射頻識別的立體化倉儲物料管理方法。文獻(xiàn)[5]基于在復(fù)雜產(chǎn)品裝配過程中的時(shí)間、效率和追溯需求，提出了一種基于條碼的物流控制技術(shù)。文獻(xiàn)[6]針對物料配送準(zhǔn)時(shí)化需求的路徑優(yōu)化問題，建立數(shù)學(xué)模型并設(shè)計(jì)具有較快收斂速度的改進(jìn)蟻群算法。

以上學(xué)者研究的問題規(guī)模及其所針對的環(huán)境有所區(qū)別，導(dǎo)致上述成果并不能完全適用于傳統(tǒng)小微農(nóng)機(jī)裝備制造企業(yè)。針對穴播器混裝線多品種、小批量生產(chǎn)方式亟待解決的物料配送問題，擬綜合考慮配送策略、控制方法和路徑規(guī)劃，對裝配線動態(tài)物料配送方法進(jìn)行優(yōu)化研究。開發(fā)一種拉動式動態(tài)物料聯(lián)合配送方案，構(gòu)建路徑優(yōu)化數(shù)學(xué)模型并設(shè)計(jì)遺傳算法求解，最后實(shí)例驗(yàn)證模型的正確性。

2 動態(tài)物料配送方案

2.1 物料分類

物料分類是庫存管理和物流配送的前提，不同物料的配送策略有所不同。分析穴播器BOM 表，根據(jù)混流裝配線物料特點(diǎn)將其分為序列件和非序列件兩種。標(biāo)準(zhǔn)件等體積小重量輕的物料稱為非序列件，一般成箱成盒配送；不同型號產(chǎn)品之間有差異的物料稱為序列件，應(yīng)結(jié)合生產(chǎn)排程配送。序列件是配送重點(diǎn)，為保證配送方案完整，分別考慮領(lǐng)料和補(bǔ)料兩個過程。開工之前，工位線邊庫存為零，需進(jìn)行領(lǐng)料活動。裝配過程中，當(dāng)工位線邊庫存降至物料請求點(diǎn)后，拉動補(bǔ)料過程。每個生產(chǎn)周期內(nèi)可能會發(fā)生多次物料配送，每個配送周期由一個領(lǐng)料過程和多個補(bǔ)料過程組成，如圖1 所示。

圖1 物料配送周期Fig.1 Material Delivery Cycle

2.2 動態(tài)配送方法

2.2.1 領(lǐng)料配送策略

領(lǐng)料過程發(fā)生在生產(chǎn)準(zhǔn)備階段，是物料配送周期的開始，應(yīng)結(jié)合排產(chǎn)情況、物料BOM 表與線邊庫存容量等確定不同類型序列件的領(lǐng)料數(shù)量。

以穴播器混流裝配線為例進(jìn)行說明，混裝線可裝配五種不同型號的穴播器 X7，X8，X9，X10，X15，每個產(chǎn)品裝配 1 個腰帶（序列件），其型號分別為 Y7，Y8，Y9，Y10，Y15。假設(shè)工位線邊庫存最大容量為10，某階段穴播器的排產(chǎn)結(jié)果為：X7X7X8X8X9X10X10X10X15X7，則領(lǐng)料過程物料配送具體數(shù)量如下：3 個 Y7，2 個 Y8，1 個 Y9，3 個Y10，1 個 Y15。

2.2.2 補(bǔ)料配送方案

補(bǔ)料過程較領(lǐng)料過程更為復(fù)雜，現(xiàn)有研究關(guān)于物料的補(bǔ)充方式主要有單一物料單獨(dú)補(bǔ)充和多類物料聯(lián)合補(bǔ)充兩種，擬研究一種拉動式的動態(tài)物料聯(lián)合配送方案。

圖2 補(bǔ)料配送策略Fig.2 Feed Distribution Strategy

補(bǔ)料配送策略，如圖2 所示。裝配時(shí)，當(dāng)有工位線邊庫存到達(dá)補(bǔ)料請求點(diǎn)時(shí)，率先拉動補(bǔ)料過程。補(bǔ)料請求點(diǎn)為定值，在數(shù)值上等于訂貨提前期內(nèi)的物料消耗量與該物料松弛時(shí)間內(nèi)的消耗量之和。在松弛時(shí)間內(nèi)，收集該補(bǔ)料周期內(nèi)其他工位補(bǔ)料請求信息，進(jìn)行聯(lián)合配送。為避免裝配線停產(chǎn)，規(guī)定最晚到貨時(shí)刻為線邊庫存恰好完全消耗。補(bǔ)料過程配送的物料數(shù)量是一個區(qū)間值，其最小數(shù)量應(yīng)滿足：補(bǔ)料后該工位能裝配的產(chǎn)品數(shù)與領(lǐng)料后最早拉動物料請求工位的線邊庫存能裝配的產(chǎn)品數(shù)相同；其最大數(shù)量應(yīng)滿足：補(bǔ)料后該工位線邊庫存飽和。在該動態(tài)物料聯(lián)合配送方案中，拉動補(bǔ)料過程的唯一條件是最早物料請求工位的線邊庫存降至物料請求點(diǎn)，保障配送有序進(jìn)行。

工位線邊庫存變化，如圖3 所示。在物料配送周期中，工位線邊庫存在領(lǐng)料過程結(jié)束瞬間飽和。隨著裝配進(jìn)行，物料消耗，線邊庫存降至物料請求點(diǎn)，拉動補(bǔ)料過程。在松弛時(shí)間內(nèi)收集其他補(bǔ)料請求信息，到達(dá)訂貨提前期，線邊庫存降至訂貨提前期內(nèi)物料消耗量。補(bǔ)料過程結(jié)束，線邊庫存數(shù)量位于卸貨后物料必須達(dá)到的最小點(diǎn)和最大線邊庫存之間。

圖3 裝配工位線邊庫存變化Fig.3 Change in Line Side Stock of Assembly Station

3 問題描述與數(shù)學(xué)模型

3.1 問題描述

穴播器混流裝配線動態(tài)物料配送問題可描述為：在車間物料存儲區(qū)和裝配線多個工位之間，規(guī)劃合適的行車路徑，使搬運(yùn)車輛以一定的順序依次經(jīng)過他們，在滿足一定約束條件的基礎(chǔ)上，達(dá)到既定目標(biāo)。為避免混裝線因工位線邊庫存耗竭而導(dǎo)致停產(chǎn)，需嚴(yán)格限制物料的最晚到達(dá)時(shí)刻，此類配送問題屬于有時(shí)間窗限制的車輛路徑問題。穴播器車間物料配送影響因素較多，需制定合理的優(yōu)化目標(biāo)與約束條件。

（1）優(yōu)化目標(biāo)

為使配送效率最高且成本最低，擬對多個物料聯(lián)合配送，故選取動態(tài)物料聯(lián)合配送方案的具體優(yōu)化目標(biāo)為以下兩個：

①車輛運(yùn)輸時(shí)間最短化；

②搬運(yùn)車輛數(shù)量最小化。

（2）約束條件

為使混裝線補(bǔ)料方案更符合生產(chǎn)實(shí)際，同時(shí)提高動態(tài)物料聯(lián)合配送方案的有效性，設(shè)置約束條件應(yīng)滿足以下五點(diǎn)：

①車型約束：車間內(nèi)搬運(yùn)車輛只有一種類型；

②行程約束：車輛從物料存儲區(qū)起止；

③數(shù)量約束：工位接收物料不得超過最大線邊庫存；

④裝載約束：車輛每次配送物料數(shù)量總和不得超載；

⑤時(shí)間約束：設(shè)單邊硬時(shí)間窗，限制最晚到貨時(shí)刻。

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

設(shè)定每個物料請求工位僅需一種序列件，物流點(diǎn)集合D=｛0，1，…，n｝，其中 0 表示物料存儲區(qū)，1，…，n 表示相關(guān)工位。物料存儲區(qū)和各工位之間節(jié)點(diǎn)坐標(biāo)矩陣D，如式（1）所示。

車間有充足的搬運(yùn)車輛可進(jìn)行物料配送，車型最大裝載量為常量q。工位i 配送的物料數(shù)量為決策變量qi（1，2，…，n），其不得超過車輛最大裝載量，取值范圍為［qimin，qimax］。已知每出動一輛搬運(yùn)車輛的固定成本為C1，單位距離的變動成本為C2。一種物料只允許通過一臺車輛配送，每一次配送過程必須在最晚到貨時(shí)刻之前結(jié)束。

（1）目標(biāo)函數(shù)，如式（2）所示。

（2）約束條件如下所示：

式中：yik—0-1 變量，當(dāng)工位 i 由車輛 k 配送時(shí)為 1，否則為 0；xijk—0-1 變量，當(dāng)車輛 k 經(jīng)過工位 i 到達(dá) j 時(shí)為 1，否則為 0；qi—工位i 配送的物料數(shù)量；q—車輛最大裝載量；m—補(bǔ)料過程需要的車輛數(shù)；W—生產(chǎn)節(jié)拍；Ni—某個產(chǎn)品需要物料i 的數(shù)量；Si—物料i 的物料請求時(shí)刻；Ui—物料i 拉動補(bǔ)料過程時(shí)，對應(yīng)工位線邊庫存可裝配產(chǎn)品數(shù)；Sik—車輛k 將物料i 運(yùn)輸至所需工位的時(shí)刻；Q—領(lǐng)料過程完成時(shí)，最早物料請求工位線邊庫存可裝配的產(chǎn)品數(shù)量；Qimax—物料i 所需工位線邊庫存最大時(shí)可裝配的產(chǎn)品數(shù)量；dij—工位i 與j 之間的距離；tij—工位i與j 之間的運(yùn)輸時(shí)間；α—足夠大的數(shù)；bi—物料i 的最晚到貨時(shí)刻；qimin—物料i 的最小配送數(shù)量；qimax—物料i 的最大配送數(shù)量。

式（3）約束搬運(yùn)車輛數(shù)量；式（4）約束所有物料都有車輛配送；式（5）和式（6）約束每種物料能且僅能被一輛搬運(yùn)車輛配送；式（7）約束各車輛的裝載量不超載；式（8）約束車輛搬運(yùn)路線的連貫性；式（9）約束搬運(yùn)車輛以合理的時(shí)間按順序依次到達(dá)各工位；式（10）約束搬運(yùn)車輛滿足工位的時(shí)間窗限制；式（11）約束物料的配送數(shù)量范圍；式（12）與式（13）約束物料的最小和最大配送數(shù)量；式（14）約束物料的最晚到達(dá)時(shí)刻；式（15）約束消除子回路。

4 基于遺傳算法的模型求解

4.1 算法概述

VRP 模型是典型NP 難問題，主要有精確算法和啟發(fā)式算法等求解方法，精確算法因自身特性而不適用于求解大規(guī)模問題。啟發(fā)式算法是基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，在可接受的時(shí)間和空間下給出組合優(yōu)化問題的可行解。遺傳算法是元啟發(fā)式算法之一，在車輛路徑問題中的應(yīng)用較為豐富。

4.2 遺傳算法設(shè)計(jì)

4.2.1 編碼

擬采用順序編碼方式，實(shí)際為三段式編碼，分別為：車輛數(shù)、配送工位和車輛編號。染色體個體的編碼方式，如圖4 所示。車2配送工位 4，2，3，車 1 配送工位 1，5，6。

圖4 染色體編碼方式Fig.4 Chromosome Coding

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

適應(yīng)度是度量種群個體質(zhì)量的指標(biāo)，遺傳算法的關(guān)鍵在于判據(jù)的選取。遺傳算法要求適應(yīng)度函數(shù)取正值，由于目標(biāo)函數(shù)為求最小值，故取其倒數(shù)作為適應(yīng)度函數(shù)，即Fit=1/F。

4.2.3 遺傳算子操作

選擇：為避免搜索獲得局部最優(yōu)解，在采取最優(yōu)保存策略的基礎(chǔ)上結(jié)合輪盤賭法進(jìn)行遺傳算子的選擇操作。

交叉：為避免出現(xiàn)非法染色體，主要對第二段編碼進(jìn)行交叉操作。在種群中隨機(jī)選擇兩個染色體為父本，并任選一個區(qū)域交叉，得到子代1 和子代2。

變異：為改進(jìn)算法的全局搜索能力，對配送順序和搬運(yùn)車輛的編碼進(jìn)行變異操作。配送順序的變異可在染色體第二段中隨機(jī)選取兩點(diǎn)進(jìn)行調(diào)換，搬運(yùn)車輛的變異可在染色體第三段中隨機(jī)選取一個車輛編號更改為另一個可行編號。

4.2.4 終止

終止條件一般為預(yù)先設(shè)定最大遺傳代數(shù)的方法，當(dāng)算法迭代到最大代數(shù)時(shí)終止計(jì)算，一般取迭代次數(shù)為（100～1000）。

5 實(shí)例驗(yàn)證

以R 農(nóng)機(jī)裝備制造企業(yè)穴播器混流裝配線為研究對象，實(shí)例驗(yàn)證動態(tài)物料配送方法的有效性。該裝配線共有10 個工位，1個物料存儲區(qū)和3 臺搬運(yùn)車輛，每個物料請求工位需1 種序列件，生產(chǎn)節(jié)拍為259.8s。車輛裝載量為60，以1m/s 的速度勻速行駛。每輛車運(yùn)輸?shù)墓潭ǔ杀緸?0，每運(yùn)行1m 的變動成本為1。在某補(bǔ)料周期內(nèi)，穴播器混裝線共有6 個工位發(fā)出了物料請求，工位節(jié)點(diǎn)坐標(biāo)矩陣，如式（16）所示。工位0 為物料存儲區(qū)即配送中心，其坐標(biāo)為（0，0）。

工位物料相關(guān)信息，如表1 所示。工位1 最早發(fā)出物料請求，松弛時(shí)間259.8s，即所有工位補(bǔ)料在一個周期內(nèi)。

表1 工位物料相關(guān)信息表Tab.1 Station Material Related Information

采用Matlab 遺傳算法求解，取種群規(guī)模100，最大遺傳代數(shù)200，交叉概率0.9，變異概率0.05。隨機(jī)運(yùn)行10 次，最優(yōu)成本為94.3，行駛距離為74.3，需2 輛車進(jìn)行配送。車輛運(yùn)行結(jié)果，如表2所示。物料配送結(jié)果，如表3 所示。遺傳優(yōu)化過程，如圖5 所示。車輛行駛軌跡，如圖6 所示。從結(jié)果可知，物料實(shí)際配送數(shù)量與到貨時(shí)刻均滿足相關(guān)約束，且車輛的裝載率也較高，驗(yàn)證了動態(tài)物料配送方法的正確性，該結(jié)果可供現(xiàn)場物料配送參考。

表2 車輛運(yùn)行結(jié)果表Tab.2 Vehicle Operation Results

表3 物料配送結(jié)果表Tab.3 Material Distribution Results

圖5 遺傳優(yōu)化過程Fig.5 Genetic Optimization Process

圖6 車輛行駛軌跡Fig.6 Vehicle Trajectory

6 結(jié)論

針對穴播器混流裝配線多品種、小批量生產(chǎn)方式亟待解決的物料配送問題，重點(diǎn)研究序列件領(lǐng)料和補(bǔ)料兩個過程的配送方法。設(shè)計(jì)了一種一次配送能滿足多個工位需求的動態(tài)物料聯(lián)合配送方案。建立了以車輛數(shù)量最少、行駛時(shí)間最短為目標(biāo)，帶單邊硬時(shí)間窗等約束的車輛路徑問題數(shù)學(xué)模型，并設(shè)計(jì)遺傳算法求解。實(shí)例驗(yàn)證表明，工位實(shí)際配送物料數(shù)量和到達(dá)時(shí)刻均滿足約束條件，說明模型正確且算法有效。