戴 韜，沈 靜

(東華大學(xué) 旭日工商管理學(xué)院，上海 200051)

外賣配送是外賣O2O中重要的服務(wù)環(huán)節(jié)，外賣平臺(tái)為了提升競(jìng)爭(zhēng)力，保證較高的服務(wù)質(zhì)量和用戶體驗(yàn)，紛紛建立基于眾包的配送平臺(tái)，如蜂鳥眾包、美團(tuán)眾包等。眾包模式的引入，既解決了平臺(tái)自建物流配送模式中固定的配送員運(yùn)力與波動(dòng)的訂單量不匹配的問題，也為臨時(shí)配送員兼職服務(wù)提供可能。

外賣配送主要有3種訂單分配方式：派單、搶單和搶派結(jié)合。對(duì)于參與眾包的兼職配送員來說，工作時(shí)間更靈活，搶單的自主選擇性更強(qiáng)。在搶單模式下，外賣平臺(tái)以取餐點(diǎn)與配送員位置等指標(biāo)向附近配送員推薦一批訂單，配送員搶單成功則必須完成該訂單。而眾包配送員在選擇訂單時(shí)往往憑經(jīng)驗(yàn)與下意識(shí)的反應(yīng)，若接受不適合的訂單容易導(dǎo)致送餐延誤產(chǎn)生賠付、客戶投訴等情況，既影響眾包配送員的收益，降低其參與眾包的積極性，又影響外賣平臺(tái)的服務(wù)聲譽(yù)。

因此，本文從配送員的角度出發(fā)，對(duì)眾包模式下的外賣配送訂單選擇問題進(jìn)行研究，提出基于路徑規(guī)劃的雙層算法，通過比較接受不同訂單所帶來收益進(jìn)行訂單選擇，使得在滿足各項(xiàng)約束下配送員的實(shí)際所得收益最優(yōu)。本文的研究結(jié)果能提高眾包配送員的工作效率及收益，也能提高外賣平臺(tái)的訂單推薦效率。

1 相關(guān)文獻(xiàn)綜述

訂單選擇是從大量任務(wù)中選擇最適合的若干個(gè)任務(wù)進(jìn)行執(zhí)行，也被稱為任務(wù)推薦，不少學(xué)者為眾包模式下的任務(wù)推薦提供了多種解決思路。Azi等[1]對(duì)空間眾包下實(shí)現(xiàn)工人收益最大的在線配送路徑進(jìn)行研究，在此基礎(chǔ)上為動(dòng)態(tài)任務(wù)推薦提供參考，文中采用自適應(yīng)大型鄰域搜索啟發(fā)式算法求解。Sun等[2]同樣關(guān)注了該問題，不同的是采用基于預(yù)測(cè)的路徑推薦算法進(jìn)行任務(wù)推薦。Deng等[3]提出基于動(dòng)態(tài)編程和分支定界策略的精確算法，用于求解時(shí)空眾包模式下，單個(gè)工人完成任務(wù)數(shù)最多的任務(wù)推薦問題。鄧娜等[4]采用基于聚類分析和TSP路徑規(guī)劃的外賣配送訂單集指派模式，以配送距離最短為原則將配送員和訂單匹配。宋天舒等[5]將眾包任務(wù)地點(diǎn)也作為考慮因素，提出自適應(yīng)隨機(jī)閾值算法進(jìn)行任務(wù)內(nèi)容、眾包人員和任務(wù)地點(diǎn)的三維匹配，使得總效用最大。

