基于“全局道段優(yōu)化模型”的末端配送作業(yè)模式

劉 芳，黃 康，羅 雕

（中國郵政集團有限公司郵政研究中心 技術(shù)應用研究中心，北京 100096）

1 概述

1.1 末端配送現(xiàn)狀

隨著電子商務(wù)的快速發(fā)展，中國快遞包裹數(shù)量急劇增加，根據(jù)國家郵政局監(jiān)測數(shù)據(jù)顯示，2019年全國快遞服務(wù)企業(yè)業(yè)務(wù)量累計完成635.2億件，同比增長25.3%[1]。隨之而來的投遞“最后一公里”問題也愈加突出，其表現(xiàn)為市場變化與資源配給平衡的沖突，客戶體驗與服務(wù)能力匹配的沖突，作業(yè)組織與成本控制的沖突。

從企業(yè)運營的角度，快遞末端配送模式主要包括：自營、第三方和共同配送。國家標準《物流術(shù)語》（GB/T18354-2001）對共同配送的定義是“由多個企業(yè)聯(lián)合起來組織實施的配送活動[2]。多個企業(yè)開展共同配送，可以有效降低配送成本，其機理是規(guī)模增大可以提高效率。末端共同配送是將共同配送的理念運用于城市配送中心到終端客戶的配送過程，是共同配送的一個子環(huán)節(jié)?？爝f末端配送方式包括：上門投遞、包裹柜自提、便利店自提、快遞公共服務(wù)站（如菜鳥驛站）、無人機投遞、投遞到車等。

快遞企業(yè)在運營過程中面臨諸多的困境。首先快遞行業(yè)末端配送成本占整個物流配送成本的比例居高不下，其原因主要包括：配送環(huán)節(jié)難以做到標準化、作業(yè)流程不合理、人車資源與任務(wù)不匹配等。其次，普遍存在“招人難”“留人難”的問題，一般招聘到配送人員后，經(jīng)過簡單培訓便開始上崗服務(wù)，導致配送人員的專業(yè)化程度較低、服務(wù)意識較差。在固定道段的作業(yè)組織模式下，業(yè)務(wù)量變化導致攬投網(wǎng)點的投遞人員富余或者不足，缺乏人力資源的合理調(diào)配手段。客戶對收件時間、地點、方式的個性化需求，商品品類多樣、規(guī)格不同，投遞區(qū)域的多樣性，都增加了投遞難度。派件員上門投遞時，無人在家導致投遞失敗，需要二次或多次投遞。這些因素也導致了對客戶的服務(wù)質(zhì)量無法保證[3]。

1.2 作業(yè)模式分析

末端配送無論采用哪種運營模式，其作業(yè)組織的關(guān)鍵都是攬投任務(wù)的分配，目前攬投網(wǎng)點普遍采用固定道段的作業(yè)組織模式對任務(wù)進行分配。道段指的是將網(wǎng)點覆蓋范圍劃分成一些無交集的子區(qū)域，固定意味著在較長一段時間內(nèi)道段組劃保持不變。

投遞道段組劃通常采用的原則包括：每條道段配備一名投遞員；保證投遞員在規(guī)定工時內(nèi)及時妥投郵件；各個投遞道段的勞動量基本平衡[4]。當遇到較大變化時，例如投遞員辭職、投遞部覆蓋范圍變化、增減代投點，則需要對道段做相應的調(diào)整。

固定道段作業(yè)組織模式的優(yōu)點是生產(chǎn)組織與管理相對容易，缺點是當業(yè)務(wù)量發(fā)生變化時，人工調(diào)配任務(wù)會增加管理成本、降低投遞效率，同時也會影響客戶服務(wù)質(zhì)量和投遞時限。

投遞部的道段組劃主要依賴人的經(jīng)驗。為了完成道段組劃任務(wù)，一方面生產(chǎn)組織者要與投遞員進行溝通，了解現(xiàn)有道段的業(yè)務(wù)量、地理特征、上門投遞占比等基本情況；另一方面通過實際生產(chǎn)來評估投遞員的投遞能力。然后經(jīng)過一段時期的磨合，最終給出道段組劃結(jié)果。雖然這種道段組劃方法能基本滿足實際生產(chǎn)需要，但是每次組劃周期較長，導致顯著增加管理成本、降低生產(chǎn)效率。

1.3 研究現(xiàn)狀

