基于改進的蟻群算法的汽車零部件物流配送路徑優化

陳疇鏞，王 覲

（杭州電子科技大學 管理學院，浙江 杭州 310018）

基于改進的蟻群算法的汽車零部件物流配送路徑優化

陳疇鏞，王 覲

（杭州電子科技大學 管理學院，浙江 杭州 310018）

文章針對汽車零部件產業中入廠物流模式進行研究，在分析庫存和配送之間的博弈合作關系以及考慮時間窗對實際物流配送過程的重要影響下，建立帶軟時間窗約束和庫存約束的汽車零部件循環取貨入廠物流模型，并將禁忌搜索算法中禁忌最優路徑的思想融入了傳統蟻群算法中，通過改進后的蟻群算法求解模型，最后結合具體實例利用 M atlab軟件進行仿真試驗，得到優化后的汽車零部件的循環配送線路方案，驗證了模型和算法的有效性。

汽車零部件；物流配送；路徑優化；循環取貨；蟻群算法

一、引言

伴隨著中國經濟的快速發展，汽車行業競爭日趨激烈，汽車生產廠商追求效益、降低成本的壓力必然向汽車產業鏈的物流環節釋放。汽車零部件配送數量多，供應商數量多，導致汽車零部件供應物流的組織與運行成為汽車產業物流中難度最大和最復雜的環節之一，對相應供應鏈的敏捷度、效率和企業的物流成本等方面的影響顯著。因此，汽車廠商對零部件物流體系的研究尤為重要，通過合理地組織運輸與配送來降低現代物流中的儲存成本和運輸成本，進而提升整個汽車供應鏈整體的競爭力[1]。

本文研究的是循環取貨模式下汽車零部件物流配送中的路徑優化問題。車輛路徑優化問題的研究突飛猛進，國內外不同學者進行了大量的研究，經典的車輛路徑優化問題最早是由學者Dantzig和Ramser在1959年提出的。Keng Hoo Chuah和Jon C.Yingling率先在2001年針對車輛路徑優化問題，提出建立循環取貨運行的數學理論模型，探討循環取貨模式的運行機制并在實際運行中各個變量對庫存成本和運輸成本的影響，循環取貨模型被隨之廣泛應用于路徑優化問題；張蕾于2006年通過對汽車企業案例的對比分析，指出了汽車制造企業JIT生產中庫存和運輸配送兩個效益悖反環節所產生的矛盾可以采用循環取貨模式有效地解決，并指出了汽車制造企業采用循環取貨模式所需要的一些前提條件以及確定了循環取貨的實用范圍；鄧愛民、賓松、Balakrishnan、Calvete、George等人考慮到因車輛遲到產生的懲罰費用和因車輛早到產生的機會損失費對車輛路徑問題的影響，將這些影響因素加入車輛調度所建立的目標函數和約束條件中，建立了相應的基于軟時間窗的車輛路徑優化模型，同時設計了相應的算法進行求解[2]。

在汽車的循環取貨過程中，庫存和配送環節綜合起來構成了汽車生產企業零部件入廠物流系統，所以在研究汽車零部件循環取貨模式下物流配送的路徑優化問題時，一定要考慮庫存和配送的相互影響并且協調好兩者的關系。在汽車入廠物流中，汽車零部件庫存的高低對汽車企業各個環節產生巨大的影響：高庫存量會導致企業在庫存造成過多的資金占用和會造成汽車生產成本的增加，隨之配送成本就會降低，容易形成規模效益；低庫存對供應鏈的要求較高，風險也較大，可能導致生產的中斷，造成更大損失，但相應的，庫存成本大幅度降低，企業流動資本相對比較充足[3]。在同一企業中，庫存和配送之間是合作博弈的關系，通過合理的資源優化配置，在保證正常生產的前提下，使配送和庫存達到均衡，保證總體成本最低化，從而達到供應鏈整體的利益最大化[4]。除此之外，在實際的汽車零部件物流配送過程中，若物流配送車輛未能遵守約定的時間窗約束，可能會造成推遲卸貨等特殊情況，甚至會有拒收的風險，物流供應的整體時效性及服務質量將大打折扣，長此以往，會影響汽車制造企業正常的生產流水，時間效應成本不僅影響物流運輸路徑成本，而且還會影響服務質量，所以時間懲罰成本在模型中的加入十分必要[5]。本文針對汽車零部件行業的實際情況，對其中的車輛路徑問題進行優化設計，建立汽車零部件的循環取貨模型，在基礎之上增加庫存約束和時間懲罰成本的概念，并將禁忌搜索算法中對搜索能力改進、最優路徑的選擇優化等思想融入了傳統蟻群算法中，通過改進后的蟻群算法求解模型[6]。最后結合具體實例利用仿真軟件進行仿真試驗，得到優化后的汽車零部件的循環配送線路方案，驗證了模型和算法的有效性[7]。

