基于時(shí)間窗約束的車間物料配送路徑優(yōu)化方法

朱伏平，曹婷婷

（西南科技大學(xué)制造科學(xué)與工程學(xué)院，四川綿陽 621010）

1 引言

隨著制造業(yè)的高速發(fā)展，混流生產(chǎn)已成為企業(yè)滿足市場需求的有效手段?；炝魃a(chǎn)中待配送的零部件種類繁雜、配送頻率較高。同時(shí)，自動(dòng)化設(shè)備的廣泛應(yīng)用，裝配時(shí)間偏差、設(shè)備故障等不確定因素，增大了物料配送的難度。因此，研究混流裝配線物料配送具有重要意義。

傳統(tǒng)的物料配送多側(cè)重于算法的設(shè)計(jì)。文獻(xiàn)[1]針對車輛路徑問題，提出一種結(jié)合螢火蟲優(yōu)化和蟻群系統(tǒng)算法的HAFA 算法。文獻(xiàn)[2]在冷鏈物流路徑優(yōu)化模型中，針對蟻群算法收斂速度慢的問題，將A*算法與蟻群算法相結(jié)合。文獻(xiàn)[3]提出一種通用的啟發(fā)式算法，能解決五種車輛路徑問題。文獻(xiàn)[4]建立了混流車間物料配送路徑模型并設(shè)計(jì)基于柵格環(huán)境地形的蟻群算法，并驗(yàn)證了算法的有效性。針對大量不確定因素導(dǎo)致實(shí)際需求發(fā)生偏差問題，文獻(xiàn)[5]用正態(tài)模糊數(shù)的隸屬度表征工位對物料到達(dá)時(shí)間的滿意度。文獻(xiàn)[6]用物料到達(dá)時(shí)間的模糊隸屬度函數(shù)表征工位對物料到達(dá)時(shí)間的滿意度。文獻(xiàn)[7]用三角模糊數(shù)來表征工位對物料到達(dá)時(shí)間的滿意度。模糊時(shí)間窗在一定程度上提高了物料配送時(shí)間的準(zhǔn)確性，但未考慮車間實(shí)際生產(chǎn)情況。

近年，信息化技術(shù)為實(shí)時(shí)生產(chǎn)驅(qū)動(dòng)物料配送提供了依據(jù)。文獻(xiàn)[8]采用智能感知網(wǎng)獲取工位實(shí)時(shí)生產(chǎn)數(shù)據(jù)，利用物料送達(dá)時(shí)間點(diǎn)與物料消耗速度確定每次配送時(shí)間窗，提高物料配送的準(zhǔn)確性。但未考慮不確定性因素導(dǎo)致物料消耗速度的波動(dòng)性。

基于上述分析，這里提出將實(shí)時(shí)生產(chǎn)數(shù)據(jù)與正態(tài)模糊數(shù)相結(jié)合的方法來計(jì)算時(shí)間窗。針對無法在規(guī)定時(shí)間窗內(nèi)到達(dá)的車輛，建立成本懲罰函數(shù)。以配送成本最低為目標(biāo)建立模型，采用改進(jìn)遺傳算法求解。最后應(yīng)用實(shí)例驗(yàn)證方法的有效性。

2 工位物料需求時(shí)間數(shù)學(xué)模型

根據(jù)實(shí)時(shí)生產(chǎn)數(shù)據(jù)動(dòng)態(tài)計(jì)算時(shí)間窗，然后利用正態(tài)模糊數(shù)來表征工位物料需求，從而提高工位物料需求時(shí)間滿意度。

以工位不缺料為前提，計(jì)算工位服務(wù)時(shí)間區(qū)間長度[9]：

防止物料提前達(dá)到而出現(xiàn)等待，設(shè)置最早到達(dá)時(shí)間TEi：

防止因缺料而停線現(xiàn)象，設(shè)置物料最晚到達(dá)時(shí)間TLi，m：

式中：Vi，max—工位i的物料緩存區(qū)的最大容量—工位i的物料緩存區(qū)的安全庫存；ci—單位物料在工位i的裝配時(shí)間；Ti，m?1—工位i第m?1次物料送達(dá)時(shí)間；Vi，m?1—工位i第m?1次物料送達(dá)時(shí)工位i的線邊庫存；ti，m—工位i第m次配送的服務(wù)時(shí)間；m>1。

通過實(shí)時(shí)數(shù)據(jù)計(jì)算得到的工位i第m次配送的物料需求時(shí)間為[TEim，TLim]，根據(jù)文獻(xiàn)［5］建立基于正態(tài)模糊數(shù)的物料需求時(shí)間滿意度數(shù)學(xué)模型：

式中：ui，m—Ti，m的期望值；σi，m—高斯函數(shù)的寬度；μ(Ti)，m—Ti，m的隸屬度，μ()Ti，m∈[0，1]，用于表示工位的滿意度。Ts—期望時(shí)間，Ti，m離TS越近，滿意度值越大；當(dāng)Ti，m=Ts時(shí)，滿意度最大為1。β—物料需求時(shí)間的正態(tài)模糊數(shù)置信度。TEi，m′，TLi，m′—置信度β下，工位i的時(shí)間窗下限和上限，如圖1所示。

