侯秀英，李正紅，林 森，羅奕輝，鄒 斌

（福建農(nóng)林大學 交通與土木工程學院,福建 福州 350002）

基于混合算法的汽車零部件物流配送路徑優(yōu)化

侯秀英，李正紅，林 森，羅奕輝，鄒 斌

（福建農(nóng)林大學 交通與土木工程學院,福建 福州 350002）

針對汽車零部件供應(yīng)物流，建立循環(huán)取貨配送路徑優(yōu)化模型，將遺傳算法與Max-Min蟻群算法融合，采用遺傳算法生成初始信息素分布，利用Max-Min蟻群算法求精確解，并通過實例驗證。結(jié)果表明，混合算法對于解決供應(yīng)商數(shù)量多、帶時間窗限制與碳排放限制的配送路徑優(yōu)化問題，可有效降低車輛取貨頻次和提高車輛裝載率。

汽車零部件；循環(huán)取貨；遺傳算法；Max-Min蟻群算法

汽車制造企業(yè)增強供應(yīng)鏈競爭能力的重要環(huán)節(jié)之一就是汽車零部件物流。汽車零部件數(shù)量多，因此供應(yīng)商數(shù)量多，導致零部件供應(yīng)物流的組織與運行成為汽車物流中難度最重要和最復雜的環(huán)節(jié)之一[1]，對供應(yīng)鏈的敏捷度、企業(yè)的物流成本等方面的影響日益凸顯。為更好的運用運輸車輛，降低物流成本，提高供應(yīng)鏈敏捷度，循環(huán)取貨成為許多汽車制造企業(yè)供應(yīng)物流模式的首選，并在一些國際著名汽車制造企業(yè)中得到成功的應(yīng)用。

對于汽車循環(huán)取貨而言，由于供應(yīng)商數(shù)量多與嚴格的時間窗口限制，會導致車輛裝載率下降、取貨成本上升等問題，因此零部件物流車輛路徑問題（即VRP）是關(guān)鍵，即如何合理安排車輛從配送中心對顧客進行配給貨物使總運距離最短。本文以國內(nèi)一家著名的汽車物流企業(yè)實際情況為背景，對其零部件循環(huán)取貨的車輛路線問題進行優(yōu)化設(shè)計，建立相應(yīng)的數(shù)學模型，并將遺傳算法與Max-Min蟻群算法融合進行優(yōu)化求解。

1 循環(huán)取貨路徑規(guī)劃模型

汽車零件部件供需系統(tǒng)通常由若干個供應(yīng)商、若干臺運輸車輛和一個零部件配送中心構(gòu)成[2]，采用循環(huán)取貨模式時，要在既定的約束條件下合理安排運輸車輛的行車路線，使得用最少車輛進行配送。目前大多數(shù)研究就是追求路徑最短及單次取貨量最大，從而達到降低運輸成本的目的，但對由于物流系統(tǒng)中存在的效益悖反現(xiàn)象所造成的供應(yīng)商庫存成本升高等其他問題則表現(xiàn)為忽略的態(tài)度，導致難以實現(xiàn)整個系統(tǒng)最優(yōu)化。在配送過程中，如何實現(xiàn)綠色運輸也是需要考慮的問題。未來物流要做到可持續(xù)發(fā)展，必須走低碳化道路，運輸過程中應(yīng)盡量控制碳排放，將碳排放作為取貨路徑設(shè)計考慮的因素之一。因此，針對帶時間窗的循環(huán)取貨問題，在建立模型時以盡量降低運輸成本和供應(yīng)商的庫存成本為目標，并以控制碳排放量作為約束條件，使得汽車零部件物流配送既獲得較好的經(jīng)濟效益，又實現(xiàn)物流的綠色化。

假設(shè)有n個供應(yīng)商點，有m條配送路徑，循環(huán)取貨VRP模型如下：

