考虑拆分策略的智能仓库订单拣选优化问题

万明重，蒋忠中+，秦绪伟，乔 双,李铭阳

(1.东北大学 工商管理学院，辽宁 沈阳 110167；2.东北大学 行为与服务运作管理研究所，辽宁 沈阳 110167；3.天津大学 管理与经济学部，天津 300072)

0 引言

伴随着电子商务的高速发展，其对客户订单的配送服务也提出了更高的要求。天猫超市、京东商城等购物平台纷纷推出次日达、今日达等限时配送服务。通常地，配送服务包括客户从下达订单到送货上门等流程，其中，仓库中的订单拣选是配送服务的重要环节，属于仓库作业中劳动密集度和成本最高的活动，其成本约占仓库总运营成本的55%以上[1]。传统仓库中，为降低人工操作的失误，订单拣选通常要求订单不被拆分，即每个订单只能分配给一名拣选员[1]，但也限制了订单拣选作业的效率。借助新兴的信息技术，智能仓库可轻松地实现订单任务拆分和重组，为订单拣选作业效率的提高创造了有利条件。以京东智能仓库——无人仓为例，基于3D视觉识别等技术，运用智能小车、拣货机器人、机械手等设备代替传统的拣货员和拣货车，一方面避免了人工操作可能带来的失误，另一方面实现了仓库的自动拣选、智能打包等功能。可见，相对于传统仓库，订单可拆分是智能仓库拣选作业的新特征，因此如何实现订单可拆分情形下的拣选作业优化是企业实现智能仓库高效运作的重要决策问题。

近年来，订单拣选优化问题备受学者关注，国内外文献从订单分批、批次分配和拣货车路径优化等角度对订单拣选问题进行了研究。订单分批是将不同订单组成批次，交由拣货车同时拣取；批次分配是将这些批次分配给不同拣货车，并确定其拣货顺序。国外方面，SCHOLZ等[2]研究了订单分批、批次分配问题，其目标是使订单总延误时间最小；ARDJMAND等[3]研究了按波次拣选仓库中订单分批和批次分配问题，其目标是最小化订单总完工时间；THEYS等[4]和GLOCK等[5]研究了仓库拣选的路径优化问题，并分别将其转化有旅行商问题(Traveling Salesman Problem, TSP)和有容量限制的车辆路径优化问题(Capacitated Vehicle Routing Problem, CVRP)。国内方面，梁旭[6]和邹霞等[7]对传统仓库中订单的调度问题进行了研究。上述针对传统仓库订单拣选问题的研究中，为降低拣货员在作业中的失误率，通常较少考虑订单可拆分的情况。

随着智能化技术的发展，仓库逐渐开始使用自动导引车(Automated Guided Vehicle, AGV)、拣货机器人、智能拣货车等代替传统的人工拣选，部分学者也开始研究订单拆分策略下的仓库拣选问题。订单拆分策略下，一个订单可被拆分成多个部分并分配给不同批次或拣货车。ARCHETRI等[8]研究表明，订单拆分策略有助于提高拣货车容量的利用率，进而提高订单拣选的效率。CERGIBOZAN等[9]研究指出，若单个订单较大无法由一辆拣货车完成拣选任务时，可对订单进行拆分，并交由多辆拣货车进行拣选。PARIKH等[10]研究了仓库分区条件下的订单分批、拣选问题，研究将单个订单依货品的存储区域拆分给多个部分，并交由每个区域的拣货车同时进行拣选，其目标是最小化拣货车的空闲时间。BRIANT等[11]基于HappyChic公司的案例研究了考虑订单拆分策略的订单分配、拣货车路由问题，其目标是最小化拣货车的总行走距离。

在处理限时订单的拣选、配送问题中，确保订单按时完成配送是最重要的目标。但考虑订单拆分策略的现有研究中，尚未对最小化订单总延误时间的问题进行探讨。基于此，本文首次在以最小化订单总延误时间为目标的订单拣选问题中考虑了订单拆分策略。当订单允许被拆分时，某个订单可被拆分成多个部分并分配给不同批次；而只有当该订单需要的所有货品都被拣选后，才能对该订单进行配送。此时，订单的完成时间由包含该订单的所有批次共同决定。因此，订单拆分策略使得以目标为最小化订单总延误时间的订单拣选问题相对传统仓库的订单拣选问题更为复杂。

