考虑时间窗服务价值的越库车辆路径优化

刘虹，林楚玥

（福州大学经济与管理学院，福建福州350100）

一、引言

近年来，国内物流行业发展迅猛，第九届中国物流信息化大会以“创新驱动物流产业升级”为主题，力求推进智慧物流的行业应用。而越库（cross-docking）作为一种以供给链间信息化为基础的高效物流新技术，因其能大幅降低库存水平，加快货物流动，在国外已被广泛应用于配送网络中[1]。

越库问题的研究主要有内部运作调度和外部车辆路径两方面，其中车辆路径研究考虑了协调运送、运输策略等方面。Lee 等学者首次提出越库的车辆路径问题，取货车辆应同时到达越库中心，以便于合并处理[2]；Liao 等学者对此方法进行了改进[3]。Wen 等学者放宽了车辆在越库中同步到达的假设，通过整合来协调运送路线[4]。Yu 等学者研究越库的开放式车辆路径问题，协同取货车辆的到库时间[5]。曹克官讨论了直送和循环取货两种调度策略下的越库配送网络问题[6]。葛显龙等学者在循环取送货策略下，研究供应链环境下的越库协同配送网络最小成本问题[7]。而Baniamerian 等学者则关注越库配送网络的最大利润问题[8]。Maknoon 和Laporte 在多越库的配送网络中考虑车辆负载同步性，研究货物可在越库间转移合并策略下的车辆路径问题，并提出自适应大领域搜索算法[9]。

越库配送网络注重整体的配送效率，而配送效率的高低直接影响着客户服务水平，衡量配送服务水平的研究，主要集中在建立与时间相关的满意度函数来评价服务水平，满意度越高则服务水平越好。Fan 认为配送服务水平与客户等待时间呈现反比关系，由此构建满意度函数[10]。Chen、楼振凯等学者用梯形模糊数表征模糊时间窗，用模糊度隶属函数刻画客户满意度，通过线性分段式函数体现客户对配送服务的满意程度[11-12]。王君同样是用模糊时间窗反映客户对时间的偏好程度，并将客户满意度表示为关于时间的凹模糊数[13]。任亮等学者考虑客户拖期厌恶行为，运用前景理论价值函数体现客户配送服务水平[14]。

综上所述，越库配送的研究主要集中于车辆调度、协同到库策略等，考虑分拣整合策略的越库配送相对较少。另一方面，由于存在交通阻塞等一些不确定因素，可能使产品送达时间不确定，进而使产品送达时间窗偏离，也会使客户的心理感受随之变化；对于越库配送中心而言，产品配送时间的不确定对车辆和驾驶员的调度均会产生影响。本文主要研究的问题是：在连锁零售的越库配送网络中，针对越库中心内部的协同到库、分拣整合和外部车辆路径的集成配送，考虑客户对配送时间的心理感知对服务水平评价存在影响，引入前景理论，构建客户时间窗服务价值函数，寻求使得时间窗服务价值最高和配送成本最低的越库车辆路径优化方案。

二、问题描述及建模

（一）问题描述与假设

连锁零售的越库配送网络，包括：多个供应商、一个越库配送中心和多个客户零售商。零售商依据各自的销售需求向各供应商提交货物订单，越库配送系统由此获取客户订单，其中客户订单包含三个属性信息：取货地点（即供应商节点）、送货地点（即零售商节点）和订单货物量。配送网络见图1。

根据越库协同到库和分拣整合策略，调度取货车辆前往取货点拾取货物，并协同抵达越库中心；订单货物根据目的地进行分拣重装；经过整合的货物由送货车辆按一定顺序送达客户点，送货车辆最后返回越库中心。客户根据货物送达时间会产生不同的心理感知，影响着时间窗服务价值，越库配送系统需要优化车辆配送路径，以期在降低配送成本的同时提高客户时间窗服务价值。有以下假设：

假设1客户订单的三个属性信息（取货点、送货点、货物量）以及配送时间窗已知；

假设2每个取/送货点仅由一辆取/送货车辆服务，并且仅被服务一次；

假设3取/送货车辆均从越库中心出发，在访问完取/送货点之后必须返回越库中心；

假设4取货车辆采用整车直运方式运输，即每个取货点只需一辆车，且不考虑载重约束；

假设5送货车辆具有载重约束，要求每辆车所分配的所有订单货物量之和不超过其最大载重量；

假设6节点间车辆运输成本和运输时间、货物的单位装卸时间和单位处理时间以及可用车辆数量已知。

图1：越库配送网络

（二）符号与变量说明

1.模型参数

R{ r |r= 1, … l}：表示订单集合；

D{i | i= 1, … n}：表示送货点（零售商）集合；

P{ j |j= 1,…m }：表示取货点（供货商）集合；

