拣货作业是根据客户订单需求，从仓库的存储区或缓冲区收集货物的作业过程。在拣货作业的各个步骤中，在不同拣货点间行走的所耗费的时间占拣货时间的一半。由此可见，通过优化拣货路径降低行走距离，可以有效提高仓库的作业效率。

仓库拣货区的通道布局通常包括若干平行的拣货巷道与数条与之垂直的主通道。拣货巷道与货架平行，拣货员经由主通道在不同的拣货巷道间穿行。孙军艳等[1]设计一种动态算法解决单车次的双区型仓库拣货路径优化。王宏等[2]采用改进的遗传算法，对有装载能力限制的双区型仓库的拣货路径进行优化。不过在实际运营中，拣货区的布局和相应的拣货路径会受到许多条件的限制，Chen等[3]提出了六种启发式方法来解决具有出入限制的仓库拣货问题，但是只考虑了没有车辆载重限制的情况。

在前人研究的基础上，本文将根据某企业仓库的实际运作情况，建立相应的装载能力有限的非标准双区型仓库拣货路径优化模型，并使用Gurobi线性规划求解器进行实验求解。

A公司为一家服装连锁零售企业，其仓库服务所在区域的诸多门店。各门店每日向仓库发送订单，仓库将所有订单汇总整理后生成拣货计划。仓库采用订单别的拣选方式，即拣货员每人每次只处理一份订单中的商品。由于门店订货需求种类较多，通常一张订单需要在仓库内进行多个巡回来完成拣货。

A公司仓库的拣货区示意图见图1。仓库共有6条平行的拣货巷道，每条巷道两侧摆放有相同数量的货架。拣货区被通道A分成货架数量相同的上、下两个半区，其中上半区货架的上边缘贴近仓库墙壁，拣货员只能经由货架中间的通道A在上半区的不同巷道穿行，而下半区的货架两侧均有通道，拣货员可选择A、B任意一条通道穿行。拣货员从I/O(In/Out）点进入拣货区，按照安排完成拣货后再由该点离开。

仓库的巷道序号从左至右从1递增，通道内的货位序号从上至下从1递增。任意货位点的位置可用坐标表示，其中：为所在巷道序号；为在巷道的侧向，左侧为0，右侧为1；为通道内的货位序号。例如，表示第4条巷道右侧第5个货位。

本文所研究的问题可以描述为：给定一个包含n种商品的订单，由若干辆拣货车完成作业。要求确定每辆拣货车的路径安排和调度，使得所有车辆的拣货行走总距离最短。

图1 A公司仓库布局示意图   

1. 每个储位i上只存储一种商品，同一种商品只在一个储位存储。

2. 每个储位保管的商品数量不少于订单中该商品的数量，即库存可以完全满足订单需求。

3. 每辆拣货车的实际载重不得超过其最大载重Q的限制，且所有拣货车的Q均相同。

4. 同一种商品的需求不可拆分，且最大不超过拣货车载重。

5. 巷道宽度较窄，拣货员在巷道中可以进行双侧取货，即在同一巷道左右两边取货时拣货员的移动距离可以忽略不计，可以将同一巷道左右两侧的两个储位视为同一个拣货点。

6. 拣货员在过道和巷道均沿中线行走，忽略转弯产生的距离误差。

已知拣货点编号的集合X={1,2,…,n}，则可将仓库的任意点（拣货点或I/O点）组成的序列P(X)={V1V2,…,Vn}视为一条拣货路径。假设拣货车从V1出发开始拣货，当到达Vn时小车载重超过Q，则在序列的第N个元素之前插入一个I/O点，并从第N个元素开始重新计算载重，最终形成一个满足小车载重约束的序列，并且该序列由m条路径组成。令模型相关变量参数表示如下：n为订单中包含点的数量（含拣货点和I/O点）；m为子路径总数（即拣货车辆数）；k为子路径编号；Nk子路径k上的点的数量；Qki为子路径k上第i点上拣货商品的重量；Q为拣货车的最大载重；dk(V1,Vj)为子路径k上V1点到Vj点的最短距离；Pk(V1,Vj)为决策变量，表示子路径k上是否由V1点前往Vj点。

仓库拣货路径优化的问题模型可表示为：

其中，式为目标函数，表示所有车辆总的拣货距离最短；式表示每辆拣货车的载重不得超过自身最大载重；式和表示子路径k上的每个拣货点只能被经过一次；式为决策变量取值，若路径k上拣货车从V1点前往Vj点则取值为1，否则为0。

在仓库环境下，拣货车辆只能沿通道横向、纵向行走，因此需要对仓库内任意点的距离进行计算。

设ai,bi,ci为拣货点i的坐标，di A、di B分别为点i到通道A和通道B的垂直距离，L为通道每排货架数，D1为通道宽度，D2为巷道宽度，D3为货架宽度，D4为货架深度。其中，di A、di B可进一步表示为：

根据点的距离不同，可将两点间距离分为I/O点到任意拣货点距离和两拣货点间距离进行计算。

表1 拣货点信息  

表2 仓库和拣货车辆信息     

a.I/O点到任意拣货点距离

由I/O点到拣货点的最短距离

b.两拣货点间距离

设两拣货点i和j的坐标分别为(ai,bi,ci)和(aj,bj,cj)，且ci≤cj，则点i和点j间的距离可表示为：

随机取一个包含20种拣货商品的订单，商品的拣货点和需求量见表1。仓库规模和拣货车辆信息见表2。

本文在内存为4 G B的计算机上，使用Python编程调用Gurobi求解器进行规划求解。当求解过程的对偶间隙gap=0时，得到的结果为全局最优解。使用上述数据调用求解器求得的最短拣货距离为226.5m，具体路径和示意图见表3及图2。

从结果可以看出，优化后的路径安排可以满足仓库布局和拣货车辆载重的约束，证明了模型的有效性。拣货路径大体按照区域和巷道安排，比较便于记忆。同时，求解器的使用可以确保得到的解为全局最优解，从而能够有效提高仓库的拣货效率，降低运营成本。

表3 最优解路径    

本文根据某A公司仓库的实际情况，建立了相应的距离矩阵计算模型和仓库拣货路径优化模型，并对拣货路径进行优化。结果显示，拣货路径优化效果明显，可以为之后仓库运作优化提供有效参考。

图2 最优解路径示意图