一种配送中心订单分拣优化问题的研究

马 超，雷 斌，陈洪满

(兰州交通大学 机电技术研究所，甘肃 兰州 730070)

一种配送中心订单分拣优化问题的研究

马 超，雷 斌，陈洪满

(兰州交通大学 机电技术研究所，甘肃 兰州 730070)

研究一种配送中心订单分拣优化问题．目标函数设置为总的拣选订单行走的距离，使用遗传算法优化订单的分批组合，并且在本文中订单分批时，先挑选种子订单，通过对种子订单有策略的选取，最终达到优化拣选的总距离的目的．所采用的模型、方法对订单分拣有较好的优化．

订单拣选；订单分批；遗传算法；优化

0 引言

在现在物流供应链中，配送中心起了很大的作用，它可以很好的满足客户的特定要求，比如配送时间．目前其类型仍以密集型为主[1]，其中拣货作业流程在其中占了很大比例，拣选作业的时间投入也占整个总体运作时间的40%左右[2]，所以正确的规划和设计拣选作业对于提高整体的运作效率有很大的影响．

订单分批拣选，是为了应对不同客户的要求，将货物按订单要求取出的过程．在拣选之前，要进行订单分批，即对订单按不同的需求批次进行拣选．这种分批模式的目的是为了减少人力物力的消耗和缩短拣选路程[3]．

之前的研究表明，订单分批问题是典型的NP—hard问题[4]．很多学者对此问题采用启发式算法来研究，而这些算法的核心内容主要是种子算法和节约算法两种思路．节约算法[5]，它是将多路径或者短路径的订单合并转换到长路径的订单中，从而实现优化拣选路径的方法．种子算法就是当全部订单未分批时先选出一个订单作为特定订单，将其分配到其他的批次中．剩余的订单也按照某标准插入其中，整体形成一个拣选批次，来实现高效分批的目的[6]．

本文研究问题不同之处在于选择S形路线进行拣货[7]，以体积较大和重量较重两个限制条件来选择种子订单．考虑拣选设备的容量和承重并采用单区型仓库模型为假设条件，以拣选的行走距离为优化目标来测试此模型的优化效果，并且对该模型的求解方法用遗传算法．

1 订单分批拣选问题描述

为了本论文的研究需要，做以下假设：

图1 仓库的布局结构

(1)配送中心的存储空间由货架并行排列行成，本文的模型是单区型仓库,基本布局结构如图1所示．

(2)拣选人员或拣选设备数量至少为一个．

(3)忽略货架高度所带来的位移，该位移不计入拣选路径的计算．

(4)每张订单至少包含一个货品，并且订单不能被拆分为多个批次进行拣选．

(5)每批次有N个拣选人员(拣选设备)同时进行拣选，拣选完一个批次后继续进行下一个．

(6)每一个拣选设备的承重和容量限制是同等的，并且单个货品不能超过一个拣选设备的质量和容量限制．

(7)对于每个批次拣选订单上的所有物品，不能超过该拣选批次中所有拣选设备的总容量和总重量限制．

(8)没有紧急插入订单和缺货的情况．

(9)拣选单上物品的存储货位是已知的．

(10)拣选过程中采用的是改进S型策略．

2 拣选数学模型建立

订单分批的问题模型可以被描述为：假设有N个订单Qn(n=1,2,3,…,N)，用来拣选设备的数量为M，每个订单含有多个货品且必须拣选完毕．本文要求对N个订单分批拣选，由m个拣选设备对每批订单同时拣选，在此期间，被拣选的订单不能分割到其它批次．但在同一个批次中，订单可以划分到其它拣选设备上完成本次拣选，最终实现总的拣选路径最小．本文中的订单分批数学模型如下所示：

目标函数：

(1)

约束条件：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

N：需要拣选的总订单数；

M：拣选人员(拣选设备)的数量；

On：订单n；

vnk：批次k中，订单n中货品的容积，k=1，2，…，K；