为此，本文针对智能仓库的订单拣选优化问题的新特征，研究考虑拆分策略的订单拣选优化模型与算法，并探讨拆分策略和算法设计对于订单拣选作业效率的影响规律。首先，以订单总延误时间最小化为目标，构建考虑拆分策略的订单拣选优化模型；其次，依据模型特点将该问题分解为订单分批和批次分配两阶段，并分别提出了订单分批算法和智能果蝇优化算法对模型进行求解；最后，通过数值算例计算和对比分析，验证了所提算法的高效性。研究结果表明，在拆分策略情形下订单总延误时间显著减小，进而大幅度提升了订单拣选作业的效率。

1 问题描述与模型建立

1.1 问题描述和符号定义

订单拣选作业流程一般包括订单分批、批次分配和拣选路由3部分。订单分批是将多张订单组成不同批次；批次分配是将组成的不同批次分配给拣选员(智能小车或智能拣货车)，并确定批次的拣选顺序；拣货路由则是拣选员依据分配订单确定拣货路径。在电子商务环境下，考虑智能仓库可实现订单拆分的新特征，其订单拣选问题描述如下：仓库将某时段接收到的多张客户订单，通过订单拆分并依据其截止时间组成不同批次，再由智能拣货车根据批次进行拣选路由，最后将属于同一客户订单的货品整合在一起，并进行复核和打包。如图1所示为订单拣选的具体流程，由于智能仓库的自动化水平较高，订单拆分和分批可快速地自动完成(花费时间可忽略)，订单拣选花费时间主要体现在智能拣货车行走时间和取货时间方面。行走时间是指智能拣货车完成从仓库起点开始逐个访问订单货品所需拣选位置并返回仓库起点的路径所花费的时间(假设行走速度恒定，则行走时间取决于智能拣货车的行驶距离)；取货时间是指智能拣货车到达指定拣选位置后取出货品所需的时间。

研究以单区型智能仓库为例，智能拣货车按照包含U-turn的S型路径拣选货品[12]，即拣货车在完成最后一通道的货品拣选后立即返回，而不是继续按照S路径走完通道。为方便机械手存取货品，智能仓库中拣货车的货框往往使用托盘或隔板划分出若干个区域，每个区域存放至多一件货品。因此，本文中拣货车容量C亦指拣货车货框中托盘的个数(或隔板划分的区域个数)。智能拣货车接收批次任务的时刻记为批次的开始时间，智能拣货车完成拣选任务回到起始点的时刻记为批次的完成时间。当被拆分的订单中所需的全部货品拣选完成时，该订单被完成；订单的延误时间为该订单的完成时间减去该订单的截止时间。基于此，问题的基本假设如下：①仓库中存储货品的位置是固定的，且每个位置只存放一种货品，智能拣货车行走在巷道的中间可同时从左右两边拣选货品;②智能拣货车直至当前任务完成后才能开始下一个任务，中间不可被打断;③每个批次中货品的体积不得超过智能拣货车的容量;④每个订单至少包含一件货品。问题的模型参数和变量包括：

(1)模型参数

I为客户订单集合，i∈I={1,2,…,m}；

P为智能拣货车集合，p∈P={1,2,…,n}；

Q为订单批次集合，q∈Q={1,2,…,|Q|}；

K为货品集合，k∈K={1,2,…,|K|}；

C为智能拣货车容量；

B为智能仓库中两相邻通道间的距离；

L为智能仓库中通道的长度；

(2)决策变量

xiqk为0-1变量，若批次q包含订单i中的货品k，则xiqk=1，否则xiqk=0；

ypqq′为0-1变量，若批次q′紧接着批次q由智能拣货车p拣取，则ypqq′=1，否则ypqq′=0。

(3)辅助变量

τi为订单i延误时间；

vtravel为智能拣货车行驶速度；

disq为完成批次q所需行走距离；

