含多条横向巷道的仓库拣选路径优化研究

       1 引言

       越来越多的企业为了削减成本和提高生产效率，将目光放到仓储设施和配送中心上，订单拣选作业开始受到管理人员和研究学者的重视。研究表明，拣货作业占仓库总作业成本的比例约为60％[1]。

       订单拣选作业是指基于顾客的订单从特定的储存位置获取货物的过程，订单拣选作业的效率取决于储存系统、仓库布局、控制机制等诸多因素，可以通过降低拣选订单所需的时间来减少拣选作业时间，从而提高拣选作业效率。总的拣选时间可粗略地分为订单准备时间、拣货行走时间、搜索货物时间、拣取货物时间等，其中，在人工拣选系统中，行走时间是总拣选时间最大的组成部分，占到50％左右[2]。

       为了减少行走时间，可从以下五个方面着手：(1)通过优化不同待拣选货物的拣选顺序，寻求更好的拣选路径；(2)将拣选区域分成数个工作区即进行作业分区，拣选人员只完成其所委派区域内的待拣选货物；(3)根据特定的分配策略，对货物进行储位分配；(4)对订单进行分批处理，处于同一批次的订单将在一次拣选作业中完成；(5)对仓库的布局进行优化，通过调整和改变仓库设备的尺寸和位置包括存储区的设置，提高仓库的利用率和拣选效率[3]。

       本文将提出一种新的拣选路径优化算法，通过对待拣选点的优化排序，缩短拣选路径的距离，从而减少行走时间，提高拣选作业效率。除此之外，并将其运用到含有多个横向巷道的仓库中，通过实验仿真探索横向巷道的数量对拣选距离的影响，并对仓库布局时横向巷道的数目提出了建议。

       2 问题描述

       本文所考虑的是含多条横向巷道的仓库的拣选路径问题。在仓库中，至少含有两条横向巷道，即位于仓库两端的“前横向巷道”和“后横向巷道”。加入额外的横向巷道，为拣选路径的选择提供更大柔性，从而可能获得更短的行走距离。本文中，将横向巷道编号依照距出入口的远近依次编号，记为“横向巷道1”、“横向巷道2”等。横向巷道将仓库分为多个区，按距出入口的远近，依次被称为“区1”、“区2”等。仓库布局的简图如图1所示。图1中的每个小方格都代表一个储位，黑色填充的方格代表按订单需要拣取的货物所在的储位[4]。

      

       图1 仓库布局简图

       仓库呈矩形，竖直方向上的巷道称为拣选巷道，水平方向上的巷道称作横向巷道，横向巷道中并不包含储位，仅被用来转换巷道，即只有进入到拣选巷道中才能拣选货架上的货物。本文假设货架的列数为偶数，每条拣选巷道左右两侧都含有一列货架。在仓库中，拣选人员能够沿着巷道自由通行，并且拣选巷道足够窄，忽略同一拣货通道中左右两边拣货时拣货人员移动的距离。鉴于仓库的出入口位于第一条横向巷道的边缘和中间，对平均拣选路径的影响不超过1％[5]，本文中假设出入口位于仓库的左下角，第一拣选巷道和第一条横向巷道的交界处，同时是拣选任务起始点和终点。

       通常情况下，这些横向巷道将仓库分为多个区块，形成多区块的仓库，在拣选路径规划时，按照待拣选点所处分区的不同进行分类，逐个分区进行拣选[6]。在本文中，拣选员将逐条巷道依次拣选货物，横向巷道仅作为拣选员在拣选巷道间移动的通道，而根据横向巷道对仓库所进行的分区，仅作为拣选员在拣选巷道间移动时选择经过的横向巷道的参照。

       3 模型介绍及算法求解

       拣选路径问题主要是考虑怎样将一次拣选任务中的货物从储位中依次取出，使得此次拣选任务的行走路径最优。这类问题类似于Steiner TSP问题，与经典的TSP问题不同，其所求得的路线不需要经过所有的节点，而且在必要的情况下可以多次经过同一个节点。

       3.1 模型假设

       (1)各个待拣选点间相互独立；

       (2)拣选员在每个待拣选点取货花费的时间是相同的；

       (3)拣选通道和横向通道均无行走方向限制；

       (4)拣货员执行的拣选任务在出发前既已确定，且拣选过程中不发生变动；

       (5)拣选员沿拣选巷道和横向巷道的中间行走；

       (6)除最后一个分区外，其余所有分区含有相同排数的货架，且最后一个分区所含有的货架排数不少于其他任一分区含有的货架排数。

       3.2 数学模型

       Steiner TSP问题一般可以根据0-1规划模型进行求解：

      

       决策变量=1表示拣选员决定在完成i点的任务后前往j点(i，j∈Ω，i≠j)。目标函数式(1)要求取得完成一个订单的行走路线的最小值；约束(2)和(3)确保每个任务点有且只有一个前项和后项任务；约束(4)确保拣选路线中不出现子回路；约束(5)是定义决策变量的取值域。拣选路线规划问题的研究目的就是确定拣货点间的拣选顺序，即的取值。

       3.3 基于组合算法的路径优化原理

       本文所提出的组合算法是一种新的启发式算法，在解决拣选路径优化问题上，首先假设拣选员是按照待拣选点的分布状况逐条巷道依次完成拣选任务，其次，联系到mid-point算法和Largest Gap算法，将分布较分散的待拣选点放入回程上拣选，然后，根据拣选员所处的位置同待拣选点的相对位置关系决定待拣选点的拣选顺序。新的组合算法利用了回程时的行走路径，同时，拣选员到达下一待拣选点时总是将行走距离最短的路径作为拣选路径，因而，其在路径优化中体现出更加有效的优化效果。