基于改進(jìn)型果蠅算法的聯(lián)運(yùn)物流攬件調(diào)度仿真

黃繼梅，陳進(jìn)強(qiáng)

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

1 引言

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

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

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

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

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

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

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

2.1 單個(gè)攬件中心

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

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

2)計(jì)算攬件中心和用戶節(jié)點(diǎn)、兩個(gè)用戶節(jié)點(diǎn)之間的距離。

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

(1)

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

決策變量[6]表示為

(2)

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

(3)

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

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

最短攬件時(shí)長(zhǎng)

(4)

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

最少派出車輛

B=Min∑yk

(5)

最短攬件距離：

(6)

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

P1A+P2B+P3C

(7)

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

(8)

(9)

(10)

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

2.2 多個(gè)攬件中心

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

(11)

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

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

(12)

(13)

(14)

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

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

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

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

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

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

(15)

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

(16)

但是，由于車輛必須經(jīng)過所有攬收點(diǎn)后再返回?cái)埵罩行?，故?/p>

(17)

(18)

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

(20)

(21)

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

(22)

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

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

1)種群規(guī)模

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

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

2)果蠅初始位置

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

3)步進(jìn)值

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

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

遞減搜索尋優(yōu)步長(zhǎng)的表達(dá)式如下

(23)

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

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

(24)

4)果蠅味道濃度

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

Si′=1/Disti′

(25)

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

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

(26)

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

(27)

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

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

(28)

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

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

smelli′=function(Si′)

(29)

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

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

(30)

第六步：視覺定位，對(duì)最優(yōu)濃度值與最佳個(gè)體坐標(biāo)進(jìn)行記錄。此時(shí)，果蠅群體將通過視覺定位飛向最佳個(gè)體方位

(31)

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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