qnk：批次k中，订单n中货品的重量，k=1,2,…，K；

no_batchk：第k个拣选批次，k=1,2,…，K；

K：订单的分批批数；

capmv：拣选设备m的最大载货容积；

capmq：拣选设备m的最大载货质量；

L：路径总数；

Tik：拣选批次k包含的拣选路径I，i=1,2,…，L；

Di：按路径Ti进行拣选行走的总距离；

Pnk决定订单n是否在批次k中；

Xni决定订单n是否在批次i中；

Z：货品种类数．

(1)是目标函数，即对全部订单分批拣选得到的最小的总拣选路径．(2)表示任意拣选批次中，被拣选的总重量要低于该批次拣选设备的最大承重．(3)表示任意拣选批次中，被拣选货物的总体积要低于该批次拣选设备的最大容量．(4)表示任意订单中，拣选设备的数量要多于拣货路径数量，即不会出现闲置的拣货路径．(5)表示订单不可分割，由一个拣选批次完成拣选．(6)表示任意拣选批次中，所有货物能由拣选设备一次性拣选完成．(7)表示订单n在分批k中时取值为1，否则为0．(8)表示订单n在路径i中时取值为 1，否则为0．(9)表示订单都会被分配．(10)表示每个订单只会分配一次．

3 遗传算法的改进与实现

遗传算法的操作主要有以下几种步骤：(1)确定对应的编码方法；(2)交叉、变异[8]；(3)合理的选择．现具体描述如下：

(1)染色体编码方法

把订单集合S{O1,O2,O3…,ON}中所有的订单进行参数编码操作，本文中采用的模型是多个批次和多个拣选设备，所以选取r-t这种方式来表示，r代表订单所在的批次，t代表订单由哪个拣选设备．例如{2-31,2-12,…,r-tn}中数项2-3表此位置的订单被分配到第2个批次的地3个拣选设备上．

(2)种子订单设置

根据De Koster[9]的研究结论，种子订单要根据体积和重量这两个限制条件来综合确定，其剩余的订单插入是由计算机随机完成的，但不会超过拣选设备的容量限制．

(3)适应度函数设计

在求极大值maxx∈(a,b)f(x)问题的时候，适应度函数可以直接用模型的目标函数f(x)来表示[10]．

(4)选择策略的设计

这是选择概率算子，每个染色体都要按上式算出其选择概率算子，然后应用其选出用于交叉繁殖的染色体．

(5)交叉操作

本文选择的交叉方法是单点交叉，而且交叉点是随机选取的，交叉的同时没有改变订单所属的批次．所有的交叉完毕后，形成新一代群体，比如：

父代：A=(A1,A2,A3,A4,|A5,A6,A7,A8)B=(B1,B2,B3,B4,|B5,B6,B7,B8)

子代：A=(A1,A2,A3,A4,|B5,A6,A7,A8)B=(B1,B2,B3,B4,|A5,B6,B7,B8)

(6)变异操作

遗传算法中的变异操作是将染色体编码中的某些基因位用该基因位的其它等位基因来替换，来形成一个新的个体．比如：

父代：A=(A1,A2,A3,A4,A5,A6,A7,A8)A=(A1,A2,A3,A4,|B5,A6,A7,A8)

变异后的子代：A=(A1,A2,A3,A4,B5,A6,A7,A8)B=(B1,B2,B3,B4,|A5,B6,B7,B8)

4 实验计算结果

本文的研究问题所采用的数据是参考万杰[11]的研究数据，但是在算法上进行了不同的改进,添加了设计问题中对应的限制条件．本文中采用的遗传算法的编程是通过Visual C实现的．其基本数据如表1所示．

表1 算例基本初始数据

由于初始种群是随机生成的，而且在遗传算法中有以一组数据对其结果有重大影响，称之为控制参数[12]．本文中的控制参数：种群规模chro=20，最大遗传代数为500，迭代次数为50．为了加快寻优速度，在此我们将交叉概率设为1，就是每次都要交叉．

