互联网家装服务中的供应链优化模型

张 巍

(上海交通大学 安泰经济与管理学院 管理科学与工程系，上海 200030)

1 文献综述

库存路径问题研究的是考虑库存和运输的相互影响，在各种约束条件的限制下确定补货策略和配送策略，使得库存和运输的总成本最低[1]。库存路径问题由于整合了库存管理和运输问题，是车辆路由问题的进一步延伸，更具有研究价值。库存路径问题通常不考虑货物的生产制造过程，主要同时解决三个关键问题：何时向客户送货、车辆向客户送多少货物以及车辆的行驶路径规划[2]。

设计启发式算法是目前学者处理库存路径问题的主流研究方向。利用已有的车辆路由问题、经济批量订货模型等研究基础，设计两阶段启发式算法寻找近似解在研究初期被广泛使用。两阶段法的基本思路是先确定车辆向各个客户配送货物的数量，再利用已有的车辆路由问题成果确定车辆行驶路径；另外，也可以先确定车辆行驶路线，再确定给客户的配送量。代颖等[3]考虑了一种多周期的定位库存路径优化问题模型，并设计先定位分配后设计路径的两阶段启发式算法进行求解。Campbell和Savelsbergh[4-5]提出包含时间窗的库存路径优化问题，并利用先客户分区后确定线路的启发式算法进行求解。

由于库存路径问题各规划期内的库存变化具有马尔科夫性，部分文献提出利用马尔科夫决策过程解决库存路径问题。Kelywegf等[6-7]建立了马尔科夫决策过程离散模型用于研究直接送货策略，但计算过程存在求解困难的问题。Adelman[8]引入松弛函数对类似离散模型进行研究。此外，Hvattum等[9]采用决策树方式对库存路径问题进行了近似求解。

利用计算机极强的处理能力，设计元启发式算法求解的文献近年来陆续增加。Liu和Lin[10]在将库存路径问题使用两阶段法拆分后，利用禁忌搜索算法和模拟退火算法对解进行进一步改进。吕飞等[11]针对带软时间窗的选址库存路径备件物流问题，设计了基于禁忌搜索算法和C-W节约算法的混合算法进行求解。Huang等[12]使用改进后的蚁群算法，对需求不确定下的多产品补货调度问题进行求解，获取随机性条件下的配送和补货数量方案。Moin等[13]设计了一个先分配货物后设计行进线路的两阶段遗传算法，引入新的交叉与变异算子和新染色体标识，成功对多周期多产品有装载容量限制的舰队配送网络优化问题进行了求解。

由于具体行业中对搭建供应链模型存在多种实用性或技术可行性限制，针对具体行业的物流系统或供应链库存路由问题的相关文献相对较少，主要集中在原油运输供应[14]、煤炭开发运输[15-16]、天然气海路运输[17]、售后备件物流[11,18]、水泥生产运输[19]、家畜运输屠宰[20]等领域。

2 问题描述及模型

2.1 问题描述

基于前述业务流程，我们可以构造一个以单个仓库为决策中心的供应链优化问题，问题描述如下：

整个供应链模型由一个仓库、多个一级供应商和多个客户组成。供应链的总运营成本包括建材的订货成本、库存成本以及运输成本。订货成本在仓库向供应商发出订单时产生，订货成本与订单的订货数量无关；将建材存储于仓库中会产生库存成本，当建材配送至客户装修现场后不再产生库存成本；卡车配送建材时会产生运输成本，运输成本取决于卡车行驶路径。

仓库作为决策中心，在规划周期内的每个规划日需要确定是否向一级供应商发出订单(若发出订单则需要确定订货数量)、是否向客户配送建材(若配送则需要确定各建材的配送数量)、卡车配送建材的类别数量以及卡车的行驶路径。仓库的决策目标是使前述的总运营成本最低。

整个优化过程周期跨度为T。下达订单的客户共有N位，客户对建材的需求互不相同。装修过程涉及建材M类，分别对应M个一级供应商。建材m有其固定的型号规格，体积为Vm。仓库配送过程可供使用的卡车总数为L，其规格相同。

客户n在签订合同后，装修期间每日所需要的建材数量是确定的，客户n在时间t所需要的建材m数量为dmnt，需求发生在每个规划期的开始。仓库需要将建材及时送到客户处，整个规划过程中不允许缺货。装修现场可容纳的建材总量有限，客户n所能容纳的最大建材体积为Cn。客户n初始建材库存为invmn0=0。

各个供应商负责提供相应的建材。建材m在仓库中的安全库存为Sm，当建材在仓库中的存量即将低于安全库存时，仓库需要向相应供应商发出订单，整个规划周期内任意建材仓库储量不得低于其安全库存。供应商对仓库订单的订货量有要求，建材m单次订单所需要的最低订货量为Qminm。供应商m收到订单后到建材m运至仓库存在前置时间lm。仓库每次向供应商下达订单的订货成本为om。

