1. 研究目的与意义（文献综述）

1.1研究目的

配送中心的基本作业流程包括收货、验收入库、补货、储存保管、分拣、打包和配送等环节，在配送中心的所有作业中,拣货作业是其中十分重要的一环,其所扮演的角色相当于人体的心脏、空调系统的压缩机^[1]。拣选作业是配送中心为了响应客户的订单需求（订单所规定的商品品名、数量和储位），将商品从存储区或缓冲区取出，搬运到在指定场所，并按照客户配货要求配送的活动，包括订单分批、拣选路径优化和物品的储位安排等。在配送中心的三项核心作业：仓储、拣选和配送中，和其它两项作业相比，拣选作业在以人工为主的拣选系统中往往是劳动力最密集的作业，在自动化拣选系统中，往往是资金最密集的作业，其劳动量约占配送中心内部总作业量的 60%。并且其作业成本占仓库总运作成本的50%-75%^[2]。图1-2是配送中心物流成本结构的比例分析，由此可见，拣货作业和配送作业所占的成本比例几乎达到了80%，而配送作业发生在配送中心之外，不可控的影响因素比较多，所以，拣选作业是降低物流成本，挖掘“第三利润源泉”的重要环节。提高拣选作业的效率，将各项作业时间缩短，对配送中心综合效益的提升和成本的降低有很大的促进作用。

影响拣货效率的因素有很多：储位安排、仓库布局、货架设计、拣选设备、拣选策略和拣选路径等，配送中心每天面对成千上万的订单，因客户需求的多样性和不确定性导致订单信息灵活多变，因此在固定设施上所做的优化改变不仅容易受到空间或其它条件的限制，而且还需要大量的资金投入，灵活性也不高。研究表明，在配置相同的情况下，对拣选的方式及策略进行一定程度的改进，配送中心的作业效率可以达到几倍或者十几倍的提升效果^[3]。而在拣选策略中这些年订单分批策略也一直备受许多专家学者的关注。国内学者李诗珍认为对缩短拣货作业的总时间影响最大的活动就是分批策略^[4]。

本文研究的拣选系统是以人工为主的“人到货”的拣选系统，在实际中，尽管近年来自动化仓储系统的技术有了很大的发展，但由于对意外变化的反应灵活性高，80%的订单拣选系统都是人工操作的。本文讨论的内容是配送中心在批量拣货时所采取的分批策略，根据订单的实际到达情况，选择合适的分批策略，建立合理的订单分批模型，在一定程度上能缩短拣选环节中行走的总距离或时间，提高配送中心的运作效率和服务水平。

在进行研究时，本文重点要解决如下几个问题：

（1）在订单同时到达和订单实时到达的情况下，开发相应的订单模拟生成管理系统。

（2）订单实时到达的情况下，针对配送中心无配送时间约束的特点下，如何制定相应的合理在线订单分批策略，建立合适的数学模型，设计相应的优化算法，将实时到达订单生成拣选批次并分配给员工进行拣选。

（3）订单同时到达的情况下，如何制定相应的合理静态的订单分批策略，建立合适的数学模型，设计相应的优化算法，将订单生成拣选批次分配给员工拣选。

1.2研究意义

在阅读大量的相关文献后，发现在大部分的研究中，一般将订单拣选作业假设在简单的、静态的、确定的仓库环境中进行，这类研究意味着忽视了订单拣选作业中普遍存在的不确定性、动态性以及复杂性。在电子商务的环境下，配送中心面对的客户订单具有批量小、订购频次高、品种丰富和实时到达的特点，并且客户对物流服务也提出了更高的要求，有更快的响应速度，准确无误及时地送达客户手中，所以在动态环境下，设计相应的符合配送中心特性的订单分批优化策略就显得十分重要了。

