廣告 | 點擊查看

摘要：為提升物流中心卷煙分揀調度工作效率，本文以“云南煙草現(xiàn)代物流綜合業(yè)務管理平臺”卷煙分揀調度系統(tǒng)為研究對象，通過對物流業(yè)務中卷煙訂單分解及分揀平衡調度處理流程進行分析，提出一種基于貪心算法（Greedy algorithm）的卷煙分揀調度數(shù)據(jù)處理模型。通過對原始數(shù)據(jù)進行排序，先從分揀“卷煙條數(shù)”單一維度入手，分析并建立了貪心算法數(shù)學模型，再根據(jù)制定的貪心策略對第二維度因素“訂單戶數(shù)”進行調整，從而構建了一個精度可控的數(shù)據(jù)處理模型，使分揀總量在卷煙條數(shù)和訂單戶數(shù)兩個維度上能較平衡地分配到各分揀線，實現(xiàn)分揀平衡調度流程的整體優(yōu)化，避免人為進行二次調整的現(xiàn)狀，從而提升分揀調度工作效率。結果表明，與原系統(tǒng)數(shù)據(jù)處理方式相比，貪心算法節(jié)省了人為二次調整所需的時間30～40分鐘。且結果中各組數(shù)據(jù)之間分布更均勻，數(shù)據(jù)分布離散程度降低了75%，平衡調度效果顯著。

關鍵詞：煙草物流；訂單分解；貪心算法；平衡調度

作者：牟乾 李昌珮 黃欣 薛盛元 趙曉柳

云南省煙草公司昆明市公司物流分公司

近年來，隨著煙草企業(yè)數(shù)字化轉型的深入推進，信息技術在煙草物流業(yè)務中的有效運用大幅降低了生產成本，提高了生產效率[1]。卷煙分揀調度是煙草物流業(yè)務中一個重要環(huán)節(jié)，對于物流中心而言，卷煙分揀調度效率直接關系到配送服務，關系企業(yè)經濟效益的實現(xiàn)、卷煙零售戶滿意度的提高，甚至企業(yè)核心競爭力的提升。昆明市煙草公司物流分公司在用的“云南煙草現(xiàn)代物流綜合業(yè)務管理平臺”以營銷系統(tǒng)為計劃源頭，相繼處理銷售訂單結轉、分揀調度、物流排程、運力調度等，各業(yè)務模塊環(huán)環(huán)緊扣，相互關聯(lián)緊密，業(yè)務執(zhí)行按照既定流程由上至下順序流轉。在現(xiàn)行的卷煙分揀調度模式下，由于各業(yè)務環(huán)節(jié)前后關聯(lián)緊密，因此各環(huán)節(jié)中不合理、處理滯后等問題將直接影響后續(xù)工作，形成蝴蝶效應[2]，造成分揀效率的大幅下降。因此，合理優(yōu)化分揀各環(huán)節(jié)作業(yè)流程，有效縮短各環(huán)節(jié)流轉時間，提升各環(huán)節(jié)工作效率，對提升整體分揀效率具有重要的研究意義和現(xiàn)實意義。

一

問題分析

現(xiàn)行工作模式下，昆明市煙草公司物流分公司每個訂單日要處理兩個批次的分揀平衡調度任務。其中，上午處理T+0（當天送達）批次，為城區(qū)直送業(yè)務；下午處理T+1（第二天送達）批次，涉及各縣級分公司和中轉站配送業(yè)務。

昆明市煙草公司物流分公司在用的分揀設備為6條自動化分揀線。在實際工作中，為節(jié)約搬運和裝車時間，6條分揀線按照1、3、4號線和2、5、6號線分成兩組，分別對應就近的兩部貨運電梯搬運發(fā)貨，對應不同發(fā)貨目的地，便于裝車。經過統(tǒng)計分析，“云南煙草現(xiàn)代物流綜合業(yè)務管理平臺”分揀調度相關流程及耗時情況如圖1所示。

圖1 分揀調度相關流程及耗時示意圖

