电商仓储联合订单批次分配排序和路径问题

中国每年要产生300亿件以上的快递包裹, 这得益于电子商务的快速发展。仓储物流日益成为电商发展中的瓶颈所在。订单拣选流程是仓储运营中最为关键的流程, 占用了60%以上的运营成本。相较于传统的仓储中心, 电商仓储中心的订单具有日均单量高、订单体量小、及时响应性高等特点。如何确定最优的订单批次, 如何调度批次的分配和排序, 如何在较短时间内完成订单的拣选, 联合订单批次分配排序和路径问题引起了业界和学术界的关注。

客户订单通常会有一个确切的完成期限, 一旦产生延误, 会降低客户满意度并带来较高的成本。在多人拣选的场景下, 是否发生延误以及延误程度, 取决于批次的分配和先后排序、批次的订单组成和批次处理时间 (主要是路径行走时间) 等。一般的, 由于不可能满足所有订单的完成期限, 必须确定一个最优分配排序方案, 以最小化订单的总延迟时间。

本文对最小化订单总延迟时间的联合订单批次分配排序和路径问题进行描述并建立数学模型, 之后给出求初始解的方法, 并用可变邻域下降算法改进订单分批、用2-opt方法改进行走路径, 最终求得最小的订单总延迟时间。

我们考虑的是一个人工拣选、低位货架的单库区, 采用人到货的拣选方式。库区中货架有规则地编号, 商品可以方便地被拣选员拣取。库区仅有一个起始点, 分布在库区左下角, 可以进行准备、卸货和打包等操作。拣选员采用手推车等拣选设备进行拣选, 拣选设备有容量限制。

问题涉及的拣选流程描述如下:首先, 一定数目的客户订单进入系统, 订单通常包含商品编码、名称、所需数量、存储点和完成期限等信息。由于拣选设备容量、完成期限等因素限制, 订单按某些规则汇总成批次, 又称为拣选单。最后, 将拣选单分配给拣选员, 拣选员按照拣选单进行拣选, 直到完成任务。

S型策略是实际应用中最常用的拣选路径策略, 图1是S型策略的示意图。拣选路径问题是一个TSP, 由于批次容量的限制, 一个批次的路径问题规模不大, 我们将S型路径作为初始解, 采用2-opt方法, 可以更快求得最优路径。

拣选过程所花费的时间包括准备时间、行走时间和搜寻时间等。其中, 准备时间包含领取拣选单和推车、卸货打包等动作时间, 一般是固定的。假设行走速度恒定, 行走时间取决于路径策略和货位点的分布。假设搜索每个商品的速度恒定, 搜寻时间包括对商品的搜索、拣取和核对等时间, 主要取决于货位点的多少。对于一个批次, 拣选员从起始点领取拣选单的时刻记为批次起始时刻。类似的, 拣选员完成拣选任务回到起始点的时刻记为批次完成时刻。一个批次中所有订单的完成时刻都是批次完成时刻, 这样每个订单的延迟时间等于订单所在批次的批次完成时刻减去该订单完成期限。

订单批次分配与排序问题的示意图如图2所示。在图2中, 8个订单 (含有1~5件商品) 被分批次地分配给两名拣选员, 每个批次容量限制为7件。例如, 在图2 (a) 给出的初始解中, 订单O2和O3汇总成批次#1, 被分配给了拣选员甲, 该批次共需拣选6件商品。图2 (b) 是拣选员甲的批次#1与批次#2交换后生成的解。图2 (c) 是拣选员甲的批次#1和拣选员乙的批次#4交换后生成的解。订单图示和每个解的订单总延迟时间如图2 (d) 和图2 (e) 所示。

结合如上问题描述, 我们给出建立模型所需的集合、参数和决策变量。

集合:

P={1, 2, …, p_max}拣选员的集合;

一个拣选员的拣选位置集合, 是分配给该拣选员的最大批次数;

B={1, 2, …, m}可行批次的集合;

J={1, 2, …, n}客户订单的集合;

V={v₁, v₂, …, v_g}商品存储点的集合。

参数:

c_j订单j (j∈J) 包含的商品数量;

C批次容量限制;

d_j订单j (j∈J) 的完成期限;

M一个足够大的数;

v_travel拣选员在拣选路径中的行走速度 (单位:距离每单位时间) ;

