基于極值
—蟻群算法的電商末端物流彈性配送策略研究

阮　煥， 耿　亮,2， 肖人彬

(1. 華中科技大學(xué) 自動(dòng)化學(xué)院，湖北 武漢 430074；2. 湖北工業(yè)大學(xué) 理學(xué)院，湖北 武漢 430068)

?

基于極值
—蟻群算法的電商末端物流彈性配送策略研究

阮煥1， 耿亮1,2， 肖人彬1

(1. 華中科技大學(xué) 自動(dòng)化學(xué)院，湖北 武漢 430074；2. 湖北工業(yè)大學(xué) 理學(xué)院，湖北 武漢 430068)

摘要：主要研究電商物流配送中貨物由配送中心送達(dá)客戶的過程，即末端物流。為降低配送成本同時(shí)提高服務(wù)質(zhì)量，結(jié)合車輛路徑問題與電商中消費(fèi)需求“多品種、小批量、多批次、短周期”的特點(diǎn)，針對(duì)客戶每日需求的不確定性，提出針對(duì)每日需求的信息化的彈性配送策略，以人均成本最小化為目標(biāo)構(gòu)造了模型；設(shè)計(jì)基于極值動(dòng)力學(xué)的改進(jìn)蟻群算法對(duì)物流配送路徑進(jìn)行優(yōu)化，通過“尋優(yōu)”與“棄差”、局部搜索與全局搜索相結(jié)合，提高了算法收斂效率；并通過對(duì)算例驗(yàn)證了該算法在面對(duì)多種不確定性需求時(shí)候的彈性，有助于實(shí)現(xiàn)電商物流的有效配送。

關(guān)鍵詞：電商末端物流； 極值動(dòng)力學(xué)； 蟻群算法； 彈性配送

隨著互聯(lián)網(wǎng)以及電商的普及，由于網(wǎng)購能夠提供更多的商品信息，并且不受時(shí)間地點(diǎn)的約束，省事省力，因此越來越多的人選擇在網(wǎng)上購物。但是相對(duì)于傳統(tǒng)的上街購物模式，網(wǎng)購商品需要一定的時(shí)間到達(dá)客戶手中，而這段時(shí)間的長(zhǎng)短是影響客戶網(wǎng)購體驗(yàn)最重要的因素之一。因而電子商務(wù)的發(fā)展需要健全的物流體系大力支持，同時(shí)也必然帶動(dòng)以快遞業(yè)務(wù)為基礎(chǔ)的電商物流業(yè)的快速發(fā)展。根據(jù)中國(guó)快遞協(xié)會(huì)公布的最新數(shù)據(jù)，2014年我國(guó)快遞業(yè)務(wù)量達(dá)140億件，同比增長(zhǎng)52%，躍居世界第一。快遞業(yè)務(wù)量連續(xù)46個(gè)月累計(jì)同比平均增幅超過50%，在從“快遞大國(guó)”向“快遞強(qiáng)國(guó)”轉(zhuǎn)變的道路上邁出了堅(jiān)實(shí)的一步。但與此同時(shí)，“最后一公里”投遞難題依然存在[1]。

電子商務(wù)的發(fā)展以及物聯(lián)網(wǎng)和大數(shù)據(jù)時(shí)代的來臨，給全球物流帶來了物流信息化的新發(fā)展。與傳統(tǒng)的物流配送服務(wù)不同，物流設(shè)施、商品包裝的標(biāo)準(zhǔn)化，物流的社會(huì)化、共同化都是電子商務(wù)下物流模式的新特點(diǎn)。此外電商物流配送的運(yùn)作重心后移，愈加偏重前臺(tái)物流，更直接地面向消費(fèi)者，更加注重物流的效率以及用戶的體驗(yàn)[2]，因此在物品由配送中心到客戶手中這一段過程，即末端物流顯得尤為重要。

電商末端物流的主體是車輛路徑問題。相比于傳統(tǒng)的車輛路徑問題，電商物流中的末端物流具有如下特點(diǎn)：1) 客戶數(shù)量多，分布廣；2) 每次產(chǎn)生需求的客戶數(shù)量以及位置是不確定的；3) 快遞配送由訂單生成到配送過程是有滯后性的[3]。因此配送過程應(yīng)當(dāng)結(jié)合每日訂單，實(shí)現(xiàn)信息流、物流、資金流的有效結(jié)合[4]。物流配送中心要根據(jù)消費(fèi)需求“多品種、小批量、多批次、短周期”的特色，靈活組織和實(shí)施物流作業(yè)。面對(duì)這些客戶需求的不確定性，彈性化的物流正是適應(yīng)生產(chǎn)、流通與消費(fèi)的需求而發(fā)展起來的一種新型物流模式。

車輛路徑問題(vehicle routing problem， VRP)來源于交通運(yùn)輸，由Dantzig等[5]于1959 年提出。它是組合優(yōu)化問題中一個(gè)典型的NP-hard問題。它通過對(duì)車輛的運(yùn)輸路線進(jìn)行優(yōu)化，在滿足客戶需求的前提下，盡量以最低的運(yùn)輸成本與費(fèi)用將貨物送達(dá)目的地。自VRP問題提出以來，吸引了眾多學(xué)者進(jìn)行研究。1995年出版的《運(yùn)籌學(xué)與管理科學(xué)手冊(cè)》在第八章專門講解了車輛路徑問題[6]；2002年,Paolo等[7]全面分析了當(dāng)時(shí)VRP的研究?jī)?nèi)容及展望。相對(duì)而言，國(guó)內(nèi)的研究起步較晚。郭耀煌等[8]首次詳細(xì)講解了VRP問題；之后掀起了國(guó)內(nèi)VRP的研究熱潮，馮輝宗等[9]通過對(duì)汽車運(yùn)輸?shù)奶攸c(diǎn)和成本的分析，采用了遺傳算法求解；劉小蘭等[10]針對(duì)帶時(shí)間窗的車輛路徑問題(VRPTW)，通過引入短路徑優(yōu)先策略，構(gòu)造了改進(jìn)的大規(guī)模鄰域搜索算法求解；溫惠英等[11]以車輛配送的總費(fèi)用最小為目標(biāo)，對(duì)帶時(shí)間窗協(xié)同車輛路徑問題(CVRP)構(gòu)建了數(shù)學(xué)規(guī)劃模型，并采用自適應(yīng)離散粒子群算法求解，驗(yàn)證了模型的正確性和合理性；李妍峰等[12]對(duì)實(shí)時(shí)交通信息下的城市動(dòng)態(tài)網(wǎng)絡(luò)車輛路徑優(yōu)化問題，結(jié)合初始路徑安排與實(shí)時(shí)路線調(diào)整構(gòu)建了模型，驗(yàn)證了新實(shí)時(shí)路線更新機(jī)制的優(yōu)越性。這些對(duì)于傳統(tǒng)車輛路徑問題的研究提供了很多種不同的VRP模型，以及各種各樣的解決方案，但是并沒能很好地解決電商物流問題的模型以及方案。電商物流的配送過程中，由配送中心到客戶手上這一過程對(duì)客戶的不滿意度有著極大的影響，并且其成本占了物流配送成本中極大的一部分；更主要的是相對(duì)于傳統(tǒng)車輛路徑問題，它在客戶需求上具有極大的不確定性，因此無論是路徑優(yōu)化，還是成本計(jì)算，傳統(tǒng)車輛路徑問題的解決方案都無法完美解決。

