基于温区细化的多温共配车辆路径优化

唐 燕，许 睿，黄锴迪，孟令清

(天津理工大学 管理学院，天津 300384)

0 引言

生鲜产品随外界温度变化，品质受较大影响，其保质期与食品的特性、储藏温度和时间密切相关[1]。多温共配车辆长时间配送所处的环境温度会有较大波动，制冷机的能耗随外界温度变化而改变[2]。为探讨外界温度变化对配送车能耗的影响，提出温区细化(指动态环境温度对制冷能耗的影响)的配送车温控问题。

在生鲜产品配送方面，国内外相关学者主要在约束变量设置上进行了研究，如时间窗、货损值、顾客满意度等方面。Stellingwerf[3]提出负载目标约束最小的车辆路径模型，对温控环境下的碳排放量做出详细研究。Bottani[4]探讨了食品冷藏供应链的经济和环境可持续问题，发现交付过程对环境影响最大。为提升温控运输系统效率，王勇等[5]将不同温度控制下生鲜货物的价值损失进行比较分析，构建了包含配送成本与货物价值损失的目标优化模型。方文婷等[6]利用遗传算法求解负载与卸载顺序的绿色车辆路径问题。付焯等[7]对风险与货损进行分析，构建了生鲜农产品供应链风险决策模型。吴芳芸[8]将资源与需求集中化，提出轴辐式冷链物流网络模型对于冷链物流温控成本的计算仅仅定义于车辆的运行时间、车厢门开关次数、卸货时间等因素，忽略了外界温度对配送车制冷能耗的影响。本研究将VRPTW问题结合大规模订单，构建基于温区细化的ALNS生鲜产品配送模型，使之更符合实际配送情况。

1 问题描述

配送流程中对温度的控制不能得到保证，导致生鲜农产品新鲜度衰减加快，造成不必要的浪费和冷链成本提高。为有效控制整个冷链运输中的温度变化，减少生鲜农产品新鲜度损失速率，综合考虑碳排放、客户服务时间约束、制冷成本等因素，进行合理运输调度。

具体假设如下：

(1)配送中心拥有一定数量且规格相同的配送车，每辆车的装载量有限且大于单个客户点的需求量。

(2)各节点位置、需求量、配送时间窗及服务时间确定。

(3)同一配送车可进行不同节点配送，每个节点仅配送1次且满足客户需求。

(4)配送车仅进行配送和装卸任务，不接受任何其他配送服务且完成配送任务后返回到配送中心。

(5)配送过程中车辆匀速行驶，忽略道路拥挤情况。

生鲜配送过程对温度要求较为严格，其中外部环境温度变化也对配送车温控的能耗产生影响[9]。根据我国气象数据，收集天津市夏季平均气温每小时温度(如表1所示)，最低温度与最高温度在时刻3和时刻13差值可达13.6 ℃。

表1 温度变化Tab.1 Temperature change

不同种类产品对温度的要求不同，配送车需对产品特性进行温度控制。为计算温度与能耗之间的关系，用COP表示热量和能量间转化比率，如式(1)所示：

(1)

式中，σl为车内的环境温度；σh为车外环境温度。为方便计算，利用开尔文温度替代摄氏度，表示为σ(K)。开尔文温度与摄氏度σ转化关系为：

σ(K)=273+σ(℃)。

(2)

根据能量转化关系，以车外25.8 ℃、车内零下5 ℃的冷却单位成本来计算车厢内外不同温度对应的制冷系数，得出制冷系数矩阵。利用MATLAB的CFTOOL工具进行薄板样条法插值，拟合得到配送车内外温度与制冷系数间的变化关系，拟合优度R2为0.98。由图1(a)可得，在车外温度为22～26 ℃，制冷系数较高，对应能耗随之增大，图1(b)更直观地反映了制冷系数在不同温区间的变化情况。

图1 温度细化的制冷系数相关图Fig.1 Correlation diagrams of refrigeration coefficient for temperature refinement

2 模型建立

对生鲜农产品配送的问题假设及场景进行描述后，建立生鲜农产品配送模型。包括变量的定义、约束条件及目标函数。

