电子标签拣货作业订单分批算法研究与应用毕业设计说明书.docx

电子标签拣货作业订单分批算法研究与应用毕业设计说明书.docx

《电子标签拣货作业订单分批算法研究与应用毕业设计说明书.docx》由会员分享，可在线阅读，更多相关《电子标签拣货作业订单分批算法研究与应用毕业设计说明书.docx（46页珍藏版）》请在冰点文库上搜索。

电子标签拣货作业订单分批算法研究与应用毕业设计说明书

毕业设计说明书（论文）中文摘要

本文分析了订单拣货作业在配货中心所有流程中所占的时间和成本比例，凸显出订单拣货作业的重要地位，进而提出对订单分批进行拣货的优化问题。

介绍订单拣货在拣货方法、路径选择、订单分批方法方面的研究现状，简单介绍了一些常用的订单分批方法，包括传统的先到先拣方法，种子方法，启发式方法和遗传算法。

其中重点介绍了启发式算法的基本思想和求解过程。

论文构造了拣货作业中订单分批问题的数学模型，在节约方法和聚类分析两种思想的基础上，分别提出了节约距离公式和相似系数公式。

然后通过算例分析，采用两种启发式算法分别求解分批结果。

最后以拣货行走的总距离为比较对象，对比两种方法对算例的优化结果。

文章验证了两种算法对解决模型的有效性。

关键字：

订单拣货；分批；启发式算法；节约算法；聚类分析；模型

毕业设计说明书（论文）外文摘要

TitleResearchandapplicationonorderpickingalgorithm

inElectronic-Tagging-PickingSystem

Abstract

Thisarticleanalyzedtheproportionoftimeandcostoforderpickingoperationinallprocessesinthedistributioncenter,thereforehighlightedtheimportanceoforderpickingoperation,thenproposedtheoptimizationofit.Thepaperintroducedtheresearchstatusofpickingoperationonpickingmethods,pathselectionandorderbatchingmethods,andbrieflyintroducedsomeregularmethodsoforderbatchingincludingthetraditionalfirstcomefirstpick,seedmethod,heuristicmethodandgeneticalgorithms.Thepaperspeciallyfocusedonthebasicideasandsolutionprocedureofheuristicmethod.

Thearticleconstructedamathematicalmodelfororderbatchinginorderpickingoperation,andcameupwiththesavingdistanceformulaandsimilaritycoefficientformulabasedonthetheideaofsavingmethodandclusteranalysisrespectively.Thenwesolveanumericalexampleusingtwoheuristicalgorithmsrespectively,andcomparedtheoptimizationresultsofthemtakingthetotalwalkingdistanceofpickingascomparisonobject.Thearticleprovedthevalidityoftwoalgorithmsforsolvingthemodel.

Keywords:

orderpiching;batch;heuristicmethod;savingalgorithm;clusteranalysis;model

前言

随着供应链管理的出现，仓库的使用者开始注重优化其配送网络以降低安全库存来获得规模经济，仓库也变得越来越大。

随着电子商务的成功实现，大量的订单呈小型化趋势发展，制造业也正向小批量多批次配送模式、订单与产品定制化、前置时间下降等方面转变。

配送时间要求越来越短，订单拣选活动通常要在规定的有限时间内完成，从而导致配货和订单拣取的难度增加[1]。

从成本分析的角度看，物流成本约占商品最终售价的30%，其中包括配送、搬运、储存等成本项目。

一般而言，配送中心订单拣选作业成本约是其它堆叠、装卸、运输等成本的9倍，占物流搬运成本的绝大部分[2]。

从人力需求的角度来看，目前绝大多数的配送中心仍属于劳力密集型产业，其中与订单拣选作业直接相关的人力，更是占50%以上[3]。

无论是零售业还是制造业，在多品种配送中心的物料搬运作业中，卸货、储运和装车作业约占总作业时间的20%，其余80%则属于订单拣选作业的时间。

在成本上，订单拣选人工作业成本占配送中心总成本的15%—20%。