外賣配送及眾包物流的路徑規(guī)劃成為近幾年的研究熱點(diǎn)之一。李桃迎等[6]對(duì)動(dòng)態(tài)外賣訂單調(diào)度及配送路徑問題進(jìn)行研究，提出基于商家和顧客聚類的路徑規(guī)劃。蔣麗等[7]在對(duì)眾包外賣配送路徑規(guī)劃的研究中，提出加入未來潛在客戶數(shù)量影響因子的蟻群算法，使得配送成本最小。吳騰宇等[8]針對(duì)O2O外賣配送中需求不確定及取送貨的特點(diǎn)，建立相應(yīng)的路徑規(guī)劃模型，設(shè)計(jì)了TAIB算法和IGNORE算法，實(shí)現(xiàn)外賣配送車輛的實(shí)時(shí)調(diào)度。慕靜等[9]基于眾包物流參與人員積極性不高等問題，以最大化收益為目標(biāo)，構(gòu)建眾包物流運(yùn)力調(diào)度問題模型。陳萍等[10]提出基于時(shí)間滿意度的外賣配送路徑優(yōu)化模型，并使用改進(jìn)的遺傳算法求解。Liu等[11]構(gòu)建一個(gè)納入出租車眾包配送的外賣配送網(wǎng)絡(luò)，采用包括構(gòu)造算法和大鄰域搜索算法的兩階段方法解決配送問題，使得所需出租車數(shù)量最少。Veenstra等[12]研究包含取送貨按后進(jìn)先出處理成本的取送貨旅行商問題，基于此特點(diǎn)建立模型，并采用大鄰域搜索算法求解。

外賣配送路徑規(guī)劃與取送貨旅行商問題(pickup and delivery travelling salesman problem, PDTSP)比較接近。由于VRP問題為NP難問題，因此通常使用啟發(fā)式算法求解，主流的有遺傳算法、蟻群算法、禁忌搜索算法和粒子群算法等。Zhao等[13]提出一種混合遺傳算法，用于解決取送貨一體的旅行商問題。潘立軍等[14]在傳統(tǒng)遺傳算法的基礎(chǔ)上，采用時(shí)差插入法改進(jìn)交叉算子、變異算子與變異算子的設(shè)置，并使用非代際搜索策略求解帶時(shí)間窗取送貨問題。Ai等[15]提出一種基于隨機(jī)密鑰解決方案的粒子群算法，用于實(shí)現(xiàn)取送貨車輛路徑問題，基于客戶優(yōu)先級(jí)列表和車輛優(yōu)先級(jí)矩陣構(gòu)建車輛路線。

綜上，任務(wù)匹配與取送貨一體化TSP問題的先期研究為本文奠定了很好的理論基礎(chǔ)，但是本文研究的配送訂單選擇問題是一個(gè)“開放性”的決策問題，配送員可以根據(jù)自身情況選擇一個(gè)或多個(gè)備選訂單；在執(zhí)行一系列訂單過程中，與TSP問題不同，具有“路徑開放(不用回到起點(diǎn))”、“參與時(shí)間有限”、“最終目的地確定”等特點(diǎn)。這些特點(diǎn)讓問題變得更加復(fù)雜，因此本文提出將訂單選擇與執(zhí)行路徑統(tǒng)一考慮的雙層算法。

2 決策模型與算法

2.1 問題描述

外賣配送訂單選擇的實(shí)際場(chǎng)景為眾包配送員在尚有未完成的待配送訂單情況下，如何從系統(tǒng)推薦訂單列表中選擇多個(gè)訂單，使得配送收益最大化的問題?？梢猿橄竺枋鰹榕渌蛦T在 T時(shí)刻前到達(dá)某個(gè)指定點(diǎn)，在此之前可參與兼職配送，現(xiàn)有 m個(gè)訂單尚未配送(可能部分已取)。此時(shí)外賣平臺(tái)的配送訂單推薦列表中有 n個(gè)訂單可供配送員進(jìn)行搶單，配送員如何從列表中選擇合適的訂單，使得完成所有訂單后按時(shí)到達(dá)終點(diǎn)，同時(shí)配送收益最大化。

2.2 雙層算法邏輯與說明

由于外賣配送的所得收益不僅是訂單配送費(fèi)用的簡(jiǎn)單相加，還需扣除因延遲配送導(dǎo)致的懲罰，因此在選擇訂單時(shí)需考慮是否能在規(guī)定時(shí)間內(nèi)送達(dá)、是否會(huì)產(chǎn)生懲罰等情況。配送路徑規(guī)劃本身是NP難問題，訂單選擇是基于配送路徑規(guī)劃的更高層次的決策問題，而且由于現(xiàn)實(shí)問題的特點(diǎn)，模型的求解速度要求較高，更加大了決策難度。