其中，V={i|i=0,1,2,…，n}為n個供應(yīng)商點與主機廠的集合，i=0代表主機廠；K={k|k=0,1,2,…，m}為m條路徑集合；fk為路徑的取貨頻次；Cij為供應(yīng)商i到j(luò)的距離，特別地Cii=0；Pik表示如果路徑k經(jīng)過供應(yīng)商i，則一個車次到i處的單次取貨量為Pik=(di/fk)；di為供應(yīng)商i的全天需求量；Qk為路徑k上車的容量限制；ti為供應(yīng)商i的裝卸貨時間k；tij為供應(yīng)商i到j(luò)的行駛時間；T為每條路徑單次循環(huán)時間的最大允許值；S為制造企業(yè)允許的最高庫存量；α為單位距離運輸成本；β為零部件的在主機廠的單位庫存成本；Fijk為第k條路徑上的固定成本；Si為車輛到達供應(yīng)商i處的時刻；Ti為車輛在供應(yīng)商i處的等待時間；ai為供應(yīng)商在i處允許最早接受服務(wù)時間；bi為供應(yīng)商i處允許最遲接受服務(wù)時間；λ為單位距離的平均碳排放量；A為每次取貨允許的最大碳排放量。

2 模型求解的混合算法

2.1遺傳與Max-Min蟻群混合算法

對于VRP問題的求解，目前一些文獻常采用某一種智能算法進行求解，但每種算法都存在一定的問題，如蟻群算法，其前期搜索的局限性、算法收斂性都比較差，導致求解結(jié)果不夠精確，因此考慮兩種算法混合求解。本文將遺傳算法與Max-Min蟻群算法進行融合，汲取兩種算法的優(yōu)點，克服各自的缺陷，優(yōu)勢互補，使得混合算法在時間效率上優(yōu)于蟻群算法，在求精解效率上優(yōu)于遺傳算法?；旌纤惴ǖ幕舅枷胧撬惴ㄇ斑^程采用遺傳算法，充分利用遺傳算法的快速性、隨機性、全局收斂性，其結(jié)果是產(chǎn)生有關(guān)問題的初始信息素分布[3]；算法后過程采用Max-Min蟻群算法，在有一定初始信息素分布的情況下，充分利用蟻群算法并行性、正反饋性、求精解效率高等特點，實現(xiàn)兩種算法的優(yōu)勢互補。

2.1.1 遺傳算法初代種群初始化

為了避免遺傳算法在初期盲目性的搜索，我們先對初代種群進行如下初始化，即把供應(yīng)商的點作為染色體（這里采用符號編碼），隨機選擇一個點，然后判斷該點是否滿足碳排放、載重量和時間窗，若是滿足，則加入到該染色體中，否則選擇一個點，直至所有點都被選擇過。

2.1.2 輪盤賭選擇方法

輪盤賭選擇的基本思想是各個個體被選中的概率與其適應(yīng)度函數(shù)值大小成正比。設(shè)群體大小為N，個體xi的適應(yīng)度為f(xi)，這里的適應(yīng)度函數(shù)取目標函數(shù)，則個體xi的選擇概率為：

2.1.3 個體保優(yōu)策略

通過遺傳算法對個體的交叉與變異等操作，可以不斷更新出優(yōu)良的新生個體。但由于本身的遺傳操作是基于隨機性的，故有時會破壞目前最好的適應(yīng)度值，從而造成整體的種群平均適應(yīng)值下降。為此提出了個體保優(yōu)策略來進行優(yōu)勝劣汰操作，即當前群體中適應(yīng)度最好的個體不參與交叉、變異遺傳操作，而是用它來替換本代群體中經(jīng)過交叉、變異操作后所產(chǎn)生的適應(yīng)度值最低的個體[3]。

2.1.4 次序交叉