相應(yīng)的，目前國(guó)內(nèi)關(guān)于電商物流的研究主要有：楊建功[2]針對(duì)電商物流與傳統(tǒng)物流的區(qū)別，提出了前臺(tái)物流與后臺(tái)物流的概念；楊聚平等[13]對(duì)電商物流配送中的最后一公里問題提出了若干解決方案；張昕[14]分析了多種末端物流共同配送模式及決策路徑下的方案研究，并對(duì)這些方案進(jìn)行對(duì)比，以及在面對(duì)特定問題時(shí)對(duì)這些方案進(jìn)行組合提出最優(yōu)解決方案；席運(yùn)江等[15]對(duì)于快遞網(wǎng)絡(luò)這種典型的混合軸輻式網(wǎng)絡(luò)，提出了快遞企業(yè)配送網(wǎng)絡(luò)系統(tǒng)的多層、多維、多標(biāo)準(zhǔn)以及整體性特征，選用超網(wǎng)絡(luò)模型理論對(duì)其進(jìn)行研究和分析；黃建華等[16]分析了快遞網(wǎng)絡(luò)在分別遭遇了人工破壞以及蓄意破壞時(shí)，所表現(xiàn)出的魯棒性以及脆弱性。這些快遞網(wǎng)絡(luò)的研究，大部分是針對(duì)電商物流的定性研究，從運(yùn)營(yíng)策略上來解析問題；而對(duì)于電商物流的定量的研究中，又沒有真正地結(jié)合電商物流配送本身的特性解決問題。

因此，本文綜合傳統(tǒng)車輛路徑問題與電商物流配送的實(shí)際問題，結(jié)合電商物流的信息化以及需求不確定性的特點(diǎn)，提出電商末端物流的彈性管理措施；并設(shè)計(jì)基于極值動(dòng)力學(xué)的改進(jìn)蟻群算法，針對(duì)客戶需求數(shù)量不確定的問題，將人均成本作為成本計(jì)算方式，制定配送計(jì)劃，通過與普通蟻群算法的對(duì)比驗(yàn)證了算法的有效性，并通過仿真驗(yàn)證了模型在面對(duì)不同客戶需求下的彈性，對(duì)實(shí)際的電商物流運(yùn)作具有一定的指導(dǎo)作用。

1問題描述

彈性概念最早產(chǎn)生于彈性力學(xué)研究中，屬于物理學(xué)科的范疇。1973年，Holling[17]將彈性概念引入生態(tài)學(xué)，并將其定義為系統(tǒng)在均衡改變前吸收擾動(dòng)的能力；之后在供應(yīng)鏈中斷事件背景下，Christopher等[18]提出了供應(yīng)鏈彈性的框架，并指出彈性是指系統(tǒng)在中斷后回到原始(或新的更理想)狀態(tài)的能力。隨后彈性概念逐漸被引入不同的學(xué)科來描述復(fù)雜動(dòng)態(tài)系統(tǒng)的關(guān)鍵特征，如生態(tài)學(xué)、工程學(xué)、經(jīng)濟(jì)學(xué)、心理學(xué)、社會(huì)學(xué)等。綜合各學(xué)科關(guān)于彈性的定義可以看出，彈性作為系統(tǒng)的內(nèi)在屬性，包含承受擾動(dòng)、緩解風(fēng)險(xiǎn)、恢復(fù)中斷等多維度概念，反映了系統(tǒng)在面臨風(fēng)險(xiǎn)事件時(shí)的適應(yīng)性和調(diào)節(jié)能力。

在電商物流配送過程中，面對(duì)的主要干擾類型為每天不確定的客戶需求以及促銷等情況下的需求量劇增。如果日常成本有著大幅變動(dòng)，將使企業(yè)管理變得十分困難。而通過電子商務(wù)的物流信息化，系統(tǒng)能夠掌握每天的客戶需求情況；通過對(duì)每天的需求進(jìn)行分析并制定合理的配送方案，進(jìn)而實(shí)現(xiàn)電商物流的彈性管理。本處將電商物流的彈性配送定義為系統(tǒng)緩解小擾動(dòng)以及大干擾之后的恢復(fù)能力，即適應(yīng)性和敏捷性。

適應(yīng)性是系統(tǒng)對(duì)干擾的響應(yīng)能力[19]，表現(xiàn)為配送過程隨著客戶需求的變動(dòng)及時(shí)調(diào)整以滿足客戶需求的靈活性。由于電商中消費(fèi)需求的產(chǎn)生是一個(gè)動(dòng)態(tài)的過程，因此每天的物流配送必然也是一個(gè)動(dòng)態(tài)的過程，需要根據(jù)客戶的需求采取合理的配送措施，在節(jié)約成本的同時(shí)使系統(tǒng)每天處于一個(gè)較穩(wěn)定的狀態(tài)，表現(xiàn)為系統(tǒng)的適應(yīng)性。

