基于改進型果蠅算法的聯運物流攬件調度仿真

黃繼梅，陳進強

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

1 引言

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

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

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

2 確立聯運物流攬件約束條件

攬件調度問題與多約束條件具有緊密關聯性。但約束條件通常較為復雜，這對調度模型的構建產生一定障礙，本文將最大程度給出和此問題具有較強相關性的約束條件。

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

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

2.1 單個攬件中心

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

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

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

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

(1)

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

決策變量[6]表示為

(2)

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

(3)

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

上述不同目標之間互相關聯影響，構建目標體系[7]，得出攬件中心的目標函數：

最短攬件時長

(4)

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

最少派出車輛

B=Min∑yk

(5)

最短攬件距離：

(6)

結合目標重要程度，設計約束條件優先級P1

P1A+P2B+P3C

(7)

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

(8)

(9)

(10)

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

2.2 多個攬件中心

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

(11)

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

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

(12)

(13)

(14)

3 基于改進型果蠅算法的聯運物流攬件調度

3.1 調度模型構建

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

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

因此，車輛從攬收中心出發到某一客戶處的調度策略描述為

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

(15)

因此，該攬件調度策略必須符合

(16)

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

(17)

(18)

綜上所述，結合xii=0，0≤i≤m得出

(20)

(21)

攬件調度模型為

(22)

3.2 基于果蠅算法的攬件調度模型求解

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

1)種群規模

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

但是在實際應用過程中，并非種群數量越大越好，當數量過大時，會損耗較多的系統內容，CPU的運行時間也更長。必須結合攬件調度模型的實際特點，經過大量實驗后，給出種群的合理數量，滿足搜索實時性要求。

2)果蠅初始位置

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

3)步進值

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

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

遞減搜索尋優步長的表達式如下

(23)

式中，L0代表原始步長，maxgen為最大迭代次數，g表示現階段迭代次數。

則計算自適應步長的公式如下

(24)

4)果蠅味道濃度

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

Si′=1/Disti′

(25)

為確保算法有效性，避免出現早熟問題[12]，本文利用有效因子α與避免局部最優因子β對傳統算法這一缺陷進行改進

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

(26)

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

(27)

經過上述改進后，利用改進型果蠅算法求解聯運物流攬件調度模型的全部過程如下：

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

(28)

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

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

smelli′=function(Si′)

(29)

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

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

(30)

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

(31)

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

4 仿真與結果分析

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

表1 不同方法的均方差計算結果表

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

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

圖1 本文方法攬件調度路線

圖2 文獻[1]方法攬件調度路線

圖3 文獻[2]方法攬件調度路線

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

5 結論

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