时间窗约束下需求可拆分的拣选与配送联合优化问题研究

徐 菱，胡小林，胡小亮

时间窗约束下需求可拆分的拣选与配送联合优化问题研究

徐 菱1, 2，胡小林1，胡小亮1

（1.西南交通大学，交通运输与物流学院，成都 611756；2. 综合交通运输智能化国家地方联合工程实验室，成都 611756）

针对企业急需解决的订单履行效率低问题, 基于需求可拆分的思想, 综合考虑时间窗和组合拣选策略特征, 建立时间窗约束下需求可拆分的拣选与配送联合优化模型。通过拣选成本、拆分需求成本、配送成本、时间惩罚成本反映订单履行效率, 指出拆分需求、组合策略以及算法对于模型的优化。利用两阶段算法对模型求解, 通过算例验证了模型和算法的有效性。最后以不拆分需求、S-Shape策略和顺序决策算法为对比方案, 发现总成本分别下降了33.43%、12.3%和28.17%, 证明本文建立的模型和算法可以有效提高订单响应速度, 降低订单履行成本。

联合优化; 组合策略; 需求可拆分; 时间窗; 两阶段算法

0 引 言

随着电子商务的发展，我国快递量高速增长，2017年国内快递量突破400亿件，其中电子商务驱动的快件量超过130亿件。高速增长的快递量使企业面临成本居高不下、快递爆仓、暴力分拣、配送延误等问题，同时消费者对商品送达时效性要求更高，提高订单履行效率、缩短订单响应时间是电子商务企业亟待解决的问题。

订单履行包括拣选和配送两个环节，配送路径优化决定车辆订单及其拣选截止时间（PickingDue Date，简称PDD），订单PDD影响拣选批次划分和批次拣选顺序，批次拣选顺序影响批次拣选完成时间，从而影响车辆开始配送时间。而将拣选与配送联合优化可以从整体上降低5%~20%的成本[1-3]。此外，电子商务环境下需求呈现数量少、种类多的特点，若1个需求点由1个人员拣选并由1辆车配送效率太低，拆分需求可以提高车辆满载率、缩短配送距离、提高配送准点率[4-6]。

因此，本文借鉴生产与配送联合优化（Integrated Production and Delivery Problem，简称IPDP）成果，将拣选视为生产环节，研究时间窗约束下需求可拆分的拣选与配送联合优化问题（Integrated Optimization of Picking and Spilt Delivery Problem under Time Windows，简称IOPSDPTW）。2005年Chen等[1-3]提出了IPDP问题，并于2010年构建了该问题的通用模型[1-3]，接着越来越多的学者进行了深入的研究，目前国内外对IPDP的研究有以下特点：从确定性环境[7]转向不确定环境的研究[8]；从一般行业的联合优化转向研究新兴行业的联合优化[9]；配送阶段从简单的VRP问题转向CVRP[10]、VRPTW[11]等复杂VRP问题的研究；生产阶段从单机转向并行机的联合优化[12]。

目前对于IPDP的研究较为丰富，但对于拣选与配送联合优化问题（Integrated Order Picking and Delivery Scheduling，IOPDS）的研究较少。Su等[10]首次研究了带车辆容量约束的单车辆IOPDS问题及其分阶段算法，根据任意两个配送批次之间有无等待时间调整，但并未研究拣选分批问题；而王旭坪等[13]第一次详细研究了单车辆IOPDS及其三阶段算法，论述了IOPDS问题的不同，根据配送时间调整拣选顺序，但仅仅基于拣选通道相似度进行分批；Zhang等[14,15]研究了基于通道相似度与时间紧急度的混合分批规则。还有一部分学者主要从配送阶段进行深入探讨，Schubert等[16]证明了与非联合优化相比，带截止时间、时间窗等复杂VRP的IOPDS问题及其分阶段禁忌搜索算法平均减少了37.8%的配送延迟时间。

