王晨宇,溫浩珉,郭晟楠,2,林友芳,2,萬懷宇,2

(1.北京交通大學(xué)計算機與信息技術(shù)學(xué)院,北京 100044;2.交通數(shù)據(jù)分析與挖掘北京市重點實驗室,北京 100044)

1 引言

近年來電商行業(yè)的快速增長帶動了快遞行業(yè)的迅猛發(fā)展。僅2022年春節(jié)期間我國攬收和投遞的包裹量就達到了7.49億件[1]。快遞攬收是快遞業(yè)務(wù)中一個非常重要的末端服務(wù)環(huán)節(jié)。在該環(huán)節(jié)中，快遞員上門攬件時間的預(yù)估精度一直是物流企業(yè)關(guān)心的重要問題。準(zhǔn)確的攬件到達時間預(yù)測能為用戶提供更準(zhǔn)時的服務(wù)，提升用戶體驗，也可以提升企業(yè)的服務(wù)效率，增強企業(yè)競爭力。

然而實際場景中的攬件到達時間預(yù)測問題同時面臨著以下幾個方面的挑戰(zhàn)：

(1) 任務(wù)路徑未知：快遞員執(zhí)行攬件任務(wù)的路徑與待預(yù)測任務(wù)的到達時間具有較強的相關(guān)性。但是現(xiàn)實中，快遞員在執(zhí)行攬收任務(wù)期間，還會不斷收到系統(tǒng)分配的新訂單。因此，在預(yù)測某個任務(wù)的到達時間的時侯，快遞員未來的攬收路線無法得知，這也給到達時間的預(yù)測帶來了高度的不確定性。因此，如何在路線未知的情況下做出精準(zhǔn)的到達時間預(yù)測，是一項巨大的挑戰(zhàn)。

(2) 訂單之間存在相互影響：當(dāng)物流系統(tǒng)給快遞員分配新的攬收訂單時，快遞員手中可能還有其他已接受但未完成的訂單需要完成，因此如何有效地建模這些已接未完成訂單對于新分配攬收任務(wù)的影響，對于新分配任務(wù)的到達時間預(yù)測也是一個難點。

(3) 外部影響因素復(fù)雜：待預(yù)測攬件任務(wù)的到達時間預(yù)測不僅會受到自身以及快遞員當(dāng)前其他未完成訂單的影響，還會受到當(dāng)前時段、目的地POI(Point of Interest)、工作日與節(jié)假日等復(fù)雜外部因素的影響。如何有效建模多種外部因素也是一大挑戰(zhàn)。

針對以上挑戰(zhàn)，本文提出了一種面向攬件到達時間預(yù)測的多任務(wù)深度時空網(wǎng)絡(luò)MSTN4PAT(Multi-task deep Spatial-Temporal Network for Pick-up Arrival Time prediction)模型，通過從快遞員產(chǎn)生的海量攬件歷史軌跡數(shù)據(jù)中學(xué)習(xí)攬件到達時間的復(fù)雜時空模式，以實現(xiàn)對攬件到達時間的精準(zhǔn)預(yù)測。在2組真實攬件數(shù)據(jù)集上的大量實驗表明，該模型優(yōu)于其他對比模型。本文的主要貢獻總結(jié)如下：

(1) 針對在預(yù)測時無法得知快遞員未來攬收路線的挑戰(zhàn)，本文提出充分挖掘待預(yù)測任務(wù)的始發(fā)地和目的地OD(Origin,Destination)之間內(nèi)在關(guān)聯(lián)的模型MSTN4PAT。該模型可以靈活地捕獲攬件場景中的復(fù)雜時空相關(guān)性。

(2) 針對受到其他已接未完成訂單影響的挑戰(zhàn)，設(shè)計了一種多任務(wù)學(xué)習(xí)機制，通過設(shè)置目標(biāo)訂單順序預(yù)測和其他未完成訂單攬收時間預(yù)測2個子任務(wù)，有效建模其他未完成訂單對待預(yù)測訂單的影響。

(3) 針對攬件到達時間受外部影響因素復(fù)雜的挑戰(zhàn)，構(gòu)建多頭注意力機制整合現(xiàn)有未完成訂單對于待預(yù)測訂單的影響，之后分別從特征寬度和特征深度2個角度進行低階交叉特征和高階交叉特征的捕獲，以此提升模型的記憶能力和泛化能力。