由此可见规划合理的订单拣选作业方法，对配送中心运作效率的高低具有决定性的影响[4]。

电子标签拣货系统是一种电脑辅助的无纸化拣货系统，其原理是借助安装于货架上每一个货位的LED电子标签取代拣货单，利用电脑的控制将订单信息传输到电子标签中，引导拣货人员正确、快速、轻松地完成拣货工作，拣货完成后按确认钮完成拣货工作，增加了物流系统的高效性，减少人员数量，提高系统效率，达到降低成本的目的，通过电子标签实现订单式拣货实时监控，利用管理人员处理业务。

借助电子标签拣货系统，拣货人员可以大大提高拣货效率降低分拣人员的劳动强度，缩短订单拣选的时间，从而提高整个配送中心的运行效率，达到了降低成本的最终目的。

配送中心利用电子标签拣货系统进行订单分批拣选，所以分析研究订单分批拣选的方法。

并用研究成果对系统进行优化。

通过引申，也可以将其运用到大型生产型企业的仓库管理中，从运营管理、制造系统合理化的角度对企业的

生产计划进行合理的设计和规划，从而降低企业的生产成本、优化管理，最终

提高生产制造型企业的市场竞争力。

第一章绪论

1.1选题依据

在所有物流配送中心作业流程包括接货，搬运，存放，拣货，集中/分类，越库，出货等一系列活动，如图1-1。

在所有流程中，拣货作业时最受关注的。

主要因为拣货作业成本找到配送中心总成本的60%—80%[5]，另一个重要原因就是拣货作业效率高低直接关系到客户的满意程度。

快速准确的拣货能力成为交易成功的一个重要组成部分。

图1-1配送中心的工作流程

在所有作业中，拣货作业是其中十分重要的一环，其所扮演的角色相当于人体的心脏、空调系统的压缩机[6]。

拣货作业在人工仓库系统中属于劳动力密集程度最高的作业，在自动仓库系统中则属于资本密集程度最高的作业[8]。

其劳动量约占配送中心的所有作业量的60%[5]。

而且，其成本占仓库所有运作成本的50%—75%[7]。

由于拣货作业内容千差万别、拣货方法繁多，很难还是先拣货的机械化、自动化和信息化，使拣货作业异常辛苦，效率低下。

特别是随着计算机的普及、信息化的应用，物流配送中心的出库指导书和货单均由计算机自动处理（电子标签拣货系统）大大缩短了事务处理的时间，进而加大了拣货作业所占时间的比例。

可以说，物流配送作业受到拣货作业的瓶颈影响[8]。

鉴于此，美国仓储教育和研究协会在1986年的一项调查报告中将拣货作业定为提高仓库运作效率的首要领域。

从成本分析角度看，物流成本约占商品最终售价的30%，其中包括配送、搬运、储存等成本项目。

一般而言，拣货成本约是其它堆叠、装卸、运输等成本的9倍，占物流成本的绝大部分。

从人力需求角度来看，目前绝大多数的配送中心仍属于劳力密集型产业，其中与拣货作业直接相关的人力，更是占50%以上[5]。

无论是零售还是制造业，在多种配送中心的搬运作业中，卸货、储运和装车作业约占总作业时间的20%，其余80%的时间则属于拣货作业时间。

在成本上拣货工人作业成本占配送中心总成本的15%—20%[5]。

由此可见，规划合理的订单拣货作业方法，对配送中心运作效率的高低具有决定性的影响。

1.2选题背景

物流配送中心是在物流领域社会分工、专业分工进一步细化后产生并在仓库的基础上形成和发展起来的。

配送中心是由各种自动化储存设备、堆垛搬运设备、分拣分类设备以及计算机管理控制系统构成的一个复杂的现代化物流系统设施[9]。

而电子拣货系统作为一种电脑辅助的无纸化拣货系统，其原理是借助安装于货架上每一个货位的电子标签取代拣货单，利用电脑的控制将订单信息传输到电子标签中，引导拣货人员正确、快速、轻松地完成拣货工作，拣货完成后按确认钮完成拣货工作。