2.1 变量定义

生鲜农产品配送中有关变量参数的定义如表2所示。

2.2 成本分析

2.2.1固定成本FC

配送车从配送中心出发用于支付驾驶员工资、车辆维修等费用。

(3)

2.2.2运输成本TC

配送车正常行驶过程中的费用。

表2 已知参数Tab.2 Known parameters

(4)

式中α为单位距离成本。

2.2.3绿色成本GC

配送车的绿色成本包括负载状态下，配送途中消耗的燃油成本及产生的碳排放对环境造成污染的成本。

(1)油耗成本

利用负载估计法对配送车配送过程的油耗量进行计算，确定负载与能耗之间的关系[10]。其油耗关系式为：

(5)

式中，ρ(G)为当前载重G吨货物时造成的油耗；ρ0和ρ1分别为空载和满载时的油耗系数；W为配送车最大载重量。

油耗Oil和油耗成本OC的表达式为:

(6)

OC=H·Oil，

(7)

式中，H为单位油耗成本；ρ(Wij)为载重量W的配送车从i到j的单位距离油耗量；dij为客户i到j的行驶距离。

(2)碳排放成本

碳排放量与油耗量呈一定线性关系，建立油耗模型[11]。

CC=β·γ·Oil，

(8)

GC=OC+CC

(9)

式中，β为碳税；γ为碳排放系数。

绿色成本等于油耗成本与碳排放成本之和。

(4)温控成本TCC

在生鲜产品配送中要使温度保持恒定，由此产生的能耗作为制冷成本。在装车前预冷及配送过程中，制冷能耗与外界温度、车厢表面积、太阳辐射面积等有关[12]，这里主要分析配送车外部环境中的温度变化与制冷能耗的关系。

①装配前对配送车预冷成本PC

生鲜农产品从产地采摘下来到分拣包装运上配送车前，根据车内温度与车外温度，需对内部进行预冷操作，抑制其呼吸热，延缓新鲜度衰减。

(10)

式中ησl,σh为车内温度σl与车外温度σh相对应的制冷系数。

②配送过程制冷成本DRC

配送车k从i到j的运输时间tijk内车内温度σl与车外温度σh变化所产生的制冷成本DRC为：

(11)

③装卸过程制冷成本LRC

(12)

④温控总成本TCC：

TCC=PC+DRC+LRC。

(13)

(5)货损成本TL

式(14)为生鲜农产品新鲜度衰减函数，表示在一定温度下的腐化比例[13]：

Ω(t)=Ωoe-ωt，

(14)

式中，Ω(t)表示货物在t时的新鲜度；Ωo为货物出发时的新鲜度。

新鲜度衰减系数通常与产品的呼吸热、周围温度有关，在装卸过程中车厢门打开使车厢内外温差及氧气含量变大，生鲜产品新鲜度衰减速率加快从而得知ω2>ω1。其货损成本表达式为：

(15)

(16)

式中，SL为生鲜配送过程的损失成本；HL为装卸过程的损失成本；ω1为货物在配送过程中的新鲜度衰减系数；ω2为货物在装卸过程中的新鲜度衰减系数。衰减系数通常与产品的呼吸热、周围温度有关，在装卸过程中车厢门打开使车厢内外温差及氧气含量变大，生鲜产品新鲜度衰减速率加快，从而得知ω2>ω1，Wir为车辆离开客户点i时车上剩余货物重量；Di为客户i需求量；Ti为在客户i的装卸时间。

TL=SL+HL。

(17)

基于温度细化的生鲜农产品配送模型的目标函数：

(18)

约束条件：

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

a(i)≤Ti≤b(i),(i∈N)，

(27)

(28)

Tj=Ti+Tij, ∀i,j∈N，

(29)

Xijk,Yik=0或1, ∀i,j,k。

(30)