tsetup为批次的准备、取货时间；

Aq为拣选批次q中的货品需要访问的通道数量；

1.2 拆分策略和优化模型

传统的订单拣选问题中，一般遵循订单不可被拆分的原则。但由于每个订单包含的货品种类和数量不同，拣选每个订单所需的拣货车容量也不同，需要将不同订单进行组合来提高拣货车容量的利用率。理想的情况是组成同一批次的订单恰好占满整个拣货车且具有相同的截止时间。但在实际问题中，不同订单的组合很难恰好占满拣货车，订单的截止时间不尽相同，因此以上两方面目标很难同时达到最优。

针对智能仓库的新特征，即当机械手和智能拣货车代替了传统的人工拣货后，可以准确执行复杂的拣货方案，不必再遵守订单不可被拆分的原则；同时为进一步提升拣货车容量的利用率，本文在订单分配问题中引入订单拆分策略[8]。订单拆分策略允许将单个订单拆分为多个部分，并分配给不同批次进行拣选。因此，每个批次可包含多个订单，每个订单也可由多个批次共同完成。由于单个订单需要在其包含的所有货品都完成拣选后才能配送，订单的完成时间取决于包含该订单批次完成时间的最大值。基于上述特性，构建基于拆分策略的订单拣选问题数学模型如下：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

xiqk∈{0,1},∀i∈I,∀q∈Q,∀k∈K。

(10)

ypqq′∈{0,1},∀q∈Q∪{0},

∀q′∈Q,∀p∈P。

(11)

disq=

(12)

2 模型的求解算法

以最小化总延误时间为目标的订单拣选问题属于NP-hard问题，当问题规模较大时很难高效求解[13]。由于在电子商务环境下，商家需要处理大量紧急的订单(今日达、次日达等)，因而期望算法能在较短的时间内得到高质量的解。为实现这一目标，本文针对考虑拆分策略的订单拣选问题的特点进行深入分析，结果发现，若同时处理订单分批与批次分配问题，则每次对批次进行分配时都需要计算完成该批次拣选任务所需时间，从而导致计算十分耗时。鉴于此，本文提出将问题拆分成订单分批和批次分配两阶段的求解思路。在订单分批阶段，将订单按需求进行拆分，并根据订单的截止时间重新组成批次。完成订单分批后，每个批次的拣选时间可以直接计算得到。在批次分配阶段，算法基于订单分批的结果进行批次分配，因此不用重复计算批次的拣选时间，只需要将以上批次分配给不同拣货车，并确定这些批次的拣选顺序。上述两阶段拆分求解思路可使得模型的计算时间显著降低。此外，两阶段拆分求解思路实质上只是改变了订单拣选问题决策的顺序，并不会影响模型的正确性。

2.1 订单分批算法

订单分批问题是将不同的订单组成批次，其目标是最大化智能拣货车容量的利用率，且最小化同一批次中订单截止时间的差值。在不考虑拆分策略的订单分批问题中，为了提高拣货车容量的利用率，需要将不同大小(货品数量不同)的订单进行组合。由于不同订单的截止时间不一致，无法保证组成同一批次的订单恰好占满拣货车的容量，且订单的截止时间相近。

订单拆分策略可以较好地处理上述问题。在进行订单分批时，按照订单截止时间的升序逐个选取订单并组成批次。若新加入批次的订单大小超过智能拣货车的剩余容量，则对该订单进行拆分，并将多出的部分订单放入新的批次。该算法的详细步骤如下：

步骤1获取全部的订单集合Ω，生成一个空的初始批次Bq。

步骤2选择订单集合Ω中截止时间最小的订单Oi，该订单包含货品所需的智能拣货车容量为Ci。令Cq表示当前批次Bq剩余的容量，

(1)若Ci+Cq≤C，将订单Oi放入批次Bq，并将Oi从订单集合Ω中移除。

(2)若Ci+Cq>C，对订单Oi进行拆分：将订单Oi中容量C-Cq的部分放入批次Bq，并将订单Oi中容量Ci-(C-Cq)的部分放入新批次Bq+1；将Oi从订单集合Ω中移除。

