基于機器學習的成品卷煙銷售訂單配送調度優化算法研究與應用

安裕強，徐躍明，歐陽世波，李圣毅

1.紅云紅河煙草（集團）有限責任公司物流中心，昆明市紅錦路367號 650000

2.昆明理工大學管理與經濟學院，昆明市景明南路727號 650000

3.馬來西亞博特拉大學經濟學院，馬來西亞雪蘭峩州沙垱 434000

成品卷煙銷售訂單的配送調度是卷煙工業企業物流管理的重要環節，也是物流管理優化決策的核心問題。針對該問題國內學者已有較多研究，任曉智等［1］基于智能化策略輔助啟發式算法優化了配送中心選址，并設計了求解大規模原問題的方法。李存兵等［2-3］通過引入工作量均衡指標，提出了改進的雙層遺傳算法，并通過實驗驗證了該算法相比單層遺傳算法性能更優；基于加權糅合構建了綜合目標模型，并設計了精英自適應遺傳聚類算法進行求解。張丹羽［4］按照分級調度的思路，采用聚類方法獲得配送節點中心區域，再利用改進的C-W法求解每個區域中的最短路徑。鄒霞［5］在分級優化的基礎上，引入時間窗設計了改進里程節約法，用于求解動態同城配送優化模型。劉昕雨［6］、方偉華［7］采用類似于圖計算方法求解調度優化問題。禹旺明［8］基于蟻群算法提出了多回路車輛調度問題模型，并在卷煙企業進行了驗證。徐明元［9］提出了改進型染色體編碼方法以及不同蟻群分工的遺傳算法和多態蟻群算法，提高了求解效率。潘國鵬［10］針對單調度中心，非滿載，具有最大配送里程約束、載重約束、軟時間窗約束的大規模純卸貨的路線優化問題，設計了改進信息素計算機制的蟻群算法。李蒙龍等［11］提出了基于任務分層模型的優化調度方法，可減小問題求解過程中的解搜索空間。馮子炎等［12］通過構造合適的遺傳算子，設計了用于解決帶時間窗的車輛路徑規劃問題（Vehicle Routing Problem，VRP）的遺傳算法。肖正中等［13］采用邊界分配法將多起點轉化為單起點車輛調度問題，并結合遺傳算法與蟻群算法求解跨區域配送尋優問題。章惠民［14］提出了一種改進的柔性線路截取優化算法，實現了車輛利用率最大化以及配送里程最小化目標。

而國外的研究主要集中在卷煙等快消品配送調度優化方面。Desrochers等［15］研究了帶有時間要求的配送服務問題，通過將原問題分解成受限主問題和子問題，利用列生法逐步迭代求解主、子問題，能夠獲得在客戶節點規模（約100個）較大情況下的可靠解法。Gendreau等［16］、Bullnheimer等［17］、Baker等［18］針對裝載量限制、行駛路程限制的單配送中心的VRP問題，分別利用禁忌搜索算法、蟻群算法和遺傳算法進行求解，并對不同啟發式算法的求解效率進行對比。Thangiah［19］研究了多配送中心下的配送優化問題，提出了一種利用遺傳算法對客戶聚類，再通過嵌入式啟發算法求解的方法。Dethloff［20］將配送優化從純卸貨問題擴展到沿途混合裝卸，并設計了啟發式算法進行求解。Br?ysy等［21］探討了啟發式算法的特性和評價準則，針對時間窗VRP問題，分析比較了路徑構造和路徑優化兩種啟發式算法的求解效率。Novoa等［22］研究了隨機需求下的VRP問題，通過將優化目標設定為期望路徑最短，并利用Rollout回溯算法進行求解，解決了車輛動態執行臨時配送任務的調度問題。Fleszar等［23］研究了開放式VRP問題，提出了一種變鄰域搜索算法求解該問題。Baldacci等［24］對比了求解裝載量限制VRP和時間窗VRP兩種問題的精確算法，提出了一種整數規劃的割平面方法。Rahmawan等［25］針對快消品公司PT X TBK存在的配送問題，通過引入容量限制、路徑沖突限制，以及采用基于活動掃描的離散時間仿真方法，提高了資源使用效率，增加了客戶滿意度。

