基于时空相似测度的冷链物流分区配送路径优化

卢甲东，张世斌,b

(上海海事大学 a.物流科学与工程研究院; b.文理学院，上海 201306)

0 引 言

随着我国经济的快速增长和人民生活水平的稳步提高，人们对生鲜品的需求量越来越大。2017年，冷链市场规模已达4 600亿元。然而，冷链运输成本的居高不下严重制约着冷链产业的发展，难以满足人们消费升级的热切期望。冷链品配送作为冷链物流的最后一个环节，配送路径的合理规划对降低整个物流运作成本和提高冷链品配送质量至关重要。[1]因此，针对冷链物流时效性[2]强的特点，提供合理有效的配送方案是冷链物流企业亟待解决的问题。

冷链物流配送问题主要考虑在一定约束条件下配送路径的合理优化，其约束条件涉及特定商品、软硬时间窗、随机环境和多周期等因素。例如：TARANTILIS等[3]针对希腊的鲜肉配送问题，提出了一种新的随机搜索元算法；邵举平等[4]针对生鲜农产品时效问题，建立了生鲜农产品的配送路径多目标优化模型；CALVETE等[5]基于软时间窗建立了车辆路径规划的多目标优化模型，并采用枚举法选择较优的配送方案；王淑云等[6]利用了k-means聚类算法和蚁群算法解决随机需求下多温共配的冷链品路径优化问题。由于车辆路径问题(vehicle routing problem,VRP)为NP难问题，其求解方法多为启发式算法。TAN等[7]建立了带时间窗的VRP (VRP with time window,VRPTW)的多目标优化模型，提出了求解模型的混合遗传算法；DONDO等[8]利用混合整数线性规划方法对VRP进行了优化；DING等[9]提出一种混合蚁群算法求解VRPTW；KASSEM等[2]采用模拟退火算法和爬山算法求解VRPTW。利用聚类算法对客户地理位置进行分类，再利用启发式算法求解是一种新思路。谷炜等[10]在分析了k-means聚类算法的优劣后，设计了一种配送区域划分方法——改进的两阶段k-means聚类算法；高学东等[11]提出了一种考虑配送路网结构和配送量约束的聚类算法以避免以往不考虑配送道路状况的研究缺陷；王旭坪等[12-13]采用“聚类-路径优化”思想，基于客户地理位置确定配送方案，并以最小化平均有效订单服务时间为目标函数，构建了考虑订单完成期限的在线订单分批混合整数规划模型。

与传统的配送方式相比，在冷链物流配送前，根据客户地理位置先进行聚类，再按订单类别进行分区配送，无疑可以大大节约运输成本。[6]然而，传统的k-means聚类[10]是仅基于客户的地理位置利用空间位置相似性进行的。另外，当配送系统中客户数目较多且受严格的时间窗和车辆数目限制时，用VRPTW优化模型往往无法得到可行配送方案。[4]鉴于此，对于考虑时间窗的冷链物流分区配送问题，本文主要对客户分区方法进行进一步改进。首先，同时考虑客户地理位置的相邻性和订单配送时间窗的相似性，提出了时空相似测度的概念。然后，在最小化配送成本时，基于时空相似测度利用改进的k-means聚类算法对客户进行分区。最后，利用遗传算法对分区配送路径进行优化，并设计算例来验证基于时空相似测度的客户分区策略在配送路径优化方面的优势。

1 冷链物流分区配送路径优化模型

1.1 问题描述和基本假设

考虑“一对多”配送模式，即一个配送中心服务多个客户。优化目标是使冷链配送成本最小。目前，分区配送主要是借助空间相似测度通过对客户的地理位置进行聚类实现的。在对客户进行分区时，本文同时考虑客户地理位置的相邻性和订单配送时间窗的相似性，提出时空相似测度，对客户进行聚类以实现客户分区。