圖1 工位i在置信度為β時(shí)配送時(shí)間窗Fig.1 Time Window of Distribution for Station i when Confidence Level is β

3 物料配送模型構(gòu)建

3.1 問題描述

裝配車間由一個(gè)倉庫向N個(gè)工位提供物料，各工位旁有一個(gè)緩存量為Vi，max的物料緩存區(qū)，倉庫有K輛運(yùn)載能力為V的配送小車，始終保持勻速行駛。假設(shè)通過實(shí)時(shí)采集數(shù)據(jù)已知各工位的位置、需求量、物料服務(wù)時(shí)間和配送時(shí)間窗，建立總配送費(fèi)用最低的路徑規(guī)劃數(shù)學(xué)模型。每個(gè)工位只能由一輛車訪問一次，且滿足以下主要約束條件：

（1）運(yùn)載能力約束。任意小車所服務(wù)的工位物料需求量總和不超過最大運(yùn)載能力為V。

（2）持續(xù)能力約束。小車從倉庫出發(fā)，完成任務(wù)后回到倉庫，總行駛距離不超過最大行駛距離L。

（3）時(shí)間窗約束。工位接受物料時(shí)間窗為[TEi,m′,TLi,m′]，如小車未在[TEi，m′，TLi，m′]內(nèi)到達(dá)，則建立相應(yīng)的成本懲罰函數(shù)，如下：

3.2 參數(shù)定義

根據(jù)問題描述，設(shè)置參數(shù)如下：

3.3 建立模型

構(gòu)建配送成本最低的目標(biāo)函數(shù)。

式（8）是總配送費(fèi)用最小的目標(biāo)函數(shù)；式（9）表示配送小車的數(shù)量；式（10）表示每個(gè)工位只能由一輛小車配送；式（11）表示任意小車運(yùn)載量不超過小車最大裝載容量；式（12）表示小車從倉庫出發(fā)，完成任務(wù)后回到倉庫，式（13）表示任意小車行駛距離不超過小車最大行駛距離，式（14）表示置信度為β時(shí)，配送時(shí)間窗限制；式（15）表示工位i需要物料時(shí)間要滿足正態(tài)模糊數(shù)的置信度β；式（16）表示工位i的等待時(shí)間。

4 模型求解

遺傳算法具有良好的全局搜索能力和魯棒性，搜索效率高，非常適合處理路徑規(guī)劃等非線性優(yōu)化問題。但容易出現(xiàn)早熟現(xiàn)象，陷入局部最優(yōu)解。因此，這里對遺傳算法進(jìn)行改進(jìn)，引入禁忌搜索算法。當(dāng)遺傳算法的迭代次數(shù)為10的整數(shù)倍時(shí)，執(zhí)行禁忌搜索，利用禁忌策略限制搜索陷入局部最優(yōu)。算法流程，如圖2所示。

圖2 算法執(zhí)行流程Fig.2 Execution Flow of Algorithm

4.1 編碼

這里采取自然數(shù)編碼方式，設(shè)計(jì)兩層染色體，第一層表示配送工位，第二層表示配送小車。第一輛小車的配送路徑為0?7?6?1?0；第二輛小車的配送路徑為0?4?5?2?0；第三輛小車的配送路徑為0?8?3?0，如圖3所示。

圖3 編碼示意圖Fig.3 Coding Diagram

4.2 適應(yīng)度設(shè)計(jì)

初始群體按編碼生成配送路徑方案，編碼隱含每個(gè)工位僅由一輛車服務(wù)一次的約束條件，但不能保證小車配送最大行駛距離和載重量的約束。

為此，對判斷每條子路徑是否滿足約束條件。這里假設(shè)個(gè)體i所有子路徑中不可行（Yi>0）的個(gè)數(shù)為Yi，模型目標(biāo)函數(shù)為Zi，則自適應(yīng)度值為：

式中：W—無窮大的數(shù)，用于懲罰不可行個(gè)體。

4.3 遺傳操作

4.3.1 選擇策略

為保證適應(yīng)度高的個(gè)體進(jìn)入下一代，采用最佳個(gè)體保留法結(jié)合輪盤賭法的方法。

4.3.2 交叉策略

傳統(tǒng)的交叉方式可能產(chǎn)生大量不可行解，從而丟失優(yōu)良解，這里采用一種改進(jìn)的交叉法[10]進(jìn)行交叉，其基本流程如下：

（1）根據(jù)選擇策略選取兩條染色體作為父代A、B；

（2）隨機(jī)選擇父代A、B的交叉區(qū)域；

（3）提取父代A、B的交叉區(qū)域配送工位基因值，如果基因值相同，則交叉區(qū)域進(jìn)行交換，從而得到子代A1、B1，若基因值不相同，則返回（2）；

