考慮員工滿意度的多目標(biāo)外賣訂單配送路徑優(yōu)化研究

高椿林 張維存 許建

摘要 針對(duì)外賣訂單配送問題，首先對(duì)員工滿意度影響因素進(jìn)行量化分析，并構(gòu)建了以配送總成本、客戶滿意度、員工滿意度為目標(biāo)的外賣訂單配送路徑優(yōu)化模型;其次提出適用于外賣訂單配送的兩階段初始解構(gòu)造法、基于“HV貢獻(xiàn)值”的鄰域解評(píng)價(jià)策略以及新的拆分和修復(fù)算子，對(duì)自適應(yīng)大鄰域搜索算法進(jìn)行改進(jìn);最后以餓了么外賣平臺(tái)的實(shí)際數(shù)據(jù)設(shè)計(jì)仿真實(shí)驗(yàn)，與原始自適應(yīng)大鄰域搜索算法求解結(jié)果進(jìn)行對(duì)比，驗(yàn)證了模型在提升員工滿意度上的實(shí)用性和改進(jìn)算法對(duì)外賣訂單配送的有效性。

關(guān) 鍵 詞 外賣訂單配送；車輛路徑優(yōu)化；離散多目標(biāo)問題；自適應(yīng)大鄰域搜索算法

中圖分類號(hào) F274；TP301.6? ? ? 文獻(xiàn)標(biāo)志碼 A

Research on multi-objective takeout delivery routing optimization considering employee satisfaction

GAO Chunlin1， ZHANG Weicun1， XU Jian2

（1. School of Economics and Management， Hebei University of Technology， Tianjin 300400， China; 2. School of Humanities and Laws， Hebei University of Technology， Tianjin 300400， China）

Abstract To solve the delivery problem of takeout orders， first， the factors influencing employee satisfaction are quantified， and the delivery route optimization model aiming at the total delivery cost， customer satisfaction as well as employee satisfaction is constructed; secondly， a two-stage initial solution construction method suitable for takeout order distribution， a neighborhood solution evaluation strategy based on "HV contribution " and new split and repair operators are proposed to improve the adaptive large neighborhood search algorithm; finally， a simulation experiment of the actual data design of ELEME platform is used to compare the results with the original adaptive large neighborhood search algorithm， which verifies the practicability of the model in improving employee satisfaction and the effectiveness of the improved algorithm for the distribution of takeout orders.

Key words distribution of takeout orders; vehicle routing optimization; discrete multi-objective problem; adaptive large neighborhood search algorithm

0 引言

在互聯(lián)網(wǎng)經(jīng)濟(jì)高速發(fā)展背景下，外賣市場(chǎng)迎來(lái)了廣闊的發(fā)展空間，外賣訂單配送路徑優(yōu)化問題逐漸成為車輛路徑問題（Vehicle Routing Problem，VRP）的研究熱點(diǎn)之一。

在外賣訂單配送路徑優(yōu)化問題目標(biāo)設(shè)定上，目前平臺(tái)和學(xué)者大多將平臺(tái)配送總成本、客戶滿意度作為外賣訂單配送的主要目標(biāo)。徐倩等[1]構(gòu)建了以外賣平臺(tái)總成本最小為目標(biāo)的外賣訂單配送模型；余海燕等[2]將平均每單配送距離以及平均每單完成時(shí)間最小作為優(yōu)化目標(biāo)，建立了實(shí)時(shí)訂單分配與路徑優(yōu)化模型；陳萍等[3]提出一個(gè)基于時(shí)間參數(shù)的顧客滿意度函數(shù)，優(yōu)化目標(biāo)是顧客訂單總的時(shí)間滿意度最大；范厚明等[4]構(gòu)建了最小化超時(shí)訂單比例、單均配送時(shí)間和單均行駛距離為目標(biāo)的兩階段優(yōu)化模型；張力婭等[5]引入外賣平臺(tái)顧客優(yōu)先級(jí)概念，從顧客滿意度和配送成本兩個(gè)角度出發(fā)，建立了多目標(biāo)取送貨模型。但對(duì)于配送活動(dòng)中的另一行為主體——外賣騎手，在現(xiàn)有文獻(xiàn)中卻很少得到關(guān)注。近年來(lái)外賣騎手?jǐn)?shù)量不斷攀升，社會(huì)對(duì)外賣騎手的關(guān)注度的越來(lái)越高。外賣騎手員工滿意度是從客戶滿意度的概念引申而來(lái)，其不僅可以在一定程度上衡量外賣訂單配送工作狀況，而且直接影響到客戶能否獲得準(zhǔn)時(shí)、滿意的配送服務(wù)。因此構(gòu)建以平臺(tái)配送總成本、客戶滿意度、員工滿意度的多目標(biāo)外賣訂單配送路徑優(yōu)化問題模型具有十分重要的價(jià)值。