如何提升末端投遞效率、降低末端投遞成本、提供優(yōu)質(zhì)的投遞服務(wù)，成為快遞服務(wù)企業(yè)持續(xù)關(guān)注的問題。如何以數(shù)據(jù)為導向，從全局出發(fā)，運用運籌學、人工智能、機器學習等理論與技術(shù)，實現(xiàn)道段科學組劃和攬投任務(wù)合理分配，成為學術(shù)界和行業(yè)關(guān)注的焦點。

張慧敏研究了任務(wù)均衡下的快遞末端配送區(qū)域劃分及路徑優(yōu)化問題，根據(jù)任務(wù)均衡、配送分區(qū)規(guī)則，將研究問題轉(zhuǎn)化為小區(qū)之間的遍歷順序和小區(qū)內(nèi)部客戶節(jié)點遍歷順序兩個子問題[5]。谷煒提出了一種改進K-means 聚類算法的物流配送區(qū)域劃分方法[6]。王迪首先基于收貨點密度設(shè)計啟發(fā)式算法得到配送分區(qū)的初始解，之后采用禁忌搜索算法對分區(qū)結(jié)果進行優(yōu)化[7]。

順豐科技提出了智慧物流地圖的解決方案，在客戶下單、智能調(diào)度、中轉(zhuǎn)分揀、規(guī)劃運輸、末端配送等環(huán)節(jié)積累了大量數(shù)據(jù)，沉淀多種物流解決方案，提供貨車和騎行場景的高效路徑規(guī)劃服務(wù)，為業(yè)務(wù)賦能。針對收派難點，順豐科技提出了多維度的解決方案：通過郵件量預測，實現(xiàn)資源需求的預測；利用大數(shù)據(jù)，實現(xiàn)投遞員能力評估、訂單難度評估，從而使得任務(wù)與收派員最佳匹配；智能排班解決了收派業(yè)務(wù)中業(yè)務(wù)高峰低谷人力分配不均的實際問題[8]。

京東物流針對多時效產(chǎn)品、特定區(qū)域派送場景、時效優(yōu)先基礎(chǔ)上成本最低的業(yè)務(wù)需求，解決多種寬度時間窗下準確的派送路徑規(guī)劃推薦，實現(xiàn)了智能路徑優(yōu)化系統(tǒng)。該系統(tǒng)融合了目前業(yè)內(nèi)最領(lǐng)先的分支-切割算法、可變鄰域搜索、快速小鄰域局部搜索、元啟發(fā)式算法、分布式并行技術(shù)，融入了客戶收貨習慣、站點地址、訂單號、訂單時效、客戶收貨地址經(jīng)緯度、配送員當前坐標、配送員配送習慣等各項參數(shù)，在最大限度保持配送員現(xiàn)有配送節(jié)奏的前提下，實現(xiàn)以配送路徑最短的形式準確達成包括京準達訂單在內(nèi)的全部訂單配送的效果，滿足客戶更精準的需求[9]。

菜鳥物流云現(xiàn)已提供“車輛路徑規(guī)劃服務(wù)”，該服務(wù)將訂單信息和可用車輛信息進行智能匹配，結(jié)合多種限制因素，給出每輛車的最優(yōu)訂單配送順序和路徑。

2 解決方案

2.1 方案概述

柔性是系統(tǒng)所具有的有效應對環(huán)境變化的能力。柔性能力不僅僅是一種被動的應對變化的能力，更是一種主動的適應變化，甚至尋求變化的能力。將柔性理念應用于末端配送作業(yè)組織問題，可增強攬投網(wǎng)點的快速響應能力，高效率、低成本地滿足顧客的需求?；谌嵝岳砟詈蛿?shù)據(jù)驅(qū)動的方式，本文提出了動態(tài)末端配送作業(yè)組織模式的整體設(shè)計思路。

首先通過對攬投網(wǎng)點的網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計實現(xiàn)人車資源的共享；其次利用評估攬投網(wǎng)點現(xiàn)有投遞生產(chǎn)效率，選址引擎給出最佳的位置選擇方案；然后以基于柔性理念的道段作業(yè)組織模式進行末端網(wǎng)點的生產(chǎn)運營；最后融合大數(shù)據(jù)、人工智能、云計算等多種前沿技術(shù)實現(xiàn)智慧化的末端攬投生產(chǎn)與管理。