订单的生成问题在很多研究中都被忽略了，一般是提前设置好，这样做并没有真正模拟配送中心订单的到达情况，在以后的流程中也都是静态的批量处理，本文的研究内容中实现了订单的模拟到达，并设计了订单的生成及管理系统，更符合配送中心的实际情况，具有现实研究意义。

从配送中心实际的角度来看，对订单分批问题的研究有助于提高拣选作业的效率，缩减人工拣选的作业成本和作业时间，从而提高整个配送中心的运作效率，降低物流成本，满足顾客的配送要求，提高顾客满意度，増强市场竞争力，具有一定的借鉴意义。

1.3订单分批国内外研究现状

订单分批是为了提高拣选作业效率按照一定的规则将多张订单合并成一批，其目的是提升拣选设备利用率，缩短分拣时平均行走搬运的距离和时间。订单分批的概念最早是由AckermanK B.在1990年在文献[5]中提出的，Choe and Sharp(1991)^[6]提出了订单分批有两个标准：拣选位置的相似度和时间窗。

1、 基于相似的订单分批的研究现状

基于相似的订单分批的原理是根据各个订单中物品存放位置之间的相似性大小来判断是否属于同一个批次，因此基于相似的订单分批的核心问题就是在按照某一规则的前提下，准确计算出订单之间的相似程度。Gademannet al(2001)^[7]针对以人工为主的仓库中，建立了以任意一批订单的最大提前期最小化为目标函数的数学模型，采用分支定界法求解订单分批问题。GademannVan De Velde(2005)^[8]同样在以人力为主的仓库系统中，研究订单分批的优化目标更具一般性——拣选行走时间最小化，并且已经证明，当一个批次中被拣选订单的个数不唯一时，订单分批问题被定义为一个典型的NP（Non-deterministicPolynomial）问题。Chenand Wu(2005)^[9]提出了一种基于数据挖掘和整数规划的订单分批算法，根据订单之间的品项重复程度来测量订单的接近程度，以每批订单之间的关联性最大为优化目标，建立了0-1整数规划的订单聚类模型。

由于订单分批问题是NP难问题,并且在实际的拣货系统中不适合用精确算法,所以大多数的研究人员都利用启发式方法来解决这个问题，在人工拣选系统中，比较常用的有种子算法和节约算法。

种子算法的概念最早是由Elsayed^[10]在1981年提出，种子算法分两个阶段形成批次：种子订单的选择和备选订单分配。国外学者对种子算法的研究比较早，所以在种子算法方面有比较系统的研究，表1-1将国内外学者的研究内容进行了简单的介绍和比较。

表1-1 国内外学者研究内容对比

其中,Elsayed(1981)^[10],Elsayedand Stern(1983)^[11],Hwang and Lee (1988)^[12]和Panand Liu (1995)^[15]等文献考虑了单货架AS/RS分拣系统的种子算法;Gibsonand Sharp(1992)^[13],Rosenwein(1996)^[14],De Kosteretal.(1999)^[17],Ho and Tseng(2006)^[18]和Ying-chinHo(2008)^[19]则研究了多货架的拣选系统的种子算法。

节约算法最早是由Clarke和Wright^[22]在1964年提出的，节约启发式算法的基本思想是将运输问题中的车辆路径问题运用到订单分批问题中，它的原理是在拣选车容量限制的条件下，将订单i和订单j合并成在一条路线上进行拣取的新订单，使得合并后的行走距离（行走时间）比分别拣取订单i和订单j具有最大的节约量。Elsayed and Unal(1989)^[23]提出了四种订单分批节约启发式算法，其中SL(Small-Large)算法在订单分批之前将订单分为“大订单”和“小订单”两类，最终能得到最小拣选行走距离。DeKoster etal(1999)^[17]对比研究了在多巷道人工拣选系统中种子算法和节约启发式算法，在两种路径决策下衡量算法的有效性，结果表明，（1）即使是简单的订单分批方法也可以产生比先到先服务好的多的效果；（2）种子算法在分拣设备容量较大且为 S 形路径分拣中是最好的，节约算法在最大差距路径法和小容量分拣设备时结果最优。