在外賣訂單配送路徑優(yōu)化問題求解上，由于“先取后送、一單一線、準(zhǔn)時(shí)送達(dá)”等外賣訂單配送約束存在，使得外賣訂單配送路徑優(yōu)化問題求解難度增大，并且車輛路徑問題已被證實(shí)為NP-hard問題，智能算法是目前普遍使用的求解方式。李桃迎等[6]引入k-means對(duì)“商家-客戶”進(jìn)行聚類，類內(nèi)設(shè)計(jì)“商家-客戶”遺傳算法，得到啟發(fā)式路徑優(yōu)化方案；Ren等[7]采用插入啟發(fā)式算法構(gòu)建初始解，引入前向連續(xù)交叉和差分突變策略，設(shè)計(jì)改進(jìn)了遺傳算法；趙向南等[8]設(shè)計(jì)了可有效求解混合整數(shù)規(guī)劃模型的帶有精英策略的非支配排序遺傳算法（NSGA-II）；陳希瓊等[9]在蟻群算法中加入禁忌搜索表以及貪婪轉(zhuǎn)移準(zhǔn)則，從而在迭代過(guò)程中進(jìn)行局部的禁忌搜索以產(chǎn)生更優(yōu)解。其中，自適應(yīng)大鄰域搜索算法憑借其“搜索空間大、搜索效率高”的特點(diǎn)，在求解VRP問題上取得了良好的效果。例如Xue等[10]設(shè)計(jì)一個(gè)兩階段模型，將訂單根據(jù)時(shí)間和位置分配到子區(qū)域后，在子區(qū)域內(nèi)設(shè)計(jì)了自適應(yīng)大鄰域啟發(fā)式算法，以減少配送員數(shù)量；Pelletier等[11]針對(duì)不確定因素背景下的電動(dòng)車車輛路徑問題，設(shè)計(jì)一種基于大規(guī)模鄰域搜索的兩階段啟發(fā)式算法進(jìn)行求解；南麗君等[12]提出新的刪除、修復(fù)算子及動(dòng)態(tài)階段加速策略改進(jìn)了自適應(yīng)大鄰域搜索算法求解異質(zhì)車輛路徑優(yōu)化問題；Ropke等[13]提出由多個(gè)競(jìng)爭(zhēng)子啟發(fā)式算法組成的自適應(yīng)大鄰域搜索算法求解帶時(shí)間窗的取送貨問題。盡管如此，原始算法的鄰域解評(píng)價(jià)機(jī)制導(dǎo)致解的進(jìn)化方向單一，僅適用于單目標(biāo)問題，無(wú)法求解多目標(biāo)問題。因此本文將依據(jù)模型特點(diǎn)，對(duì)自適應(yīng)大鄰域搜索算法進(jìn)行改進(jìn)，提出一種多目標(biāo)自適應(yīng)大鄰域搜索算法（Multi-objective Adaptive Large Neighbourhood Search Algorithm，MALNS）。

綜上所述，本文的創(chuàng)新點(diǎn)如下：1）面向外賣訂單配送問題，對(duì)外賣騎手的員工滿意度進(jìn)行分析和量化，構(gòu)建了以降低配送總成本，提高客戶滿意度和員工滿意度為目標(biāo)的多目標(biāo)車輛路徑問題模型；2）設(shè)計(jì)了MALNS，改進(jìn)了鄰域解評(píng)價(jià)策略以應(yīng)用于離散多目標(biāo)問題的求解，提出了適用于外賣訂單配送的兩階段初始解構(gòu)造法，基于問題特性設(shè)計(jì)了新的拆分和修復(fù)算子，以保證非支配解集的多樣性和精確性。

1 問題與模型

1.1 問題與假設(shè)

問題描述：某區(qū)域內(nèi)有一定數(shù)量的外賣騎手，他們處在不同位置，各自的裝載量、速度也不相同?？蛻粼谕赓u平臺(tái)提交訂單，訂單有取單節(jié)點(diǎn)和送單節(jié)點(diǎn)，以一個(gè)配送任務(wù)對(duì)的形式分布在該區(qū)域范圍內(nèi)不同位置，平臺(tái)接到訂單后預(yù)設(shè)了取單節(jié)點(diǎn)時(shí)間窗及送單節(jié)點(diǎn)時(shí)間窗。當(dāng)外賣騎手在平臺(tái)派單時(shí)間[Bi]收到訂單配送任務(wù)后，根據(jù)系統(tǒng)給出的行駛路線，在配送其他訂單的過(guò)程中，需要先到取單節(jié)點(diǎn)并在取單時(shí)間[Ei]后取單，隨即出發(fā)按照規(guī)定的路線將該訂單在規(guī)定的時(shí)間[Li]前送到相應(yīng)的送單節(jié)點(diǎn)。平臺(tái)綜合考慮訂單和騎手相關(guān)信息，將訂單配送任務(wù)分配給合適的外賣騎手，并規(guī)劃出最佳行駛路線，實(shí)現(xiàn)訂單和外賣騎手的最優(yōu)匹配，使得我們關(guān)注的目標(biāo)（配送總成本、客戶滿意度、員工滿意度）達(dá)到最優(yōu)。

假設(shè)條件：1）騎手（車輛）的裝載量以外賣份數(shù)核算；2）騎手（車輛）無(wú)最大行駛里程約束；3）每個(gè)訂單有且僅有一個(gè)騎手提供服務(wù)；4）騎手在完成配送后從最后一個(gè)配送節(jié)點(diǎn)隨即返回到騎手出發(fā)位置；5）騎手出發(fā)位置、取單節(jié)點(diǎn)、送單節(jié)點(diǎn)的坐標(biāo)及相對(duì)距離已知，訂單取、送單節(jié)點(diǎn)時(shí)間窗的限制已知，騎手（車輛）的位置、裝載量、行駛速度固定且已知。

1.2 參數(shù)變量

集合：

[N]表示訂單集合[N=1，2，…，i]；

[P]表示騎手（車輛）集合[P=1，2，…，k]；

[O]表示騎手（車輛）位置集合[O=1′，2′，…，k′]；

[R]表示取單節(jié)點(diǎn)集合[R=1+，2+，…，i+]；

[C]表示送單節(jié)點(diǎn)集合[C=1-，2-，…，i-]；

[A]表示取單節(jié)點(diǎn)和送單節(jié)點(diǎn)集合[A=R∪C]；

[S]表示騎手位置，取/送單節(jié)點(diǎn)集合[S=O∪A]；

參數(shù)：

[i+]：訂單[i]的取單位置，[i∈N]；

[i-]：訂單[i]的送單位置，[i∈N]；

[k′]：騎手（車輛）[k]的初始/終止位置；

[vk]：騎手（車輛）[k]行駛速度，[k∈P]；

[K]：騎手（車輛）總數(shù)；

[Mk]：騎手（車輛）[k]的裝載量，[k∈P]；

[θ]：騎手（車輛）固定成本；

[θ1]：騎手（車輛）單位距離運(yùn)輸成本；

[θ2]：早到取單節(jié)點(diǎn)的時(shí)間懲罰成本；

[θ3]：晚到送單節(jié)點(diǎn)的時(shí)間懲罰成本；

[Di]：訂單[i]的配送費(fèi)，[i∈N]；

[Bi]：訂單[i]的平臺(tái)派單時(shí)間，[i∈N]；

