□ 于江霞 卞 喆 羅太波

(西安電子科技大學(xué) 經(jīng)濟與管理學(xué)院, 陜西 西安 710126)

[基金項目]教育部人文社會科學(xué)基金項目(20YJAZH123,18YJC630114);陜西省自然科學(xué)基金項目(2020JM-211);國家自然科學(xué)基金項目(72101196,71701162)。

一、引 言

隨著近場電商的發(fā)展及消費體驗升級,在線外賣市場規(guī)模持續(xù)增加,2019年中國餐飲外賣產(chǎn)業(yè)規(guī)模達到6 536億元,相比2018年增長了39.3%[1]。面對持續(xù)增長的訂單量和愈發(fā)激烈的行業(yè)競爭,外賣平臺更加關(guān)注配送時效和成本,卻忽略了派單機制的合理性及騎手的權(quán)益,導(dǎo)致派單不均衡,騎手收入差距過大,配送員心理失衡引起矛盾激化,頻發(fā)“騎手抗議強制派單”事件[2]。不合理的派單模式已成為影響即時配送行業(yè)持續(xù)健康發(fā)展的重要因素,是即時配送平臺亟需解決的現(xiàn)實問題。平臺任務(wù)分派實質(zhì)取決于配送路徑的優(yōu)化,因此本文在均衡準(zhǔn)則下兼顧配送成本和客戶滿意度,研究在不大幅增加成本和降低客戶滿意度的前提下,均衡配送員派單量、提高工作量與收入適配度的方案,進一步穩(wěn)定配送隊伍,促進外賣行業(yè)健康發(fā)展。

即時配送具有取送貨、商家和客戶有序配對的特征,有嚴(yán)格的先后訪問順序,且對配送準(zhǔn)時性要求較高,因此該類問題可歸結(jié)為同時取送貨的車輛路徑問題(vehicle routing problem with simultaneous pickup and delivery,VRPSPD)。針對VRPSPD問題,學(xué)者們在不同約束條件下對配送成本或客戶滿意度進行了優(yōu)化研究[3-7]。然而追求單一目標(biāo)的優(yōu)化方案易忽略其他限制,不能達到實際最優(yōu)。因此,學(xué)者們開始考慮多方面的綜合優(yōu)化,如考慮最小化車輛數(shù)及總行駛成本[8],最小化運輸成本和最大化客戶滿意度[9],最小化車輛路徑總長度、最小化客戶等待總時間[10],車輛行駛總里程最小和服務(wù)準(zhǔn)時率最大[11],運輸成本和路徑最大長度差最小[12]，考慮顧客層級的固定成本、運輸成本和超時懲罰成本最小[13]等。近年來,部分學(xué)者開始考慮工作量均衡對車輛路徑問題進行探討,如Rabbani等[14]考慮工作量均衡和時間窗約束對危險廢物的配送路徑問題進行研究,孫麗君等[15]考慮司機工作量均衡對成品油配送方案進行優(yōu)化。

可見,配送路徑優(yōu)化問題已引起廣泛關(guān)注,但多集中于配送成本和客戶滿意度的優(yōu)化,訂單分配不均、工作量負荷過重、群體內(nèi)收入與工作量不匹配等問題較少涉及。本文兼顧平臺、客戶和配送員三方利益,對配送成本、客戶滿意度和均衡配送員收入三個目標(biāo)進行綜合優(yōu)化,不僅能夠提高配送員訂單任務(wù)的均衡性,緩解收入不均、訂單量負荷過重的矛盾,也從一定程度上有助于解決員工高離職率問題,對即時配送行業(yè)的有序健康發(fā)展具有重要的現(xiàn)實意義。

二、問題描述及模型構(gòu)建

(一)問題描述

某平臺在一段時間內(nèi)接到N個訂單,對商家和客戶提供一對一的取送服務(wù)。配送員從初始位置出發(fā),配送完成后無需返回。需要合理安排配送路線,實現(xiàn)均衡配送員收入、最小化配送成本和最大化客戶滿意度的綜合優(yōu)化。不失一般性,做如下假設(shè):

(1) 配送員須先到商家取貨再配送至客戶點,訪問順序不能顛倒;

(2) 商家和客戶能且僅能被服務(wù)一次;

(3) 不考慮配送車輛的容量約束;

(4) 配送車輛具有最大行駛里程約束;

(5) 配送車輛行駛速度恒定;

