2.3 多区块仓库布局及其常用订单拣选路线规划方法

为了使拣货员更灵活地改变作业通道，除了位于仓库前端和后端有横向通道外，仓库的中部也可以有数条横向通道，这些横向通道将仓库分成了数个区块（block），形成了多区块（multiple blocks）仓库[166]。同时，通道也被分成数段子通道（subaisle）。本书中涉及的仓库布局主要是多区块的情形，其典型布局如图2-8所示，该类布局可以在很多拣选策略相关文献中见到[2][116][117][128]。

这些区块从仓库前端向后端依次命名为B1, B2, …，横向通道也从前端向后命名CA1, CA2, …。通道和子通道则是从左至右依次命名为PA1, PA2, …和S1, S2, …。此外，对于每个区块，位于其前端的横向通道即成为前端横向通道（front cross aisle, CAf），同样的有后端横向通道（back cross aisle, CAb）。可以看出，除了B1，每个区块的CAf都是前一个区块的CAb。

从问题结构上来看，多区块仓库下的拣选路线仍然可以用2.2节的模型进行评价，所以这里不再复述。文献[117]将之前由Ratliff和Rosenthal提出的最优算法扩展到双区块仓库。然而，对于存在更多横向通道的多区块仓库，到目前为止，还没有相应的精确最优算法[124]，所以针对多区块仓库下的订单拣选路线规划，相关研究集中在寻找能够为拣货员提供最合适拣选路线的启发式策略上。前面提到的常用启发式策略都是在单区块仓库基础上给出的，针对实际中仓库存在多区块的情况，文献[117]提出，这些现有启发式策略经过一些改动是可以应用在多区块仓库中的。之后，一些研究给出了这些经过改进后的策略[116]。

其中，文献[116]给出了关于S-Shape、Largest Gap和Combine在多区块仓库下的详细流程：

（1）针对多区块仓库布局的S-Shape改进[116]，如图2-9所示。

Step 1：从所有区块中找出包含了至少一个拣货点的通道中最靠左的一条并定义为最左通道，以及包含了至少一个拣货点的最远离Depot的区块，定义为最远区块。

Step 2：拣货员从Depot出发，到达最左通道入口。

Step 3：沿着最左通道行走，直到最远区块的CAf。

Step 4：沿着最远区块向右行走，直到最远区块中最靠左的一条有拣货点的子通道入口。如果这条子通道是该区块中唯一一个有拣货点的通道，则进入拣选并返回到最远区块的CAf；如果有多条有拣货点的子通道，则穿过整个通道到达最远区块的CAb。

Step 5：这时，拣货员是在一个区块的CAb，将这个区块设为当前工作区块，接下来有以下两种可能性。

Step 5.1：当前工作区块中还有拣货点尚未拣选。寻找当前工作区块中距离拣货员当前位置最远的有拣货点的子通道，定义为最远子通道，相反的一条定义为最近子通道，行至最近子通道，前往Step 6。

Step 5.2：当前工作区块中没有拣货点需要拣选。沿着CAc向前走，到达当前工作区块的CAf，前往Step 8。

Step 6：如果当前工作区块中还有拣货点，沿着CAc到达下一个有拣货点的子通道并完全穿过。重复这个步骤，直到当前工作区块只剩一个有拣货点的子通道。

Step 7：前往当前工作区块的最后一个有拣货点的子通道，拣选完这个子通道的拣货点后到达当前工作区块的CAf。当然，最后一个通道的拣选方式可能是完整穿过，也可能是从前端进入又从前端返回。

Step 8：如果CAc不是CA1，返回Step 5。

Step 9：最终，返回Depot。

（2）针对多区块仓库布局的多区块Largest Gap改进[116]，如图2-10所示。

Step 1：从所有区块中找出包含了至少一个拣货点的通道中最靠左的一条并定义为最左通道，以及包含了至少一个拣货点的最远离Depot的区块，定义为最远区块。

Step 2：拣货员从Depot出发，到达最左通道入口。

Step 3：沿着最左通道行走，直到最远区块的CAc。

Step 4：沿着最远区块的CAf向右行走，直到最远区块中最靠左的一条有拣货点的子通道入口。如果这条子通道是该区块中唯一一个有拣货点的通道，则进入拣选并返回到最远区块的CAf；如果有多条有拣货点的子通道，则穿过整个通道到达最远区块的CAf。

Step 5：这时，拣货员是在一个区块的CAb，将这个区块设为当前工作区块，接下来有以下两种可能性。

Step 5.1：当前工作区块中还有拣货点尚未拣选。寻找当前工作区块中距离拣货员当前位置最远的有拣货点的子通道，定义为最远子通道，相反的一条定义为最近子通道，行至最近子通道，前往Step 6。

Step 5.2：当前工作区块中没有拣货点需要拣选。沿着PAc向前走，到达当前工作区块的CAf，前往Step 9。

Step 6：沿着当前工作区块的CAb到达最近子通道，按照从最近子通道向最远子通道的次序，依次进入所有需要从后端进入拣选的子通道，并在到达最大间隔前返回当前工作区块的CAb。当然这一过程可能是从左向右，也可能反之。

Step 7：穿过最远子通道，到达当前工作区块的CAf。

Step 8：从最远子通道开始，向最近子通道反向移动，将所有剩下的位于最大间隔前端的拣货点全部拣选完。

Step 9：如果CAc不是CA1，返回Step 5。

Step 10：最终，返回Depot。

（3）针对多区块仓库布局的Combine改进[116]，如图2-11所示。

Step 1：从所有区块中找出包含了至少一个拣货点的通道中最靠左的一条并定义为最左通道，以及包含了至少一个拣货点的最远离Depot的区块，定义为最远区块。

Step 2：拣货员从Depot出发，到达最左通道入口。

Step 3：沿着最左通道行走，直到最远区块的CAf。

Step 4：沿着最远区块的CAf向右行走，直到最远区块中最靠左的一条有拣货点的子通道入口。

Step 5：这时，拣货员是在一个区块的CAf，将这个区块设为当前工作区块，接下来有以下两种可能性。

Step 5.1：当前工作区块中还有拣货点尚未拣选。寻找当前工作区块中距离拣货员当前位置最远的有拣货点的子通道，定义为最远子通道，相反的一条定义为最近子通道，行至最近子通道，前往Step 6。

Step 5.2：当前工作区块中没有拣货点需要拣选，前往Step 9。

Step 6：根据单区块下Combine的动态规划原则，即在完全穿过该子通道还是拣选完该子通道后原路返回两种策略中，选择行走距离短的执行，在拣选完后，沿着当前工作区块的CAb或CAf，向最远子通道所在的方向移动，到达下一个有拣货点的子通道，重复这一过程，直到最远子通道。

Step 7：完成最远子通道拣选，但必须到达当前工作区块的CAf。

Step 8：如果CAc不是CA1，返回Step 5。

Step 9：最终，返回Depot。

值得注意的是，这些启发式策略无论是针对单区块还是多区块，拣选路线的生成都是针对当前通道中拣货点分布情况给出的决策，缺乏对所有拣货点总体上的分析。同时，这些已有订单拣选路线规划算法与策略都没有在构建路线时包含处理拣货员堵塞的机制，当然也没有专门针对不确定性、动态性订单的处理能力。