综上所述，IOPDS的研究大多是从订单分批和配送路径两方面进行单独的深入研究，文献[14,15]研究了混合分批规则，但配送阶段为单车辆TSP问题，文献[16]研究拣选阶段为单一员工订单分批和批次排序问题。此外，目前的研究主要采用S-Shape拣选策略和分阶段算法，尚未考虑拣选截止时间和需求可拆分。因此，本文针对以上不足，考虑增加拆分需求成本，拣选阶段采用分区组合拣选策略提高拣选效率[17]，提出了IOPSDPTW，并设计两阶段算法求解，对IOPDS进行进一步拓展研究。

1 研究问题与模型

1.1 问题描述

图1 IOPSDPTW流程图

订单配送阶段解决时间窗约束下需求可拆分的车辆路径问题（Spilt Delivery Vehicle Routing Problem，SDVRP），保证所有需求得到满足，且车辆在仓库装货，完成配送后返回仓库；在订单拣选阶段，结合订单PDD构建订单处理规则，解决并行分区系统下订单分批和批次排序问题（Order Batching and Batch Sequencing Problem under Synchronized Zone Order Picking System，OBBSPSZOPS），相关符号说明如下：

决策变量：

1.2 目标函数

该模型目标是由拣选成本、拆分需求成本、配送成本和惩罚成本四部分组成的订单履行成本最小化，即：

图2 拣选距离计算示意

通道拣选距离计算如下：

配送成本包括车辆路径成本和车辆调度成本，即：

综上，订单履行的总成本为：

1.3 约束条件

（1）拆分需求约束

本文考虑需求拆分拣选和配送，但订单不可拆分，即：

（2）容量约束

在实际情况中，配送车辆和拣选装置有容量约束，即：

（3）拣选约束

②批次拣选顺序与时间约束。两个批次之间拣选顺序唯一，拣选人员必须拣选完上一批次才能继续拣选下一批次，即：

（4）配送约束

① 节点被访问数量约束。每一条路径均从配送中心出发再返回配送中心，所有需求都要被满足，即：

②路径配送流量约束。配送遵循能量守恒定律，即：

③路径分配和所属区域的约束。每一条配送路径都要分配相应的车辆进行配送，即：

④配送顺序约束。路径上两个需求点之间的配送顺序唯一，即：

⑤局部子回路约束。配送路径不能出现局部子回路，即：

（5）变量取值约束

2 算法设计

文献[13]证明了拣选与配送联合优化问题是NP-hard问题，而本文是考虑时间窗和需求可拆分的IOPDS问题，是对IOPDS问题的进一步研究与深入，无法用精确算法求解。现有研究中，文献[11]采用了S-AGA和AGA-2OPT算法求解IPDP问题，文献[14-15]基于遗传算法和聚类算法求解IOPDS问题。IOPSDPTW问题的拣选和配送两个环节相互制约，共同影响需求被服务的时刻，因此两阶段需统筹优化，本文设计两阶段算法求解该问题，配送阶段采用遗传算法，拣选阶段采用订单操作算法，两个阶段通过遗传算法的适应度函数连接成一个整体，即在适应度函数计算时调用订单操作算法求解最优的订单分批和批次顺序，从而使得拣选成本最低。

2.1 遗传算法

step2 初始种群生成。初始种群要满足可行性、随机性和高质量性三个条件，据此，首先需要确定较好质量的解在种群中所占比例，在比例内采用最邻近插入法生成初始种群，比例外采用随机插入法生成初始种群。

step4 遗传算子设计。遗传算子包括选择、交叉、变异和拆分可行化算子，选择操作采用精英选择策略，其他算子设计如下：

① 交叉。随机生成小于1的两个数1和2作为交叉点，由于SDVRP存在过度拆分不可行解，交叉点之间的子串需要整体取出，因此取出两条父代染色体1、2交叉点之间的完整化子串middle1和middle2后，再按顺序将其他节点从左至右填充，具体如图3所示，其中深色代表交叉点子串，浅色代表完整化子串。