該設(shè)計思路包含四個視角：客戶視角，即采用多種渠道和手段滿足客戶多樣性需求、提升時效性和服務(wù)質(zhì)量；攬投員視角，即以動態(tài)道段的作業(yè)組織模式實現(xiàn)任務(wù)與資源的合理分配，釋放投遞效能；管理人員視角，即為管理員提供輔助管理手段，包括攬投監(jiān)控、資源預報、投遞部選址；第三方視角，通過協(xié)同方式構(gòu)建共享的人車資源池，實現(xiàn)末端共同配送。

道段組劃是末端配送作業(yè)組織的關(guān)鍵問題之一。針對道段組劃問題，本文提出了帶有投遞車裝載量、投遞員最大工作時長、客戶點時間窗等約束的“全局道段優(yōu)化模型”，以該模型為核心開發(fā)了“智能攬投管控平臺”系統(tǒng)，研發(fā)了排班排線引擎、經(jīng)緯度學習引擎、線路學習引擎和攬收調(diào)度引擎等。末端柔性道段組劃的出發(fā)點是突破固定的道段作業(yè)模式，按照郵件的流量流向來規(guī)劃任務(wù)分配和投遞線路，落腳點是合理均衡分配工作任務(wù)，從而使得整體效率達到最高。

2.2 場景設(shè)計

基于動態(tài)的作業(yè)組織生產(chǎn)環(huán)節(jié)包括：投遞郵件信息接收、排班排線計算、任務(wù)下發(fā)、郵件接收及內(nèi)場處理、掃描分揀下段、掃描裝車、投遞作業(yè)處理、攬收調(diào)度、攬投實時監(jiān)控和作業(yè)結(jié)束。系統(tǒng)處理流程如圖1所示。

郵件實物到達攬投機構(gòu)前，系統(tǒng)根據(jù)提前發(fā)送的郵件收寄信息、郵件修正信息、網(wǎng)運系統(tǒng)發(fā)送的郵件到達信息、投遞歷史數(shù)據(jù)、人員信息、車輛信息等，計算出當天所需作業(yè)人員，生成排班計劃，預告管理人員，管理人員根據(jù)實際情況調(diào)整確認，下發(fā)任務(wù)給攬投員。

圖1 系統(tǒng)處理流程

投遞部是按照生產(chǎn)作業(yè)頻次進行組織的，通常一天有三個作業(yè)頻次。當郵件處理中心的郵車將實物送達投遞部后，進行郵件交接，開始了第一個作業(yè)頻次。攬投員進行集中作業(yè)，每個人執(zhí)行郵件掃描，系統(tǒng)提示郵件所在的動態(tài)段號。掃描完所有郵件后，正常郵件已經(jīng)被確定所在的動態(tài)段號。

郵件按動態(tài)段號歸集分堆后，攬投員根據(jù)熟練程度，選擇下段裝車方式。對地址不熟悉的投遞員，可掃描郵件，系統(tǒng)提示出郵件投遞順序號，攬投員進行標識，最后按順序裝車。

攬投人員根據(jù)APP 指示路線出班作業(yè)，在到達下一個投遞點之前，系統(tǒng)自動發(fā)送預告投遞信息給收件人，并再次確認投遞方式。投遞員通過手持終端設(shè)備逐件對每個郵件的妥投或者未妥投等信息進行反饋。

攬投員在外場投遞作業(yè)過程中，產(chǎn)生的收寄訂單進行如下處理：本系統(tǒng)接收到寄件信息后，計算出適合的候選攬投員，投遞班長會實時看到訂單的處理情況，并可對異常情況進行處理。

投遞部接收完第二個頻次的郵件后，由內(nèi)勤人員對郵件進行掃描分揀下段。距離投遞部較近的投遞員返回投遞部取件，距離較遠的投遞員可不返回投遞部，由汽車將郵件運送交接點與投遞員進行交接，并將收寄的郵件和未投出去的郵件帶回投遞部。第三個生產(chǎn)頻次與第二個生成頻次的過程類似。

攬投人員完成全天任務(wù)后，將收寄郵件歸集到就近的攬投部或營業(yè)部，截郵時間前送達的，由趟車運回處理中心，截郵時間后送達的，由攬投部或營業(yè)部負責發(fā)出眾包信息，由社會車輛接單，運送至處理中心。無攬收郵件的攬投員，可上傳郵件面單照片，系統(tǒng)內(nèi)完成郵件平衡合攏，自動反饋郵件信息，結(jié)束全天任務(wù)，不必返回攬投部。攬投員車輛由第三方公司提供的，不必停放回攬投部。

2.3 “全局道段優(yōu)化模型”