為了能夠更好的貼近自然界進化規(guī)律，選擇次序交叉作為該遺傳算法中的交叉操作，從而隨機性生成新個體。次序交叉指的是首先，對隨機的兩個新種群，找到兩個交叉點，將交叉點之間的數(shù)值移動到最后面，得到臨時兩個種群；然后，交換原先新種群交叉之間的數(shù)值；最后，已交叉后的新種群為依據(jù)，將臨時種群依次填補兩個交叉點前后的空值，在此期間要保證數(shù)值不能有重復。

2.1.5 替換變異

作為遺傳算法另外一個重要的遺傳操作變異，其可以產(chǎn)生種群未曾出現(xiàn)過的新生代。雖然變異操作只是產(chǎn)生新個體的輔助方法，但它也是必不可少的一種遺傳操作，因為它決定了遺傳算法的局部搜索能力。交叉與變異的相互配合，共同完成對搜索空間的全局搜索和局部搜索，從而使得遺傳算法能夠以良好的搜索性能完成最優(yōu)化問題的尋優(yōu)過程[4]。

替換變異指的是首先在種群中隨機找到兩個變異點x1，x2，暫時移除兩個變異點之間的數(shù)值。然后，在剩下的染色體字段中隨機到一點rnd，將變異點之間的數(shù)值插入rnd中。最后根據(jù)變異種群是否滿足相應(yīng)的約束條件來判斷種群變異失敗與否。

2.1.6 螞蟻信息素初始化

MMAS是把各路徑信息素初值設(shè)為

通過遺傳算法得到了一定的路徑信息素，把信息素的初值設(shè)置為

其中c為常量，f(xij)是該條路徑上的目標函數(shù)值。

2.1.7 改善信息素更新

為盡可能的避免早熟（局部最優(yōu)）和提高解的質(zhì)量，在算法的運行中期，引入趨于相同路徑的螞蟻數(shù)γ和負反饋因子δ，對信息素的全局更新進行動態(tài)調(diào)節(jié)來改善探索新路徑的能力，從而達到進一步提高求解質(zhì)量的目的[5]。采用的公式如式（2）～（5）：

式（4）中Q是一個常數(shù)，在這里取1；Lk表示在本次循環(huán)中第k只螞蟻所走過路徑的長度。

2.1.8 改善螞蟻的能見度

為了彌補運行后期時，即當所有螞蟻中有h只螞蟻所走路徑完全相同時，可能會遺漏更優(yōu)節(jié)點的選擇，引入適當增大能見度機制，從而改善螞蟻路徑選擇的影響力，進一步提高解的質(zhì)量[5]。公式如式（5）～（6）：

2.1.9 螞蟻轉(zhuǎn)移概率選擇

借鑒Dorigo等的Ant-Q算法思想，采用確定性與隨機選擇策略，根據(jù)式(4)和式(5)結(jié)合節(jié)約算法對蟻群算法轉(zhuǎn)移規(guī)則進行細化[6]，定義如下形式的螞蟻轉(zhuǎn)移概率：

《城市綠化條例》與《風景名勝區(qū)條例》是風景園林行業(yè)主要的行政法規(guī)，它們對我國綠化事業(yè)的發(fā)展，改善、美化生態(tài)與生活環(huán)境，充分保護風景名勝資源，有效進行行業(yè)管理等方面做出了明確的約束和規(guī)定。

式(7)中：τij為邊(i,j)上的信息素；ηij為邊(i,j)上的啟發(fā)信息，值為邊(i,j)長度的倒數(shù)，即ηij=1/dij；μij表示將點i與j在滿足車輛容量約束的基礎(chǔ)上連接在j一條線路上的費用節(jié)約值，其值通過節(jié)約算法求得，先將各點單獨與源點0相連，構(gòu)成1條已含一個點的線路，然后計算μij=dio+doj-dij，μij越大，收益越大，選擇結(jié)點μj的概率也就越大，但μij的值需要作最大值和最小值限制，以免μij過大或過小而影響整個路徑轉(zhuǎn)移概率。在這里做如下的規(guī)定：當μij≤0，取μij=0.01；當μij≥10時，取μij=10，這樣的話就可以使得整個轉(zhuǎn)移概率公式的其他影響因素失去意義；kij=(qi+qj)/Q是考慮車輛容量約束和車輛容量利用率而引入的變量；α、β、γ、λ為權(quán)重參數(shù)；p是取值在(0,1)區(qū)間內(nèi)的隨機數(shù)；p0取0.1。

