黃繼梅，陳進強

(1. 南昌航空大學科技學院，江西 九江 332020；2. 南昌大學共青學院，江西 九江 332020)

1 引言

隨著各類網(wǎng)絡(luò)應(yīng)用的普及，電子商務(wù)已經(jīng)成為促進經(jīng)濟增長的亮點。在此背景下，物流行業(yè)發(fā)展迅速，聯(lián)運物流作為運輸?shù)母呒壏绞剑C合了各類交通工具的優(yōu)勢，并將其有機組合，確保成本最低的同時提高運輸效率。在聯(lián)運物流模式下，攬件作為首個環(huán)節(jié)，一定程度上決定貨物整體運輸效率。現(xiàn)階段，大多數(shù)快遞攬收利用固定的分區(qū)攬收形式，每個快遞員負責一個區(qū)域，且互不支援。若某攬件區(qū)域任務(wù)數(shù)量分配不均，會導(dǎo)致攬件員業(yè)務(wù)能力與業(yè)務(wù)量不匹配。因此攬件速度慢、距離長等問題就會越來越突出，尤其是在大型電商活動節(jié)期間，無法滿足快遞數(shù)量急劇增長的需求。隨著電子商務(wù)的不斷發(fā)展，客戶特征體現(xiàn)為小批量、多批次，在顧客需求復(fù)雜多變情況下，如何實現(xiàn)高效、靈活攬收是保證高效物流的關(guān)鍵。

為解決以上問題，應(yīng)毅[1]等人將地理信息系統(tǒng)技術(shù)與K近鄰算法(K-Nearest Neighbors，KNN)相結(jié)合，建立“最后一公里”配送的智能信息系統(tǒng)，在此系統(tǒng)中，利用加權(quán)KNN方法完成快遞員的實時攬件調(diào)度。馬軍平[2]等人提出基于服務(wù)時長與可選擇性的攬收車輛調(diào)度方法。在正負半軸分別提出Replan與ReOPT策略，綜合分析攬件時長等因素制定具體調(diào)度策略。

但以上方法在求解過程中無法實現(xiàn)快速收斂，所得結(jié)果也容易陷入局部最優(yōu)[3]。為解決這一問題，本文提出基于改進型果蠅算法的聯(lián)運物流攬件調(diào)度方法。通過改進果蠅算法對物流攬件調(diào)度模型進行求解，獲取最優(yōu)攬件路線。果蠅算法是模仿果蠅尋找食物的行為完成設(shè)計的，應(yīng)用過程簡單，搜索效率高，且參數(shù)能夠自由調(diào)節(jié)。通過不斷迭代操作[4]，獲得問題最優(yōu)解。為進一步提高尋優(yōu)精度，本文對該算法進行改進，對種群規(guī)模、初始位置與迭代步長的合理設(shè)置，提高搜索能力，避免陷入局部最優(yōu)。

2 確立聯(lián)運物流攬件約束條件

攬件調(diào)度問題與多約束條件具有緊密關(guān)聯(lián)性。但約束條件通常較為復(fù)雜，這對調(diào)度模型的構(gòu)建產(chǎn)生一定障礙，本文將最大程度給出和此問題具有較強相關(guān)性的約束條件。

車輛約束[5]：任意一攬件車輛在重量與體積方面均有固定限制；每輛車都會受到攬件時間限制；車輛均有維修期等閑置時期；不同車輛類型滿足不同貨物需求；

顧客約束：顧客的攬件需求包括數(shù)量與種類；顧客對于攬件具有時間要求，也是提高顧客滿意度的關(guān)鍵，是互利的，必須最大程度滿足；分析顧客的優(yōu)先級，便于企業(yè)發(fā)展，增強顧客信任度；

2.1 單個攬件中心

在建立約束模型之前，給出如下假設(shè)：

1)攬件中心全部車輛類型相同，且載重量相同；

2)計算攬件中心和用戶節(jié)點、兩個用戶節(jié)點之間的距離。

若用戶i與j的坐標分別表示為(Xi，Yi)與(Xj，Yj)，則兩點之間的距離計算公式為

(1)

式中，u為距離系數(shù)，也是兩個用戶具有的真實距離和理想距離之間的系數(shù)。

決策變量[6]表示為

(2)

式中，K代表攬件車數(shù)量，i，j=0，1，2，3，…，N，k=0，1，2，3，…，K-1。

(3)

攬件系統(tǒng)的目標體系分為：根據(jù)用戶規(guī)定的時間準時完成攬件任務(wù)，且減少車輛等待時長；合理規(guī)劃攬件路線，降低總成本，保證車輛指派數(shù)量最少。

上述不同目標之間互相關(guān)聯(lián)影響，構(gòu)建目標體系[7]，得出攬件中心的目標函數(shù)：