[Ei]：訂單[i]預(yù)計(jì)的取單時(shí)間，[i∈N]；

[Li]：訂單[i]預(yù)計(jì)的送單時(shí)間，[i∈N]；

[dij]：節(jié)點(diǎn)[i，j]之間的距離，[i，j∈S]；

[tik]：騎手（車輛）[k]到達(dá)節(jié)點(diǎn)[i]的時(shí)間，[i∈S，k∈P]；

[mik]：騎手（車輛）[k]離開節(jié)點(diǎn)[i]時(shí)的載重，[i∈S，k∈P]。

[Tk]：騎手（車輛）[k]的全天工作時(shí)長(zhǎng)；

決策變量：

[Xijk]：當(dāng)車輛[k]從節(jié)點(diǎn)[i]行駛到節(jié)點(diǎn)[j]時(shí)為1，否則為0，[i，j∈S，k∈P]；

[Yik]：若訂單[i]指派給車輛[k]，其值為1，否則為0，[i∈N，k∈P]。

1.3 目標(biāo)函數(shù)

1）最小化配送總成本

①人員運(yùn)營(yíng)成本[C1]，外賣平臺(tái)支付給外賣騎手參與配送的固定成本

②行駛距離成本[C2]，騎手在為訂單提供配送任務(wù)時(shí)產(chǎn)生的相關(guān)費(fèi)用

③時(shí)間懲罰成本[C3]，因未按約定的時(shí)間取送單而產(chǎn)生的成本，由取單時(shí)間懲罰成本[C3a]與送單時(shí)間懲罰成本[C3b]之和表示

在[Ei]之后到達(dá)取單節(jié)點(diǎn)，在[Li]之前到達(dá)送單節(jié)點(diǎn)，不產(chǎn)生懲罰成本；在[Ei]之前到達(dá)取單節(jié)點(diǎn)，在[Li]之后5 min內(nèi)到達(dá)送單節(jié)點(diǎn)，將會(huì)產(chǎn)生一定的懲罰成本；在[Li]之后5 min后到達(dá)送單節(jié)點(diǎn)，客戶拒絕服務(wù)，懲罰成本設(shè)為某一最大值[Q]。

2）最大化客戶滿意度

客戶滿意度主要由外賣騎手到達(dá)送單節(jié)點(diǎn)時(shí)間與時(shí)間窗約束的差距決定。在規(guī)定時(shí)間[Li]內(nèi)送單，滿意度為100%；超時(shí)5 min以內(nèi)，客戶滿意度逐漸減少，超時(shí)5 min后，客戶滿意度為0，如式（6）所示：

總體客戶滿意度[U]由每個(gè)客戶滿意度的平均值決定，關(guān)系式如下：

3）最大化員工滿意度

外賣騎手作為謀生型員工[14]，其員工滿意度主要取決于生理層次的滿意度構(gòu)成因素，即工資待遇、工作強(qiáng)度。由此，本文刻畫了工作時(shí)間飽和度[ωt]、工作薪酬滿意度[ωs]分別表示外賣騎手的工作強(qiáng)度和工資待遇。

工作時(shí)間飽和度[ωt]由騎手配送任務(wù)時(shí)長(zhǎng)在全天工作時(shí)長(zhǎng)的比率表示，假設(shè)某外賣騎手[k]訂單[ii∈Nk]的派單時(shí)間為[Bi]，送單時(shí)間為[Li]，全天工作時(shí)長(zhǎng)為[Tk]，則工作時(shí)間飽和度計(jì)算公式如下：

工作薪酬滿意度[ωs]由所有配送訂單的配送費(fèi)與外賣騎手駕駛車輛裝載量的比率表示，即外賣騎手送單報(bào)酬和工作能力的比值。訂單的配送費(fèi)[Di]的計(jì)費(fèi)方式按照取單節(jié)點(diǎn)與送單節(jié)點(diǎn)直線距離計(jì)算，在3 km以內(nèi)[?]5，超過(guò)3 km的[?]2/km。假設(shè)某外賣騎手[k]的裝載量為[Mk]，其訂單[ii∈Nk]的配送費(fèi)為[Di]，則工作薪酬滿意度計(jì)算公式如下：

基于公平理論的思想，外賣騎手員工滿意度取決于所有騎手工作時(shí)間和工作薪酬是否均衡。本文取所有騎手的工作時(shí)間飽和度、工作薪酬滿意度的離散系數(shù)刻畫騎手工作時(shí)間飽和度和工作薪酬滿意度的均衡性。

①騎手工作時(shí)間飽和度均衡，由所有外賣騎手的騎手工作時(shí)間飽和度的離散系數(shù)表示。某外賣騎手[k]的工作時(shí)間飽和度為[ωtk]，假設(shè)所有外賣騎手的工作時(shí)間飽和度均值為[ωt]，則騎手工作時(shí)間飽和度均衡的計(jì)算公式為：

②騎手工作薪酬滿意度均衡，由所有外賣騎手的騎手工作薪酬滿意度的離散系數(shù)表示。某外賣騎手[k]的工作薪酬滿意度為[ωsk]，假設(shè)所有外賣騎手的工作薪酬滿意度均值為[ωs]，則騎手工作薪酬滿意度均衡的計(jì)算公式為：

1.4 數(shù)學(xué)模型

本文外賣訂單配送路徑優(yōu)化模型如下：

式（12）～（14）表示配送總成本最小，客戶滿意度和員工滿意度最大；式（15）表示每個(gè)訂單當(dāng)且僅當(dāng)被一個(gè)外賣騎手服務(wù)一次；式（16）表示一個(gè)訂單必須被同一個(gè)外賣騎手服務(wù)；式（17）表示訂單取單節(jié)點(diǎn)和送單節(jié)點(diǎn)的前后順序；式（18）表示外賣騎手駕駛配送車輛[k]的裝載量約束；式（19）表示外賣騎手配送路線的連貫性；式（20）表示騎手只有訂單派單后才能為訂單服務(wù)；式（21）表示每個(gè)騎手從初始位置出發(fā)，配送任務(wù)結(jié)束后務(wù)必回到出發(fā)位置；式（22）表示到達(dá)節(jié)點(diǎn)的時(shí)間推導(dǎo)；式（23）表示各節(jié)點(diǎn)車輛載重推導(dǎo)；式（24）表示對(duì)于所有的節(jié)點(diǎn)[i]有且只有一個(gè)外賣騎手訪問一次。