本文提出雙層算法基本邏輯是上層邏輯為貪心算法，即通過某個(gè)評(píng)分機(jī)制，對(duì)待選擇訂單進(jìn)行評(píng)分。由于平臺(tái)實(shí)時(shí)推薦的訂單數(shù)量較多，為了提高求解速度，將根據(jù)評(píng)分結(jié)果篩選出分?jǐn)?shù)較高的 n個(gè)訂單進(jìn)入考慮選擇的范圍，由大到小逐個(gè)加入這n個(gè)訂單進(jìn)行配送路徑規(guī)劃，并得到相應(yīng)的配送收益，若加入新訂單后的配送收益大于配送原有訂單所帶來的收益，則接受該訂單，否則，不接受，直到再加入新訂單無法得到可行解；下層邏輯為以配送收益最大為目標(biāo)的考慮時(shí)間窗、延遲配送懲罰、配送攜帶訂單數(shù)量約束等現(xiàn)實(shí)因素的配送路徑規(guī)劃模型，對(duì)應(yīng)的求解算法是改進(jìn)的遺傳算法。

雙層算法流程如圖1所示。

圖1 雙層嵌套算法邏輯圖Figure 1 The logic diagram of two-layer algorithm

2.3 訂單評(píng)分模型

在上層算法中，依次加入推薦訂單的順序?qū)⒅苯佑绊懽罱K訂單選擇的結(jié)果，而 n個(gè)訂單所有可能的順序組合有種。為了減小求解規(guī)模，同時(shí)增加較優(yōu)的訂單被選擇的可能性，本文建立訂單評(píng)分模型，根據(jù)分?jǐn)?shù)高低確定訂單加入的順序與規(guī)模。

本文考慮影響配送訂單選擇的主要因素包括訂單配送費(fèi)、訂單服務(wù)點(diǎn)(取餐點(diǎn)或送餐點(diǎn))與待訪問點(diǎn)(待配送訂單的取餐點(diǎn)或送餐點(diǎn))間的距離、送餐點(diǎn)與配送員計(jì)劃終點(diǎn)的距離、取送餐方向。針對(duì)上述4個(gè)主要因素構(gòu)建評(píng)分模型為

其中， s(FR)i為基礎(chǔ)配送收益，本文將用訂單i的配送費(fèi)占推薦列表中所有訂單配送費(fèi)總和的占比表示； s(PDN)i、 s(DDN)i為訂單i的取餐點(diǎn)、送餐點(diǎn)與原計(jì)劃下一訪問點(diǎn)間的距離得分，距離越近分?jǐn)?shù)越高； s(DDR)i為 訂單i送餐點(diǎn)與計(jì)劃終點(diǎn)間距離得分，計(jì)算方法與 s(PDN)i以 及 s(DDN)i相同； s(DR)i是取送餐方向得分，訂單i的取餐點(diǎn)或送餐點(diǎn)若在配送員當(dāng)前位置至計(jì)劃終點(diǎn)的方向相反的區(qū)域，則該項(xiàng)得分為0，反之為1。 FW、 N W、 D DW、 D W分別表示各因素所占權(quán)重。

2.4 眾包外賣配送路徑規(guī)劃模型

外賣配送有以下幾個(gè)特征：1) 每個(gè)訂單需先取餐再送餐；2) 取餐及送餐均有時(shí)間窗；3) 因?yàn)楸叵淙萘坑邢蓿袛y帶訂單數(shù)量限制。除此之外，眾包(兼職)配送員可以在任意空閑時(shí)間開始或停止接單，因此，眾包配送員的配送路線一般不是閉環(huán)：從當(dāng)前位置開始配送，完成所有任務(wù)后在某個(gè)最晚時(shí)間前回到一個(gè)預(yù)期的終點(diǎn)，如圖2所示。配送電動(dòng)車受電瓶電量限制有行駛里程約束，全職配送員一般會(huì)配備多個(gè)電瓶克服里程限制。而眾包配送員多為兼職參與，因此需考慮電動(dòng)車電量所能支持的行駛里程。綜上，在前3個(gè)基本特征之外，眾包配送新增的特征為：4) 開放式取送貨旅行商問題；5) 有最晚到達(dá)終點(diǎn)時(shí)間約束；6) 有行駛里程約束。

