基于兩階段啟發(fā)式算法的多目標(biāo)外賣配送優(yōu)化分析

徐肇元

(山西農(nóng)業(yè)大學(xué) 軟件學(xué)院，山西 太谷 030800)

0 引 言

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

1 模型的建立

在模型建立之前先定義二進(jìn)制決策變量：

1.1 問(wèn)題假設(shè)

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

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

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

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

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

1.2 時(shí)間滿意度

每進(jìn)行一次外賣配送，都會(huì)打開(kāi)一次外賣配送箱.每次打開(kāi)都會(huì)對(duì)箱中不同的食物品質(zhì)產(chǎn)生影響.假設(shè)配送箱中共有v種不同的食物[12]，每次打開(kāi)外賣配送箱對(duì)客戶b外賣的時(shí)間滿意度影響值為μb.客戶時(shí)間滿意度

(1)

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

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

(2)

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

1.3 配送總成本

商家在進(jìn)行外賣配送時(shí)需要考慮配送的總成本[13]，配送總成本主要包括固定成本、運(yùn)輸成本和貨損成本.

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

E1=p·Efixed,

(3)

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

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

(4)

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

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

(5)

配送總成本為

E=E1+E2+E3=

(6)

1.4 模型構(gòu)建

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

(7)

minE=min(E1+E2+E3).

(8)

約束條件為

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

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

每個(gè)外賣訂單僅被一個(gè)外賣配送員配送.

2 兩階段啟發(fā)式算法設(shè)計(jì)

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

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

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

算法步驟：

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

(9)

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

當(dāng)0≤r(a)<λ時(shí)，客戶節(jié)點(diǎn)a由門店o1進(jìn)行配送；當(dāng)λ≤r(a)≤1時(shí)，該節(jié)點(diǎn)a為邊界點(diǎn)，λ∈[0,1];

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

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

(10)

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

2.2 改進(jìn)蟻群算法

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

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

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

Select=

(11)

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

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

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

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

全局信息素更新公式為

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

(12)

(13)

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

2.2.3 引入局部搜索算法

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

2.3 算法步驟

2)將μ只螞蟻隨機(jī)放到p個(gè)節(jié)點(diǎn)上；

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

表1 門店和客戶節(jié)點(diǎn)相關(guān)數(shù)據(jù)參數(shù)表Tab.1 Related data parameter table between store and customer node

4 結(jié) 論

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