徐肇元

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

0 引 言

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

1 模型的建立

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

1.1 問題假設

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

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

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

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

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

1.2 時間滿意度

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

(1)

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

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

(2)

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

1.3 配送總成本

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

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

E1=p·Efixed,

(3)

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

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

(4)

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

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

(5)

配送總成本為

E=E1+E2+E3=

(6)

1.4 模型構建

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

(7)

minE=min(E1+E2+E3).

(8)

約束條件為

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

配送路徑的數(shù)量不超過外賣配送員人數(shù),

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

2 兩階段啟發(fā)式算法設計

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

2.1 SWEEP配送區(qū)域劃分算法

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

算法步驟：

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

(9)

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

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

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

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

(10)

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

2.2 改進蟻群算法

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

2.2.1 偽隨機比例狀態(tài)轉移規(guī)則

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

Select=

(11)

改進偽隨機比例狀態(tài)轉移規(guī)則參數(shù)q0.令

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

2.2.2 信息素更新規(guī)則

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

全局信息素更新公式為

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

(12)

(13)

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

2.2.3 引入局部搜索算法

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

2.3 算法步驟

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

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

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

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

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

3 實驗結果與分析

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

該商家以最大化客戶滿意度為主要目標，在進行路徑規(guī)劃時，其規(guī)劃方案為：門店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 門店和客戶節(jié)點相關數(shù)據參數(shù)表Tab.1 Related data parameter table between store and customer node

4 結 論

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