2 算法設(shè)計(jì)

根據(jù)上文對(duì)考慮員工滿意度的多目標(biāo)外賣訂單配送路徑優(yōu)化問題模型的分析，算法設(shè)計(jì)要點(diǎn)如下。

1）由于本文提出的模型為離散多目標(biāo)問題模型，MALNS將非支配解集代替原始算法中最優(yōu)解，改進(jìn)了鄰域解評(píng)價(jià)策略，引入單個(gè)解[HV]貢獻(xiàn)值的概念“[IHV]”，計(jì)算新解的“[IHV]”與當(dāng)前非支配解集[D]超體積[HV]的比值，判斷新解對(duì)非支配解集的改進(jìn)效果。

2）由于本文提出的模型具有多項(xiàng)約束條件，約束條件的增多導(dǎo)致解空間的不規(guī)則的可能增大，因此針對(duì)性地提出了新的拆分和修復(fù)算子以提高搜索效率，同時(shí)為了保證搜索效果，MALNS采用“兩階段初始解構(gòu)造法”提高初始解質(zhì)量，保證了非支配解集的精確性和多樣性。

2.1 初始解的構(gòu)造

2.1.1 編碼設(shè)計(jì)

本文研究的是考慮車輛異質(zhì)性且具有取送順序的外賣訂單配送路徑優(yōu)化問題，關(guān)鍵在于訂單分配及取單節(jié)點(diǎn)和送單節(jié)點(diǎn)訪問次序進(jìn)行優(yōu)化。為了便于理解和操作，本文采用自然數(shù)編碼，編碼方案為[1′，i11，i12，…，i1v，1′，2′，i21，i22，…，i2u，2′，…，k′，ik1，ik2，…，ikm，k′]，其中[k′]表示騎手[k]的初始/終止位置，[ikm]表示訂單的取/送單節(jié)點(diǎn)。

2.1.2 初始解的構(gòu)造

為了保證初始解的質(zhì)量和多樣性，本文將外賣訂單配送初始解的構(gòu)造劃分為2個(gè)階段。

1）將訂單合理地分配給外賣騎手。針對(duì)訂單[i]，計(jì)算每個(gè)外賣騎手[k]從初始位置[k′]出發(fā)，先到取單節(jié)點(diǎn)[i+]取單，再到送單節(jié)點(diǎn)[i-]送單，最后回到終止位置[k′]的配送時(shí)間[Tk=dk′i++di+i-+di-k′/vk·Rnd]，從所有外賣騎手[P]中選出配送時(shí)間最短的騎手[k]即[minTk]，將訂單[i]分配給該騎手。該訂單分配方式盡可能多的保證外賣騎手配送的訂單在一定的距離范圍內(nèi)，縮短了配送距離，降低了配送總成本。其中，擾動(dòng)系數(shù)[Rnd∈（0.9，1.1）]，可以保證初始解的多樣性，使得初始解在解空間中隨機(jī)分布，以免在搜索中陷入局部最優(yōu)解。

2）規(guī)劃取送訂單的路徑。首先生成只包含外賣騎手[k]初始位置和終止位置的車輛路徑[k′，k′]，將該騎手在1）分配到的訂單隨機(jī)生成一個(gè)訂單序列[Uk]。在滿足訂單需求及車容量限制條件下，按照訂單序列[Uk]中的訂單順序，采用貪婪插入法依序?qū)⒂唵尾迦氲津T手[k]的車輛路徑中。直到所有騎手的訂單均完成插入，最終生成該初始解的車輛調(diào)度方案。針對(duì)騎手[k]的車輛路徑規(guī)劃具體步驟如下所示。

步驟1? ? 根據(jù)式（1）～（5）計(jì)算當(dāng)前路徑成本[F1]，將第一個(gè)訂單[i]從訂單序列[Uk]中剔除。