在處理訂單分解任務時，現(xiàn)行系統(tǒng)雖能將每一批次的分揀量較均勻地分配到各條分揀線上，但并沒有考慮按貨運電梯位置分組的實際需要，且訂單分解均勻程度不夠，需人工進行二次調節(jié)。由于人工介入調節(jié)，需要額外的時間完成平衡調度工作，尤其在第二批次分揀量較大、線路較多的情況下，經驗豐富的操作人員平均需要30～40分鐘進行二次調節(jié)，大大降低了分揀調度作業(yè)效率。

二

解決思路

為提升分揀調度作業(yè)效率，縮短平衡調度耗時，提升平衡調度均勻程度，有效的做法是盡量避免人工二次調節(jié)，通過一定算法由計算機直接按實際需求將訂單分解，實現(xiàn)自動平衡調度，節(jié)約人力成本和時間成本。

首先需要將所有訂單數(shù)據(jù)按貨運電梯與分揀線的位置關系進行分組，將分揀量均勻分成A（1、3、4號分揀線）、B（2、5、6號分揀線）兩組，再在各組中將分揀量均勻分到各分揀線，從而實現(xiàn)平衡調度優(yōu)化。

這一問題可抽象成一個數(shù)學模型進行分析，即由n個作業(yè)組成的作業(yè)集，可由m臺相同機器加工處理，要求給出一種作業(yè)調度方案，使所給的n個作業(yè)在盡可能短的時間內由m臺機器加工處理完成，作業(yè)不能拆分成更小的子作業(yè)，且每個作業(yè)均可在任何一臺機器上加工處理。這是一個NP（Non-deterministic Polynomial）完全問題，即多項式復雜程度的非確定性問題，目前還沒有有效的求最優(yōu)解解法[3]。

目前求解NP問題的方法主要有模擬退火算法（Simulated annealing）、遺傳算法（Genetic algorithm）、神經網絡算法（Neural network algorithm）和動態(tài)規(guī)劃（Dynamic programming）等[4]。其中模擬退火算法是通過賦予搜索過程一種時變且最終趨于零的概率突跳性，從而可有效避免陷入局部極小并最終趨于全局最優(yōu)的串行結構的優(yōu)化算法[5]；遺傳算法是仿真生物遺傳學和自然選擇機理，通過人工方式所構造基因并進行交叉變異的方法，尋求最優(yōu)解[6]；神經網絡算法是根據(jù)人腦神經連結方式，即神經對能量的接受并不是立即作出響應，而是將它們累加起來，當這個累加的總和達到某個臨界閾值時，它們將它們自己的那部分能量發(fā)送給其它的神經[7]；動態(tài)規(guī)劃（Dynamic programming）是求解決策過程最優(yōu)化的數(shù)學方法，其把多階段過程轉化為一系列單階段問題，利用各階段之間的關系，逐個求解，從而解決過程整體優(yōu)化問題[8]。

以上討論的幾種算法均能較好地處理NP問題，但在實際場景中，由于數(shù)學建模過程較復雜，超出本例平衡調度問題實際需求，因此本文采用貪心算法來解決本例提出的NP問題。

貪心算法（Greedy algorithm）的基本思路是從問題的某一個初始解出發(fā)一步一步地進行，根據(jù)某個優(yōu)化策略，每一步都要確保能獲得局部最優(yōu)解。每一步只考慮一個數(shù)據(jù)，數(shù)據(jù)的選取應該滿足局部優(yōu)化的條件。若下一個數(shù)據(jù)和部分最優(yōu)解連在一起不再是可行解時，就不把該數(shù)據(jù)添加到部分解中，直到把所有數(shù)據(jù)枚舉完，或者不能再添加算法為止[9]。貪心算法并不是對所有問題都能得到整體最優(yōu)解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個狀態(tài)以前的過程不會影響以后的狀態(tài)，只與當前狀態(tài)有關。

與動態(tài)規(guī)劃相似，貪心算法在解決最優(yōu)解問題時可以把整體優(yōu)化問題拆分成一個個的子問題，求子問題的最優(yōu)解。而貪心算法是動態(tài)規(guī)劃方法的一個特例，可以證明每一個子問題的解不取決于整體狀況，而只取決于當前問題的狀況。由于貪心算法的這個特性，它對解空間樹的遍歷不需要自底向上，而只需要自根開始，選擇最優(yōu)的路，就能展開至結束[10]。