计算机监控整个过程，并自动完成数据处理。

所以仓储配送中心利用电子标签拣货系统来进行业务的开展，有利于生产企业降低库存、减少固定资金投入，实现准时生产，仓库减少存货，降低流动资金使用量，而且能保证销售的顺畅。

配送中心系统规划是否合理、订单处理速度快慢、拣选顺序是否得当，都直接影响配送中心的经济效益，关系着整个物流供应链的顺畅运行[10]。

随着社会整体的发展，高水平的服务要求和激烈的市场竞争使配送中心的地位有了很大的提高，合理科学的设计订单分批拣选的方法和过程，可以使得配送中心的作业流程顺畅高效，提高工作效率，从而减小费用，达到提高企业整体竞争力的目的。

图1-2各项活动所占的费用比例

在配送中心的所有仓库作业活动中，订单拣选是配送中心消耗费用费用和

时支出间最大的作业活动，据国外的调查，拣选作业所消耗的劳动费用和时间

占配送中心全部劳动费用和时间消耗的比例高达60%（如图1-2所示）。

同时，

在订单拣选作业中不同的动作方式所消耗的工作时间也是不同的，其中，拣选

作业中的移动时间所占比例最大达60%左右，所以降低配送中心运营成本的核心应该是如何最小化订单拣选作业人员的行走路径。

由此从费用和工作时间两个方面我们可以得出，对配送中心的订单分批拣选问题进行优化研究具有重要的意义。

1.3研究的主要内容

结合我国当前仓库拣货作业与管理实践，以国外对该领域的研究状况，借鉴多学科的观点和方法，系统研究拣货作业的优化设计。

才用定性和定量相结合，以定量研究和理论研究为主，通过仿真实验验证和得出某些结论。

主要内容如下：

1.分析和总结国内外有关分拣作业设计方面的理论、方法和研究结论，准确把握国内外研究现状，分析与订单分批拣货作业相关的文献资料。

2．对启发式订单分批算法进行详细的介绍，启发式算法（heuristicalgorithm）是相对于最优化算法提出的。

一个问题的最优算法求得该问题每个实例的最优解。

启发式算法可以这样定义：

一个基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解。

这种算法以最小化行走距离为目标，构造了拣货作业中订单分批问题的数学模型。

适用于求解订单分批分拣这样的NP问题。

3．订单分批分拣数学模型的建立。

订单分批是拣货作业经常用到的策略，良好的分批策略可以缩短拣取时的平均行走搬运距离，减少寻找储位的时间，进而提升拣货的效率，降低分拣的成本，最终降低仓储中心的成本，提高客户的满意率。

本文基于一定的假设，建立起了数学模型。

同时考虑拣货人员的行走距离和订单聚类分析的相似度问题，并分别给出了其相应的算法过程。

4．数学模型的求解。

订单分批分拣问题是NP问题，采用启发式算法可以有效地在较短的时间里取得理想的结果。

本文将详细介绍两种启发式算法（节约启发式算法和基于聚类分析的启发式算法）如何应用于订单分批分拣问题，包括初始批量的形成，批量优化，节约量和相似系数的计算等操作。

5．算例的验证。

为了验证数学模型的有效性，采用某些实际数据，利用模型对两种启发式算法的在算例中的应用进行逐步优化求解直至最终求出最优解，并对采用订单分批分拣前后结果以及先到先服务方法进行比较。

最后采用VB编写仿真程序，实现结果。

第二章订单拣选的研究现状

目前国内关于订单拣选的研究，主要涉及到以下几个方面：

布局设计的研究、存储策略的研究、配送中心内部存储货位的设计、拣选方法的选择、作业路径的确定以及订单拣选中订单分批的研究。

本文是在电子标签拣货作业的基础上进行订单分批算法研究与应用，所以研究的重点为拣选方法的选择、作业路径的确定以及订单拣选中订单分批几方面。

2.1订单拣选方法的研究现状

对订单拣选方法的分类如图2-1：