敏捷性是系統(tǒng)面對(duì)大擾動(dòng)時(shí)恢復(fù)到較穩(wěn)定狀態(tài)的能力。當(dāng)?shù)昙掖蟠黉N導(dǎo)致訂單生成量劇增進(jìn)而產(chǎn)生大量客戶需求時(shí)，配送中心往往無法在當(dāng)天完成任務(wù)從而導(dǎo)致配送延遲以及快件積壓，而快件積壓的影響將在之后的配送過程逐漸消除，表現(xiàn)為系統(tǒng)的恢復(fù)能力，即敏捷性。

2模型建立

對(duì)于電商物流配送而言，在保證服務(wù)質(zhì)量的同時(shí)，降低物流配送成本才能獲得更大的競(jìng)爭(zhēng)優(yōu)勢(shì)。電商物流配送的彈性配送核心是一個(gè)復(fù)雜的、多目標(biāo)、多約束的優(yōu)化問題，模型中存在客戶數(shù)量、客戶分布、車輛運(yùn)載能力、員工工作時(shí)間、成本構(gòu)成等復(fù)雜因素的約束。根據(jù)電商物流配送的特點(diǎn)，為了方便模型的建立，作如下假設(shè)：1) 城市中所有可能產(chǎn)生需求的客戶是均勻分布的，某一個(gè)區(qū)域的客戶分布用一個(gè)m×n的點(diǎn)陣表示；2) 任意兩個(gè)客戶之間是可以到達(dá)的，它們之間的距離是歐氏距離；3) 所有車輛的型號(hào)都相同；4) 只考慮單一區(qū)域中一個(gè)配送中心的情況。

2.1配送中心的選取

在代表區(qū)域客戶的m×n點(diǎn)陣中，其中每個(gè)點(diǎn)代表一個(gè)可能購買的客戶，客戶i在點(diǎn)陣中的坐標(biāo)(xi，yi)即代表客戶的位置。由于顧客需求隨機(jī)性大的特點(diǎn)，配送中心可以依據(jù)需求的歷史數(shù)據(jù)，獲取每個(gè)節(jié)點(diǎn)平時(shí)產(chǎn)生需求的概率pi，然后以pi為權(quán)值采用重心法[20]選址，則配送中心的坐標(biāo)為：

(1)

這樣在面對(duì)個(gè)體隨機(jī)的客戶需求時(shí)，可以使總體的需求分布期望相對(duì)于配送中心處于一個(gè)較均衡的狀態(tài)，能夠增加配送過程對(duì)不同客戶需求的適應(yīng)性。

2.2配送過程及成本計(jì)算

模型實(shí)際配送的過程如下：1) 依據(jù)客戶購買幾率pi，隨機(jī)生成客戶需求；2) 配送中心依據(jù)產(chǎn)生的需求信息，尋找最優(yōu)配送路徑；3) 車輛對(duì)其下對(duì)需要配送的節(jié)點(diǎn)實(shí)施配送。

模型的約束來自于客戶以及車輛的約束，具體描述如下。

2)每個(gè)配送車輛一次行駛的最大距離為L(zhǎng)M，從而每條配送路徑長(zhǎng)度不超過LM。

在普通車輛路徑問題[21]的基礎(chǔ)上，針對(duì)客戶需求數(shù)量不確定的特點(diǎn)，以人均成本作為優(yōu)化目標(biāo)函數(shù)。當(dāng)總共有s名客戶產(chǎn)生需求時(shí)候，整個(gè)配送過程的成本由4個(gè)部分組成：車輛行駛油費(fèi)，人工費(fèi)，延遲庫存成本，延遲造成客戶不滿意度的額外成本。具體如下。

1)每公里的運(yùn)輸成本為a，總的運(yùn)輸長(zhǎng)度為l，那么運(yùn)輸成本z1=a×l。

2)初始每輛車的成本為b1，初始的車數(shù)目為nv1，額外添加的每輛車的成本為b2，額外添加的車輛數(shù)目為nv2，那么車輛的成本為z2=b1×nv1+b2×nv2。

3)每天未完成配送的客戶數(shù)量為s1，每個(gè)客戶由于延遲一天的不滿意度產(chǎn)生的額外成本為c1，每個(gè)快件延遲的庫存產(chǎn)生的額外成本為c2，那么當(dāng)天由于延遲產(chǎn)生的額外成本為

z3=(c1+c2)×s1。

當(dāng)天實(shí)際配送的人均成本為

ZAi= (z1+z2+z3)/s。

(2)

2.3彈性評(píng)估

上文中提到的彈性主要由適應(yīng)性以及敏捷性構(gòu)成。由于配送過程的不確定性，模型的彈性以每天人均成本相對(duì)于歷史人均成本的波動(dòng)進(jìn)行評(píng)估。假設(shè)總共有day天的成本數(shù)據(jù)，依次為{ZA1, ZA2，…，ZAi，…，ZAday-1, ZAday}，則第j天的成本波動(dòng)系數(shù)

(3)

如果在當(dāng)天發(fā)生了很大的擾動(dòng)，則當(dāng)天的wav會(huì)變得很大，并且在后面的dy天的時(shí)間逐漸恢復(fù)到正常水平。定義第j天的恢復(fù)系數(shù)

(4)

適應(yīng)性為配送過程隨著客戶需求的變動(dòng)及時(shí)調(diào)整以滿足客戶需求的靈活性，以wav值的大小作為衡量指標(biāo)。如果每天的wav越小，表示系統(tǒng)的適應(yīng)性越強(qiáng)，在不同客戶需求下表現(xiàn)出良好的穩(wěn)定性；wav越大，表明系統(tǒng)適應(yīng)性越弱，配送成本容易受到客戶需求的影響。

敏捷性是系統(tǒng)面對(duì)大擾動(dòng)時(shí)恢復(fù)到較穩(wěn)定狀態(tài)的能力，以rec的大小，以及恢復(fù)到正常的天數(shù)dy作為衡量指標(biāo)。如果dy以及rec的值越小，表明系統(tǒng)在干擾之后能夠很快地恢復(fù)正常運(yùn)作，即敏捷性越強(qiáng)；dy以及rec越大，表明系統(tǒng)恢復(fù)時(shí)間越長(zhǎng)，即敏捷性越弱。

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

3.1極值動(dòng)力學(xué)與自組織臨界

