基于蟻群-免疫算法的組團(tuán)彈性物流配送優(yōu)化

牛鍇文，初良勇，許小衛(wèi)

（1.集美大學(xué)航海學(xué)院，福建 廈門(mén)361021；2.大連海事大學(xué)交通運(yùn)輸工程學(xué)院，遼寧 大連116026）

0 引言

煙草物流是煙草行業(yè)的核心業(yè)務(wù)。據(jù)估計(jì)，煙草行業(yè)的物流成本占行業(yè)總成本的22%，其中運(yùn)輸成本約占物流成本的50%。為有效降低物流成本，特別是運(yùn)輸成本，研究學(xué)者們主要從兩方面入手：配送中心選址優(yōu)化和物流線路優(yōu)化。在物流配送線路優(yōu)化方面，最具代表性的方法就是由Bullnheimer 等［1］提出的蟻群算法，陸海良等［2］提出的遺傳算法，以及楊春周等［3］提出的粒子群優(yōu)化（particle swarm optimization，PSO）算法［3］。相比于最短路法，蟻群算法為近似算法，用以解決至今沒(méi)有找到精確有效的算法的問(wèn)題，但存在前期信息匱乏，易陷入局部搜索和收斂速度慢等困境。針對(duì)此類(lèi)缺陷，王坤［4］提出了改進(jìn)的蟻群算法，在參數(shù)選擇、信息素更新方面都有了較好的發(fā)展；張超［5］提出了一種自適應(yīng)的粒子群算法，提高了在求解單峰問(wèn)題時(shí)算法的性能；Huang［6］建立了HGVRP 模型并設(shè)計(jì)了一種基于負(fù)荷的車(chē)輛模型分配方法；Tan 等［7］結(jié)合遺傳算法與搜索算法的優(yōu)點(diǎn)，通過(guò)構(gòu)建知識(shí)庫(kù)，實(shí)現(xiàn)人工智能輔助求解車(chē)輛路線規(guī)劃問(wèn)題。為了加強(qiáng)對(duì)配送時(shí)間的把控，孫國(guó)華［8］提出以帶時(shí)間窗的開(kāi)放式滿(mǎn)載車(chē)輛路徑為出發(fā)點(diǎn)，通過(guò)遺傳算法對(duì)各區(qū)域劃分，從而優(yōu)化了算法，提高了運(yùn)輸效率，降低了運(yùn)輸成本；李陽(yáng)等［9］針對(duì)客戶(hù)點(diǎn)不斷更新的動(dòng)態(tài)需求車(chē)輛路徑問(wèn)題，設(shè)計(jì)多階段求解的混合變鄰域人工蜂群算法，確保路徑實(shí)時(shí)更新和車(chē)輛信息匹配；葉小龍等［10］提出了層次化網(wǎng)絡(luò)優(yōu)化方法與體系，實(shí)現(xiàn)了二級(jí)物流配送的路徑優(yōu)化；李常敏等［11］結(jié)合顧客時(shí)間滿(mǎn)意度函數(shù)，建立了基于顧客時(shí)間滿(mǎn)意度的車(chē)輛配送模型，并利用模擬退火算法完成求解；文展等［12］設(shè)計(jì)了改進(jìn)的粒子群算法用于求解帶時(shí)間窗的車(chē)輛運(yùn)輸問(wèn)題；Trachanatzt 等［13］引入基于坐標(biāo)的螢火蟲(chóng)算法，通過(guò)不斷的編碼與解碼，減少配送距離，完成對(duì)配送線路的優(yōu)化；林文如等［14］用改進(jìn)的神經(jīng)網(wǎng)絡(luò)解決了非滿(mǎn)載情況下物流配送成本優(yōu)化問(wèn)題等。綜上所述，國(guó)內(nèi)外學(xué)者的研究多集中于對(duì)配送線路的優(yōu)化，而在配送模式創(chuàng)新方面的研究則較少。