O：表示越库配送中心；

εjr：表示订单r (r ∈R)与取货点j (j ∈P)对应关系，若 εjr=1，表示订单r 的取货点为j；

V{k |k= 1, … v}：表示取货车辆集合；

V'{k |k= 1, … v'}：表示取货车辆集合；

Q：表示送货车辆最大载重量（以托盘为单位）；

Qv：表示可用车辆数量；

S =P ∪｛O｝ ∪ D ：表示配送网络中所有节点集合；

Cv：表示车辆固定运营成本；

qr：表示订单r(r∈R)货物量（以托盘为单位）；

di：表示送货点i(iD∈)供货总量（以托盘为单位）；

pj：表示取货点j(j∈P)收货总量（以托盘为单位）；

Tab：表示节点a 到节点b 的运输时间(a, b∈S)；

Cab：表示节点a 到节点b 的运输成本(a, b∈S)；

γ ：表示在取/送货点每一单位货物所需装/卸货时间；

φ：表示在越库中心每一单位货物所需处理时间；

M ：表示极大的数；

[T1,T2]：表示送货点最早最晚工作时间窗；

EETi：表示送货点i(i∈D)期望送货服务时间节点；

LLTi：表示送货点i(i∈D)可容忍送货服务时间节点。

2.决策变量

stk：取货车辆 k(k∈V)离开越库中心出发取货的时间；

atk：取货车辆k(k∈V)到达越库中心的时间；