(6) 送貨時的時間損耗忽略不計;

(7) 客戶滿意度僅與物品送達時間有關(guān)。

(二)參數(shù)及變量分析

集合和變量定義,見表1。

表1 集合和變量定義

(三)配送員績效工資

根據(jù)即時配送工資構(gòu)成[16],配送員績效主要包含訂單量和行駛距離,配送距離超過兩公里后有距離補貼,因此配送員k的績效工資可表示為:

Fk=nk×p1+max(Lk-2,0)×p2

(1)

(四)訂單超時懲罰成本

即時配送平臺有嚴(yán)苛的超時懲罰措施，一旦配送超時，則扣除一半配送費；若客戶給予差評，則直接扣除50～100元的罰款。根據(jù)《2016年餐飲消費調(diào)查報告》，有12%的消費者不習(xí)慣等待，超半數(shù)的消費者可以接受15分鐘以內(nèi)的等待時間，接近30%的消費者可以接受15～30分鐘的等待，愿意接受半小時以上等待時間的僅占7%[17]，顧客對不同超時時長容忍度不同[18]。本文引入容忍度概念，結(jié)合顧客可容忍的超時時間范圍，設(shè)置分段超時懲罰成本函數(shù) ，如圖(1)和式(2)所示。

圖1 懲罰成本函數(shù)

(2)

(五)客戶滿意度函數(shù)

經(jīng)過對美團外賣平臺客戶評論信息進行統(tǒng)計分析，發(fā)現(xiàn)客戶滿意度主要取決于送達時間，客戶大多偏好于在預(yù)計送達時間前得到服務(wù)，晚于該時間點則滿意度下降，且超時越長滿意度越低。因此，本文以配送準(zhǔn)時性作為衡量客戶滿意度的指標(biāo)，配送超時客戶滿意度呈線性下降，滿意度函數(shù)如圖(2)和式(3)所示。

圖2 時間滿意度函數(shù)

(3)

實際配送中輕微超時不可避免。統(tǒng)計發(fā)現(xiàn)客戶給予投訴或差評,98%是由于極端超時造成的。因此,為減少極端超時情況的發(fā)生,本文以最小化客戶最大不滿意度為目標(biāo),則客戶不滿意度函數(shù)為S′i=1-Si。

(六)模型建立

構(gòu)建最小化配送員工資極差、最小化配送成本和最小化客戶最大不滿意度的多目標(biāo)優(yōu)化模型:

(4)

(5)

min maxS′i,i∈N

(6)

(7)

(8)

(9)

(10)

l=1,2,…n,k=1,2,…m

(11)

(12)

i,l=1,2,…n,k=1,2,…m

(13)

式(4)表示最小化配送員薪酬極差;式(5)表示配送總成本最小;式(6)表示最小化客戶最大不滿意度;式(7)和式(8)確保每個訂單僅能被一輛車服務(wù)一次;式(9)表示每個客戶都得到配送服務(wù);式(10)確保任一輛車的配送訂單順序相連,防止出現(xiàn)空單行駛現(xiàn)象;式(11)為配送車輛的行駛里程約束;式(12)與式(13)為訂單的到達時間限制。

(七)多目標(biāo)問題的處理

將min maxS′i轉(zhuǎn)化為Z3=minb1及k個約束條件:f1(x)≤b1,f2(x)≤b1…fk(x)≤b1其中:

fk(x)=S′i

(14)

式(4)、(5)和(6)的隸屬度函數(shù)可以定義為具有同一量綱的單目標(biāo)函數(shù)式:

(15)

(16)

(17)

由于各目標(biāo)重要度不同,采用自適應(yīng)權(quán)重法來確定各目標(biāo)的權(quán)重值ω1,ω2和ω3,則統(tǒng)一量綱后的單目標(biāo)函數(shù)模型為:

minZ=ω1φ(Z1)+ω2φ(Z2)+ω3φ(Z3)

(18)

該問題屬于NP-hard問題,若采用精確算法易產(chǎn)生指數(shù)爆炸,難以在規(guī)定時間內(nèi)求得模型最優(yōu)解,而蟻群算法因其具有正反饋機制、較強的適應(yīng)性和尋求最優(yōu)解的能力等優(yōu)勢在路徑優(yōu)化問題中廣泛應(yīng)用,適用于求解此類問題。

三、混合蟻群算法設(shè)計