二、汽車零部件物流配送路徑優化模型

本文研究的汽車零部件循環取貨入廠物流模型（見圖1），由多個供應商、汽車生產企業、配送中心等組成，采取循環取貨模式，同時在時間窗約束、庫存約束和時間懲罰成本等約束條件下，合理安排運輸車輛的行車路線，有效地解決汽車零部件物流配送問題。

現實中汽車零部件物流配送路徑優化問題是十分復雜的，為了方便建模和求解，現對現實問題進行一些抽象與簡化后，具體概括如下：（1）所有零部件供應商的位置是固定的，配送過程中每次到每個供應商的取貨量是一定的；（2）在配送過程中，每個零部件商有且僅能用一輛車進行配送服務，并且每輛車可以對多個零部件商進行配送服務；（3）配送中心的庫存量有一定的限制；（4）車輛到達供應商和配送中心的配送過程是有一定的時間窗約束[8]。

圖1 循環取貨模式圖

通過以上分析，假設有n個供應商點，有m條配送路徑，現建立模型如下：

其中，N為節點集合，代表所有零部件商的集合，N={1，2，…，n}；O 為第三方物流配送中心，N=0；K 為配送車輛集合，K={1，2，…，k}；Q 為配送車輛的載重能力；pi2表示零部件i的單位平均庫存成本，pi3表示零部件i的單位缺貨損失成本；zijk為配送車輛k離開零部件商i到零部件商j的載重量；cit為零部件商i至零部件商j的行駛距離；ai為零部件商i允許的最早開始服務時間；bi為零部件商i允許的最晚開始服務時間；si為配送車輛到達零部件商i的時刻；tij為配送車輛由零部件商i到零部件商j的行駛時間；ci（ti）為配送車輛在第i時刻達到零部件商j的懲罰成本；Qk為路徑k上車的容量限制。

此外，

其中 i，j∈N，i≠j。

在上述的數學模型中，約束條件1表示目標函數，使得汽車零部件配送過程的總成本最小。

約束條件2和3表示在配送過程中，每個零部件商有且僅能用一輛車進行配送服務，并且每輛車可以對多個零部件商進行配送服務；約束條件4表示配送車輛完成零部件商i配送任務，必定從部件商i駛出；約束條件5表示車輛配送路徑中沒有重復路徑；約束條件6表示零部件商各個配送點的時間窗要求；約束條件7表示配送車輛違反軟時間窗要求得到的懲罰函數；約束條件8表示每條路徑的上車容量約束；約束條件9表示每條路徑的取貨量不得超過制造商的最高庫存量。

三、模型求解的算法

（一）禁忌搜索與蟻群混合算法