三

基于貪心算法的處理流程

用貪心算法來解決由m臺相同機器加工處理n個作業(yè)組成的作業(yè)集問題。當n≤m時，只要將作業(yè)按數(shù)量分配給機器即可；當n>m時，首先要將n個作業(yè)按作業(yè)量從大到小排序，然后依此順序將作業(yè)分配給空閑的機器處理。也就是說從剩下的作業(yè)中，選擇需要處理時間最長的，然后依次選擇處理時間次長的，直到所有的作業(yè)全部處理完畢，或者機器不能再處理其他作業(yè)為止。

圖2 基于貪心算法的處理流程

如圖2所示，利用貪心算法把整體平衡優(yōu)化問題化解成若干子問題，再對每一子問題進行優(yōu)化求解，得到子問題的局部最優(yōu)解，最后把子問題的局部最優(yōu)解合成原問題的一個整體優(yōu)化解。具體可分為幾個步驟完成：

步驟一：根據(jù)貨運電梯與分揀線的位置關系，用貪心算法將全部分揀量均勻分解成A、B兩個組；

步驟二：檢查分組結果是否滿足貪心策略，若滿足則進入下一步，不滿足返回上一步重新計算；

步驟三：運用貪心算法，根據(jù)實際需求加入適當貪心策略，分別在兩組數(shù)據(jù)中對分揀量進行平衡分配；

步驟四：檢查平衡分配結果是否滿足貪心策略，若滿足則進入下一步，不滿足返回上一步重新計算；

步驟五：上一步計算所得各分揀線分揀任務量即為優(yōu)化問題的解，計算結束。

四

試驗

為檢驗該算法實用性，隨機選取昆明市煙草公司物流分公司某日T+1批次的實際生產數(shù)據(jù)，對數(shù)據(jù)進行貪心算法處理，處理結果與目前在用系統(tǒng)的結果進行對比。包含配送線路、訂單條數(shù)和訂單戶數(shù)等信息的原始分揀數(shù)據(jù)參見表1。

表1 昆明市煙草公司物流分公司某日T+1批次分揀數(shù)據(jù)

表1中不同線路代碼對應不同配送線路，運用貪心算法將分揀數(shù)據(jù)分解成兩組，并結合業(yè)務實際制定以下規(guī)則：

1.線路cg、fm、sm必須分配在A組，線路an、jn、yl必須分配在B組；

2.線路dc、xd由于分揀量通常均較大，必須分配到不同組；

3.其余各條線路被分配到A組或B組均可，必要時可將其中某一條或幾條線路按線路編號打散分配至不同組別間的分揀線；

4.分組結果與分揀總量的條平均值和戶平均值間的偏差均不超過5%。

對以上數(shù)據(jù)按線路歸類，并按分揀條數(shù)降序排列后，根據(jù)以上貪心策略進行分組，所得結果參見表2。

表2 貪心算法對分揀總量分組結果

通過計算，組平均值為128689.5，戶平均值為1384.5，分組后A組條偏差和戶偏差分別為：0.16%、1.26%，B組條偏差和戶偏差分別為0.16%、1.26%，符合設定要求。

下一步，分別在各組中用貪心算法對分揀任務進行分配，各組貪心策略相同，分配步驟為：

步驟一：對各組數(shù)據(jù)進行升序排序，按從多到少的順序依次將分揀任務分配至各分揀線；

步驟二：按照局部最優(yōu)原則，當各分揀線條分揀量與分揀線條平均值間的偏差小于5%時，停止對該分揀線分配任務，依次分配直至將組內所有任務分配完畢；

步驟三：計算各分揀線戶分揀量與分揀線戶平均值間的偏差，若小于5%即符合要求，大于或等于5%時在組內進行調整，最終滿足分配要求。

表3 整批次平衡調度結果