考慮即時配送具有取送貨、商家和客戶有序配對的特征,將遺傳算法和蟻群算法相結(jié)合設(shè)計混合蟻群算法,在標(biāo)準(zhǔn)蟻群算法中加入遺傳算法的交叉和變異操作,迭代更新路徑上的螞蟻狀態(tài),通過自適應(yīng)增量系數(shù)和揮發(fā)系數(shù)對信息素進行優(yōu)化。算法框架如圖3所示。具體算法步驟如下:

步驟1:參數(shù)初始化。設(shè)定信息素因子α、啟發(fā)信息因子β、信息素揮發(fā)系數(shù)ρ、最優(yōu)個體數(shù)目e。

步驟2:設(shè)定當(dāng)前迭代次數(shù)t=0,最大迭代次數(shù)T;當(dāng)前蟻群規(guī)模n=0,最大蟻群規(guī)模N;當(dāng)前行動螞蟻k=0,螞蟻數(shù)量K。

步驟3:初始化一隊蟻群,并初始化每個螞蟻的禁忌表,可訪問客戶節(jié)點表和共同可訪問的商家節(jié)點表。

步驟4:所有訂單配送完成判斷,判斷每個螞蟻的可訪問客戶節(jié)點和共同可訪問商家節(jié)點是否都為空,若都為空則進入步驟9,反之進入步驟6。

步驟5:配送員k是否配送完成判斷,判斷螞蟻k的可訪問客戶節(jié)點和共同可訪問商家節(jié)點是否都為空,若都為空則進入步驟8,反之進入步驟7。

步驟6:按概率確定螞蟻移動到下一個節(jié)點的位置。在螞蟻k的可訪問客戶節(jié)點或共同可訪問商家節(jié)點中選擇一點加入禁忌表,若是商家節(jié)點則需要把對應(yīng)的客戶節(jié)點加入螞蟻k的可訪問客戶節(jié)點。

步驟7:令k=k+1,若k

步驟8:令n=n+1,若n

步驟9:混合蟻群算法的交叉操作。以某一父代中配送員的順序為基準(zhǔn),對另一父代中的螞蟻進行排序,之后將每個配送員的禁忌表根據(jù)配送員的順序進行拼接,以生成兩條父代染色體。在兩條父代染色體中隨機確定一對交叉點,進行交叉操作生成子代,然后解碼成禁忌表。

步驟10:混合蟻群算法的變異操作。確定父代染色體k個配送員的禁忌表進行變異操作,首先按概率選擇變異點、并找到相應(yīng)的配對點,隨機確定商家、客戶節(jié)點需要變異的位置,剩余基因原序填充至空余基因位,以生成一條子代染色體。

圖3 混合蟻群算法流程圖

步驟11:根據(jù)自適應(yīng)權(quán)重系數(shù)處理多目標(biāo)優(yōu)化問題。將多個目標(biāo)建立為具有同一量綱的單目標(biāo)函數(shù)式;并構(gòu)建基于均值的權(quán)重更新函數(shù),通過判斷子目標(biāo)均值占比計算以確定各目標(biāo)的最佳權(quán)重系數(shù),從而保證算法的精度和效率。

步驟12:根據(jù)多目標(biāo)計算蟻群的適應(yīng)度并排序,用最優(yōu)的m個蟻群更新信息素。判斷迭代次數(shù)t是否達到設(shè)定的最大迭代次數(shù)T,若未達到則令t=t+1并進入步驟2;若已達到則程序結(jié)束,并輸出最優(yōu)個體。

四、算例分析

(一)算例結(jié)果

選取某即時配送平臺實際數(shù)據(jù)進行測試分析。該平臺在一段時間內(nèi)共接到6 000個訂單,由該區(qū)域內(nèi)30輛同車型車提供服務(wù),配送員的平均配送速度為25 km/h,模型參數(shù)見表2,商家和客戶的位置,預(yù)計送達時間均已知。

表2 模型參數(shù)

運用C++編程求解,設(shè)置信息啟發(fā)式因子α=1.0,期望啟發(fā)式因子β=2.0,信息素揮發(fā)系數(shù)ρ,信息素增量系數(shù)Q,螞蟻數(shù)量m=50,最大迭代次數(shù)為500次,得到基于均衡配送員工作量的配送方案如表3所示,記為方案一,其算法的迭代過程如圖4和圖5所示。

