貪心算法在煙草物流卷煙分揀調(diào)度系統(tǒng)中的應(yīng)用研究

廣告 | 點(diǎn)擊查看

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

關(guān)鍵詞：煙草物流；訂單分解；貪心算法；平衡調(diào)度

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

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

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

一

問題分析

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

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

圖1 分揀調(diào)度相關(guān)流程及耗時(shí)示意圖

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

二

解決思路

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

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

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

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

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

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

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

三

基于貪心算法的處理流程

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

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

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

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

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

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

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

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

四

試驗(yàn)

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

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

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

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

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

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

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

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

表2 貪心算法對(duì)分揀總量分組結(jié)果

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

下一步，分別在各組中用貪心算法對(duì)分揀任務(wù)進(jìn)行分配，各組貪心策略相同，分配步驟為：

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

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

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

表3 整批次平衡調(diào)度結(jié)果

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

表4 貪心算法平衡調(diào)度結(jié)果偏差

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

表5 系統(tǒng)自動(dòng)平衡與貪心算法平衡結(jié)果對(duì)比

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

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

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

五

結(jié)論

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

參考文獻(xiàn):

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

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

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

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

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

[6]王勛,宋建民,賀毅朝.基于遺傳算法求解NPC的研究[J].河南科技學(xué)院學(xué)報(bào)(自然科學(xué)版), 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]李泰新,靳析函.基于動(dòng)態(tài)規(guī)劃和順序概率比檢驗(yàn)的企業(yè)生產(chǎn)決策優(yōu)化研究[J].市場(chǎng)瞭望, 2024, (24): 7-9.

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

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

———— 物流技術(shù)與應(yīng)用融媒 ————

編輯、排版：王茜

本文內(nèi)容源自

歡迎文末分享、點(diǎn)贊、在看！轉(zhuǎn)載請(qǐng)聯(lián)系后臺(tái)。

廣告宣傳