电子标签拣货作业订单分批算法研究与应用.doc

毕业设计说明书（论文）中文摘要本文分析了订单拣货作业在配货中心所有流程中所占的时间和成本比例，凸显出订单拣货作业的重要地位，进而提出对订单分批进行拣货的优化问题。介绍订单拣货在拣货方法、路径选择、订单分批方法方面的研究现状，简单介绍了一些常用的订单分批方法，包括传统的先到先拣方法，种子方法，启发式方法和遗传算法。其中重点介绍了启发式算法的基本思想和求解过程。论文构造了拣货作业中订单分批问题的数学模型，在节约方法和聚类分析两种思想的基础上，分别提出了节约距离公式和相似系数公式。然后通过算例分析，采用两种启发式算法分别求解分批结果。最后以拣货行走的总距离为比较对象，对比两种方法对算例的优化结果。文章验证了两种算法对解决模型的有效性。关键字：订单拣货；分批；启发式算法；节约算法；聚类分析；模型46 / 50毕业设计说明书（论文）外文摘要Title Research and application on order picking algorithm in Electronic-Tagging-Picking System AbstractThis article analyzed the proportion of time and cost of order picking operation in all processes in the distribution center, therefore highlighted the importance of order picking operation, then proposed the optimization of it. The paper introduced the research status of picking operation on picking methods, path selection and order batching methods, and briefly introduced some regular methods of order batching including the traditional first come first pick, seed method, heuristic method and genetic algorithms. The paper specially focused on the basic ideas and solution procedure of heuristic method.The article constructed a mathematical model for order batching in order picking operation, and came up with the saving distance formula and similarity coefficient formula based on the the idea of saving method and cluster analysis respectively. Then we solve a numerical example using two heuristic algorithms respectively, and compared the optimization results of them taking the total walking distance of picking as comparison object. The article proved the validity of two algorithms for solving the model. Key words: order piching; batch; heuristic method; saving algorithm; cluster analysis; model目 录前 言1第一章 绪论21.1选题依据21.2选题背景31.3研究的主要内容4第二章 订单拣选的研究现状62.1订单拣选方法的研究现状62.2 订单拣选路径的研究现状72.3 订单分批拣选的研究现状102.4 订单分批拣选优化方法的总结11第三章 订单分批拣选算法描述133.1先到先服务方法的简介133.2种子启发式算法的简介133.3节约启发式算法的简介143.3.1订单分批中节约启发式算法的思想153.3.2订单分批中节约启发式算法实施步骤15第四章 订单分批拣选启发式算法的研究与应用174.1 订单分批问题的数学模型174.1.1 模型假设174.1.2 数学模型的建立184.2 节约启发式算法求解订单分批问题过程194.2.1 初始批量的形成194.2.2 批量的优化194.3 节约启发式算法的算例分析204.3.1 节约启发式分批214.3.2 比较分析274.4 订单分批问题的聚类分析274.4.1 特征向量274.4.2 相似系数284.4.3 基于聚类分析的启发式算法294.5 基于聚类分析的启发式算法的算例分析304.5.1 聚类分析的启发式分批过程304.5.2 比较分析36第五章 电子标签拣货系统的优化375.1 系统优化前375.2系统优化后38第六章 总结与展望416.1总结416.1展望42参考文献43致 谢45前 言随着供应链管理的出现，仓库的使用者开始注重优化其配送网络以降低安全库存来获得规模经济，仓库也变得越来越大。随着电子商务的成功实现，大量的订单呈小型化趋势发展，制造业也正向小批量多批次配送模式、订单与产品定制化、前置时间下降等方面转变。配送时间要求越来越短，订单拣选活动通常要在规定的有限时间内完成，从而导致配货和订单拣取的难度增加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对启发式订单分批算法进行详细的介绍，启发式算法（heuristic algorithm)是相对于最优化算法提出的。一个问题的最优算法求得该问题每个实例的最优解。启发式算法可以这样定义：一个基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解。这种算法以最小化行走距离为目标，构造了拣货作业中订单分批问题的数学模型。适用于求解订单分批分拣这样的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-2 S型拣选路径（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固定订单量分批 订单分批按先到先处理的基本原则，当累计订单量到达设定的固定量（Fixed Number) 时，再开始进行拣选作业。适合的订单形态类似于时窗分批，但这种订单分批的方式偏重在维持较稳定的作业效率，而在处理的速度上平均较前者慢。 4智能型分批 订单在汇集后经过电脑计算， 将拣取路径相近的订单分成一批同时处理， 可大量缩短拣选行走搬运距离。采用这种分批方式的配送中心通常将前一天的订单汇集后，经电脑处理在当天下班前产生次日的拣选单据，因此对紧急插单作业处理较为困难。 马士华,文坚16介绍了时窗分批，即波次拣选的基本思路。介绍了静态时窗分批（按时间）与动态时窗分批（按订单设计的物品数，并运用实际的数据案例对两种方法进行了比较。指出，动态的视窗分析法较优越。伍经纬,蔡临宁17，回顾了当前企业分拣过程中订单分批的最优算法。在人工分拣环境,不同储位分配和仓储物品量的条件下,对订单分批的FIFS，MAA，COG，GSM，GS 等五种算法进行考察。并根据某国有大型企业的订单数据和计算机生成订单,采用 Java 编程实现各种算法,通过程序分析了不同条件下各 种算法的分拣效率。实验结果表明 S 型分拣路线的 MAA 启发式算法,比其他算法优化效果更好,因此推荐大家采用。 李诗珍等人在很多文章中1819提出分批拣选根据分类方式的不同可以分为边拣选边分类和拣选后再分类两种方法。并介绍了订单分批模型建立的假设条件,以及用节约式启发算法的求解的过程。在此方面，国外的一些文章也进行了研究 。李诗珍，杜文宏20又在聚类分析的基础上,构造了拣选作业中订单分批问题的数学模型, 提出了三种相似系数计算公式, 并建立了订单分批问题的聚类模型。然后采用启发式算法求解聚类模型得到分批结果, 再根据分批模型求最短行走距离。最后以拣选行走的总距离为目标, 通过算例结果将算法与现有的分批方法进行比较, 验证了模型和算法的有效性。 2.4 订单分批拣选优化方法的总结由于订单分批是个NP问题，很多学者专注于设计开发启发式的算法来解决这类问题。对订单分批问题进行优化的方法总结如表2-1：表2-1 订单分批问题优化方法总结文章作者研究的问题优化目标使用的方法伍经纬,蔡临宁17 比较了多个订单分批算法的优缺点采用Java编程序实现各种算法李诗珍等1819 订单分批问题建模寻优路程最短启发式算法李诗珍、杜文20 建立订单分批问题的聚类模型路程最短启发式算法王雄志21 订单分批拣选、拣选路径、分区拣选问题运行时间最少启发式与遗传算法Chen and Wu 22分析了订单之间的相关性01整数规划De Koster et al.23 比较了种子方法和节约方法两种理论运行时间最少通过两种不同的启发式方法对其评价第三章 订单分批拣选算法描述对于人工型的拣选配送中心系统， 在实现订单分批时， 一般会遵循一定的分批原则， 即按照一定的分批思想和步骤对大量订单进行分配。而分批时有传统的先到先服务拣选方法，另外为了提高效率，常选用的方法主要有种子启发式算法24、节约启发式算法、包络算法( nve1opeAlgorithm)、墓于聚类分析的启发式算法、基于包络解码的遗传算法。由于基于聚类分析的启发式算法的基本思想类似于节约启发式算发，只不过分批的依据是最大相似系数而不是最大节约量。在此，本文重点介绍下种子启发式算法和节约启发式算法的概念和解题思想。 3.1先到先服务方法的简介所谓先到先拣选分批方法，不对订单做任何处理，每到达一个订单便对其进行独立的拣选。这种拣选放法必然会浪费大量的人力和物力，并使总拣选路程变得非常的巨大。但是在许多小型的仓库中，都是运用这种方法进行拣选的11。 先到先拣选分批方法的结果可以作为本文数据结果分析的一个参照对象，这种方法展示了在订单还没有被分批时，拣选完所有货物需要行走的总距离。间接表示了现实中，最常用的拣选方法消耗的运作成本是多少。实验过程中，此方法的实验结果可以作为一个参考对象，其他的方法通过与其进行比较，可以分析出优化程度的多少，以及优化意义如何。 3.2种子启发式算法的简介种子启发式算法就是订单分批过程中， 选出一些具有某些特征的订单作为“种子”，首先将这些种子订单放入到要组合的批次中去，随后再根据某些原则将剩余的订单添加到已包含有种子订单的批次中，从而完成整个分批过程的思路24。由上理论可以看出，种子方法构造订单批量主要分两步进行： 种子订单的选择，即从所有待分批的订单中选择一些有特色的订单分别插入到确定好的拣选批次中，作为初始订单； 剩余订单的插入，是指即将剩余的订单插入到已经包含有种子订单的批次中来。种子拣选的准则有很多，根据不同的原则来选择订单作为种子，必定会对分批后的拣选效率产生很大的影响。根据优化目标的不同，可以适时的选择某个原则来拣选种子订单，常用的有订单体积、包含货物的位置、单个订单的拣选路线等等。将没有分配的订单插入到已包含有种子订单的批量中来称为剩余订单的插入。一般情况下， 将一个订单选入一个批量是根据订单到这个批量中种子订单距离的测量方法来确定的。例如：(1)此订单 的加入所需要增加的通道数；(2)所加入订单中心点与中子订单中心点的差距；(3)加入订单和种子订单中最近货物的总距离24。 3.3节约启发式算法的简介节约启发式算法最早由Clarke和Wright21在1964年提出，主要用于解决车辆的配载与调度问题。其基思想是运行路径的节约问题，是通过将一批小的路径合并到大路径中，形成一个组合,从而来获得最佳路径。在车辆载重容量允许的情况下，将分别向各个客户送货改为由一辆车同时向多个客户送货，使得每次节约的里程数最大。根据这一思想，如果有一个配送中心分别向N个客户配送货物，在车辆载重能力允许的情况下，每辆车的配送线路上经过的用户个数越多，则配送线路越合理，总配送距离越小。借鉴节约法的思想， 主要有四种订单分批节约启发式算法法：LC-W算法；2EQUAL算法；3SL（Small一 Large）算法；4MAXSAV算法。 节约启发式算法的基本原理本质上仍然是种子启发式算法， 只不过无论采取上述哪种具体算法，其处理订单的标准都是距离或时间的最大节约值，在种子订单的选择和相似性度量方面的标准都比较单一。自动化立体仓库和多巷道的低层仓库都可以采用节约启发式算法对订单进行分批处理。De Koster et al.在多通道、拣选员到物的配送中心系统中比较了种子方法和节约方法两种理论。这2个算法的执行效果是通过两种不同的启发式行程来评价的。这种分批算法考虑了运行时间、组成的分批数量以及现实的可行性。两种方法总结到,（1）即使是简单的分批与先到先拣选相比也有明显的优越性；（2）种子启发式算法法与S形行走方法、最大的设备容量相结合时效果最佳，然而，节约启发式算法与最大跨度行走路线、较小设备容量相结合时效果最佳。 3.3.1订单分批中节约启发式算法的思想节约启发式算法的基本思想史车辆路径问题中的节约算法在订单分批中的应用。节约算法就是将一对订单合并成在一条路线上进行拣取的新订单，使合并后的行走距离比分别拣取这对订单具有最大的节约量。在订单分批问题中，订单相当于车辆路径问题中的城市，订单合并后产生的行走距离节约量相当于城市合并配送后节约的里程数。两者本质的不同在于合并的订单中，存在具有共同存储位置的品项。对这些品项的拣取，秩序访问依次就能同时满足多张订单的要求。另外，由于车辆容量的限制，并不是每张订单都能与其他订单合并成一批进行拣取25。3.3.2订单分批中节约启发式算法实施步骤1输入一个时间段内所有需要拣取的订单数据，包括拣货车的容量；2将所有的订单两两组对，计算其品项数之和，如果品项数之和小于等于，则计算其行走距离节约量； 3将节约量按由大到小非增序排列； 4选择节约量最大的组合合并成一批，组成一个新的订单，形成初始批量。5分别以两个选定订单为基准订单，检查与两个基准订单与其余订单的所有节约量，将节约量按由大到小非增序排列。6选择节约量最大的组合。 7将当前批量中的订单从带分批的订单集合中移走转至4。8如果所有的组合都已经检查完成，但仍有订单没有分配到适当的批中，则将这些订单单独成批。第四章 订单分批拣选启发式算法的研究与应用仓库配送中心拣货作业中的订单分拣是为了提高拣货作业效率而把多张订单集合成一批，进行批次拣取作业，其目的是缩短拣取时平均行走搬运的距离和时间。若再将每批次订单中的统一商品品项汇总后拣取，然后再把货品分配给每一个不同的顾客订单，则形成批量拣取，这样不仅缩短了拣取时平均行走搬运的距离，也减少了重复寻找储存位置的时间，而使拣货效率提高。批量拣取特别适合与品项数少而订单数量庞大的系统，越是少量多次的配送，批量拣取就越有效。订单分批问题用数学语言来表达就是指将订单按照适当的方式进行分批并确定批量拣取路径以使目标函数达到最优。批量拣取的基础目标有两种：（1）减少拣货行走的总时间；（2）减少拣货行走的距离进而提升产能和改善交货期。本文以最小化拣货行走距离为目标构造了订单分批问题的数学模型，提出了解决该问题的两种启发式算法：节约启发式算法；基于聚类分析的启发式算法。其中节约启发式算法需要事先知道路径策略，而聚类问题的分析求解提出了多种相似系数的计算方法，且相似系数的计算不需要事先知道路径策略。在提出解决问题的两种启发式算法之后，还将给出一个用这两种方法求解该类问题的实例。节约启发式算法和基于聚类分析的启发式算法均可以有效求得订单分批问题的近优解，能够广泛运用于大型配送中心和流通仓库的拣货系统，以提高拣货的效率。4.1 订单分批问题的数学模型4.1.1 模型假设（1） 仓库结构已知；（2）一个订单至少包含一个品项；（3）保持订单的完整性，不允许分割订单；（4）订单数据及品项存储位置已知；（5）每张订单的品项数不超拣货车的容量；（6）每批订单的拣取都能在1条拣货路线上完成；（7） 任意拣货路径的起点和终点都在出入口，即拣货员推着拣货车从出入口出发，按设定的路径策略从仓库中拣出货物，最后返回出入口；（8） 拣取时不存在缺货现象和紧急插单情况；（9） 订单数据输入后，计算机能按事先规定的路径策略对需要拣取的品项进行路径排序，形成顺序拣货单。4.1.2 数学模型的建立根据假设，可以将订单分批拣货问题描述为：假设有a个订单On(n=1，2，a)需要拣取，每个订单中包含若干品项，第n个订单中的品项数为qn。现要求在不分割订单的情况下，对a个订单进行分批拣取，每批订单的拣取在一条路线上一次完成，并使拣取所有订单的总行走距离最小。订单分批拣货问题的数学模型可以表示为：目标函数： mintSdtxt (4.1)约束条件： n=1aqnantC (4.2) tSantxt=1 , n=1,，a (4.3) xt0,1,ant0,1 (4.4) 式中: a需要拣取的订单总数 C拣货车的容量 qn第n个订单中所有品项的数量 S所有可行订单批量集合t每个可行的订单批量，tSajs=1 订 单 n 属 于 第t 批 0 订单n不属于第t批 n=1,2,，adt拣取第t批订单中的所有品项的总行走距离xt=1 第t批 被 选 中0 第t批没被选中 模型的目标函数是订单分批后，使各批订单拣取路线总和最小。约束条件（4.2）表示每批订单包含的品项数不超过拣货车的容量，约束条件（4.3）和（4.4）表示每个订单只能被分配到一个批量中。4.2 节约启发式算法求解订单分批问题过程当模型订单数量大于3时，属于NP完全问题，其求解较复杂。节约启发式算法的基本思想是车辆路径问题中的节约算法在订单分批中的应用。节约算法就是将订单m和订单n合并成在一条路线上进行拣取的新订单，使合并后的行走距离比分别拣取订单m和n具有最大的节约量Smn=dm+dn-dmn。在订单分批问题中，订单相当于车辆路径问题中的城市，订单合并后产生的行走距离节约量相当于城市合并配送后节约的里程数。两者本质的不同在于合并的订单中，存在具有共同存储位置的品项。对这些品项的拣取，秩序访问依次就能同时满足多张订单的要求。另外，由于车辆容量的限制，并不是每张订单都能与其他订单合并成一批进行拣取25。4.2.1 初始批量的形成（1）输入一个时间段内所有需要拣取的订单数据，包括拣货车的容量；（2）将所有的订单两两组对，计算其品项数之和qmn=qm+qn(m=1,a；n=1,a；nm)，如果qmnC，则计算其行走距离节约量Smn=Snm；（3）将节约量按由大到小非增序排列；（4）选择节约量最大的组合Skp=maxSmn合并成一批（如果有两组数字相同，则任选一组）；有订单Ok和Op组成一个新的订单，即Ot=Ok,Op形成初始批量。4.2.2 批量的优化（1） 分别以订单k和订单p为基准订单，检查Smk和Snp(m=1,，a；n=1,，amp,nk)，将节约量按由大到小非增序排列。（2）选择节约量最大的组合，存在两种情况： maxSmk，Snp=Sxk,则计算Ot和Ox品项数之和qtx=qt+qx,若qtxC,则将订单Ox加入当前批Ot中形成新的当前批Ot=Ot+Ox=Ok，Op，Ox。否则对余下的组合重复（2），直到找不到符合组成条件的订单为止。当前批Ot即为找到的优化批量。 maxSmk，Snp=Syk,则计算Ot和Oy品项数之和qty=qt+qy,若qtyC,则将订单Oy加入当前批Ot中形成新的当前批Ot=Ot+Oy=Ok，Op，Oy。否则对余下的组合重复（2），直到找不到符合组成条件的订单为止。当前批Ot即为找到的优化批量。（3）将当前批量Ot中的订单从带分批的订单集合中移走转至4.2.1中步骤（4）。（4） 如果所有的组合都已经检查完成，但仍有订单没有分配到适当的批中，则将这些订单单独成批。4.3 节约启发式算法的算例分析仓库结构为长方形，出入口位于仓库的一角第1个巷道的中心处，共有8个拣货巷道，货架为底层固定货架，每排货架上沿巷道方向有15列存储位置，图4-1为仓库货架二维平面图。已知货架长15个单位，巷道中心距离为4个单位，拣货车容量为10品项。现有5个需要拣取得订单，包括8种不同的品项。订单订购的品项数分别为：订单1为5品项；订单2为7品项；订单3为5品项；订单4为3品项；订单5为4品项。订单品项在仓库中的分布如图4-1所示。图4-1 仓库结构及订单品项分布4.3.1 节约启发式分批由条件可知：5张订单订购总品项数为24，拣货车容量为10，所以要拣取所有的品项至少要分3批才能实现。由于分批的目的在于最小化订单拣取的行走距离，所以在分批之前必须确定相应的路径策略。路径策略主要有穿越策略（即S形策略）、返回策略、重点策略、最大间隙策略及优化策略等。本课题采用最简单的穿越策略。穿越策略就是一个拣货员从仓库的一端进入拣货通道，而从该通道的另一端退出进入下一个包含拣取位置的拣货通道。拣货员从出入口出发，在返回错入口之前按这种方法遍历所有包含拣取位置的通道。节约启发式算法对订单进行分批过程如下：（1）将所有的订单两两分成两组对，如果qmnC(m=1,5；n=1,5；nm)，则计算其行走距离节约量Smn=Snm。因为Smn=dm+dn-dmn，所以S13=d1+d3-d13；S14=d1+d4-d14；S15=d1+d5-d15；S45=d4+d5-d45。下面为S13的计算过程：订单1的拣取路径如图4-2所示。通过通过路径可计算出d1=108。订单3的拣货路径如图4-3所示。图4-2 订单1的拣货路径图4-3 订单3的拣选路径通过通过路径可计算出d3=116。若将订单1和订单3组对，则其拣选路径如图4-4所示。图4-4 订单1和订单3组对的拣选路径通过路径可计算出d13=176。 得S13=d1+d3-d13=48同理依次可以计算出所有的订单两两组对后的行走距离节约量Smn（如图4-5至图4-10）计算结果如表4-1所示表4-1 订单组合节约值表订单123451234844856865787848 注：表示不符合组合条件图4-5 订单3、4组合成批的拣货路径计算其路径的行走距离ds=d34=116。（2）选择节约值最大的3、4组合，形成初始批量。令Os=O3,O4,则 qs=q3+q4=8C，不满足组合条件，放弃。（5）从余下的排序中选择节约值最大的S31，计算qs+q1=8+5C,不符合条件，放弃。（6） 重复步骤（5），均不符合组合条件，所以只将订单3、4组成批量s中，即Os1=O3,O4 。由于qs=8，后面的组合不必再检查，当前批s即为第1个优化批量。其拣货路径如图4-5所示，总行走距离ds=d34。（7）将订单3、4从待分配订单中移走，此时只剩余订单1、2、5两两组对的节约值（如表4-2所示）。转至步骤（1），同理得到第2批优化分批Os2=O1,O5，其拣货路径如图4-6所示，总行走距离ds2=d15。（8）再将订单1、5从待分配订单中移走。此时只剩下订单2，而q2=7C,所以订单2自成一批。至此分批完毕，结果为（1,5,），2,（3，4）。图4-6 订单1、5组合成批的拣选路径其路径的行走距离ds2=d15=138。图4-7 订单1、4组合成批的拣选路径图4-8 订单2、4组合成批的拣选路径图4-9 订单3、5组合成批的拣选路径图4-10 订单4、5组合成批的拣选路径表4-2 订单组合节约值订单125125784.3.2 比较分析在拣货作业中，最简单的对订单进行分批的经验方法就是遵循先到先拣原则，很显然，在受到拣货车容量约束的条件下，算例按先到先服务的原则分批结果为（1），（2），（3,4），5。下面依然采用S形启发式路径策略计算不分批和2种分批情况下的行走总距离，即模型中目标函数的值。不分批：D=d1+d2+d3+d4+d5=108+146+116+86+108=564先到先服务分批：D=d1+d2+d34+d5=108+146+116+108=478节约启发式分批：D=d15+d2+d34=138+146+116=400从计算结果可以看出：节约启发式分批总行走距离最短，不分批行走距离最长，先到先服务介于两者之间。订单中重复产品的数量越多，不同订单产品分布的巷道重复产品的数量越多，不同订单产品分布的巷道重复数越多，节约算法中行走距离的节约量也会越大，分批拣货的优越性就会越明显。4.4 订单分批问题的聚类分析聚类分析又称群分析，是研究分类问题的一种多元统计方法。所谓类通俗地说就是指相似元素的集合。严格的数学定义比较麻烦，在不同问题中类的定义是不同的。聚类分析一杯广泛应用于各种工程的科学领域，如心理学、生物学、医学、数据分解、模式识别、成组技术及生产流程分析等。订单那分批问题的聚类就是通过一定的聚类准则，将订单分成不同的类别、然后对每一类订单进行批量拣取作业。分类的目的是为了最小化拣取所有订单那的行走距离。问题的关键在于选取聚类准则和类间的相似性度量20。4.4.1 特征向量相似度的测量可以通过特征向量来进行定义。Hwanget al.在研究自动化仓库拣货中的订单处理时，为了定义订单之间的相似性，定义了两个特征向量。根据其特征向量的具体含义，文中将其称为订单品项的储位特征向量和坐标特征向量。因为以上两种特征向量不是本文研究的方向，所以在这里就不再多做介绍。4.4.2 相似系数两个对象之间的相似度（similarity）是指两个对象相似程度的数值度量。两个对象越相似，它们的相似度就越高。在任何聚类分析中，相似性度量的选择都是非常重要的。目前用得最多的方法之一就是相似系数，性质越接近的样品，其相似系数的绝对值越接近1，而彼此无关的样品，其相似系数的绝对值越接近零。对订单分批问题，借鉴种子算法中的相似性度量原则，分析总结一下集中相似系数的计算公式20。（1）储位相似系数 两个订单中品项的共同储位数的比例可以用两个订单的储位特征向量表示如下： Smn=VAmVAn,VAmVAm,+VAnVAn,-VAmVAn, (4.5) VAm表示VAm转置。这里的相似系数类似tanimoto系数，具有“距离”的性质。在订单分批问题中，表示两个订单具有的共同的储位数于两个订单总储位数的比。（2）面积相似系数 面积相似系数可以由订单的坐标向量来表示。 Smn=minam,anminbm,bnambm+anbn-minamanminbm,bn (4.6)其实实质就是订单Om，On的共同储位面积，于链各个订单那储位面积的并集之比。用坐标来表示就是（0,0），（0，minbm，bn），（minam，an，minbm，bn）及(minam，an，0)组成的矩形面积与订单Om，On所组成的两个矩形面积并集之比。 （3）巷道相似系数判断两个订单的相似程度，除上述根据两个订单那拥有的共同储位和品项分布