傳統(tǒng)配送模式多采用配送中心到零售商的直達(dá)配送。在零售商提交訂單后，配送中心根據(jù)訂單詳情，指派車(chē)輛完成相應(yīng)的配送。考慮到不同地區(qū)不同零售商對(duì)煙草需求的急迫程度不同，若僅參考訂單量，而不根據(jù)實(shí)際位置分布與需求特性進(jìn)行規(guī)劃，可能會(huì)造成補(bǔ)貨速度慢、發(fā)車(chē)頻率高、配送距離較遠(yuǎn)及車(chē)輛裝載率較低等情況。本文從配送模式創(chuàng)新角度出發(fā)，針對(duì)煙草物流需求量大、配送時(shí)效性要求較高等特點(diǎn)，提出一種新型配送模式——組團(tuán)式彈性配送，通過(guò)整合位置信息與需求量，將待配送點(diǎn)合理分組，完成統(tǒng)一配送，從而達(dá)到降低配送成本的目的。目前國(guó)內(nèi)外先進(jìn)的企業(yè)在配送過(guò)程中已經(jīng)有在使用，但此類(lèi)學(xué)術(shù)研究還相對(duì)較少，因此本文將從組團(tuán)式物流配送模式入手，研究其線路優(yōu)化模型及算法。

1 組團(tuán)式彈性配送的提出

本文提出的組團(tuán)彈性配送新模式如圖1 所示。其中“組團(tuán)”是通過(guò)分組標(biāo)號(hào)的方式對(duì)同一地區(qū)相鄰區(qū)域的零售商進(jìn)行整合，將集中模式之下的單獨(dú)配送轉(zhuǎn)換為組內(nèi)多零售商的統(tǒng)一配送。而“彈性”的概念則是指從庫(kù)存的角度考察，當(dāng)組內(nèi)任一零售商庫(kù)存不足時(shí)，配送中心將會(huì)獲取組內(nèi)其余零售商的需求量并同時(shí)給予補(bǔ)貨，有效增加各物流節(jié)點(diǎn)的庫(kù)存和應(yīng)急能力。與共同配送不同，組團(tuán)式配送注重的是將同一類(lèi)貨物依次配送至不同零售商。

圖1 組團(tuán)式彈性配送模式Fig.1 Group flexible distribution model

2 優(yōu)化模型的構(gòu)建

針對(duì)當(dāng)前配送模式單一的問(wèn)題，本文以配送車(chē)輛數(shù)盡可能少、配送車(chē)輛總里程盡可能短，滿(mǎn)載率盡可能高等為目標(biāo)，在彈性配送模式下，基于蟻群-免疫算法，對(duì)組內(nèi)的物流配送路徑進(jìn)行優(yōu)化。

2.1 模型構(gòu)建因素分析

通過(guò)調(diào)研分析煙草物流配送的各個(gè)環(huán)節(jié)，對(duì)收集到的已知條件進(jìn)行匯總與模型構(gòu)建，完成配送路徑動(dòng)態(tài)優(yōu)化模型的約束分析。具體如下：

1）零售客戶(hù)集合信息約束 零售客戶(hù)在模型中為各個(gè)零售商的信息，根據(jù)地理位置、地理性質(zhì)和路網(wǎng)性質(zhì)形成零售客戶(hù)“點(diǎn)集”信息。另外還包括每個(gè)零售商對(duì)卷煙的需求量。

2）線路信息約束 制定配送線路需要結(jié)合需求點(diǎn)位置與需求量，保證配送路徑通暢穩(wěn)定，原則上選取地理位置相對(duì)集中的零售客戶(hù)由同一輛送貨車(chē)進(jìn)行送貨，以提高配送的時(shí)效性及效率。

3）車(chē)輛信息約束 車(chē)輛約束為本模型的核心約束，主要包括在物流中心的配送車(chē)輛的數(shù)量、每輛車(chē)最大裝載能力、每輛車(chē)日配送貨物最長(zhǎng)時(shí)間、車(chē)公里油耗、車(chē)輛的固定成本以及時(shí)間成本。

