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

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

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

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

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

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

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

1 模型建立

1.1 問題描述

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

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

1.2 數(shù)學模型

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

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

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

（1）定義決策變量：

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

（2）設定優(yōu)化調度模型目標函數(shù)為總成本最?。?/p>

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

總運輸成本C1=u1cT

車輛使用成本C2=u2cV

時間成本C3=

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

2 算法設計原理及實現(xiàn)

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

2.1 訂單聚類

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

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

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

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

2.2 基于策略函數(shù)的待決策子集優(yōu)化

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

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

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

2.2.1 時間窗規(guī)則

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

2.2.2 發(fā)貨倉庫規(guī)則

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

2.2.3 裝載量規(guī)則

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

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

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

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

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

3 應用分析

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

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

3.2 系統(tǒng)搭建及測試方法

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

3.3 結果與分析

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

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

4 結論

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