基于订单拆分的线上到线下连锁门店配送优化模型

辛禹辰，施胜男，杨华龙

(大连海事大学交通运输工程学院，辽宁大连116026)

0 引 言

为应对电商的迅猛冲击，零售企业实施O2O(Online To Offline)转型策略，即将线下商务机会与互联网结合，互联网成为线下交易的前台，利用连锁门店(简称门店)向客户配送商品[1].客户订单存在差异性，每个客户对不同商品有不同的需求量；各门店的库存容量及其所拥有商品种类也存在差异，故会出现一家门店无法单独满足一个客户订单需求的情况.因此，研究基于拆单的O2O多家门店共同配送问题具有重要的现实意义.

O2O门店配送涉及线上订单分配和线下物流配送两方面.线上订单分配问题，已有研究很少考虑商品区分，针对客户只含一种商品订单的分配问题.Wang 等[2]针对电商与OTO 包裹集成配送优化问题，构建了混合整数规划模型，并设计适合大规模问题的混合邻域搜索策略.有关多种商品的订单分配问题研究较少，文献[3]针对快餐企业O2O 订单分配中一单多品情况，提出每份快餐订单只能分配到一家门店的订单分配模型，即在考虑订单不拆分的情形下进行订单分配.针对O2O背景下，线下物流配送主要研究一家门店向客户配送问题.Zhang 等[4]研究了考虑拣选员学习效果的OTO 订单拣选和配送优化问题，在一家社区超市对在线订单进行综合拣选和配送；陈萍等[5]基于传统的取送货车辆路径问题，提出适合一家餐饮企业O2O 外卖配送的优化模型，缺乏多家连锁门店共同配送问题的研究.

上述研究是针对O2O订单分配和门店配送孤立的局部优化，容易出现商品不能及时送达、履约率低下等问题.此外，一单多品O2O 订单中，会出现订单中的多种商品不能由一个门店满足的情况，需要考虑将订单拆分.现有关于一单多品O2O订单拆分问题的研究主要是配送中心发货的情形.张凯源[6]等针对网上超市一单多品订单拆分问题，根据商品种类在配送中心对订单进行拆分；韩曙光等[7]研究电商一单多品订单拆分及配送，在配送中心对订单进行拆分.订单不拆分或只在配送中心进行拆分的研究不适合OTO 背景下，线上订单门店分配及发货的实际需要.

因此，本文针对O2O 背景下零售企业门店一单多品订单分配及配送问题，考虑各门店库存容量限制，以及可能存在回收客户商品退回的实际情况，提出客户订单仅按商品类别拆分，从多家门店分别配送各类商品的策略，构建基于订单拆分的O2O 门店配送优化模型，以期为零售企业顺利实施O2O转型策略提供科学参考.

1 基于拆单的O2O门店配送优化模型

1.1 问题描述及假设

一家零售企业在较小区域(如城区)内拥有多家门店，一段时期内线上平台共接收N个客户订单.对于每一个订单，企业可根据客户地理位置、需求商品种类和数量，将订单分配至门店，若该门店关于订单中的某种(或某几种)商品缺货，则需要将订单拆分，将缺货商品组成的新订单分配给其他门店.以此类推，直至该客户订单中商品完成配送为止.O2O背景下每位客户(普通消费者)订单数量通常较少，故假设每家获得配送任务的门店可将某种(或某几种)商品作为一个包裹配送给客户.在规定的时间窗内，每辆车可以服务多个客户，每个客户能被多辆车服务.若车辆早于或晚于客户要求的时间窗到达，需要承担相应的惩罚成本.基于拆单的O2O 门店配送优化问题，是如何将线上平台接收到的订单分配至一个或多个门店，并设计各门店到客户间物流总费用最小的配送路径.

为便于建模，给出以下假设：

(1)单家门店某种产品可以缺货，全部门店不可缺货；

(2)只允许按商品种类进行订单拆分，不对数量进行拆分；

(3)门店把配送给同一个客户的商品打包成一个包裹.

1.2 模型建立

符号说明如下：

Δ={1 ,2,…,m,…,M} ——门店集合，其中，m表示门店序号，M表示门店总数；

Ω={M+1,M+2,…,M+N}——配送客户集合，其中，N表示客户总数；