图2-1订单拣选系统的分类

其中，低水平的人找物拣选是指，订单拣选人员靠人力行走去拣选货物。

高水平的人找物拣选是指，订单拣选人员依靠机器行走或搬运方式去拣选货物。

不同的拣选系统配置可能会带来不同的拣选作业方式，其中人至物，即人行走到储存区寻找并取出所需的货品（如托盘式货架系统）；物至人，指将货品移动到拣选人员或拣选机器旁，由拣选人员或拣选机器拣选出所需的货品（如旋转货架系统）。

不同的拣选作业方式也会带来不同的分类系统，我们需要考虑拣选方式所能增加的收益（提高效率和降低拥挤度）是否足以弥补建立分类拣选系统所需的额外投资。

例如，拣选作业系统涉及的成本因素主要有拣选区域拣选人员的人力成本、拣选设备成本（如叉车、拣选货物的周转箱等）、拣选区设备成本（如传送带、货架等）、机会成本、分类系统的设备成本、分类区分类作业人员的人力成本，等等。

这些因素相互作用，共同影响着拣选系统的成本、效益[11]。

电子标签拣货作业即属于较低水平的人找物拣选系统。

2.2订单拣选路径的研究现状

李诗珍，王转[12]，用计算数字显示拣选方法、传统订单拣货方式、及启发式方法来确定订单拣选的移动距离。

其中电子标签拣选是利用数字显示器与人工配合的一种拣选方式，拣选人员只要依据灯号及数字显示，就可将商品拣出，是一种无纸化的拣选。

再利用启发式方法确定最短的拣选路径。

在其它情况下，拣选路径会因拣取货位的不同而不同，但他们指出适用S形启发式方法确定的拣选路径，拣选时需要移动的距离最多只可能与其它方法算出的拣选路径移动距离相等，不可能比其它的方法更大。

本文采用S型拣选策略经过对文献的学习和总结，目前订单拣选时常采用的拣选路径主要有以下几种方式[13]：

（1）S型拣选路径策略

S型路径策略是拣选人员完全通过包含要分拣的品项的通道，不包含有需要分拣的品项的通道则不通过，拣选完最后一个品项时返回出发点。

如图2-2所示。

图2-2S型拣选路径

（2）返回型型拣选路径策略

返回式拣选方式是订单分拣人员从巷道的同一端进入和离开，跟S型拣选方式一样，分拣人员只进入那些有物品的巷道。

如图2-3所示。

图2-3返回型拣选路径

（3）中点返转策略

中点返转策略把整个配送中心分成两个区域（如图2-4）。

需要分拣的物品在前半部分的订单分拣人员就从前面的入口进入，需要分拣的物品在后半部分的订单分拣人员就从后面的入口进入。

分拣人员从已访问过的最后一个通道或者第一个通道返回出发点。

图2-4中点型拣选路径

（4）最大间隙型拣选路径策略

最大间隙策略是指在同一个巷道内需要分拣的物品和上下两侧底端走道的距离做比较，选择较短距离的路径。

若物品和上下两侧底端的巷道距离小于需要分拣的物品之间的距离，则直接返转。

如图2-5所示。

图2-5最大间隙拣选路径

（5）混合型拣选路径策略

联合策略是S型策略和返转式策略的联合，对于这种路径策略，拣选人员或者穿过整个巷道，或者在拣选完一个物品后从巷道的同一侧离开。

如图2-6所示。

图2-6混合型拣选路径

2.3订单分批拣选的研究现状

配送中心订单拣选作业中的订单分批是为了提高拣选作业效率而把多张订单集合成一批,进行批次拣取作业，其目的是缩短拣选过程中时平均行走的距离和时间[14]。

通过分批后，将每批次订单中的同一商品品项加总后拣取，然后再把货品分类给每一个顾客订单，则形成批量拣取，这样不仅缩短了拣选过程中平均行走搬运的距离，也减少了重复寻找储位的时间，而使拣选效率提高。