最短攬件時長

(4)

式中，ei表示客戶i給出的最早攬件時間，ti為車輛在用戶i處起始攬件時間。

最少派出車輛

B=Min∑yk

(5)

最短攬件距離：

(6)

結(jié)合目標重要程度，設(shè)計約束條件優(yōu)先級P1

P1A+P2B+P3C

(7)

確立單攬件中心與多顧客情況下的約束模型

(8)

(9)

(10)

式中，N為用戶總數(shù)量，h描述攬件中心。

2.2 多個攬件中心

若該地區(qū)由多個攬件中心負責攬件，則將其轉(zhuǎn)換為單攬件中心問題處理，從而確定攬件中心的服務(wù)任務(wù)。假設(shè)H表示攬件中心數(shù)量，Vh表示第h個攬件中心h=0，1，2，…，H-1，各中心具備的車輛數(shù)量表示為a0，a1，a2，…，aH-1。則目標函數(shù)如下

(11)

式中，Ah、Bh與Ch分別代表第h個攬件中心完成此次任務(wù)所有的最短時間、最少車輛以及最短距離。

與單攬件中心利用的決策變量相同，針對任意一個攬件中心h∈[0，H-1]的路徑約束模型為

(12)

(13)

(14)

3 基于改進型果蠅算法的聯(lián)運物流攬件調(diào)度

3.1 調(diào)度模型構(gòu)建

假設(shè)各攬件中心與用戶位置一致，某車輛從中心出發(fā)到用戶所在處執(zhí)行攬件任務(wù)后再回到攬件中心，如何合理安全調(diào)度路線，并將攬件成本降到最低，是調(diào)度模型的關(guān)鍵應(yīng)用要求。在上述約束條件作用下，將攬件距離最短設(shè)定為最終目標，構(gòu)建攬件調(diào)度模型，再通過果蠅算法對該模型求解，獲取最優(yōu)調(diào)度路線。

假設(shè)存在m+1個攬件點，xij代表取值為0或1的決策變量，若攬件車輛從客戶i處能直接到達客戶j處，此時xij=1，反之xij=0。若i與j之間不能實現(xiàn)直接通行，則dij=∞。

因此，車輛從攬收中心出發(fā)到某一客戶處的調(diào)度策略描述為

X′=(xij)(m+1)×(m+1)

(15)

因此，該攬件調(diào)度策略必須符合

(16)

但是，由于車輛必須經(jīng)過所有攬收點后再返回攬收中心，故有

(17)

(18)

綜上所述，結(jié)合xii=0，0≤i≤m得出

(20)

(21)

攬件調(diào)度模型為

(22)

3.2 基于果蠅算法的攬件調(diào)度模型求解

傳統(tǒng)的果蠅算法作為尋優(yōu)方法同樣具有一定缺陷。當利用其協(xié)作與共享機制求解最優(yōu)算法時，一般具備較強的全局搜索能力，但是攬件調(diào)度模型屬于較為復(fù)雜的模型，若直接利用此算法會導(dǎo)致后期搜索效率下降。因此必須從下述幾方面進行改進。

1)種群規(guī)模

果蠅種群大小會直接影響其搜索能力，規(guī)模越大，尋找食物的時間也越短。此外種群大小也影響尋優(yōu)質(zhì)量，當種群規(guī)模大時，果蠅行進速度加快，收斂精度[8]提高。

但是在實際應(yīng)用過程中，并非種群數(shù)量越大越好，當數(shù)量過大時，會損耗較多的系統(tǒng)內(nèi)容，CPU的運行時間也更長。必須結(jié)合攬件調(diào)度模型的實際特點，經(jīng)過大量實驗后，給出種群的合理數(shù)量，滿足搜索實時性要求。

2)果蠅初始位置

初始位置越合理，算法收斂速度越快，表明在較短時間內(nèi)可以獲取最優(yōu)值。而初始位置與理想位置距離越大，算法效率也低，易出現(xiàn)局部最小情況。傳統(tǒng)的果蠅算法中初始位置的確定是通過隨機搜索方式完成，為改進這一缺陷，本文縮短了初始位置與最優(yōu)值的距離[9]，以優(yōu)化算法性能。

3)步進值

步進值，又稱作尋優(yōu)步長，是指果蠅利用其嗅覺優(yōu)勢將搜索步長為單位，完成搜索與尋優(yōu)。若果蠅數(shù)量確定，步長越大，尋優(yōu)范圍也越廣，改善全局尋優(yōu)性能，但局部搜索性能會降低；反之當步長過小，算法的全局尋優(yōu)能力會下降。

本文利用自適應(yīng)搜索尋優(yōu)步長[10]的方式，使全局與局部搜索能力達到平衡[11]，改善算法的整體性能。詳細做法如下：

