摘要：针对物流配送中心常见的双区型仓库进货路径的特点，来建立数学模型，然后采用CA算法来求解最优拣货路径，以此来降低物流成本中的拣货作业成本这里采用遗传算法进行拣货路径的仿真试算，同时与S-shape启发式算法，传统穿越策略以及动态规划方法进行比较，最后的出结论证明采用遗传算法优化拣货路径问题，能够非常有效的求解出拣货路径的最优距离，这样也就缩短拣货作业的时间，进而大大提高了物流中心的拣货作业效率。

关键词：拣货;CA算法;拣货路径;物流

中图分类号：F713.36;F252;TP391.9

文献标识码：A

文章编号：1001-5922（2020）06-0171-05

物流中心进行各项内部作业时，其中一项最重要的工作就是拣货作业，拣货作业就是根据订单进行分拣，将客户订购的货物分别从仓库里面挑选出来然后发货的业务。想要提高配送中心的工作效率首要就是提高拣货作业的效率，因为拣货作业工作比较繁琐，人力资源消耗较大，耗时也比较久，作业时间是整个物流配送中心总的作业时间的30-40%，所以对拣货流程的优化就至关重要[8]。订单拣货路径问题可以看作是以指挠沸组合优化问题，如果能够合理地安排订单中货物的拣取顺序，就能够大大减少拣货工作人员在拣货作业是的行走距离，从而加快了拣货速度，客户的等待时间也就大大缩短。优化拣货路径的问题也有了一定的研究成果，当仓库规模比较小时，可以采用分支定界法等方法求解，但是当规模增大时，求解就会变得非常复杂，那么传统的优化方法就无法解决这些问题了。这里主要针对不同的拣货路径所存在的不同特点，然后设计相应的遗传算法对其进行仿真研究。

1 拣货作业

1.1 问题描述

物流配送中心常见的仓库类型就是双区型仓库[7]，所以我们这里研究的问题也是针对双区型仓库而言的。双区型仓库主要是由许多等长的巷道组成，然后在巷道两旁排列一定数量的货架，这些货架是仓库货物存放的主要区域，双区型仓库与单区型仓库相比较而言最大的不同就是它的横向过道有3条，多出的中间这条过道对提高仓库拣货效率有非常大的帮助。常见的仓库示意图如图l所示。

如图中所示，I/O表示仓库的出人口，其中每个货品的储位点由一个小方格代替，订单中需要拣取的货品的储位点也已经在图中标明。方块上所标识的数组即表示其对应的储位标号，例如其中一个数组a-b-c中，a表示该储位所在的拣货的巷道编号，1-10为其取值范围，6则表示该储位位于拣货巷道a的方向，左边用1表示，右边用2表示，c则代表该储位所在的行的编号，取值范围为1-40，例如6-1-26则表示该储位位于仓库的第6巷道左边的第26行。这里我们将同一巷道中左右两边进行拣货时人员移动的距离忽略。

将订单的拣货时间可以分成几个部分，即行走时间，搜索时间以及分拣时间等等。根据相关人员的研究发现，拣货时间中行走时间通常要占到50%以上，由此可见为了有效的缩短拣货时间应该尽可能地减少行走时间，行走时间的长短又跟行走路径的路线长短直接相关[6]，所以为了提高拣货效率应该将优化拣货路径作为重要的研究内容。

1.2 问题分类

根据拣货工作人员所用推车的容量将订单的拣货方式分为一单多车和一单一车两种类型。其中，一单多车是指将一个订单中所需要的全部物品通过一辆推车来回多次从仓库中取回，这也表示这个订单上的货物的总量超过了一辆推车的最大容量;一单一车是指一个拣货订单中所需要的所有货品由一辆推车来回一次从仓库中取回，即该订单的货品总量不超过推车的最大容量[2]。

1.3 建立模型

在研究一单多车拣货路径问题时，我们最需要考虑的就是如何将所需要的的货品合理地分配到每个车次中拣取，以确保其拣货路径最优，该问题问题与运筹学中的涉及的车辆路径问题（VRP）相似[1]，VRP描述的问题主要是当提供一系列的客户点，需要确定合理地行车路线，然后再从车场发车，有秩序的为这些客户服务，这里通常会设定一些约束条件，诸如客户需求量或者车辆最大载重以及时间限制等等，使得总的运输成本控制到最小。

一单多车的拣货路径问题就可以根据这类车辆路径问题（VRP）的数学模型来设计一个合理的数学模型。

