订单寻仓与分批拣选联合调度问题研究

（上海海事大学 物流科学与工程研究院，上海 201306）

0 引言

随着电商的发展，网购已经成为大众主要的购物消费方式之一。企业为了吸引客户流量，提高商品销量，频繁开展促销活动，订单的数量和规模都急剧增加。当库存水平降低，单个仓库越来越难以满足订单需求，导致订单拆分情况频繁发生。大量的订单分配到仓库后，导致仓库拣选作业量繁重，订单履行时间变长。订单的拆分和订单履行时间的延长不仅增加了物流成本也降低了客户满意度。仓库作业是订单履行的主要落地场景，订单拣选又是最耗费人力和时间的环节，影响到整个仓库的作业效率以及作业成本。目前，仓库订单拣选普遍采用的方法之一为分批拣选。因此，将订单寻仓和订单分批问题联合优化能够提升仓库作业效率，降低订单履行成本，从而提升订单履行整体效果。

针对电商订单履行中的订单寻仓问题，国外学者对降低订单履行过程中的拆单率做了较多研究。Xu[1]等利用订单下达到发货之间的延迟时间，对客户订单进行重新分配，降低了订单的拆单率。Liu[2]等建立了两级物流模型，目的是将在线订单分配至配送中心，同时能满足区域内的门店销售需求，运用拉格朗日松弛法求解模型，降低了物流成本。Mahar和Wright[3]提出了一种动态订单履行策略，通过对订单的积累和库存信息的充分利用，以减少订单履行的等待、库存和运输成本。Acimovic和Graves[4]通过对未来订单履行成本进行估计，以当前订单履行成本和未来预估成本之和为目标建立模型，并设计了启发式算法降低了运输成本。Jasin and Sinha[5]未来订单考虑在内，用一个确定的模型来近似考虑往后不确定的销售机会的多商品在线订单分配问题的模型，设计了启发式算法降低包裹数量和运输成本。Ardjmanda[6]等在订单履行问题中考虑了运输过程中的包装问题，以最小运输成本和时间为目标建立数学模型，设计了多目标遗传算法，最终降低了运输成本以及运输时间。Ishfaq[7]研究了全渠道下在线零售商的订单履行问题，考虑了供应商、区域仓库、电商仓、门店联合发货下的订单履行成本，设计了启发式算法最终降低了总成本。

国内学者更倾向于联合仓储、配送问题进行综合研究。张源凯[8]研究了一地多仓环境下网上超市订单分配问题，将订单寻仓和车辆调度问题结合建立模型，设计了能够快速生成较优解的启发式算法。李建斌[9]等通过在销售初期对商品在各仓库中的数量进行优化分配，减少了销售过程中的拆单率。徐浩轩[10]研究了电商在预判发货背景下双模式运输的动态批量配送优化问题，为三级供应链系统建立数学规划模型，并设计了动态规划算法求解，算例证明了该算法的有效性。师嘉欣[11]研究了城市物流配送订单履行问题，设计启发式算法优化整体履行效率。

另外，针对电商仓库的仓库拣选问题，也有学者进行了大量的研究。对于订单分批问题，Wang[12]研究了在线订单情况下的订单分批问题，考虑了订单批次的完成时间，以最小化所有批次拣选时间为目标建立数学模型，基于启发式算法中提出的新的规则求解，提高了订单的交付效率，平衡了工作量。王旭坪[13]研究了订单动态到达情况下，考虑拣选员工数量、拣选设备容量的电商仓库订单分批拣选问题，采用改进的固定时间窗订单分批启发式规则求解，降低了订单拣选时间。针对新零售情景下的订单拣选作业优化问题，张宁[14]考虑了新零售拣选时效、拣选策略以及分区拣选工作量均衡等因素，以订单拣选完成时间和各批次订单的分区拣选完成时间标准差之和最小为目标函数建立模型，并采用带精英策略的非支配排序遗传算法求解。王迪[15]研究了订单分批和批次分配的联合问题，以最小化批次拣选延时时间为目标建立了数学模型，并提出了一种基于一定规则的混合算法，减少了订单处理延时时间。王转[16]考虑拣选器具和商品包装体积,构造以最大化里程节约量为目标的订单分批模型，提出基于启发式拣选路径下节约里程的订单分批算法，降低了拣选路径。王华东[17]针对跨境电商客户订单的多品类且数量不稳定的特点，采用订单动态时间窗分拣策略,并在仓库拣货路径优化的基础上,建立了跨境电商保税仓库拣货模型，提出了适用于跨境电商保税仓库的波次分拣策略，降低了拣选路径长度。另外，杨宏燕[18]构建了以作业时间最短、成本最小为目标，满足交货期限制、等约束下电商企业仓库出库作业计划编制优化模型，并设计了遗传算法求解，提高了仓库作业效率，降低了成本。

