中国每年要爆发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, …, pmax}拣选员的荟萃;
B={1, 2, …, m}可行批次的荟萃;
J={1, 2, …, n}客户订单的荟萃;
V={v1, v2, …, vg}商品存储点的荟萃 。
参数:
cj订单j (j∈J) 包括的商品数量;
C批次容量限制;
dj订单j (j∈J) 的完成期限;
M一个足够大的数;
vtravel拣选员在拣选路径中的行走速度 (单位:距离每单位时间) ;
vitem拣选员搜寻、拣取、核对货物的速度 (单位:时间每单位货物) ;
tsetup拣选员准备一个批次的时间;
est商品存储点s与t之间的距离的荟萃 (s≠t∈V) ;
αsj订单j (j∈J) 中是否包括存储在位置s (s∈V) 的商品;若是则αsj=1, 不然αsj=0 。
决策变量:
Tjpk订单j (j∈J) 分派到拣选位置Lpk (p∈P, k∈K) 的延迟时间;
ctp, k拣选位置Lpk (p∈P, k∈K) 的完成时间;
xjpk订单j (j∈J) 是否分派到拣选位置Lpk (p∈P, k∈K) 中, 若是则xjpk=1, 不然xjpk=0;
zbs在存储点s (s∈V) 的商品是否在可行批次b (b∈B) 中被拣选, 是则为1, 不然为0;
ybst弧段 (s, t) (s≠t∈V) 是否在可行批次b (b∈B) 的行走路径中, 是则为1, 不然为0;
ubpk批次b (b∈B) 是否分派到拣选位置Lpk (p∈P, k∈K) 中, 是则为1, 不然为0;
Vbj订单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的最后一个批次的结束时间为sdp;
办法3:取p*=arg min{sdp|p∈P};给拣选员p*新开一个批次并将订单j分派到新批次中;在荟萃U中去除订单j, 返回办法1 。
阶段二
办法4:记初始解为目今解;重置所有订单到荟萃U;
办法5:若荟萃U非空, 取荟萃U中完成期限最早的订单n*;不然, 跳转办法9;
办法6:记订单n*所在批次Bpk={n*}, 批次Bpk的容量W=wn*, 在荟萃U中去除订单n*;
办法7:界说savn, pk为将订单n分派到批次Bpk中后获得的新解比目今解减少的总延迟时间 。若savn, pk保存且max{savn, pk|n∈U:W+wn≤C}>0 (C为批次容量限制, wn是订单n的商品数) , 进入下一步;不然, 返回办法5;
办法8:取使总延迟时间减少最多的订单n’, 将订单n’加入批次Bpk中, 更新批次容量, 调解目今解并重新盘算总延迟时间;在荟萃U中去除订单n’;返回办法7;
办法9:输出目今解, 算法结束 。
在运用可变邻域下降算法前, 首先剖析初始解的邻域结构 。邻域的界说:设一个组合优化问题的可行解荟萃为S, 对一个解s∈S, 我们界说N (s) 为解s的邻域, 其中
。关于s’∈N (s) , s’可以通过s的一次局部移动或交换获得 。本文初始解的结构可以参考图2 (a) 。初始解的邻域分为两种类型, 一种参考图2 (b) 和图2 (c) , 我们称为批次邻域, 另一种称为订单邻域 。
批次邻域并不改变批次的内部订单组成, 只通过批次的移动或交换生成 。批次的移动或交换, 可以爆发在一个拣选员内部, 也可以爆发在两个拣选员之间 � ？悸堑轿颐且鸦谧钤缙鹗既掌诮峁沽顺跏冀�, 显然同一拣选员内部批次之间的移动或交换已不可改善初始解 。这样, 初始解的批次邻域有如下两种:
Nbatch1:在两个差别的拣选员之间, 移动其中一个拣选员的某个批次到另一个的批序次列中;
Nbatch2:在两个差别的拣选员之间交换两个批次 。
类似的, 订单邻域通过订单的移动或交换生成 。然而, 由于订单的移动或交换会改变批次结构, 需要考虑两方面的特殊情况 。一方面, 由于批次保存容量限制, 订单纷歧定能移动或交换进去, 为包管邻域是可行解, 关于这种订单, 需要开辟一个新批次来安排, 新批次将插入目标拣选序列最后一个拣选位置之后 。另一方面, 当某个批次的订单被移走后, 拣选位置会酿成空拣选位, 需要删除这些空拣选位, 制止盘算资源的浪费 。初始解的订单邻域有如下四种:
Norder1:在同一个拣货员内部, 移动其中某批次的某个订单到另一个批次中;
Norder2:在两个差别的拣选员之间, 移动一个拣选员某个批次的某个订单到另一拣选员的某个批次中;
Norder3:在同一个拣货员内部, 交换差别的两个批次中的两个订单;
Norder4:在两个差别的拣选员之间交换两个订单 。
以确定性的方法探索邻域结构的局部搜索算法被称为可变邻域下降算法 (Variable Neighborhood Descent, VND) 。因为差别的邻域结构通常具有差别的局部最小值, 所以通过邻域简直定性变革, VND能较快挣脱局部最优陷阱 。
算法需要一个确定的邻域结构序列 。我们基于革新节约法, 结合之前的数值实验, 确定选取N1=Nbatch2, N2=Norder1, N3=Norder2, N4=Norder3, N5=Norder4 。VND算法的具体办法如下
算法2:可变邻域下降算法
办法1:生成初始解s;
办法2:sinc=s;m=1;盘算总延迟时间tard (s) ;
办法3:当m不大于M时, 取s*=arg min{tard (s) |s∈Nm (sinc) };不然跳转办法6;
办法4:当tard (s*) <tard (sinc) 时, 进入办法5;不然, m=m+1, 跳回办法3;
办法5:sinc=s*;m=1;跳回办法3;
办法6:输出目今解sinc, 算法结束 。
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;sinc=s;
办法2:置count为0, 当count不满足终止条件, 进入下一步;不然, 跳至办法6;
办法3:通过2-opt操作爆发新路径snew=2opt (sinc) ;
办法4:若distance (snew) <distance (sinc) , 进入下一步;不然, count++;跳转回办法2;
办法5:count=0;sinc=snew;跳转回办法2;
办法6:输出目今解sinc, 算法结束 。
算法的实现基于一组数值实验 。我们假设了一个单库区, 具有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}中 。每个订单的完成期限从一个时间窗口[minj∈Jptj, (2· (1-MTCR) ∑j∈Jptj+minj∈Jptj) /pmax]中随机生成 。其中, 订单处理时间ptj是指订单j单独作为一个批次拣选处理的时间, MTCR (0<MTCR<1) 称为修正交通阻塞率, 描述了订单完成期限的紧急度 。当比率较大时, 订单的完成期限比较紧急, 且上述的时间窗口较窄 。我们设定MTCR的比率为0.6和0.8, 划分对应完成期限要求宽松和紧急的情况 。
设两个货位之间的距离为一个长度单位, 记为LU 。起始点距离最近的货位点距离为5LU 。通道宽1LU, 通道收支口转弯需1LU 。行走速度vtravel设为20LU/min, 搜索核对商品速度vitem设为0.25min/item, 准备时间tsetup设为3min 。设立三种情形, 后两种都是对第一种的革新 。情形Ⅰ接纳ESD算法求初始解, S型路径战略进行拣选作业;情形Ⅱ坚持路径战略稳定, 用节约法革新初始解;情形Ⅲ仍用ESD算法求初始解, 换用2-opt路径战略拣选 。
基于上述设定, 我们随机生成了一批订单, 春联合订单批次分派排序和路径问题, 划分对上述三种情形进行求解, 用python3.6编程, 在Core (TM) i7-6700CPU@3.4GHz, 16G内存的PC上实现了仿真实验 。结果如表1所示, 其中对初始解的提升比率imp= (tard (sESD) -tard (sVND) /tard (sESD) 。
剖析实验结果 。首先, VND算法对初始解的提升比率平均约为40%, 当订单完成期限较紧 (MTCR=0.8) 时, VND对初始解的提升比率 (情形Ⅰ、情形Ⅲ) 抵达50%以上 。其次, 情形Ⅲ的2-opt路径战略比情形Ⅰ求得的总延迟时间更优, 平均减少约100min;提升比率也最高, 平均比情形Ⅰ横跨近7% 。最后, 当MTCR=0.8时, 情形Ⅱ的革新节约法给出的初始解优于ESD算法;对初始解提升比率, 当订单量较大 (N=100) 时提升显著, 比情形Ⅰ横跨9% 。
表1 三种情形的总延迟时间 (单位:min) 和对初始解的提升比率
本文对电商仓储中前沿的联合订单批次分派排序和路径问题进行描述, 给出了相应的示例图, 并建立了混淆整数计划的数学模型 。我们接纳启发式算法求解, 基于革新节约法给出一个较好的初始解, 通过可变邻域下降算法对模型进行求解, 其中对批次拣选路径利用2-opt要领快速优化 。仿真实验结果标明, 在联合拣选路径问题之后, 2-opt路径战略能显著节省订单总延迟时间;当订单完成期限较紧急、订单量较大时, 革新节约法给出的初始解优于ESD算法 。
【本文标签】
【责任编辑】yd2333云顶电子游戏云仓
yd2333云顶电子游戏冷链物流与茶百道告竣相助：在现代快节奏的生活中，奶茶已经成为了许多人生活中的···【详情+】
yd2333云顶电子游戏家人们！春暖花开，春意盎然，在这个温暖的日子，荣誉降生在安徽的铜陵，等了很久···【详情+】
邮 箱：liufei@pingwl.com
地点：上海市松江区佘山镇陶干路1199号D幢
电 话：400-096-2966
182-0218-6162
备案号：沪ICP备2022022726号-2
技术效劳：一躺网络
手机二维码