對比禁忌搜索算法和蟻群算法，可以發現它們各有優缺點。蟻群算法是一種較為通用的并行算法，容易與其他的算法進行結合，通過迭代搜索可以得到較好的初始解，但是經常會因為搜索局部最優路徑時信息素大量積累而陷入局部最優，導致搜索結果不符合要求[9]。而禁忌搜索算法憑借靈活的記憶功能和藐視準則，是一種局部搜索能力很強的全局迭代尋優算法，能夠接受次優解，不會陷于局部最優，但會過度依賴初始解，兩種算法思路各有優勢，經過相互結合和改善，能夠有效地提高算法的效率和性能。

鑒于此，本文提出蟻群算法與禁忌搜索算法的混合算法，結合它們算法在設計原則和算法特點的優勢，以蟻群算法作為混合算法的整體框架，控制算法的整體結構和進程，運用搜索禁忌表的禁忌策略、局部標識表的更新策略以及路徑解禁策略等改進因子加入到蟻群算法的框架之中。具體來說，通過傳統蟻群算法找到最優或者最差的全局路徑，在經過局部優化等操作后，根據禁忌搜索最優路徑的思想，把禁忌存儲到搜索禁忌表中。接下來再根據表中禁忌路徑動態，將其映射成一個局部標識表，以此來反映最優最差路徑的選擇情況，以達到控制當前螞蟻選擇路徑的效果。并且通過禁忌解禁策略來約束禁錮最差路徑，這樣劣質路段就會減少訪問次數，甚至不再訪問。

（二）混合算法的步驟

混合算法求解本文模型的步驟如下。

步驟1：初始化混合改進算法中的各個參數，如，算法最大的循環次數，標記為Nmax，螞蟻數量，設置為M，這個相當于配送點數量。

步驟2：將實驗數據導入算法模型中，并根據坐標計算各個配送點之間的距離，并且籍此構建啟發式信息矩陣。

步驟3：設置循環變量Nc++，根據最大-最小螞蟻系統MMAS算法思想的指引，首先對信息素矩陣按公式τij（t+1）=ρτij（t）進行信息素揮發。

步驟4：對m只螞蟻執行迭代運算，選擇下一配送點,構建新路徑，并按更新公式進行局部信息素的更新。

步驟5：對是否完成對所有配送點的訪問進行判斷，如果沒有返回步驟4，否則繼續執行步驟5。

步驟6：所有螞蟻完成迭代運算結束后，找出本次運算的最優路徑Route_best和最差路徑Route_worst，如果本次最優路徑長度 Lbest（Nc）比當前最優路徑更優，則當前最優路徑被Lbest（Nc）替換。

步驟7：對最優路徑進行N次2-opt局部優化操作，即如果進行局部優化變換后 Lbest（Nc）＜L2-opt，則 Lbest（Nc）=L2-opt。

步驟8：按照算法思想，通過如下公式對最優路徑進行全局信息素更新，把最優路徑和最差路徑分別存儲到搜索禁忌表中，以此來更新禁忌搜素表，同時相應地按照改進的算法思想更新禁忌搜索標識矩陣。

步驟9：對算法中的Nmax進行判斷，是否滿足結束，不滿足返回步驟3，否則結束并輸出結果[10]。

根據上面的算法流程，改進后的混合算法如圖2所示。

圖2

（三）參數設計

通過比較改進算法在CVRP問題庫中選擇不同復雜程度的問題檢驗的算法求解效果，對算法中的各個參數進行初始化設置。根據求解問題的具體規模設最大算法循環的次數，設置cityneighbors=citynumbers*0.2，α=2，β＝3，ρ=0.3，自適應參數 q0=0.2，信息素總量Q=110。

四、實驗與仿真分析

某著名汽車制造企業有多家汽車零部件的供應商，主要分布在長江三角洲周邊地區，企業之前零部件入場物流業務發展速度較為緩慢，運輸成本較為高昂，車輛裝載率普遍較低，庫存壓力承受方面存在一定的風險，并且有未按時交貨的情況，推遲卸貨甚至拒收的現象也時有存在。現針對該企業現階段的實際情況，委托某外包物流方，研究現有的汽車零部件的供需系統，建立適合當前企業發展的帶軟時間窗和庫存約束的汽車零部件循環取貨入廠物流模型。從所有供應商中選出了76家供應商作為研究對象，數據如表1所示。配送中心的坐標是（40，40），針對這76家供應商進行循環取貨的研究，其中運輸車輛的載重量5噸，車輛容積12×2.3×2.3 m3，取貨量用貨物體積表示。采用Matlab軟件進行運算，運行50次后，最優路徑結果如表2所示。