2.2 算法步驟

混合算法求解VRP問題步驟如下。

步驟1：初始化．初始化螞蟻數(shù)n，供應(yīng)商數(shù)量m，單位距離運輸成本unitCost，信息素揮發(fā)參數(shù)ρ，影響因子α、β、γ、λ，固定成本cost，每條路徑上單次循環(huán)時間的最大值maxTime，單位距離的碳排放量carbon、每次循環(huán)取貨允許的最大碳排放量maxCarbonEmission及信息素軌跡范圍[τmin,τmax]；

步驟2：初始化遺傳算法的種群個數(shù)ind_N、交叉率p_c_t、變異率p_m_t。

步驟3：初始化初代種群的分布，該分布滿足碳排放、載重量、時間窗。

步驟4：進化次數(shù)是否已經(jīng)達到了MAX_GEN，如果已經(jīng)達到，則跳轉(zhuǎn)到步驟9；否則跳轉(zhuǎn)到步驟5。

步驟5：比例選擇，這里利用在[0,1]之間隨機數(shù)來確定被選中的下一代種群初始染色體，以及被選中的次數(shù)。

步驟7：隨機選擇兩個種群，進行次序交叉。判斷交叉后的種群是否滿足載重量、碳排放、時間窗，如果滿足則跳轉(zhuǎn)到步驟8，否則判斷當前次數(shù)是否小于m，如果小于，則進入下一循環(huán)，同時種群回退到上一代的染色體狀態(tài)。否則跳轉(zhuǎn)到步驟6，同時種群回退到上一代的染色體狀態(tài)。

步驟8：對次序交叉后的種群進行替換變異，判斷變異后的種群染色體是否滿足載重量、碳排放、時間窗。如果不滿足，則種群回退到交叉遺傳操作之前的染色體狀態(tài)，否則保存該新生種群的染色體。跳轉(zhuǎn)步驟到6。

步驟9：初始化信息素．根據(jù)給定數(shù)據(jù)，按式(1)計算各邊初始信息素軌跡最；

步驟10：構(gòu)造解，初始化最大迭代次數(shù)MAX_GEN。每只螞蟻的初始出發(fā)位置都為配送中心，根據(jù)(5)(6)(7)式選擇下一個供應(yīng)商地點。如果該點滿足以每一條路徑上車輛載重量總和小于最大的車輛載重量、每一條路徑上碳排放量總和小于允許的最大碳排放量以及每一條路徑上所花的時間也小于允許的時間，則將該點置于該螞蟻的禁忌表中，并從allowed表中刪除該點，直到該螞蟻(車)均不滿足上述的3個條件，則返回至配送中心。重復循環(huán)直到所有供應(yīng)商地點都被訪問過，計算目標函數(shù)值，記錄下當前最好的路徑長度以及其對應(yīng)tabu中的點[6]。

圖1 算法流程圖

步驟11：重復步驟10，直到所有螞蟻都構(gòu)造好相應(yīng)的解

步驟12：比較所有螞蟻的路徑，累計h及r，更新最小目標函數(shù)值的路徑及路徑條數(shù)，根據(jù)式(2)(3) (4)更新各邊信息素軌跡，并根據(jù)Max-Min思想限制信息素軌跡量[6]；

步驟13：迭代次數(shù)依次遞增；

步驟14：若迭代次數(shù)超過MAX_GEN或蟻群全部收斂到相同路徑，則輸出最優(yōu)解，否則轉(zhuǎn)步驟10。

算法流程圖見圖1。