Γm={1 ,2,…,k,…,Km} ——门店m配送车辆集合，Γm={1 ,2,…,Km} ，其中，k表示车辆序号，Km表示门店m拥有的车辆总数；

Φ={1 ,2,…,r,…,R} ——商品种类集合，其中，r表示商品种类序号，R表示商品种类总数；

U——车辆最大装载量；

V——车辆行驶速度；

Wmr——门店m中商品r的库存量；

F——车辆的固定成本；

G——车辆单位距离行驶成本；

Dir——客户i对商品r的需求量；

Lij——门店(或客户)i到门店(或客户)j的距离，i,j∈Ω,i≠j；

δj——客户j的时间偏离惩罚；

Ej——客户j的最早服务时间；

Lj——客户j的最迟服务时间；

——0-1变量，若由门店m出发的车辆k由客户i到j，则取1，否则，取0，i≠j；

——0-1 变量，若由门店m出发的车辆k为客户i配送商品r，则取1，否则，取0；

——车辆k由门店m出发到达客户j的时间；

——门店m利用车辆k为客户i配送商品r的数量.

构建O2O门店配送优化模型为

目标函数：式(1)表示物流配送总费用最小，第1 项为配送车辆的固定费用，第2 项为配送车辆的运输费用，第3 项为时间惩罚成本.约束条件：式(2)表示每个客户每种商品的配送需求只能由一家门店和一台配送车辆完成，式(3)表示每个客户的每种商品配送需求均要得到满足，式(4)表示门店配送的任一种商品总量均不超过该门店的库存，即门店库存量应满足其配送客户的需求量，式(5)表示门店配送车辆数量约束，式(6)表示车辆从门店出发成功配送任务后返回门店，式(7)表示配送车辆不能从一家门店到另一家门店，式(8)表示从每家门店出发的每台配送车辆至多为客户配送一次，式(9)表示配送车辆从门店出发时装载配送商品数量不能超过其装载量限制，式(10)表示配送车辆到达客户的时间，式(11)表示客户配送时间偏离惩罚费用取值.

2 求解算法设计

订单分配和配送相结合的O2O门店配送优化模型，实质上是对带时间窗的多车场车辆路径问题的扩展，是NP难题.借鉴文献[8]，设计先拆单分配，后配送路径优化的两阶段启发式算法.首先，基于所有门店和客户间的距离，进行订单就近拆单分配，大幅降低计算复杂性；然后，设计改进的禁忌搜索算法对配送路径进行优化.

2.1 线上订单就近拆单分配

订单就近拆单分配算法是按商品种类(而非按数量)进行客户订单拆分，通过判断某门店是否拥有某客户需求的某种商品，判断订单是否需要拆分.在此基础上，计算各客户与各门店间的距离，按就近原则进行订单分配.具体步骤如下：

Step 1计算各客户点与各门店之间的距离.

Step 2对客户需求的每一种商品分别进行分配.将客户到各门店间的距离按升序排列，判断距离客户最近的门店是否能满足客户的某种商品需求.如果是，则该客户的该种商品由最近的门店进行配送服务；如果否，则转Step 3.

Step 3除去已判断过的门店，继续判断剩余门店中距离其最近的门店是否能满足该客户的某种商品需求.如果是，则将该客户的该种商品由该门店进行配送服务；如果否，则继续Step 3.

Step 4输出各客户的订单分配结果.

2.2 改进的禁忌搜索算法

结合问题模型特点，在邻域结构产生方面对禁忌搜索算法加以改进，设计搜素速度更快的改进禁忌搜索算法.具体步骤如下：

Step 1解的表示及初始解的生成.对节点进行编号，0表示门店，如某条线路为0-4-8-10-0，表示客户点4、8、10 由此线路配送.每条线路均从0 开始，经过数个客户点，最终以0结束.说明车辆从门店出发，最终返回门店.采用随机方式生成初始解.

Step 2邻域结构.采用交换算子、插入算子及2-opt 交换算子3 种算子构成的混合邻域变换.交换算子是将解的排列中任意两个客户点的位置进行交换，插入算子是将排列中一个客户点插入到第一位置或某个客户点之后，2-opt 交换算子是把两个客户点之间的所有客户点路径顺序翻转[9].在算法搜索过程中可以随机地从3 种算子中选择一种，以改变固定的搜索顺序.