将建材m置于仓库中会产生库存成本，每单位建材m在一个规划间隔内产生的库存成本为hm，仓库中建材m的初始库存为invm00。

卡车在运输过程中有装载容量限制，能装载的最大建材体积为Ctmax。卡车能够装载多位客户的建材，逐个送到客户施工现场。卡车从地点i运至地点j(i,j为0,1,…,n，其中0代表仓库)所产生的运输成本为cij。建材在每个规划期的开始时送至客户处，没有运输时间。

本研究描述的供应链优化问题与通常库存路径问题的区别在于考虑建材补给情况，此外存储在客户施工现场的建材不会产生库存成本。

2.2 理论模型

根据前述问题描述，我们可以建立一个混合整数线性规划模型进行求解。

s.t.

∀l=1，…，L,n=0，…，N,t=1，…，T

(2)

rliit=0 ∀l=1，…，L,i=0，…，N,t=1，…，T

(3)

∀l=1，…，L,n=1，…，N,t=1，…，T

(4)

∀l=1，…，L,t=1，…，T

(5)

∀l=1，…，L,t=1，…，T

(6)

∀m=1，…，M,t=1，…，lm

(7)

∀m=1，…，M,t=lm+1，…，T

(8)

∀m=1，…，M,n=1，…，N,t=1，…，T

(9)

∀n=1，…，N,t=1，…，T

(10)

invm0t≥Sm∀m=1，…，M,t=1，…，T

(11)

0≤invmnt

∀m=1，…，M,n=1，…，N,t=1，…，T

(12)

xmt≥Qminm·ymt

∀m=1，…，M,t=1，…，T

(13)

xmt≤Z·ymt∀m=1，…，M,t=1，…，T

(14)

模型中决策变量意义如下：

xmtt时刻仓库向供应商m发出的订货数量；

ymt如果t时刻仓库向供应商m发出订单，那么为1，否则为0；

qlmntt时刻卡车l向客户n运送建材m的数量；

rlijt如果t时刻卡车l从地点i驶向地点j，那么为1，否则为0。

方程(1)是混合整数线性规划模型的目标函数，表示该模型的优化目标是使总运营成本最小化。总运营成本由三个求和函数加总构成，分别代表订货成本、库存成本和运输成本。限制条件(2)使得单位卡车在任意规划日内对某个地点的访问次数和离开次数保持一致且最多访问一次；限制条件(3)保证了卡车相邻的两个访问地点不相同；限制条件(4)保证了卡车向客户配送建材的时候其行驶路径通过该客户；限制条件(5)使得卡车在有配送任务时必定从仓库出发；限制条件(6)导入了车辆最大装载体积限制，卡车装载的建材总体积不超过卡车的最大装载体积；限制条件(7)是规划时刻小于建材前置时间时仓库建材数量变化的递归关系；限制条件(8)是规划时刻大于建材前置时间时仓库建材数量变化的递归关系；限制条件(9)是客户施工现场建材数量变化的递归关系；限制条件(10)导入了施工现场的最大建材体积限制，保证了施工现场所堆积的建材总体积不会超过客户施工现场所能容纳的最大体积；限制条件(11)导入了仓库建材的安全库存限制，在任意时刻建材在仓库的存量不会小于其安全库存；限制条件(12)保证了客户施工现场积累的建材能够满足当日的装修需求；限制条件(13)和(14)导入了最小订货量限制，保证了仓库发出的订单数量超过供应商所要求的最低订货数量。

显然，这样建立的混合整数线性规划模型不会存在一个多项式时间算法能够准确地计算出该问题的最优解，需要通过其他途径获得问题的可行解。

3 近似算法

简单的供应链优化问题如经济批量订货问题、最短路径问题均有多项式时间内的最优算法可以求解，但是大多数问题往往都是NP困难的，难以在多项式时间内计算出最优解，缺乏理想的解决方案。本文构建的供应链优化问题就属于这一类。对于该供应链优化问题，建材配送、存储和补充有很多种可能的组合方式。如果采用数学规划的方法将每个规划期内的订单情况、配送数量以及行驶路径确定下来，将是一项极为复杂的工作，通常只在案例参数都比较小的情况下可行。随着建材种类M、客户数量N和规划周期T的增大，供应链优化问题的计算复杂度将呈几何倍数增长。

对于NP困难问题，可以通过设计近似算法，在较短的时间内得到一个非常逼近原问题最优解的可行解。本文采用禁忌搜索算法作为近似算法，用以获取前述供应链优化问题最优解的近似解。禁忌搜索算法是邻域搜索算法中的一种典型方法，通过在现有解的邻域进行搜索，评价邻域内的可行解，按照给定的接受-拒绝规则选择一个候选解作为下一次迭代的初始解。在经过反复的迭代过程后，所得的解就可以作为禁忌搜索算法得到的近似解。下面将对本文采用的禁忌搜索算法进行详细说明。

