考虑电商超市多仓多品类订单拆分与整合的车辆路径优化

孙一凡，高更君

（上海海事大学 物流研究中心，上海 201306）

0 引言

2021年双11电商产业实现稳健增长，折射出消费活力和经济韧性。国家邮政局检测数据显示，全国邮政、快递企业11月11日当天共处理快件6.96亿件，再创历史新高，未来订单量的增长是常态化的。电商超市布局多仓存储货物可服务区域更广，但客户订单的差异化以及收货时间、服务次数的限制使得电商订单配送的研究受到广泛关注，如何有效减少物流成本，提高客户服务水平是本文的优化目标。

林昌辉[1]针对电商企业在配送订单时面临的订单拆分需求，提出考虑订单拆分的多仓库车辆路径优化问题，以最小化配送距离为目标，同时决策订单的分配和车辆路径的规划。喻锐[2]设计医药物流多仓联动的双层配送模式，将区域内车辆调度问题与物流中心库存问题相结合，实现多仓联动模式的创新。刘鹏程[3]针对多中心集货需求随机的同时配集货车辆路径问题展开研究，构建了两阶段优化模型。范厚明等[4]研究多中心开放式同时配集货需求可拆分车辆路径问题，建立以车辆派遣成本、理货成本以及运输成本之和最小为目标的车辆路径优化模型，设计混合遗传算法进行求解，研究成果拓展了车辆路径问题的相关理论。Imen Harbaoui Dridi等[5]研究多车、多仓库、带时间窗口的提货和交货问题，满足客户和供应商之间的运输要求，优先级、容量和时间限制，找到最小化总旅行距离的最佳路线。盛虎宜[6]综合考虑区域内多配送中心、客户居住地较分散、同时具有集货和送货双重需求、集货量与需求量都比较小等因素，以总配送费用最少为目标构建农村电商基于共同配送策略的集送货一体化车辆路径问题数学模型。WANG Yong等[7]提出基于时间窗分配的多中心协同取货配送问题，并将其化为两阶段优化问题进行求解，通过时间窗口分配策略，将一组候选时间窗口分配给相应的客户，以提高物流网络的运行效率，目标为最小化车辆数量和总运行成本。符卓等[8]综合考虑客户需求依订单拆分和客户有被服务时间的要求，研究带软时间窗的需求依订单拆分车辆路径问题。李寒梅[9]结合企业实践提出同时具有多品种运输物品、多车场、多时间窗、需求可拆分集送货车辆路径问题。张维智[10]考虑车辆装载量、运行距离限制、网点服务时间限制对同时取送货车辆路径的影响，构建以系统总成本最小为优化目标包括调用成本、运行成本、装卸成本及时间窗偏离惩罚成本的同时取送货车辆路径优化模型。章园园[11]通过分析电子商务订单的特点，针对“一地多仓”型自营电子商务平台的订单拆分与分配进行研究，提出以提高客户满意度、降低履约成本为目标的新拆单原则，并将订单拆分与配送相结合，在保证客户满意度的情况下最小化订单履约成本。杨明星[12]分析电子商务环境下在线零售商客户订单的特点，研究“一地多仓”模式下在线零售商的订单拆分及在各仓库间的分配问题，考虑品类拆单与数量拆单同时存在的情形，最小化总配送成本，构建以“最小拆单数”作为订单拆分规则的在线零售商订单分配与车辆路径的联合优化模型。ZHU Shan等[13]提出了一种基于多商品订单配送的启发式k链接聚类算法来优化多仓库之间的产品类别分配，以最小化订单拆分的总次数，减少多商品的客户订单因需要分成多个发货导致的更高的运输成本。郭琼[14]针对网上超市的高拆单率问题，提出利用多供应商间的横向转运策略，以最小化订单履行总成本为目标，将拆分订单合并运输优化问题分为完全合并和部分合并两种方式，可针对客户的需求选取适合的拆分订单合并优化方法。ZHANG Yuankai等[15]讨论在线零售最后一英里配送中出现的多个货物被多次交付给同一客户问题，提出一种订单合并方法，将相同客户的货物在派送站合并，以更少的配送距离完成配送。建立一个在分装和合并货物之间进行成本权衡的整数规划模型。黄敏芳等[16]以减少大型网上超市拆分子订单的包裹在分拨中心的合并成本为目标，针对多分拨中心之间通过循环发车对拆分订单子包裹进行横向转载与合并这一作业流程，建立了大型网上超市拆分子订单的包裹合并配送的优化模型，提出采用分段整数编码的遗传算法优化订单合并次序。