結(jié)果顯示方案一工資級差為284.910元,訂單分配量較為均衡,說明本模型能夠有效緩解收入不均、訂單量負荷過重的問題;花費的配送總成本為1 6164.372 8元,而總的超時懲罰成本僅156.681元,客戶最低滿意度為82.4%。

表3 方案一配送優(yōu)化結(jié)果

由圖4可知,該算法在求解過程中共迭代了500次,在運行初期目標(biāo)值下降趨勢顯著,遺傳至400代時基本收斂,最優(yōu)解趨于穩(wěn)定。表明該算法具有較好的尋優(yōu)能力,算法收斂結(jié)果好。

由圖5可得,隨著迭代次數(shù)的增加,三個目標(biāo)均呈現(xiàn)逐步優(yōu)化的趨勢, 當(dāng)最優(yōu)解趨于穩(wěn)定時, 配送員工資差、配送總成本和客戶最低滿意度均得到相對較優(yōu)的結(jié)果。將方案一與僅考慮配送總成本的方案二、僅考慮客戶滿意度的方案三和同時考慮配送總成本和客戶滿意度的方案四進行對比分析,結(jié)果見表4。

圖4 綜合目標(biāo)的算法迭代過程

圖5 單個目標(biāo)的算法迭代過程

表4 計算結(jié)果對比表

與方案二相比,方案一中配送員的工資級差顯著優(yōu)于方案二,降低了30.27%,超時客戶數(shù)雖略有增加,但客戶的最大超時卻明顯降低,滿意度優(yōu)于方案二,同時配送總成本僅增加3.26%;與方案三相比,配送員工資級差降低了29.49%,配送總成本也低于方案三1.57%,配送時間和配送里程也均有所減少,而客戶滿意度僅稍有降低;與方案四相比,客戶滿意度略有增加,配送總成本和總里程幾乎無變化,但配送員的工資級差卻減少了16.64%。

綜上,本文構(gòu)建的多目標(biāo)綜合優(yōu)化方案顯著優(yōu)于其他幾個方案,在成本幾乎無增加的前提下,一方面大幅度提高了配送員工作量的均衡性,提高了收入與工作量的優(yōu)化匹配,能夠有效緩解收入不均、員工高離職率的問題,確保配送隊伍穩(wěn)定性;另一方面還能夠有效確保配送的效率和準(zhǔn)時性,提高客戶的整體滿意度。

(二)算法性能分析

為驗證模型和算法的有效性,隨機生成不同數(shù)量的訂單,用MATLAB直接求最優(yōu)解與本文算法求解進行比較,結(jié)果如表5所示。

表5 模型驗證與算法對比

通過比較可知,當(dāng)訂單數(shù)量較小時(≤50),本文算法的結(jié)果與最優(yōu)解保持一致,而當(dāng)數(shù)量較大時(≥100),本文算法結(jié)果與最優(yōu)解相差較小。此時求精確解的計算時長已大于2小時,而本文算法計算時長一直在10分鐘內(nèi)，從而說明本文采用的混合蟻群算法是合理有效的。但由于精確算法容易形成指數(shù)爆炸,難以在規(guī)定時間求得模型最優(yōu)解,因而本文采用的混合蟻群算法更適用于解決較復(fù)雜的實際配送問題。

五、結(jié) 論

為緩解即時配送領(lǐng)域出現(xiàn)的訂單量分配不均、員工頻繁離職等問題,本文在配送員收入均衡準(zhǔn)則下兼顧配送成本和客戶滿意度,結(jié)合訂單具有取送貨、商家和客戶有序配對的特征,對多目標(biāo)取送貨配送問題進行綜合優(yōu)化研究。研究結(jié)果表明,考慮均衡配送員收入的多目標(biāo)綜合優(yōu)化,并不會導(dǎo)致配送成本的大幅增加,還能達到均衡配送員工作量和提高客戶滿意度的效果。

基于該研究結(jié)果,即時配送平臺可考慮更多因素進行派單機制的優(yōu)化,能夠在不損傷現(xiàn)有優(yōu)化目標(biāo)的同時,提高配送員派單量的均衡性,進一步提高工作量與收入的適配度,可在一定程度上達到穩(wěn)定配送隊伍,提高運營穩(wěn)定性的效果,對促進即時配送行業(yè)的健康穩(wěn)定發(fā)展具有重要意義?！?/p>