表1 研究對象數據圖

表2 路徑優化結果

由上述運算結果可以知道，在所有優化的配送路徑中，汽車取貨頻次較低，這樣可以保證車輛不會濫用，提高利用率，就能大幅減少車輛費用支出；而在裝載容積上，多點取貨車輛裝載率最低88%，線路車輛裝載率超過80%，最高可達98%，企業原來存在的車輛容積率低閑置浪費的問題得到了有效解決，大大減少了資源浪費。此外，每條線路起止時間都在時間窗限制范圍內，時間懲罰成本僅647元，且最大庫存僅為10.5。

現將混合算法與禁忌搜索法、蟻群算法進行對比分析，結果如表3所示，可得采取混合算法后，不僅運行的結果更加優化，而且運行時間較短，效率也得到了提高。

表3 算法對比

五、結束語

通過本文的論述，可以看出，帶軟時間窗和庫存約束的汽車零部件循環取貨入廠物流模型能夠有效地提高車輛的運輸效率，有效減少車輛取貨頻次，在規定的時間內能提高車輛的使用效率，供貨實現了多頻次、小批量和準時化，極大地降低了運輸成本、庫存成本以及取貨成本，將混合算法用于求解汽車零部件供應物流中的路徑優化問題，所得結果比單獨采用禁忌搜索算法或蟻群算法更加合理。因此，建立帶時間窗限制與庫存限制的汽車零部件循環取貨入廠物流對于零部件數量大、供應商數量多、JIT準時化生產嚴格要求的汽車零部件物流配送路徑問題的解決有著很好的效果。

[1]侯秀英，李正紅，林森，等.基于混合算法的汽車零部件物流配送路徑優化[J].三明學院學報，2014，31（4）：38-44.

[2]左曉露，劉志學，鄭長征.汽車零部件循環取貨物流模式的分析與優化[J].汽車工程，2011，33（1）：79-84.

[3]陸明.基于精益思想的汽車制造企業零部件采購物流的研究[D].天津大學，2009.

[4]于淼.淺析汽車零部件采購物流模式[J].物流工程與管理，2014，36（4）：21-22.

[5]郎茂祥.基于遺傳算法的物流配送路徑優化問題研究[J].中國公路學報，2002，15（3）：76-79.

[6]王更生，俞云新.一種改進蟻群算法求解VRP問題[C]//南昌：信息技術與應用學術會議議論文集，2009：255-256.

[7]何民愛，李艷峰，2005.我國汽車零配件產業物流管理的新模式[J].物流技術（11）：17-19.

[8]謝和業，王恒鵬，蔡文學.廣州本田汽車零部件采購物流改進設計[J].物流技術，2008，27（11）：80-83.

[9]劉志碩，申金升，柴躍廷.一種求解車輛路徑問題的混合多蟻群算法[J].系統仿真學報 2007，19（15）：3513-3520.

[10]劉希洋.應用改進型蟻群算法求解車輛路徑優化問題的研究[D].浙江師范大學，2010.

F252；U492.2+2

F59

1004-2768（2017）11-0124-04

2017-09-05

國家自然基金項目“面向制造企業的協同物流系統優化機制及多agent仿真研究”（71171070，U1509220）

陳疇鏞（1955-），男，浙江紹興人，杭州電子科技大學管理學院教授，研究方向：供應鏈與物流管理、信息管理與商務智能；王覲（1992-），男，陜西漢中人，杭州電子科技大學管理學院碩士研究生，研究方向：供應鏈與物流管理。

A 校對：L）