假设：(1)配送中心每天有一定数量的订单需要配送，并且客户的位置信息已知；(2)每个客户都有固定的配送时间窗，如果不在该时间窗内配送，就会产生相应的时间惩罚成本；(3)配送中心的每辆车负责一个配送区域，且该区域总配送量不超过车辆的最大载质量，即不考虑回程补货因素；(4)车辆只负责送货。

1.2 数学模型

1.2.1 模型常量和变量

常量：N为客户位置集合；L为客户位置分类集合，K为配送车辆集合，|L|=|K|，其中|L|与|K|分别代表集合|L|和|K|中元素的个数；Q为配送车辆的载质量；C1为单位运费；C2为早于客户最佳配送时间窗配送的惩罚系数，即早到的单位损失成本；C3为晚于客户最佳配送时间窗配送的惩罚系数，即晚到的单位损失成本；m为单位货损成本；a1为运输过程中的货损比例；a2为装卸过程中的货损比例；qj为位置j的卸货量；[T1j,T2j]为客户j所要求的最佳配送时间窗；Tok为车辆k出发的时刻(o为配送中心位置)；dij为从位置i到位置j的距离；v为配送车辆的平均速度。

变量：Nl为第l类客户位置集合，l∈L;Nol为包含配送中心位置的分类客户位置集合，l∈L；xijk为0-1变量，若车辆k从位置i到达位置j则为1，否则为0；Tik为车辆k到达位置i的时刻；Ti为车辆在位置i的工作时间。

1.2.2 基于时空相似度的客户分区

(1)

式中，θ表示时空成本转化系数，为单位时间损失成本折算成的运费。在本文中，θ=2C1/(C2+C3)，即把单位运费与不按期(早于或晚于最佳配送时间窗)配送的平均惩罚系数的比值作为将时间在成本等效意义下转化为距离的比例系数。在对ti用θ修正后，由式(1)定义的时空相似测度的本质是三维空间上的两点(xi,yi,θti)与(xj,yj,θtj)之间的欧氏距离相似测度。基于时空相似测度，利用k-means聚类算法，即可实现对所有客户的分区，得到Nl,l∈L。

1.2.3 分区配送路径优化模型

以冷链配送成本最小为目标构建的配送模型为

(2)

s.t.

(3)

Tok=to

(4)

(5)

xijk∈{0,1},i∈Nol,j∈Nl,k∈K

(6)

(7)

(8)

(9)

式(2)为目标函数，表示使配送成本最小，配送成本包括运输成本、时间惩罚成本和货损成本,其中x+=max(x,0)。式(3)～(9)为约束条件：式(3)为车辆的实际装载量不超过车辆的载质量；式(4)给出配送车辆从配送中心出发的时刻(to)；式(5)为配送车辆到达位置j的时刻；式(6)为0-1变量约束；式(7)表示每个客户订单只能由一辆车进行配送，不能拆分；式(8)表示车辆完成客户订单后必须离开；式(9)表示所有车辆在完成配送任务后都必须回到配送中心。

2 两阶段优化求解分区配送问题

对于单配送中心问题，如果采用传统固定分区方式将配送区域划分为几个独立区域(见图1，其中∘ 为客户位置)，则只会求得每个分区的最优解，与整个区域内的全局最优解尚有很大差别。采用时空相似测度对配送区域进行分区，然后再对每个分区进行配送路径优化，这样比基于空间相似测度进行分区的方法更接近整个配送区域的全局最优解。

图1 传统固定分区图例

在给定分区数目的情况下，k-means聚类算法是最经典的分割式聚类算法。取分区数目与配送车辆|K|相同，随机选择|K|个点作为个分区的起始质心，分别计算剩下的客户位置点与这|K|个点的相似度，将剩下的客户位置点分别划归到相似度最高的分区中。重新计算|K|个分区的质心重复上述过程，直至迭代至聚类结果不再发生变化。本文基于时空相似测度(式(1))，将整个客户集合N分成|K|个类，以便于下一步对每个客户群l(l∈L)进行配送路径优化。

