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

陳疇鏞，王 覲

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

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

陳疇鏞，王 覲

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

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

汽車零部件；物流配送；路徑優(yōu)化；循環(huán)取貨；蟻群算法

一、引言

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

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

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

二、汽車零部件物流配送路徑優(yōu)化模型

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

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

圖1 循環(huán)取貨模式圖

通過以上分析，假設(shè)有n個供應(yīng)商點，有m條配送路徑，現(xiàn)建立模型如下：

其中，N為節(jié)點集合，代表所有零部件商的集合，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允許的最早開始服務(wù)時間；bi為零部件商i允許的最晚開始服務(wù)時間；si為配送車輛到達零部件商i的時刻；tij為配送車輛由零部件商i到零部件商j的行駛時間；ci（ti）為配送車輛在第i時刻達到零部件商j的懲罰成本；Qk為路徑k上車的容量限制。

此外，

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

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

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

三、模型求解的算法

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

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

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

（二）混合算法的步驟

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

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

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

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

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

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

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

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

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

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

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

圖2

（三）參數(shù)設(shè)計

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

四、實驗與仿真分析

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

表1 研究對象數(shù)據(jù)圖

表2 路徑優(yōu)化結(jié)果

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

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

表3 算法對比

五、結(jié)束語

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

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

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

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

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

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

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

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

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

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

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

F252；U492.2+2

F59

1004-2768（2017）11-0124-04

2017-09-05

國家自然基金項目“面向制造企業(yè)的協(xié)同物流系統(tǒng)優(yōu)化機制及多agent仿真研究”（71171070，U1509220）

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

A 校對：L）