2.4.1 問題描述及模型假設(shè)

考慮 n個(gè) 配送任務(wù)時(shí)，配送網(wǎng)絡(luò)包含1個(gè)配送員當(dāng)前位置、1個(gè)配送員計(jì)劃終點(diǎn)和 2n個(gè)服務(wù)點(diǎn)(取送餐)，配送員須在時(shí)間 T前完成所接受的配送任務(wù)并回到計(jì)劃終點(diǎn)。定義網(wǎng)絡(luò)中節(jié)點(diǎn)集合V={0,2n+1}∪R∪C， 其中，節(jié)點(diǎn) 0表 示當(dāng)前位置；節(jié)點(diǎn) 2n+1表示終點(diǎn)；集合 R={1,2,···,n}表示所有訂單的取餐點(diǎn)；集合 C ={n+1,n+2,···,2n}表示所有訂單的送餐點(diǎn)；i和 n +i分 別對(duì)應(yīng)訂單i的取餐點(diǎn)和送餐點(diǎn)。配送員將決策收益最大的配送路徑，要滿足的約束有：須在每個(gè)節(jié)點(diǎn)的時(shí)間窗內(nèi)訪問該節(jié)點(diǎn)；若超出最晚送餐時(shí)間則產(chǎn)生延時(shí)懲罰；同時(shí)每個(gè)訂單必須“先取再送”；配送過程中攜帶的訂單數(shù)有限；時(shí)間 T前到達(dá)計(jì)劃終點(diǎn)。

本文假設(shè)如下。1) 配送員在取餐和送餐過程中的服務(wù)時(shí)間忽略；2) 車輛在行駛過程中行駛速度確定；3) 行駛成本與行駛路徑成正比；4) 對(duì)于超時(shí)送餐的訂單，將取消配送費(fèi)，并懲罰一倍配送費(fèi)的金額。

2.4.2 參數(shù)說明及數(shù)學(xué)模型

1) 符號(hào)定義。

O：所有訂單集合。

2) 模型參數(shù)。

①車輛相關(guān)參數(shù)。

v為車輛行駛速度； Q為車輛攜帶訂單容量；L為最大里程限制； α為行駛成本系數(shù)。

②網(wǎng)絡(luò)圖相關(guān)參數(shù)

dij為 節(jié)點(diǎn)i到 節(jié)點(diǎn) j 的距離； ai為 車輛 到達(dá)節(jié)點(diǎn)i的時(shí)間； si為 車輛離開節(jié)點(diǎn)i的 時(shí)間； wi為車輛在節(jié)點(diǎn)i的等待時(shí)間；qi為 車輛離開節(jié)點(diǎn)i時(shí)所載訂單數(shù)量。

③訂單參數(shù)。

3) 決策變量。

根據(jù)上述定義，得到配送路徑模型為

其中，式(2)為目標(biāo)函數(shù)，表示配送收益最大化；式(3)、(4)表示配送員從當(dāng)前位置節(jié)點(diǎn)0出發(fā)；式(5)、(6)表示配送員最后回到計(jì)劃終點(diǎn)；式(7)、(8)表示每一個(gè)訂單的取餐點(diǎn)和送餐點(diǎn)都必須被訪問一次；式(9)計(jì)算車輛到達(dá)節(jié)點(diǎn) j的時(shí)間；式(10)、(11)為配送員在節(jié)點(diǎn)i的等待時(shí)間以及離開該點(diǎn)的時(shí)間；式(12)保證最晚取餐時(shí)間被滿足；式(13)確保先取餐點(diǎn)后送餐點(diǎn)；式(14)表示配送員在預(yù)期時(shí)間內(nèi)完成待配送任務(wù)并到達(dá)終點(diǎn)；式(15)、(16)為車輛攜帶訂單數(shù)量約束；式(17)保證配送行駛路程不超過當(dāng)前電動(dòng)車剩余電量所能滿足的里程。