式(19)表示各客户点需求量之和不超过配送中心最大配送量，S为配送中心最大配送量；式(20)表示每个客户点只能访问1次；式(21)表示每辆车的配送量不超过最大载重量；wi为各客户点需求量；式(22)～(23)表示所有客户的需求量得到满足；式(24)表示车辆k从配送中心o出发，完成客户点j配送任务后返回到配送中心；式(25)～(26)表示任意节点只允许车辆出发到达1次，Yjk为配送车k为客户点j服务；式(27)表示配送车辆达到时间必须为最大容忍时间窗内；式(28)表示消除子回路，L为任两点间的回路总数；式(29)表示配送的过程是连续的，Tj为到达客户点j的时间，Ti为到达客户i的时间，Tij为两点间行驶时间；式(30)为其约束条件。

3 算法设计

大规模邻域搜索(LNS)通过构造初始可行解将多个具有相关性节点进行重组操作，探索解决问题的邻域[14]。但随着邻域规模的增加，数据处理较为复杂。在此基础上，自适应大规模邻域搜索(ALNS)对于同一搜索中节点移除和插入的操作采用多种方法进行塑造，避免了LNS易陷入局部最优的问题。其流程图如图2所示。

图2 ALNS优化流程图Fig.2 Flowchart of ALNS optimization

3.1 初始解的构造

为提高生鲜配送模型优化效率，采用贪心算法构造初始解。以时间窗和配送容量为约束，通过初始化的距离矩阵，寻找距离节点i+1最近节点i直至遍历网络中所有节点得到VRPTW初始解。

3.2 算子移除操作

通过不同方法对初始解配送路线中节点进行移除。

(1)随机移除：选择一定数量节点移除，增加搜索过程多样性。

(2)最差移除：在改进解的过程中，对成本最大节点进行移除。定义成本为：c(i,s)=f(s)-f-i(s)，其中f-i(s)为移除节点i的成本，将c(i,s)的值进行排序，靠前的节点被选择概率最大。将差值较大的节点移除重新插入到其他位置，从而构造更优解。

(3)Shaw移除[15]：考虑相关度高的节点，r(i,j)为任两点p和q间的相关程度；θ1，θ2，θ3，θ4分别为节点间距离d、时间T、载重量G、配送车辆k的权重系数。若相关程度越高，则移除该组节点的可能性越大，在后续重新构造更优解时增加多样性和随机性，如式(31)所示：

r(i,j)=θ1[dp(i),p(j)+dq(i),q(j)]+θ2(|Tp(i)-

Tp(j)|+|Tq(i)-Tq(j)|)+θ3|Gi-Gj|+θ4

(31)

3.3 算子插入操作

(1)随机插入：相似于随机移除，选择一定数量节点进行插入，增加多样性。

(2)贪心插入：不断将被移除节点插入到使目标函数值最小的位置上，与构造初始解的方法相同。

(3)最少成本插入：Δfi为客户i插入到第i′个节点后，目标成本增加的变化量为Δfi=max(fi-f′i)。

3.4 最优解筛选

利用轮盘赌法对不同算子表现情况所占的比例概率进行选择[16]。τ1为产生新的全局最优解；τ2为产生新解但对应的目标函数值劣于当前解；τ3为产生非改进解但被接受。分数排序为τ1>τ2>τ3。对各组算子对应解的情况，新的最优解概率最高，非改进解概率最低。采用模拟退火算法的接受准则对候选解进行判断，若目标函数适应度值Δf(x)<0，则更新当前最优解x，否则以概率exp(Δf(x)/T)接受X′作为新的当前解[17]。

4 结果分析

4.1 算法检验

利用Solomon算例，将禁忌搜索法(TS)[18]、大规模邻域搜索法(LNS)与自适应大规模邻域搜索法(ALNS)进行对比。得出每组车辆调度总配送路程结果，如表3所示。根据各算法结果表明LNS与ALNS计算优于TS，ALNS的计算普遍结果优于LNS计算，可得知使用ALNS算法对于求解VRPTW问题具有一定的可行性。

表3 算法检验Tab.3 Algorithm checking

