基于XGBoost 的卷煙送貨時(shí)間預(yù)測(cè)仿真模型研究*

張 超 宋 偉 胡 鵬 陳 輝 汪 明 全 鵬

（1.中國(guó)煙草總公司湖北省公司 武漢 430030）（2.武漢大學(xué)計(jì)算機(jī)學(xué)院 武漢 430072）（3.湖北省煙草公司十堰市公司 十堰 442099）

1 引言

由于卷煙配送系統(tǒng)中，客戶所處地點(diǎn)、卷煙的銷售量，以及交通路線，都會(huì)隨著時(shí)間發(fā)生改變。因此，我們必須定期自適應(yīng)地更改卷煙的物流配送路線。然而，定期改變配送路線，存在一系列的風(fēng)險(xiǎn)與挑戰(zhàn)。首先，配送時(shí)長(zhǎng)與送達(dá)時(shí)間是評(píng)估配送路線的重要指標(biāo)。雖然可以使用人工經(jīng)驗(yàn)來(lái)衡量配送路線，但這顯然無(wú)法高效地對(duì)比大量路線方案，也無(wú)法保證始終得到高準(zhǔn)確的評(píng)估結(jié)果。我們的現(xiàn)有系統(tǒng)中缺少高效的路線方案對(duì)比的相關(guān)功能；其次，配送路線的改變，是高成本與長(zhǎng)周期的。根據(jù)我們的經(jīng)驗(yàn)，一次配送路線的改變，會(huì)至少耗費(fèi)2 個(gè)月到5 個(gè)月的時(shí)間，用于小范圍使用實(shí)車進(jìn)行試點(diǎn)配送、優(yōu)化路線方案、擴(kuò)大試點(diǎn)范圍、把方案投入實(shí)際使用等流程；最后，由于新配送路線不一定盡善盡美，因此在試運(yùn)行期間，我們無(wú)法準(zhǔn)確把控卷煙的配送時(shí)長(zhǎng)與送達(dá)時(shí)間，這會(huì)影響我們的服務(wù)質(zhì)量，從而降低用戶的體驗(yàn)。

為降低傳統(tǒng)卷煙配送路線調(diào)整帶來(lái)的不利影響，本文提出一套卷煙配送時(shí)間預(yù)測(cè)仿真模型，運(yùn)用模擬仿真理論、XGBoost 模型和數(shù)字地圖，對(duì)配送路線時(shí)間進(jìn)行更精確的模擬仿真，降低調(diào)整配送路線所需的成本與時(shí)間。與此同時(shí)，為客戶預(yù)測(cè)精確的預(yù)計(jì)送達(dá)時(shí)間，提高服務(wù)質(zhì)量與服務(wù)滿意度，為卷煙物流路線優(yōu)化提供了一種有效的輔助工具。

2 問(wèn)題分析

卷煙送貨時(shí)間預(yù)測(cè)仿真有三個(gè)核心部分：配送總時(shí)長(zhǎng)預(yù)測(cè)仿真、單戶行車時(shí)間預(yù)測(cè)和單戶上門服務(wù)時(shí)間預(yù)測(cè)。

2.1 配送總時(shí)長(zhǎng)預(yù)測(cè)仿真

配送總時(shí)長(zhǎng)預(yù)測(cè)仿真模擬了車組進(jìn)行一次配送的全部流程，包括配送車從出發(fā)到返回、完成路線上所有需要送貨的客戶的卷煙配送，并得到配送流程的整體時(shí)間。

我們的卷煙配送流程如下：物流中心或中轉(zhuǎn)站發(fā)出車組，按照送貨上門、客戶核查與簽收、配送下一戶的流程嚴(yán)格執(zhí)行。一對(duì)一服務(wù)每一位客戶，手把手送達(dá)每一份貨物，直至完成所有的配送任務(wù)，各車組返回出發(fā)點(diǎn)。具體流程見圖1。

圖1 單個(gè)車組配送作業(yè)流程

從圖1 可知單個(gè)車組配送總時(shí)長(zhǎng)=去往送貨區(qū)行車時(shí)間+送貨區(qū)工作時(shí)間（多個(gè)單戶服務(wù)時(shí)間）+回物流中心行車時(shí)間。

圖2是圖1中的單戶送貨流程，單戶服務(wù)時(shí)間=單戶行車時(shí)間+單戶上門服務(wù)時(shí)間。配送總時(shí)長(zhǎng)預(yù)測(cè)仿真包含下述三條特征：