步驟2? ? ?插入取單節(jié)點(diǎn)[i+]。將訂單[i]的取單節(jié)點(diǎn)[i+]按順序插入騎手[k]路徑中的初始位置到終止位置間的未插入過(guò)的位置上，根據(jù)公式（25）計(jì)算路徑[k]上取單節(jié)點(diǎn)[i+]及后續(xù)所有節(jié)點(diǎn)的載重[mik]，并判斷其中所有取單節(jié)點(diǎn)[j+]是否滿足車輛裝載量。根據(jù)公式（26）計(jì)算取單節(jié)點(diǎn)[i+]及后續(xù)所有節(jié)點(diǎn)的到達(dá)時(shí)間[tik]，并判斷其中所有送單節(jié)點(diǎn)[j-]是否滿足配送時(shí)間窗。如果2個(gè)條件均滿足，則轉(zhuǎn)入步驟3，否則進(jìn)一步判斷取單節(jié)點(diǎn)[i+]插入位置是否終止位置[k']的緊前位置，如果不是，則重復(fù)步驟2，否則，直接轉(zhuǎn)入步驟6。

步驟3? ? 插入送單節(jié)點(diǎn)[i-]。將訂單[i]的送單節(jié)點(diǎn)[i-]按順序插入路徑[k]的取單節(jié)點(diǎn)[i+]到終止位置間的未插入過(guò)的位置上，根據(jù)式（26）計(jì)算送單節(jié)點(diǎn)[i-]及后續(xù)所有節(jié)點(diǎn)的到達(dá)時(shí)間[tik]，并判斷其中所有送單節(jié)點(diǎn)[j-]是否滿足配送時(shí)間窗。如果滿足，則根據(jù)公式（1～5）計(jì)算當(dāng)前路徑成本[F1′]，并轉(zhuǎn)入步驟4，否則轉(zhuǎn)入步驟5。

步驟4? ? 計(jì)算插入取單節(jié)點(diǎn)[i+]和送單節(jié)點(diǎn)[i-]的成本差值[Δki=F1′-F1]，記錄取單節(jié)點(diǎn)[i+]和送單節(jié)點(diǎn)[i-]的插入位置及該插入位置下的成本變化[Δki]。

步驟5? ? 判斷送單節(jié)點(diǎn)[i-]插入位置是否是終止位置的緊前位置，如果不是，則轉(zhuǎn)回步驟3，否則，進(jìn)一步判斷取單節(jié)點(diǎn)[i+]插入位置是否是終止位置的緊前位置，如果不是，則轉(zhuǎn)回步驟2，否則，轉(zhuǎn)入步驟6。

步驟6? ? 將訂單[i]插入最佳位置。選擇記錄下的成本變化最小值[Δki]對(duì)應(yīng)的取單節(jié)點(diǎn)[i+]和送單節(jié)點(diǎn)[i-]的插入位置作為訂單[i]在路徑中的最佳插入位置，將訂單[i]插入到配送路徑中。

步驟7? ? 判斷訂單序列[Uk]是否為空集，如果是，騎手[k]的車輛路徑規(guī)劃完成，否則轉(zhuǎn)回步驟1。

2.2 訂單“拆分-修復(fù)”策略

2.2.1 訂單拆分策略

訂單拆分策略即拆分算子，其中包含了4種訂單移除操作，每種移除操作的結(jié)果都是將[q]筆訂單從當(dāng)前解[S]中移除：

1）隨機(jī)移除策略：將隨機(jī)選中的[q]筆訂單都從[S]中移除，此策略不考慮訂單的特點(diǎn)和訂單間的相關(guān)性，只為增加鄰域解的多樣性。

2）相似訂單移除策略：根據(jù)訂單之間的相似度對(duì)訂單進(jìn)行移除處理。訂單[i]和訂單[j]之間的相似度[R（i，j）]最早由Shaw[15]提出，本文[R（i，j）]的計(jì)算從時(shí)間、距離2個(gè)方面來(lái)考慮，權(quán)重分別用[α，β]表示。[R（i，j）]的數(shù)值越小，訂單[i]和訂單[j]的相似度越高。通過(guò)選擇相似匹配度高的訂單進(jìn)行移除，便于相似度高的訂單交換配送順序，有可能構(gòu)造出更高質(zhì)量的鄰域解。

3）移除成本最高的訂單：定義訂單[i]的成本為[costi，S=fS-f-i（S）]，其中[f-i（S）]表示從當(dāng)前解[S]中移除訂單[i]后的成本。對(duì)[S]中各訂單按[costi，S]數(shù)值按從大到小的順序構(gòu)成序列。選擇[costi，S]最高的[q]筆訂單進(jìn)行移除，有可能構(gòu)造出成本更低的鄰域解。

4）移除浪費(fèi)時(shí)間最長(zhǎng)的訂單：外賣騎手無(wú)論是提前到達(dá)取單節(jié)點(diǎn)還是送單節(jié)點(diǎn)都是對(duì)外賣平臺(tái)運(yùn)力的一種浪費(fèi)。定義訂單[i]的浪費(fèi)時(shí)間為[wastei，S=Ei-ti+k+Li-ti-k]。對(duì)[S]中各訂單按[wastei，S]數(shù)值按從大到小的順序構(gòu)成序列。選擇浪費(fèi)時(shí)間最多的[q]筆訂單進(jìn)行移除，有可能構(gòu)造出高質(zhì)量鄰域解。

2.2.2 訂單修復(fù)策略

移除[S]中[q]筆訂單之后，然后再將這些訂單重新插入到各路徑中獲得鄰域解。訂單修復(fù)策略即修復(fù)算子，其中包含4種插入操作。

1）貪婪插入策略：篩選出符合約束條件的位置，按照貪婪原則選擇訂單[i]插入到每條路徑中成本增量最低的位置上。用[?f（i，k）]表示在每一次插入過(guò)程中訂單[i]插入路徑[k∈K]中所帶來(lái)的成本增量，如果在路徑[k]中無(wú)法插入訂單[i]，則[?fi，k=∞]。然后，定義[ci=min?f（i，k）]表示將訂單[i]插入第[k]條路徑中某位置使得路徑配送成本最低，而產(chǎn)生的最低成本增量。最后，從未插入訂單集合[U]中選出插入成本增量最小的訂單[i]，即[min ci]，從[U]中刪除并插入對(duì)應(yīng)位置，直到所有訂單被插入或沒有訂單可以被插入后停止。

2）最大后悔值準(zhǔn)則插入策略：用變量[xik∈1，2，…，m]表示第[k]低插入成本的一條路徑，對(duì)貪婪插入中所定義的[?f（i，k）]，表示將訂單[i]插入路徑[k∈K]中最佳位置（成本最低）所帶來(lái)的成本增量，當(dāng)[k

3）均衡工作時(shí)間飽和度插入策略：為了達(dá)到目標(biāo)中騎手工作時(shí)間飽和度均衡，需要盡可能將訂單分配給工作時(shí)間不飽和的外賣騎手。從未插入訂單集合[U]中選擇[di+i-]（起止距離越遠(yuǎn)，工作時(shí)間越長(zhǎng)）最大的訂單，根據(jù)第[k]條路徑上的外賣騎手的工作時(shí)間飽和度[ωtk]，用[?i，k=ωt′k-ωt]表示在每一次插入過(guò)程中訂單[i]插入路徑[k]后該路線[ωtk]與所有路線均值[ωt]的差值，差值越小，工作時(shí)間飽和度越均衡。從所有路線[P]中，選擇[?i，k]最小的路徑[k]，再根據(jù)“貪婪插入策略”在該路線上選擇最佳位置進(jìn)行插入，該過(guò)程持續(xù)到所有訂單被插入后停止。

4）均衡工作薪酬滿意度插入策略：為了達(dá)到目標(biāo)中騎手工作薪酬滿意度均衡，需要盡可能將訂單分配給工作能力不飽和的外賣騎手。與“均衡工作時(shí)間飽和度插入策略”相似，為了均衡工作薪酬滿意度，從未插入訂單集合[U]中選擇[Di]最大（配送費(fèi)越高，工作薪酬越高）的訂單，根據(jù)第[k]條路徑上的外賣騎手的工作薪酬滿意度[ωsk]，用[?i，k=ωs′k-ωs]表示在每一次插入過(guò)程中訂單[i]插入路徑[k]后該路線[ωsk]與所有路線均值[ωs]的差值，差值越小，工作薪酬滿意度越均衡。從所有路線[P]中，選擇[?i，k]最小的路徑[k]，再根據(jù)“貪婪插入策略”在該路線上選擇最佳位置進(jìn)行插入，該過(guò)程持續(xù)到所有訂單被插入后停止。

2.3 鄰域解評(píng)價(jià)策略

在多目標(biāo)優(yōu)化問題中，最后求解得到的往往是一組非支配解集，由于非支配解之間沒有明顯的優(yōu)劣關(guān)系，所以原始自適應(yīng)大鄰域搜索算法在求解多目標(biāo)優(yōu)化問題時(shí)，無(wú)法評(píng)選出最優(yōu)解，也無(wú)法比較“當(dāng)前解”與“新解”的質(zhì)量。因此本文將非支配解集[D]代替最優(yōu)解，并在非支配解集的超體積（[hypervolume，HV]）的理論基礎(chǔ)上，引入單個(gè)解[HV]貢獻(xiàn)值的概念“[IHV]”設(shè)計(jì)鄰域解評(píng)價(jià)策略，計(jì)算“新解”的單個(gè)解[HV]貢獻(xiàn)值，并計(jì)算其與當(dāng)前非支配解集[D]超體積[HV]的比值，判斷“新解”對(duì)非支配解集的改進(jìn)效果，用來(lái)動(dòng)態(tài)選擇較優(yōu)的訂單“拆分-修復(fù)”策略組合生成鄰域進(jìn)行搜索。

非支配解集的超體積[HV]是在多目標(biāo)優(yōu)化問題中，評(píng)價(jià)解性能的重要指標(biāo)之一，它度量了非支配解集[D]與參考點(diǎn)圍成的目標(biāo)空間中區(qū)域的尺寸大小。[HV]值越大，說(shuō)明算法得到的非支配解集的覆蓋率越好，即算法性能越好。超體積[HV]計(jì)算公式如下：

式中：[xref]為參考點(diǎn)；[xj]是非支配解集[D]中的非支配解。

以雙目標(biāo)優(yōu)化問題為例，該問題求解2個(gè)最小化目標(biāo)函數(shù)，假設(shè)[fub1]和[fub2]分別表示單個(gè)目標(biāo)問題的上界，則參考點(diǎn)設(shè)定為[xref=fub1，fub2]。如圖1所示，2個(gè)非支配解集[D1]、[D2]和參考點(diǎn)圍成的區(qū)域分別表示[HVD1]和[HVD2]，由圖可知[HVD1>HVD2]，因此解集[D1]中的非支配解優(yōu)于[D2]中的非支配解。

[HV]越大，表明非支配解集的綜合性越好，所以單個(gè)解對(duì)非支配解集的超體積[HV]貢獻(xiàn)值[IHV]越大，那么該解的性能就越好，對(duì)算法搜索引導(dǎo)效果越好。單個(gè)解[HV]貢獻(xiàn)值[IHV]計(jì)算公式如下：

如圖2所示，假設(shè)[fub1]和[fub2]分別表示單個(gè)目標(biāo)問題的上界，則參考點(diǎn)設(shè)定為[xref=fub1，fub2]。通過(guò)在非支配解集里加入一個(gè)解的[HV]變化，刻畫了單個(gè)解[HV]貢獻(xiàn)值“[IHV]”的概念。假設(shè)非支配解集[D=a，b，c，d，e]，單個(gè)解[a]的[HV]貢獻(xiàn)值[IHV]可以用圖片中的點(diǎn)陣陰影部分表示。

2.4 算法框架

為了適應(yīng)該模型的求解，本文對(duì)自適應(yīng)大鄰域搜索算法流程進(jìn)行了改進(jìn)，改進(jìn)后算法MALNS求解具體流程為：

1）根據(jù)初始解構(gòu)造方案生成初始解集（詳見2.1），根據(jù)解的非支配關(guān)系得到非支配解集，記為[D*]，計(jì)算[D*]的[HV]值。

2）計(jì)算其中每個(gè)解的[HV]貢獻(xiàn)值[IHV]（詳見2.3），選擇[IHV]最大的解進(jìn)行標(biāo)記，并將其設(shè)定為當(dāng)前解[S]，如果該解曾被標(biāo)記，則選貢獻(xiàn)率次大的解，依此類推。

3）根據(jù)算子權(quán)重隨機(jī)選擇拆分算子、修復(fù)算子（詳見2.2）對(duì)當(dāng)前解[S]進(jìn)行拆分并修復(fù)獲得新解[S′]，將[S′]與[D*]合并，通過(guò)非支配判斷更新非支配解集[D*]，轉(zhuǎn)入步驟4）。

4）如果[S′]在與[D*]合并中被支配，直接轉(zhuǎn)步驟7）。否則更新非支配解集[D*]的[HV]，并令[S=S′]，計(jì)算[S′]的[IHVS′]與非支配解集[D*]的[HV]值比率Δ%。如果非支配解集改進(jìn)明顯（Δ%＞0.01），則轉(zhuǎn)步驟5），否則轉(zhuǎn)步驟6）。

5）令模擬退火溫度[T]=[Tinit]，對(duì)所選擇的拆分和修復(fù)算子增加相對(duì)應(yīng)的分?jǐn)?shù)[δ1]，轉(zhuǎn)步驟8）。