dtk：送货车辆k (k ∈V')离开越库中心时间；

tik：送货车辆k (k ∈V')到达送货点i (i∈D)时间。

（三）客户时间窗服务价值模型

考虑到客户在评价配送水平时，往往会受行为和心理因素的影响，且对准时性要求也并非完全刚性。前景理论价值函数，运用到服务评价中能够表示为“收益”与“损失”，结合模糊时间窗，构建客户时间窗服务价值函数，以此衡量配送服务水平。

1.价值函数的表示

客户对配送到货时间产生主观感受的满意度或价值，前景理论可用来描述客户对时间窗服务的不同感知，客户i 的感知价值函数可表示为如下：

其中：α ,β,λ为参数，α 表示收益系数，β 表示损失系数，λ 表示客户对损失的敏感程度。任何收益或损失都需要根据参考点做出判断，一般选取价值为0 的点作为参考点，在模糊时间窗中，若送货时间在客户可容忍时间之前，则客户的时间窗服务价值为正值，可看作是收益；反之则价值为负，即损失。因此，本文将客户可容忍服务时间（LLTi）作为参考点。考虑到在可容忍时间端点上是符合配送要求的，取值为0 不符合实际情况，故假设在此端点上取值为0.5。

2.背景假设

为表达客户时间窗服务价值，作如下背景假设：

假设7在越库配送网络中，所有客户（零售商）最早和最晚工作时间分别为 T1、 T2；

假设8所有客户拥有相同的评价系数，即每个客户的α 和β 取值相同；

假设9客户在评价配送服务水平时，选择可容忍服务时间端点作为参考点，送货车辆在此端点到达，时间窗服务价值取值为0.5；

假设10当送货车辆在客户i 期望时间EETi之前到达客户点，时间窗服务价值最高，取值为1；

假设11当送货车辆在客户i 期望时间EETi之后，且可容忍时间LLTi之前到达客户点，客户将车辆到达时间与参考点（可容忍时间端点）进行比较，认为符合自身时间要求，时间窗服务价值为正值，可看作收益，应选用价值函数xi≥ 0部分；

假设12当送货车辆在客户i 可容忍时间LLTi之后，且在最晚工作时间前到达客户点，客户接受服务但认为不符合自身时间要求，时间窗服务价值为负值，可看作损失，应选用xi＜ 0部分。

假设13当送货车辆在最晚工作时间端点到达客户点时，时间窗服务价值取值为-1，而在2T 之后，客户将不再接受服务。

3.客户时间窗服务价值

定理1在越库配送网络中，若送货车辆k 服务客户点i，到达时间为 tik，在可容忍时间之内（ [T1,EETi]和(EETi,LLTi]两个区间），则时间窗服务价值函数U (tik)表达如下：

证明：由假设11 可知，客户将送货车辆到达时间与参考点（可容忍时间端点）进行比较，车辆到达时间若在可容忍时间之前，则认为符合自身时间要求，即时间窗服务价值为正，可看作收益，应选用价值函数xi≥ 0部分，即

（1）当tik∈[T1,EETi]，由假设10 可知，在期望时间内，客户时间窗服务价值最高，数值恒定为1，即：

（2）当tik∈(EETi,LLTi]，设时间窗服务价值函数 U (tik)为：

由假设10 和假设11 可知送货车辆到达时间为EETi时，客户时间窗服务价值数值为1，而LLTi时，时间窗服务价值数值为1/2，即：

将式（6）除以（5），得：

将1a 代入式（5），得：

即：

综上，式（2）得证。

定理2在越库配送网络中，若送货车辆k 服务客户点i，到达时间为ikt ，在可容忍时间之后且在最晚工作时间内（(LLTi, T2]区间），则时间窗服务价值函数U (tik)如下：

证明：

由假设12 和假设13 可知，客户将送货车辆到达时与参考点（可容忍时间端点）进行比较，若车辆到达时间在可容忍时间之后，客户认为不符合自身时间要求，即时间窗服务价值为负，可看作损失，应

选用价值函数中xi＜ 0部分，即V ( xi)=-λ · (-xi)β。

当tik∈(LLTi, T2,]，时间窗服务价值函数 U (tik)为：

由假设12 和假设13 可知，送货车辆到达时间为LLTi时，时间窗服务价值数值可看作0，而 T2时，时间窗服务价值数值为-1，即：

由式（14）得：

将 a2代入式（15），得：

即：

式中λ 可约去，得：

式（12）得证。

推论在假设7 至假设13 背景下的越库配送网络中，如果送货车辆k 在 tik时间到达客户点i，则客户时间窗服务价值函数模型为：

其图形见图2，其中，T1、T2分别为客户最早、最晚工作时间，EETi是客户期待服务时间节点、LLTi是客户可容忍时间节点。

图2：时间窗服务价值函数

车辆在不同时间段到达客户点，客户对配送服务的感知会有所不同，相应的时间窗服务价值含义也有所不同：

（1）车辆在iEET 节点之前到达，客户对配送服务感知最为满意，时间窗服务价值取值均为1；

（2）车辆在(EETi,LLTi]内到达，时间窗服务价值则随时间减小，特别的，在LLTi节点上，仍满足客户配送要求，亦可看作收益，因此取值0.5；

（3）车辆在iLLT 之后到达，则看作损失，且在2T 节点上取得最小值-1。

4.数学模型

（1）目标函数

（2）约束条件

其中：式（21）和式（22）为目标函数，式(21)是总成本最小化目标，包括车辆运输成本以及车辆固定成本；式（22）是平均客户时间窗服务价值最大化目标；式（23）和式（24）分别是各取货点和送货点取货或送货的货物量计算公式；式（25）是送货车辆最大载重约束；式（26）表示整个配送过程所用车辆数目不超过可用车辆数；式（27）表示每个取/送货点仅被服务一次且仅由一辆车服务；式（28）-式（31）表示每个订单仅被分配一辆车，且同一个取/送货点的订单分配同一辆车；式（32）-式（33）表示变量 jrky 、'irky 与abkx 之间的正确关系；式（34）保证车辆路线的连续性；式（35）表示取货车辆协同到达越库中心；式（36）是取货车辆到达越库中心时间的计算公式；式（37）表示送货车辆离开越库中心的时间约束；式（38）和式（39）表示送货车辆在配送阶段的时间约束；式（40）和式（41）表示决策变量属性。

三、求解算法

越库的路径优化属于NP-hard 问题，且双目标优化模型的求解难度远大于单目标优化，宜采用启发式算法求解。禁忌搜索算法（Tabu Search，TS）通过使用禁忌列表，能够避免算法在局部最优点迂回搜索，实现全局最优化[15]。在此基础上，本文结合局部搜索算法（Local Search，LS）设计了混合多目标求解算法。整个算法主要分为两层：外层使用TS 算法来优化越库车辆路径问题，形成配送方案，其中在内部嵌套了一层LS 算法判断送货车的载量，嵌套程序对其方案进行判断，将结果返回主程序，主程序再根据其返回值对路径方案进行调整，以此递推，最终得到较优的车辆路径方案。

算法具体步骤如下：

Step1：初始化算法参数。包括最大迭代次数max_iter，禁忌长度tb_length，邻域解个数neighbor_coun，禁忌表tabulist=∅，全局非劣解集局部非劣解集

Step2：生成初始解。采用随机方式产生初始送货路径序列Initial_TSP，由此得到初始解Initial_Sol，并置当前解Current_Sol=Initial_Sol，

Step3：计算目标函数值 f1、 f2，并判断是否满足时间窗约束条件，若不满足，则令 f2= f2- M，M是一个很大的数。

Step4：调用局部搜索算法，判断装车是否成功，若成功直接返回 f1、 f2，否则返回 f1= f1+M，f2= f2- M。

Step5：对当前解进行邻域操作，得到候选解集Candidate_Sol。

Step6：重复Step3 和Step4，得候选解Candidate_Soli 的目标函数值 f1(i )、f2(i )。

Step7：更新局部非劣解、全局非劣解，在候选解集中，应用非支配排序算法筛选局部非劣解集与全局非劣解

Step 8：判断候选解集是否满足藐视准则。若是，则将对应的禁忌对象替换最早进入禁忌表的禁忌对象，更新全局非劣解集；否则，在非禁忌对象的候选非劣解中选择一个作为当前解，并将相应的禁忌对象替换最早进入禁忌表的禁忌对象，更新全局非劣解集。

Step9：终止条件判断。若达到最大循环迭代次数，输出全局非劣解集结束算法；否则继续Step5-Step8。

四、算例与仿真

（一）算例与实验设计

越库车辆路径优化模型尚无标准测试算例，本文选用已有算例数据，由10、50 个节点组成的两种规模问题，并根据研究内容对数据进行扩展[5]，算例参数值见表1。

两组实验设计如下：

实验1：对小规模算例进行仿真求解，研究协同到库和分拣整合策略在越库车辆路径中的作用。

实验2：对大规模算例进行仿真，对比研究存在负值的时间窗服务价值（场景1）与其他文献中服务水平最低值仅为0（场景2）。

表1：参数信息

表2：第1 组实验取货调度方案

表3：第1 组实验Pareto 解集及送货方案

（二）实验结果与分析

本文应用MATLAB R2016a 进行仿真实验，系统是Windows 7，硬件环境是Intel（R）Core（TM）i3-7100 CPU@3.90GHz，内存3.87G。经过反复测试，参数设置如下：迭代次数max_iter=500，邻域解个数neighbor_count=160，禁忌长度tb_length=20。根据Kahneman 的结论[16]，α 、β 取值为0.88。通过算法求解，实验1 仿真结果见表2 和表3。

实验1 结果分析：

1.由表2 可知，取货阶段采用直运方式，共需4 辆车，路径1 中，行车时间为186.3 个单位时间，在供应商处装货时间为19 个单位时间，路径总时间为205.3 个单位时间。4 辆车的路径总时间在[169.9,225.5]区间，根据协同到库策略要求，以225.5 作为取货车辆协同到库基准，据此调度取货车辆的发车顺序，为后续货物进行分拣整合提供有效保障。

2.由表3 可知，24 份订单货物在越库中心根据不同目的地被分拣重装为6 份，并由3 辆送货车进行后续配送。

表4：第2 组实验仿真结果

实验2 仿真结果如表4 所示，场景1 所得解集中，总成本最低为7305.6307，时间窗服务价值最高为0.8234，当时间窗服务价值上升时，总成本会亦有所增加。时间窗服务价值的提高往往是以增加配送成本为代价。

对比场景1 和场景2 可知，通过改变超过可容忍时间的价值函数，函数值取零和取负的结果是不同的。在相近成本下，场景2 所衡量的服务水平会高于场景1。为考虑具体影响，选取场景1 总成本最低的实验结果进行下一步分析，根据相应的配送方案计算每一个客户在场景1 和场景2 下的时间窗服务价值，结果对比见图3。其中，场景1 中时间窗服务价值平均值为0.7277，场景2 平均值为0.7446。

图3：时间窗服务价值对比分析图

实验2 结果分析：

（1）时间窗服务价值和配送总成本之间存在相关性，两者互相冲突，决策者可根据实际情况选择合适的配送方案。

（2）由图3 可知，该方案有6 个客户点出现了配送延迟，超过了客户可容忍时间，两种方法计算出的客户时间窗服务价值平均值分别为0.7446 和0.7277，由于存在负数，降低了整个配送的服务水平。

（3）场景1 中的客户时间窗服务价值存在负值，直观地表示出客户负向的心理认知，大大影响了其总体配送服务水平，应引起决策者的重视。

五、结论

在越库配送系统中，通过协同到库策略，相同目的地的货物得以在越库中心得到分拣整合，合理规划车辆路径，有助于进一步降低配送成本，同时提高配送服务水平。本文同时考虑了协同到库、分拣和客户时间窗服务，以配送总成本最小、客户时间窗服务价值最大化为优化目标，建立越库配送路径多目标优化模型；针对模型特点，设计了禁忌搜索算法和局部搜索算法相结合的混合算法寻求最优配送路径。得出以下结论：

（1）越库中心的协同到库及分拣策略、配送车辆运输路径是越库问题中较重要的影响因素，将两阶段集成研究能有效提高越库的整体配送效率，更符合实际。

（2）采用客户时间窗服务价值，符合客户的心理变化，反映出客户对越库配送服务的感知水平。

（3）禁忌搜索算法和局部搜索算法相结合的混合多目标求解算法，能降低无效路径生成的概率，提高算法求解效率。

在现实中，越库配送网络的应用更为复杂，未来将进一步研究多个越库中心、多个周期的动态越库系统调度。