雖然目前關于配送車輛調度、配送路徑優化的研究較多，但針對卷煙工業企業成品卷煙銷售訂單配送調度問題的研究則鮮有報道，在實踐中配送調度主要依靠人工經驗決策，存在著工作效率低、管理不科學、人工作業量大等問題。針對此，王保中［26］基于求解VRP數學模型是典型NP-hard問題，通過改進蟻群算法解決了煙草物流線路優化問題；楊燕霞等［27］對模擬場景抽象處理，通過減少約束條件降低求解難度，也獲得了可行解。上述研究結果表明啟發式算法具有可行性，但存在對模型參數依賴度高［8］、問題模型簡化后過于理想等問題，導致求解結果難以應用于生產實踐。此外，若求解規模過大，啟發式算法還容易出現收斂速度慢或者全局搜索能力下降等問題［28］。為此，首先將待調度的成品卷煙銷售訂單進行凝聚聚類，然后利用專家策略函數和機器策略函數構建搜索樹，再根據業務規則構造調度優化評價函數進行配送調度決策［29］，進而設計了一種基于機器學習的智能配送調度算法并對其進行模擬仿真，以期提高卷煙成品銷售訂單配送調度效率，實現調度決策支持。

1 模型建立

1.1 問題描述

卷煙工業企業的客戶一般是按照地級市行政區設置商業企業，每個地級市有且只有一個煙草商業企業，因此工業企業配送主要為干線運輸。考慮到調度后實際運輸業務并不會立即發生，且中間還存在一個倉儲發貨作業時間，故在調度時將路網簡化為時序靜態的、點與點之間有且僅有一條路徑的有向圖，不考慮多路徑選擇及擁堵、過路費高低等因素。工業企業通常擁有若干個發貨倉庫，且發貨倉庫間的庫存結構存在差異。由于卷煙運輸實行法定準運證制度，即每個訂單必須對應一個由行政管理部門簽發的有時效的準運證，且訂單必須在時效內完成交付。該制度還要求同一個訂單不能分別在兩個或兩個以上倉庫拆分出庫，當發貨倉庫庫存結構與訂單需求不匹配時，可以采用將各發貨倉庫的庫存移庫至中心庫集中配貨方式。此外，訂單及訂單對應的準運證和承運車輛只能是“多對一”關系，即一輛貨車可以承運總和不超過其裝載量上限、不低于其裝載量下限的多個訂單，每個訂單只能由一輛車承運，不能同一訂單分車裝運。

因此，成品卷煙銷售訂單配送調度優化問題可以歸納為：某一配送調度周期內，工業企業根據客戶下達的訂單，綜合考慮運輸路線、庫存結構、承運車輛，以及由訂單要求到貨日期、準運證時效組成的時間窗口，通過合理組拼訂單完成車貨匹配，確定發貨倉庫和發貨日期，進而實現時間窗條件下運輸配送成本最低。

1.2 數學模型

在決策時點上，工業企業會接收到一個由M個客戶在時間周期P內下達的R個訂單組成的訂單池，訂購在銷的K批次的T個規格的成品卷煙。定義O表示訂單，設第m個客戶下達的第r個訂單為且∈Om∈O。定義artk表示訂單包含的批次為k∈K且規格為t∈T的卷煙數量。定義時間區間表示訂單的要求到貨時間窗，即時間窗范圍為要求到貨日期當天上午9點至下午3點之間。設定車輛運輸標準速度v為650 km/d，從貨物啟運至送達的在途時間為，其等于發貨倉庫和客戶倉庫之間距離與標準速度v的比值，故訂單最晚出發時間為此外，準運證時效為要求到貨日期下限時間后的48 h內，即為

用NS表示發貨倉庫，i∈NS，第i個發貨倉庫出庫能力上限為Hi；用NC表示客戶倉庫，客戶倉庫集合定義為NC=｛uj｜j∈M｝；定義一個由發貨倉庫和客戶倉庫以及倉庫之間基于地理路網組成的權值有向圖G=（N，A），其中N=NS∪NC，A=N×N。以遼寧省為例，采用基于地理路網的權值有向圖表示客戶倉庫網絡空間關系權值有向圖。用arc（i，j）表示有向圖中第i個倉庫到第j個倉庫的路徑，以兩倉庫間的運輸距離作為路徑權重wij，見表1。τij表示兩倉庫間的運輸在途時間，τij=wij/v。如果i∈NS，則表示裝貨時間；如果i∈NC，則表示卸貨時間。

