陶燁

摘要：汽車制造有四大關(guān)鍵工藝——沖壓、焊接、涂裝和總裝，其中總裝車間的占地面積最大、工人數(shù)量最多，迫切需要技術(shù)幫助降本增效。本文構(gòu)建了以所有車輛服務(wù)工位間的距離總和與倉(cāng)庫(kù)間的距離總和為目標(biāo)的優(yōu)化模型，并設(shè)計(jì)了遺傳算法進(jìn)行求解，最終得到了適應(yīng)度值為2.1785543113589823e-05的分配方案。

關(guān)鍵詞：工位分組;配送物料優(yōu)化;遺傳算法

中圖分類號(hào)：F407.474? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)：1674-957X（2021）16-0153-02

1? 問(wèn)題分析

物料配送的全周期主要包含兩個(gè)步驟：①取料：前往目標(biāo)物料的存儲(chǔ)位，將物料裝載至拖車;②配送：將物料運(yùn)送至目標(biāo)工位和卸載。這就意味著，要想在承包制模式下提高整個(gè)汽車組裝車間的配送效率，就需要盡可能讓車輛從距離較近的幾個(gè)倉(cāng)庫(kù)取到裝配工位較近的物料。即本文認(rèn)為，讓所有車輛節(jié)省取貨時(shí)的行駛成本與送貨時(shí)的行駛成本可以提升整個(gè)車間的效率。[1]基于此想法，本文構(gòu)建了的模型，并且設(shè)計(jì)了算法進(jìn)行求解，詳細(xì)的思路、模型及算法詳見(jiàn)后文。

2? 符號(hào)說(shuō)明

D：倉(cāng)庫(kù)的集合;

N：工位的集合;

K：車輛的集合;

dij：位置i與位置j之間的行駛距離;

tij：位置i與位置j之間的行駛時(shí)間;

L：車輛裝/卸零件耗時(shí);

S：車輛的行駛速度;

M：最大可裝載任務(wù)數(shù);

Tn：工位n的需求時(shí)間;

tkn：車輛k到達(dá)工位n的時(shí)間;

ω1：車輛晚于需求時(shí)間帶來(lái)的懲罰成本;

■;

■。

3? 建模與求解

3.1 建模

結(jié)合前述對(duì)模型的分析，我們認(rèn)為在承包制模式下是對(duì)工位進(jìn)行劃分時(shí)，需要考慮車輛從III區(qū)裝貨過(guò)程產(chǎn)生的行駛成本，所以在形成分配方案時(shí)要將裝貨過(guò)程的影響考慮進(jìn)來(lái)，不能只是按照工位的分布特點(diǎn)來(lái)劃分承包區(qū)。據(jù)此，提出了模型的優(yōu)化目標(biāo)如公式（1）所示。

（1）

式（1）中共有兩部分構(gòu)成，其中■表示所有車輛服務(wù)工位間的距離總和，■表示倉(cāng)庫(kù)間的距離總和，該目標(biāo)值越小則說(shuō)明車輛的行駛距離越短，車間效率越高。

3.2 求解模型

3.2.1 距離數(shù)據(jù)的獲取

基于求解模型的思想，我們需要計(jì)算出工位與工位之間的距離[2]，倉(cāng)庫(kù)與倉(cāng)庫(kù)之間的距離，此外，對(duì)于后文的研究會(huì)利用到工位與倉(cāng)庫(kù)之間的距離，故在此將計(jì)算這三部分距離數(shù)據(jù)：

①工位與工位之間的距離;

②倉(cāng)庫(kù)與倉(cāng)庫(kù)之間的距離;

③工位與倉(cāng)庫(kù)之間的距離。

由于汽車裝配車間的結(jié)構(gòu)復(fù)雜，工位分布呈流水線形式，道路的排布也十分有特點(diǎn)，直接導(dǎo)致了獲取不同位置間的距離需要進(jìn)行歸類然后對(duì)每一類進(jìn)行計(jì)算。本文根據(jù)車間構(gòu)造的特點(diǎn)在對(duì)任意兩個(gè)位置間的距離進(jìn)行計(jì)算時(shí)，設(shè)計(jì)了如圖1所示的框架。