“動態(tài)作業(yè)與線路規(guī)劃”功能的實現(xiàn)依賴于道段組劃數(shù)學模型，在該數(shù)學模型的基礎(chǔ)上，根據(jù)驗證方案，對模型與算法進行了驗證，并對模型效果進行分析。

模型描述：給定某個投遞頻次的待投郵件、郵件的投遞時限、投遞三輪車、若干名投遞員，在不超過最大工作時長、投遞車裝載量的前提下，分配投遞任務(wù)及規(guī)劃投遞線路，使得投遞員總工作時間、總行駛里程最少。

上述目標函數(shù)約束條件的含義如下：

式（1）表示優(yōu)化目標為總的行駛時間最少；

式（2）表示不同車型的裝載量約束；

式（3）表示每個投遞員的工作時長限制；

式（4）表示每個投遞點只能由某個投遞員負責投遞；

式（5）表示所有投遞員都從投遞部出發(fā)；

式（6）表示每位投遞員到達每個投遞點完成投遞任務(wù)后離開該投遞點；

式（7）表示所有投遞員都返回投遞部；

式（8）表示投遞點時間窗口約束；

式（9）表示路線和時刻表之間的相容性約束；

式（10）表示決策變量的取值范圍。

2.4 系統(tǒng)架構(gòu)與功能

針對上述業(yè)務(wù)場景及其業(yè)務(wù)處理流程，研發(fā)了“智能攬投管控平臺”系統(tǒng)，系統(tǒng)架構(gòu)如圖2 所示，該系統(tǒng)實現(xiàn)了6個核心功能。

圖2 系統(tǒng)架構(gòu)圖

（1）輔助選址。該功能提升攬投機構(gòu)整合、調(diào)整能力。我們提出了一種基于均勻分割和車輛路徑規(guī)劃的選址算法，該算法根據(jù)歷史郵件數(shù)據(jù)的分布，從全局投遞效率最優(yōu)的角度給出了投遞部的建議位置。

（2）作業(yè)量預測。該功能提高資源配置精確度，利用郵件的收寄信息及全程時限數(shù)據(jù)，預測投遞部未來7天的進口郵件量，并給出建議的人車資源配置。

（3）動態(tài)人員分配。該功能實現(xiàn)高效排班，投遞部進口郵件量存在較大的波動，在現(xiàn)有生產(chǎn)作業(yè)組織模式下，投遞部每天出班的人數(shù)基本固定，該系統(tǒng)利用未來7 天的作業(yè)量預測結(jié)果來合理地進行人員排班。

（4）動態(tài)作業(yè)與線路規(guī)劃。該功能實現(xiàn)柔性作業(yè)，在現(xiàn)有的作業(yè)組織模式下，道段基本固定，當郵件分布變化時，投遞效率不高，該系統(tǒng)根據(jù)投遞部每天的進口投遞郵件，動態(tài)地分配投遞任務(wù)及規(guī)劃投遞線路，克服了傳統(tǒng)固定道段不靈活的缺點。

（5）攬收調(diào)度。該功能提高派攬效率，根據(jù)所有正在外場作業(yè)投遞員的實時位置及攬收完成情況，在滿足攬收時限的前提下，智能計算出“搶單模式”下的任務(wù)分配方案，從而使得攬收響應速度更快、攬收成本更低。

（6）實時監(jiān)控。該功能實現(xiàn)管理賦能，管理員根據(jù)系統(tǒng)的實時監(jiān)控信息及時干預生產(chǎn)過程，對攬投生產(chǎn)進行質(zhì)量監(jiān)控。

2.5 “動態(tài)作業(yè)與線路規(guī)劃”功能的驗證

（1）驗證方案。在驗證階段，項目組與寄遞事業(yè)部的業(yè)務(wù)專家共同確定了智能攬投系統(tǒng)的驗證方案。在該方案基礎(chǔ)上，驗證的實施過程如下：首先進行生產(chǎn)寫實，即利用終端設(shè)備上安裝的App 采集實際生產(chǎn)的出歸班打卡時間、投交點位置以及處理時長，利用安裝在投遞車上的定位器記錄投遞員的行駛軌跡和行駛里程；其次排班排線引擎利用采集的數(shù)據(jù)計算出任務(wù)分配以及投遞線路；然后按照規(guī)劃的線路進行實跑并采集數(shù)據(jù)；最后將實際生產(chǎn)、系統(tǒng)規(guī)劃和系統(tǒng)規(guī)劃實跑的結(jié)果進行對比。

