（安徽理工大學(xué) 經(jīng)濟(jì)與管理學(xué)院，安徽 淮南 232001）

電子商務(wù)的快速發(fā)展將物流推向風(fēng)口浪尖，各界學(xué)者和企業(yè)管理者將研究目光轉(zhuǎn)向物流領(lǐng)域，各物流公司在降低物流成本、提高客戶滿意度等方面競爭也愈加激烈。隨著市場需求日益增長，單配送中心配送壓力大，易導(dǎo)致車輛調(diào)度失衡、物流成本增加、配送效率降低，已不能適應(yīng)企業(yè)發(fā)展。而多個配送中心進(jìn)行進(jìn)行配送時，需要各配送中心根據(jù)配送地點、需求數(shù)量、需求種類來合理規(guī)劃路線，這就需要配送中心實現(xiàn)信息實時共享，協(xié)作配送，實現(xiàn)配送規(guī)模化，從而提高配送車輛利用率、降低配送成本。

在車輛配送中，秦敏[1]、畢國通[2]等學(xué)者只研究了單配送中心車輛配送，然而單個配送中心切斷區(qū)域間的聯(lián)系，使得物流資源難以共享，導(dǎo)致車輛配送成本增加。經(jīng)濟(jì)的快速發(fā)展使得客戶對糧食[3]、冷鏈?zhǔn)称穂4]的需求增多，單配送中心顯然已不能滿足客戶對期望配送時間的要求。在多配送中心車輛路徑研究上，高珊珊[5]提出時間窗概念，引入懲罰因子，在滿足配送成本的同時，提高客戶滿意度。蘇海倩[6]在此基礎(chǔ)上考慮碳排放量，為綠色物流打下基礎(chǔ)。日本最早提出協(xié)同配送，要求有組織任務(wù)的各配送中心形成聯(lián)盟，共同組織配送任務(wù)，Andrsm[7]采用哥倫比亞首都圣菲波哥大的真實數(shù)據(jù)來比較聯(lián)盟與未聯(lián)盟的差異，事實證明，配送中心形成聯(lián)盟卓有成效。張占云[8]結(jié)合人工智能，在協(xié)同配送基礎(chǔ)上，提出了基于智能體交互的聯(lián)盟，各配送中心和客戶點能夠根據(jù)具體環(huán)境協(xié)調(diào)、合作求出適應(yīng)環(huán)境的最優(yōu)解。求解多配送中心車輛配送模型時，Yong Wang[9]提出包含k-means、NSGA-II的混合算法，將客戶大致分類，轉(zhuǎn)化為多個單配送中心配送問題，雖簡化了算法，但求解出來的配送路線并非最優(yōu)，還會出現(xiàn)資源浪費現(xiàn)象(如車輛空載率高、人員配備冗余)和客戶滿意度降低。侯宇超[10]提出精英蟻群算法，來避免傳統(tǒng)蟻群算法陷入局部最優(yōu)和增大算法收斂性。

1 問題描述

1.1 多配送中心車輛路徑問題描述

多配送中心車輛路徑問題是研究車輛從多個配送中心出發(fā)向多個客戶點服務(wù)的過程。一般可以描述為在整個物流系統(tǒng)中有多個配送中心，車輛從各自所在的配送中心出發(fā)，選擇合理的配送路線對客戶進(jìn)行物流服務(wù)，使其在滿足客戶需求，配送車輛滿足時間窗要求、車輛容量、行駛里程和配送時間約束條件下，達(dá)到整體目標(biāo)最優(yōu)(如配送成本最低、車輛行駛路徑最短、服務(wù)時間最短、車輛空載率低等)。

1.2 智能體聯(lián)盟問題描述

智能體是在某個特定的環(huán)境下，與外界環(huán)境交互，自發(fā)解決特定任務(wù)的計算機(jī)系統(tǒng)，具有自主性、分布性、協(xié)調(diào)性等特點。多智能體系統(tǒng)中，每個智能體負(fù)責(zé)系統(tǒng)中某一模塊，具有相當(dāng)獨立性，通過協(xié)調(diào)、溝通、合作完成系統(tǒng)整體任務(wù)。智能體之間結(jié)構(gòu)是動態(tài)的，可以依據(jù)具體環(huán)境進(jìn)行調(diào)整，具有一定的適應(yīng)性?；谥悄荏w的聯(lián)盟的多配送中心核心思想是將模型中單個配送中心和客戶點看作一個智能體，從而將多配送中心車輛路徑問題轉(zhuǎn)化為多任務(wù)環(huán)境下的智能體聯(lián)盟問題，求解智能體間如何聯(lián)盟合作使整體效果最優(yōu)。在車輛配送時，各配送中心和客戶點自主協(xié)調(diào)、合作找出滿足條件最優(yōu)解。