2.5 改進(jìn)遺傳算法設(shè)計(jì)

1) 編碼方式。

為了便于體現(xiàn)取餐點(diǎn)和送餐點(diǎn)的區(qū)別，本文采用自然數(shù)編碼的方式對(duì)取餐點(diǎn)和送餐點(diǎn)進(jìn)行編碼，0,1,2, ···,2n+1表示2n+2個(gè)訪問點(diǎn)，其中，0為起點(diǎn)，1,2,…,n為取餐點(diǎn)，分別對(duì)應(yīng)第1,2, ···,n號(hào)訂單，送餐點(diǎn)對(duì)應(yīng)為n+1, n+2, ···, 2n，終點(diǎn)為2n+1，即訂單 i的取餐點(diǎn)編碼為i，送餐點(diǎn)為 i +n。例如，假設(shè)當(dāng)前有5個(gè)待配送訂單，取餐點(diǎn)和送餐點(diǎn)編碼如表1所示，起點(diǎn)為0，終點(diǎn)編碼為11。以上編碼組隨機(jī)排序組合成一條染色體，代表一條配送路線，如0-2-1-6-4-7-3-8-5-10-9-11，其中，每個(gè)編碼代表染色體上的一個(gè)基因。

表1 5個(gè)待配送訂單的取餐點(diǎn)及送餐點(diǎn)編碼Table 1 Serial ID of 5 orders pickup and delivery nodes

2) 初始化種群及改進(jìn)的個(gè)體構(gòu)造方法。

由于帶有取送餐順序約束以及攜帶訂單數(shù)量約束，隨機(jī)生成的初始種群符合約束的概率較小，遺傳難以進(jìn)行下去。為了提高初始種群的質(zhì)量以及算法運(yùn)算速度，本文提出2個(gè)構(gòu)造方法在隨機(jī)生成初始種群的基礎(chǔ)上，對(duì)不符合約束的染色體重新構(gòu)造。

① 取送餐順序約束構(gòu)造。

若隨機(jī)生成的染色體中存在某個(gè)送餐點(diǎn)在對(duì)應(yīng)訂單的取餐點(diǎn)之前訪問，則將該訂單的取餐點(diǎn)移到送餐點(diǎn)前一位，送餐點(diǎn)與原取餐點(diǎn)位置中間的訪問點(diǎn)依次后移一位。例如，當(dāng)前有5個(gè)待配送訂單，假設(shè)隨機(jī)生成的某一染色體為0-2-3-4-6-7-8-1-9-5-10-11，其中，1號(hào)訂單的取餐點(diǎn)1出現(xiàn)在對(duì)應(yīng)的送餐點(diǎn)6之后，不符合取送餐順序約束，因此將基因1移至基因6前一位，原染色體中基因6與1之間的基因依次后移一位，其余基因位置保持不變，形成新的染色體，其操作如圖3所示。

圖3 取送餐順序約束調(diào)整操作圖Figure 3 Examplefor sequence constraint adjustment

② 攜帶訂單數(shù)量約束構(gòu)造。