在多次数字试验中，结果都比原文中的寻到的值优．表2列举了相应的数据，并且和其参考文献采用的的基本遗传算法GABM进行对应数据的比较，本文中含有种子订单选择的遗传算法描述为GASM．

表2 实验结果比较

表2中方差反映了不同批次策略的劳动强度的平衡状况，数据大，说明一个批处理过程的差异程度越大．很容易看出，在有相同的遗传代数的前提下选择种子订单拣选方法进行试验，拣选总距离相对较小，那按照一定的条件比随机选择种子的订单更好．

5 结论

在本文中，用遗传算法来求解构建的订单分批模型，以拣选距离最短为最终目标，采用了不同于以往的分批优化算法，在初始的订单分批中加入了种子订单拣选的策略．通过这种有效的策略，进一步使拣选的总距离得到了显著的优化．

由于遗传算法的灵活性，能够很容易的运用到各种不同的假设情况和不同的仓库布局模型，所以在以后的实验中，相应的限制条件可以适当变更，更加符合现实．即在拣选路径方式，种子订单选择方法、拣选机械限制条件等发生变化时，订单分批拣选的优化问题．

[1]R.D.Koster,T.Le-Duc,K.J.Roodbergen.Design and control of warehouse order picking:a literature review[J].European Journal of Operational Research，2007，182:481～501.

[2]张大海.物流配送中心订单分批配送问题研究.中国科学技术协会、河南省人民政府.第十届中国科协年会科技人力资源与区域经济发展论坛论文集[C].中国科学技术协会、河南省人民政府,2008.

[3]李 哲.物流中心拣选单处理及拣选路径优化研究[D].大连：大连海事大学，2011.

[4]王艳艳,吴耀华,孙国华,等.配送中心分拣订单合批策略的研究[J].山东大学学报(工学版)，2010，(3):124～140.

[5]刘进平.配送中心分拣系统设计方法研究[D].大连：大连海事大学,2011.

[6]陈伊菲,刘 军.仓储拣选作业路径VRP模型设计与应用[J].计算机工程与应用，2006，(3):97～104.

[7]李诗珍,王 转.订单拣取路径优化研究——S形启发式方法在配送中心拣货中的应用[J].物流技术与应用,2002,(5):67～70.

[8]J.H.Holland.Progres in Theoretical Biolo-gy[J].Adaptation，1976，(4):264～293.

[9]R.D.Koster,E.S.Van der Poort,Wolters M.Efficient order batching methods in warehouses[J].International Journal of Production Research，1999，(7):1479～1504.

[10]王银年.遗传算法的研究与应用[D].无锡：江南大学,2009.

[11]万 杰,张少卿,李 立.基于遗传算法的配送中心订单拣选优化问题研究[J].河北工业大学学报,2009,(5):10～14.

[12]李延梅.一种改进的遗传算法及应用[D].广州：华南理工大学,2012.

ResearchontheDistributionCenterOrderPickingBatch

MAChao，LEIBin，CHENHong-man

(Mechanical and Electrial Technology Institute,Lanzhou Jiaotong University,Lanzhou 730070,China)

In this paper,the distribution center order picking optimization problem was researched.The objective function was set to the total distance travelled by picking orders using a combination of genetic algorithm optimization batch orders.And in the order in batches,the first selection was the seed orders.By strategically selecting seed orders, the purpose of optimizing the total distance was ultimately achieved.The model and method used in the paper were the optimization for order piching.

order picking;order batching;genetic algorithms;optimization

郎集会)

2014-05-26

甘肃省自然科学基金项目(1310RJZA056)；兰州交通大学青年基金项目(2013016)

马 超(1988-)，男，河北省石家庄市人，现为兰州交通大学机电技术研究所硕士研究生．研究方向：物流信息调度优化．

TP312

A

1674-3873-(2014)03-0118-04