自組織臨界狀態(tài)是由Bak等人于1987年首次提出來的概念, 用于說明控制廣延耗散動(dòng)力系統(tǒng)的普遍組織原則。在自組織臨界模型中, 最值得關(guān)注的是1993年Bak等[22]提出的Bak-Sneppen生物演化模型(下文簡(jiǎn)稱BS模型)。在BS模型的生態(tài)系統(tǒng)中, 不同個(gè)體間相互關(guān)聯(lián), 個(gè)體的變異會(huì)影響鄰近其他個(gè)體的狀態(tài)。其突出的特點(diǎn)為非平衡性(準(zhǔn)平衡性), 不會(huì)收斂到一個(gè)平衡態(tài), 而出現(xiàn)斷續(xù)平衡, 產(chǎn)生的波動(dòng)性使算法具有更好的持續(xù)搜索和跳出局部最優(yōu)解的能力。

極值優(yōu)化算法的基本思想是通過不斷以新的隨機(jī)組元替換個(gè)體中的最差組元, 最終使整個(gè)系統(tǒng)演化到一個(gè)臨界狀態(tài)。此過程中, 所有的組元都能協(xié)同進(jìn)化, 個(gè)體的構(gòu)造不斷得到改善, 最終可以找到近似最優(yōu)解或最優(yōu)解, 達(dá)到尋優(yōu)的目的[23]。它不需要調(diào)整參數(shù), 易于實(shí)現(xiàn), 計(jì)算量小, 算法效果好, 因此得到了廣泛的應(yīng)用。

3.2改進(jìn)算法原理

蟻群算法是一種由于受自然界生物的行為啟發(fā)而產(chǎn)生的“自然”算法。它是從對(duì)蟻群行為的研究中產(chǎn)生的,最初由Dorigo等[24-25]提出用于解決旅行商問題。由于蟻群算法是一種正反饋的自組織優(yōu)化算法，通過信息素的不斷累積尋找最優(yōu)解，因此相對(duì)而言容易陷入局部最優(yōu)解，而且可能使得更優(yōu)解由于信息素的累積過低而很難被再度選取；而極值優(yōu)化算法通過尋找最差個(gè)體及其領(lǐng)域優(yōu)化系統(tǒng)，是一種“去差”算法，擁有很強(qiáng)的局部搜索能力，并且由于優(yōu)化過程的隨機(jī)性，因而具有良好的跳出局部最優(yōu)解的能力。因此，通過極值優(yōu)化算法的局部搜索能力，配合蟻群算法的全局搜索能力，能使算法具有更強(qiáng)的跳出局部最優(yōu)解的能力，避免算法早熟、停滯，使算法的收斂效率大幅提高。

本文主要在路徑搜索以及信息素更新兩個(gè)方面，對(duì)蟻群算法進(jìn)行改進(jìn)，通過定義節(jié)點(diǎn)的局部適應(yīng)度在蟻群算法中引入極值優(yōu)化算法。對(duì)于客戶i，取其當(dāng)前所在路徑中的前向邊長(zhǎng)度為dif，后向邊長(zhǎng)度為dib，與它相連節(jié)點(diǎn)的最短距離為di1，次短距離為di2。定義該客戶的局部適應(yīng)度為

fi=dif+dib-di1-di2。

(5)

如果fi越小，表明該解更優(yōu)。在螞蟻搜索路徑之后，對(duì)其中適應(yīng)性最差的節(jié)點(diǎn)及其領(lǐng)域進(jìn)行優(yōu)化。由于解中的各條邊之間是強(qiáng)耦合的，因此改變一個(gè)節(jié)點(diǎn)的適應(yīng)度會(huì)影響到其他與他關(guān)聯(lián)的節(jié)點(diǎn)的適應(yīng)度，即實(shí)現(xiàn)極值優(yōu)化算法的過程。而且在該網(wǎng)絡(luò)結(jié)構(gòu)中,任意兩個(gè)節(jié)點(diǎn)是可達(dá)的, 即可以通過有限步的鄰域操作從一個(gè)可行解搜索到另一個(gè)可行解[26]。因此通過鄰域搜索不斷改變具有較高局部適應(yīng)度的節(jié)點(diǎn)的狀態(tài),使優(yōu)化系統(tǒng)逐步達(dá)到自組織臨界狀態(tài)。

此外，信息素更新策略是蟻群算法的關(guān)鍵步驟之一，信息素的更新方案直接影響了蟻群算法的求解速度以及解的好壞。因此，本文在蟻群算法的信息素更新時(shí)，也加入局部適應(yīng)度的影響。對(duì)于解中的路徑i→i′，第u次循環(huán)更新規(guī)則如下：

τii′(u+1)=ρ·τii′(u)+(1-ρ)·Δτii′(u+1),

(6)

Δτii′(u+1)=(fi+1)-θ。

(7)

其中τii’表示路徑上的信息素濃度，ρ為信息素殘留系數(shù)，Δτii’為每次的信息素增量，θ為信息素增量與局部適應(yīng)度的指數(shù)關(guān)系。

3.3算法實(shí)現(xiàn)

依據(jù)以上特點(diǎn)，本文構(gòu)建算法的具體實(shí)施步驟如下。

1)配送中心的選址以及客戶需求的產(chǎn)生。

在一個(gè)20×20的點(diǎn)陣模型中，根據(jù)每個(gè)節(jié)點(diǎn)的購買概率p以及重心法選擇配送中心，每個(gè)點(diǎn)依據(jù)購買的概率p隨機(jī)選擇是否購買。

2)螞蟻尋找路徑。

依據(jù)基本的蟻群算法，用螞蟻代替車輛對(duì)客戶點(diǎn)進(jìn)行配送，螞蟻在i客戶點(diǎn)選擇服務(wù)的下一個(gè)客戶點(diǎn)i′ 時(shí)，主要考慮2個(gè)因素：1)i，i′ 兩顧客點(diǎn)之間的親密程度，稱為可見度，記為ηii’，其中：ηii’=dii’；2)由迄今完成的循環(huán)所得路徑方案體現(xiàn)出來的由i到i′ 的可行性，即信息素濃度τii’。在第u次循環(huán)時(shí)候，螞蟻h由客戶點(diǎn)i轉(zhuǎn)移到客戶點(diǎn)i′ 的概率：

