基于智能體聯(lián)盟的多配送中心路徑優(yōu)化研究

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

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

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

1 問題描述

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

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

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

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

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

智能體聯(lián)盟問題可以描述為：設(shè)有n個(gè)智能體的集合N={A1,A2,…,An},現(xiàn)有任務(wù)集T={t1,t2,…tm}需要并行執(zhí)行，其中任務(wù)tj最低的能力需要為。聯(lián)盟C為N的一個(gè)非空子集，問題的一個(gè)合法解定義為：尋找N的一個(gè)聯(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í)用性，假設(shè)系統(tǒng)滿足以下條件：

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

2.2 基于軟時(shí)間窗的MDVRP

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

懲罰成本為：

其中：Pt為有時(shí)間窗約束的懲罰成本，?為在時(shí)間窗[EET,ET]內(nèi)服務(wù)客戶的懲罰系數(shù)，b為在時(shí)間窗[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表示客戶點(diǎn)i到客戶點(diǎn)j的距離；Fl表示第l輛車的固定成本；ti表示到達(dá)客戶點(diǎn)i的時(shí)間；Cd表示單位距離內(nèi)產(chǎn)生的運(yùn)輸成本；Dl表示車輛l行駛的最大距離；Ql表示車輛l的最大載重量；qi表示客戶i的需求量。

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

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

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

2.4 模型建立

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

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

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

3.1 處理方法及分析

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

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

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

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

對信息素總量Q實(shí)行三段函數(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ā)點(diǎn)，按狀態(tài)轉(zhuǎn)移規(guī)則選擇下一個(gè)代訪問的客戶點(diǎn)，選擇之后更新禁忌表。

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

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 實(shí)例驗(yàn)證

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

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

表1 配送中心位置

表2 客戶資料表

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

通過多次試驗(yàn)和參考相關(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)生的運(yùn)輸成本Cd=5；車輛l 行駛的最大距離為200 km；車輛l 的最大載重量為15 t，車輛速度為40 km/h。

4.3 算法分析

運(yùn)用改進(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ì)量上都有明顯提高。

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

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

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

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

表4 單配送中心車輛配送

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

5 結(jié)論

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