1）連續(xù)兩戶的送貨流程與簽收流程的發(fā)生時(shí)間是隨機(jī)的。這是因?yàn)槊績(jī)晌豢蛻糁g的路程不同、不同客戶的簽收速度不同，因此單戶上門服務(wù)所耗費(fèi)的時(shí)間也不同。綜上，單戶服務(wù)時(shí)間是不確定的，是一個(gè)離散事件。

2）每天需要卷煙送貨的客戶也是隨機(jī)的。每個(gè)車組每天的配送任務(wù)是變化的，且按周循環(huán)。在添加動(dòng)態(tài)路線規(guī)劃系統(tǒng)后，我們可以依照當(dāng)天的客戶訂單數(shù)據(jù)，合理規(guī)劃每個(gè)車組每天的送貨數(shù)量、路線、客戶，生成配送任務(wù)，配送任務(wù)也是隨機(jī)的。

3）將一系列單戶送貨流程事件進(jìn)行排序，以達(dá)到對(duì)配送路線時(shí)間的仿真。事件必須按序發(fā)生，不可調(diào)序或略過(guò)，并且不同事件的分類清晰明白。

通過(guò)上述三條特征，我們的卷煙送貨路線時(shí)間預(yù)測(cè)防震的需求，符合“離散事件-事件調(diào)試法”（下文簡(jiǎn)稱“事件調(diào)試法”）應(yīng)用特點(diǎn)。因此，我們的模型采用“事件調(diào)試法”為理論來(lái)源。

“事件調(diào)試法”是面向事件的，不僅詳盡保存事件的發(fā)展流程，還會(huì)處理事件發(fā)生時(shí)系統(tǒng)狀態(tài)的變化結(jié)果。王鐵寧等［1］采用變步長(zhǎng)的推進(jìn)方法，推進(jìn)一次仿真時(shí)鐘，記錄和處理一個(gè)事件發(fā)生所引起的狀態(tài)變化。本文以十堰煙草物流中心為例，設(shè)計(jì)的卷煙送貨時(shí)間預(yù)測(cè)仿真模型。

2.2 單戶行車時(shí)間預(yù)測(cè)

我們以十堰卷煙配送任務(wù)為例。在這個(gè)案例下，物流管控平臺(tái)會(huì)根據(jù)卷煙的銷售數(shù)據(jù)安排客戶的配送順序，生成配送任務(wù)。該任務(wù)將于兩日后被車組配送。每個(gè)車組每天根據(jù)客戶配送順序、兩戶之間的路徑連接形成配送路線，按配送路線完成80個(gè)到150個(gè)單戶配送任務(wù)。因此，為更好地實(shí)現(xiàn)配送路線的預(yù)測(cè)和仿真，我們重點(diǎn)關(guān)注兩位客戶間的路程與時(shí)間的預(yù)測(cè)。

目前，市面上已有多款成熟的電子地圖軟件，可以根據(jù)設(shè)定的起點(diǎn)與終點(diǎn)，計(jì)算兩者之間的路程與時(shí)間。這可以幫助我們獲取路網(wǎng)、實(shí)時(shí)路況等重要信息，實(shí)現(xiàn)兩位客戶之間的路徑計(jì)算。比如我們熟知的百度地圖API，就可以依據(jù)道路歷史運(yùn)行數(shù)據(jù)、海量用戶數(shù)年的大數(shù)據(jù)積累等，綜合得到導(dǎo)航信息，為我們提供高準(zhǔn)確率的起點(diǎn)與終點(diǎn)間的距離與時(shí)間，甚至可以提供路線上紅綠燈數(shù)量以及預(yù)計(jì)等待時(shí)間。綜上所述，配送路線的預(yù)測(cè)，可以借助使用合適的電子地圖軟件來(lái)實(shí)現(xiàn)。本文直接采用成熟的電子地圖工具（Baidu Map API）來(lái)實(shí)現(xiàn)兩位客戶之間的行車時(shí)間和路徑的預(yù)測(cè)。

2.3 單戶上門服務(wù)時(shí)間預(yù)測(cè)

