基于时空距离聚类的冷链物流路径优化研究

张建同，经 科 （同济大学 经济与管理学院，上海 200092）

0 引 言

冷藏冷冻产品通常具有易腐性、时效性、损耗大等特点，使得冷链运输与常温运输相比，具有更大的资金投入和成本耗费，其中，配送路径的选择、客户对产品损耗的要求、制冷温度等因素都会令配送方案发生改变。除此之外，由于冷藏车在运输过程中产生的二氧化碳量远高于常温运输，考虑到有关限碳政策和绿色物流理念，企业在安排产品配送时也需考虑冷藏车产生的碳排放影响。因此，对于冷链配送问题的研究具有广泛的应用意义。本文涉及到考虑多配送中心的冷链物流优化问题，将从冷链物流配送问题和具有多配送中心的车辆路径优化问题这两个部分展开文献综述。

Chen 等[1]考虑了交通拥堵、碳排放和碳税关系的影响，假设四种不同的交通情况采用模拟退火回火算法进行路径最优化测试。王旭坪等[2]考虑时空距离度量的冷链配送，先采用K-means 聚类构造初始路径，然后采用改进的模拟退火算法进行优化。Zhang 等[3]建立了冷链低碳物流路径优化模型，结合RNA 计算和基本蚁群优化算法的优点，引入蚁群算法的迭代过程、RNA 计算中的变换、重组和置换操作来优化初始参数。Leng 等[4]提出一个基于最小化物流成本和最大化网络效率的低碳冷链双目标选址路径模型，使用六种多目标进化算法，研究了每个算子的搜索机制。Al-Theeb 等[5]结合库存分配、车辆路径以及冷链问题构建出IVRPCSC 模型，设计了一种三阶段算法进行求解。

另一个相关的问题是具有多配送中心的车辆路径问题（MDVRP） 是VRP 问题的一种变体形式。Allahyari 等[6]提出需求可以发生传递覆盖的MDCTVRP 模型，结合三种启发式算法的思想进行求解。Sadati 等[7]提出了一种变邻域禁忌搜索算法，在强化阶段采用粒度局部搜索机制，多样化阶段采用禁忌振荡机制，并在MDVRP 的三类变种问题上进行算法测试。Fan 等[8]针对时变路网下的MDVRP 问题，综合考虑各方面成本、车速、载荷以及道路坡度对燃料消耗的影响，引入时空距离聚类，采用自适应领域搜索机制，提出一种改进的混合遗传算法。Gulczynski 等[9]研究需求可拆分的MDVRP 问题，采用改进的CW 算法产生初始解，再用一种两阶段启发式算法进行改进，得到MDVRP 的最优解。

综上所述，已有大量成果为进一步研究具有多配送中心的冷链物流问题奠定了良好的基础，但依旧存在一定的研究缺口：（1） 已有文献在研究MDVIRP 时，大多以客户间的空间距离为基础进行研究，较少考虑时间距离对于路径安排的影响；（2）已有冷链配送文献大多假设冷藏车从单个配送中心出发，但实际中，单个配送中心通常无法解决整体配送问题。鉴于此，本文提出了基于时空距离聚类的多配送中心冷链路径优化问题，以综合成本最小化为目标，构建相应的数学模型。设计了一种两阶段算法求解该问题，在第一阶段考虑路径安排的合理性，先基于时空距离对配送中心及客户点进行聚类处理并构造初始解，第二阶段分别对每个聚簇的初始解进行优化，并对算法可行性进行分析。

1 问题描述及数学模型

1.1 问题描述

研究的问题可以描述为：企业的多个配送中心向特定客户点配送产品，运输工具为具有制冷设备的冷藏车，每个客户点的需求、地理位置以及配送时间窗、冷藏车的装载量均已知，完成服务后车辆从客户点返回原配送中心。在此基础上提出以下假设：（1） 每个客户点只能由一辆车服务，仅能被服务一次，且需求固定；（2） 每辆车从某个配送中心出发必须返回原配送中心；（3） 车辆行驶速度相同且固定不变；（4） 每条配送路径上的客户需求量之和不能超过车辆最大装载量；（5） 车辆必须在指定时间窗内到达，早到晚到都需要承担惩罚。

