基于改進(jìn)遺傳算法的汽車混流裝配線物料配送路徑優(yōu)化

張新敏+李亮+劉設(shè)

摘 要：物料配送的及時和準(zhǔn)確是汽車裝配線高效運作的根本。針對汽車裝配線物料配送路徑優(yōu)化的問題，運用無量綱化方法建立了以物料配送距離最短和懲罰成本最低為目標(biāo)的多目標(biāo)綜合評價物料配送路徑優(yōu)化模型，引入新的輪盤賭選擇算子和交叉算子，形成改進(jìn)遺傳算法，并采用該算法對模型進(jìn)行了求解，最后用實例驗證了該模型和改進(jìn)遺傳算法的有效性，并通過和遺傳算法的計算結(jié)果對比，驗證了改進(jìn)遺傳算法的優(yōu)越性。

關(guān)鍵詞：汽車裝配線；VRPTW；改進(jìn)遺傳算法

中圖分類號：F252.14 文獻(xiàn)標(biāo)識碼：A

Abstract： Timely and accurately distribution of the material is the fundamental of the efficient operation of automobile assembly line. A multi objective comprehensive evaluation model of material distribution path based on the shortest material distribution distance and the lowest penalty cost is established by using the method of dimensionless method. Then， an improved genetic algorithm is presented to solve it. In this algorithm， the new roulette selection operator and crossover operator are proposed. Finally， the validity of the proposed model and improved genetic algorithm is verified by an example， and the superiority of the improved genetic algorithm is also verified by comparison with the standard genetic algorithm.

Key words： automobile assembly line； VRPTW； improved genetic algorithm

0 引 言

混流生產(chǎn)線是指在不做改變或者稍微調(diào)整后就能生產(chǎn)多種不同類型和數(shù)量的相似或相近產(chǎn)品的生產(chǎn)線。汽車裝配線作為典型的混流生產(chǎn)線，其主要是完成零部件裝配工作，由于同一裝配線上產(chǎn)品種類和數(shù)量比較多，導(dǎo)致零部件的種類和數(shù)量更加繁多。物料的準(zhǔn)時化配送成為了汽車裝配線重點考慮的問題，也是提高裝配效率的關(guān)鍵所在。準(zhǔn)時化的物料配送，要求物料配送路徑最優(yōu)，成本最低，而且物料到達(dá)工位的時間有嚴(yán)格的區(qū)間要求。

目前針對混流生產(chǎn)線的物料配送路徑研究較少，對路徑優(yōu)化問題，大多是設(shè)計新的算法，提高問題的求解速度，還有一部分是根據(jù)實際研究情況，改變數(shù)學(xué)模型或者增加約束。楊斯淇結(jié)合生產(chǎn)車間的實際情況，構(gòu)建了有容量限制的物料配送優(yōu)化模型[1]；任星球等提出帶緩存區(qū)的準(zhǔn)時化物料配送問題，建立總成本最低為目標(biāo)的模型，并設(shè)計了混合量子進(jìn)化算法，對模型進(jìn)行求解[2]；高貴兵等建立了以車輛行駛距離最短、車輛利用率最大和配送次數(shù)最少為優(yōu)化目標(biāo)的多目標(biāo)配送車輛路徑優(yōu)化模型，并根據(jù)問題實際情況，設(shè)計了雙層遞進(jìn)進(jìn)化多目標(biāo)優(yōu)化算法進(jìn)行問題模型求解[3]；馬尚兵等建立了以成本最低為目標(biāo)的帶時間窗的物料配送路徑優(yōu)化模型，并設(shè)計了改進(jìn)的混合蟻群算法對模型進(jìn)行求解[4]；侯玉梅等建立了帶軟時間窗的整車物流配送路徑優(yōu)化問題，并提出自適應(yīng)遺傳算法求解[5]。國外關(guān)于路徑優(yōu)化問題研究的相對較早也比較成熟，Mazzeo等建立了一種求解帶容量限制的車輛路徑優(yōu)化的蟻群算法，并驗證了算法的高效性[6]；CHOIW提出了一個動態(tài)的物料配送系統(tǒng)，根據(jù)實際生產(chǎn)進(jìn)度動態(tài)預(yù)測生產(chǎn)線所需消耗的零部件種類和數(shù)量，然后完成配送[7]；Sulieman. D等根據(jù)不確定需求的車輛路徑問題，提出了兩個雙目標(biāo)模型，采用多目標(biāo)進(jìn)化算法求解[8]；William Ho等采用混合遺傳算法求解VRP問題，首先用領(lǐng)域搜索算法構(gòu)造初始解，然后用遺傳算法進(jìn)行求解[9]。