图3 改进后的遗传算子操作示意图

②变异。在交叉完成后，采用固定概率进行变异操作，随机生成小于1两个数1和2作为变异位，对位于变异点之间的完整化子串进行逆序操作，具体操作如图3所示。

step5设置最大迭代次数1 000为进化终止条件。

2.2 订单操作算法

订单分批完成后，需要对各个拣选批次的先后顺序进行调整，本文考虑按批次订单的车辆离开时间和包装难度进行批次拣选顺序的调整，即车辆离开时间越早、包装难度越大的批次拣选顺序越靠前，最后将批次订单分配给各个分区的人员拣选。

图4 订单分批流程图

2.3 对比算法

本文的对比方案为组合拣选策略下需求不拆分的拣选与配送联合优化问题（Integrated Optimization of Picking and Delivery Problem under Time Windows and Combined Strategy, IOPDPTW- C）、S-Shape拣选策略下需求可拆分的拣选与配送联合优化问题（Integrated Optimization of Picking and Spilt Delivery Problem under Time Windows and S-Shape Strategy, IOPSDPTW-S）、顺序决策算法（Sequential Decision Algorithm）求解IOPSDPTW（SDA-IOPSDPTW），三种方案与IOPSDPTW相比不同的是IOPDPTW-C配送阶段考虑需求一次性全部配送完成，拣选阶段与IOPSDPTW一致，配送阶段的模型和算法参考侯玉梅等[19]提出的软时间窗整车物流配送路径优化模型和算法；IOPSDPTW-S考虑拣选阶段采用S-Shape策略进行拣选，S-Shape策略批次拣选距离计算参考张珺[20]提出的方法；而SDA-IOPSDPTW则是采用顺序决策算法求解IOPSDPTW问题，其中顺序决策算法主要流程为：

step1 订单分批。不考虑订单所属车辆的离开时间，直接建立拣选通道相似度指标，采用种子算法进行订单分批，不对批次的拣选顺序进行调整；

step2 路径优化。不考虑拣选对车辆离开配送中心时间的调整，对SDVRP问题进行求解，以最小化配送成本为目标优化配送路径；

step3 整合step1和step2的解。

3 仿真实验

3.1 参数设计

3.2 结果分析

算法迭代到598次已经收敛到最优解，收敛较快，算法收敛情况如图5，实例配送路径如图6，从路径图可以看出，需求点3、5、11的客户需求拆分到两辆车进行配送。

图5 目标函数值随迭代次数的变化情况

图6 车辆的配送路径

为了验证拆分需求是否可以降低总成本，将IOPSDPTW与IOPDPTW-C各项成本进行对比分析，具体数据如表1所示，从表中看出，IOPSDPTW总成本为341.311 3元，低于IOPDPTW-C总成本512.688元，优化率为33.43%。

表1 各方案成本对比

Tab.1 Cost comparison of programs

从成本组成来看，IOPSDPTW增加了拆分需求成本，同时拣选成本上升，这是由于与IOPDPTW-C相比，车辆订单在仓库内分布更分散。但是在IOPSDPTW问题中，拆分需求成本和拣选成本在总成本中占比仅为12.1%和12.6%，两个成本对总成本的影响相对较小。

与IOPDPTW-C相比，拆分需求后惩罚成本下降了70.64%，这是由于一个需求点对应多个时间窗，IOPDPTW-C使得车辆到达一个需求点后会产生多个节点的时间窗惩罚成本，而IOPSDPTW使得不同的车辆可以在需求点相对应的时间窗内到达，从而降低需求点惩罚成本。