1.2 相关变量及参数

使用有向图G=表示整个冷链配送网络，其中V= ｛1,2,…,n+m ｝表示配送网络中节点的集合，其中包括客户点集合N= ｛1,2 ,…,n ｝以及配送中心集合M= ｛n+1,n+2,…,n+m ｝两部分，E= ｛（i, j ）｜i≠j ｝表示配送路线的弧集，K= ｛1,2 ,…,k ｝表示冷藏车的集合。表1 为相关变量和参数及其各自定义。

表1 相关参数及变量

1.3 数学模型

构建出相关的冷链配送路径优化模型如下：

其中：式（1） 表示目标函数，目标是使配送总成本最小化。式（2） 表示车辆装载量约束，即每条配送路径上的客户需求量之和不能超过车辆最大装载量。式（3） 表示每个客户点只能由一个配送中心服务，且仅被服务一次。式（4） 表示每辆车只能被使用一次。式（5） 表示车辆进出平衡约束，到达某个客户点必须从该客户点离开。式（6） 表示车辆出发和返回的节点都是同一个配送中心。式（7） 表示产品新鲜度约束，实时新鲜度不得低于最低新鲜度。式（8） 表示前一个节点和后继节点之间的时间关系，M 为一个足够大的常数。式（9） 至式（11） 为决策变量的取值。C1为使用车辆的固定成本，C2为运输和卸货过程产生的制冷成本，C3为时间窗惩罚成本，C4为运输过程中的燃油消耗成本，其中燃油消耗率ρm采用负载估计法[10]计算可得，C5和C6分别为运输和卸货过程产生的货损成本以及碳排放成本[11]。

1.4 时空距离度量

在VRP 问题中，通常只用欧式距离来衡量远近。但实际上，时间也是衡量可行性的标志之一，将地理位置相近但时间窗相差很大的客户点放在同一路径中，虽然路径运输成本较小但会产生较大的时间窗惩罚成本。若只考虑时间窗限制，将地理位置相距甚远的客户点放在同一路径中则会造成较大的路径运输成本，因此对两者综合考虑。由于两者属性量纲不一致，先对两者进行归一化处理后进行加权平均，根据参考文献[12]的时空距离计算公式为：

（1） 若LT'j

（2） 若ET'j>LTj，即冷藏车在客户点j 的最晚开始服务时间后到达，令其迟到的惩罚系数为τ2，时间距离τ2（ET 'j-LTj）。

（3） 若ETj≤ET'j

2 算法设计

本文研究的本质问题为车辆路径问题，是NP-Hard 问题，求解此类问题的主要方法为启发式算法和精确算法。本文设计了一种两阶段启发式算法，基本思想为：在第一阶段计算各点之间的时空距离，并基于时空距离采用k 中心点算法对各客户点进行聚类，形成不同的聚簇；第二阶段，先用一个小型启发式算法即改进的CW 算法构造初始解，随后采用引入了变邻域搜索思想的模拟退火算法对初始路径进行优化，以提高算法的全局搜索能力。

2.1 客户点聚类与初始解构造

考虑到K-means 聚类算法受极端值影响较大，且算法选择最开始的质心时具有很大的随机性，因此采用k 中心点算法对客户进行聚类，并采用改进的CW 算法进行初始解构造，算法流程如图1 所示。

图1 改进CW 算法流程图

2.2 改进模拟退火算法的设计

模拟退火算法（SA） 的核心思想是以一定的概率接受使目标函数上升的解，从而使温度下降，不断进行重复搜索，直到满足终止准则。本文借鉴文献[13]的改进模拟退火算法，引入变邻域搜索的思想，在随机搜索的过程中，改变邻域结构，拓展搜索范围，从而提升算法全局搜索能力。算法流程如图2 所示：

图2 改进模拟退火算法流程图