Step 3禁忌表.将每次迭代得到的最优解作为禁忌对象放入禁忌表中，取禁忌长度为一个常数.

Step 4候选集合的确定.从当前解的邻域中随机选择若干个邻居作为候选集合.

Step 5终止准则的确定.采用迭代指定步数的终止准则.

3 算例分析

假设某O2O零售企业有6家门店，网上接到54位客户的订单(坐标点均选自标准算例库R111 的前60个坐标点，其中，每隔9个选一个为门店，剩余的为客户点)，该企业共有100种商品.随机生成各门店商品库存.门店库存变化难以度量且门店库存对订单分配影响较大，对6家门店各种商品的总库存进行假设；门店除为线上客户订单服务外，还要为到店选购商品的客户服务；此外，门店还需保留一部分库存以备不时之需.因此，门店库存由这3部分组成，线下客户难以预测及保留库存不定，假设6 家门店各种商品的总库存均为线上所有客户订单各种商品总需求的3 倍.首先，随机产生每位客户订单商品的需求信息，商品种类数服从区间为[1,10] 的均匀分布，每种商品购买数服从区间为[1,3] 的均匀分布.然后，运用均匀分布在区间为[1,100] ，随机生成各门店库存商品种类，汇总每种商品r的所有客户需求数量并乘以3(倍)作为该商品的总库存量Wr；根据各门店随机生成库存商品种类情况，在含有商品的门店中，运用伪随机数发生器，依此总库存量Wr生成各门店含有商品r的库存数量.车辆固定成本为50元/车次，可变成本为0.7元/km，载重限制为20件包裹，平均行驶速度为60 km/h，早到惩罚系数为1，晚到惩罚系数为3.5.

使用本文方法和文献[3](订单不拆分)方法运行算例，订单分配结果分别如图1 和图2 所示，其中，编号D1～D6为门店，编号1～54为客户.

图1 本文方法订单分配Fig.1 Order allocation by this paper

图2 订单不可拆分下订单分配Fig.2 Order distribution without order split

对比图1 和图2 可以看出，在相同情况下，本文方法能完成所有订单的配送；订单不可拆分时，造成26 位客户的订单不能及时配送，约占总客户数的48.15%.

门店库存数量对客户订单履约率产生很大影响.令各门店商品总库存量为客户订单总需求量(例如本文随机生成量为596)的1～7 倍，进行敏感性分析，在订单可拆分的情况下，门店能够完成全部客户订单的配送任务，配送总费用的敏感性分析如图3所示.

图3 配送总费用敏感性分析结果Fig.3 Sensitivity analysis results of total distribution cost

由图3 可以看出，随各门店商品总库存量的增加，配送总费用不断下降，但门店库存量从客户订单需求量的1 倍增加到7 倍时，配送总费用从1 973.56 元下降至1 092.68 元(下降了44.63%)，配送费用并未随之成倍下降.这是因为门店商品库存量增加，可以减少客户订单拆单，配送距离减少，配送费用下降，但库存与配送成本间存在效应背反规律.因此，零售企业需要权衡门店线下和线上需求与库存关系，结合门店库存容量，保持合理的商品库存规模.

订单不可拆分时，未履约订单数及其比率敏感性分析如图4所示.

图4 未履约订单敏感性分析结果Fig.4 Sensitivity analysis results of unfulfilled order

由图4 可以看出，随门店总库存量升高，未能服务的客户数及其比率随之降低，但仍有部分客户未能得到服务.如门店商品总库存量为客户订单总需求量7倍时，仍然有10位客户(约占18.52%)的订单未能得到及时配送.而按本文方法，只要各门店商品总库存量大于等于客户订单总需求量，客户订单及时配送履约率便可达到100%.因此，对客户订单进行拆分处理是非常必要的，能够有效地提高客户订单及时配送履约率.

4 结 论

本文针对O2O背景下订单分配与配送问题进行联合优化.与不拆单方法相比，按照商品种类(不按数量)进行拆单，客户订单中某一种类的商品只能由一家门店配送，不仅便于管理客户退货，还能提高客户订单的及时配送履约率.研究表明，在O2O 背景下，对客户订单按商品种类进行拆分处理必要且有效；电商零售企业需要保持各门店合理的商品库存规模，以满足客户线下和线上O2O订单的需求.