6）對(duì)所選擇的拆分和修復(fù)算子增加相對(duì)應(yīng)的分?jǐn)?shù)[δ2]，轉(zhuǎn)步驟8）。

7）利用模擬退火溫度[T]以式（30）計(jì)算相應(yīng)的概率接受新解，如果接受，令[S=S′]，對(duì)所選擇的拆分和修復(fù)算子增加相對(duì)應(yīng)的分?jǐn)?shù)[δ3]，轉(zhuǎn)步驟8）。

8）將模擬退火的溫度[T=T*c]，如果溫度[T

9）利用式（31）判斷是否達(dá)到更新算子權(quán)重的條件，如果達(dá)到則依據(jù)算子得分更新權(quán)重，將算子得分重置為0。

10）判斷是否達(dá)到最大迭代次數(shù)[N*]，若達(dá)到則轉(zhuǎn)到步驟11），否則轉(zhuǎn)到步驟3）繼續(xù)搜索。

11）判斷[D*]中是否存在未被標(biāo)記的解，存在則轉(zhuǎn)到步驟2），否則解除所有標(biāo)記，輸出非支配解集[D*]，算法停止。

本文依據(jù)模擬退火算法的判斷準(zhǔn)則，將經(jīng)過(guò)“拆分-修復(fù)”得到的鄰域解[S′]與當(dāng)前解[S]進(jìn)行比較，設(shè)定解[S′]的接受概率如下：

算子權(quán)重的更新取決于算子的一段迭代次數(shù)所取得的分?jǐn)?shù)。根據(jù)當(dāng)前算子權(quán)重，算法在拆分、修復(fù)時(shí)會(huì)通過(guò)輪盤賭方法，依照概率選擇算子進(jìn)行操作。在算法進(jìn)行搜索初期設(shè)定拆分算子、修復(fù)算子選擇權(quán)重均為0.25。每當(dāng)達(dá)到一定的迭代次數(shù)ψ，則表示算法進(jìn)入一個(gè)新的階段，根據(jù)算子上階段表現(xiàn)情況，以及算子綜合表現(xiàn)情況對(duì)算子進(jìn)行重新評(píng)價(jià)并給予新的權(quán)重，權(quán)重更新公式如下：