2.3 邻域结构设计

本文算法在设计可用于搜索的邻域结构时，采用了两种交换算子，分别是Cross_Exchange[14]和iCross_Exchange[15]。Cross_Exchange 算子是指随机选取两条路径，分别从中抽取一部分子路径后进行交换。iCross_Exchange 算子是指在进行交换的过程中，将抽取出来的子路径反向逆序插入，具体如图3 所示。邻域结构以不同概率选取两种算子，选取Cross_Exchange 算子的概率为p，选取iCross_Exchange 算子为1-p。

图3 Cross_Exchange 和iCross_Exchange 示意图

多配送中心问题中进行交换的路径以及相应的子路径可以在一个配送中心所涉及的路径中选择，也可以在不同配送中心的路径中选择。本文借鉴文献[16]定义的邻域结构集合，如表2 所示。该集合由12 个邻域结构组成，每个邻域结构都有各自对应的配送中心数量以及子路径最大长度，其中Cr表示路径r 中的客户数量。

表2 邻域结构集合

3 算例测试

3.1 测试算例

本文采用Solomon Benchmark 测试集中混合随机聚类分布的客户点算例，即RC101、RC102、RC201、RC202 的前25、50、100 个客户点算例，并自主设定四个配送中心数据对算例改造后，在Matlab_R2018a 上进行算法测试。增加的配送中心坐标分别设定为（15,10 ）， （25,25 ）， （45,40 ）， （65,60 ）。

3.2 参数设定

设定车辆使用成本Ck=200 元，最大装载量Q=200kg，单位路径成本S=20 元，Pet=10 元，Plt=15 元，制冷成本分别为a=7元，b=10 元，每单位燃油价格P0=5 元，新鲜度衰减系数分别为δ1=0.005，δ2=0.01，每单位碳排放成本Ce=2 元，碳排放系数β=0.08，空载时燃油消耗率ρ0=0.1，生鲜产品单位价值P=5 元/kg，最低新鲜度θ=0.6。改进模拟退火算法的参数分别为内循环迭代次数iter=300，降温系数r=0.98，初始温度T0=5 000。

3.3 算法有效性检验

本文通过将考虑时空路径的改进SA 算法（ST-CWSA） 与只考虑空间路径的CWSA 算法、考虑时空路径的传统SA 算法（ST-SA） 进行比较来验证算法的有效性，算法参数设置与ST-CWSA 的参数设置相同。本文将三种算法分别对上述16 组算例进行10 轮求解后取平均值，表3 展示了三种算法各自最优值，表4 展示了三种算法分别对算例求解后的结果及各自标准差。

表4 三种算法求解得到的平均值及标准差

通过表3 和表4 的结果可知，随着样本算例规模的增大，三种算法下的标准差随之增大。同时，ST-CWSA 算法相对于其他两种算法的成本优化率呈现出先增大后减小的趋势，在算例规模为100 时优化率最高，随后开始减小。与只考虑空间路径的CWSA 算法与ST-SA 算法相比，ST-CWSA 算法的最优值与平均值都相对较小。

ST-CWSA 求解RC101，其最优解如表5 所示，总配送成本为2 645 679.91，所需车辆数为15。

表5 RC101 的最优解

4 结 论

本文综合冷链物流以及多车场车辆路径问题，同时考虑客户时间窗限制以及位置的影响，以最小化多成本之和为目标函数，构建基于时空距离聚类的冷链路径优化数学模型，设计了一种两阶段启发式算法进行求解。通过算例测试可知，考虑时空距离后，算法求得的平均值与最优值都比只考虑空间距离有一定程度的提升。除此之外，改进的模拟退火算法在引入变邻域搜索算法的思想后，与传统模拟退火算法相比，其性能也有所提高。

本文所设定的情况基于配送中心之间无资源共享、配送过程中无路况变化以及客户点需求固定。为了使问题更加具有实际意义，还可以考虑设定为开放式车场即车辆配送完成不返回原始配送中心，且配送过程中考虑实时路况及车速的影响等情况。