按批次进行拣选特别适合于品项数少而订单数量大的系统，愈是少量多次的配送，批量拣选就愈有效[15]。

李诗珍，王转，张克成[14]在订单分批策略研究中中对订单分批方式做了总结，主要有以下几种：

1．总合计量分批

合计拣选作业前累积的所有订单中每一商品项目的订购总量，再根据这一总量进行拣取以将拣取路径减至最短，同时储存区域的储存单位也可以单纯化，但需要有功能强大的分类系统来支持。

这种方式适用于固定点之间的周期性配送，可以将所有的订单在中午前收集，下午作总合计量分批拣取单据的打印等资讯处理，第二天一早进行拣取分类等工作。

2．时窗分批

在考虑时间窗口时，在同一个时间段到达的货物称为一个时间窗口，它们构成一个批量。

这批货物在下一步中同时被处理。

如果不可以拆分订单，就可以在拣选的同时按订单分离货物。

当从订单到达到拣选完成出货所需的时间非常紧迫时，可利用此策略开启短暂而固定的时窗，如五分钟或十分钟，再将此时窗中所到达的订单做成一批，进行批量拣取。

这一方式常与分区及订单分割联合运用，特别适合于到达时间短而平均的订单形态，同时订购量和品项数不宜太大，此分批方式适合密集频繁的订单，且较能应付紧急插单的需求。

3．固定订单量分批

订单分批按先到先处理的基本原则，当累计订单量到达设定的固定量（FixedNumber）时，再开始进行拣选作业。

适合的订单形态类似于时窗分批，

但这种订单分批的方式偏重在维持较稳定的作业效率，而在处理的速度上平均

较前者慢。

4．智能型分批

订单在汇集后经过电脑计算，将拣取路径相近的订单分成一批同时处理，可大量缩短拣选行走搬运距离。

采用这种分批方式的配送中心通常将前一天的订单汇集后，经电脑处理在当天下班前产生次日的拣选单据，因此对紧急插单作业处理较为困难。

马士华,文坚[16]介绍了时窗分批，即波次拣选的基本思路。

介绍了静态时窗分批（按时间）与动态时窗分批（按订单设计的物品数，并运用实际的数据案例对两种方法进行了比较。

指出，动态的视窗分析法较优越。

伍经纬,蔡临宁[17]，回顾了当前企业分拣过程中订单分批的最优算法。

在人工分拣环境,不同储位分配和仓储物品量的条件下,对订单分批的FIFS，MAA，COG，GSM，GS等五种算法进行考察。

并根据某国有大型企业的订单数据和计算机生成订单,采用Java编程实现各种算法,通过程序分析了不同条件下各种算法的分拣效率。

实验结果表明S型分拣路线的MAA启发式算法,比其他算法优化效果更好,因此推荐大家采用。

李诗珍等人在很多文章中[18][19]提出分批拣选根据分类方式的不同可以分为边拣选边分类和拣选后再分类两种方法。

并介绍了订单分批模型建立的假设条件,以及用节约式启发算法的求解的过程。

在此方面，国外的一些文章也进行了研究。

李诗珍，杜文宏[20]又在聚类分析的基础上,构造了拣选作业中订单分批问题的数学模型,提出了三种相似系数计算公式,并建立了订单分批问题的聚类模型。

然后采用启发式算法求解聚类模型得到分批结果,再根据分批模型求最短行走距离。

最后以拣选行走的总距离为目标,通过算例结果将算法与现有的分批方法进行比较,验证了模型和算法的有效性。

2.4订单分批拣选优化方法的总结

由于订单分批是个NP问题，很多学者专注于设计开发启发式的算法来解决这类问题。

对订单分批问题进行优化的方法总结如表2-1：

表2-1订单分批问题优化方法总结

文章作者

研究的问题

优化目标

使用的方法

伍经纬,蔡临宁[17]

比较了多个订单

分批算法的优缺点

采用Java编程序

实现各种算法

李诗珍等[18][19]

订单分批问题

建模寻优

路程最短

启发式算法

李诗珍、杜文[20]

