基于兩階段啟發式算法的多目標外賣配送優化分析

徐肇元

(山西農業大學 軟件學院，山西 太谷 030800)

0 引 言

隨著人們生活水平的提高和互聯網的發展，新興的網絡訂餐模式——外賣由于其便捷性，越來越受到人們的認同.當前主流的銷售方法是通過O2O的形式，即顧客通過訂餐平臺下單，商家通過線下配送的方式送貨上門.外賣配送作為外賣的基礎業務，如何提高送餐效率，降低送餐成本是其重要的問題[1].在商家進行外賣配送的過程中，過早或過遲到達，顧客的時間滿意度都會受到影響[2].外賣配送線路優化問題被認為是一種準MDVRPTW(帶時間窗的多車場車輛路線問題).該問題需要同時滿足外賣配送和MDVRPTW的要求[3].其中VRP是由Dantzig和Ramser在1959年提出來的一種NP-hard問題[4]，是指基于一個或多個中心、汽車集和客戶集，在滿足約束條件的前提下使其線路最優的問題.現用來解決VRP的算法有遺傳算法[5]、蟻群算法[6]、粒子群算法[7]和節約算法[8]等.易彩玉[9]研究了如何使用聯合調度，以解決預約和即時兩種模式下的外賣生產配送的問題；王荃菲[10]對基于商家自營外賣配送服務和訂餐平臺配送服務的兩種不同的模型，設計了不同的配送路徑方案；陳萍[11]等人提出了一個適合餐飲O2O外賣配送的優化模型并利用一種改進的遺傳算法進行求解.本文對基于客戶時間滿意度和配送總成本的多目標外賣配送線路優化模型進行深入研究，以最大化客戶滿意度為主要目標為商家提供了線路規劃方案.

1 模型的建立

在模型建立之前先定義二進制決策變量：

1.1 問題假設

1)商家各門店擁有的外賣車數量足夠外賣配送員使用；

2)每輛外賣車型號相同，載重量是固定的；

3)每輛外賣車從商家的某門店出發，完成配送任務后回到該門店；

4)每輛外賣車保持勻速行駛，不受路況環境的影響；

5)每個外賣訂單僅被一個外賣配送員配送.

1.2 時間滿意度

每進行一次外賣配送，都會打開一次外賣配送箱.每次打開都會對箱中不同的食物品質產生影響.假設配送箱中共有v種不同的食物[12]，每次打開外賣配送箱對客戶b外賣的時間滿意度影響值為μb.客戶時間滿意度

(1)

式中：η為系數且η∈(0,1]；δ為指數；r為打開外賣箱的次數.

該商家的客戶時間滿意度可以表示為

(2)

式中：L為門店的數量；m為外賣車的數量；n為外賣訂單的數量.

1.3 配送總成本

商家在進行外賣配送時需要考慮配送的總成本[13]，配送總成本主要包括固定成本、運輸成本和貨損成本.

固定成本為商家每日需要支付給外賣配送員的工資等.其函數表示為

E1=p·Efixed,

(3)

式中：p為外賣配送員的人數；Efixed為商家每日支付給每個外賣配送員的工資.

運輸成本為運輸過程中的能源消耗成本.該成本與運輸距離有關.其函數表示為

(4)

式中：Etrans為運輸過程中單位路程的能源消耗成本；dab為客戶節點a到節點b的距離.

此外，在進行外賣配送時，隨著運輸時間的增加，外賣的質量和溫度不斷下降.貨損成本函數表示為

(5)

配送總成本為

E=E1+E2+E3=

(6)

1.4 模型構建

本文對該多目標問題采用主要目標法[14]進行求解，以最大化客戶時間滿意度為主要目標，最小化配送總成本為次要目標.其多目標外賣配送路徑優化模型為

(7)

minE=min(E1+E2+E3).

(8)

約束條件為

所有的外賣訂單都被配送到位,

配送路徑的數量不超過外賣配送員人數,

每個外賣訂單僅被一個外賣配送員配送.

2 兩階段啟發式算法設計

本文采用兩階段啟發式算法進行線路優化.第一步采用基于就近分配原則的SWEEP算法將多門店問題轉化為單一門店問題進行求解，降低問題的復雜性，提高求解效率；第二步使用改進的蟻群算法對多個外賣配送員的配送線路進行優化.

2.1 SWEEP配送區域劃分算法

SWEEP算法是由Gillett和Miller提出來的一種啟發式算法[15]，其本質是將距離相對近的客戶節點歸并在一條線路中.本文利用改進的SWEEP算法對各門店配送區域進行劃分以降低計算問題的復雜性.

算法步驟：

1)比較商家各門店和客戶節點的最近距離和次近距離

(9)

式中：o1為離客戶節點a最近的門店；o2為離客戶節點a次近的門店；dao1為客戶節點a和門店o1之間的距離；dao2為客戶節點a和門店o2之間的距離.

當0≤r(a)<λ時，客戶節點a由門店o1進行配送；當λ≤r(a)≤1時，該節點a為邊界點，λ∈[0,1];

2)對所有的n個客戶節點進行第1步的判斷，得到門店A,B,C…的配送集WA,WB,WC…;