遞減搜索尋優(yōu)步長的表達式如下

(23)

式中，L0代表原始步長，maxgen為最大迭代次數(shù)，g表示現(xiàn)階段迭代次數(shù)。

則計算自適應(yīng)步長的公式如下

(24)

4)果蠅味道濃度

在傳統(tǒng)果蠅算法中，種群在較大范圍內(nèi)任意分布，因此個體與原點之間的距離Disti′值也會越大，結(jié)合下述味道濃度表達式能夠得出，此時，味道濃度判定值Si′較小。因Si′值與0接近，則果蠅判斷函數(shù)Smelli′=function(Si′)的數(shù)值變化范圍過小，造成算法早熟。

Si′=1/Disti′

(25)

為確保算法有效性，避免出現(xiàn)早熟問題[12]，本文利用有效因子α與避免局部最優(yōu)因子β對傳統(tǒng)算法這一缺陷進行改進

Si′=1/(Disti′+α)+β

(26)

式中，α>0，而β則分為下述兩種情況

(27)

經(jīng)過上述改進后，利用改進型果蠅算法求解聯(lián)運物流攬件調(diào)度模型的全部過程如下：

第二步：嗅覺搜索，將原始迭代數(shù)設(shè)置為g=0，同時定義迭代時果蠅在尋找食物過程中飛行方向與尋優(yōu)步長：

(28)

第三步：初步計算，因不能掌握食物的詳細方位，需得出個體與原點之間的距離Disti′，進而獲取味道濃度值Si′；

第四步：將濃度判斷值代入式(29)的判斷函數(shù)中，得出現(xiàn)階段所有果蠅的氣味濃度smelli′：

smelli′=function(Si′)

(29)

第五步：按照濃度值大小，確定種群中最優(yōu)個體

[bestSmell，bestindex]=min/max(smelli)

(30)

第六步：視覺定位，對最優(yōu)濃度值與最佳個體坐標進行記錄。此時，果蠅群體將通過視覺定位飛向最佳個體方位

(31)

第七步：迭代尋優(yōu)，判定是否滿足停止條件g=maxgen。若g

4 仿真與結(jié)果分析

為證明所提方法的優(yōu)越性，在仿真環(huán)境為Windows7/CPU3.8GHz/VC++下與文獻[1]方法、文獻[2]方法進行對比實驗。為降低隨機因素對上述算法性能測試產(chǎn)生影響，將最大迭代次數(shù)設(shè)置為500。首先在攬件點數(shù)量不斷增長情況下，結(jié)合各方法目標函數(shù)獲得的最大值、最小值與均值對均方差進行計算，結(jié)果如表1所示。

表1 不同方法的均方差計算結(jié)果表

由表1可知，在攬件點數(shù)量較小時，三種算法的均方差沒有出現(xiàn)明顯區(qū)別。但隨著攬件點數(shù)的增長，文獻[1]方法與文獻[2]方法的均方差大幅度變大，而所提方法的均方差較為穩(wěn)定，表明該方法搜索過程較為穩(wěn)定。這是因為本文通過對果蠅算法的改進，設(shè)置合理的迭代步長，使搜索過程更加平穩(wěn)，避免陷入局部最優(yōu)。

為進一步驗證所提方法的應(yīng)用優(yōu)勢，將三種方法進行實踐，實驗的攬件地址與數(shù)量完全相同，利用不同方法給出的最優(yōu)策略進行攬件調(diào)度，不同方法調(diào)度路線分別如圖1～圖3所示，圖中星型表示顧客攬件位置。

圖1 本文方法攬件調(diào)度路線

圖2 文獻[1]方法攬件調(diào)度路線

圖3 文獻[2]方法攬件調(diào)度路線

由圖1～圖3提供的路線圖可知，傳統(tǒng)方法在滿足所有攬件需求時，出現(xiàn)路線重復(fù)問題，工作效率偏低，且顧客等待時間較長，降低了滿意度。相比之下，本文方法能夠規(guī)劃出更加合理的調(diào)度路線，驗證了所提方法理想的應(yīng)用性能。

5 結(jié)論

為提高物流攬件工作效率，本文利用改進型果蠅算法實現(xiàn)聯(lián)運物流攬件調(diào)度。仿真結(jié)果證明，該方法搜索效果穩(wěn)定，能夠獲得合理的調(diào)度路線，節(jié)省了人力資源與運輸成本，適用于業(yè)務(wù)量較多地區(qū)，為今后電商的自動化調(diào)度提供可靠依據(jù)。但是在研究攬收調(diào)度策略的同時，也應(yīng)不斷改進攬件工作模式，提高業(yè)務(wù)能力，使其能夠支撐電商行業(yè)的快速發(fā)展。