建立订单分批

问题的聚类模型

路程最短

启发式算法

王雄志[21]

订单分批拣选、拣选路径、分区拣选问题

运行时间最少

启发式与

遗传算法

ChenandWu[22]

分析了订单之间的相关性

0—1整数规划

DeKosteretal.[23]

比较了种子方法和

节约方法两种理论

运行时间最少

通过两种不同的启发式方法对其评价

第三章订单分批拣选算法描述

对于人工型的拣选配送中心系统，在实现订单分批时，一般会遵循一定的分批原则，即按照一定的分批思想和步骤对大量订单进行分配。

而分批时有传统的先到先服务拣选方法，另外为了提高效率，常选用的方法主要有种子启发式算法[24]、节约启发式算法、包络算法（nve1opeAlgorithm）、墓于聚类分析的启发式算法、基于包络解码的遗传算法。

由于基于聚类分析的启发式算法的基本思想类似于节约启发式算发，只不过分批的依据是最大相似系数而不是最大节约量。

在此，本文重点介绍下种子启发式算法和节约启发式算法的概念和解题思想。

3.1先到先服务方法的简介

所谓先到先拣选分批方法，不对订单做任何处理，每到达一个订单便对其进行独立的拣选。

这种拣选放法必然会浪费大量的人力和物力，并使总拣选路程变得非常的巨大。

但是在许多小型的仓库中，都是运用这种方法进行拣选的[11]。

先到先拣选分批方法的结果可以作为本文数据结果分析的一个参照对象，这种方法展示了在订单还没有被分批时，拣选完所有货物需要行走的总距离。

间接表示了现实中，最常用的拣选方法消耗的运作成本是多少。

实验过程中，此方法的实验结果可以作为一个参考对象，其他的方法通过与其进行比较，可以分析出优化程度的多少，以及优化意义如何。

3.2种子启发式算法的简介

种子启发式算法就是订单分批过程中，选出一些具有某些特征的订单作为“种子”，首先将这些种子订单放入到要组合的批次中去，随后再根据某些原则将剩余的订单添加到已包含有种子订单的批次中，从而完成整个分批过程的思路[24]。

由上理论可以看出，种子方法构造订单批量主要分两步进行：

①种子订单的选择，即从所有待分批的订单中选择一些有特色的订单分别插入到确定好的拣选批次中，作为初始订单；

②剩余订单的插入，是指即将剩余的订单插入到已经包含有种子订单的批次中来。

种子拣选的准则有很多，根据不同的原则来选择订单作为种子，必定会对分批后的拣选效率产生很大的影响。

根据优化目标的不同，可以适时的选择某个原则来拣选种子订单，常用的有订单体积、包含货物的位置、单个订单的拣选路线等等。

将没有分配的订单插入到已包含有种子订单的批量中来称为剩余订单的插入。

一般情况下，将一个订单选入一个批量是根据订单到这个批量中种子订单距离的测量方法来确定的。

例如：

（1）此订单的加入所需要增加的通道数；

（2）所加入订单中心点与中子订单中心点的差距；

（3）加入订单和种子订单中最近货物的总距离[24]。

3.3节约启发式算法的简介

节约启发式算法最早由Clarke和Wright[21]在1964年提出，主要用于解决车辆的配载与调度问题。

其基思想是运行路径的节约问题，是通过将一批小的路径合并到大路径中，形成一个组合,从而来获得最佳路径。

在车辆载重容量允许的情况下，将分别向各个客户送货改为由一辆车同时向多个客户送货，使得每次节约的里程数最大。

根据这一思想，如果有一个配送中心分别向N个客户配送货物，在车辆载重能力允许的情况下，每辆车的配送线路上经过的用户个数越多，则配送线路越合理，总配送距离越小。

借鉴节约法的思想，主要有四种订单分批节约启发式算法法：

L．C-W算法；

2．EQUAL算法；

3．SL（Small一Large）算法；

4．MAXSAV算法。

节约启发式算法的基本原理本质上仍然是种子启发式