4）配送中心約束 配送中心信息包括配送中心的地理位置、配送中心到各零售客戶(hù)點(diǎn)的距離、零售客戶(hù)之間的距離，并且各零售商之間與配送中心配備較完善的信息系統(tǒng)，用以確保信息的時(shí)效性。

5）特殊信息約束 為了保證車(chē)輛裝載率，異形煙草在配送過(guò)程中采用特殊的車(chē)輛進(jìn)行配送，即系統(tǒng)通過(guò)調(diào)查歷史需求得出各個(gè)零售店對(duì)于異形煙草的需求量，擬定合適的線路進(jìn)行組團(tuán)式配送。

2.2 模型建立及參數(shù)

要求配送總里程Z（即各條配送路徑的長(zhǎng)度之和）最短的目標(biāo)函數(shù)為

其中：K表示配送中心擁有的車(chē)輛數(shù)；為車(chē)輛k從組內(nèi)第i-1 個(gè)客戶(hù)配送至第i個(gè)客戶(hù)間的距離；為新增車(chē)輛從配送中心到客戶(hù)點(diǎn)間的距離；nk表示第k輛車(chē)服務(wù)的客戶(hù)數(shù)量。

模式約束條件：

1）客戶(hù)的貨物需求量為其最大儲(chǔ)存量qi與庫(kù)存量pi之差。需保證每條路徑上各客戶(hù)對(duì)貨物需求量之和不超過(guò)配送車(chē)輛的最大載重量Qk，即≤Qk。

2）在配送過(guò)程中，i＋1點(diǎn)的貨物需求量不超過(guò)車(chē)輛在i點(diǎn)的裝載量，即qj＋1-pj＋1≤Qk-。

3）每條配送路徑的長(zhǎng)度不超過(guò)配送車(chē)輛的最大行駛距離D，即×sign（nk）］≤D。

4）每條路徑上的客戶(hù)數(shù)nk不超過(guò)總客戶(hù)數(shù)L，即0≤nk≤L。

6）每條路徑Rm均由客戶(hù)組成，即Rm＝｛∈｛1，2，…，L｝，i＝1，2，…，nk｝。

7）分組確定后，當(dāng)組內(nèi)任一客戶(hù)庫(kù)存不足倉(cāng)儲(chǔ)量的30%時(shí)，觸發(fā)全組配送，即?pi＜0.3×qi。通過(guò)調(diào)查及存儲(chǔ)論的知識(shí)可知，平均補(bǔ)貨周期是3 d，即平均每天消耗庫(kù)存的1／3。由于訂貨費(fèi)與需求速度已知，為保證總成本最小，只需要保證儲(chǔ)存費(fèi)用最小即可，故此處選擇30%較為合適。

9）所有由配送中心出發(fā)的車(chē)輛完成配送后均返回到配送中心。

10）當(dāng)?shù)趉輛車(chē)服務(wù)的客戶(hù)數(shù)≥1 時(shí)，說(shuō)明該臺(tái)車(chē)參加了配送，則取sign（nk）＝1；當(dāng)?shù)趉輛車(chē)服務(wù)的客戶(hù)數(shù)＜1 時(shí)，表示未使用該臺(tái)車(chē)輛，則取sign（nk）＝0。

3 求解算法設(shè)計(jì)

3.1 蟻群-免疫算法原理及流程

由于煙草訂單量大、目標(biāo)多樣化，零售商分布散亂、需求不一，以及優(yōu)化復(fù)雜性較高，本文采用了蟻群算法與免疫算法相結(jié)合的混合算法。