(8)

其中nh表示螞蟻當(dāng)前尚未經(jīng)過的路徑，α、β作為信息素濃度與可見度的指數(shù)，表明了在轉(zhuǎn)移過程中它們的相對(duì)重要程度。當(dāng)下一個(gè)要服務(wù)的客戶點(diǎn)會(huì)使運(yùn)載總量超出汽車載重量，或者使運(yùn)距超過一次最大行駛距離LM時(shí)，就返回到配送中心。螞蟻代表下一輛車出發(fā)，直到遍歷所有的客戶節(jié)點(diǎn)。

3)路徑極值優(yōu)化。

計(jì)算螞蟻路徑中每個(gè)客戶的局部適應(yīng)度。并將局部適應(yīng)度由大到小排序?yàn)殚L(zhǎng)度為list_len的序列List，則適應(yīng)度最大的客戶為該序列中的第1個(gè)元素, 而適應(yīng)度最小的客戶為該序列中的第list_len個(gè)元素。對(duì)于List中的第r個(gè)元素，根據(jù)文獻(xiàn)[27]的結(jié)果，它被選中的概率p’(r) ∝r-3時(shí)候，系統(tǒng)能取得最優(yōu)解。因此，定義第r個(gè)元素被選中的概率為

(9)

采用輪盤法選擇客戶Customer_n，對(duì)Customer_n實(shí)施2-opt優(yōu)化，該領(lǐng)域定義策略會(huì)產(chǎn)生list_len-1個(gè)解，選擇最小的結(jié)果作為當(dāng)前最優(yōu)路徑。

4)更新信息素。

當(dāng)一次循環(huán)結(jié)束后，螞蟻遍歷了所有客戶點(diǎn)，完成一次配送。當(dāng)所有螞蟻完成一次循環(huán)后，根據(jù)各螞蟻遍歷結(jié)果的好壞(目標(biāo)函數(shù)值)，計(jì)算信息素增量，更新相關(guān)路徑上的信息素。

5)重復(fù)2)～4)，直到滿足算法的終止條件，輸出最優(yōu)解。

3.4算法分析

基于極值動(dòng)力學(xué)的改進(jìn)蟻群算法以當(dāng)前路徑與最小路徑的距離差定義局部適應(yīng)度，能更直接地反映該節(jié)點(diǎn)路徑的優(yōu)劣性，局部適應(yīng)度值越大表明解越劣；搜索之后的信息素更新過程中，對(duì)于局部適應(yīng)度越小的點(diǎn)，信息素的增量越大，表明系統(tǒng)對(duì)優(yōu)解的保留性更強(qiáng)。此外，搜索過程中在全局上依據(jù)信息素搜索下一個(gè)節(jié)點(diǎn)，同時(shí)局部上依據(jù)局部適應(yīng)度對(duì)適應(yīng)度較差的節(jié)點(diǎn)進(jìn)行極值優(yōu)化，實(shí)現(xiàn)全局與局部、尋優(yōu)與棄差的搜索相結(jié)合，大幅提高算法的收斂效率。同時(shí)由于模型的配送中心是基于客戶的購買幾率采取重心法選址，并且客戶的基數(shù)足夠大，因此配送中心總是處于客戶需求的期望中心從而使需求相對(duì)于配送中心的分布呈現(xiàn)一定的穩(wěn)定性。采取人均成本最小化作為目標(biāo)函數(shù)，可使系統(tǒng)在面對(duì)客戶數(shù)量變化時(shí)，最終優(yōu)化結(jié)果能表現(xiàn)出很好的穩(wěn)定性。因此算法在面對(duì)不同的客戶需求進(jìn)行求解時(shí)候能表現(xiàn)出良好的彈性。

4算例分析

在快遞配送的最后一公里，通常是每個(gè)區(qū)域以一個(gè)配送中心負(fù)責(zé)該區(qū)域的客戶需求的配送。而且城市中某一個(gè)區(qū)域的客戶，是零散而且比較均勻地分布于其中。可以以一個(gè)m×n點(diǎn)陣模擬該區(qū)域的客戶分布，每個(gè)點(diǎn)代表了一個(gè)可能購買的客戶，相鄰兩點(diǎn)間的距離為1，任意兩點(diǎn)間的距離為歐式距離。然后每個(gè)客戶根據(jù)自身可能購買的幾率p，隨機(jī)選擇是否購買：沒有購買則無需實(shí)行配送，購買了則需要配送。依據(jù)上文模型，本處實(shí)例分析以Matlab為平臺(tái)，在20×20的點(diǎn)陣中模擬區(qū)域中的客戶分布，并對(duì)模擬進(jìn)行仿真。

4.1殘留系數(shù)對(duì)改進(jìn)算法的影響

在算法的搜索過程中，信息素殘留系數(shù)ρ對(duì)算法性能有著重要影響。ρ的值變大時(shí)，表明前次的信息素殘留越多，每次搜索完信息素的增量越少，會(huì)削弱全局搜索能力，算法容易停滯；當(dāng)ρ的值變小時(shí)，由于信息素殘留過小又會(huì)影響算法的收斂速度。為了驗(yàn)證ρ的取值對(duì)算法的影響，以num=99，循環(huán)次數(shù)Circ=200，ρ分別取0.4,0.6,0.8時(shí)，根據(jù)以往的蟻群實(shí)驗(yàn)對(duì)蟻群算法的初始數(shù)據(jù)設(shè)置如下：信息素濃度與可見度的指數(shù)分別為α=1，β=2，θ=1，車輛載貨上限QW=40，車輛一次行駛的最大距離LM=70。畫出優(yōu)化過程曲線如圖1所示。

圖1　ρ不同時(shí)的優(yōu)化過程曲線

如圖1所示，在曲線前半段，當(dāng)ρ的值越大時(shí)候，優(yōu)化過程曲線下降速度越快，表明算法具有更快的收斂速度；在曲線后半段，當(dāng)ρ的值越小時(shí)候，獲得的優(yōu)化結(jié)果越優(yōu)，表明算法的搜索能力越強(qiáng)。因此，綜合考慮收斂速度以及優(yōu)化結(jié)果，取ρ=0.7進(jìn)行之后的實(shí)驗(yàn)。