2.3 參數(shù)設(shè)計

計算中，一些參數(shù)的選取會對算法的的運行速度與最優(yōu)解等產(chǎn)生重要影響，以下對交叉率p_c_t、變異率p_m_t與信息素揮發(fā)參數(shù)ρ 3個參數(shù)進行設(shè)計。

在進行初始化時，交叉率與變異率的取值尤為重要。交叉率p_c_t決定了種群的多樣性，而變異率p_m_t則決定了程序跳出局部最優(yōu)解的能力。在運行過程中發(fā)現(xiàn)，交叉率和變異率的取值不能太大，如果交叉率太大會使種群的多樣性變小，而變異率太大則會頻繁破壞種群。因此，經(jīng)過分析，選取3組參數(shù)進行計算，運行結(jié)果見表1，由表1可見，選取第2組參數(shù)可獲得更優(yōu)結(jié)果。

信息素揮發(fā)參數(shù)ρ決定螞蟻是否能夠找尋到原有的路線。ρ取值過大會造成信息素揮發(fā)過快，導致不能利用之前所得到結(jié)果值，而取值過低則會導致陷入局部最優(yōu)，影響整體最優(yōu)的求解。其它參數(shù)不變，分別選取信息素揮發(fā)參數(shù)ρ為0.1、0.5和1.0 3組計算，運行結(jié)果見表2，由表2可知，選取第2組的ρ=0.5可獲得更優(yōu)結(jié)果。

表1 選取的3組交叉率與變異率數(shù)值及運行結(jié)果

表2 選取不同ρ值及運行結(jié)果

3 實例驗證

某物流企業(yè)目前為上海大眾、上海通用、上汽通用五菱、一汽豐田、廣汽豐田、比亞迪等多家國內(nèi)主機廠提供物流服務(wù)，其零部件入廠物流業(yè)務(wù)采用循環(huán)取貨方式，目前運輸成本較高，車輛裝載率低于85%，裝載率低。該物流企業(yè)目前在上海有一家主機廠，200家循環(huán)取貨的供應(yīng)商，主要分布在上海和江蘇，由于供應(yīng)商數(shù)量眾多，配送量差異較大，因此先對供應(yīng)商進行層次聚類分析和概率選擇。在概率選擇中，由于所有供應(yīng)商提供的供應(yīng)量數(shù)據(jù)離散性較強，而且實際上每家供應(yīng)商提供的量也是差異化的，選出的所有供應(yīng)商滿足離散型概率的程度高于連續(xù)型概率。借鑒乘客坐公交車概率問題，提出了每個供應(yīng)商取貨量的概率，公式見式(8)。

根據(jù)上述計算，符合降低取貨頻次的原則，選擇出41家供應(yīng)商作為研究對象。配送中心的坐標是（31.2961，121.1702），15臺運輸車輛對41家供應(yīng)商進行循環(huán)取貨，載重量5噸，車輛容積12×2.3× 2.3 m3，取貨量用貨物體積表示。計算過程中，根據(jù)美國加州環(huán)保機構(gòu)的數(shù)據(jù)，我國運輸車輛C02平均排放量約為190～200 g/km[7]，而運輸貨車載貨量較大碳排放量更高，因此，結(jié)合相關(guān)標準，根據(jù)載貨量的平均值設(shè)定運輸車輛單位距離的碳排放量為203 g/km，并確定每次取貨允許的最大排放量為82000 g。此外，每條路徑單次循環(huán)時間最大允許值為6 h，種群交叉率取0.8%，種群變異率取0.015%，信息素揮發(fā)參數(shù)取0.5，殘留信息素的重要程度取2.0，啟發(fā)信息的重要程度取2.5，費用節(jié)約值的重要程度取1.0，車輛容量約束和車輛容量利用率的權(quán)重參數(shù)值取1.0。采用MATLAB軟件進行運算，運行50次后，得到的最優(yōu)結(jié)果見表3。

