广告 | 点击查看
摘要：为提升物流中心卷烟分拣调度工作效率，本文以“云南烟草现代物流综合业务管理平台”卷烟分拣调度系统为研究对象，通过对物流业务中卷烟订单分解及分拣平衡调度处理流程进行分析，提出一种基于贪心算法（Greedy algorithm）的卷烟分拣调度数据处理模型。通过对原始数据进行排序，先从分拣“卷烟条数”单一维度入手，分析并建立了贪心算法数学模型，再根据制定的贪心策略对第二维度因素“订单户数”进行调整，从而构建了一个精度可控的数据处理模型，使分拣总量在卷烟条数和订单户数两个维度上能较平衡地分配到各分拣线，实现分拣平衡调度流程的整体优化，避免人为进行二次调整的现状，从而提升分拣调度工作效率。结果表明，与原系统数据处理方式相比，贪心算法节省了人为二次调整所需的时间30～40分钟。且结果中各组数据之间分布更均匀，数据分布离散程度降低了75%，平衡调度效果显著。
关键词：烟草物流；订单分解；贪心算法；平衡调度
作者：牟乾 李昌珮 黄欣 薛盛元 赵晓柳
云南省烟草公司昆明市公司物流分公司
近年来，随着烟草企业数字化转型的深入推进，信息技术在烟草物流业务中的有效运用大幅降低了生产成本，提高了生产效率[1]。卷烟分拣调度是烟草物流业务中一个重要环节，对于物流中心而言，卷烟分拣调度效率直接关系到配送服务，关系企业经济效益的实现、卷烟零售户满意度的提高，甚至企业核心竞争力的提升。昆明市烟草公司物流分公司在用的“云南烟草现代物流综合业务管理平台”以营销系统为计划源头，相继处理销售订单结转、分拣调度、物流排程、运力调度等，各业务模块环环紧扣，相互关联紧密，业务执行按照既定流程由上至下顺序流转。在现行的卷烟分拣调度模式下，由于各业务环节前后关联紧密，因此各环节中不合理、处理滞后等问题将直接影响后续工作，形成蝴蝶效应[2]，造成分拣效率的大幅下降。因此，合理优化分拣各环节作业流程，有效缩短各环节流转时间，提升各环节工作效率，对提升整体分拣效率具有重要的研究意义和现实意义。
一
问题分析
现行工作模式下，昆明市烟草公司物流分公司每个订单日要处理两个批次的分拣平衡调度任务。其中，上午处理T+0（当天送达）批次，为城区直送业务；下午处理T+1（第二天送达）批次，涉及各县级分公司和中转站配送业务。
昆明市烟草公司物流分公司在用的分拣设备为6条自动化分拣线。在实际工作中，为节约搬运和装车时间，6条分拣线按照1、3、4号线和2、5、6号线分成两组，分别对应就近的两部货运电梯搬运发货，对应不同发货目的地，便于装车。经过统计分析，“云南烟草现代物流综合业务管理平台”分拣调度相关流程及耗时情况如图1所示。
图1 分拣调度相关流程及耗时示意图
在处理订单分解任务时，现行系统虽能将每一批次的分拣量较均匀地分配到各条分拣线上，但并没有考虑按货运电梯位置分组的实际需要，且订单分解均匀程度不够，需人工进行二次调节。由于人工介入调节，需要额外的时间完成平衡调度工作，尤其在第二批次分拣量较大、线路较多的情况下，经验丰富的操作人员平均需要30～40分钟进行二次调节，大大降低了分拣调度作业效率。
二
解决思路
为提升分拣调度作业效率，缩短平衡调度耗时，提升平衡调度均匀程度，有效的做法是尽量避免人工二次调节，通过一定算法由计算机直接按实际需求将订单分解，实现自动平衡调度，节约人力成本和时间成本。
首先需要将所有订单数据按货运电梯与分拣线的位置关系进行分组，将分拣量均匀分成A（1、3、4号分拣线）、B（2、5、6号分拣线）两组，再在各组中将分拣量均匀分到各分拣线，从而实现平衡调度优化。
这一问题可抽象成一个数学模型进行分析，即由n个作业组成的作业集，可由m台相同机器加工处理，要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成，作业不能拆分成更小的子作业，且每个作业均可在任何一台机器上加工处理。这是一个NP（Non-deterministic Polynomial）完全问题，即多项式复杂程度的非确定性问题，目前还没有有效的求最优解解法[3]。
目前求解NP问题的方法主要有模拟退火算法（Simulated annealing）、遗传算法（Genetic algorithm）、神经网络算法（Neural network algorithm）和动态规划（Dynamic programming）等[4]。其中模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法[5]；遗传算法是仿真生物遗传学和自然选择机理，通过人工方式所构造基因并进行交叉变异的方法，寻求最优解[6]；神经网络算法是根据人脑神经连结方式，即神经对能量的接受并不是立即作出响应，而是将它们累加起来，当这个累加的总和达到某个临界阈值时，它们将它们自己的那部分能量发送给其它的神经[7]；动态规划（Dynamic programming）是求解决策过程最优化的数学方法，其把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，从而解决过程整体优化问题[8]。
以上讨论的几种算法均能较好地处理NP问题，但在实际场景中，由于数学建模过程较复杂，超出本例平衡调度问题实际需求，因此本文采用贪心算法来解决本例提出的NP问题。
贪心算法（Greedy algorithm）的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化策略，每一步都要确保能获得局部最优解。每一步只考虑一个数据，数据的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法为止[9]。贪心算法并不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
与动态规划相似，贪心算法在解决最优解问题时可以把整体优化问题拆分成一个个的子问题，求子问题的最优解。而贪心算法是动态规划方法的一个特例，可以证明每一个子问题的解不取决于整体状况，而只取决于当前问题的状况。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，就能展开至结束[10]。
三
基于贪心算法的处理流程
用贪心算法来解决由m台相同机器加工处理n个作业组成的作业集问题。当n≤m时，只要将作业按数量分配给机器即可；当n>m时，首先要将n个作业按作业量从大到小排序，然后依此顺序将作业分配给空闲的机器处理。也就是说从剩下的作业中，选择需要处理时间最长的，然后依次选择处理时间次长的，直到所有的作业全部处理完毕，或者机器不能再处理其他作业为止。
图2 基于贪心算法的处理流程
如图2所示，利用贪心算法把整体平衡优化问题化解成若干子问题，再对每一子问题进行优化求解，得到子问题的局部最优解，最后把子问题的局部最优解合成原问题的一个整体优化解。具体可分为几个步骤完成：
步骤一：根据货运电梯与分拣线的位置关系，用贪心算法将全部分拣量均匀分解成A、B两个组；
步骤二：检查分组结果是否满足贪心策略，若满足则进入下一步，不满足返回上一步重新计算；
步骤三：运用贪心算法，根据实际需求加入适当贪心策略，分别在两组数据中对分拣量进行平衡分配；
步骤四：检查平衡分配结果是否满足贪心策略，若满足则进入下一步，不满足返回上一步重新计算；
步骤五：上一步计算所得各分拣线分拣任务量即为优化问题的解，计算结束。
四
试验
为检验该算法实用性，随机选取昆明市烟草公司物流分公司某日T+1批次的实际生产数据，对数据进行贪心算法处理，处理结果与目前在用系统的结果进行对比。包含配送线路、订单条数和订单户数等信息的原始分拣数据参见表1。
表1 昆明市烟草公司物流分公司某日T+1批次分拣数据
表1中不同线路代码对应不同配送线路，运用贪心算法将分拣数据分解成两组，并结合业务实际制定以下规则：
1.线路cg、fm、sm必须分配在A组，线路an、jn、yl必须分配在B组；
2.线路dc、xd由于分拣量通常均较大，必须分配到不同组；
3.其余各条线路被分配到A组或B组均可，必要时可将其中某一条或几条线路按线路编号打散分配至不同组别间的分拣线；
4.分组结果与分拣总量的条平均值和户平均值间的偏差均不超过5%。
对以上数据按线路归类，并按分拣条数降序排列后，根据以上贪心策略进行分组，所得结果参见表2。
表2 贪心算法对分拣总量分组结果
通过计算，组平均值为128689.5，户平均值为1384.5，分组后A组条偏差和户偏差分别为：0.16%、1.26%，B组条偏差和户偏差分别为0.16%、1.26%，符合设定要求。
下一步，分别在各组中用贪心算法对分拣任务进行分配，各组贪心策略相同，分配步骤为：
步骤一：对各组数据进行升序排序，按从多到少的顺序依次将分拣任务分配至各分拣线；
步骤二：按照局部最优原则，当各分拣线条分拣量与分拣线条平均值间的偏差小于5%时，停止对该分拣线分配任务，依次分配直至将组内所有任务分配完毕；
步骤三：计算各分拣线户分拣量与分拣线户平均值间的偏差，若小于5%即符合要求，大于或等于5%时在组内进行调整，最终满足分配要求。
表3 整批次平衡调度结果
根据上述步骤，得出以上表3结果，并计算6条分拣线的条平均值为42896.5条，户平均值为461.5户。各分拣线条偏差和户偏差计算结果参见表4。
表4 贪心算法平衡调度结果偏差
将基于贪心算法的试验结果与目前在用系统自动平衡调度结果进行比较，参见表5。从表5可以看出，利用贪心算法进行平衡调度后，各条分拣线的条偏差值和户偏差值均明显下降，更趋近于任务总量在各分拣线上的条平均值和户平均值，平衡调度效果显著。
表5 系统自动平衡与贪心算法平衡结果对比
为直观比较贪心算法与系统自动平衡调度结果的离散程度，计算两种方法所得调度结果的方差和标准差参见表6。表6可以看出，贪心算法计算所得结果标准差较小，表明贪心算法较系统算法能更好地将分拣任务均匀分布在各分拣线。图4直观地反映了贪心算法计算所得结果的离散分布情况，离散程度较系统算法降低了75%，平衡调度效果提升显著。
表6 系统算法与贪心算法离散程度对比
图4 系统自动平衡与贪心算法平衡结果离散分布情况
五
结论
本文通过对现有平台系统“云南烟草现代物流综合业务管理平台”和业务流程进行调查分析，结合实际工作流程，提出了一种基于贪心算法的数据处理流程。通过对分拣原始数据进行贪心算法处理，得到符合实际需求的较好的平衡调度结果，有效避免了由于原系统算法不优导致的人工二次调节，节省了人工二次调节所需时间30～40分钟，大大提升了物流分拣整体工作效率。通过运用贪心算法计算所得结果在均匀程度方面也有较大提升，平衡调度结果较原系统计算结果离散程度降低了75%。
参考文献:
[1] 葛治存,路宏伟,李荣国. 烟草物流平台管理信息系统设计[J]. 物联网技术,2015(4):88-90,93.
[2]李春玉.由“蝴蝶效应”引发的思考[J].广西烟草, 2009(5).
[3]周廷慰.基于粒子群优化算法在NP难问题中的应用研究[J].哈尔滨师范大学自然科学学报, 2023, 39(1): 46-51.
[4]杜立智,符海东,张鸿,等. P与NP问题研究[J].计算机技术与发展, 2013(1):37-42.
[5]徐博,韩晓霞,董颖超,等.自适应状态转移模拟退火算法及其应用[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]李泰新,靳析函.基于动态规划和顺序概率比检验的企业生产决策优化研究[J].市场瞭望, 2024, (24): 7-9.
[9]赵铁军,王玲.基于改进贪心算法的Delta机器人分拣路径优化[J].组合机床与自动化加工技术,2021(12):58-61,66.DOI:10.13462/j.cnki.mmtamt.2021.12.014.
[10]张茜,聂亿兵,董存军.基于贪心算法与动态规划结合的线路优化研究[J].现代商贸工业,2025(07):236-238.DOI:10.19311/j.cnki.1672-3198.2025.07.076.
———— 物流技术与应用融媒 ————
编辑、排版：王茜
本文内容源自
欢迎文末分享、点赞、在看！转载请联系后台。
广告宣传
热门跟贴