從上述文獻(xiàn)中也可看出，針對物料配送路徑優(yōu)化問題，大多建立單目標(biāo)的數(shù)學(xué)模型，即使建立多目標(biāo)數(shù)學(xué)模型，運用無量綱化處理多目標(biāo)函數(shù)進(jìn)行運算的研究文獻(xiàn)較少，同時考慮混合時間窗約束限制和運用改進(jìn)遺傳算法求解的文獻(xiàn)也比較少。本文根據(jù)汽車裝配線的實際需求，考慮了物料配送時間的限制，建立了以物料配送距離最短，物料在時間窗之外到達(dá)工位的懲罰成本最低為目標(biāo)的多目標(biāo)帶時間窗物料配送路徑優(yōu)化問題模型，同時運用無量綱化手段對多目標(biāo)函數(shù)進(jìn)行相加運算，最后設(shè)計了一種新的選擇算子和交叉算子的改進(jìn)遺傳算法對問題模型進(jìn)行求解。

1 問題描述

本文提出的帶有時間窗的物料配送路徑優(yōu)化問題（VRPTW）可以描述為：首先通過裝配車間生產(chǎn)計劃得到產(chǎn)品的種類和數(shù)量，再由BOM表得到所需物料種類和數(shù)量，最后按照各工位物料需求量和車間配送能力，完成物料從配送中心到需求點的配送，并且在完成配送后，小車返回配送中心。小車到達(dá)工位節(jié)點的時間也有嚴(yán)格的時間區(qū)間限制，在要求的時間區(qū)間之外到達(dá)工位節(jié)點，會造成成本增加，受到懲罰。

VRPTW就是在傳統(tǒng)的VRP模型中加入了時間窗的限制，除了要滿足物料配送嚴(yán)格的時間要求外，還要設(shè)計合理的配送路徑，使得車輛行駛距離最短。時間窗分為軟時間窗、硬時間窗和混合時間窗三種，本文根據(jù)汽車裝配車間實際情況，采用混合時間窗，如圖1所示。

要使本文提出的VRPTW模型成立，需滿足以下假定條件：endprint

（1）所有車輛都是勻速行駛，且不同車輛的速度相同；

（2）配送車輛有容載量的限制，每輛車每次的裝載量不得超過容載量；

（3）工位節(jié)點位置固定，每個工位只能由一輛車完成配送。

2 模型建立

本文的VRPTW模型建立如下：

式（6）為車輛未按工位滿意時間完成物料配送的懲罰成本；式（7）為每輛車的最大載重量不得超過Q；式（8）為每個工位有且僅有一輛車提供配送服務(wù)；式（9）、式（10）分別表示每輛車都是從配送中心出發(fā)，且最終返回配送中心；式（11）為工位i接受服務(wù)的時間范圍；式（12）為車輛k為工位i服務(wù)的起止時間；式（13）和式（14）表示工位i與工位j起止時間的關(guān)系。

3 改進(jìn)遺傳算法設(shè)計