2 相關(guān)工作

本文所要研究的攬件到達時間預(yù)測問題可以看成一類ETA(Estimated Time of Arrival)預(yù)測問題。ETA預(yù)測是指預(yù)測從始發(fā)地到目的地所需的時間。ETA作為交通和物流服務(wù)領(lǐng)域的重要概念，是快遞攬收、外賣配送和打車拼車等場景中的一個重要變量。目前解決ETA預(yù)測問題的思路可以分為2大類：

第1類是基于路徑的ETA預(yù)測。這類方法要求從始發(fā)地到目的地的路徑是確定且唯一的，其思路通常通過捕獲每個子路段的時空相關(guān)性來把控對總預(yù)計到達時間的預(yù)估。Wang等人[2]利用Wide & Deep框架[3]增強模型對有效外部特征的記憶能力和泛化能力，并結(jié)合循環(huán)模塊捕獲時序特征完成到達時間的預(yù)估。Wang等人[4]在劃分子路徑的基礎(chǔ)上利用卷積層捕獲空間相關(guān)性，利用長短時記憶LSTM(Long Short-Time Memory)網(wǎng)絡(luò)捕獲時間相關(guān)性，最后預(yù)測完整路徑與各子路徑的到達時間。Zhang等人[5]提出了DeepTravel模型，在利用Bi-LSTM(Bidirectional Long Short-Time Memory)網(wǎng)絡(luò)[6]同時捕獲長期和短期的時間特征的基礎(chǔ)上完成路徑旅行時間的估算。為了建模路網(wǎng)中的異質(zhì)信息對于出行時間預(yù)測的影響,Hong等人[7]從建模路網(wǎng)中的異質(zhì)信息的角度完成了出行時間的預(yù)測。Fang等人[8]通過建模路段間的時空相關(guān)性和上下文信息來提升預(yù)測精準(zhǔn)度。Sun等人[9]通過建模和遷移駕駛員個性化信息提升到達時間預(yù)估精度。Fang等人[10]采用元學(xué)習(xí)[11]的思想通過對駕駛員歷史路徑的行駛習(xí)慣的捕獲來完成對未來路徑的行駛時間預(yù)測。雖然以上方法在實際中取得了較好的效果，但是現(xiàn)實生活中這類方法的弊端也非常明顯：其過分依賴從始發(fā)地到目的地的路徑。現(xiàn)實生活中有些場景的ETA問題是無法得到具體的任務(wù)路徑的，比如本文所要解決的攬件ETA問題。

第2類是基于OD的ETA預(yù)測。這類方法較為靈活，不需要指定具體路線。一般通過融合待預(yù)測任務(wù)的始發(fā)地、目的地和其他有效特征完成對到達時間的預(yù)估。Jindal等人[12]提出的STNN(Spatio-Temporal Neural Network)模型利用同時預(yù)測實際行駛距離和到達時間來提升時間的預(yù)估精度，但該模型缺乏對交通場景中時空相關(guān)性的具體思考。Li等人[13]利用道路網(wǎng)絡(luò)和時空先驗知識通過深度神經(jīng)網(wǎng)絡(luò)得到有意義的表示向量，并采取多任務(wù)學(xué)習(xí)輔助預(yù)測到達時間。但是，該方法對數(shù)據(jù)集要求過高，需要路網(wǎng)結(jié)構(gòu)和實際行駛距離等。Wang等人[14]通過始發(fā)地和目的地獲取相似軌跡集合，并通過相似軌跡預(yù)測目標(biāo)軌跡的行駛時間。但是，該模型需要得知駕駛員的行駛速度，且存在部分軌跡數(shù)據(jù)過少的數(shù)據(jù)稀疏問題。Zhu等人[15]針對快遞員外賣場景，提出OFCT(Order Fulfillment Cycle Time)模型，該模型通過設(shè)計深度模型選擇快遞員，并通過有效特征整合完成對用戶服務(wù)時間的預(yù)測。但是，該模型同樣對數(shù)據(jù)集要求過高，需要很多細化特征。