配送員在訪問取餐點(diǎn)后車輛攜帶訂單數(shù)量加1，訪問送餐點(diǎn)后數(shù)量減1。若在訪問某點(diǎn)后，車輛攜帶訂單數(shù)量超過容量，那么該點(diǎn)一定為取餐點(diǎn)，同時(shí)，該取餐點(diǎn)前一定有其他尚未送餐的訂單的取餐點(diǎn)。因此，為了避免破壞取送順序約束，本文以該取餐點(diǎn)所在的基因位為界限，從該取餐點(diǎn)之后的基因中選取已經(jīng)取餐但尚未送餐訂單的送餐點(diǎn)，將該送餐點(diǎn)前移。以圖4為例，假設(shè)車輛攜帶訂單容量為2，車輛訪問取餐點(diǎn)4后訂單數(shù)量為3，超過容量限制，因此從取餐點(diǎn)4往后尋找已經(jīng)在該點(diǎn)之前取過餐的訂單對(duì)應(yīng)的送餐點(diǎn)，先找到送餐點(diǎn)7，將7移至4前一位，原染色體中4與7之間的基因均依次后移一位，其余基因位置保持不變，形成新的染色體。

圖4 攜帶訂單數(shù)量約束調(diào)整操作圖Figure 4 Example for order amount constraint adjustment

經(jīng)過一次調(diào)整可以得到新染色體，但該染色體仍有可能違反約束，例如取餐點(diǎn)1。因此，需要按照上述方式進(jìn)行順序檢查，最后可以得到如圖5所示的符合約束的可行解。

圖5 經(jīng)過調(diào)整后滿足約束的染色體Figure 5 A feasible chromosome after adjustment operations

3) 適應(yīng)度函數(shù)。

模型適應(yīng)度函數(shù)與目標(biāo)函數(shù)一致，適應(yīng)度函數(shù)f =M。若染色體不滿足最大里程約束或者最晚到達(dá)終點(diǎn)時(shí)間約束，則該染色體的適應(yīng)度直接計(jì)為0。

4) 遺傳算子設(shè)計(jì)。

① 采用輪盤賭方法選擇算子。

② 使用雙交叉點(diǎn)法選擇交叉算子，即隨機(jī)選取2個(gè)基因點(diǎn)，獲取父代染色體中在基因點(diǎn)之間的基因片段，并將這2個(gè)基因片段互換，形成2個(gè)新個(gè)體。例如，如圖6所示，2條父代染色體隨機(jī)選取的交叉點(diǎn)為4和7，則交叉的基因片段為“4-8-1-6”和“1-6-5-8”，將這2段基因片段在父代染色體中互換，得到新的子代染色體?？梢姡哟?中取餐點(diǎn)5重復(fù)出現(xiàn)，卻缺少取餐點(diǎn)4，子代2中取餐點(diǎn)4出現(xiàn)2次，卻缺少取餐點(diǎn)5，說明交叉得到的染色體很容易不符合約束。

圖6 父代染色體交叉Figure 6 Chromosomes crossover

為了解決交叉操作后基因重復(fù)問題，本文的處理是先找出交叉片段與染色體中的重復(fù)基因，子代1的基因5和子代2的基因4，然后進(jìn)行重復(fù)基因互換，如圖7所示。同理，若重復(fù)基因有多個(gè)，則在子代的交叉片段中的基因互換也需要進(jìn)行多次。

圖7 處理重復(fù)基因后的子代Figure 7 Offspring after handling duplicate gene

③ 根據(jù)變異概率判斷父代染色體是否變異，若變異，則隨機(jī)選擇2個(gè)基因位置，交換這2個(gè)位置的基因，形成新的子代。

④ 本文采用精英選擇策略進(jìn)行種群更新，先進(jìn)行當(dāng)前種群的交叉和變異，交叉及變異得到的新的子代若不符合約束，同樣使用2)中所述構(gòu)造方法將其改造，然后根據(jù)染色體的適應(yīng)度從父代和子代群體中篩選出當(dāng)前適應(yīng)度最高的染色體，數(shù)量滿足群體大小，形成新的種群。

5) 遺傳終止條件。

為了確保算法盡可能接近最優(yōu)解，同時(shí)減少運(yùn)算時(shí)間，采用以下2個(gè)迭代終止條件：① 若連續(xù)100次迭代的適應(yīng)度相同，則終止迭代；② 迭代次數(shù)達(dá)到最高次數(shù)1 000次，則終止迭代。

3 算例實(shí)驗(yàn)