国内学者李诗珍等人针对人工操作的人至物的拣选系统，以最小化行走距离为目标构造订单分批问题的数学模型，提出了节约启发式算法，此算法的订单分批结果优于传统的先到先服务分批结果^[24]。李哲(2011)^[25]以拣选路径最短为目标函数，建立0-1整数规划模型，在求解订单分批上采用节约启发式算法，在优化路径上采用改进的蚁群算法。

2、 基于时间窗的订单分批的研究现状

基于相似度的订单分批的研究文献一般假定订单的特性（品项数、订单数量）等信息在分批之前都是预先知道的，研究优化的重点主要集中在如何提高拣货环节效率。而实际上配送中心接收的客户订单可能是实时到达的,这些订单的信息还是无法提前悉知的，并且随着客户的逐渐增多，订单量也越来越多，及时响应客户订单和提高服务质量也变得越来越重要，因此也有不少专家学者研究时窗分批策略。时间窗订单分批的原理首先要根据工作情况设定一个时间窗（时间窗可以是定值也可以是变值），在该时间窗内到达的订单被分成为同一个批次。时间窗分批可以通过两种不同的方式进行，即动态时间窗批处理和固定时间窗批处理(Van Nieuwenhuyseamp;de Koster(2009)^[26])。在动态时间窗分批中，通常以可容纳的客户订单数量来定义拣货设备的容量，它关注的重点是如何确定最优的批量。固定时窗分批则是将特定时间间隔内的到达的客户订单分配到一个批次，它关注的则是如何确定最优的时窗。Choe and Tang(1999)^[27]提出了一个针对单拣选区仓库的可变时间窗分批的时间模型，该系统被设计为一个具有两个队列的排队网络。在第一种情况下，客户订单根据泊松分布到达，并通过FCFS规则生成批次。如果第一个队列中有特定数量的客户订单，则将这些客户订单分配到一个批次并移到第二个队列。在数值实验中，作者重点研究了应该分配给批次的客户订单的最优数量，从而使平均周转时间最小化。Le andKoster(2007)^[28]对双储存区布局的随机客户订单的平均周转时间也做了类似的调查研究。由Van andKoster(2009)^[29]提出了双储存区的固定时间窗模型。Gong andKoster(2008)^[30]提出了动态顺序拣选的系统，并使用轮询模型进行分析，结果表明，这种系统优于传统的拣选系统，有更短的订单等待时间和更高的准时服务完成率。Sebastian Hen(2012)^[31]修改了静态分批的启发式算法，并将其运用到动态分批中，并通过一系列实验来验证算法，结果表明合理的订单分批策略可以大量降低拣选时间。上面这些文献考虑的目标函数一般是最短的拣选行走时间或距离，但事实上有可能还需要考虑交货期，提前期和订单延误后的惩罚等问题。Elsayed etal(1993)^[32]和Elsayed andLee(1996)^[33]研究了时间窗分批方式，建立订单提前期和延误期的惩罚函数最小模型，并采用启发式方法计算模型。Won andOlafsson(2005)^[34]考虑基于顾客响应时间的订单分批问题,提出了SBP和JBP算法,不仅考虑提高拣选效率,而且还尽量降低拣选时间和有效利用拣选设备的容量。Tzu-li Chen(2015)^[35]等人以订单总延迟最小为目标，建立了同时确定订单分批，排序和路径优化问题的IOBSRP模型，结合遗传算法和蚁群算法求解，其中,遗传算法被用来解决订单分批和排序优化问题，蚁群算法被用来解决订单拣选路径优化问题。Henn(2013)^[36]同样考虑订单总延迟最小，在迭代局部搜索的基础上，提出了一种基于属性的爬山启发式算法解决订单分批和排序的问题。Azadnia(2013)^[37]考虑订单的完成期限，构建带权重的关联规则计算订单关于到期日期的关联度，建立基于二进制整数规划的模型，结合遗传算法与旅行商问题，确定最合适的拣选路径。最后，应用遗传算法对构建的批次进行排序，以减少延误时间。