定義sitk表示發貨倉庫i∈NS包含的批次為k∈K且規格為t∈T的成品卷煙庫存數量，第i個發貨倉庫的庫存總數如果車輛在時間窗下限之前到達客戶倉庫，將產生因等待卸貨而帶來的承運機會損失成本；如果車輛在時間窗上限之后、準運證到期之前到達，將產生因延遲到貨而帶來的客戶滿意度損失成本；如果車輛在準運證到期之后到達，將產生違規經營成本。B表示可調配車輛的集合，對于任意發貨倉庫i∈NS，Bi表示發貨倉庫i可調配車輛的集合，Gbll表示車輛b∈B的裝載量下限，Gbsl表示裝載量上限。

（1）定義決策變量：

dbi=車輛b從i點出發的時間，dbi∈R+，?b∈B，?i∈N

（2）設定優化調度模型目標函數為總成本最小：

f=min（c），令c=C1+C2+C3

總運輸成本C1=u1cT

車輛使用成本C2=u2cV

時間成本C3=

式中：u1表示運輸里程，表示運輸成本，元/km；u2表示執行任務的車輛數量，輛；cV表示每輛車的使用成本，元/輛；cX表示每輛車因提前到達產生的承運機會損失成本，每等待1 h記1個單位成本；cM表示因延遲到貨產生的客戶滿意度損失成本，每延遲1 h記1個單位成本；cL表示因準運證過期產生的違規經營成本，元。

2 算法設計原理及實現

由圖1可見，本研究中設計的算法流程主要分為3步：一是對待調度成品卷煙銷售訂單構成的原問題集聚類，將業務規則和車貨匹配歷史數據作為聚類中心，使用凝聚聚類（Agglomerative Clustering，AC）進行訂單合并并重復此步驟，從而縮小原問題規模；二是將歷史銷售訂單組拼記錄作為算法的數據樣本，構建一個基于歷史數據的專家策略函數作為優先策略，并采用蒙特卡洛搜索建立搜索樹，再構建一個基于地理空間有向圖的機器策略函數作為次級策略，采用與優先策略相同的方法建立搜索樹；三是建立一個由業務規則組成的調度優化評價函數，對搜索樹評價剪枝，確定搜索樹結果。由此實現訂單組拼和車貨匹配結果的智能決策。在下一次調度優化中利用包含最近一次調度結果在內的歷史數據樣本對部分聚類規則及專家策略函數進行迭代，進而實現算法迭代。

2.1 訂單聚類

任何時點待調度成品卷煙銷售訂單構成的原問題集，都會存在具有相同關鍵特征的訂單，這些關鍵特征包括客戶、客戶倉庫、訂單號、需求結構（規格、批次和數量）、要求到貨日期、發貨倉庫，共6個。如果訂單的全部或部分關鍵特征相同，那么就可以將其合并為一類，即凝聚聚類，將小訂單組合成大訂單。當大訂單達到經濟運輸規模，且要求到貨時間窗和發貨倉庫庫存結構均滿足約束的情況下，可以直接獲得大訂單的調度結果，無需作為原問題集輸入模型求解。

由于原問題集中訂單的關鍵特征均為字符串數據，為了量化關鍵特征進而通過度量實現凝聚聚類，需要將關鍵特征數據轉變為多維的0-1稀疏矩陣，即將訂單數據進行歐式空間化。首先，以訂單號為主鍵值，將客戶、客戶倉庫兩個關鍵特征的字符串數據分別轉化為各自維度上的0-1變量，構成聚類空間中的兩個維度。其次，根據訂單需求結構和庫存結構，構造兩個維度的0-1矩陣，再進行矩陣運算，獲得每個發貨倉庫維度上的0-1變量。例如，發貨倉庫現有A、B、C、D、E共5個批次為1的卷煙規格，訂單ID.1需求結構為A規格1批次50萬支，B規格1批次120萬支，各發貨倉庫的庫存結構見表2。當發貨倉庫庫存滿足訂單需求結構時，發貨倉庫維度上相應的向量值取1，否則取0。最后，要求到貨日期啞變量化，根據作業準備期和在途運輸時間，能夠推算出每個訂單的要求發貨日期，進而獲得發貨日期維度上的0-1啞變量。

表2 發貨倉庫WH 1～WH 4庫存情況Tab.2 Inventories of warehouse WH 1-WH 4（萬支）