遗传算法操作步骤如下。(1)编码。采用自然数编码，产生与客户群相同个数的自然数序列作为遗传算法的染色体。(2)初始化种群。由上一步编码形成的自然数序列作为遍历客户群的一个初始解，产生M个染色体，组成遗传算法的初始种群。(3)配送中心设置。配送中心设置在整个客户群分布的中心点位置。(4)适应度函数值计算。根据初始配送路径，计算适应度函数值。(5)选择、交叉、变异操作。先用轮盘赌选择策略进行选择操作，再随机选择2个优秀个体，以0.9的交叉概率进行交叉操作，然后以0.05的变异概率进行变异操作。(6)精英策略。在进化过程中，把每代最优秀的个体保留下来直接进入下一代遗传操作，以此不破坏父代的优秀个体信息，加快算法的全局收敛速度。(7)迭代。根据给定的遗传算法迭代次数进行迭代，得到所有的配送区域的最优路径。

3 算例验证及分析

3.1 算例信息

假设某配送中心有5辆配送车辆，60个客户点，配送车辆的车型规格统一，配送车辆的载质量Q=30 t，配送车辆的平均速度v=45 km/h，配送车辆的单位运费C1=7.5元/km。早到的单位损失成本C2=5元/(h·kg)，晚到的单位损失成本C3=10元/(h·kg)，单位货损成本m=400元/ t。冷链配送考虑运输过程中的货物损失，运输过程中的货损率a1=0.1%，装卸过程中的货损率a2=0.2%。每个客户的坐标、作业时间和配送时间窗见表1。

表1 客户订单信息

3.2 3种分区方法的比较

基于传统固定分区(分区方式见图1)的最优配送路径见图2a，其详细配送路径见表2；基于时空相似测度进行分区的最优配送路径见图2b，其详细配送路径见表3。由图2可见，基于时空相似测度进行分区优化后，许多客户订单所属的配送区域发生了较大改变，例如，图2a中属于同一配送区域的两个客户订单12和5(在点(90 km，50 km)附近)在图2b中却属于不同配送区域。

a)固定分区配送

b)基于时空相似测度的分区配送

表2 基于固定分区的最优配送路径

表3 基于时空相似测度分区的最优配送路径

采用3种不同分区方法的配送成本见表4。由表4可见，与传统分区配送、基于空间相似测度的分区配送相比，基于时空相似测度的分区配送的运输成本和货损成本与之相差不大，但时间惩罚成本明显减少，从而使配送总成本分别降低16%和13%，且按时送达的订单数也大有改观。

表4 采用3种不同分区方式的配送成本比较

4 结 论

针对采用冷链物流传统固定分区方式的路径规划难以求得全局最优解和现有聚类分区配送仅考虑地理位置相似性对客户进行分区等问题，提出基于时空相似测度进行分区的配送方式。在该分区方式下，冷链车辆对应的配送区域将不再固定，而是同时根据客户地理位置信息和订单配送时间窗即时调整。根据冷链配送的特殊性，以最小配送成本为目标构建模型，同时考虑时间惩罚成本和货损成本，为单配送中心的冷链分区配送提出可行方案。冷链企业在进行冷链配送时，需综合考虑时间和空间因素来优化配送路径，基于时空相似测度进行分区配送正融合了上述两个关键因素，在保证时效性的前提下使物流企业冷链配送方案优于考虑空间相似性的分区配送方案。

本文的配送车辆不考虑回程补货的情况，所有的配送任务均一次完成。融合现有多配送中心物流配送路径优化的相关方法，基于时空相似测度进行分区的冷链物流配送路径优化方法可以拓展到多配送中心冷链物流的联合配送优化问题中。例如，将本文中时空相似测度引入到多配送中心物流配送车辆调度问题的分层算法模型[14]中进行分层求解，即利用聚类分析得到的时空距离最近方法划定每个配送中心服务的客户群，进而可以将多配送中心问题转化为多个单配送中心车辆调度问题进行求解；还可以将时空相似测度引入到考虑碳排放的冷链物流联合配送路径优化[15]目标函数中的运费计量中，以进一步优化冷链物流的联合配送路径。