在本文中，上門服務(wù)包括配送員到達(dá)客戶收貨點(diǎn)，卸貨，把煙包交付給客戶，客戶檢查煙包，若沒(méi)有問(wèn)題則確認(rèn)簽收，配送員返回車輛并整理煙包（可能有），啟動(dòng)車輛繼續(xù)給下一位客戶配送的時(shí)間。卷煙物流配送應(yīng)用中，客戶上門服務(wù)時(shí)間受到諸多不確定因素影響，如配送方案調(diào)整、實(shí)時(shí)路況、前置送貨時(shí)間等，這些數(shù)據(jù)特征具有明顯的不確定性，而且在配送路線上后方配送客戶的服務(wù)時(shí)間不確定性會(huì)由于前期配送任務(wù)的不確定性而累加。因此單戶上門服務(wù)時(shí)間預(yù)測(cè)是一個(gè)不確定、時(shí)序關(guān)聯(lián)的復(fù)雜學(xué)習(xí)目標(biāo)。據(jù)我們所知，XGBoost 被認(rèn)為是非常適合于數(shù)據(jù)缺失和不確定數(shù)據(jù)場(chǎng)景的機(jī)器學(xué)習(xí)方法，被廣泛地應(yīng)用于運(yùn)動(dòng)預(yù)測(cè)、商品銷售預(yù)測(cè)、文本分類、行為預(yù)測(cè)等領(lǐng)域［1～4］，結(jié)合單戶上門服務(wù)時(shí)間預(yù)測(cè)任務(wù)的服務(wù)特點(diǎn)，本文利用XGBoost模型預(yù)測(cè)單戶上門服務(wù)時(shí)間。

2.4 國(guó)內(nèi)外研究現(xiàn)狀

近年來(lái)，隨著物流配送、共享單車、基于位置服務(wù)等各種新形態(tài)應(yīng)用的興起，路徑調(diào)度優(yōu)化研究得到越來(lái)越多的來(lái)自工業(yè)界和學(xué)術(shù)界的重視。遺傳算法是一種模擬生物自然選擇的算法模型，很多學(xué)者基于遺傳算法和各種改進(jìn)優(yōu)化算法對(duì)路徑調(diào)度優(yōu)化問(wèn)題開展研究［5～15］。現(xiàn)有研究關(guān)注了路徑優(yōu)化算法的優(yōu)化效率和算法收斂速度，但目前針對(duì)卷煙物流配送任務(wù)中多優(yōu)化目標(biāo)、數(shù)據(jù)不確定、數(shù)據(jù)缺失問(wèn)題的路徑優(yōu)化研究還很少，這是本研究的主要研究動(dòng)機(jī)。

3 預(yù)測(cè)仿真模型的構(gòu)建

3.1 卷煙配送時(shí)長(zhǎng)預(yù)測(cè)仿真模型

由事件調(diào)度法仿真鐘的推進(jìn)過(guò)程得出模型算法：

T 表示完整配送路線的配送時(shí)長(zhǎng)；n 表示需要配送服務(wù)的客戶數(shù)目，n≥1；TRij代表客戶i 與j 間的單戶行車時(shí)間，i，j=0，1，…，n，i≠j；TRoi、TRn0依次表示配送車從當(dāng)前位置到第i 個(gè)客戶的行車時(shí)間、客戶n到配送起點(diǎn)的行車時(shí)間，i=1，…，n。

TLi表示單戶上門服務(wù)花費(fèi)的總時(shí)間，包括配送人員到達(dá)第i 個(gè)客戶的收貨地點(diǎn)后，卸貨并把貨物送到客戶手中的時(shí)間、客戶核驗(yàn)貨物并簽收的時(shí)間、配送人員返回配送車耗費(fèi)的時(shí)間、整理煙包時(shí)間（可能有）、啟動(dòng)車輛時(shí)間，i=1，…，n。

式（1）說(shuō)明：

1）一組車組的配送總時(shí)長(zhǎng)=單戶服務(wù)時(shí)間之和+返回物流中心或中轉(zhuǎn)站的行車時(shí)間；

2）單戶服務(wù)時(shí)間=單戶行車時(shí)間+單戶上門服務(wù)時(shí)間。

根據(jù)式（1），送貨時(shí)間預(yù)測(cè)的準(zhǔn)確性由單戶行車時(shí)間和單戶上門服務(wù)時(shí)間兩個(gè)因素決定。

3.2 單戶行車時(shí)間計(jì)算方法

式（2）說(shuō)明xi、yi，依次代表客戶ui的經(jīng)度和緯度，i，j=1，…，n，且i≠j。MAPAPI 表示調(diào)用電子地圖API，計(jì)算出任兩個(gè)客戶的車行時(shí)間、車行距離。

3.3 單戶上門服務(wù)時(shí)間計(jì)算方法

XGBoost 適用于回歸、分類問(wèn)題，單戶上門服務(wù)時(shí)間預(yù)測(cè)屬于回歸模型，表示為式（3）。

