基于改進遺傳算法的汽車混流裝配線物料配送路徑優化

張新敏+李亮+劉設

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

關鍵詞：汽車裝配線；VRPTW；改進遺傳算法

中圖分類號：F252.14 文獻標識碼：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 引 言

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

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

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

1 問題描述

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

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

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

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

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

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

2 模型建立

本文的VRPTW模型建立如下：

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

3 改進遺傳算法設計

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

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

3.2 適應度函數。適應度函數是用來評價染色體的優劣，適應度值越大，染色體越優越。本文提出的VRPTW模型，目標函數值越大，即染色體越優越，因此本文采用目標函數作為適應度函數。

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

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

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

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

3.6 終止進化規則。本文采用種群中個體在連續10代中未獲得改進作為終止進化規則。

4 算例驗證

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

4.2 算法對比驗證。將上述算例數據帶入相關程序進行運行，得出結果見表3至表6和圖2、圖3。

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

5 結 論

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

參考文獻：

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

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

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

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

[5] 侯玉梅，賈震環，田歆，等. 帶軟時間窗整車物流配送路徑優化研究[J]. 系統工程學報，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] 劉海，郝志峰，林智勇. 改進遺傳交叉算子求解TSP問題[J]. 華南理工大學學報，2002，30（12）：71-73.endprint