對完成關鍵特征歐式空間化的訂單數據，使用凝聚聚類將其歸入不同的類并添加類標簽，然后類標簽為同一發貨倉庫、同一客戶倉庫、同一發貨日期的訂單直接輸出調度結果，并將達到經濟運輸規模，且要求到貨時間窗和發貨倉庫庫存結構均滿足約束的訂單從原問題集中剔除，從而將訂單分為已調度和待調度兩類，待調度訂單形成新的原問題子集，由此縮小調度問題規模。

2.2 基于策略函數的待決策子集優化

待調度子集是由聚類后關鍵特征離散的訂單組成，基于機器學習的智能配送調度算法的核心是在路線優化的基礎上對這些訂單進行車貨匹配決策，以實現總成本最小目標。分析可見，遍歷所有可能的組合并評估目標函數是獲得最優解的最佳方式，但遍歷所需的深度和廣度顯然是不可接受的。為此，算法模擬人工在調度中采用的“按圖索驥”搜索方式，基于蒙特卡洛搜索設計了具備優先級差異的兩個策略函數，用于控制決策空間搜索的深度和廣度，從而實現對待決策子集的優化。

將待調度子集R0original作為初始狀態s0，在子集中選擇距離發貨倉庫最遠，即max（wi）j的一個訂單r0，r0∈R0original，作為初始節點并創建搜索樹。搜索樹的分支首先由數據樣本中的專家策略確定，只有當初始狀態s0不具備專家經驗時，才以次級的基于客戶網絡空間關系權值有向圖的機器策略替代專家策略。在專家策略下，訂單r0會存在若干歷史組拼方式，定義p（a｜s0，R0resul）t表示初始狀態s0下，專家經驗中R0result訂單與初始節點訂單r0歷史上已有的各種組拼方式出現的概率。由于決策當期內的成本、里程、車輛、庫存結構相比各歷史決策期不會發生突變，因此可以將pr≠0的組合組成策略空間Aexpe（rts，R），并認為其是近似最優策略空間。

首先，根據初始節點訂單r0的客戶、客戶倉庫、訂單號、需求結構（規格和批次）、要求到貨日期、發貨倉庫6個關鍵特征，從歷史銷售訂單組拼記錄中抽取客戶、客戶倉庫兩個關鍵特征與初始節點有過組拼的訂單，組成歷史訂單集R0history，求解待調度子集R0original與歷史訂單集R0history的交集R0result=R0history∩R0original，訂單r0與訂單集R0result就組成一棵二級搜索樹；如果不具備專家經驗，以基于客戶網絡空間關系權值有向圖獲得的距離矩陣作為關鍵特征，在R0original中抽取距離wij滿足閾值的訂單組成訂單集R0result，并與訂單r0組成二級搜索樹。其次，利用需求結構、要求到貨日期、發貨倉庫3個關鍵特征，對初始狀態s0下的二級搜索樹進行剪枝，即在搜索中調用組合評價函數，進而找到初始狀態下s0與r0的最優組合。組合評價函數是一個規則引擎，評價和判斷當前狀態下哪種組合較優的核心規則是按順序將時間窗、發貨倉庫、裝載量三者相互協調。

2.2.1 時間窗規則

成品卷煙物流是具備時間窗的約束問題。因此，首先評價二級搜索樹中訂單組拼時間窗的協調程度。初始節點訂單r0的時間窗為，可以與r0進行組拼配送的訂單是需要滿足時間窗協調的訂單ri∈且其最晚到貨時間必須滿足dr（iorder_3pm）≥dr（0order_3pm）+wr0ri/v。

2.2.2 發貨倉庫規則

由于經過凝聚聚類后原問題子集中的訂單需求結構已歐式空間化處理，因此可以直接與同樣經過歐式空間化處理的發貨倉庫庫存結構進行矩陣運算，獲得每個發貨倉庫數據維度上的0-1變量，并使用“訂單是同一個發貨倉庫”的規則，對已經過時間窗規則剪枝的二級搜索樹再次剪枝。

2.2.3 裝載量規則

由于成品卷煙物流是規模效益顯著的經濟活動。因此，裝載量規則的核心是車輛滿載率盡可能不低于下限并趨于100%，故滿足發貨倉庫規則的訂單r0的訂單數量可以建立關系：

其中，車輛上限Gbsl由歷史上服務過訂單r0客戶頻次最高的車型決定。對于ri∈，取GapR為最小值的訂單ri與r0組合。以沈陽市煙草公司為例，相應裝載量數據見表3。