綜上，本文要解決的攬件ETA問題因為無法得知具體的任務(wù)路徑，因此更適合采用基于OD的思路解決?？墒?，目前基于OD思路解決ETA的方法又各有其局限性，無法高效準(zhǔn)確地預(yù)測攬件ETA。

3 模型介紹

3.1 相關(guān)定義

在攬件場景中，用戶在下單后，系統(tǒng)需要立刻將該訂單的預(yù)計完成時間發(fā)送給該用戶，并且之后不再改變。在預(yù)測時，快遞員手中還有其他未完成訂單，這些未完成訂單已經(jīng)完成了到達時間預(yù)測并且在等待攬收。本文將待預(yù)測到達時間的攬收訂單稱為目標(biāo)訂單，而快遞員手中的其他未完成訂單稱為已接未完成訂單。

(1)目標(biāo)訂單：本文將目標(biāo)訂單狀態(tài)定義為tar=(olng,olat,dlng,dlat,onum,oddis)。其中，olng和olat分別表示系統(tǒng)將目標(biāo)訂單分配給指定快遞員的時候，快遞員所在地點的經(jīng)、緯度坐標(biāo)；dlng和dlat分別表示目標(biāo)訂單攬收地點的經(jīng)緯度坐標(biāo)；onum表示系統(tǒng)將目標(biāo)訂單分配給指定快遞員的時候，快遞員手中已有的其他未完成訂單的數(shù)量；oddis表示從始發(fā)地到目的地的球面距離。

(2)已接未完成訂單集合：系統(tǒng)在給快遞員分配新訂單的時候，快遞員手中已有的其他待攬收未完成訂單統(tǒng)稱為已接未完成訂單(下文簡稱未完成訂單)，其定義為r=(dlng,dlat,tspend,tremain)，其中，dlng和dlat分別表示訂單攬收地點的經(jīng)、緯度坐標(biāo)，tspend表示相對當(dāng)前時刻該訂單距離被系統(tǒng)分配時刻已經(jīng)過去的時間，tremain表示該訂單距離超時的剩余履約時間。未完成訂單集合定義為R={r1,r2,…,rn}。

(3)攬件到達時間：本文將目標(biāo)訂單的攬件達到時間定義為Ttar=Tpick-Trequest，其中，Tpick表示目標(biāo)訂單的攬收時刻，Trequest表示用戶下單時刻。

(4)外部影響因素：日期、時段和目的地屬性等外部因素都會對目標(biāo)任務(wù)的預(yù)測時間產(chǎn)生影響。本文將外部因素日期定義為eday，外部因素時段定義為eperiod，外部因素目標(biāo)訂單目的地屬性定義為epoi，外部因素統(tǒng)稱為E={eday,eperiod,epoi}。

(5)問題定義：本文將攬件到達時間的預(yù)測問題定義為一個多變量回歸任務(wù)，如式(1)所示：

F(tar,R,E)→Ttar,TR,OR

(1)

即，給定待預(yù)測目標(biāo)訂單tar、未完成訂單R和外部特征E，本文的目標(biāo)是構(gòu)建一個多任務(wù)預(yù)測模型F，完成目標(biāo)訂單到達時間Ttar的預(yù)測，以及R的到達時間TR={Tr1,Tr2,Tr3,…,Trn}和R相對于目標(biāo)訂單的先后完成順序，也就是R在目標(biāo)訂單完成之前完成攬收還是在目標(biāo)訂單完成之后完成攬收，本文將其定義為OR={Or1,Or2,Or3…,Orn|Ori=0/1}。其中，預(yù)測Ttar為主任務(wù)，預(yù)測TR和OR為輔助任務(wù)。

Figure 1 Structure of MSTN4PAT圖1 MSTN4PAT模型結(jié)構(gòu)

3.2 MSTN4PAT模型

圖1展示了本文提出的MSTN4PAT模型的總體結(jié)構(gòu)，其主要由3部分組成，分別是OD時空特征模塊、時空多任務(wù)學(xué)習(xí)模塊和多源特征融合模塊。模型首先通過OD時空特征模塊建模目標(biāo)訂單的時空相關(guān)性；之后利用時空多任務(wù)學(xué)習(xí)模塊建模R對目標(biāo)訂單的影響；最后在融合模塊采用多頭注意力機制整合不同視角下R對于目標(biāo)訂單的影響，并從特征寬度和特征深度2個角度充分挖掘特征對預(yù)測的影響，以此最終實現(xiàn)目標(biāo)訂單的到達時間預(yù)估。圖1中，Lsubtask_order表示子任務(wù)順序預(yù)測損失，Lsubtask_time表示子任務(wù)時間預(yù)測損失，Ltarget為目標(biāo)任務(wù)預(yù)測損失，Lall表示總的預(yù)測損失，MLP(MultiLayer Perceptron)表示多層感知機。