蟻群-免疫算法的基本思路是將免疫操作引入到蟻群系統(tǒng)中，利用免疫算法搜索速度快，全局收斂性強(qiáng)等特點(diǎn)，改善蟻群算法前期因信息素匱乏造成的搜索速度慢、易陷入局部最優(yōu)等情況。在求解過(guò)程中，每只螞蟻都代表優(yōu)化問(wèn)題中的一個(gè)解。通過(guò)整合與目標(biāo)問(wèn)題相關(guān)的先驗(yàn)知識(shí)并將其當(dāng)做疫苗作用在部分螞蟻上，可得到求解能力較強(qiáng)的“精英螞蟻”。由于精英螞蟻的存在，不滿(mǎn)足先驗(yàn)知識(shí)的線路將不再被選擇，隨著迭代次數(shù)的增加，可選擇的點(diǎn)逐漸減少，收斂速度將得到提升。

蟻群-免疫算法的基本流程如圖2 所示，其中最大迭代次數(shù)僅作用于蟻群算法。在分組之后，受車(chē)輛最大裝載量的限制，各個(gè)組內(nèi)客戶(hù)不會(huì)很多，所以最大迭代次數(shù)不需要設(shè)置很大。隨后進(jìn)入免疫操作，每完成一次搜索，算法會(huì)計(jì)算抗體濃度與抗體間的親和力并更新當(dāng)前可行解與禁忌表，在不斷免疫選擇與變異的過(guò)程中，低質(zhì)量的解逐漸被淘汰，高質(zhì)量的解得以保留，直到子代中抗體間的親和度小于等于父代時(shí)停止循環(huán)，此時(shí)輸出的路徑即為全局最優(yōu)路徑。

圖2 彈性模式下蟻群-免疫算法流程圖Fig.2 The flow chart of ant colony-immune algorithm in elastic mode

3.2 算法的實(shí)現(xiàn)

由于蟻群系統(tǒng)中精英螞蟻對(duì)搜索方向起決定性作用，而參與全局最優(yōu)競(jìng)爭(zhēng)的只有每一代中的最優(yōu)解，故完成單次循環(huán)之后，只需對(duì)最優(yōu)的螞蟻實(shí)施信息素更新，公式為：

其中：p（Aab（k））代表了高質(zhì)量抗體間的相似程度，取值范圍在0～1 之間，且值越大相似程度越高解也越接近；f（Aab（k））為螞蟻a、b的適應(yīng)度；d（Aab（k））為螞蟻a、b散發(fā)的信息素濃度；α為信息啟發(fā)因子。

由于環(huán)境信息素具有最大、最小值范圍，信息素每次進(jìn)行更新后需檢查，若超過(guò)范圍則需要調(diào)整。信息素最大、最小值計(jì)算公式為：

抗體親和力計(jì)算方式與信息素更新公式為：

其中：ηij為邊（i，j）上的能見(jiàn)度；allowedk為下一步允許到達(dá)的節(jié)點(diǎn)集合；τ為信息素；τij（t）表示第t周期內(nèi)，點(diǎn)i與點(diǎn)j間的信息素總量，其象征最優(yōu)解方案的發(fā)展方向；τis（t）表示第t周期內(nèi)的全局信息素總量；ηis（t）表示第t周期內(nèi)的全局能見(jiàn)度；表示第t周期內(nèi)邊（i，j）上抗體親和力；ρ為信息素殘留系數(shù)；表示該次循環(huán)里最優(yōu)的螞蟻在i，j路徑上信息量的增加量；f（sbest）為螞蟻所走最優(yōu)路徑長(zhǎng)度；avg＝L／2，L為配送客戶(hù)數(shù)量；Pbest＝0.05，表示螞蟻搜索一次即尋到最優(yōu)解的概率。環(huán)境信息素在運(yùn)算開(kāi)始時(shí)設(shè)置為τmax。

由于在實(shí)際運(yùn)輸過(guò)程中，運(yùn)輸總成本由運(yùn)輸方式和運(yùn)輸時(shí)間共同決定，故在選擇一條運(yùn)輸成本和時(shí)間綜合考慮的路徑時(shí)，其狀態(tài)轉(zhuǎn)移策略也不同。通過(guò)循環(huán)迭代可得全局最優(yōu)螞蟻的路徑長(zhǎng)度。