本文采用组合策略，表2为IOPSDPTW和IOPSDPTW-S的订单拣选时间，从表1和表2中可以看出，采用组合策略和S-Shape策略四辆车的订单拣选时间分别为0.2332、0.3536、0.4796、0.5860和0.3288、0.4766、0.6262、0.7575，采用组合策略缩短了每一配送批次的拣选时间，降低了拣选成本，优化率为24.52%。

表2 各方案拣选时间对比

Tab.2 Picking time of programs

为更好地分析本文研究问题和算法效果，将本文提出算法与该问题采用顺序决策算法的各项成本进行对比，具体数据如表1所示，从表中可以看出，与顺序决策算法相比，两阶段算法优化了28.17%的总成本。

基于两阶段算法的拣选批次数量为16，同样基于顺序决策算法将订单划分为16个拣选批次，两阶段算法与顺序决策算法的拣选时间如表2所示。从表中可看出对于IOPSDPTW问题，两阶段算法和顺序决策算法的拣选成本分别为41.31元和41.625元，优化率为0.76%。

与顺序决策算法相比，两阶段算法计算出的拆分需求成本为72.98元，优化率为40.9%；配送成本为194.1431元，优化率为18.12%；惩罚成本为123.433元，优化率为49.18%。其中惩罚成本的优化率达到了49.18%，这是因为两阶段算法按拣选截止时间分批和调整批次拣选顺序以后，使得配送车辆在时间窗内到达的节点增多，数据如表3所示。

表3 各方案偏离时间窗程度表

Tab.3 Time window deviation of programs

4 结 论

本文第一次提出了时间窗约束下需求可拆分的拣选与配送联合优化问题，结合拣选截止时间、时间窗、车辆容量约束等建立了数学模型，并设计两阶段算法求解，以IOPDPTW-C、IOPSDPTW-S和SDA-IOPSDPTW作为对比应用场景，结果表明，拆分需求后将需求点按不同时间窗配送，增加了拆分需求成本，但惩罚成本减少了70.64%，总成本下降了33.43%；而采用分区组合策略拣选，与全区域S-Shape拣选策略下的IOPSDPTW相比，拣选成本减少了24.52%，总成本减少了12.3%；此外本文提出的算法与顺序决策算法相比，总成本节约了28.17%，证明本文研究的IOPSDPTW问题和算法对物流企业运作具有重大意义。DNA本文仅研究了需求量已知的情况，现在随着信息技术发展，实时订单系统下的IOPSDPTW有待进一步研究。

[1] CHEN Z L, Vairaktarakis G L. Integrated scheduling of production and distribution operations[J]. Management Science, 2005, 51(4): 614-628.

[2] CHEN Zhi-Long. Integrated production and outbound distribution scheduling: review and extensions[J]. Operation Research, 2010, 58(1): 130-148.

[3] CHANG Y C, LI V C, CHIANG C J. An ant colony optimization heuristic for an integrated production and distribution scheduling problem [J]. Engineering Optimization, 2014, 46(4): 503-520.

[4] WANG X, GOLDEN B, WASIL E, et al. The min–max split delivery multi-depot vehicle routing problem with minimum service time requirement[J]. Computers & Operations Research, 2016, 71: 110-126.

[5] 符卓, 刘文, 邱萌. 带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索算法[J]. 中国管理科学, 2017, 25(5): 78-86.

[6] 郭海湘, 潘雯雯, 周欣然, 等. 基于单车场多车型车辆路径问题的混合求解算法[J]. 系统管理学报, 2017(5): 824-834.

[7] 马士华, 王青青. 同步物流系统下准时化生产与配送调度问题研究[J]. 中国管理科学, 2012, 20(6): 125-132.

[8] 方伯芃, 孙林夫. 不确定环境下的产业链生产与配送协同调度优化[J]. 计算机集成制造系统, 2018, 24(1): 224-244.

[9] MARANDI F, ZEGORDI S H. Integrated production and distribution scheduling for perishable products[J]. Scientia Iranica, 2017, 24(4): 2105-2118.