式中：[πi，j+1]代表在[j+1]階段算子[i]的權(quán)重；[πi，j]代表算子[i]在[j]階段獲得的評(píng)分；[ai，j]表示算子[i]在[j]階段的使用次數(shù)；[πi，j]表示算子[i]在[j]階段的權(quán)重。

3 實(shí)驗(yàn)分析

3.1 參數(shù)設(shè)定

為了確保算法求解的穩(wěn)定性，首先對(duì)算法進(jìn)行試運(yùn)行以調(diào)整算法參數(shù)，本文對(duì)迭代次數(shù)[N*]和移除訂單數(shù)量上限[q] 2個(gè)主要參數(shù)進(jìn)行了求解實(shí)驗(yàn)。經(jīng)多次實(shí)驗(yàn)分析，算法在[N*=900]時(shí)，算法搜索能力接近最大極限；移除訂單數(shù)量上限[q]為[10]，既能保證算法搜索能力又能盡可能減小算法運(yùn)行時(shí)間。

另外，算法采用模擬退火判斷準(zhǔn)則接受部分解，以Ropke[16]中各參數(shù)作為參考，初始溫度[Tinit]的值基于初始可行解[s]的單個(gè)解[HV]值進(jìn)行設(shè)置，將其設(shè)置為[Tinit=ω·HVS/ln2]，即如果解[S′]的單個(gè)解[HV]值比當(dāng)前解小ω%，則該解會(huì)以50%的概率予以接受，冷卻率[c=0.998 7]。對(duì)拆分和修復(fù)算子增加的分?jǐn)?shù)[δ1]、[δ2]、[δ3]的取值分別為33、13、9。

3.2 仿真實(shí)驗(yàn)

本文收集餓了么外賣平臺(tái)外賣訂單數(shù)據(jù)模擬外賣訂單配送情形設(shè)計(jì)10個(gè)外賣騎手配送100個(gè)訂單的仿真實(shí)例，在win8.1系統(tǒng)上，利用python3.8編譯MALNS進(jìn)行求解。為了直觀的分析非支配解集的相對(duì)位置，將非支配解集的目標(biāo)函數(shù)值進(jìn)行過(guò)歸一化處理，非支配解的分布如圖3所示。

由圖3分析可得，非支配解在目標(biāo)空間的分布基本滿足非支配解集的多樣性的要求，但是在均勻性表現(xiàn)一般，分析原因可能是因?yàn)樵谕赓u訂單配送問題是一個(gè)離散問題，解空間的不規(guī)則導(dǎo)致目標(biāo)函數(shù)空間相互割裂。在該仿真測(cè)例上可能是訂單數(shù)量有限，無(wú)法保證均勻的分配給每個(gè)員工，進(jìn)而導(dǎo)致員工滿意度無(wú)法進(jìn)一步提高。

為驗(yàn)證本文設(shè)計(jì)改進(jìn)的自適應(yīng)大鄰域搜索算法在外賣訂單配送優(yōu)化問題求解精確性和多樣性的具體表現(xiàn)，本文將該算法與原始自適應(yīng)大鄰域搜索算法的求解結(jié)果進(jìn)行比較，在相同運(yùn)算條件下，根據(jù)非支配解的擁擠度進(jìn)行排序，分別選取前10個(gè)非支配解，求解結(jié)果如表1所示。

首先從2個(gè)非支配解集的超體積（[HV]）指標(biāo)上來(lái)看，改進(jìn)后算法MALNS非支配解集[HV]值為0.352，改進(jìn)前算法非支配解集[HV]值為0.275，[HV]值提升了0.077，說(shuō)明MALNS求得的解集更接近真實(shí)的非支配解集最優(yōu)邊界。從表中各目標(biāo)函數(shù)均值可以看出，MALNS所得的非支配解集各目標(biāo)函數(shù)值均優(yōu)于原始算法，分別提高了3.7%，4.4%，3.0%。從單個(gè)目標(biāo)函數(shù)值來(lái)看，MALNS所得各目標(biāo)函數(shù)最優(yōu)值仍均優(yōu)于原始算法，分別提高了0.7%，25.5%，0.6%。由此可見，MALNS不僅提高非支配解集的目標(biāo)函數(shù)值，而且還保證了非支配解集的空間分布質(zhì)量，兼顧了非支配解集的收斂性和多樣性。