A条件假设，我们假设有n次车仓库的出人口出发，到仓库的许多不同的储位去取货品，并假设储位分别为v1，v2：…vn。同时假设源点以及多个储位的位置是已知的。

B目标模型，假设每一趟车次构成一个回路，确认每趟车次的调度和路径安排，从而使其所有回路总的行走距离最小。

C各个变量的表示，第i次车与其对应的回路上的第i个储位点的取货量用O表示，第i条回路上的储位数用Z，表示，第i次车对应的路径用ci表示，第i次车对应的回路上第J储位点用G ij表示，每次车对应的编号用i表示，推車的最大载重量用W表示，某订单上需要拣取货品的总量用V表示，某订单中货品在仓库中的储位数用m表示，源点用v0表示，需要的车次数用n表示，总的行走距离用S表示，第i次车对应的回路中排列第j-1个储位点和第i个储位点之间的最短距离用di（j - 1）j表示，最后第i次车对应回路中的第Z。个储位点和源点v0。间的最短距离用di（li）（0）表示。

2 GA算法求解拣货路径问题

2.1 算法流程

GA算法，即遗传算法，是一种应用非常广泛的计算模型，其主要模拟的是遗传学机理的生物进化过程，以及达尔文生物进化论的自然选择[3]。这里我们建立模型，然后运用遗传算法求解拣货路径问题首次就要确定一个优化的算法流程，如图2所示。

2.2 编码方案的确定

当拣货类型为一单一车时，可以运用自然数编码的方法，将需要拣货订单是上的货品对应其在仓库中的储存位置依次用自然数编号，然后就可以用这些自然数的序列表示拣货的路径。