目前学者对订单履行过程中的订单寻仓问题已进行了充分研究，主要研究内容是通过对订单的延时处理，即积累一定量的订单，再充分利用库存信息或者对未来的销售机会进行评估，调整订单分配的仓库从而减少订单的拆单率，降低物流成本。然而，随着电商发展，电商订单趋于多批量，小规模的特点，日常销售过程中拆单率日益降低，只有在电商促销场景下，订单寻仓问题才更具有优化空间。并且，电商订单履行过程还包括仓库作业和配送等环节，订单拣选是仓库作业中占用人力、时间最多的环节，订单量的上升也加大了仓库的作业量。对于电商仓库拣选的研究，学者们的研究集中在如何将仓库已接受在线订单在满足发货时间约束下进行分批处理。然而，订单分配到不同仓库直接决定仓库的拣选作业，因此，在订单寻仓的成本和拣选作业效率二者之间寻找到一个平衡点能够提高订单履行的整体效率。

本文以最小化订单履行总成本和拣选路径长度为目标，建里多目标数学模型，并设计了三阶段启发式算法：首先将订单分配到合适的仓库，目标是总成本最小，再以一定规则生成初始订单批次。同时，调整订单批次，使得所有批次的巷道数量和减少，从而提高拣货效率。实验结果证明，三阶段启发式算法能够有效提高订单履行的整体效果。

1 问题描述与模型建立

1.1 问题描述

本文研究的问题包括电商订单履行的两个阶段，如图1所示，第一阶段为订单寻仓，客户订单到达后，电商首先要决定该订单由哪些仓库发货，传统电商发货策略为先就全，再就近，即优先单仓发货，单仓不能满足发货则由最近的仓库联合发货。订单到达仓库后，为了提升拣货效率，需要对订单进行分批操作，每个拣货员每次拣选一个批次订单，针对订单分批问题，本文采用遍历策略，即拣货员从入口出发，遍历每个含有批次中商品的巷道并取走商品，然后再返回入口处。订单批次的巷道数越少，拣货员的行走距离越短，拣货效率越高。

表1列出了两个仓库的库存信息以及分别到两个订单接收地的运输费用，假设仓库固定处理费用为5元。当订单1先到达时，根据先就全，再就近的原则，仓库1距离订单1的收货地址最近，且满足需求，则将订单1分配给仓库1，同时更新仓库的库存信息，库存剩余为1和1，订单1产生的履行成本为固定费用5元和运输费用10元，共计15元。之后，订单2到达，根据就全原则，没有单个仓库能够满足商品A的数量需求，而仓库1和仓库2距离订单1的收货地址较近，且总库存满足需求，则将订单2分配给仓库1和仓库2，产生固定成本10元和运输成本26元，共计36元。该业务场景下将产生仓库固定费用和运输费用共计51元。

图1 订单履行流程

表1 仓库库存和运费

表2 订单需求

现在对这一场景做一个优化，如果订单1和订单2先后到达，优先处理订单2，那么订单2将被分配给仓库1，仓库1剩余库存变为0和1，那么订单2的成本为16元，当订单1到达后，仓库1库存不能满足，则分配给仓库2，仓库2剩余库存变为0和1，成本为18。可见，与原始策略相比，仓库剩余库存并没有变化，然而总成本变为34，成本减少了17元。

表3 仓库订单

对于第二阶段的订单分批问题，表3展示了第一阶段的分配结果，以及每个订单所处的巷道，假设有3个巷道，每个订单在不同仓库中的巷道情况相同。可知，仓库1和2都需要拣选2个巷道，仓库3的拣选作业只要经过1个巷道，将订单3重新分配给仓库1，成本上升了2元，但是总的拣选路径长度减少了一个巷道的距离。订单履行过程中不仅要考虑运输成本，仓库作业效率的提升也将减少仓库作业成本，提高发货速度。

