穴播器混流裝配線動態(tài)物料配送方法優(yōu)化研究

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

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

1 引言

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

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

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

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

2.1 物料分類

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

以穴播器混流裝配線為例進行說明，混裝線可裝配五種不同型號的穴播器 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 補料配送方案

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

圖2 補料配送策略Fig.2 Feed Distribution Strategy

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

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

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

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

3.1 問題描述

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

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

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

①車輛運輸時間最短化；

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

（2）約束條件

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 算法概述

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

4.2 遺傳算法設(shè)計

4.2.1 編碼

擬采用順序編碼方式，實際為三段式編碼，分別為：車輛數(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é)合輪盤賭法進行遺傳算子的選擇操作。

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

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

4.2.4 終止

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

5 實例驗證

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

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

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

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

表2 車輛運行結(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)方式亟待解決的物料配送問題，重點研究序列件領(lǐng)料和補料兩個過程的配送方法。設(shè)計了一種一次配送能滿足多個工位需求的動態(tài)物料聯(lián)合配送方案。建立了以車輛數(shù)量最少、行駛時間最短為目標(biāo)，帶單邊硬時間窗等約束的車輛路徑問題數(shù)學(xué)模型，并設(shè)計遺傳算法求解。實例驗證表明，工位實際配送物料數(shù)量和到達時刻均滿足約束條件，說明模型正確且算法有效。