3.2.1 OD時空特征模塊

OD時空特征模塊基于OD思路通過充分挖掘目標(biāo)訂單的始發(fā)地和目的地狀態(tài)特征，并充分建模外部特征，以此應(yīng)對預(yù)測時攬件路線不確定的挑戰(zhàn)。具體設(shè)計如圖1中OD時空特征模塊所示。

(2)

攬件到達時間受到多種不同外部因素的影響。所處日期不同，快遞員工作模式也會隨之發(fā)生變化，比如工作日和周末的交通路況變化可能會有很大的不同。此外，在不同的時段，系統(tǒng)分配的任務(wù)量不同，比如用戶更傾向于快遞員能在午飯、晚飯等時間完成攬收。并且攬收任務(wù)的目的地類型也會影響快遞員的決策模式，比如居民區(qū)和商業(yè)區(qū)的區(qū)別。本文分別用one-hot編碼對eday,eperiod和epoi進行建模，經(jīng)過信息嵌入之后得到特征向量Vday∈RD,Vperiod∈RD,Vpoi∈RD。

3.2.2 時空多任務(wù)學(xué)習(xí)模塊

對于目標(biāo)訂單來說，其不僅僅會受到外部特征和自身屬性的影響，還會受到未完成訂單集合R的影響。因此，要對目標(biāo)訂單到達時間實現(xiàn)準(zhǔn)確預(yù)測，必須考慮R的時空相關(guān)性，并建模R對于目標(biāo)訂單的影響。因此，本文設(shè)計了時空多任務(wù)學(xué)習(xí)模塊[16]，如圖1所示，來實現(xiàn)上述目的。

(3)

其中,Wr∈R4×D和br∈RD均為可學(xué)習(xí)參數(shù)。

Figure 2 Structure of order prediction layer圖2 順序預(yù)測層結(jié)構(gòu)

(4)

(5)

(6)

(7)

首先通過線性映射得到Qr、Kr和Vr，具體計算如式(8)～式(10)所示：

Qr=MrWq+bq

(8)

Kr=MrWk+bk

(9)

Vr=MrWv+bv

(10)

其中，Wq∈R(5D+2)×D,Wk∈R(5D+2)×D,Wq∈R(5D+2)×D,bq∈RD,bk∈RD,bv∈RD均為可學(xué)習(xí)參數(shù)，Qr、Kr和Vr將分別作為查詢、鍵和值參與后續(xù)的注意力機制運算。

注意力計算公式如式(11)所示：

(11)

其中，d為D除以頭數(shù)k之后的維度數(shù)，Q、K、V分別代表注意力機制計算中的查詢、鍵和值。

將得到的特征向量Qr、Kr和Vr輸入編碼塊中進行處理，每一個編碼塊包含多頭自注意力機制計算和MLP計算，則第l層的具體計算如(12)所示:

(12)

(13)

3.2.3 多源特征融合模塊

為了高效整合OD時空特征模塊和時空多任務(wù)學(xué)習(xí)模塊得到的特征，即捕獲不同特征之間的交互關(guān)系，本文設(shè)計了多源特征融合模塊，如圖1中多源特征融合模塊所示。

由于特征眾多，且特征間存在復(fù)雜的交互關(guān)系，本文參考Wide & Deep模型[3]對現(xiàn)有特征從寬度層面和深度層面兩個角度進行高效整合，設(shè)計了W&D融合層結(jié)構(gòu)，如圖3所示。

Figure 3 Structure of W&D fusion layer圖3 W&D融合層結(jié)構(gòu)

首先對特征進行拼接，得到融合特征向量Vmix∈RD,具體計算如式(14)所示：

(14)

Wide部分通過設(shè)計線性模型從特征寬度層面捕獲現(xiàn)有特征間的關(guān)系，從而增強模型的記憶能力。具體計算如式(15)所示：