在国内，马士华，文坚(2004)^[38]将延迟制造思想引入到配送中心拣货作业中,提出利用动态时窗来解决目前拣货系统存在的等待时间和块状需求(闲忙不均)的问题，使拣货系统的效率得到极大的提高。王雄志，王国庆(2009)^[39]提出了优化目标为配货时间与客户订单延误时间加权和最小的分批配货问题，并建立了整数规划模型，设计了相应的JBS算法得到初始解，利用遗传算法求解。王艳艳(2010)^[40]等人对人工拣选的仓库，从拣选路径、拣选次数、订单提前期3个方面考虑,构建了拣货作业中订单分批的多目标优化数学模型，依据仿真实验结果,分析了不同的订单数据从拣选时间和优化效果方面所对应的最优求解方法。王旭坪(2014)^[41] 以最小化平均有效订单服务时间为优化目标，构建考虑订单完成期限的在线订单分批混合整数规划模型，并使用改进的固定时间窗方法进行求解模型。赵兰(2015)^[42]以拣选行走时间与分拣时间之和为优化目标，建立了订单分批模型，利用遗传算法求解分批模型并得到优化的分批结果。Zhanget al(2017)^[43]研究了多批在线订单分批处理和排序问题(OOBSPMP)，考虑三种订单处理情况：非高峰、正常、高峰，考虑两种订单分配情况：分配给一个繁忙的拣选区、分配给一个空闲的拣选区，提出一种结合订单波动的订单分配策略。

研究现状总结：

综上所述，国内外学者对人到货拣选系统下的订单分批优化方面进行了一定的研究，主要集中于采用不同的优化方法求解订单分批模型，如种子算法、节约启发式算法、智能算法等，主要体现在对求解算法的创新上。大部分研究在实证分析时的订单数据规模较小，无法准确表现智能算法在处理大规模订单数据时的优势，并且智能算法在处理订单分批后规划的拣选路径可能复杂多变，不适合拣选人员的记忆，因此本文的研究算法主要集中在传统的分批算法的改进。

国内学者对订单分批的研究虽然有很大的发展，但是其整体研究进展依然要落后于国外的研究，在时间窗分批方面，国内学者进行动态分批研究的并不是很多，大部分研究依然是基于静态分批的改进，但是动态分批更符合配送中心订单到达特点，更具有研究意义。

2. 研究的基本内容与方案

2.1研究目标

本文的研究旨在根据配送中心的实际运作情况，对订单分批策略进行优化设计，研究成果“配送中心订单分批优化策略设计与实现”体系，设计了订单的生成及管理系统，通过分析订单历史数据对商品货位进行优化分配，根据订单到达情况，合理选择基于时间的分批、基于数量的分批或者基于种子法的订单分批策略，并选择最佳拣选路径，以此缩短订单拣选时间，提高配送中心运作效率和顾客满意度。

2.2研究基本内容

3. 研究计划与安排

(1)第1周—第2周，2周时间收集并阅读毕业设计过程中相关的各种文献资料，调研，完成英文文献的翻译。提交开题报告并完成开题

(2)第3周，1周时间，进行相关研究理论及方法学习；

(3)第4周—第7周，3周时间，问题建模；并用matlab编写相应算法的代码，完成论文中期检查；

4. 参考文献（12篇以上）

[1] 赵启兰,刘宏志.计划与供应链中的库存管理.北京：电子工业出版社，2003.

[2]马士华,文坚.基于时间延迟的订单分批策略研究. 工业工程与管理，2004, 6:1-4.

[3]李诗珍.配送中心订单分批拣货模型及种籽启发式算法[j].起重运输机械,2009(1).