各個智能體之間通過黑板模式進(jìn)行協(xié)調(diào)溝通，從而形成聯(lián)盟。黑板是各智能體進(jìn)行交流溝通的公共區(qū)域，每個智能體從黑板中發(fā)生和獲取信息，從而完成系統(tǒng)賦予自己的任務(wù)。多配送中心智能體聯(lián)盟配送可以描述為：首先客戶對產(chǎn)品需求形成訂單，訂單智能體將客戶需求傳送給各配送中心，配送中心智能體實時接收車輛智能體和倉庫智能體發(fā)送信息，各配送中心智能體之間根據(jù)訂單智能體需求，通過黑板協(xié)調(diào)溝通，合理安排車輛和貨物，形成動態(tài)聯(lián)盟。多配送中心智能體聯(lián)盟配送如圖1。

智能體聯(lián)盟問題可以描述為：設(shè)有n個智能體的集合N={A1,A2,…,An},現(xiàn)有任務(wù)集T={t1,t2,…tm}需要并行執(zhí)行，其中任務(wù)tj最低的能力需要為。聯(lián)盟C為N的一個非空子集，問題的一個合法解定義為：尋找N的一個聯(lián)盟結(jié)構(gòu)Cs={C1,C2,…Cm}，要求對于任意的i,j＜m,i≠j,Ci∩Cj=φ,任意i≤m,Ci中所有智能體能力總和滿足任務(wù)tj的能力需求。聯(lián)盟Ci的成本特征函數(shù)為V(Ci)=F(Ci)+G(Ci)，D(Ci)≤Di,i≤m。式中：F(Ci)為聯(lián)盟Ci的成本；G(Ci)為聯(lián)盟Ci的通信或合作開銷。

2 MDVRP 模型建立

2.1 模型假設(shè)

為了便于建立MDVRP 模型，使該模型簡潔又具有一定的實用性，假設(shè)系統(tǒng)滿足以下條件：

(1)配送中心，客戶點的地理位置、需求量已知；(2)運輸對像為同種類型，滿足運輸規(guī)范；(3)配送中心庫存充足，產(chǎn)品種類和數(shù)量滿足客戶需求；(4)每個客戶的需求量不得超過車輛容載量，車輛出發(fā)到返回配送中心行駛的總距離不得超過車輛的最大行駛距離；(5)每個客戶點只能由一輛車進(jìn)行服務(wù)，且車輛最終需返回配送中心。

2.2 基于軟時間窗的MDVRP

配送時，客戶往往要求在規(guī)定的時間內(nèi)送達(dá)，這就提出了車輛路徑時間窗的概念。在實際過程中，由于一些不確定因素，配送時間未在客戶期望的時間段內(nèi)到達(dá)客戶手中，但客戶也存在可接受的上下界時間窗，若在客戶可接受的時間窗內(nèi)送達(dá)，則只需付出一定的懲罰費用，不影響配送結(jié)果。若配送時間超出客戶可接受范圍，則客戶拒絕接受貨物，設(shè)懲罰費用無窮大。問題描述為：ETi為客戶i期望最早服務(wù)時間，LTi為客戶i 期望最遲服務(wù)時間。在[ETi,LTi]時間窗內(nèi)，客戶樂意接受貨物，滿意度為100%。EETi為客戶i可接受的最早服務(wù)時間，LLTi為客戶i可接受的最遲服務(wù)時間。在時間窗[EETi,ETi]和[LTi,LLTi]內(nèi)，客戶可接受服務(wù)，但需付出一定的懲罰費用。若服務(wù)時間早于EETi或晚于LLTi,客戶i拒絕接受貨物，懲罰費用無窮大?？蛻糗洉r間窗下滿意度如圖2。

懲罰成本為：

其中：Pt為有時間窗約束的懲罰成本，?為在時間窗[EET,ET]內(nèi)服務(wù)客戶的懲罰系數(shù)，b為在時間窗[LT,LLT]內(nèi)服務(wù)客戶的懲罰系數(shù)。

2.3 參數(shù)定義

I={i=1,2,…n}表示客戶訂單集合；M={m=1,2,…m0}表示配送中心集合；L={l=1,2,…I0}表示配送車輛集合；dij表示客戶點i到客戶點j的距離；Fl表示第l輛車的固定成本；ti表示到達(dá)客戶點i的時間；Cd表示單位距離內(nèi)產(chǎn)生的運輸成本；Dl表示車輛l行駛的最大距離；Ql表示車輛l的最大載重量；qi表示客戶i的需求量。

(1)車輛固定成本：車輛固定成本包括車輛的購買費、燃油費、修理費、定期保養(yǎng)費以及支付給司機(jī)的人工費。車輛的固定成本與執(zhí)行任務(wù)的車輛數(shù)量有關(guān)，與道路狀況和行駛過程無關(guān)。車輛固定費用用S1m表示從配送中心m出發(fā)nm車輛的總固定成本。