3.1 初始解的构建

初始解将作为禁忌搜索算法迭代过程的初始序列， 反复迭代逐步进化为问题的近似解。本问题初始解的构建将分为订单数量确定、规划日配送数量确定、车辆行驶路径确定三部分实现。

订单数量确定：初始解的订单在规划周期开始时发出，订货数量涵盖整个规划期内所有客户的建材需求，规划期间将不再向供应商发出订单。初始解具体特征如下：

∀m=1，…，M

xmt=0

∀m=1，…，M,t=2，…，T

规划日配送数量确定：仓库每天都会向客户配送其当天所需求数量的建材，且配送数量仅覆盖当天需求。每辆卡车仅向一位客户配送建材，如果客户当天的建材需求总量超过一辆卡车的最大装载体积，则分配多辆卡车进行配送。初始解具体特征如下：

∀l=1，…，L,t=1，…，T

车辆行驶路径确定：由于每辆卡车仅向一位客户配送建材，初始解下卡车配送路径非常简单，从仓库出发后仅路过其配送客户的装修现场然后返回仓库。

3.2 候选集合的构建

在初始序列产生后，需要在初始序列的邻域空间中选取数个可行序列构建候选序列集合。在禁忌搜索算法中，候选集合的构建是至关重要的，候选集合的好坏直接影响算法近似解与理论最优解的误差范围及计算时间。

本研究中，候选序列集合从初始序列的邻域中随机抓取产生，抓取方法包括订单时间变更、订单数量增减、订单合并、订单拆分、配送时间变更、配送数量增减、卡车配送合并、卡车配送置换、卡车路线变更，等等。迭代过程中，候选序列集合的可行序列数量通常多达数十个。

3.3 禁忌变换表

在禁忌搜索算法的每一次迭代过程中，会保持一个变动的禁忌变换表，任何位于该表中的变换方式是不允许进行的。禁忌变换表有一个固定的长度，通常是5～10个变换方式。每次迭代过程最后，新生成的序列会替代现有序列作为下一次迭代的初始序列，反向变换将被加入禁忌变换表的顶部，并剔除禁忌变换表中最后一个元素。这是为了防止在经过禁忌变换表长度次数的变换内，回到原先已经产生过的一个局部最优序列，招致循环。

禁忌变换表长度的设置需要严格控制，若长度偏小往往难以发挥作用，偏大则会加重设备计算负担，本研究采用的禁忌变换表长度为10。

3.4 回溯机制的设置

在禁忌搜索算法的迭代过程中，某个迭代初始序列的领域变换序列可能都在禁忌变换表中，导致迭代的可行候选序列集合可能是空集。这种情况下，本轮迭代将返回初始序列，进而导致无限循环，禁忌搜索算法将陷入局部最优解中，无法在整个搜索域内获取其他可行解。

为了解决该问题，研究中引入了回溯机制，在记录邻域内最优解s1的同时保留邻域内的次优解s2、s3、…、sm。当s1、s2、…、sj-1的可行候选序列集合为空集时，sj将作为初始序列进行下一次迭代。次优解记录范围m值的大小对算法的有效性有较大影响，m值偏小将会使回溯机制失效，偏大则会增加处理设备的计算负担，本研究中采用的m值为3。

3.5 强化机制的设置

在最坏的情况下，回溯机制仍可能无法帮助算法跳出局部最优解。算法需要在最优序列长期未得到改进的情况下，重新产生初始序列进行迭代。本研究通过强化机制来实现这个过程。

在强化机制下，当迭代过程未能优化最优序列这一事件连续触发且达到某一预先设定的阈值时，当前已得到的最优序列将作为初始序列进行下一次迭代。强化机制可以使算法跳出当前局部最优，并且显著减少随后的迭代次数。强化机制在一次算法中通常只能触发一至两次。

3.6 算法的具体实现

下面对所使用的禁忌搜索算法进行详细的说明：

步骤一令k=1，找到一个可行解作为初始序列S1，定义最优序列S0=S1。

步骤二从Sk的邻域中产生候选序列集合S。

步骤三如果候选序列集合非空，则在候选序列集合中选取总运营成本最低的候选序列Sc1，令Sk+1=Sc1，并记录次优序列Sc2，Sc3。

如果候选序列集合为空集，则触发回溯机制，定义前次迭代的次有序列作为Sk+1，转到步骤七。

步骤四将初始序列Sk置于禁忌变换表的顶部，并删除禁忌变换表的最后一个元素。