式（3）說(shuō)明fk代表某一函數(shù)，K代表函數(shù)迭代次數(shù)，xi、yi表示第i個(gè)樣本特征和預(yù)測(cè)值。

建立預(yù)測(cè)回歸模型時(shí)，需要尋找最優(yōu)的參數(shù)，其目標(biāo)函數(shù)為式（4）。

式（4）說(shuō)明為損失函數(shù)是預(yù)測(cè)值與目標(biāo)值之間的差值，為正則化項(xiàng)。

式（5）說(shuō)明yi、yi代表是第i個(gè)歷史簽收數(shù)據(jù)樣本值和預(yù)測(cè)值，n 是個(gè)數(shù)，l 是誤差函數(shù)，fk是第k 顆樹。

正則化項(xiàng)式（6）說(shuō)明：T 代表葉子節(jié)點(diǎn)數(shù)量，ωj表示葉節(jié)點(diǎn)權(quán)重。此時(shí)目標(biāo)函數(shù)為

其中t 代表訓(xùn)練輪次，constant 為前t-1 顆樹正則化項(xiàng)之和。

最后建立決策回歸樹，計(jì)算方法為

4 實(shí)證驗(yàn)證

為驗(yàn)證論文方法的有效性，構(gòu)建了基于XG?Boost的卷煙送貨時(shí)間預(yù)測(cè)原型系統(tǒng)對(duì)論文提出方法進(jìn)行驗(yàn)證。原型系統(tǒng)基于Python構(gòu)建，搭建了B/S 系統(tǒng)用于十堰市卷煙配送路徑優(yōu)化。實(shí)驗(yàn)數(shù)據(jù)來(lái)自十堰市2019-2020 年的卷煙物流簽收數(shù)據(jù)信息，采用MySQL 存儲(chǔ)，共91 萬(wàn)條數(shù)據(jù)。實(shí)驗(yàn)過(guò)程中，卷煙送貨時(shí)間預(yù)測(cè)仿真模型驗(yàn)證流程共有5 個(gè)步驟：數(shù)據(jù)采集、數(shù)據(jù)處理、數(shù)據(jù)特征提取、樣本劃分、預(yù)測(cè)及分析。

4.1 數(shù)據(jù)采集

采集2019年1月至2020年12月十堰市煙草公司卷煙物流簽收記錄，共91萬(wàn)條物流數(shù)據(jù)。

4.2 數(shù)據(jù)處理

由于原有物流數(shù)據(jù)質(zhì)量問(wèn)題，我們首先清洗了原有數(shù)據(jù)中缺乏重要信息的基礎(chǔ)數(shù)據(jù)。并基于電子地圖擴(kuò)展了網(wǎng)點(diǎn)中任意兩點(diǎn)之間的路程與時(shí)間，這些信息是使用電子地圖API 獲取的。清洗后共有67.1萬(wàn)條數(shù)據(jù)。

4.3 數(shù)據(jù)特征提取

物流數(shù)據(jù)維度很大，為提高算法效率首先提取必要數(shù)據(jù)特征，形成16 維數(shù)據(jù)集，16 維列名分別是：配送時(shí)間（年月日）、配送時(shí)間周數(shù)、淡旺季標(biāo)志、路線名稱、路線編碼、起點(diǎn)編號(hào)、起點(diǎn)經(jīng)緯度、終點(diǎn)編號(hào)、終點(diǎn)地理經(jīng)緯度、送貨數(shù)量（煙包數(shù)）、送貨數(shù)量（條）、出發(fā)時(shí)間（時(shí)分秒）、服務(wù)結(jié)束時(shí)間（時(shí)分秒）、行車時(shí)長(zhǎng)（s）、行車路程（m）、單戶上門服務(wù)時(shí)長(zhǎng)（s）。

總結(jié)清洗過(guò)的單戶上門服務(wù)時(shí)長(zhǎng)數(shù)據(jù)，得到表1，可以看到，標(biāo)準(zhǔn)差為77s，服務(wù)平均時(shí)長(zhǎng)為94s，與我們跟車調(diào)查得到的實(shí)際數(shù)據(jù)相吻合。

表1 單戶服務(wù)時(shí)長(zhǎng)統(tǒng)計(jì)表

4.4 樣本劃分

2019年1月至2020年10月數(shù)據(jù)，劃分訓(xùn)練集；

2020 年11 月至12 月數(shù)據(jù)，劃分為驗(yàn)證集，驗(yàn)證集少“單戶上門服務(wù)時(shí)長(zhǎng)（s）”數(shù)據(jù)特征。

4.5 預(yù)測(cè)及分析