3)基于已得到的配送集對少部分邊界客戶節點進行門店的分配.分別在某邊界客戶節點a最近和次近門店對應的配送集Wo1,Wo2中選擇距離客戶節點a最近的客戶節點bo1和bo2，比較兩者相對距離

(10)

式中：dabo1,dabo2分別為客戶節點a到節點bo1和bo2之間的距離.

2.2 改進蟻群算法

蟻群算法已廣泛應用于多個領域.但該算法存在著收斂速度慢、常出現搜索停滯現象和易陷入局部最優等問題.本文通過對蟻群算法進行改進可以有效地解決上述問題，增強算法實用性和提高算法性能.

2.2.1 偽隨機比例狀態轉移規則

蟻群系統(ACS)由M.Dorigo在1996年提出[16]，主要改進是采用了偽隨機比例狀態轉移規則[17].在ACS算法中，偽隨機比例參數q0反應了螞蟻利用已有知識和探索新知識的相對性.當 0≤q≤q0時，螞蟻進行確定性搜索；當q0

Select=

(11)

改進偽隨機比例狀態轉移規則參數q0.令

其中，q0_min為偽隨機比例參數q0的最小值，υq0為參數變化函數系數.在算法前期，參數q0取值較小，有較大概率進行隨機搜索，有利于發現更優解；在算法后期，參數q0取值較大，有較大概率進行確定搜索，縮短算法運行時間，加快收斂速度.

2.2.2 信息素更新規則

蟻群算法中信息素的更新可分為全局更新和局部更新兩部分.在全局更新中，基本算法對所有路徑都執行信息素更新，包括較差路徑，這會降低最優路徑被搜索到的可能性，易造成算法振蕩，陷入局部最優解.對全局信息素更新規則進行改進，通過正負反饋方法更新至今最優路徑和最差路徑上的信息素，提高全局最優解搜索能力，加快算法收斂速度.

全局信息素更新公式為

τab(t+n)=(1-ρ)·τab(t)+Δτab,

(12)

(13)

式中：ρ為全局信息素揮發系數;Q為全局信息素增量系數;Sbest和Sworst為至今最優和最差路徑客戶時間滿意度;Snext-best和Snext-worst為至今次優和次差路徑客戶時間滿意度;Sbest-ave和Sworst-ave分別為至今多次迭代最優和最差路徑的平均客戶時間滿意度.

2.2.3 引入局部搜索算法

k-opt去交叉算法是由Croes提出來的一種局部搜索算法[18].該算法是基于鄰域的概念，在局部最優解的鄰域中尋找更好的解，如果有則替換當前的解.本文利用2-opt算法對局部最優解進行優化，可以創造大量有較大差異的可行解，一定程度上避免更優的解丟失，克服其陷入局部最優.

2.3 算法步驟

2)將μ只螞蟻隨機放到p個節點上；

3)構造每只螞蟻未訪問的節點To_visit和已訪問節點Visited，遍歷所有節點，利用路線轉移和偽隨機比例轉移規則選擇下一個客戶節點或是回到門店，并將節點加入Visited中，最后所有配送點全部被訪問，更新禁忌表；

4)記錄當次迭代參數并應用2-opt算法更新局部最優解，記錄至今最優、次優、最差和次差路徑；

5)根據全局信息素更新規則更新信息素矩陣Tau；

6)達到預定的迭代次數N_max時，結束循環，否則跳轉到第2步.

3 實驗結果與分析

假設某商家共有門店2家，單日訂單數為25個，根據建立的多目標外賣配送路徑優化模型，利用如上算法設計求解.其中：外賣車最大載重量為8 kg，行駛速度為20 km/h，各客戶節點配送等待時間為3 min，每日每位外賣配送員固定支出Efixed為3元/人，時間滿意度系數η為0.4，指數δ為2，運輸過程中單位路程能源消耗成本Etrans為1.2元/公里.在實例分析時兩個客戶節點間的配送路程使用直線距離，門店和客戶節點對應其他數據參數如表1 所示.

該商家以最大化客戶滿意度為主要目標，在進行路徑規劃時，其規劃方案為：門店A負責9個訂單的配送，需要2個外賣配送員，其配送路徑為：0-5-4-8-11-1-0，0-23-2-7-3-0；門店B負責16個訂單的配送，需要4個外賣配送員，其配送路徑為：0-11-14-10-9-5-12-0，0-4-3-2-8-7-0，0-6-13-15-16-0,0-1-0.此時該商家客戶時間滿意度為96.49%，配送總成本為82.64元.此外，商家還可以設置配送總成本的最高限制，在有限配送總成本的條件下達到客戶滿意度的最大值.

表1 門店和客戶節點相關數據參數表Tab.1 Related data parameter table between store and customer node

4 結 論

本文建立了關于客戶時間滿意度和配送總成本的多目標外賣配送路徑優化模型，并利用兩階段啟發式算法進行求解，在將客戶時間滿意度作為主要目標的前提下為外賣商家設計了規劃方案.本文在建立模型時，分別將客戶時間滿意度和配送總成本作為目標分析，符合外賣商家客戶第一的要求，對外賣配送路徑規劃具有一定的指導意義.