根據(jù)上述步驟，得出以上表3結果，并計算6條分揀線的條平均值為42896.5條，戶平均值為461.5戶。各分揀線條偏差和戶偏差計算結果參見表4。

表4 貪心算法平衡調度結果偏差

將基于貪心算法的試驗結果與目前在用系統(tǒng)自動平衡調度結果進行比較，參見表5。從表5可以看出，利用貪心算法進行平衡調度后，各條分揀線的條偏差值和戶偏差值均明顯下降，更趨近于任務總量在各分揀線上的條平均值和戶平均值，平衡調度效果顯著。

表5 系統(tǒng)自動平衡與貪心算法平衡結果對比

為直觀比較貪心算法與系統(tǒng)自動平衡調度結果的離散程度，計算兩種方法所得調度結果的方差和標準差參見表6。表6可以看出，貪心算法計算所得結果標準差較小，表明貪心算法較系統(tǒng)算法能更好地將分揀任務均勻分布在各分揀線。圖4直觀地反映了貪心算法計算所得結果的離散分布情況，離散程度較系統(tǒng)算法降低了75%，平衡調度效果提升顯著。

表6 系統(tǒng)算法與貪心算法離散程度對比

圖4 系統(tǒng)自動平衡與貪心算法平衡結果離散分布情況

五

結論

本文通過對現(xiàn)有平臺系統(tǒng)“云南煙草現(xiàn)代物流綜合業(yè)務管理平臺”和業(yè)務流程進行調查分析，結合實際工作流程，提出了一種基于貪心算法的數(shù)據(jù)處理流程。通過對分揀原始數(shù)據(jù)進行貪心算法處理，得到符合實際需求的較好的平衡調度結果，有效避免了由于原系統(tǒng)算法不優(yōu)導致的人工二次調節(jié)，節(jié)省了人工二次調節(jié)所需時間30～40分鐘，大大提升了物流分揀整體工作效率。通過運用貪心算法計算所得結果在均勻程度方面也有較大提升，平衡調度結果較原系統(tǒng)計算結果離散程度降低了75%。

參考文獻:

[1] 葛治存,路宏偉,李榮國. 煙草物流平臺管理信息系統(tǒng)設計[J]. 物聯(lián)網技術,2015(4):88-90,93.

[2]李春玉.由“蝴蝶效應”引發(fā)的思考[J].廣西煙草, 2009(5).

[3]周廷慰.基于粒子群優(yōu)化算法在NP難問題中的應用研究[J].哈爾濱師范大學自然科學學報, 2023, 39(1): 46-51.

[4]杜立智,符海東,張鴻,等. P與NP問題研究[J].計算機技術與發(fā)展, 2013(1):37-42.

[5]徐博,韓曉霞,董穎超,等.自適應狀態(tài)轉移模擬退火算法及其應用[J].計算機應用研究, 2024,41(1) :156-164.

[6]王勛,宋建民,賀毅朝.基于遺傳算法求解NPC的研究[J].河南科技學院學報(自然科學版), 2014, 42(6):43-48.

[7]Cao Jie, LiuChengzhi, Chen Zuohan,et al. A neural network guided dual-space search evolutionary algorithm for large scale multi-objective optimization[J].Engineering Applications of Artificial Intelligence,2025,147:110089.

[8]李泰新,靳析函.基于動態(tài)規(guī)劃和順序概率比檢驗的企業(yè)生產決策優(yōu)化研究[J].市場瞭望, 2024, (24): 7-9.

[9]趙鐵軍,王玲.基于改進貪心算法的Delta機器人分揀路徑優(yōu)化[J].組合機床與自動化加工技術,2021(12):58-61,66.DOI:10.13462/j.cnki.mmtamt.2021.12.014.

[10]張茜,聶億兵,董存軍.基于貪心算法與動態(tài)規(guī)劃結合的線路優(yōu)化研究[J].現(xiàn)代商貿工業(yè),2025(07):236-238.DOI:10.19311/j.cnki.1672-3198.2025.07.076.

———— 物流技術與應用融媒 ————

編輯、排版：王茜

本文內容源自

歡迎文末分享、點贊、在看！轉載請聯(lián)系后臺。

廣告宣傳