遺傳算法是一種借鑒自然界生物進(jìn)化機制而形成的隨機全局搜索和優(yōu)化方法，由于其具有群體搜索、不需任何附加信息僅用適應(yīng)度函數(shù)值就可評估基因個體、并行計算、可擴展性和發(fā)展成熟等特性，在解決VRPTW的問題上，遺傳算法得到了廣泛的應(yīng)用。但同時，遺傳算法也存在遺漏優(yōu)秀個體、不能很好保留父代優(yōu)秀基因和算法效率低下等不足，導(dǎo)致計算結(jié)果可能不是最理想的。因此本文通過引入新的選擇算子和交叉算子，改善遺傳算法的不足，形成改進(jìn)遺傳算法。

3.1 編碼。本文中VRPTW要求，m輛車從配送中心（0）出發(fā)，完成n個工位的物料配送服務(wù)，并最終返回物料配送中心（0），且每輛車都僅要求完成一次配送和每個工位僅接受一次配送服務(wù)。根據(jù)VRPTW要求，提出了一種基于工位需求的基因分段自然數(shù)編碼模式：n個基因代表n個工位，組成染色體并隨機全排列，由m+1個基因代表m+1個物料配送中心（0），隨機插入n個工位組成的染色體，形成完整的染色體，要求染色體的首末基因位置必須為物料配送中心（0）。

3.2 適應(yīng)度函數(shù)。適應(yīng)度函數(shù)是用來評價染色體的優(yōu)劣，適應(yīng)度值越大，染色體越優(yōu)越。本文提出的VRPTW模型，目標(biāo)函數(shù)值越大，即染色體越優(yōu)越，因此本文采用目標(biāo)函數(shù)作為適應(yīng)度函數(shù)。

3.4 交叉。交叉的主要目的就是使子代能最大限度地保留父代的優(yōu)秀基因，而傳統(tǒng)的交叉算子不能很好地實現(xiàn)父代優(yōu)秀基因的遺傳，因此本文基于貪婪法的思想，提出了一種新的交叉算子，提高父代優(yōu)秀基因遺傳給子代的概率。具體方法說明如

下[10]：設(shè)現(xiàn)有工位需求點ii=1，2，…，n，待交雙親：

（3）重復(fù)步驟（2），直到生成完整的子代。

3.5 變異。變異是發(fā)生在少數(shù)基因位上的基因突變，是一種局部隨機搜索過程。本文采用逆轉(zhuǎn)變異模式，即在個體字符串中隨機選擇兩個逆轉(zhuǎn)點，使兩個逆轉(zhuǎn)點之間的基因值在變異概率為p的條件下逆向排序。

3.6 終止進(jìn)化規(guī)則。本文采用種群中個體在連續(xù)10代中未獲得改進(jìn)作為終止進(jìn)化規(guī)則。

4 算例驗證

4.1 算例描述。某汽車裝配車間有1個物料配送中心，3輛載重量為300個物料當(dāng)量的小車給8個工位段提供物料配送服務(wù)，每輛小車的固定啟動成本為1元，行駛成本為10元/km，早于最早滿意接受時間到達(dá)工位的懲罰成本系數(shù)為C=12元/h，晚于最晚滿意接受時間到達(dá)工位的懲罰成本系數(shù)為C=18元/h，M=30，現(xiàn)已知物料配送中心與各工位段之間的距離以及各工位段之間的距離（見表1）和各工位段的物料需求量d以及最佳服務(wù)時間段W，W（見表2），設(shè)計車輛物料配送路徑，使得總距離最短和總成本最低，本文中距離權(quán)重取0.4，成本權(quán)重取0.6。

4.2 算法對比驗證。將上述算例數(shù)據(jù)帶入相關(guān)程序進(jìn)行運行，得出結(jié)果見表3至表6和圖2、圖3。