3.1 算例基礎(chǔ)數(shù)據(jù)

假設(shè)某眾包配送員當(dāng)前位置為(0,0)，計(jì)劃在1.2 h后到達(dá)終點(diǎn)為(2,2)，尚有 3個(gè)訂單未配送，待配送外賣訂單信息如表2所示。此時(shí)外賣平臺(tái)根據(jù)就近取餐原則，向該眾包配送員推薦了若干個(gè)新訂單，根據(jù)表3所示的權(quán)重設(shè)置為訂單打分，假設(shè)從其中分?jǐn)?shù)最高的10個(gè)訂單中進(jìn)行選擇，納入考慮選擇范圍的10個(gè)訂單信息如表4所示。

表2 待配送外賣訂單信息Table 2 Order info.in to-do list

表3 訂單評(píng)分模型權(quán)重設(shè)置Table 3 Weight setting in order scoring model

表4 備選外賣配送訂單信息Table 4 Alternate delivery order info.

對(duì)配送過程及配送車輛的各項(xiàng)參數(shù)設(shè)置以及訂單評(píng)分模型權(quán)重設(shè)置分布如表5所示。

表5 車輛及配送服務(wù)實(shí)驗(yàn)參數(shù)設(shè)置Table 5 Experimental parameters of vehicle and delivery service

3.2 算例實(shí)驗(yàn)結(jié)果

本文使用C++語言在Visual Studio 2017中編寫程序并運(yùn)行，實(shí)驗(yàn)運(yùn)行環(huán)境均為Intel Celeron i5-1017U 1.60 GHz CPU，6GB內(nèi)存和Windows 10專業(yè)版64位操作系統(tǒng)。遺傳算法的參數(shù)設(shè)定為種群大小=100，交叉概率=0.7，變異概率=0.1。

當(dāng)前待配送訂單的路徑規(guī)劃結(jié)果如表6所示，最優(yōu)配送路徑為“0→2→1→3→4→5→6→7”，當(dāng)前配送收益為18.22元。

在現(xiàn)有3個(gè)訂單基礎(chǔ)上，利用設(shè)計(jì)的雙層算法從10個(gè)備選訂單中選擇最合適的一些訂單。為了驗(yàn)證算法的計(jì)算速度，進(jìn)行15次實(shí)驗(yàn)，如圖8。除了第2次運(yùn)算時(shí)長(zhǎng)超過4 s外，其余14次實(shí)驗(yàn)所用時(shí)間均在3 ～ 4 s之間，運(yùn)行平均時(shí)間為3.67 s，證明從10個(gè)備選訂單進(jìn)行選擇花費(fèi)時(shí)間可接受。

表6 當(dāng)前待配送訂單配送路徑規(guī)劃結(jié)果Table 6 Delivery route planning for current orders

圖8 基礎(chǔ)算例15次實(shí)驗(yàn)運(yùn)算時(shí)間Figure 8 Calculating time of 15 experiments on basic example

在運(yùn)行時(shí)間驗(yàn)證的基礎(chǔ)上，繼續(xù)進(jìn)行算法效率驗(yàn)證。圖9為15次實(shí)驗(yàn)中典型的收斂圖，大部分實(shí)驗(yàn)均在適應(yīng)度53左右時(shí)收斂。

圖9 基礎(chǔ)算例典型實(shí)驗(yàn)收斂圖Figure 9 Typical convergence graphs of basic example

表7和圖10更直觀地展現(xiàn)了依次加入推薦訂單后的配送收益變化?？梢钥闯?，并非訂單數(shù)量越多配送收益越大，若多個(gè)訂單的送餐時(shí)間窗相近，過多的訂單將導(dǎo)致送餐時(shí)間延遲產(chǎn)生懲罰，進(jìn)而降低配送收益；此外，初始的訂單評(píng)分越高只是表示“優(yōu)先考慮”但并非“最終選擇”，如訂單7的評(píng)分為4.26，訂單3的評(píng)分為4.15，模型先考慮了訂單7，但最后僅選擇了訂單3，產(chǎn)生這種情況的原因是加入訂單7后的配送收益小于訂單3。表8展示了配送收益最優(yōu)的訂單選擇，加入推薦的9、10、6、4、5、3號(hào)訂單后收益可達(dá)53.06，增加了34.84，配送路徑從自然編碼翻譯成最終結(jié)果為起點(diǎn)→取10→送10→取3'→取1'→送3'→送1'→取9→送9→取5→送5→取3→送3→取6→送6→取4→送4→取2'→送2'→計(jì)劃終點(diǎn)。

