遗传算法在物流多分拣线任务分配中应用.pdfVIP

中国烟草学会2011年学术年会论文集 遗传算法在物流多分拣线任务分配中的应用 唐晋 (四川省烟草公司成都市公司，成都市清江东路烟草公司5801、610000) 摘要：针对烟草物流中心多分拣线任务均衡分配的实际应用，提出了利用实数编码的遗传算法 解决方案。通过对实际生产环境数据进行测试和分析，得出了各种参数的经验值，并在实际应用中取 得了比较满意的结果。 关键词：遗传算法；任务分配；多目标优化 0引言 四川省烟草公司成都市公司物流中心现有9条电子标签辅助人工分拣线，承担了成都市每年 2400000万支卷烟的分拣任务，日均分拣卷烟约9562万支。待分拣订单根据客户所在地理位置以及送 货车的容量被组合成为若干配送单，每张配送单中的订单必须由同一分拣线分拣并由同一辆送货车送 货，不同配送单中的客户数和订货量均不相同。 成都市公司物流中心分拣线目前平均单线分拣速率约为140万支／／l,时，实际分拣效率以及分拣人 员的劳动强度主要取决于客户数和订货数量，订货数量大则分拣时间长，在订货数量相同的情况下， 客户数多，则订单散。劳动强度大，耗时长。配送单的分配必须均衡的考虑订货数量以及客户数，使 得每条分拣线分拣的客户数和总订货量基本一致，才能保证每条分拣线的劳动强度基本一致，并且基 本同时完成分拣任务。目前成都市公司物流中心每天生成约200张配送单．分两个批次分别分配到9 条分拣线上，手工分配每批次至少耗时40分钟，不仅浪费时间，更是直接延迟了分拣线的启动时间。 1遗传算法简介 遗传算法(Genetic Algorithm)是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。 它的思想源于生物遗传学和适者生存的自然规律，是具有“生存+检测”的迭代过程的有哪些信誉好的足球投注网站算法。它 函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获 取和指导优化的有哪些信誉好的足球投注网站空间，自适应地调整有哪些信誉好的足球投注网站方向，不需要确定的规则。遗传算法的这些性质，已被 人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域，是现代有关智能 计算中的关键技术之一。 遗传算法在物流多分拣线任务分配中的应用 2算法设计 2．1 算法思想 本文将多分拣线的任务分配建立为一个多目标的优化模型，在优化的过程中需要协调客户数与订 货数量两个目标。这两个目标具有一定的相关性和排斥性，在优化过程中必须统筹考虑。本文采用实 数编码的遗传算法，使用带权重的适应值对优化目标进行协调。基本过程为： 步骤l创建原始种群 步骤2计算种群中个体适应度 步骤3选择和复制个体 步骤4随机选择数对个体进行交叉繁殖 步骤5随机选择一定数量的个体进行变异 步骤6遗传未达到指定代数，回到步骤2 步骤7结束 2．2原始种群的建立和选择 长度为N的一维数组，N为配送单的数量，lndv[j]存储了第j张配送单的分拣线编号，也称作基因。 原始种群的数量和质量决定了算法的收敛速率，根据传统的遗传算法，我们采用随机生成个体的方法 产生原始种群，在实际计算中，我们把M的取值设为200。 2．3个体适应度的计算 本算法需要同时对两个目标进行优化，分别是客户数量和订货数量。对于每个个体，首先汇总每 条分拣线要分线的客户总数和订货总数量，再分别计算所有分拣线的总客户和总订货数量的方差。最 后将这两个方差按照一定的权重相加得到个体的适应值，公式如下： ^=嗽厂d+凡 (1) P ^=墨(cip—c)2IP (2) 。 2I P P 凡=釜(qip—g)2／P (3