目前电商配送研究多为车辆路径优化、车辆调度方面的研究，使得货物配送在便捷性、实用性和经济性方面有了质的飞跃，更好的满足客户的个性化需求，但仅研究订单的拆分或者整合，仅考虑配送没有考虑车辆回程等环节对成本的影响。本课题从客户下订单开始，按照仓库库存拆分订单，通过设置转运仓库整合订单等一系列物流活动的闭环服务，从而在提高客户服务质量的前提下降低物流配送成本。

1 模型构建

1.1 问题描述

电商超市在一个地区设置多个品类仓，由于商品具有互斥性，仓库内存放多种商品，商品种类有差异且有部分重合；每个仓库有多辆车，保证每个仓库车辆进出平衡。考虑距离、包裹数、客户及仓库的时间窗选择转运仓库，通过横向转运的方式集齐订单所需商品后访问客户一次；转运或配送任务完成后，车辆就近返回仓库，通过转运、储存、配送、车辆回程等物流活动过程中的成本，研究多仓多品类订单先拆分后整合的车辆路径优化问题如图1所示，确定合适的订单分配和客户服务方案，提高电商订单整体处理效率。

图1 多仓多品类订单先拆分后整合的车辆路径优化问题图

1.2 假设条件

作出假设如下：

1）电商超市在一个区域的多个仓库为分类仓，即每个仓库所储存商品种类有重合；

2）满足每个客户点的需求，且只能被服务一次，每个客户的送货需求量都小于车辆最大载容量限制；

3）每个仓库有充足的同类型的配送车辆，车辆完成配送任务后，按照就近原则返回任一仓库，且每个仓库的车辆进出平衡；

4）卡车以平均速度行驶，车辆成本与单位运行成本有关；

5）仓库装货成本、客户点卸货成本与包裹数有关，含在包裹的配送成本中；

6）客户、仓库对配送服务有期望接收服务的时间窗；

7）不宜混装货物在多仓库分开存储，配送时可在卡车混装。

1.3 符号说明

符号说明如表1所示。

表1 符号说明表

1.4 建立模型

根据本文提出的多仓多品类订单先拆分后整合的车辆路径优化问题，以成本作为目标函数，构建模型如下：

其中，式(1)按客户所购种类划分客户归属仓库；式(2)表示该地区的仓库备货充足，不存在缺货情况；目标函数式(3)为总成本最小化，总成本包括转运成本，储存成本，车辆单位运行成本及与包裹数有关的配送成本，客户及仓库的时间惩罚成本，客户到仓库的空车分配成本、转运仓库到仓库的空车分配成本；式(4)某配送车辆k在客户点i的时间惩罚成本；式(5)某配送车辆k在仓库n的时间惩罚成本；式(6)计算车辆到达客户点i的时间；式(7)计算车辆到达仓库n的时间；式(8)表示当车辆到达客户点i的时间点比规定的时间窗口稍早时，需要等待一会；式(9)表示当车辆到达仓库n的时间点比规定的时间窗口稍早时，需要等待一会；式(10)表示从第1个仓库开始装货的初始时间设为零；式(11)保证每个客户点由一辆车提供服务；式(12)表示每个节点流入的车辆数和流出的车辆数相等；式(13)表示节点自己内部流量为零；式(14)表示某卡车从某仓库出发时，所载货物量等于该仓库服务客户点的送货量之和；式(15)指从仓库出发的车辆上的货物不能大于最大车载能力；式(16)表示车辆从转运仓库出发，并且回到任一仓库；式(17)表示当仓库n中含有客户i中的某种商品时，该仓库与该客户才有可能匹配；式(18)表示客户i备选仓库中商品r的数量需满足订单需求；式(19)表示每一个订单至少被一个仓库满足，即必须被匹配完成；式(20)表示一个订单在一个转运仓库合并；式(21)表示订单合并完成时间取决于转运时间最长的子订单的转运时间；式(22)表示客户i的订单分配在j仓库开始转运的时间；式(23)表示仓库的库存量不能超过仓库最大容量；式(24)表示所有订单开始转运的时间一致。

2 遗传算法

2.1 算法选择及概述