1.2 基本假设

本文提出了如下假设。所有订单需求能够被满足保证了算法运行的顺畅；仓库配置相同为模型提供了理想化的业务场景，本文提出的算法依然能够处理仓库配置不同的情况；为了突出核心问题，不考虑堵塞情况。此外，假设订单能够一次拣选完成。

假设1：所有订单都能被履行，不存在仓库缺货情况；

假设2：所有仓库除库存余量信息以外的内部基础设施、人员配置相同；

假设3：订单拣货过程中不考虑堵塞情况；假设4：同一批次订单能够一次拣选完成。

1.3 模型建立

首先对本文模型的变量做出以下定义：

I：表示仓库集合，I={i|i=1，2，…，m}；

J：表示订单集合，J={j|j=1，2，…，n}；

K：表示商品种类集合，K={k|k=1，2，…，v}；

S：所有批次集合，S={s|s=1，2，…，u}；

ls：批次u的拣选路径长度；

q：拣选批次最大容量；

c1：仓库固定发货成本；

订单履行问题的模型定义如下：

约束条件：

式(1)和式(2)为目标函数，式(1)为最小化订单履行成本，即仓库固定处理成本和运输成本的总合，式(2)为最小化仓库拣选路径长度。式(3)表示仓库总发货量不能超过库存量。式(4)表示仓库发货量满足每个订单的需求。式(5)和式(6)确定了yij的值，yij用来计算仓库的固定成本以及包裹数量。式(7)确保一个订单只能分配至一个批次中，不能重复拣选。式(8)表示每个批次订单商品数量不能超过批次上限。

2 基于联合调度的三阶段启发式算法

2.1 算法基本思路

本文研究的是订单履行过程中的订单寻仓和订单分批联合调度问题，设计了三阶段启发式算法求解。第一阶段是求解订单寻仓问题，基于目前电商订单的特点，订单数量多，规模小，订单拆分集中在多商品订单中，所以将多商品订单和单商品订单分开处理，优先处理多商品订单。第二阶段订单已经被分配到了合适仓库，在种子算法的基础上做一些调整为每个仓库生成订单分批问题的初始解。第三阶段通过一定规则让初始解在邻域内扰动来减少所有批次包含的总数巷道，从而优化订单分批问题。

2.2 三阶段启发式算法具体步骤

2.2.1 求解订单寻仓问题

订单寻仓问题的解与订单处理顺序有关，所以通过交换每个多商品订单和它的关联订单的处理顺序优化订单寻仓问题的解，图2为第一阶段求解订单寻仓算法流程。

Step1：生成订单集合O。

Step2：将O中的订单按照商品种类数量降序排列，优先处理多商品订单。

Step3：为多订单生成关联订单集合。对于任意多商品订单，只要其余的多商品订单中与该订单有重合商品，则认为是该订单的关联订单。

Step4：按照先就全，再就近的原则以订单集合T中的顺序处理订单，并计算订单履行成本。

Step5：令i=2。

Step6：将第i个订单与前i-1个订单中的关联订单交换位置，计算订单履行成本F1，若F1＜F，则更新订单处理顺序；否则，转step7。

Step7：检查i是否为最后一个订单，如果是，则结束；否则，令i=i+1，转step6。

图2 第一阶段流程

2.2.2 生成初始订单批次

对于一个仓库中的订单分批问题，将该仓库的订单分为多商品订单任务集合T1和单商品订单任务集合T2，再使用传统种子算法分别生成初始批次。生成初始批次的规则是取一订单作为种子批次，按照最大相同巷道数量为优先级，不断加入订单直到到达批次容量上限，并且加入的订单与种子批次的相同巷道数量必须大于0，这有助于第三阶段的解的改进。下面说明多商品订单任务集合的分批过程，单订单的批次生成方式与之相同，图3为第二阶段多商品订单生成初始订单批次流程。

Step1：将T1中的订单按照巷道数量降序排列。

Step2：检查T1是否为空，若为空，则结束；否则，转step3。