步骤3重复步骤2，直至订单集合Ω为空。

通过订单分批算法，可保证每个批次货品恰好占满智能拣货车的容量。此外，只有当新加入批次中的订单大小超过智能拣货车剩余容量时，才对订单进行拆分。因此，该算法可以保证每个订单不被过度拆分。

推论1订单分批算法中，任意一个订单至多被拆分成两部分，且一个批次中至多包含两个被拆分的订单。

在订单分批阶段，若干个订单组成一个批次。当考虑订单分配策略时，部分订单被拆分成若干部分并在不同批次进行拣选。此时，被拆分订单的完成时间取决于它所属批次的最大批次完成时间。为提高订单拣选效率，在订单的批次分配时，应考虑被拆分订单的齐套性[14](使得同一订单被拆分的部分尽可能同时完成)。若订单被过度拆分，会使得批次分配阶段的计算过于复杂。

2.2 智能果蝇优化算法

FOA是模仿果蝇通过嗅觉和视觉寻找食物的算法。果蝇可以通过敏感的嗅觉发现远处的食物，并在接近后通过视觉找到食物的位置。通过嗅觉和视觉的指引，可以帮助果蝇快速接近食物，并准确找到食物的位置。FOA通过模仿这一行为，很好地协调了算法的全局搜索能力和局部搜索能力：先通过嗅觉搜索找到较优解，再通过视觉搜索在较优解附近进一步寻找更优的解；如此循环，直到收敛。ZHENG等[17]近一步改进了FOA，并提出知识引导的果蝇优化算法(Knowledge Guided FOA, KGFOA)。KGFOA通过根据果蝇的历史经验，对果蝇的搜索方向进行引导，进而加快算法的收敛速度。该算法主要包括以下步骤：

(1)种群编码。将问题的可行解通过实数编码的形式表示出来。

(2)初始化种群。随机生成一系类初始可行解(初始果蝇)。

(3)嗅觉搜索。在每个果蝇的嗅觉范围内随机生成若干个果蝇，形成子种群。

(4)视觉搜索。评价每个子种群的果蝇，并用该种群中最好的果蝇代替掉原果蝇。

(5)知识引导。每个果蝇根据历史经验进行知识引导搜索。

FOA与KGFOA的嗅觉搜索未限制新果蝇产生的方式，使得该算法能结合确定性方法或启发式规则加快FOA的收敛速度。鉴于此，本文选用KGFOA算法，并在算法的嗅觉搜索阶段结合网络效益重组(Net Benefit of Relocation, NBR)[18]规则对算法进行改进，以提高算法的收敛速度。NBR规则是一类基于贪婪法近似求解单服务台调度问题的规则。本文将NBR规则融入嗅觉搜索过程，减少了不必要的搜索空间，提高了嗅觉搜索的效率。随后，本文基于批次分配问题的特性构建了批次分配经验概率和批次排序的经验概率两个知识库，从而提高了知识引导的性能。基于此，本文通过改进KGFOA的嗅觉搜索和知识引导过程，提出智能果蝇优化算法(Smart FOA, SFOA)。相比已有的果蝇优化算法，SFOA中果蝇不仅依靠随机搜索的方法寻找最优解(近优解)，还能应用NBR规则和知识库更智能地搜索最优解(近优解)。SFOA的算法流程如图2所示。

2.2.1 种群编码

批次分配问题的决策包括不同批次与智能拣货车的匹配，以及智能拣货车进行批次拣选的顺序。因此，果蝇的编码由批次与智能拣货车的匹配、批次的拣选顺序两方面信息组成。鉴于此，本文通过实数向量A来表示果蝇的编码，每个果蝇的编码可表示为：

A=[A1,A2,…,An],

2.2.2 嗅觉搜索

嗅觉搜索时给定果蝇的嗅觉范围为(z,s)，即果蝇只能在距离(z,s)内进行嗅觉搜索。其中距离z表示随机生成的新果蝇A′与原果蝇A相比，至多有z个批次被指派的智能拣货车不同；距离s表示随机生成的新果蝇A′与原果蝇A相比，每辆智能拣货车的拣选顺序中至多有s个批次的位置发生变化。