(2)車輛運輸費用：車輛運輸費用是指車輛l從配送中心m出發(fā)，向客戶i進(jìn)行配送，再轉(zhuǎn)向客戶j,最終回到配送中心m產(chǎn)生的運輸費用。車輛運輸成本與距離成正比例關(guān)系，用S2m表示。

(3)車輛懲罰成本：根據(jù)上述對軟時間窗下車輛配送的探討，車輛懲罰成本用S3m表示。前半部分是對早于最早期望ET的機(jī)會成本，后半部分是晚于最遲期望時間LT的延遲成本。

2.4 模型建立

根據(jù)上述對目標(biāo)函數(shù)分析，模型建立為：

其中：式（4）表示為各配送總成本之和最低的目標(biāo)函數(shù)；式（5）表示分配給車輛l的總訂單路程不得超過車輛l的最大行駛距離；式（6）表示分配給車輛l的總訂單需求量不得超過車輛l的容載量；式（7）表示每個客戶i只能由一輛車進(jìn)行提供一次服務(wù)；式（8）表示執(zhí)行任務(wù)的車輛l從配送中心出發(fā)，最終返回配送中心。

3 改進(jìn)蟻群算法求解MDVRP 問題

3.1 處理方法及分析

多配送中心車輛路徑問題本身就是一個non-deterministic polynomial problems（NP）問題，隨著客戶點的增加，可選方案求解數(shù)量會急劇增加，這對求解問題最優(yōu)解帶來了困難。

改進(jìn)蟻群算法是采用正反饋機(jī)制的模擬進(jìn)化算法，具有較強(qiáng)的魯棒性，且易于結(jié)合其他算法的優(yōu)點。因此，改進(jìn)蟻群算法適用于MDVRP 問題。在用改進(jìn)蟻群算法求解MDVRP 問題時，將配送中心和客戶點看作智能體，一群人工螞蟻根據(jù)信息素和啟發(fā)信息在配送中心和客戶點行走，更新禁忌表，直至所有螞蟻都完成搜索，獲得聯(lián)盟最優(yōu)解。

3.2 改進(jìn)蟻群算法

蟻群算法雖在求解性能上，具有很好的魯棒性和搜索能力，但當(dāng)客戶點較多時，蟻群算法搜索時間過長且收斂速度慢，易陷入局部最優(yōu)。因此，為了讓蟻群算法適用于多配送中心車輛配送問題，通過首先使用輪盤賭法隨機(jī)選擇初始值，在生成初始解后，對其實施交叉，翻轉(zhuǎn)操作，增加種群多樣性，從而提高解的質(zhì)量。在完成一次循環(huán)后，對選定的螞蟻遍歷路徑進(jìn)行信息的添加，來改進(jìn)信息素，加速收斂。更新信息素時加入最優(yōu)路徑額外的信息素量，使得最優(yōu)解得到更多的利用。找到全局最優(yōu)解的螞蟻成為“精英螞蟻”。

對信息素總量Q實行三段函數(shù)進(jìn)行優(yōu)化，規(guī)則如下：

其中：iter為當(dāng)前迭代值，iter1、iter2、iter3為設(shè)定的一定臨界值。

改進(jìn)的蟻群算法基本步驟：

Step1：設(shè)置初始化參數(shù)，首先對算法中所有參數(shù)進(jìn)行初始化處理。

Step2：構(gòu)建解空間，輪盤賭法為螞蟻隨機(jī)選擇出發(fā)點，按狀態(tài)轉(zhuǎn)移規(guī)則選擇下一個代訪問的客戶點，選擇之后更新禁忌表。

Step3：對客戶點進(jìn)行交叉、翻轉(zhuǎn)、插入操作，更新禁忌表，所有螞蟻完成一次循環(huán)后構(gòu)成一個路徑解。

Step4：更新信息素，按照信息素更新規(guī)則更新信息素。

Step5：最優(yōu)路徑添加額外信息素，找到精英螞蟻。

Step6：判斷是否達(dá)到最大迭代次數(shù)，若達(dá)到最大迭代次數(shù)，則進(jìn)行下一步；若未達(dá)到最大迭代次數(shù)，則當(dāng)前次數(shù)加1 并清空禁忌表，返回Step2。

Step7：輸出最優(yōu)解，若螞蟻循環(huán)達(dá)到最大迭代次數(shù)，則完成迭代輸出最優(yōu)解。

4 實例驗證

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

本文選取4 家配送中心和30 個客戶點為研究對象進(jìn)行分析，依托matlab2015b 進(jìn)行算法編程，求解車輛配送最優(yōu)解。4 家配送中心和30 個客戶點的地理位置、客戶需求量及期望時間如表1、表2所示。

表1 配送中心位置

表2 客戶資料表

