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

在平行通道式仓库中，拣货员从出发点（Depot）开始，在通道中行走，并从位于通道两边的货位上拣选订单任务指定的拣货点（Pick），在完成拣选后返回Depot。此外，本书的通道采用的是窄通道设计，即通道宽度仅供一个拣货员作业，该设计一方面能够节省成本并提高空间利用率，另一方面，拣货员在遇到通道两边相对货位上都有拣货任务时只需要转身而不是移动，就可以完成两边的拣货点，减少了移动距离[11][13][141]。

在平行通道式仓库下的拣选作业过程中，拣货员推着拣选容器或者驾驶拣选器械在通道中行走，并可以位于仓库前后两端的横向通道改变当前作业通道。如果仓库中只有两条横向通道分布于仓库的前后两端，则整个仓库存储区域可以看作一个整体的区块，这就是平行通道式的单区块仓库布局，如图2-1所示，很多相关研究就是在这类布局下展开[9][21][115][127][158][159]。

在这类布局下，订单拣选路线规划就是要求选择一条最优的拣选路线，这与旅行商问题（travelling salesman problem, TSP）很类似，但又与经典的TSP有一些不同[2]。文献[2]将订单拣选路线规划问题具体定义成Steiner-TSP。Steiner-TSP的目的是找到一条最短的Steiner（斯坦纳，外国人名）路线，其中非Steiner点要至少访问一次。这个问题可以用图论的方式描述，即图G=（V, E）由点集与边集E组成。点集V=RUN包含了仓库中所有要拣选的p个拣货点及Depot点的集合，其中Depot是节点0，这些节点是非Steiner节点。点集R={1, …, p}+{0}代表的是n个Steiner节点，是由通道和横向通道的交汇点构成的集合。边集R×R代表的是在两两拣货点及拣货点与Depot间的所有可行路线。图2-2所示为一个有4个通道和2个横向通道（n=7）的仓库下有4个拣货点与Depot需要访问（p=5），可以抽象为示意图2-2（b）。这时，点集R={0,1, …,4}包含了所有必须访问一次的点，因为这些黑色点表示的点都是拣货点和Depot。点集N={5, …, 11}中的用白色点表示的Steiner节点则不是必须成为拣选路线的一部分，虽然从仓库的布局特点上来看，只有经过这些Steiner节点才能在拣货点间移动。

针对每个拣货员的拣选路线规划，通常的目标是最小化拣货员的行走路线长度。一般可以通过0-1规划模型进行求解：

式中

i, j∈Ω——拣货员要经过的拣货点以及Depot，其中i=0表示Depot；

dij——拣货点i和j之间的距离；

ui——拣货点i的拣选顺序，其中u0=1；

w——拣货点和Depot数量总和。

最后，模型的决策变量是xij，当xij=1时，表示提货员决定完成i点的任务后前往j点(i, j∈Ω, i≠j)。

目标函数式（2.1）是要求取得完成一个订单的行走路线的最小值；约束式（2.2）和式（2.3）是确保每个任务点有且只有一个前项和后项任务；约束式（2.4）确保拣选路线中不出现子回路；约束式（2.5）是定义决策变量的取值域。拣选路线规划问题的研究目的就是确定拣货点间的拣选顺序，即xij的取值。

针对如图2-2（a）所示布局的单区块仓库，最早由Ratliff和Rosenthal于文献[115]中给出了一个与通道数量和拣货点数量呈线性关系的最优算法。之后，文献[158]将该最优算法的适用范围扩展到分散放置（decen-tralised depositing）情况，即拣选完的货物放在通道入口处，而不是在Depot集中。在实际操作中，不同于自动化仓库中常使用智能优化算法，如蚁群算法[160]、遗传算法[163]，在这类布局下的人工作业仓库中，拣选路线的获取更多的是采用专用启发式策略。主要是因为，拣选路线规划是Steiner-TSP问题，本质上是一类NP-Hard的组合优化问题，只在单区块和双区块仓库下存在精确的最优算法[124]；更重要的是，最优算法得出的路线看起来没有逻辑性，拣选人员在执行过程中很容易偏离该路线指示[78]。相对的，专用启发式策略则由于规则简单，路线有明显的逻辑走向，更受欢迎，最常用的启发式策略有：S-Shape（Traversal）、Mid-point、Return、Largest Gap、Combine。

S型策略：S-Shape（Traversal）也称为穿越策略，使用该策略的拣货员在通道中有拣货点时，就穿过整个通道，没有拣货点的通道则忽略，在完成最后一个通道中的拣选后，就返回Depot[2][159]。由于得出的路线呈S形，故得其名，如图2-3所示。该策略由于规则简单，在很多文献中都用来作为基本假设，或者与其他订单拣选路线规划算法或策略作对比。

中点策略：Mid-point，除了第一个和最后一个有拣货点的通道要完整穿过，其他通道根据中点分成前后两部分[2]。位于通道前半段的拣货点通过前端的入口进入拣选并返回，位于后半段的拣货点通过后端入口拣选并返回[2][120]，如图2-4所示。文献[120]验证该方法在每个通道中拣货点较少时比S-Shape的表现好。

返回策略：Return，拣货员从同一个通道入口进入拣选并从这个入口离开，没有拣货点的通道不进入[2]，如图2-5所示。

最大间隔策略：Largest Gap，该策略是Mid-point和Return的综合改进。通道被最大间隔而不是中点划分成两段，所谓的间隔是指相邻的两个拣货点、前端入口和最靠近该入口的拣货点、后端入口和最靠近后端入口拣货点间的间隔。如果最大间隔是在两个拣货点之间，则该通道的实际拣选效果类似于Mid-point，拣货员从两端入口分别进入拣选并返回[2][120]。如果最大间隔位于通道口，则该通道实际就是Return策略，拣货员从最大间隔对面的通道进入拣选并返回。同样，除了第一个和最后一个有货通道要完整穿过，其他通道中的最大间隔是不能穿过的，如图2-6所示。由于是Mid-point的改进，所以，该策略也就自然比Mid-point更优化[120]，当然Mid-point由于规则简单，更容易实行。

图2-6 Largest Gap

混合策略：Combine，该策略采用动态规划的方法[2][116]，其具体流程可以表示如下。

Step 1：从最左边的通道开始。

Step 2：如果当前通道是最后一条有拣货点的通道，拣货员在进入通道拣选完通道中最后一个拣货点后，必须从前端横向通道离开通道，前往Step 4；如果当前通道不是最后一条有拣货点的通道，设Ltraverse和Lreturn分别代表穿过通道和进入通道拣选完最后一个拣货点后从原入口返回，这两种拣选方式对应的在该通道中的行走长度。如果Ltraverse<Lreturn，则拣货员穿过该通道；如果Ltraverse>Lreturn，拣货员在完成拣选后原路返回，前往Step 3。

Step 3：向右移动至下一条有拣货点的通道。

Step 4：拣货员返回Depot，如图2-7所示。

以上这些常用启发式策略在很多相关文献中都有涉及，见表2-1。