4 算例分析

4.1 數(shù)據(jù)采集

本文選擇某煙草公司17 173 條訂單數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，并將其分為A、B、C、D、E、F、G、H共八組。同時(shí)為了方便計(jì)算，在收集卷煙訂單量時(shí)，卷煙單位統(tǒng)一為m3。限于篇幅，本文摘取部分?jǐn)?shù)值如表1 所示。

表1 某煙草公司訂單數(shù)據(jù)表Tab.1 Order data of a tobacco company

4.2 運(yùn)算結(jié)果

本文基于matlab 實(shí)現(xiàn)蟻群-免疫算法，為物流配送路線優(yōu)化提供服務(wù)。為了檢驗(yàn)算法的有效性，此處選用代表性較高的A1 組作為實(shí)驗(yàn)案例。圖3 所示為組團(tuán)彈性模式下運(yùn)用蟻群-免疫算法得到的最優(yōu)配送路徑，通過(guò)導(dǎo)入各零售商的位置信息及卷煙訂購(gòu)量可知，面對(duì)A1 組內(nèi)11 個(gè)零售商，配送中心只需兩輛車(chē)即可完成補(bǔ)貨任務(wù)。與傳統(tǒng)配送模式相比，大大降低了完成配送所需的車(chē)輛數(shù)與配送成本。

圖3 組團(tuán)模式下蟻群-免疫算法配送圖Fig.3 Ant colony-immune algorithm delivery in group mode

圖4 分別呈現(xiàn)了傳統(tǒng)配送、蟻群算法、蟻群-免疫混合算法在50 次迭代過(guò)程中的路程值。由圖4可知，與傳統(tǒng)配送模式相比，蟻群算法與蟻群-免疫混合算法都能有效地降低配送距離，且混合算法得到的結(jié)果更優(yōu)。這是由于算例在求解過(guò)程中可能會(huì)存在可行解不唯一的情況，僅通過(guò)蟻群算法進(jìn)行求解容易陷入局部最優(yōu)解；而混合算法具有很好的全局搜索能力，通過(guò)引入路徑濃度抑制機(jī)制與免疫機(jī)制，在不斷迭代的過(guò)程中，親和度不足的路線將被加入禁忌表，從而在求解后期可以有效避免陷入局部最優(yōu)并提高求解效率。

圖4 傳統(tǒng)配送、蟻群算法及蟻群-免疫算法路程值比較Fig.4 Comparison of distance values among traditional delivery,ant colony algorithm and ant colony-immune algorithm

圖5 與圖6 從庫(kù)存量與補(bǔ)貨及時(shí)性角度出發(fā)，對(duì)兩種配送模式進(jìn)行了仿真。通過(guò)對(duì)比不難發(fā)現(xiàn)，在圖5 所示的傳統(tǒng)配送模式之下，各零售店以個(gè)體為單位，由于對(duì)煙草的需求量與補(bǔ)貨周期不同，剩余庫(kù)存呈無(wú)規(guī)律波動(dòng)，若依據(jù)傳統(tǒng)模式進(jìn)行配送，易導(dǎo)致車(chē)輛裝載率較低和發(fā)車(chē)頻繁等現(xiàn)象的發(fā)生。同時(shí)車(chē)輛可能因?yàn)樘鞖狻⒔煌〒矶碌韧话l(fā)狀況的影響而無(wú)法準(zhǔn)時(shí)完成配送任務(wù)，從而導(dǎo)致零售商某時(shí)刻的庫(kù)存小于等于零，帶來(lái)不必要的缺貨成本。而在彈性配送模式下，配送車(chē)輛服務(wù)于各個(gè)組團(tuán)（如圖6 所示），各組團(tuán)補(bǔ)貨周期穩(wěn)定在3 d 左右，各組僅需1 輛車(chē)即可完成配送工作，在優(yōu)化配送路徑的過(guò)程中不僅保證了配送的穩(wěn)定性與及時(shí)性，同時(shí)增加了配送過(guò)程的靈活性，提高了車(chē)輛裝載率，避免了不必要的裝載空間浪費(fèi)。