4.2算法比較

為了驗(yàn)證基于極值動(dòng)力學(xué)的改進(jìn)蟻群算法的有效性以及優(yōu)勢(shì)，分別采用傳統(tǒng)蟻群算法和本文算法，對(duì)電商物流配送問題進(jìn)行求解。首先依據(jù)初始的客戶購買幾率p，選擇配送中心，并生成客戶需求。為比較兩種算法的特性，隨機(jī)生成5天的客戶分布如圖2，依次表示num=96,99,93,95,89時(shí)的客戶分布。

對(duì)蟻群算法的初始數(shù)據(jù)設(shè)置如下：信息素殘留系數(shù)ρ=0.7，信息素濃度與可見度的指數(shù)分別為α=1，β=2，車輛載貨上限QW=40，車輛一次行駛的最大距離LM=70。循環(huán)次數(shù)Circ=500時(shí)，得出實(shí)驗(yàn)結(jié)果如表1所示。表1中的優(yōu)化曲線a、b、c、d、e分別見圖3的5個(gè)小圖。

圖2　客戶需求分布

客戶需求數(shù)優(yōu)化曲線優(yōu)化時(shí)間優(yōu)化結(jié)果原算法改進(jìn)算法原算法改進(jìn)算法96a131.685150.931222.57196.96799b135.423155.142213.434196.81993c111.66138.381222.918185.59495d124.964147.054203.328200.37989e106.608127.119229.022188.377

為方便觀測(cè)，依次畫出這5天前200次循環(huán)的優(yōu)化過程曲線如圖3所示。

圖3　兩種算法的優(yōu)化過程曲線

如圖3曲線所示，相對(duì)于傳統(tǒng)蟻群算法，改進(jìn)蟻群算法曲線的收斂速度更快、更平滑，表明改進(jìn)后的算法收斂更快，尋優(yōu)能力更強(qiáng)。根據(jù)表1以及圖3的結(jié)果，雖然引入極值優(yōu)化后，由于算法運(yùn)算量變大增加了一定的計(jì)算時(shí)間，但是總體的優(yōu)化速率與優(yōu)化結(jié)果都得到了大幅提升，總體而言大幅提升了算法的求解效率與精度。

以num=99為例，分別畫出Circ=500時(shí)，兩種算法最終生成的路徑如圖4，圖5。

如圖4、5可見，在同樣的搜索過程以后，基于極值動(dòng)力學(xué)的改進(jìn)蟻群算法結(jié)果更平滑，而蟻群算法中的路徑明顯存在可以繼續(xù)優(yōu)化的邊角部分。綜合以上實(shí)驗(yàn)結(jié)果，在引入極值優(yōu)化后，在優(yōu)化過程中能針對(duì)蟻群算法尋得路徑中較差的部分進(jìn)行優(yōu)化，相當(dāng)于給蟻群尋找路徑時(shí)候增添了尋優(yōu)指引，同時(shí)能夠避免蟻群尋優(yōu)時(shí)候，某些更優(yōu)路徑由于信息素太少而很難再被選取，從而導(dǎo)致算法陷入局部最優(yōu)解。因此，改進(jìn)后的算法擁有更好的搜索能力與收斂速度，可以更快地求得最優(yōu)解。

圖4　蟻群算法路徑

圖5　改進(jìn)算法路徑

4.3彈性驗(yàn)證

為了驗(yàn)證彈性配送策略在不同客戶需求情況下具有良好的適應(yīng)性以及敏捷性，以人均成本作為目標(biāo)函數(shù)對(duì)系統(tǒng)的不同狀態(tài)進(jìn)行仿真求解。

依據(jù)上部分的案例，如圖2可見，每天的客戶需求分布零散多變，但是總體的需求數(shù)量波動(dòng)較小。分別采用彈性管理策略對(duì)這5個(gè)不同的需求求解得到的結(jié)果如表2所示。

表2　5天的運(yùn)行結(jié)果

由表2可見，雖然每天的客戶分布完全隨機(jī)，但是最終的配送路徑的長(zhǎng)度都在195±10的范圍內(nèi)，而且每天客戶的人均成本也均在一個(gè)小范圍內(nèi)波動(dòng)。

做出每天的人均成本與5天的平均成本曲線如圖6，以及人均成本波動(dòng)系數(shù)wav的曲線如圖7所示。

圖6　人均成本曲線

圖7　人均成本波動(dòng)系數(shù)wav曲線

如圖6、7所示，在5天的配送過程中，每天的人均成本在小于4%的范圍內(nèi)波動(dòng)，表明在面對(duì)不確定的客戶需求時(shí)，系統(tǒng)表現(xiàn)出良好的適應(yīng)性。證明了采用基于購買幾率的重心法選址以及人均成本作為目標(biāo)函數(shù)構(gòu)建模型時(shí)，有效地降低每天需求變化的擾動(dòng)，從而提升系統(tǒng)適應(yīng)性。

如果在第1天的時(shí)候商家舉行了大促活動(dòng)，那么第1天的客戶需求量會(huì)劇增。假定客戶購買幾率變?yōu)槠綍r(shí)的3倍，模型隨機(jī)生成了267名客戶需求。此時(shí)最大化當(dāng)天配送額能造成最少的庫存積壓以及客戶不滿意度。假定單位庫存以及客戶不滿意度的成本為CE，運(yùn)行模型得到的配送結(jié)果如表3所示。

表3　大擾動(dòng)后5天的運(yùn)行結(jié)果

由于CE是個(gè)不確定參數(shù)，畫出CE在1～3之間，每隔0.2取一個(gè)值，模型求得的人均成本及wav的曲線如圖8、圖9所示。圖8、圖9中，由下至上的曲線分別表示CE=1.2,1.4,1.6,1.8,2.0,2.2,2.4,2.6,2.8,3.0時(shí)的結(jié)果。

如圖8所示曲線畫出了正常運(yùn)行情況下的歷史均值，以及CE取不同值時(shí)的成本曲線。分別求出CE取不同值時(shí)候，第1天的rec的值如表4所示。

圖8　人均成本曲線