(15)

其中Wwide和bwide均表示學(xué)習(xí)參數(shù)。

Deep部分通過設(shè)計深度神經(jīng)網(wǎng)絡(luò)從特征深度層面挖掘特征之間的關(guān)系，從而增強模型的泛化能力。具體計算如式(16)所示：

(16)

通過線性模型整合Wide部分和Deep部分使模型同時擁有記憶能力和泛化能力，提升特征融合質(zhì)量，完成更精準(zhǔn)的攬件到達時間預(yù)測。具體計算如式(17)所示：

(17)

其中，Wtarget和btarget均表示學(xué)習(xí)參數(shù)。

本文利用MAE損失函數(shù)對目標(biāo)訂單攬收到達時間進行監(jiān)督，具體計算如式(18)所示：

(18)

最后通過整合式(6)、式(13)和式(18)的全部損失函數(shù)對模型進行訓(xùn)練，具體計算如式(19)所示:

Lall=Lsubtask_order+Lsubtask_time+Ltarget

(19)

4 實驗與結(jié)果分析

4.1 數(shù)據(jù)集設(shè)置

本文的實驗數(shù)據(jù)集來自某快遞公司在2021年7月10日至2021年10月10日杭州15個運營區(qū)域 81 413條訂單攬收數(shù)據(jù)，以及上海20個運營區(qū)域96 453條訂單攬收數(shù)據(jù)。其攬收時間都在5 min～2 h。之后根據(jù)時間先后順序?qū)?shù)據(jù)集按照6∶2∶2比例劃分為訓(xùn)練集、驗證集和測試集。

4.2 基準(zhǔn)方法與評價指標(biāo)

本文將MSTN4PAT模型與如下7種現(xiàn)有的預(yù)測模型進行了對比。

(1)HA(History Average)：歷史平均值模型，根據(jù)始發(fā)地、目的地相似訂單的歷史平均攬收到達時間進行預(yù)測。

(2)LR(Linear Regression)：線性回歸模型，最基本的機器學(xué)習(xí)模型。

(3)STNN[12]：一種基于OD思路解決ETA問題的模型，該模型基于深度神經(jīng)網(wǎng)絡(luò)，首先預(yù)測給定 OD 對的行駛距離，然后結(jié)合出發(fā)時間來估計到達時間。

(4)XGBoost[18]：一種基于提升樹的機器學(xué)習(xí)模型，廣泛應(yīng)用在數(shù)據(jù)挖掘領(lǐng)域。

(5)DeepFM[19]和xDeepFM[20]：推薦系統(tǒng)領(lǐng)域可以建模不同特征相互作用的模型，在針對多源特征進行預(yù)測的時候具有較好的效果。

(6)OFCT[15]：一種應(yīng)用于外賣配送場景的基于OD思路解決ETA問題的模型，通過對離散特征和連續(xù)特征分別進行處理來完成送餐時間的預(yù)估。

評價指標(biāo)采用平均絕對誤差MAE和平均絕對百分比誤差MAPE(Mean Absolute Percentage Error)，計算過程分別如式(20)和式(21)所示：

(20)

(21)

4.3 參數(shù)設(shè)置

本文模型基于PyTorch深度學(xué)習(xí)框架實現(xiàn)，批量大小為128，學(xué)習(xí)率為0.001，采用Adam優(yōu)化算法。時間、時段和目的地類型外部特征分別用one-hot編碼建模成R7，R9和R35的向量。通過搜索超參的方法，得到如下最佳參數(shù)：神經(jīng)元維度D設(shè)為128，多頭注意力機制的頭數(shù)k設(shè)為8，編碼塊數(shù)L設(shè)為3，模型訓(xùn)練早停忍耐度設(shè)為10。

4.4 實驗結(jié)果

