订单分批及并行化拣选路径的研究
摘 要 随着网络通信、信息技术及移动互联网的飞速发展，电子商务作为一种新型的商业运作模式正逐渐渗透到人们生活的各个方面。配送中心作为物流系统的一个重要节点。客户购买向多品种、小批量的发展，配送中心拣货的种类和数量不确定性、无规律性急剧增加，使拣货作业的劳动量占配送中心所有作业量的60%，时间耗费主要集中在工作人员的行走消耗上，如何减少拣货作业的行走耗时，提高配送中心的效率，对配送中心运作效率具有至关重要的影响。本文提出对订单进行优先度智能分批拣选及并行化拣选，有效提高了配送中心的运作效率。
【关键词】配送中心 订单分批 拣选优化 并行
订单批量问题是指将订单按照算法设定的方式进行分批并确定批量拣取路径以使拣货员行走距离最短。批量拣取的基础目标为：（1）缩短拣货行走的距离；（2）减少拣货行走花费的时间。本文以最小化行走距离、最小行走时间为目标构造了订单分批问题的数学模型，并以分批模型进行并行化实现，此实现方法可以有效求得订单分批问题的近似最优解，能够广泛运用于大型物流配送中心。
1 订单分批数学模型的建立
1.1 模型的假设
（1）拣选人员或拣选设备数量至少为一个；
（2）每张订单至少包含一个品项以上的货品；
（3）订单数据及品项存储位置已知；
（4）每批订单都必须在1条拣货路径上必须完成；
（5）单个品项的容量和质量不能超过单个拣选设备的容量和质量限制；
（6）订单不允许分割到不同的拣选批次中，但是在同一个拣选批次中；
（7）不存在缺货和紧急插入新订单的情况；
（8）订单数据输入后，计算机能按事先规定的路径策略对需要拣取的品项进行优先度排序，形成顺序拣货单；
（9）拣选过程中行走的路径巷道采用S 型策略。
1.2 模型的建立
1.2.1 建立模型
由假设条件，可以将订单分批拣货问题描述为：配送中心有 n个订单Oi（i=1，2，…，n）需要拣取，每个订单中包含有若干个品项，第i个订单中的品项数为Qi。要求在不分割订单的情况下，对n个订单进行分批拣取，每批订单的拣取在1条路线上行走1次完成况且拣取所有订单的总行走距离最小。订单分批拣货的数学模型可以表示为：
目标函数：f=min∑ni=1 DPMjp Xp （1）
约束条件：∑nj=1qj ajp≤C （2）
∑ ajp xp=1 j=1，2，…，n （3）
Xp{0，1}，ajp{0，1} （4）
表达式中个参数含义：
C——拣货车的容量
Qj——第j个订单中所有品项的的数量
P——所有可行订单批量集合
p——每一个可行的订单批量，pP
ajp=
j=1，2，…n；
Dp——拣取第p批订单中的所有品项的总行走距离
Xp=
模型目标函数式（1）是求解将订单分批后，各分批订单拣取路线长度总和最小。约束条件式（2）表示每批订单中包含的总品项数不超过拣货货车的容量，约束条件（3）和（4）表示每个订单只能被分配到1个批量中。
1.2.2 优先度智能分批策略
订单在分批过程中由于订单品项和数量各有不同，适用条件也各不相同，如何规划订单分批首先要做的就是对订单按优先度进行排序，然后根据算法设定的参数进行详细规划，常见的订单分批方式主要有以下几种：总合计量分批、时窗分批、固定订单量分批、智能型分批，本文面向多品种、小量订单提出优先度智能型分批策略进行分批，该策略模型图1为：
模型图的策略描述为：
（1）将固定一段时间内的订单，依据紧急程度排序。
（2）确定步长，步长=总订单数/系数。
（3）依据订单的时间紧急程度，从最紧急的第一步长、第二步长......订单中选取订单品项数量最多的拣选订单分为一批。
（4）在剩余订单中，从最紧急的第一步长、第二步长......订单中选取品项存储位置最近拣选订单分为一批。
（5）在剩余订单中，从紧急的第一步长、第二步长......订单中选取拣选路径最长的订单的拣选订单分为一批。
（6）依次类推完成订单的分批。
1.3 并行分拣调度
对订单进行分批后，成批组的订单被交由分拣仓库进行分拣，系统的总任务集T= {T1，T2，…，Tp}，其中p为当前拣选订单的分批数，通常一个订单会涉及一个品项及一个以上品项数的分拣，其并行分拣调度的核心就是根据给定的任务集 T 来构造一个调度方案J*=（J1*，J2*，..，Jp*），在这个调度方案中将各子任务Ti合理分配至任务队列 Jk中并确定 Ti的分拣方案，使整个系统占用资源冲突分拣时间延误减少，并在满足一定约束条件的情况下完成任务集 T 的总花费时间最少。
因此，调度问题的目标函数为：
Min Z=MAX C（Jk），k=1，2…，m. （1）
Min t=∑ni=1Oit1Qi （2）
式中C（Jk）成任务队列 Jk中所有任务所花费的时间，包括取货时间及因冲突造成的等待时间，Oi第i个订单，ti拣选第i个订单所花费的时间，Qi是第i个订单包含的品项数。
算法设计：
开始
（1）分批订单矩阵、任务队列矩阵、资源矩阵M、生成空的缓冲矩阵 Q、禁忌表 Bt和空闲资源表的初始化，Bt长度等于分批里子订单的数目。
（2）从任务队列中选择下一个队列，k++，读空闲资源表判断其工作状态，若为状态忙则重复 3）；若为状态空闲则开始 4）
（3）读取禁忌表 Bt，判断该任务集中是否有冲突品项。若没有，则可以对该批订单下的所有子订单进行一次拣选，若有进入4）。
（4）计算任务集中所有任务的订单品项冲突等待时间，计算拣选总花费时间进行拣选，任务从任务队列中删除，修改禁忌表和空闲资源集。
4 算例求解
4.1 算例数据
根据历史记录信息，配送中心平均每3分钟处理61个订单，每个订单平均包含5种商品，所需要话费时间为5860秒，而本次试验选取1分钟共21张订单O={O1，O2， O3， O4， O5， O6，…On}，根据分批策略进行分批，得到P={P1，P2，P3，…，P5} 共4批， 其中
P1={O2，O3，O7，O16，O18 }
P2={O1，O5，O10，O13，O21 }
P3={O4，O11，O12，O17，O19 }
P4={O6，O8，O9，O14，O15，O20 }
设定任务集为T={T1，T2， T3， T4， }，其中每个任务集对应的子任务的商品可能存放于多个巷道内。利用并行分拣调度进行任务集拣选任务分派得到任务资源矩阵和分拣方案的分拣时间，如图2所示：
4.2 算例结果
（1）P1分批订单是品项数量最多订单，拣选时间为199 s。
（2）P2分批订单是拣选路径最长的拣选订单，拣选时间为521 s。
（3）P3、分批订单是品项存储位置相近的订单，拣选时间分别为299s。
（4）P4分批订单是品项巷道分布广的订单，拣选时间为450s。
完成总订单分拣的时间为1469s。而完成平均每3分钟处理的63个订单约为4407s，平均节约时间为1453，有效提高配送中心的拣选效率。
5 结论
本文提出对配送中心订单先分批后并行的拣选策略，在订单到达后进行分析归类、拣选时进行并行调度。最终通过实验表明，具有以下优点：a.有效提高配送中心的拣选效率、缩短拣选时间。b.减少工人在仓库的行走距离。
参考文献
[1]张晓川.物流学-系统，网络和物流链[M].北京：化学工业出版社，2005.
[2]李诗珍.配送中心拣货作业优化设计与控制研究[D].成都：西南交通大学，2008.
[3]李诗珍，王转.订单拣取路径优化研究[J].物流技术与应用，2002（5）.
[4]马士华，文坚.基于时间延迟的订单分批策略研究[J].工业工程与管理，2004（6）.
[5]李哲.物流中心拣选单处理及拣选路径优化研究[D].大连：大连海事大学，2011.
[6]Kenneth B Ackerman.Praetieal hand book of warehousing [M].MaterialsManagement，1990.
[7]郭进.多订单并行分拣问题的优化研究[D].上海交通大学中美物流研究院，2012（2）.
作者简介
魏伟（1988-），男，陕西省安康人。硕士学位。主要研究方向为软件复用技术。
作者单位
西安建筑科技大学信息与控制工程学院 陕西省西安市 710055