[10] GAO S, QI L, LEI L. Integrated batch production and distribution scheduling with limited vehicle capacity[J]. International Journal of Production Economics, 2015, 160: 13-25.

[11] LOW C, CHANG C M, GAO B Y. Integration of production scheduling and delivery in two echelon supply chain[J]. International Journal of Systems Science Operations & Logistics, 2015, 4(2): 122-134.

[12] BELO-FILHO M A F, AMORIM P, ALMADA-LOBO B. An adaptive large neighbourhood search for the operational integrated production and distribution problem of perishable products[J]. International Journal of Production Research, 2015, 53(20): 6040-6058.

[13] 王旭坪, 张珺, 易彩玉. B2C电子商务环境下订单拣选与配送联合调度优化[J]. 中国管理科学, 2016, 24(7): 101-109.

[14] ZHANG J, WANG X, HUANG K. On-line scheduling of order picking and delivery with multiple zones and limited vehicle capacity[J]. Omega, 2017.

[15] ZHANG J, WANG X, HUANG K. Integrated on-line scheduling of order batching and delivery under B2C e-commerce[J]. Computers & Industrial Engineering, 2016, 94(C): 280-289.

[16] SCHUBERT D, SCHOLZ A, WÄSCHER G. Integrated order picking and vehicle routing with due dates[J]. Or Spectrum, 2018: 1-31.

[17] 王旭坪, 张珺, 易彩玉. 电子商务人工并行分区拣选系统服务效率优化研究[J]. 管理工程学报, 2017, 31(2): 209-215.

[18] ELSAYED E A, STERN R G. Computerized algorithms for order processing in automated warehousing systems[J]. International Journal of Production Research, 1983, 21(4): 579-586.

[19] 侯玉梅, 贾震环, 田歆, 等. 带软时间窗整车物流配送路径优化研究[J]. 系统工程学报, 2015, 30(2): 240-250.

[20] 张珺. B2C电子商务订单分批拣选与配送联合调度[D]. 大连: 大连理工大学, 2017.

Integrated Optimization of Picking and Split Delivery Problem under Time Windows

XU Ling1,2，HU Xiao-lin1，HU Xiao-liang1

(1. School of Transportation and Logistic, Southwest Jiaotong University, Chengdu 611756, China; 2. National United Engineering laboratory of Intergrated and Intelligent Transportation, Chengdu 611756, China)

In view of the problem of low order fulfillment efficiency that enterprises need to solve urgently, an integrated optimization of picking and delivery model is established based on the idea of split delivery, considering the time window and the characteristics of combined picking strategies. The order fulfillment efficiency is reflected by picking cost, split delivery cost, distribution cost, and time penalty cost. We calculated the optimization using split demand, combination strategy, and an algorithm for the model. A two-phase heuristic algorithm was used to solve the model. Subsequently, the effectiveness of the model and the algorithm were verified using an example. Finally, compared with the non-split delivery, the S-shapestrategy, and the sequential decision algorithm, the total cost decreased by 33.43%, 12.3%, and 28.17% respectively. The results show that the model and algorithm established in this study can effectively improve the order response speed and reduce the order fulfillment cost.

integrated optimization; combination strategy; spilt delivery; time window; two-phase heuristic algorithm

1672-4747（2020）02-0018-12

N945.12

A

10.3969/j.issn.1672-4747.2020.02.003

2019-07-08

铁路总公司科技研究开发计划项目（2013X009-A-1-2）；四川省重点科技计划项目（2014GZ0019）

徐菱（1965—），女，四川成都人，教授，博士生导师，研究方向：物流系统规划与设计等，E-mail：xlhu173@163.com

徐菱，胡小林，胡小亮. 时间窗约束下需求可拆分的拣选与配送联合优化问题研究[J]. 交通运输工程与信息学报, 2020, 18（2）：18-29.

（责任编辑：刘娉婷）