假设订单中需要拣取的货品有4种，并且他们分别分布在仓库中的4个不同储位上，那么就可以将仓库的出入点用0表示，然后给4个货品依次编号卜4，则可以假设订单的拣货路径为：①出入口一②储位点1→③储位点2→④储位点3→⑤储位点4→⑥出人口，该路径用CA算法可以表示为自然数列{0 12 3 4 0）。

当拣货类型为一单多车时，则订单的拣货任务就需要多次车才能完成，这里我们可以在对应的自然数列中插入0用来显示多车次的特点。

假设订单上需要从仓库拣取的货品有7种，并且这7种货品分别分布在仓库的7个不同储位上，0用来表示仓库的出人口，7个不同的储位点分别用1-7的自然数表示，则这个订单的拣货路径可以表示为：路径1：①出入口→②储位点1→③储位点2→_④储位点3→⑤储位点4→⑥出人口，路径2：①出人口→②储位点5→③储位点6→④储位点7→⑤出人口。该路径用GA算法可以用自然数列表示为：{0 1 2 3 4 0 5 6 7 0）。

这里的0有两层含义，其一是代表拣货路径的起始点，其二则是用来对GA编码进行分隔的，从上面的编码表达中可以看出，我们首先得到的是一个自然数列{12 3 4 5 6 7），然后再从左开始加入一点，当加入到超出推车的最大载重量时，按照加入点的依次进行排列，我们可以得到一条子路径，这也就是拣货作业时的第一次车的拣货路径，可以用数列表示为{1 2 3 4），然后从没有加入点的地方继续依次加入，我们会重新获得一条新的子路径，如此重复这个过程，直到所有的点都被加人为止，最后在所选的可行数列中加入0用来将这些子路径分隔开来，就可以得到最后的总路径，用染色体编码表示为{012 3 4 0 5 6 7 0）。在对染色体编码进行交叉等相关的操作时，可以将编码中表示多车的0从染色体编码中去除，完成算法操作后再根据上面的编码方式插入0，最后得到相应的染色体编码。

2.3 确定适应度函数

这里取哈密尔顿圈长度的倒数为问题的适应度函数[4]，本文中我们将这个函数乘以一个系数用以调节避免其适应度过小的问题，该系数值为：r= 76.2. max dd.Z ch rom 0.5

则该问题的适应度函数為：

Fit（x）= r/X

系数r中的max dd表示拣货任务订单中需要拣取货品所在储位点之间的最长距离，而lchrom则表示的是编码后的染色体长度，也就是拣货路径中所经过的储位点数，X则表示其对应的可行解的拣货路径的长度。

2.4 交叉算子与选择算子的设计

这里的初始解群是通过随机生成的方式产生的，再根据适应度比例从父代中每次选取2个个体，最后根据相应的概率进行交叉变异操作。

以下为交叉操作：

A首先随机选取一个交配区域，如

A=1 2|3 4 5 6|7 8 9

B=9 8|7 6 5 4|3 21

B然后在A的前面或者后面加上B的交配区域，在B的前面或者后面加上且的交配区域，就可以的到

A'=7 6 5 4|12 3 4 5 6 7 8 9

B'=3 4 5 6|9 8 7 6 5 4 3 21

C依次删除A中经过交配区域后与其交配区相同的储位号码，就可以得到最终的子串

A'=765412389

B'=345698721

该方法与其他方法相比较来看，其主要优势在于它可以在即使两个父串一样的情况下，也能够在一定程度上产生变异效果，这也很好的保持了群体的多样化特征。

3 算例测试

3.1 一单一车

这里我们采用C语言在Visual C++6.0环境下进行算例计算。

生成随机的11组储位序号，这11组储位序号也就表示11份订单的拣货任务，然后我们用几种算法对拣货路径进行优化运算，这里我们比较了动态规划，遗传算法和S-shape启发算法的优化运算结果，这里得到的运算结果如表1所示。

根据表中的运算结果可以看出，相比较传统穿越策略拣货，采用S-shape启发算法优化问题后其拣货距离大多能够减少10%_30%，采用动态规划优化问题后的拣货距离大多能够减少20%-40%，采用遗传算法优化问题后其拣货距离能够减少30%-50%，由此可见采用遗传算法求解最佳的拣货路径更加有效，同时其求解时间也在可以接受的范围内，具有可行性。

我们选取表中的第1个订单，然后分别采用4种求解方法得到线对应的拣货路径，如图3～图6所示。

3.2 一单多车

订单上的需要拣取的货品的储位我们可以随机生成100个，这里需要考虑到仓库推车的载重能力，可以在储位表示的基础上再讲=加上一个数字，其表示为这个储位上所拣取的货品的质量，例如{6 -l - 26 - 2.8}，它表示为这个储位在仓库的6号巷道的左边的第2行，同时这个储位上所需要拣取的货品的质量为2.8kg，这里假设推车的最大载重量为30kg。

因为动态规划方法与S-shape启发式算法不能对不同车次之间的拣货任务进行优化分组运算[5]，也就是无法处理一单多车的问题，所以我们只能采用遗传算法对其进行优化求解，我们这里同样使用C语言程序在Visual C++6.0环境下进行运算求解，得到的结果是总的拣货行走距离为960m，一共需要9车次完成订单的拣取任务。

4 结语

为了降低物流配送中心的拣货成本，提高物流配送效率，减少客户等待时间，提升客户购物体验，就需要合理地安排拣货路径，对应订单的拣取类型，对其建立拣货路径的数学模型，并应用GA算法对其进行优化求解，同时将其优化结果同动态规划方法和S形启发式算法的优化结果进行比较，结果表明优化拣货路径最好的求解方法就是遗传算法，拣货路径的优化能够缩短物流中心的拣货时间，从而提高其工作效率。

参考文献

[1]陈伊菲，刘军，仓库拣货作业路径VRP模型设计与应用[J].计算机工程与应用，2006，42（6）：208-212.

[2]徐天亮.运输与配送[M].北京：中国物资出版社，2002.

[3] Hwang H，Back W，Lee M K.Clustering algorithms fororder packing in an automated storage and retrieval sys-tems[J].lnternational Journal of Production Research.1988.26（2）：189-201.

[4] Goetschalckx M.Ratliff H D.Order picking in an aisle[J].IIE Transactions 1988.20（1）：52-62.

[5]符卓.带装载能力约束的开放式车辆路径问题及其禁忌搜索算法研究[J].系统工程理论与实践，2004（3）：123-126.

[6] Tho L D，Rene M B M.de Koster R.Travel time esti-mation and order batching in a 2-block warehouse[J].Eu-ropean Journal of Operational Research.2007.176 （1）：375-388。

[7]钟石泉，杜刚，贺国光.有时间窗的开放式车辆路径问题及其遗传算法[J].计算机工程与应用，2006，42（34）：200-205.

[8] Roodbergen K J，de Koster R.Routing order pickersin a warehouse with a middle aisle[J].European Joumalof Operation Research，2001.133（1）：31-45.

作者简介：王云波（1978-），男，陕西宝鸡人，硕士研究生，副教授，主要研究方向：企业经济与管理、职业教育等。基金项目：以学生就业能力为核心的职业教育考试制度的探索与研究（SZJG-1612）