由表4、表5可分別看出改進(jìn)遺傳算法和標(biāo)準(zhǔn)遺傳算法的最優(yōu)路徑分別為0—1—3—4—0—2—5—7—0—6—8—0和0—2—1—6—0—5—4—7—0—3—8—0，車輛載重率改進(jìn)遺傳算法的結(jié)果比標(biāo)準(zhǔn)的更穩(wěn)定。由表6可看出，改進(jìn)遺傳算法的計算結(jié)果，在距離、成本和綜合評價值上，優(yōu)越于標(biāo)準(zhǔn)遺傳算法。由圖2和圖3可以看出，改進(jìn)遺傳算法的收斂性能明顯優(yōu)于標(biāo)準(zhǔn)遺傳算法，改進(jìn)遺傳算法求解的行駛距離在進(jìn)化到75代左右即收斂到最短行駛距離825，而標(biāo)準(zhǔn)遺傳算法求解的行駛距離在進(jìn)化到135代左右才收斂到最短距離895；改進(jìn)遺傳算法求解的成本在進(jìn)化到75代左右達(dá)到最小成本20.07，而標(biāo)準(zhǔn)遺傳算法在進(jìn)化到135代左右才達(dá)到最小成本21.05。最終證明了本文提出的改進(jìn)遺傳算法的有效性和優(yōu)越性。

5 結(jié) 論

本文通過對VRPTW問題分析研究，并聯(lián)系生產(chǎn)實際，建立了以物料配送距離最短和物料在時間窗之外到達(dá)工位的懲罰成本最低為目標(biāo)的多目標(biāo)帶時間窗的物料配送路徑優(yōu)化問題模型，運用無量綱化方法，建立可進(jìn)行綜合評價的目標(biāo)函數(shù)，并提出改進(jìn)遺傳算法求解問題模型，該算法采用新的選擇算子和交叉算子，從而提高優(yōu)秀個體的選擇概率和遺傳給下代的概率。最終通過實際案例驗證了模型和改進(jìn)遺傳算法的有效性，并通過改進(jìn)遺傳算法與標(biāo)準(zhǔn)遺傳算法的結(jié)果對比，證明了該算法的優(yōu)越性。同時也為實際生產(chǎn)中物料配送路徑優(yōu)化問題提供了理論依據(jù)。

參考文獻(xiàn)：

[1] 楊斯淇. 基于遺傳算法的制造企業(yè)生產(chǎn)物流牽引車配送路線優(yōu)化研究[D]. 長春：吉林大學(xué)（碩士學(xué)位論文），2008.

[2] 任星球，張景玲，趙燕偉，等. 制造企業(yè)裝配線物料準(zhǔn)時配送路徑優(yōu)化問題研究[J]. 機械制造，2012，50（570）：1-4.

[3] 高貴兵，張紅波，張道兵. 混流制造車間物料配送路徑優(yōu)化[J]. 計算機工程與應(yīng)用，2014，50（15）：228-234.

[4] 馬尚兵. 基于改進(jìn)混合蟻群算法的物料配送路徑優(yōu)化研究[D]. 武漢：華中科技大學(xué)（碩士學(xué)位論文），2013.

[5] 侯玉梅，賈震環(huán)，田歆，等. 帶軟時間窗整車物流配送路徑優(yōu)化研究[J]. 系統(tǒng)工程學(xué)報，2015，30（5）：240-250.

[6] MAZZEO S， LOISEAU I. An Ant Colony Algori-thm for the Capacitated Vehicle Routing[J]. Electronic Notes in Discrete Mathematics， 2004，18：181-186.

[7] CHOIW， LEEY. A dynamic Part-feeding System for Auto-motion Assembly Line[J]. Computer & Industrial Engineering， 2002，43：123-124.

[8] Sulieman. D， Jourdan. L， Talbi. E. Using Multiobjective metaheuristics to solve VRP with uncertain demands[C] // IEEE World Congress on Computational Intelligence， 2010.

[9] William Ho， George TSH， Ping Jib， et al. A hybrid genetic algorithm for multi-depot vehicle routing problem[J]. Engineering Application of Artificial Intelligence， 2008，21（4）：548-557.

[10] 劉海，郝志峰，林智勇. 改進(jìn)遺傳交叉算子求解TSP問題[J]. 華南理工大學(xué)學(xué)報，2002，30（12）：71-73.endprint