安裕強(qiáng)，徐躍明，歐陽世波，李圣毅

1.紅云紅河煙草（集團(tuán)）有限責(zé)任公司物流中心，昆明市紅錦路367號(hào) 650000

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

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

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

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

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

1 模型建立

1.1 問題描述

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

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

1.2 數(shù)學(xué)模型

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

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

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

（1）定義決策變量：

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

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

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

總運(yùn)輸成本C1=u1cT

車輛使用成本C2=u2cV

時(shí)間成本C3=

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

2 算法設(shè)計(jì)原理及實(shí)現(xiàn)

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

2.1 訂單聚類

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

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

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

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

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

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

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

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

2.2.1 時(shí)間窗規(guī)則

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

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

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

2.2.3 裝載量規(guī)則

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

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

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

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

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

3 應(yīng)用分析

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

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

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

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

3.3 結(jié)果與分析

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

表4 機(jī)器學(xué)習(xí)算法與其他兩種算法調(diào)度結(jié)果對比Tab.4 Comparison of schedule decisions made by machine learning-based algorithm，accurate algorithm and genetic algorithm

4 結(jié)論

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