参数设置：东风配送车规格为7.2×2.3×2.7 m，实际载重7 t/45 m3，生鲜供应客户点数分别为400，800，1 000点，如图3所示。配送车8：00从配送中心出发，额定行驶速度为60 km/h，生鲜市场价5元/kg，冷藏温度在0～5 ℃，配送车固定成本为单次运输150元。正常行驶下空载和满载的油耗系数分别为0.18和0.41，配送车配送状态的制冷系数和装卸系数为5元/h和12元/h，由此产生的生鲜新鲜度衰减系数分别为0.03和0.06，柴油价格为5.09元/L，配送车碳排放量为2.669 kg/L，碳税30 元/t，迭代次数为500次，更新选择算子的间隔迭代次数30 次。

为贴近城市实际行驶路径，将各配送点标记在二维的经纬度网格平面上，利用曼哈顿距离法计算各配送点间距离。小数点后6位精度约为1 m。由于整体数据庞大，部分配送订单信息如表4所示。

表4 需求订单信息Tab.4 Order demand information

4.2 成本分析

算法通过Win10系统的Eclipse(4.15.0)编程实现。得到不同规模的生鲜产品配送成本、制冷成本、货损成本与绿色成本，如表5所示。配送成本包括固定成本与运输成本，由表5可得。调度中花费比例占据最大为配送成本，最小为制冷成本。配送成本主要费用为配送车配送的里程油耗及驾驶人员工资，绿色成本涉及负载货物配送造成的油耗，所占比例较大。随着规模的增加，各项成本也呈倍数增加，绿色成本和货损成本的增长幅度更高，随着客户点规模扩大，对于货物需求量增大，其配送中出现不可避免的增加车次、载重油耗、运输油耗、驾驶员开资等费用。

表5 ALNS各算例结果Tab.5 Result of each example by ALNS

不同规模的成本组成分析如图3所示。各成本随总距离的增加而增加，绿色成本里包含油耗使得占有总成本的最高比例。

图3 成本分析Fig.3 Cost analysis

各规模配送方案的迭代次数如图4所示。在前50次，配送成本迅速收敛，1 000节点配送方案最先趋于稳定，800节点其次，400节点最后。在迭代450次之后，各规模配送成本趋于稳定。

图4 收敛曲线Fig.4 Convergence curves

ALNS算法执行中各算子的使用情况如表6所示。destroy和repair各类型算子中Random Destroy算子和Greedy Repair算子被选择概率最高，Random Destroy算子对于路径的重组作用较为全面，可获得更客观的当前解，避免所得解陷入局部最优，Greedy Repair算子对于更全面的当前解进行优化，其改进效果明显优于Random Repair算子和Regret Repair算子。

表6 各算子使用情况(单位：%)Tab.6 Usage of each operator (unit: %)

5 结论

以天津市生鲜配送为研究背景，结合大规模邻域搜索算法，考虑路径优化与配送成本，建立了以时间、路程、能耗最小为优化目标的车辆调度模型，并通过轮盘赌法与模拟退火算法的接受准则进行优化求解，得到以下结论：

(1)生鲜电商产地直销模式的兴起，使得生鲜产品配送规模不断扩大，由此考虑外界环境温度变化下制冷能耗的变动情况，为冷链运输中的温度控制提供一定帮助，丰富了生鲜配送路径优化的研究内容。

(2)在需求点规模庞大的路径优化问题上，针对LNS在搜索过程中易陷入局部解的缺陷，用ALNS对于不同操作的算子进行概率选择，经Metropolis接受准则得到全局最优解，求得不同客户点规模的调度路线。

(3)在路径优化的算法检验中，ALNS的配送成本明显低于LNS与TS算法，证实了ALNS在配送时间、配送距离、配送能耗等方面均有较好的结果，并利用提出的车辆调度模型解决了天津市某生鲜电商产品配送问题。

(4)从路径优化的收敛曲线与算子使用情况来看，迭代次数前200次解的优化效果最为明显，这表明ALNS对处理大规模的车辆调度问题有一定可行性。Greedy插入算子使用率最高表明初始解构造的好坏对最终结果有一定影响。

本研究为基于温区细化的大规模生鲜配送提供了理论基础，但仅考虑了外部环境温度的变化，未考虑路网拥堵情况的影响，这将是今后本研究的努力方向。