2.2.3 视觉搜索

在视觉搜索时，通过计算每个果蝇对应拣选方案的订单延误时间，对果蝇进行评价。若新生的子种群中存在果蝇对应拣选方案的订单延误时间更短，则由该果蝇代替原果蝇。因而，只有当果蝇产生的子种群中具有较小的订单总延误时间时，当前果蝇才会被其相应的子种群中最佳的新果蝇取代。

2.2.4 知识引导

为加快算法的收敛速度，本文在每次迭代后对精英果蝇进行知识引导。基于批次分配问题的特性，知识库被分为精英果蝇提供的批次分配经验概率和批次排序的经验概率两部分。知识引导搜索包含智能拣货车分配搜索和批次排序搜索两个过程，每个果蝇都在知识库的引导下通过知识引导搜索实现订单总延误时间最小化的目标。

(1)智能拣货车分配

使用轮盘赌策略对知识库中批次分配的经验概率进行抽样，通过为每个批次重新分配智能拣货车来实现批次分配搜索。经验概率初始化如下：

其中：P是智能拣货车的数量，Pqp(g)表示第g次迭代时将批次q分配给智能拣货车p的概率。每一次迭代后，精英果蝇的知识库更新公式如下：

(2)批次排序

使用轮盘赌策略对知识库中批次排序的经验概率进行抽样，通过为每个智能拣货车需要拣选的批次进行排序来实现批次排序搜索。经验概率初始化如下：

其中：K是批次可被分配给智能拣货车拣选位置的最大数，Pqk(g)表示第g次迭代时将拣选批次q排在智能拣货车的第k拣选位置的概率。每一次迭代后，精英果蝇的批次排序经验更新概率如下：

3 数值算例与结果分析

本章将通过比较订单可拆分与不可拆分情形下数值算例SFOA的计算结果，研究订单拆分策略对智能仓库的订单拣选效率的影响规律。为进一步验证订单可拆分时SFOA算法的性能，将SFOA与最早开始时间算法(Earliest Start Date, ESD)[19]、人工鱼群算法(Artificial Fish, AF)、FOA三类算法进行对比分析。上述算法统一运用Windows 10平台的MATLAB 2016b实现，并在CPU频率为2.3 GHz、内存为8 GB的计算机上运行。

3.1 数值算例

实验采用单区型且具有200个存储位置和两个交叉通道的仓库，其通道分布如图3所示。仓库起始(I/O)点位于仓库的左下角，仓库共有10个通道，从左向右依次从1到10号编号，每个通道两侧各有20个货位。仓库中，每个货位存放一类货品，其编号如图3所示。假设每个存储位置的长度为1长度单位(LU)，两个通道间的距离为5 LU。设拣选员的行走速度vtravel=10 LU/min，每个批次的准备时间tsetup=5 min。

3.2 实例验证

本文选择拣货车数量为3、订单数量为30的小规模算例进行验证。为方便求解结果展示，实例验证中按相同比例缩小了拣货车容量、订单大小和批次准备时间(拣货车容量为9、订单内物品数量服从均匀分布U[1,5]、批次的准备时间tsetup=1 min)。算法中其余参数与数值算例中的参数设置一致。该实例的订单详细数据由附录中的表1给出。订单拣选问题首先通过订单分批算法对订单进行拆分，并组成批次。订单分批算法的结果如图4所示，图中：q为批次编号，i为订单编号，k为货品编号。

在问题求解的第二阶段，智能果蝇优化算法对上述批次进行分配与排序。这些任务批次被分配给不同智能拣货车，并按照特定顺序进行拣选。求解结果如图5所示。图中，批次拣选时间通过甘特图中矩形的长度体现，批次拣选时间越长，矩形越长；反之亦然。

3.3 结果分析