步骤五如果候选序列Sc1的总运营成本小于最优序列S0的总运营成本，那么令S0=Sc1。

步骤六如果达到预设阈值，则触发强化机制，令Sk+1=S0。

步骤七如果k=N，那么已达到迭代循环上限，停止迭代，返回最优序列S0；否则，将k值增加1，转到步骤二。

4 计算实验

提出该优化问题的近似算法后，我们需要对该算法的有效性进行评估。这是因为近似算法求得的可行解与最优解的偏差往往不可预料，需要多次检验以保证误差在可接受范围内，若偏差较大，需要对算法进行修正以满足误差要求。

计算实验可以模拟互联网家装企业在一定规划期内建材的配送、存储以及补给情况。样例的各种参数信息(客户需求、建材规格、各项成本等)可通过随机数生成器随机产生。供应链优化问题的最优解可以通过前述混合整数线性规划模型借助软件求得。近似算法的近似解则可以通过程序设计，按照前述算法步骤反复迭代获得。通过比较最优解与近似解的总运营成本，可以评估近似算法的效果。

4.1 样例生成

在本次计算实验中，模拟了互联网家装企业12个规划日内的建材配送、存储以及补给过程，每组样例中涉及2类建材和3位客户。每组样例包括以下信息：卡车最大装载容量、施工现场最大建材容量、建材体积、单次订货成本、前置时间、单位库存成本、仓库初始库存、安全库存、单次最低订货量、客户位置，以及各个规划日客户的建材需求等。

建材、客户以及规划周期跨度的数量设置是出于计算机处理方面的考量。如果参数设置过少，通过穷举法就可能直接得到表现不错的近似序列，甚至得到最优序列，近似算法的实际意义就没有得到凸显；如果参数设置过多，会导致计算机软件在求解最优解上消耗过长时间，滞缓研究进度。

本研究根据实际情况预先设定了部分样例参数(卡车最大装载容量、建材规格、安全库存、最低订货量等)，不同样例间的参数差异主要体现在客户位置以及各个规划日客户的建材需求上。每个客户的位置参数由其与仓库的距离以及弧度确定，距离和弧度通过随机数生成器产生，以确保客户均匀分散在仓库周围。在生成每个客户的距离及弧度参数后，两个客户间的距离可通过余弦定理求得。客户在各个规划日的建材需求假定为一定区间内的均匀分布，利用随机数生成器产生，以符合实际施工现场建材以稳定速率被消耗的事实。

4.2 算法效果评估

在样例数据生成完毕后，我们将求解混合整数线性规划模型得到的最优序列与近似算法得到的近似序列总运营成本进行比较，数据如表1所示。为显示近似算法中初始序列的优化效果，笔者将初始序列总运营成本也纳入表格中进行比较。本研究中，混合整数线性规划模型最优解采用Cplex软件求解，供应链优化问题的近似解按前述近似算法利用Python语言编译实现，迭代次数设置为10 000次。

表1 近似算法效果评估

由表1可以看出相对于初始序列，近似算法得到的近似序列在总运营成本上的优化效果非常显著，近似序列总运营成本相对初始序列降低了70%以上。近似序列与最优序列总运营成本相当接近，两者的比值接近于1，两者间的误差在可接受范围内。因此，能够得出结论，在数据样本较大的实际案例中，用近似算法得到的近似序列来近似供应链优化问题的最优解是可行的。

此外，在计算时间方面，最优序列单个样例求解耗时在五分钟左右，近似算法单个样例的平均处理时间在五分钟内，两者相差不大。但考虑到随着客户、建材等参数数量的增长，最优算法计算时间随变量以及限制条件的几何倍数增长将同样呈现几何倍数增长，而近似算法由于迭代次数的固定计算时间几乎保持不变。可以看出，近似算法在时间消耗方面是要远远优于模型求解最优解的。

5 研究结论

本研究针对时下正热的互联网家装行业面临的线下供应链优化问题构建了混合整数线性规划模型，并设计近似算法求解其近似解。计算实验结果显示，迭代10 000次后得到的近似序列和最优序列的总运营成本差值在1%以内，近似算法误差在可接受范围内。

近似算法的优势在于处理时间。随着案例数据量的增大，问题最优解的计算时间将以几何倍数增长，而近似算法能够在计算时间几乎不变的情况下得到高精度的近似解，此时用近似算法代替最优算法求解更为可取。

实际生活中，互联网家装企业通常对接数十个一级供应商，其下游的客户更是数以万计，采用穷举法或是分支定界法获取仓库日常配送、存储和补货方案显然是不可取的，近似算法的实用价值不言而喻。此外，本文设计的近似算法适用范围并不局限于互联网家装行业，所有直接对接供应商和客户的供应链一体化行业都适用该近似算法。