（2）驗證結(jié)果。在育新花園營業(yè)部、蘇家坨營業(yè)部和頤和園營業(yè)部分別進行了為期一周的驗證數(shù)據(jù)采集。數(shù)據(jù)采集時間從2020年7月13日至19日（不含17日），使用GPS定位器采集投遞員的行駛軌跡數(shù)據(jù)，使用App 打卡功能采集出歸班時間及客戶點服務(wù)時長。GPS定位器采集的數(shù)據(jù)情況見表1。

表1 GPS定位器采集的數(shù)據(jù)情況

（3）模型效果。針對模型驗證的行駛里程和工作時長指標，系統(tǒng)規(guī)劃結(jié)果與實際生產(chǎn)的對比結(jié)果見表2、表3，如圖3、圖4 所示，驗證結(jié)果表明系統(tǒng)規(guī)劃結(jié)果與實際生產(chǎn)的行駛里程和工作時長相比均減少10%以上。

表2 行駛里程對比結(jié)果

①總行駛里程節(jié)省13%以上。“全局道段優(yōu)化模型”充分考慮郵件的空間分布特征，并且為每位投遞員規(guī)劃最優(yōu)的投遞線路，使得總行駛里程節(jié)省13%以上。

②總工作時長節(jié)省11%以上。

③任務(wù)分配更均衡。

④投遞員工作時長更均衡。使用離散度（一組數(shù)據(jù)與其均值的絕對偏差的平均值）來衡量工作時長的均衡性。2020年7月19日一頻次實際工作時長的離散度為36.3，規(guī)劃工作時長的離散度為30.6。

⑤模型適用性強?！叭值蓝蝺?yōu)化模型”對投遞部的覆蓋范圍、投遞員數(shù)量沒有要求，無需歷史數(shù)據(jù)的學習就可以給出規(guī)劃結(jié)果。

⑥排班排線算法框架具備可拓展性。排班排線算法框架易于拓展，算法需調(diào)整的參數(shù)少，除了可以求解標準的VRP 之外，還能夠求解VRPPD，MDVRP等變形問題。

在項目驗收測試中，實跑測試驗證選擇了10 月23日育新攬投部的一頻次進口包裹快遞數(shù)據(jù)。

實跑測試結(jié)果見表4，測試結(jié)果表明：

①系統(tǒng)規(guī)劃結(jié)果與實際生產(chǎn)相比，總行駛里程和總工作時長均節(jié)省10%以上，平均工作時長節(jié)省5%。

表3 工作時長對比結(jié)果

圖3 郵件分配情況對比

圖4 工作時長對比

②系統(tǒng)規(guī)劃的實跑結(jié)果與實際生產(chǎn)相比，總行駛里程和總工作時長均節(jié)省10%以上，平均工作時長節(jié)省10%。

表4 實跑測試對比結(jié)果

3 結(jié)論

基于流量流向的“全局道段優(yōu)化模型”可以優(yōu)化人車資源分配，與現(xiàn)有固定道段的投遞作業(yè)模式相比，有如下幾個方面的優(yōu)化提升：

（1）當投遞業(yè)務(wù)量發(fā)生較大變化時，實現(xiàn)人車資源與投遞任務(wù)相匹配，從而提升整體生產(chǎn)效率。

（2）在投遞業(yè)務(wù)量高峰期，讓沒有投遞經(jīng)驗的人快速進入內(nèi)場分揀角色、投遞角色，提升投遞能力。

（3）在投遞業(yè)務(wù)量減少的情況下，通過排班排線規(guī)劃引擎實現(xiàn)了投遞任務(wù)合理分配，釋放出部分投遞員，使得他們有更多時間去開展攬收業(yè)務(wù)。

（4）對于新成立的網(wǎng)點，排班排線引擎無需磨合期即可給出合理的道段組劃方案。

（5）基于“搶單模式”的智能攬收調(diào)度引擎使得攬收響應速度更快、成本更低。

4 研究展望

采用基于動態(tài)的末端配送作業(yè)模式，不但需要有準確且較完備的收寄信息、穩(wěn)定的全程時限，還需要有準確且較完備的投遞作業(yè)數(shù)據(jù)、地理信息、多維度的客戶以及攬投員數(shù)據(jù)，因此我們將在設(shè)計動態(tài)作業(yè)組織的數(shù)據(jù)構(gòu)建方案基礎(chǔ)上，進一步擴展“全局道段優(yōu)化模型”開展智能接力投遞系統(tǒng)的研究。