v_item拣选员搜寻、拣取、核对货品的速度 (单位:时间每单位货品) ;

t_setup拣选员准备一个批次的时间;

e_st商品存储点s与t之间的距离的集合 (s≠t∈V) ;

α_sj订单j (j∈J) 中是否包含存储在位置s (s∈V) 的商品;若是则α_sj=1, 否则α_sj=0。

决策变量:

T_jpk订单j (j∈J) 分配到拣选位置L_pk (p∈P, k∈K) 的延迟时间;

ct_p, _k拣选位置L_pk (p∈P, k∈K) 的完成时间;

x_jpk订单j (j∈J) 是否分配到拣选位置L_pk (p∈P, k∈K) 中, 若是则x_jpk=1, 否则x_jpk=0;

z_bs在存储点s (s∈V) 的商品是否在可行批次b (b∈B) 中被拣选, 是则为1, 否则为0;

y_bst弧段 (s, t) (s≠t∈V) 是否在可行批次b (b∈B) 的行走路径中, 是则为1, 否则为0;

u_bpk批次b (b∈B) 是否分配到拣选位置L_pk (p∈P, k∈K) 中, 是则为1, 否则为0;

V_bj订单j (j∈J) 是否分配到可行批次b (b∈B) 中, 是则为1, 否则为0。

数学模型:

根据上面的参数和变量, 建立如下混合整数规划 (MIP) 模型:

模型阐述:

函数 (1) 是目标函数, 即求订单总延迟时间的最小值。约束 (2) 给出订单分配到批次的决策变量的定义, 保证只有当订单与可行批次分配到同一拣选位置时, 决策变量才为1。约束 (3) 保证每个订单仅被分配到一个可行批次中。约束 (4) 保证批次中的商品数不超过其批次容量限制。约束 (5) 确保每个拣选位置最多分配一个可行批次。若一个可行批次被分配到某个拣选位置, 该位置记为有效拣选位, 约束 (6) ~ (8) 可看作该批次的拣选路径问题 (TSP) ;否则, 该位置为空拣选位。约束 (6) 给出批次的行走路径长度公式。约束 (7) 保证批次中的商品存储点仅被访问一次。约束 (8) 确保批次拣选路径中没有子回路出现。约束 (9) 表示批次中的商品存储点受限于订单中的商品存储点。约束 (10) 保证两个相邻的有效拣选位 (批次) 的处理时间不重叠, 即一个拣选员在某个时刻仅能处理一个批次。约束 (11) 表示拣选员的批次起始时刻为0。约束 (12) 表示拣选位置中订单的延迟时间。约束 (13) 保证批次完成时刻和拣选位置中订单的延迟时间的非负性。

对于上述建立的非线性混合整数模型, 当问题规模较大时, 求最优解十分困难, 所以我们采用启发式算法求解。本文首先设计了改进节约法得到一个较好的初始解, 再利用可变邻域下降算法得到最优解。涉及路径问题, 采用2-opt方法得到每个批次的最优拣选路径。

邻域算法的结果受初始解的影响较大, 好的初始解能够提高算法的收敛速度。Henn给出了一种最早起始日期 (ESD) 算法。这种算法基于订单完成期限的优先级规则, 却没有考虑到批次处理时间 (主要是路径行走时间) 对总延迟时间的影响。因此, 我们结合最早起始日期算法, 提出了一种基于Clark-wright算法的改进节约法。该算法的基本思路是:首先基于ESD算法, 将每个订单作为一个批次分配给拣选员;然后, 在批次容量限制下, 先选择当前完成期限最早的订单, 再选择另一个订单与其合并为一个批次, 选择依据是选择能使订单总延迟时间减少最多的那个。算法的具体步骤如下:

算法1:改进节约法

阶段一

步骤1:若未分配订单集合U中还有未分配的订单, 取其中完成期限最早的订单j;否则, 跳转阶段二;

步骤2:对每个拣选员p, 将订单j作为一个单独的批次, 分配到该拣选员p最后一个批次位置之后, 记分配前拣选员p的最后一个批次的结束时间为sd_p;

步骤3:取p^*=arg min{sd_p|p∈P};给拣选员p^*新开一个批次并将订单j分配到新批次中;在集合U中去除订单j, 返回步骤1。

阶段二