因?yàn)槟Ｐ投荚诘?天緩解了系統(tǒng)的擾動(dòng)，因此rec的大小就反映了系統(tǒng)的彈性，其中rec越小，表明恢復(fù)越快?？梢?，當(dāng)客戶需求量劇增時(shí)，通過合理的調(diào)度使系統(tǒng)維持每天效率最大化，wav都能很快恢復(fù)到正常水平，尤其在CE較小時(shí)候。當(dāng)CE逐漸變大時(shí)，系統(tǒng)的恢復(fù)速度逐漸變慢，基本在0.5左右，表明系統(tǒng)前一天的恢復(fù)速度是后一天的2倍，依然能很快在前期緩解系統(tǒng)的大干擾。因此系統(tǒng)在面臨劇增的客戶需求時(shí)，也能表現(xiàn)出很好的敏捷性。

5結(jié)論

本文在車輛路徑問題的基礎(chǔ)上，分析電商物流配送與傳統(tǒng)車輛路徑問題的區(qū)別，并以此建立了模型。針對(duì)客戶需求空間不確定的特點(diǎn)，對(duì)配送中心提出以客戶歷史購買幾率為權(quán)值的重心法選址，使需求相對(duì)于配送中心分布的期望較為穩(wěn)定；針對(duì)客戶需求數(shù)量不確定的特點(diǎn)，以客戶的人均成本作為優(yōu)化的目標(biāo)函數(shù)，緩解每天需求數(shù)量變化對(duì)目標(biāo)函數(shù)的影響。此外本文還設(shè)計(jì)了基于極值動(dòng)力學(xué)的改進(jìn)蟻群算法對(duì)模型進(jìn)行了仿真，通過實(shí)驗(yàn)驗(yàn)證了改進(jìn)算法在面對(duì)同樣的問題時(shí)擁有更好的搜索能力與收斂速度，可以更快的求得最優(yōu)解。最后本文通過對(duì)不確定性客戶需求問題的求解，驗(yàn)證了系統(tǒng)具有良好的適應(yīng)性以及敏捷性，即增強(qiáng)了電商末端物流配送的彈性。之后的工作將考慮多種電商物流模式結(jié)合的問題、帶時(shí)間窗以及指定配送的客戶需求問題。

表4　CE不同取值時(shí)候rec的值

參考文獻(xiàn)：

[1]2015年全國(guó)郵政管理工作會(huì)議——全國(guó)郵政管理系統(tǒng)黨風(fēng)廉政建設(shè)工作會(huì)議[EB/OL]. [2015-01-07]. http://www.spb.gov.cn/ztgz/gjyzjzt/2015nqgyzglgzhy/mtbd/201501/t20150107_406766.html.

[2]楊建功. 前臺(tái)物流和后臺(tái)物流——電商物流的再認(rèn)識(shí)[J]. 物流科技, 2013, 36(5): 3-5.

YANG Jiangong. Foreground and background logistics: new understanding of the e-commerce logistics [J]. Logistics Sci-Tech, 2013, 36(5): 3-5.

[3]李琳, 劉士新, 唐加福. B2C 環(huán)境下訂單配送問題的模型與算法[J]. 東北大學(xué)學(xué)報(bào) (自然科學(xué)版), 2009, 30(11): 1554-1557.

LI Lin, LIU Shixin, TANG Jiafu. Model and algorithm for distribution/ delivery of goods on order in B2C ecommerce[J]. Journal of Northeastern University (Natural Science), 2009, 30(11): 1554-1557.

[4]趙道致, 張強(qiáng). BAB: 電子商務(wù)中介型 B2B 發(fā)展的新方向[J]. 工業(yè)工程, 2007, 10(3): 1-5.

ZHAO Daozhi，ZHANG Qiang. BAB：the new development direction of intermediary B2B belonging to e-commerce [J]. Industrial Engineering Journal, 2007, 10(3): 1-5.

[5]DANTZIG G B, RAMSER J H. The truck dispatching problem [J]. Management science, 1959, 6(1): 80-91.

[6]BALL M O, MAGNANTI T L, MONMA C L, et al. Handbook in operations research and management science//Vol. 8: Network Routing [M]. Amsterdam: Elsevier Science, 1995:410-410.

[7]PAOLO Toth, DANIELE Vigo. The vehicle routing problem[M].Philadelphia, USA: Society for Industrial and Applied Mathematics, 2002.

[8]郭耀煌, 李軍. 車輛優(yōu)化調(diào)度問題的研究現(xiàn)狀評(píng)述[J]. 西南交通大學(xué)學(xué)報(bào), 1995, 30(4): 376-382.

GUO Yaohuang, LI Jun. Review of the state of the art on vehicle scheduling problem [J]. Journal of Southwest Jiaotong University, 1995, 30(4): 376-382.

[9]馮輝宗, 陳勇, 劉飛. 基于遺傳算法的配送車輛優(yōu)化調(diào)度[J]. 重慶郵電學(xué)院學(xué)報(bào)(自然科學(xué)版), 2005, 17(1): 93-96.

FENG Huizong，CHEN Yong，LIU Fei. Optimized scheduling of vehicles distributing with genetic algorithm [J]. Journal of Chongqing University of Posts and Telecommunication(Natrual Science), 2005, 17(1): 93-96.