表1和表2分別列出本文提出的模型與上述7種基準(zhǔn)模型在杭州和上海數(shù)據(jù)集上的預(yù)測結(jié)果，其中，加粗數(shù)字表示最優(yōu)結(jié)果，帶下劃線數(shù)字表示次優(yōu)結(jié)果。從表1可以看出，本文提出的MSTN4PAT模型的MAE和MAPE指標(biāo)均優(yōu)于其他對比模型。相比于MAE指標(biāo)最優(yōu)的基準(zhǔn)模型XGBoost來說，本文模型的MAE提升了1.4%，相比于MAPE指標(biāo)最優(yōu)的基準(zhǔn)模型OFCT來說，本文模型的MAPE提升了2.29%。從表2可以看出，MSTN4PAT模型的MAE和MAPE指標(biāo)均優(yōu)于其他對比模型的。相比于MAE指標(biāo)上最優(yōu)的基準(zhǔn)模型XGBoost來說，本文模型的MAE提升了0.7%,相比于MAPE最優(yōu)的基準(zhǔn)模型OFCT來說，本文模型的MAPE提升了1.5%。

Table 1 Prediction performance of different models on Hangzhou dataset

HA通過快遞員的歷史平均送達時間對快件到達時間進行預(yù)測，沒有利用攬件場景中的時空相關(guān)性，因此效果最差。LR作為線性擬合模型，模型表示能力不足，難以建模影響攬件到達之間的眾多復(fù)雜因素。對于深度多任務(wù)模型STNN，由于實驗數(shù)據(jù)中沒有記錄快遞員的行駛距離，因此對于STNN的多任務(wù)學(xué)習(xí)中的行駛距離預(yù)測，使用OD間的球面距離替代，這導(dǎo)致了其模型性能下降。DeepFM和xDeepFM表現(xiàn)不是很好，說明單純對特征進行高階和低階的多重融合不能有效解決攬件到達時間預(yù)測問題。XGBoost表現(xiàn)較好，但是其MAPE值偏高，說明樹型模型對小值預(yù)測的誤差較高。綜合來看，OFCT的表現(xiàn)效果在所有基準(zhǔn)模型中最好。一方面，因為該模型所針對的外賣場景ETA預(yù)估問題和本研究問題相似，使得該模型在本文問題上的遷移性更強。另一方面，從技術(shù)角度來看，OFCT對離散特征和連續(xù)特征分別建模的做法有利于挖掘特征之間深層次的關(guān)系，從而達到更好的預(yù)測效果。相比于OFCT，本文提出的MSTN4PAT對未完成訂單、目標(biāo)訂單以及兩者的交互關(guān)系進行了充分建模，所以取得了最優(yōu)的效果。

4.5 消融實驗

為了進一步驗證模型各部分的有效性，本文在杭州數(shù)據(jù)集上設(shè)計了MSTN4PAT的3種變體進行對比實驗：(1)w/o order：減少時空多任務(wù)學(xué)習(xí)模塊中的順序預(yù)測子任務(wù)；(2)w/o time&order:減少時空多任務(wù)學(xué)習(xí)模塊中的順序預(yù)測子任務(wù)和未完成訂單的預(yù)估攬收時間預(yù)測子任務(wù)；(3)w/o W&D:將多源特征融合模塊中的W&D融合層換成特征拼接后用MLP進行特征融合輸出。

從圖4的實驗結(jié)果可以看出：(1)MSTN4PAT中多任務(wù)學(xué)習(xí)模塊能增強模型對R時空模式捕獲，從而幫助模型實現(xiàn)了更高精度的預(yù)測； (2)W&D融合模塊在面對多源特征融合的時候也表現(xiàn)出了較為優(yōu)越的特征融合能力。因此，實驗結(jié)果有效驗證了模型中各個模塊的合理性和有效性。

Figure 4 Ablation experiment results of MSTN4PAT圖4 MSTN4PAT消融實驗結(jié)果

5 結(jié)束語

本文針對快遞員攬件場景，提出了一種多任務(wù)時空攬件到達時間預(yù)測模型MSTN4PAT。針對攬件業(yè)務(wù)中，在預(yù)測時無法得知快遞員具體路線的挑戰(zhàn)，本文基于OD思路對目標(biāo)訂單進行攬件時間預(yù)估，并采用多任務(wù)學(xué)習(xí)機制建模未完成訂單對目標(biāo)訂單的影響，最后從特征深度和特征寬度2個角度進行特征融合，完成對目標(biāo)訂單攬件到達時間的預(yù)測。在真實的攬件數(shù)據(jù)集上的實驗結(jié)果表明，本文提出的模型優(yōu)于對比模型。