步骤4:记初始解为当前解;重置所有订单到集合U;

步骤5:若集合U非空, 取集合U中完成期限最早的订单n^*;否则, 跳转步骤9;

步骤6:记订单n^*所在批次B_pk={n^*}, 批次B_pk的容量W=w_n*, 在集合U中去除订单n^*;

步骤7:定义sav_{n, pk}为将订单n分配到批次B_pk中后得到的新解比当前解减少的总延迟时间。若sav_n, _pk存在且max{sav_n, _pk|n∈U:W+w_n≤C}>0 (C为批次容量限制, w_n是订单n的商品数) , 进入下一步;否则, 返回步骤5;

步骤8:取使总延迟时间减少最多的订单n’, 将订单n’加入批次B_pk中, 更新批次容量, 调整当前解并重新计算总延迟时间;在集合U中去除订单n’;返回步骤7;

步骤9:输出当前解, 算法结束。

在运用可变邻域下降算法前, 首先分析初始解的邻域结构。邻域的定义:设一个组合优化问题的可行解集合为S, 对一个解s∈S, 我们定义N (s) 为解s的邻域, 其中。对于s’∈N (s) , s’可以通过s的一次局部移动或交换获得。本文初始解的结构可以参考图2 (a) 。初始解的邻域分为两种类型, 一种参考图2 (b) 和图2 (c) , 我们称为批次邻域, 另一种称为订单邻域。

批次邻域并不改变批次的内部订单组成, 只通过批次的移动或交换生成。批次的移动或交换, 可以发生在一个拣选员内部, 也可以发生在两个拣选员之间。考虑到我们已基于最早起始日期构造了初始解, 显然同一拣选员内部批次之间的移动或交换已不能改善初始解。这样, 初始解的批次邻域有如下两种:

N_batch1:在两个不同的拣选员之间, 移动其中一个拣选员的某个批次到另一个的批次序列中;

N_batch2:在两个不同的拣选员之间交换两个批次。

类似的, 订单邻域通过订单的移动或交换生成。然而, 由于订单的移动或交换会改变批次结构, 需要考虑两方面的特殊情况。一方面, 由于批次存在容量限制, 订单不一定能移动或交换进去, 为保证邻域是可行解, 对于这种订单, 需要开辟一个新批次来放置, 新批次将插入目标拣选序列最后一个拣选位置之后。另一方面, 当某个批次的订单被移走后, 拣选位置会变成空拣选位, 需要删除这些空拣选位, 避免计算资源的浪费。初始解的订单邻域有如下四种:

N_order1:在同一个拣货员内部, 移动其中某批次的某个订单到另一个批次中;

N_order2:在两个不同的拣选员之间, 移动一个拣选员某个批次的某个订单到另一拣选员的某个批次中;

N_order3:在同一个拣货员内部, 交换不同的两个批次中的两个订单;

N_order4:在两个不同的拣选员之间交换两个订单。

以确定性的方式探索邻域结构的局部搜索算法被称为可变邻域下降算法 (Variable Neighborhood Descent, VND) 。因为不同的邻域结构通常具有不同的局部最小值, 所以通过邻域的确定性变化, VND能较快摆脱局部最优陷阱。

算法需要一个确定的邻域结构序列。我们基于改进节约法, 结合之前的数值实验, 确定选取N₁=N_batch2, N₂=N_order1, N₃=N_order2, N₄=N_order3, N₅=N_order4。VND算法的具体步骤如下

算法2:可变邻域下降算法

步骤1:生成初始解s;

步骤2:s^inc=s;m=1;计算总延迟时间tard (s) ;

步骤3:当m不大于M时, 取s^*=arg min{tard (s) |s∈N_m (s^inc) };否则跳转步骤6;

步骤4:当tard (s^*) <tard (s^inc) 时, 进入步骤5;否则, m=m+1, 跳回步骤3;

步骤5:s^inc=s^*;m=1;跳回步骤3;

步骤6:输出当前解s^inc, 算法结束。

2-opt方法是一种简便实用的局部搜索算法, 被广泛应用于解决TSP。其基本思想是随机取路径中的两个节点 (非起止点) , 将两个节点之间的路径翻转获得新路径 (2-opt操作) 。举个例子, 若原路径是[A, B, C, D, E, F, A], 2-opt操作选取节点B和E, 则新路径变为[A, E, D, C, B, F, A]。在所有2-opt操作得到的新路径都不能改善当前路径时, 当前路径即为一条2-opt路径。在小规模TSP中, 2-opt路径几乎可以作为最优解。