表3 裝載量數據（以沈陽市煙草公司為例）Tab.3 Loading capacity data，e.g.Shenyang Tobacco Company

如果多個組合同時均滿足3個規則，則根據p(a|s0，）的大小決定組合的取舍。經過基于策略函數構建的搜索樹決策后，將訂單r0和ri從待決策的訂單池中剔除，將待決策訂單池從初始態s0更新為下一個狀態s1，并繼續迭代搜索決策，直至狀態sn中剩余訂單均無法滿足評價函數。利用線性規劃模型對剩余訂單求解，其中目標函數中的運輸成本cT取與承運商簽訂合同中約定的單價，單車使用成本cV按照車型進行經驗賦值，提前到達產生的承運機會損失成本cX取每等待1 h記1個單位成本，延遲到貨產生的客戶滿意度損失成本cM取每延遲1 h記1個單位成本。

隨著配送調度決策結果的不斷積累，每期調度決策可使用的歷史數據也不斷增加，專家策略空間的規模逐步增大。當時間足夠長時，專家策略空間將會取代基于客戶網絡空間關系權值有向圖的機器策略網絡，并趨近于當前狀態下的全部策 略 空 間 ，即由 此 可 以 減少算法時間載荷和硬件載荷，提高求解效率，并通過歷史數據不斷積累實現算法訓練，使策略函數越來越符合實際調度業務場景，進而使輸出的待決策子集逐步符合模型約束。

3 應用分析

3.1 數據采集

采集紅云紅河集團2020年4月28日至30日需調度的100個客戶下達的584個成品卷煙銷售訂單，訂單合計配送卷煙191 574.68萬支。輸入的基礎數據包括決策期內紅云紅河集團的生產入庫計劃及庫存、各發貨倉庫可用車輛、2016—2019年歷史銷售訂單組拼記錄、準運證有效期、距離矩陣、運輸里程和時間等。

3.2 系統搭建及測試方法

本研究中算法采用PYTHON（3.6.2版）進行編程，主要調用機器學習庫（Scikit-learn，0.21.3版）、數據分析和處理工具庫（Pandas，0.25.3版；Numpy 1.16.2版），運行在配置主頻2.3 GHz的酷睿i5-6200計算機上。為進一步驗證機器學習算法的性能，基于同一計算平臺使用相同的樣本訂單和基礎數據，分別采用數學規劃模型GUROBI求解器精確求解方法、時間窗VRP問題的遺傳算法求解方法［12］，綜合比較3類算法求解的使用車輛數量及結構、運輸里程、時間成本以及多點組合車次數占比（單一車輛服務多個客戶）。

3.3 結果與分析

由表4可見，對基于機器學習算法、精確算法、遺傳算法求解出的結果進行數據分析。相較于精確算法和遺傳算法，機器學習算法求解的使用車輛數分別減少19輛和14輛，運輸里程分別減少2 595和3 682 km，時間成本分別減少195個單位成本和75個單位成本，多點組合車次數分別增加11.75和8.0百分點。表明機器學習算法對于訂單調度具有更好的決策性能，多點組合車次數占比明顯提高，時間成本得到有效控制，使用車輛數和運輸里程在3種算法中均為最低。

表4 機器學習算法與其他兩種算法調度結果對比Tab.4 Comparison of schedule decisions made by machine learning-based algorithm，accurate algorithm and genetic algorithm

4 結論

為提高卷煙工業企業成品卷煙銷售訂單配送調度效率，降低配送成本，設計了一種基于機器學習的智能配送調度算法。采用紅云紅河集團2020年4月部分成品卷煙銷售訂單作為樣本數據，對機器學習算法、精確算法、遺傳算法3種算法進行對比測試，結果表明：在相同樣本數據和基礎數據前提下，機器學習算法相較于精確算法和遺傳算法，使用車輛數分別降低13.28%和10.14%，運輸里程減少5%和7.2%，時間成本減少68%和45%，多點組合車次數分別增加11.75和8.07百分點。表明機器學習算法具有更好的收斂速度和收斂精度，可以快速求得配送調度問題的最優解，提高卷煙成品配送調度效率。由于機器學習算法存在訓練集規模大、訓練速度慢等問題，未來研究中將基于真實卷煙銷售訂單數據構建智能機器學習數據庫，從而為成品卷煙銷售訂單預測以及根據學習經驗數據庫自動生成智能調度方案提供支持。