驗(yàn)證集數(shù)據(jù)共1，083（條次）路線，配送總時(shí)長(zhǎng)的預(yù)測(cè)準(zhǔn)確率為92.11%，詳情見表2。

表2 預(yù)測(cè)結(jié)果統(tǒng)計(jì)表

可以看到，配送總時(shí)長(zhǎng)預(yù)測(cè)仿真可以達(dá)到較高的準(zhǔn)確率。同時(shí)，我們收集了一天內(nèi)每條配送路線的配送總時(shí)長(zhǎng)預(yù)測(cè)值，并記錄單條路線預(yù)測(cè)的最大偏差值。以2020 年12 月2 日，共26 條路線的預(yù)測(cè)數(shù)據(jù)為例，時(shí)間預(yù)測(cè)仿真準(zhǔn)確率是高達(dá)93.86%，與驗(yàn)證集所在月份的的整體預(yù)測(cè)值大致相同，因此這是具有代表性的數(shù)據(jù)。我們將預(yù)測(cè)偏差定義為真實(shí)送貨時(shí)長(zhǎng)與預(yù)計(jì)送貨時(shí)長(zhǎng)的絕對(duì)差值，26 條配送路線的配送時(shí)長(zhǎng)預(yù)測(cè)偏差均值為0.6h，除三條路線外，預(yù)測(cè)偏差均低于一小時(shí)。

至于相同路線中的單戶服務(wù)時(shí)間，選則路線“1-1-1-周一”，上午8 時(shí)4 分，送貨車于物流中轉(zhuǎn)站出發(fā)，仿真車輛也隨之出發(fā)，共為15 位客戶提供服務(wù)后返回，送貨車與仿真車輛的時(shí)間偏差小于十分鐘。

4.6 準(zhǔn)確率統(tǒng)計(jì)

卷煙送貨時(shí)間仿真模型時(shí)間預(yù)測(cè)準(zhǔn)確率見表3。

表3 模型時(shí)間預(yù)測(cè)準(zhǔn)確率統(tǒng)計(jì)

在實(shí)際配送工作中，存在一些不可預(yù)測(cè)的事件或不可抗力對(duì)模型的預(yù)測(cè)產(chǎn)生干擾，剔除這些因素后，模型預(yù)測(cè)準(zhǔn)確率應(yīng)該還會(huì)有所提升。

5 結(jié)語(yǔ)

5.1 結(jié)論

本文基于卷煙送回的真實(shí)流程，研發(fā)出一種離散性卷煙送貨路線時(shí)間預(yù)測(cè)仿真模型。與實(shí)際送貨數(shù)據(jù)相比，我們可以達(dá)到92.11%的配送總時(shí)長(zhǎng)的預(yù)測(cè)準(zhǔn)確率，和85.36%的客戶預(yù)計(jì)送達(dá)時(shí)間預(yù)測(cè)準(zhǔn)確率。本模型實(shí)現(xiàn)了對(duì)整條配送路線時(shí)長(zhǎng)與各單戶服務(wù)時(shí)間的精準(zhǔn)預(yù)測(cè)。通過(guò)比較不同的仿真送貨路線，降低物流中心更改送貨路線帶來(lái)的時(shí)間與人力代價(jià)，提高服務(wù)質(zhì)量，提升用戶體驗(yàn)。在之后的工作中，我們將持續(xù)研究仿真模型與電子地圖結(jié)合，發(fā)展可視化路線仿真、收貨預(yù)提示、多區(qū)域集中可視化調(diào)度等功能及應(yīng)用，通過(guò)可視化展示更改路線后配送車的行駛路線，更加高效智能地調(diào)度車輛，調(diào)整配送路線，為智慧物流發(fā)展帶來(lái)案例。

5.2 討論

本模型輸出的是數(shù)據(jù)及統(tǒng)計(jì)報(bào)表是靜態(tài)的文本工具，存在查看便利性不足的問(wèn)題，而本仿真模型可與電子地圖軟件結(jié)合，實(shí)現(xiàn)卷煙物流可視化模擬仿真，即將規(guī)劃好的路線，在地圖上進(jìn)行仿真運(yùn)行，對(duì)仿真情況實(shí)時(shí)語(yǔ)音播報(bào)，可以使得路線查看更加直觀、物流管理調(diào)度更加方便；添加到貨預(yù)提醒等功能及應(yīng)用，進(jìn)一步擴(kuò)充仿真模型應(yīng)用場(chǎng)景，達(dá)成現(xiàn)代化的卷煙送貨任務(wù)管理。