[10]劉小蘭, 郝志峰, 汪國(guó)強(qiáng), 等. 有時(shí)間窗的車輛路徑問題的近似算法研究[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2004, 10(7): 825-831.

LIU Xiaolan, HAO Zhifeng, WANG Guoqiang, et al. Improved large neighborhood search algorithm for vehicle routing problem with time windows [J]. Computer Integrated Manufacturing Systems, 2004, 10(7): 825-831.

[11]溫惠英, 孫博. 基于離散粒子群算法的協(xié)同車輛路徑問題[J]. 公路交通科技, 2011, 28(1): 149-153.

WEN Huiying, SUN Bo. Resolving collaborative vehicle route problem based of discrete panicle swarm optimization [J]. Journal of Highway and Transportation Research and Developmen, 2011, 28(1): 149-153.

[12]李妍峰, 高自友, 李軍. 基于實(shí)時(shí)交通信息的城市動(dòng)態(tài)網(wǎng)絡(luò)車輛路徑優(yōu)化問題[J]. 系統(tǒng)工程理論實(shí)踐, 2013, 33(7): 1813-1819.

LI Yanfeng, GAO Ziyou, LI Jun. Vehicle routing problem in dynamic urban network with real-time traffic information [J]. Systems Engineering Theory & Practice, 2013, 33(7): 1813-1819.

[13]楊聚平, 楊長(zhǎng)春, 姚宣霞. 電商物流中 “最后一公里” 問題研究[J]. 商業(yè)經(jīng)濟(jì)與管理, 2014 (4): 16-22.

YANG Juping，YANG Changchun，YAO Xuanxia. Research on the “l(fā)ast-mile” issue in the e-commerce logistics system [J]. Journal of Business Economics, 2014 (4): 16-22.

[14]張昕. 末端物流共同配送模式及決策路徑——基于電商物流和社區(qū)服務(wù)的供需分析[J]. 財(cái)經(jīng)問題研究, 2013 (3): 123-128.

ZHANG Xin. Joint distribution patterns and decision-making paths for terminal logistics: based on supply and demand analysis of electric business logistics and community service [J]. Research on Financial and Economic Issues, 2013 (3): 123-128.

[15]席運(yùn)江, 黨延忠, 廖開際. 組織知識(shí)系統(tǒng)的知識(shí)超網(wǎng)絡(luò)模型及應(yīng)用[J]. 管理科學(xué)學(xué)報(bào), 2009,12(3): 12-21.

XI Yunjiang, DANG Yanzhong, LIAO Kaiji. Knowledge supernetwork model and its application in organizational knowledge systems [J]. Journal of Management Sciences in China, 2009, 12(3): 12-21.

[16]黃建華, 黨延忠. 快遞超網(wǎng)絡(luò)模型及基于成本的優(yōu)化方法[J]. 系統(tǒng)管理學(xué)報(bào), 2010,19 (6): 689-695.

HUANG Jianhua, DANG Yanzhong. Express supernetwork model and the cost-based optimization method [J]. Journal of Systems&Management, 2010,19 (6): 689-695.

[17]HOLLING C S. Resilience and stability of ecological systems [J]. Annual review of Ecology and Systematics, 1973,4: 1-23.

[18]CHRISTOPHER M, PECK H. Building the resilient supply chain [J]. The International Journal of Logistics Management, 2004, 15(2): 1-14.

[19]GUNDERSON L H. Ecological resilience-in theory and application [J]. Annual Review of Ecology and Systematics, 2000,31(1): 425-439.

[20]苗興東，李映紅，范存軍．重心法選址探討[J]．交通標(biāo)準(zhǔn)化，2004(10)：50-52．

MIAO Xingdong, LI Yinghong, FAN Cunjan. A discussion on location selection by gravity method [J]. Communications Standardization, 2004(10)：50-52．

[21]劉明廣, 李高揚(yáng). 物流配送車輛優(yōu)化調(diào)度模型及其求解策略[J]. 工業(yè)工程, 2007, 10(2): 121-124.

LIU Mingguang, LI Gaoyang. Logistics delivery routing scheduling model and its solving strategies [J]. Industrial Engineering Journal, 2007, 10(2): 121-124.

[22]BAK P, SNEPPEN K. Punctuated equilibrium and criticality in a simple model of evolution [J]. Physical Review Letters, 1993, 71(24): 4083.

[23]齊潔, 汪定偉. 極值優(yōu)化算法綜述[J]. 控制與決策, 2007, 22(10): 1081-1085.

QI Jie, WANG Dingwei. Overview of extremal optimization algorithm [J]. Control and Decision, 2007, 22(10): 1081-1085.

[24]DORIGO Marco, GIANNI Di Caro. Ant algorithms for discrete optimization [J]. Artificial Life, 1999, 5 (3): 137-172.

[25]DORIGO M, GAMBARDELLA L M. Ant colonies for the travelling salesman problem [J]. BioSystems, 1997, 43(2): 73-81.

[26]吳婷, 陳玉旺, 汪燁. 基于極值動(dòng)力學(xué)的自組織優(yōu)化算法求解TSP 問題[J]. 控制理論與應(yīng)用, 2010, 27(6): 715-720.

WU Ting, CHEN Yuwang, WANG Ye. Self-organized optimization algorithm with extremal dynamics for the traveling salesman problem [J]. Control Theory & Applications, 2010, 27(6): 715-720.

[27]CHEN Y W, LU Y Z, CHEN P. Optimization with extremal dynamics for the traveling salesman problem [J]. Physica A: Statistical Mechanics and its Applications, 2007, 385(1): 115-123.

E-commerce Ending Logistics Resilient Distribution Strategy Research Based on the Extreme Optimization—Ant Colony Algorithm

RUAN Huan1, GENG Liang1,2, XIAO Renbin1

(1. School of Automation, Huazhong University of Science and Technology, Wuhan 430074, China;2. School of Science, Hubei University of Technology, Wuhan, Hubei 430068, China)

Abstract：A study is conducted into the process called the ending logistics in which goods are delivered to customers from the distribution center in e-commerce logistics distribution. To reduce distribution cost and improve service quality, the vehicle routing problem is combined with the characteristics of e-commerce consumers′ demand, namely “big varieties, small quantity, multiple batches and short cycle”. Based on the uncertainty in customer daily demand, the informatization resilience distribution strategy is put forward. A model with the target of minimizing the per capita cost is established along with an improved ant colony algorithm based on the extreme dynamics to optimize the logistics distribution path. The convergence efficiency of the algorithm has been largely improved through the “optimization” and “elimination” and by combining “global search” with “l(fā)ocal search”. Finally, an example is taken to verify the resilience of the algorithm faced with uncertainty demands. Effective distribution of e-commerce logistics can be achieved based on this research.

Key words：e-commerce ending logistics; extreme dynamics; ant colony algorithm; resilience distribution

中圖分類號(hào)：F272.3

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1007-7375(2016)01- 0051- 11

doi:10.3969/j.issn.1007- 7375.2016.01.008

作者簡(jiǎn)介：阮煥(1992-)，男，湖北省人，碩士研究生，主要研究方向?yàn)楣?yīng)鏈管理、決策分析.

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(71171089)

收稿日期：2015- 03- 17