在MALNS得到的非支配解集中，解1配送總成本最低，解8客戶滿意度最高，解9員工滿意度最高（已加粗標(biāo)出）。以解1的各目標(biāo)函數(shù)值舉例分析，此解配送總成本3 045.755元，雖然在非支配解集中配送總成本最低，但是客戶滿意度為86.8%，員工滿意度為1.318，相對(duì)其他非支配解而言員工滿意度相對(duì)較低，進(jìn)一步分析該情況下外賣騎手工作時(shí)間飽和度均衡為0.903、工作薪酬滿意度均衡為0.415，可見由于外賣騎手工作時(shí)間分配存在較大差異，導(dǎo)致外賣騎手員工滿意度低，如果員工因此產(chǎn)生不滿情緒，建議外賣平臺(tái)選擇其他外賣訂單配送方案以提高員工滿意度。

通過(guò)對(duì)仿真實(shí)驗(yàn)結(jié)果分析得出，本文算法MALNS較原始算法相比求解能力有一定幅度的提升，求解該問題模型可以保證解集的精確性、多樣性，能夠?yàn)橥赓u平臺(tái)提供決策需求。

4 結(jié)語(yǔ)

本文主要研究了考慮員工滿意度的外賣訂單配送問題，將員工滿意度進(jìn)行量化融入多目標(biāo)外賣訂單配送路徑優(yōu)化模型，并改進(jìn)了自適應(yīng)大領(lǐng)域搜索算法對(duì)問題模型進(jìn)行求解。研究表明：

1）從員工滿意度的角度出發(fā)，將員工滿意度作為模型的目標(biāo)之一，結(jié)合最小化配送總成本、最大化客戶滿意度，構(gòu)建了考慮員工滿意度的多目標(biāo)外賣訂單配送路徑優(yōu)化模型，有利于平臺(tái)協(xié)調(diào)成本、客戶、員工三者之間的平衡。

2）本文設(shè)計(jì)的兩階段初始解構(gòu)造法，可以保證初始解的質(zhì)量和多樣性；提出的基于非支配解集超體積的“[HV]貢獻(xiàn)值”鄰域解評(píng)價(jià)策略以及新的拆分和修復(fù)算子，可以改進(jìn)自適應(yīng)大鄰域搜索算法以適用于求解多目標(biāo)路徑優(yōu)化問題，并生成高質(zhì)量的非支配解集。

參考文獻(xiàn)：

[1]? ? 徐倩，熊俊，楊珍花，等. 基于自適應(yīng)大鄰域搜索算法的外賣配送車輛路徑優(yōu)化[J]. 工業(yè)工程與管理，2021，26（3）：115-122.

[2]? ? 余海燕，蔣仁蓮. 基于眾包平臺(tái)的外賣實(shí)時(shí)配送訂單分配與路徑優(yōu)化研究[J]. 工業(yè)工程與管理，2022，27（2）：146-152.

[3]? ? 陳萍，李航. 基于時(shí)間滿意度的O2O外賣配送路徑優(yōu)化問題研究[J]. 中國(guó)管理科學(xué)，2016，24（S1）：170-176.

[4]? ? 范厚明，咸富山，王懷奇. 動(dòng)態(tài)需求下考慮訂單聚類的外賣配送路徑優(yōu)化[J]. 系統(tǒng)仿真學(xué)報(bào)，2022. DOI：10. 16182/j. issn1004731x. joss. 21-0965.

[5]? ? 張力婭，張錦，肖斌. 考慮顧客優(yōu)先級(jí)的多目標(biāo)O2O外賣即時(shí)配送路徑優(yōu)化研究[J]. 工業(yè)工程與管理，2021，26（2）：196-204

[6]? ? 李桃迎，呂曉寧，李峰，等. 考慮動(dòng)態(tài)需求的外賣配送路徑優(yōu)化模型及算法[J]. 控制與決策，2019，34（2）：406-413.

[7]? ? TENG R，Xu H B，JIN K N，et al. Optimisation of takeaway delivery routes considering the mutual satisfactions of merchants and customers[J]. Computers & Industrial Engineering，2021，162：107728.

[8]? ? 趙向南，邢磊，靳志宏. 考慮不確定行駛時(shí)間的雙目標(biāo)外賣配送路徑優(yōu)化[J]. 大連海事大學(xué)學(xué)報(bào)，2019，45（4）：65-72.

[9]? ? 陳希瓊，胡大偉，楊倩倩，等. 多目標(biāo)同時(shí)取送貨車輛路徑問題的改進(jìn)蟻群算法[J]. 控制理論與應(yīng)用，2018，35（9）：1347-1356.

[10]? XUE G Q，WANG Z，WANG G. Optimization of rider scheduling for a food delivery service in O2O business[J]. Journal of Advanced Transportation，2021：5515909.

[11]? PELLETIER S，JABALI O，LAPORTE G，et al. The electric vehicle routing problem with energy consumption uncertainty[J]. Transportation Research Part B：Methodological，2019，126：225-255.

[12]? 南麗君，陳彥如，張宗成. 改進(jìn)的自適應(yīng)大規(guī)模鄰域搜索算法求解動(dòng)態(tài)需求的混合車輛路徑問題[J]. 計(jì)算機(jī)應(yīng)用研究，2021，38（10）：2926-2934.

[13]? ROPKE S，PISINGER D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[J]. Transportation Science，2006，40（4）：455-472.

[14]? 孫林輝，黃放，袁曉芳，等. W電子商務(wù)公司物流員工工作滿意度測(cè)評(píng)研究[J]. 人類工效學(xué)，2015，21（4）：30-35，46.

[15]? SHAW P. Using constraint programming and local search methods to solve vehicle routing problems[C]// Principles and Practice of Constraint Programming — CP98. Berlin：Springer，1998：417-431.

[16]? ROPKE S，CORDEAU J F. Branch and cut and price for the pickup and delivery problem with time windows[J]. Transportation Science，2009，43（3）：267-286.