圖5 傳統(tǒng)模式下各個(gè)區(qū)域平均庫(kù)存剩余情況Fig.5 Average inventory surplus in each area under traditional mode

圖6 組團(tuán)彈性模式下各區(qū)域平均庫(kù)存剩余情況Fig.6 Average inventory surplus in each region under the group elastic mode

綜上所述，與傳統(tǒng)配送模式相比，組團(tuán)配送模式在減少配送距離、提高配送及時(shí)性、降低配送成本等方面都取得了新的突破。其余各組的配送優(yōu)化情況如表2 所示。

表2 模型結(jié)果對(duì)比Tab.2 Comparison of model results

通過(guò)結(jié)果比較分析可知，優(yōu)化后各條線路配送平均里程與車(chē)輛使用數(shù)都得到了有效的減少，完成一次配送的總路程可優(yōu)化縮短28.51%。此外，運(yùn)用本文得出的優(yōu)化方案，各條配送線路的工作量也較優(yōu)化之前更均衡，提高了服務(wù)水平。

5 結(jié)論

為有效提高煙草物流的配送效率，本文以配送成本最小化為目標(biāo)，從配送的合理性、及時(shí)性等方面對(duì)多個(gè)零售商的煙草需求和車(chē)輛配送問(wèn)題展開(kāi)研究。首先，考慮到各零售商對(duì)煙草的需求量以及補(bǔ)貨周期不同，構(gòu)建了彈性配送優(yōu)化模型，以保證煙草物資分配的合理性與及時(shí)性。其次，通過(guò)結(jié)合煙草物流配送實(shí)際情況，設(shè)計(jì)了蟻群-免疫算法完成路徑優(yōu)化，通過(guò)更新抗體濃度與親和力，不斷更新禁忌表，在正反饋機(jī)制作用下，使得搜索過(guò)程不斷收斂，最終求得最優(yōu)解。最后，通過(guò)算例分析對(duì)算法進(jìn)行驗(yàn)證。結(jié)果顯示蟻群-免疫優(yōu)化算法在解決路線優(yōu)化問(wèn)題時(shí)要優(yōu)于傳統(tǒng)配送與蟻群算法，大大節(jié)省了配送車(chē)輛數(shù)與行駛距離；此外，運(yùn)用本文得出的優(yōu)化方案，各條配送線路的工作量也較優(yōu)化之前明顯均衡。本研究對(duì)于構(gòu)建現(xiàn)代物流體系具有一定的借鑒意義。

在使用組團(tuán)彈性配送過(guò)程中仍需注意以下幾點(diǎn)：1）分組前，配送中心需根據(jù)各個(gè)位置信息、車(chē)輛最大裝載量、車(chē)輛最大行駛距離及需求量對(duì)零售商們進(jìn)行合理分組，保證每組僅由一輛車(chē)即可完成配送；2）結(jié)合煙草物流特性，本文建立了不允許缺貨和補(bǔ)貨需要一定時(shí)間的存儲(chǔ)模式，因此補(bǔ)貨周期應(yīng)結(jié)合組內(nèi)各零售商剩余庫(kù)存與日均銷(xiāo)量進(jìn)行調(diào)整，避免出現(xiàn)缺貨情況；3）對(duì)于異形煙草，配送中心可結(jié)合零售商的位置信息及需求量，考慮采用特殊車(chē)型進(jìn)行配送。在未來(lái)的工作中，將結(jié)合實(shí)時(shí)交通擁堵情況、車(chē)輛運(yùn)行方向及突發(fā)訂單需求等因素，完成對(duì)配送模型的深入優(yōu)化。