遗传算法是一种基于生物进化的启发式搜索算法，遗传算法构造的问题初始解不是单个解，在同一时间一起处理种群中的多个个体，因此迭代过程中不易陷入局部最优解；适应度函数是遗传算法进行个体评判的唯一标准，不需要额外辅助信息；搜素方向上没有确定的规则，根据进化过程中获得的信息直接组织搜索，更容易快速收敛于最优解。

2.2 遗传算法流程

遗传算法求解流程如下：

Step1 染色体编码设计：采用实数编码，每一个GENE都表示一个转运仓库编号，每一条染色体表示一种转运方案，每个个体染色体总长为客户数50。其中，客户数=订单数=基因长度。染色体的结构如下：

Step2 种群初始化：随机产生多组乱序的1～n序列作为遗传算法的初始种群，种群数量设置为300；

Step3 适应度函数：计算转运成本，储存成本，车辆单位运行成本及与包裹数有关的配送成本，客户及仓库的时间惩罚成本，客户到仓库的空车分配成本、转运仓库到仓库的空车分配成本之和，作为适应度函数，适应度函数值越低，个体越优；

Step4 判断迭代次数是否超过最大迭代次数，若是，跳转至step8；若否，则进行下一步；

Step5 选择：采用轮盘赌选择法。对所有个体按适应度函数进行升序排列后取倒数，各个个体被选中的概率与其大小成正比；

Step6 交叉：采用经营保留策略+单点交叉法。保留排序最优的个体染色体，随机选择298个父代染色体进行单点交叉，对应位置的基因进行互换；

Step7 变异：采用随机单点变异法。随机选取两个变异点，交换相应的基因，返回Step3；

Step8 终止条件：迭代1000次，提取种群中最优个体，算法结束。

3 算例分析

3.1 背景描述

假设上海市9个电商仓库给随机选取的50个客户配送商品，将电商订单商品分为以下15类，食品类：1食品酒饮2生鲜食品3医疗保健；电子类：4手机数码5电脑、办公6家电7母婴、玩具、乐器8个护化妆9图书、音像10服饰、鞋帽；高价值类：11钟表、珠宝12礼品箱包13工业品14汽车用品15家具、家装、厨具。品类13、14、15不宜混装货物在多仓库分开存储，配送时可在卡车混装。

3.2 参数设置

假设各仓库、客户点之间道路互通，位置如表2所示，客户需求及仓库、客户时间窗参数如表3所示，仓库商品的库存供应量如表4所示，相关参数如表5所示。

表2 仓库及客户点位置表

表3 客户需求及仓库、客户时间窗参数表

表4 仓库商品的库存供应量表

表4 仓库商品的库存供应量表

表5 相关参数表

结合算例数据得到目标函数如下：

3.3 算例结果

Python运行8min27s，得到50个客户订单对应9个转运仓库，分别为1，2，6，4，7，3，9，8，5，总成本最小为2783.59元。适应度函数与迭代次数图如图2所示。

图2 适应度函数与迭代次数图

转运及配送情况如表6所示。所有仓库均作为转运仓库，仓库6转运商品次数最多为6次，仓库5转运商品次数为5次，仓库3、4、7转运商品次数为3次，仓库1、2、8、9转运商品次数最少为1次；转运仓库1服务客户数最多为14，转运仓库5服务客户数最少为1。

表6 转运及配送情况表

客户所需商品品类转运情况如表7所示。其中，8位客户所需商品全部需要转运，在总客户数中占比16%，70%的客户有一半商品需要转运，2位客户订单的转运率最低为20%。

表7 客户所需商品品类转运情况表

电商超市订单多仓拆分及订单整合的转运、配送过程如图3所示。总转运里程：451.09km，转运仓库总存储时间：205.26h，违反仓库时间：0，违反客户时间：54.32h，客户到仓库空车里程：1025.14km，仓库间转运空车里程：38.92km。

4 结语

电商超市呈现多仓服务一个区域的形式，电商订单以多品类为主，客户需求的差异化制约订单快速响应，及时完成配送。本文建立模型通过转运仓库实现订单的拆分与整合，满足客户一次配送的需求，寻找成本最低的车辆路径。运用算例验证设计的遗传算法能求得最优解。结果表明，依据仓库及客户位置考虑转运、仓库存储成本、车辆回程成本，结合配送包裹数，时间窗等选择物流总成本最低的转运仓库，从而得出配送车辆路径，为电商订单配送问题提供从转运、仓储、配送等多环节整体优化的研究方向。