（4）計(jì)算父代A、B，子代A1、B1的適應(yīng)度值，保留較優(yōu)的兩個(gè)作為新個(gè)體A2、B2。

圖4 交叉操作示意圖Fig.4 Schematic Diagram of Cross Operation

4.3.3 變異策略

為維持種群多樣性，提高算法的局部搜索能力，本文選擇分組單點(diǎn)變異，其基本流程如下所示：

（1）根據(jù)選擇策略選取兩條染色體作為父代C；

（2）隨機(jī)選擇父代C基因中的兩個(gè)非零點(diǎn)；

圖5 變異操作示意圖Fig.5 Schematic Diagram of Variation Operation

（3）確保配送工位基因不變，交換兩工位間的配送路線，得到子代C1；

（4）計(jì)算父代C和子代C1的適應(yīng)度值，保留較優(yōu)的一個(gè)作為新個(gè)體C2。

4.4 禁忌搜索策略

禁忌搜索的基本流程如下：

（1）選擇通過遺傳操作產(chǎn)生的當(dāng)前代中所有個(gè)體為子集，建立禁忌搜索集合E；

（2）隨機(jī)選擇集合E中的一個(gè)個(gè)體ei為初始解，并置空禁忌表和最優(yōu)狀態(tài)；

（3）根據(jù)ei生成若干候選解集；

（4）藐視規(guī)則處理。若禁忌搜索產(chǎn)生的解優(yōu)于當(dāng)前最優(yōu)解，則該解作為新的當(dāng)前最優(yōu)解和目前為止最優(yōu)解，并更新禁忌表；若禁忌搜索產(chǎn)生的解劣于當(dāng)前最優(yōu)解，則從候選集中選擇非禁忌產(chǎn)生的最優(yōu)解作為當(dāng)前解，同時(shí)更新禁忌表；

（5）重復(fù)（3）和（4），直至E中所有對象ei均進(jìn)行過禁忌搜索；

（6）輸出最優(yōu)結(jié)果。

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

為驗(yàn)證方法和模型的有效性，本文以某冰箱裝配線為例，用MATLAB進(jìn)行驗(yàn)證。裝配線有10個(gè)工位，各工位之間的距離及倉庫到各工位間的距離，如表1所示。其中0代表倉庫，1～10代表工位。

表1 工位間距離（單位：米）Tab.1 Distance Between Stations（unit：m）

配送小車的最大配送量Q=300kg，最大行駛距離為2000m，行駛速度為1m/s。

設(shè)單位距離的行駛成本C1=0.02元/米，每輛配送小車的啟動(dòng)成本C2=50 元/輛，每早到1min 的懲罰成本為C3=1 元，每遲到1min的懲罰成本為∞。

各工位的物料需求量qi、物料需求時(shí)間窗及各工位的服務(wù)時(shí)間，如表2所示。

表2 物料需求時(shí)間表Tab.2 Material Demand Schedule

設(shè)種群大小為85，交叉概率和變異概率分別為0.6、0.05，迭代次數(shù)為100。

由文獻(xiàn)[7]知，置信度β取0.2時(shí)，找到目標(biāo)函數(shù)最優(yōu)解可能性最大。

因此，這里取β為0.2，對正態(tài)模糊時(shí)間窗方法和正常時(shí)間窗方法進(jìn)行求解，結(jié)果軌跡，如圖6所示。

圖6 收斂對比圖Fig.6 Convergence Contrast Graph

由圖6可知，正態(tài)模糊時(shí)間窗方法和正常時(shí)間窗方法分別經(jīng)過36次、44次迭代收斂得到最優(yōu)解，正態(tài)模糊時(shí)間窗方法收斂速度較快比較兩種方法得到的最優(yōu)解，如表3所示。

表3 兩種方法結(jié)果對比Tab.3 Comparison of Results of Two Methods

由表3可知，正態(tài)模糊時(shí)間窗方法和正常時(shí)間窗方法計(jì)算出配送成本分別為190.11元、207.47元。從以上仿真結(jié)果及其分析可以看出，與正常時(shí)間窗方法相比，正態(tài)模糊時(shí)間窗方法的收斂速度、配送成本和總行駛距離均更優(yōu)。

6 結(jié)束語

針對混流生產(chǎn)線物料配送難度大的問題，本文提出了將實(shí)時(shí)生產(chǎn)數(shù)據(jù)與正態(tài)模糊函數(shù)相結(jié)合的時(shí)間窗計(jì)算方法。

在此基礎(chǔ)上，綜合考慮車輛啟動(dòng)費(fèi)用、行駛費(fèi)用和等待費(fèi)用，建立了帶時(shí)間窗約束的配送路徑優(yōu)化模型，并采用基于禁忌搜索的遺傳算法求解。以某冰箱裝配線為實(shí)例，驗(yàn)證了這里方法的可行性和有效性。