算法3:2-opt方法

步骤1:将S型策略的路径作为初始解s;s^inc=s;

步骤2:置count为0, 当count不满足终止条件, 进入下一步;否则, 跳至步骤6;

步骤3:通过2-opt操作产生新路径s^new=2opt (s^inc) ;

步骤4:若distance (s^new) <distance (s^inc) , 进入下一步;否则, count++;跳转回步骤2;

步骤5:count=0;s^inc=s^new;跳转回步骤2;

步骤6:输出当前解s^inc, 算法结束。

算法的实现基于一组数值实验。我们假设了一个单库区, 具有800个货位, 通道的具体分布如图1所示。库区起始点在库区左下角。库区有10个通道, 通道从左向右依次从1到10号编号。每个通道两边各有40个货位。仓储中心实际常采用ABC三分类的存储策略, A类商品能够满足50%的订单需求, B类商品能够满足30%, 剩余20%归为C类。我们设定1、2号通道存放A类商品, 3、4、5号通道存放B类商品, 剩余通道存放C类商品。

拣选员人数设定为2人和4人。批次容量限制设为10和20。订单的数目设置成50和100。由于电商的订单体量较小, 假定订单包含的商品数均匀分布在集合{1, 2, 3, 4, 5}中。每个订单的完成期限从一个时间窗口[min_j∈Jpt_j, (2· (1-MTCR) ∑_j∈Jpt_j+min_j∈Jpt_j) /p_max]中随机生成。其中, 订单处理时间pt_j是指订单j单独作为一个批次拣选处理的时间, MTCR (0<MTCR<1) 称为修正交通阻塞率, 描述了订单完成期限的紧急度。当比率较大时, 订单的完成期限比较紧急, 且上述的时间窗口较窄。我们设定MTCR的比率为0.6和0.8, 分别对应完成期限要求宽松和紧急的情况。

设两个货位之间的距离为一个长度单位, 记为LU。起始点距离最近的货位点距离为5LU。通道宽1LU, 通道出入口转弯需1LU。行走速度v_travel设为20LU/min, 搜索核对商品速度v_item设为0.25min/item, 准备时间t_setup设为3min。设立三种情形, 后两种都是对第一种的改进。情形Ⅰ采用ESD算法求初始解, S型路径策略进行拣选作业;情形Ⅱ保持路径策略不变, 用节约法改进初始解;情形Ⅲ仍用ESD算法求初始解, 换用2-opt路径策略拣选。

基于上述设定, 我们随机生成了一批订单, 对联合订单批次分配排序和路径问题, 分别对上述三种情形进行求解, 用python3.6编程, 在Core (TM) i7-6700CPU@3.4GHz, 16G内存的PC上实现了仿真实验。结果如表1所示, 其中对初始解的提升比率imp= (tard (s^ESD) -tard (s^VND) /tard (s^ESD) 。

分析实验结果。首先, VND算法对初始解的提升比率平均约为40%, 当订单完成期限较紧 (MTCR=0.8) 时, VND对初始解的提升比率 (情形Ⅰ、情形Ⅲ) 达到50%以上。其次, 情形Ⅲ的2-opt路径策略比情形Ⅰ求得的总延迟时间更优, 平均减少约100min;提升比率也最高, 平均比情形Ⅰ高出近7%。最后, 当MTCR=0.8时, 情形Ⅱ的改进节约法给出的初始解优于ESD算法;对初始解提升比率, 当订单量较大 (N=100) 时提升显著, 比情形Ⅰ高出9%。

本文对电商仓储中前沿的联合订单批次分配排序和路径问题进行描述, 给出了相应的示例图, 并建立了混合整数规划的数学模型。我们采用启发式算法求解, 基于改进节约法给出一个较好的初始解, 通过可变邻域下降算法对模型进行求解, 其中对批次拣选路径利用2-opt方法快速优化。仿真实验结果表明, 在联合拣选路径问题之后, 2-opt路径策略能显著节省订单总延迟时间;当订单完成期限较紧急、订单量较大时, 改进节约法给出的初始解优于ESD算法。