通過(guò)上述計(jì)算距離的框架可以計(jì)算出任意兩個(gè)位置間的距離，本文利用Python編程進(jìn)行計(jì)算，部分距離結(jié)果見(jiàn)表1。

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

在計(jì)算得到距離數(shù)據(jù)后，本文設(shè)計(jì)了遺傳算法對(duì)承包區(qū)的劃分進(jìn)行了求解。算法的具體流程如下所示：

①編碼與解碼。將I區(qū)與II區(qū)的48個(gè)工位以列表的數(shù)據(jù)結(jié)構(gòu)隨機(jī)排序，在排序后將整個(gè)列表劃分為10個(gè)部分，并使每個(gè)部分不得超過(guò)5個(gè)工位，其中每個(gè)部分就是一個(gè)承包區(qū)。

②適應(yīng)度函數(shù)。適應(yīng)度函數(shù)用來(lái)評(píng)價(jià)個(gè)體的優(yōu)劣，本文選取目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)，即適應(yīng)度函數(shù)fitness=■。

③選擇操作。本文采取了輪盤賭選擇法[3]，該方法又稱比例選擇方法，基本思想是：各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比。具體操作可以表示為：1）計(jì)算出群體中每個(gè)個(gè)體的適應(yīng)度;2）計(jì)算出每個(gè)個(gè)體被遺傳到下一代群體中的概率;3）計(jì)算出每個(gè)個(gè)體的累積概率;4）在[0，1]區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的偽隨機(jī)數(shù)r;5）若r<q[1]，則選擇個(gè)體1，否則，選擇個(gè)體k，使得：q[k-1]<r≤q[k]成立;6）重復(fù)4）和5）直到選擇出整個(gè)種群。

④交叉操作。隨機(jī)選擇兩條染色體，然后隨機(jī)選擇兩個(gè)基因位，兩個(gè)基因位間的部分作為交叉部分，分別將兩條染色體的交叉部分放置到彼此的前段，然后從前向后排查，將染色體中重復(fù)的基因刪除，這樣可以獲得子代染色體。

⑤變異操作。隨機(jī)算計(jì)一條染色體并隨機(jī)選擇兩個(gè)位置，將兩個(gè)基因進(jìn)行互換。

⑥終止規(guī)則。本文采取設(shè)置最大迭代次數(shù)的方式作為改進(jìn)遺傳算法的終止條件。

3.2.3 求解結(jié)果

設(shè)置種群數(shù)量為100，最大迭代次數(shù)為100代，交叉概率為0.9，變異概率為0.1，利用上述遺傳算法的求解，最終計(jì)算得到適應(yīng)度函數(shù)為2.1785543113589823e-05的優(yōu)化方案，具體分組結(jié)果如表2所示的結(jié)果，算法收斂曲線圖如圖2所示。

4? 總結(jié)

本文成功對(duì)汽車組裝車間背景下物料配送的相關(guān)問(wèn)題進(jìn)行了數(shù)學(xué)建模，并設(shè)計(jì)了以遺傳算法對(duì)模型進(jìn)行求解。對(duì)于模型的求解本文設(shè)計(jì)了高效的遺傳算法用以求解模型，在交叉操作的設(shè)計(jì)上，成功規(guī)避了個(gè)體基因的重復(fù)，同時(shí)對(duì)于軟硬約束的處理通過(guò)“罰值”得到了有效的控制，使得模型的有效性和健壯性得到了極大的增強(qiáng)。

參考文獻(xiàn)：

[1]吳亮亮，蔡紅霞，朱政.汽車零件制造企業(yè)物料配送模式優(yōu)化[J].工業(yè)控制計(jì)算機(jī)，2020，33（02）：124-125.

[2]李晉航.混流制造車間物料配送調(diào)度優(yōu)化研究[D].華中科技大學(xué)，2012.

[3]李永林，葉春明，劉長(zhǎng)平.輪盤賭選擇自適應(yīng)和聲搜索算法[J].計(jì)算機(jī)應(yīng)用研究，2014，31（06）：1665-1668.