表7 多個(gè)推薦配送訂單選擇計(jì)算過程Table 7 Calculation process of multiple recommended delivery order selection

圖10 訂單選擇過程中配送收益變化圖Figure 10 Revenue graphwithnewadd-in orders

表8 多個(gè)推薦配送訂單選擇結(jié)果Table 8 Result in multiple delivery order selection

此基礎(chǔ)上，為了驗(yàn)證算法的穩(wěn)定性，本文繼續(xù)設(shè)計(jì)9組不同推薦規(guī)模的算例進(jìn)行實(shí)驗(yàn)，本文認(rèn)為經(jīng)過評(píng)分排序，現(xiàn)實(shí)納入備選范圍的訂單數(shù)量不會(huì)超過20個(gè)，因此這9組算例中待配送訂單同樣為3個(gè)，備選訂單分別為11～19個(gè)，其余參數(shù)與表5相同。9組算例在分別經(jīng)過10次實(shí)驗(yàn)后得到平均程序運(yùn)行時(shí)間如圖11所示。由此，可以得到以下2個(gè)結(jié)論。

圖11 不同備選訂單數(shù)量所需平均推薦時(shí)間Figure 11 Average calculating time with different numbers of alternate orders

1) 隨著選擇的推薦訂單數(shù)量增加，仍然能得到較優(yōu)推薦結(jié)果，程序運(yùn)算時(shí)間隨之線性增長(zhǎng)。

2) 導(dǎo)致運(yùn)算時(shí)間與推薦訂單數(shù)量線性相關(guān)的原因是，隨著訂單規(guī)模的增大，調(diào)用雙層算法中下層遺傳算法進(jìn)行迭代的次數(shù)增加，因此總運(yùn)行時(shí)間與備選訂單數(shù)量呈正相關(guān)。同時(shí)這也說明本文所設(shè)計(jì)的下層改進(jìn)遺傳算法穩(wěn)定性較好，單次運(yùn)算時(shí)間不會(huì)隨著訂單數(shù)量增加明顯改變。

4 結(jié)論

本文根據(jù)眾包配送的特點(diǎn)，提出雙層算法為眾包配送員在搶單過程中選擇訂單提供決策參考，其中接受新訂單的原則是考慮懲罰后的配送收益最大化。本文將訂單選擇與路徑規(guī)劃同時(shí)考慮，基于訂單初始評(píng)分決定進(jìn)入訂單選擇的次序，再利用整數(shù)規(guī)劃模型決定是否選擇該訂單并進(jìn)行下層的路徑規(guī)劃，在路徑規(guī)劃時(shí)，允許訂單交叉執(zhí)行。在求解下層的路徑規(guī)劃模型中，本文設(shè)計(jì)了改進(jìn)的遺傳算法，主要的創(chuàng)新是進(jìn)行染色體的再構(gòu)造，實(shí)現(xiàn)眾包配送必須的取送餐順序及訂單攜帶數(shù)量約束。論文在算例實(shí)驗(yàn)中驗(yàn)證了模型與算法在小規(guī)模問題下的求解效果與求解速度。在此基礎(chǔ)上，發(fā)現(xiàn)將本文方法擴(kuò)展到更大規(guī)模的問題時(shí)，求解時(shí)間是線性增長(zhǎng)的。因此對(duì)于大規(guī)模的現(xiàn)實(shí)問題，通過本文提出的打分方法，進(jìn)行訂單的初始篩選和排序是必要的。