表3 運行50次的計算結(jié)果

由上述結(jié)算結(jié)果可以知道，41家供應(yīng)商通過11條線路進行取貨，80%的單點取貨頻次為2次，20%的單點配送頻次為3次，基本能達到降低頻次的目的；而在裝載容積上，多點取貨車輛裝載率最低88%，83.3%線路車輛裝載率超過90%；單點取貨車輛裝載率相對較低，最低77%，80%線路車輛裝載率超過80%，最高可達98%，接近滿載，基本解決企業(yè)原來存在的車輛裝載容積率低的問題。此外，每條線路的碳排放量都少于每次取貨允許最大排放量。

將采用混合算法與采用遺傳算法、Max-Min蟻群算法進行比較，結(jié)果見表4，由表4可見，采用混合算法運行的結(jié)果更加優(yōu)化，且運行速度快。

表4 幾種算法運行結(jié)果比較

4 結(jié)束語

將混合算法用于求解汽車零部件供應(yīng)物流中的VRP問題，所得結(jié)果比單獨采用遺傳算法或Max-Min蟻群算法更加合理，在提高車輛裝載率方面有顯著作用，并能有效減少車輛取貨頻次，使碳排放量控制在標準范圍之內(nèi)，降低取貨成本。因此，將遺傳算法與Max-Min蟻群算法混合求解供應(yīng)商數(shù)量多、帶時間窗限制與碳排放限制的汽車零部件供應(yīng)物流配送路徑問題可得到較優(yōu)結(jié)果。

［1］左曉露，劉志學．汽車零部件循環(huán)取貨物流模式的分析的分析與優(yōu)化［J］．汽車工程，2011，33（1）：79-84．

［2］郎茂祥．基于遺傳算法的物流配送路徑優(yōu)化問題研究［J］．中國公路學報，2002，15（3）：76-79．

［3］蘇濤，韓慶田．VRP問題蟻群算法研究［J］．計算機與現(xiàn)代化，2012（11）：1006-2475．

［4］丁建立，陳增強．遺傳算法與螞蟻算法的融合［J］．計算機研究與發(fā)展，2003，40（9）：1352-1353．

［5］陳國良，王煦法．遺傳算法原理及應(yīng)用［M］．北京：人民郵電出版社，1996．

［6］王更生，俞云新．一種改進蟻群算法求解VRP問題［C］//南昌：信息技術(shù)與應(yīng)用學術(shù)會議論文集，2009：255-256．

［7］車昱．基于綠色供應(yīng)鏈的循環(huán)取貨模式研究［D］．北京：北京交通大學，2012．

（責任編輯：朱聯(lián)九）

Optimization of Auto Parts Logistics Distribution Path Based on Hybrid Algorithm

HOU Xiu-ying,LI Zheng-hong,LIN Sen,LUO Yi-hui,ZOU Bin

(College of Transportation and Civil Engineering,Fujian Agriculture and Forestry University,Fuzhou 350002,China))

According to the supply logistics of automobile parts,milk-run distribution path optimization model is established.The Max-Min genetic algorithm and ant colony algorithm are fused.Genetic algorithm is adopted to give information pheromone distribution;the ant algorithm is used to give the precision of the solution,and is verified by an example.The results show that the hybrid algorithm can effectively reduce the distribute frequency and improve vehicle loading rate for solving the distribution path problem of supplier and limiting the time window and carbon emissions.

auto parts；milkrun；genetic algorithm；Max-Min ant colony algorithm

F224

A

1673-4343（2014）04-0038-07

10．14098／j．cn35－1288／z．2014．04．008

2014-06-08

福建農(nóng)林大學科技創(chuàng)新（培育）團隊資助計劃（pytd12006）。

侯秀英，女，福建永泰人，副教授。研究方向：物流技術(shù)與管理。通訊作者：李正紅，女，福建浦城人，教授。研究方向：物流技術(shù)與管理。