4.2 參數(shù)設(shè)置

通過多次試驗和參考相關(guān)文獻(xiàn)，現(xiàn)設(shè)蟻群算法中最大迭代次數(shù)Maxlt=300；螞蟻數(shù)量nAnt=20;信息素更新參數(shù)Q=50；初始信息素tau0=8；信息素最小值tau_min=1.2；信息素權(quán)重α=2；啟發(fā)因子權(quán)重β=3；信息揮發(fā)系數(shù)ρ=0.05。

設(shè)模型第l 輛車固定成本Fl=200；單位距離內(nèi)產(chǎn)生的運輸成本Cd=5；車輛l 行駛的最大距離為200 km；車輛l 的最大載重量為15 t，車輛速度為40 km/h。

4.3 算法分析

運用改進(jìn)蟻群算法求得最佳路徑為配1-24-6-28-9-配 1；配 2-5-3-30-20-配 2；配2-1-7-23-22-配 2；配 2-16-10-25-21-配 2；配3-29-19-8-12-配 3；配 3-26-2-27-17-配 3；配3-14-15-18-13-配3；配4-4-11-配4。改進(jìn)蟻群算法求解車輛配送路徑圖見圖3

而蟻群算法求得的最佳路徑為配1-29-28-1-30-9-配1；配2-5-3-20-21-25-16-配2；配3-23-7-13-配3；配3-2-27-14-17-10-22-配3；配3-26-12-15-18-配3；配4-4-11-6-24-19-8-配4。蟻群算法求解車輛配送路徑圖見圖4。

從表3 可以看出改進(jìn)蟻群算法在求解總距離和總成本上都優(yōu)于蟻群算法，額外信息素避免了結(jié)果陷入局部最優(yōu)。

表3 配送距離與成本

由仿真收斂圖可以看出，改進(jìn)蟻群算法(如圖5)在不到20 代急劇收斂，在50 代已經(jīng)趨于平穩(wěn)，而蟻群算法(如圖6)在100 代才趨于平穩(wěn)。改進(jìn)后的蟻群算法在速度和質(zhì)量上都有明顯提高。

實驗結(jié)果表明，本文改進(jìn)蟻群算法求得的解在總距離和總成本上都優(yōu)于蟻群算法求得的解。雖然改進(jìn)蟻群算法在算法上較為復(fù)雜，但通過交叉、翻轉(zhuǎn)操作，增加種群多樣性，從而增加可行路徑解數(shù)量，在更新信息素時加入最優(yōu)路徑額外的信息素量，指定精英螞蟻，在精英螞蟻的帶領(lǐng)下，避免陷入局部最優(yōu)，快速找到最優(yōu)路徑，增加了算法的收斂性和蟻群的尋優(yōu)能力。

4.4 未聯(lián)盟配送中心對比

在以未聯(lián)盟配送中心計算案例時，先用k-means 聚類分析將各客戶點到配送中心距離遠(yuǎn)近劃分給各配送中心，依托R 軟件3.6.1 進(jìn)行算法編程，編程結(jié)果如圖7。

經(jīng)過k-means 分類，將問題轉(zhuǎn)化為多個單配送中心求解，用改進(jìn)蟻群算法，依托matlab2015b 求得各單配送中心車輛配送路徑，配送路線、單配送中心距離及成本如表4。

表4 單配送中心車輛配送

由表3 與表4 可知，多配送中心聯(lián)盟的配送總距離為858.255 km，總成本為6 057.984 元，而獨立存在的多個配送中心配送總距離為880.586 km，總成本為6192.590 元。在表4 中，向有的客戶進(jìn)行配送服務(wù)時，車輛負(fù)載率很低，這時就需要各配送中心之間通過黑板模式將客戶信息共享，通過溝通，協(xié)調(diào)，合理安排車輛路線，提高配送車輛的資源利用率，降低配送成本。

5 結(jié)論

在物流配送過程中，車輛路徑問題是重要環(huán)節(jié)之一，路徑規(guī)劃合理與否直接影響著整個配送過程的效率。在現(xiàn)實生活中，配送中心往往由于缺乏信任、信息更新不及時而忽視了聯(lián)盟帶來的成本降低、資源利用率高等優(yōu)勢。本文通過對比配送中心聯(lián)盟與配送中心未聯(lián)盟，得出配送中心聯(lián)盟的配送距離和配送成本明顯更優(yōu)。企業(yè)為了更好的運營，聯(lián)盟是大勢所趨。在求解多配送中心車輛配送模型時，改進(jìn)蟻群算法在解的求解速度和質(zhì)量上明顯優(yōu)于傳統(tǒng)蟻群算法。本文建立的模型是在理想假設(shè)的情況下，與實際配送存在差距，需要我們將更多的現(xiàn)實條件加入約束條件，使得車輛配送更加具有現(xiàn)實性。