基于数值算例，比较不同问题规模下订单可拆分与不可拆分时SFOA的结果，以及SFOA算法与同类型算法的性能。表1和表2中：tar表示5次独立重复实验的平均订单总延误时间;time表示算法平均计算时间；Gap1为订单可拆分与订单不可拆分条件下，SFOA算法的计算结果比较，Gap1=(tar(不可拆分)-tar(可拆分))/tar(不可拆分)×100%；Gap2为SFOA与ESD算法的计算结果比较，Gap2=(tar(ESD)-tar(SFOA))/tar(ESD)×100%；Gap3为SFOA与AF算法的计算结果比较，Gap3=(tar(AF)-tar(SFOA))/tar(AF)×100%；Gap4为SFOA与FOA算法的计算结果比较，Gap4=(tar(FOA)-tar(SFOA))/tar(FOA)×100%。

表1 订单可拆分与不可拆分情形下SFOA

续表1

表2 订单可拆分情形下SFOA与现有算法的比较分析

表1比较了订单可拆分与不可拆分情形下，SFOA求解的总延误时间与计算时间。计算结果显示，订单可拆分时SFOA的计算时间有所增加，但订单的总延误时间显著降低。比较两者的计算结果发现，订单拆分策略能显著降低智能仓库的订单总延误时间，其改善范围为8.33%(n=7,m=50)～48.61%(n=5,m=200)。

如图6所示为订单可拆分与不可拆分情形下，通过SFOA算法求解订单拣选问题的订单总延误和计算时间。结果显示，可拆分订单的总延误时间普遍优于不可拆分订单的总延误时间，但可拆分时算法的计算时间普遍高于不可拆分时算法的计算时间。尽管拆分策略会增加SFOA算法的求解时间，但增加的时间相对原求解时间较少，且不会随订单大小的变化显著上升。

为进一步分析SFOA算法的性能，表2比较了订单可拆分时SFOA算法与ESD算法、AF算法、FOA算法的计算结果。表2中结果显示，本文提出的SFOA算法性能优于其他同类型算法，SFOA算法相对ESD算法、AF算法、FOA算法能显著降低订单的总延误时间，其提升范围分别为11.36%(n=5;m=100)～34.55%(n=5,m=50)、0%(n=3;m=50)至61.72%(n=5;m=200)、2.70%(n=5;m=50)～64.71%(n=3;m=200)。

图7a、图7b分别比较了订单可拆分时ESD算法、AF算法、FOA算法和SFOA算法的订单总延误时间、计算时间。结果显示，SFOA算法在不同算例中的总延误时间、计算时间均优于其他算法。ESD算法、FOA算法的总延误时间大于SFOA算法的总延误时间，但ESD算法的计算时间随订单数量增长较快。AF算法在订单数为50时，与SFOA的计算结果相近，但随着订单数量的增加，AF算法的计算结果显著降低。

4 结束语

本文以电子商务环境下，智能仓库的订单拣选问题为背景，研究了订单拆分策略对智能仓库拣选效率的影响。研究以最小化订单总延误时间为目标，构建了考虑拆分策略的订单拣选优化模型。为提高模型的求解效率，基于问题的特性将其分解为订单分批和批次分配两个阶段。针对订单分批问题，提出了一种订单分批算法，以保证每个批次中的订单能占满智能拣货车的容量，同时使得每个批次中订单截止时间的差值最小。由于第二阶段的批次分配问题仍属于NP-hard问题，本文在KGFOA的基础上引入了NBR规则和双知识库，进而提出了SFOA算法求解该问题。数值实验结果表明，订单拆分策略能有效降低订单的总延误时间，且提出的SFOA算法相对已有算法具备更优的计算结果和更快的计算时间。研究结果表明，订单拆分策略能有效减少仓库中订单完成的延误时间。因此在工业应用中，企业处理限时配送任务时可将订单拆分后依拣货车的容量重新组成批次，进而提高订单配送的效率。

本文的研究为智能仓库中订单拣选算法的设计提供了思路，通过对订单进行拆分，可以更高效地完成限时订单的拣选任务。但该研究也存在一定局限性。本文仅研究了订单到达信息已知情况下的订单拣选优化，并未涉及在线订单达到的优化问题，同时也未考虑货品的摆放位置、紧急订单或智能仓库中机器故障等特殊情况，未来的研究可针对这些因素进行更深入的探讨。