Step3：取T1中第一个订单，视一个批次，将剩余订单与之对比，以相同巷道数量降序排列，将同巷道数大于0的订单依次加入该批次中，直到到达批次容量上限或者无订单可加入，转step2。

图3 第二阶段流程

2.2.3 优化订单分批

本阶段将每个批次中的订单按照一定规则在所有仓库中进行搜索，选择加入更加合适的批次，从而减少总批次数量和所有批次总巷道数，每个订单只能重新分配一次。搜索停止条件为批次信息不再发生改变，图4为第三阶段优化订单批次流程。

Step1：将所有仓库中的种子批次按照批次中订单数量升序排列，生成批次集合S，s表示第s个订单批次。

Step2：令s=1。

Step3：对第s个批次中每一个订单在所有仓库的订单批次中搜索，仓库搜索的优先级是较近的仓库优先搜索，若订单能加入某一批次中，且加入后该批次的拣选巷道总数不变，满足该仓库库存限制和该批次容量约束，则将该订单加入该批次，从s中删除该订单；否则，保留该订单。

Step4：若第s个批次是多巷道订单批次，即该批次包含多个巷道，转step5；否则，转step6。

Step5：更新批次信息，转step7。

Step6：若第s个批次为空，转step1；否则，还原该批次，转step7。

Step7：检查是s否为最后一个批次，若是，则结束；否则，令s=s+1，转step3。

图4 第三阶段流程

3 实验分析

本文用python语言编写程序代码，实验环境为windows10系统，Inter（R）Cor（TM）i3-8100 CPU@3.50GHz处理器，4GB内存。算例中订单信息来源于某公司促销活动当天产生的订单、仓库数据。实验共设计了10个算例，在订单600～1500的不同订单数量下进行实验。

模型中参数包括仓库14个，库存信息包含1000个sku，订单1500条。仓库共有8个巷道，巷道长度为60米，巷道间宽度为1.5米，拣选容量上限为15。仓库地址和订单地址在1500×1500km的范围内随机生成，仓库固定费用为5元/订单，运输费用如表4所示。

表4 运输费用

表5 实验对比结果

本实验对比的算法为FCFS-种子策略下的传统订单履行算法和遗传算法。FCFS-种子算法即订单按照到达顺序以传统订单寻仓算法分配到仓库，再由种子算法[19]生成订单批次，种子算法的优先规则是最大相同巷道数量。由于本问题研究内容较新，所以设计经典智能优化算法遗传算法（GA）作为对比，证明启发式算法的有效性。表5列出了10个算例的实验对比结果。

图5为拣选路径在三种算法下的对比图。实验结果表明，GA算法和本文提出的启发式算法都能够降低仓库订单拣选路径长度。图6为GA算法和启发式算法对比FCFS-算法结果的路径长度降低量，看出本文提出的启发式算法在拣选路径的优化上明显优于GA算法。经过计算，启发式算法平均提升了拣选效率7.6%。图7为对比FCFS-种子算法下，订单履行成本的降低量，GA算法优化效果非常不稳定，当订单量增多时，将会增加订单履行成本；而启发式算法随着订单量增加，订单履行成本优化效果越明显，综合能力优于GA算法。图8显示了启发式算法所得订单总包裹数的降低量，可以看出随着问题规模上升，订单的总包裹数量也随之下降。综上所述，启发式算法能够有效提升订单履行整体效率，并且性能上优于遗传算法，证明了算法求解该问题的有效性。

图5 拣选路径长度对比

图6 拣选路径降低量对比

图7 成本降低量对比

图8 包裹数量减少量

4 结语

本文研究了电商订单履行过程中订单寻仓和分批拣选的联合问题，针对电商订单的特点设计了三阶段启发式算法，将多商品订单和单商品订单分开处理，通过交换关联订单的处理顺序，降低订单履行成本和包裹数量；生成初始订单分批解后，以一定规则使得解在领域内搜索，改进订单分批问题的解。实验结果表明，提出的算法能够提升订单履行的整体效率。然而，本文也存在一些不足，比如未考虑到仓库拣选中的人员安排问题以及积累订单将会影响到订单履行过程的整个作业时间，所以下一步将对在拣选人员的安排以及考虑订单积累量的影响做进一步的研究。