3.2 基于偏离度的订单拣选路线规划算法

正如同“2订单分批与拣选路线规划研究理论基础”所讲述的那样，这种多区块仓库下的拣选路线规划问题被定义为Steiner-TSP问题，且对于多区块布局，没有相应的精确最优算法，如同其他的相关研究，本章将也尝试从启发式策略的角度解决该问题。由于本章目的是为单个拣货员求取拣选路线，其目标是获得最短路线，具体的路线评价模型可以参照2.2节的叙述，这里不再复述。

已有的启发式策略正如在“2订单分批与拣选路线规划研究理论基础”所描述的那样，在确定拣货点的拣选顺序即2.2节的0-1规划模型中的决策变量的取值时，只是根据当前待拣选子通道内拣货点的分布情况作出决策，是一种局部的优化，缺乏对全局的考量。此外，常用启发式策略规则相对简单，对所有通道只采用一种或两种访问方式，因此这些策略的表现与具体的拣货点分布情况有密切关系，例如S-Shape在拣货点集中在通道中心时比Largest Gap更优，如果拣货点分布在通道两端时，则是Mid-point和Largest Gap表现更好。所以，在构建路线时，启发式策略最好能够根据拣货点在当前待拣选通道乃至整个仓库中的空间分布作出决策，并能从多种访问方式中选择最适合当前子通道的一种。基于这一需求，本章提出了能够描述拣货点在通道中的空间分布情况的偏离度概念。

为了明确描述拣货员的位置和路线信息，除去“2订单分批与拣选路线规划研究理论基础”提及的符号，本章还使用如下符号：

CAc——拣货员当前所处的横向通道；

PAc——拣货员当前所处的拣货通道。

之后，还有如下假设：

（1）订单中的拣货点相互独立；

（2）拣货员在每个拣货点取货花费的时间是确定的；

（3）拣货员行进速度恒定；

（4）拣货通道和横向通道均无行走方向限制；

（5）拣货员执行的拣选任务在出发前既已确定，且拣选过程中不发生变动。