1. 引言
冷链物流主要是针对生鲜农产品、食品及药品生物制品等,组织从生产、储存、运输、销售直到消费前的各个环节的供应链系统,确保在各个环节都能处于规定的低温条件环境下,以保证生鲜农产品、食品及药品生物制品的质量安全,减少损耗 [1] 。我国2021年全年的冷链物流总额超过8万亿元,冷链物流市场规模达到4586亿元,整体的冷链物流总量也突破到3.02亿吨,自党的18大以来,我国冷链物流呈现蓬勃发展 [2] 。
现如今,冷链物流配送环节已成为重要的环节,与传统常温物流相比,冷链配送过程要求更加严格,同时也产生一系列问题。例如,高功耗冷藏设备与传统物流相比增加制冷成本,还有大多数物流企业未采用先进制冷设备,无法长时间为产品保鲜,再加上配送效率低下,导致产品损耗较大,增加总配送成本 [3] 。这些问题都会影响冷链物流配送路径规划,因此合理的冷链物流配送路径规划对于降低冷藏车辆配送所产生的能耗,降低运输过程的制冷成本与损耗成本,以及提升冷链配送服务质量具有重要意义。
本文以Y公司作为研究对象,主营业务为水果产品批发与销售,目前多以主观经验规划配送,造成配送时效性差及路径规划不合理等问题。一般而言,生鲜产品损耗程度与配送时间和距离密切相关,且配送时间和配送距离越长就会产生更多配送成本 [3] 。因此,为建立科学合理有效的冷链物流配送路径规划,降低生鲜产品损耗程度,本文根据Y公司目前冷链物流配送现状构建出适用的数学模型,在考虑时间约束以及载重量的限制条件下,利用改进C-W算法求解最优配送路径,不但适用于路径优化,还可应用于其他行业中的调度问题及排队计划提供参考。
2. 文献综述
冷链物流配送路径问题是车辆路径问题(Vehicle Routing Problem, VRP),常见的算法有精确算法与启发式算法。
1) 精确算法
Dantzig和Ramser [4] 提出VRP,利用组合优化规划行车路线,降低总里程和配送成本。郑飞 [5] 考虑服装配送车辆的配送路径选择,采用动态规划求解最优配送路线。Santos et al. [6] 提出二级自由选择车辆路径问题的分支割价算法,克服解决此类问题的公式对称问题,求解效果优于精确算法。龚国清 [7] 应用分支定界法(Branch and Bound)于货架存取路径,提高货物存取效率。但是,精确算法存在不易求解复杂路径优化问题的弊端。
2) 启发式算法
随着配送路径问题的日益复杂,求解最优解已经变得不符合实际,因此求解近似最优解的启发式算法成为研究对象,其中遗传算法(Genetic Algorithm, GA)、禁忌搜索算法(Tabu Search, TS)、模拟退火算法(Simulated Annealing, SA)、蚁群算法(Ant Colony Optimization, ACO)、节约里程法(C-W算法)等算法得到大规模应用。
成冲与蒋洪伟 [8] 提出基于顾客满意度和食品新鲜度的车辆配送路径优化模型,利用GA求解健身营养餐最优配送路径。曹炳汝与王霞 [9] 针对产品配送过程中配送车辆类型的多样性,以配送成本最小化作为目标,建立多车型配送路径优化模型,利用改进型GA求解,不仅降低配送成本,且减少配送车辆。GA有利于全局路线最优选择,各个配送点并入最优路线也更加简单,但是参数选择比较困难,且运行效率较慢,操作也较困难。袁志远等 [10] 建立多种药品集中配送的配送成本最小路径优化模型,利用TS克服局部最优难题,但对初始解依赖性强且优化效率一般,操作较困难。王芳等 [11] 针对蔬菜运输成本高、保鲜时间短以及成本高所导致蔬菜质量降低的问题,以时间窗和车辆载重为约束条件,提出带时间窗约束的SA,有效地实现全局最优,但SA仅适用于小规模问题,大规模问题求解耗时较长。Yu et al. [12] 将ACO应用于旅行商问题(Travel Salesman Problem, TSP)中,从物流路径优化和末端配送模式出发,找出在物流配送中影响客户满意度的因素,通过仿真验证ACO在求解过程中较好的鲁棒性和易于求解的特点,但是易于陷入局部最优,搜索时间较长,优化效率不高。
相对于前面的启发式算法,C-W算法简单且易于操作,实务操作上受到使用者的青睐 [13] 。时宇 [14] 应用TSP建立快递配送路径优化模型,以C-W算法进行求解。尹庆等 [15] 应用C-W算法对奶制品企业在城区内的配送进行求解,达到缩短配送距离、降低配送成本等目的。胡虹等 [16] 根据多影响因素综合构建模型,利用C-W算法求解多种类型的目标函数。梁乃峰 [17] 认为运用C-W算法优化配送路线,可以有效减少水果连锁企业的经营和管理成本,利于水果连锁企业的经营管理能力的提升。
总的来说,C-W算法更易于与载重量、时间窗以及新鲜度等约束条件相结合,利于与企业实际情况相结合而且易于理解,操作更加简单。各种算法的比较如表1所示。
![](Images/Table_Tmp.jpg)
Table 1. Comparison of various algorithms
表1. 各种算法的比较
3. 构建冷链物流配送路径优化模型
3.1. 建模假设与参数设计
为方便建立模型,模型假设如下:
1) 由单一配送中心向多个客户配送,每辆车配送完毕后需返回配送中心。
2) 假设冷藏配送车辆完全相同,行驶速度固定,搬运工在每个客户点卸货速率一样。
3) 配送货物为生鲜水果产品,对冷藏环境、外界温度以及时间要求相同。
4) 每个客户仅有一辆冷藏车配送,所有配送车辆均能满足配送路径上的客户需求量之和。
5) 配送中心到各客户的运输距离、各客户之间的运输距离已知。
6) 各客户的时间窗要求以及产品需求量已知,配送车辆要在客户规定的时间段到达。
7) 所有客户的需求量均小于车辆最大载重量。
3.2. 构建模型
3.2.1. 优化目标分析
本文对Y公司的冷链物流配送路径进行优化,令A0为配送中心,Ai为各客户节点(
)。为降低在配送过程中所耗费的费用,以总配送成本最小化为优化目标,总配送成本包括运输成本、制冷成本以及货损成本。鉴于水果产品易腐蚀性及客户对配送时段的硬性要求,除了车辆载重限制外,也考虑硬时间窗限制。
针对运输成本主要包括变动成本和固定成本两种,本文只考虑车辆的变动成本,假定车辆为匀速行驶且车载重的减少对油耗的影响忽略不计,车辆变动成本与配送车辆行驶距离成正比 [18] ,因此由Ai至Aj的运输成本
如式(1)所示,其中ce为单位里程运输成本,lij为Ai至Aj的配送距离,
为0-1变量,若第r辆配送车辆经过Ai至Aj的路段,则
,否则等于0。
(1)
其次,在冷链物流配送中货损成本主要产生在车辆的行驶过程中以及打开冷藏车厢时。在配送车辆的行驶过程中,随着时间的积累水果发生轻微腐烂变质的行为;在打开冷藏车厢门时,车厢内的温度提升也会导致损失一定比例的产品 [3] ,因此由Ai至Aj的货损成本
如式(2)所示,其中pe为单位产品价格,
为0-1变量,若Aj由车辆r服务,则
,否则为0,β为运输过程中单位时间货损系数,θ为卸货过程中开车厢门时单位产品货损系数,qj为Aj的产品需求量,Qij为Ai至Aj送货时配送车辆的载重。
(2)
最后,冷藏设备工作会消耗燃料以及制冷剂,因为油耗所花费成本已包含于运输成本中,因此只考虑制冷剂消耗的费用。制冷剂的消耗量可通过计算冷藏车的热负荷G来决定,热负荷产生的原因主要是太阳辐射传入车厢内部以及车厢漏气,热负荷可表示为式(3) [19] ,其中R为车厢传热系数;S为车厢的平均表面积,一般情况下
,Sn为车厢内表面积,Sw为车厢外表面积;ΔT为车厢内外温差。
(3)
由于在运输过程制冷剂消耗量受车厢内外温度差、车辆行驶时间以及车厢传热系数影响,因此制冷成本
如式(4)所示,其中Pf为单位制冷成本、G为车辆行驶中的热负荷、tij为车辆从Ai至Aj的行驶时间、
为0-1变量。
(4)
3.2.2. 目标函数及约束条件
本文以运输成本、货损成本以及制冷成本配送之和最小为优化目标,目标函数及约束条件如下:
(5)
(6)
(7)
(8)
(9)
(10)
(11)
式(6)表示服务客户的所有需求量之和小于车辆最大载重量,式(7)表示每个客户仅被一辆车配送,式(8)表示到达每个客户的配送车辆只有一辆,式(9)表示离开每个客户的配送车辆只有一辆,式(10)表示车辆配送完毕后需返回配送中心,式(11)表示配送车辆到达客户点的时间窗。
4. 改进C-W算法
4.1. 加入硬时间窗约束
时间窗约束是指Ai和Aj两点并入一条配送路径后,引起配送车辆到达Aj及其续客户的时间变化。为了求解时间窗约束,引入时间变化量Hij,表示为
,即将Ai和Aj并入一条配送路径后,配送车辆到达Aj后与不合并相比到达客户所花费时间的差值 [7] ,其中bi表示配送车辆到达Ai的时刻,ti表示配送车辆在Ai处停留的时间,bj表示配送车辆到达Aj的时刻。
接着令
,表示在为Aj后面的客户配送时不超过时间窗限制,配送车辆到达Aj的最晚推迟量;令
,表示Aj后的客户无需等待时,配送车辆到达Aj的最早提前量,Ar表示晚于Aj配送的客户。
因此,当
时,配送车辆到达Aj的时间点与原配送路径相比推迟,此时若
,则无须推迟为Aj后面的客户配送,表示Ai和Aj可以在一条路径配送。反之,需要推迟,两点不可合并。当
时,配送车辆到达客户Aj的时间与原配送路径相比提前,此时若
,则Aj后面的客户无需等待配送,表示Ai和Aj可以在一条路径配送。反之,需要等待,两点不可合并。
4.2. 优化最优目标
本文使用节约运输成本替代节约里程,节约的总成本为
,其中
为节约的运输成本、
为节约的货损成本、
为节约的制冷成本,计算Ai和Aj合并前后的成本节约总值,选择最大节约成本进行路径优化。
首先,节约运输成本为
(式(12)),Ai和Aj合并前后配送的运输成本分别为本
和
,其中
是由Ai行驶到Aj的运输成本,运输成本由运输距离决定,所以
且
。同理节约货损成本为
(式(13)),其中
是由Ai行驶到Aj的货损成本,由于连接客户点后货物装卸过程的货损成本不会发生变化,故只考虑运输过程中的货损成本,而运输过程中货损成本由行驶时间长短决定,运输时间可由运输距离与行驶速度相除得到,故货损成本的节约原理与求解节约运输成本一致,因此
且
。最后,节约制冷成本为
(式(14)),其中
是由Ai行驶到Aj的货损成本,因为制冷成本模型受到配送时间影响,因此
且
。
(12)
(13)
(14)
4.3. 改进C-W算法求解步骤
改进C-W算法求解步骤如下 [4] :
Step 1 令A0为配送中心,Ai为各客户节点(
),分别连接A0和Ai,计算A0至Ai实际距离,生成m个初始解,计算各客户点之间实际距离,生成距离矩阵。
Step 2 连接Ai和Aj,生成距离节约矩阵,若所有节约值均为0,计算结束,否则将各客户点之间距离节约值按降序排列。
Step 3 确定第一条路径的第一个配送对象。计算从配送中心到各配送点的总配送成本,并从小到大升序排列,选取配送成本最小的客户作为第一个配送对象Ak,需满足
和
。
Step 4 确定第一条路径的第二个配送对象。合并Ak与剩余的客户,分别计算出与剩余各客户合并后成本节约值(
),并从大到小降序排列,选取成本节约值最大的一项作为配送对象。
Step 5 每并入一个客户点需要满足以下约束条件:
①
。
②
且
。
③
且
。
如果满足条件①②或者①③,转到Step 6,否则回到Step 4重新寻找符合约束条件的节点。
Step 6 确定第一条路径的第二个配送对象。
Step 7 重复Step 4~Step 6,直到所有客户点都无法满足车辆载重和时间窗约束,此条路径规划完毕。
Step 8 重复Step 3~Step 7,排除第一条路径的客户,规划其余配送路径,直到完成所有客户的配送。
5. 案例分析
5.1. 配送数据及模型参数
5.1.1. 配送数据
本文以Y公司在商丘市的水果产品冷链配送作为研究主体,其在商丘市内拥有一个配送中心(A0),并有10个水果需求客户作为配送点(A1, A2, ∙∙∙, A10),在满足客户需求量、车辆载重限制及客户时间窗下,规划配送成本最小的配送路径方案。表2为配送客户的具体位置、配送时间要求及车辆在各客户的停留时间。本文已将各客户的时间窗及车辆停留时间量化处理,并得出公司原始配送路径(图1),并利用百度地图导航测量出车辆的实际行驶距离作为各客户点之间实际最短距离(式(15))。
![](//html.hanspub.org/file/19-2330725x65_hanspub.png?20230728094037512)
Figure 1. Vehicle distribution path of original distribution plan
图1. 原配方案的车辆配送路径
(15)
5.1.2. 模型参数
Y公司使用福田奥铃冷藏车(表3),利用表3信息可计算车厢平均面积;商丘市2021~2022年柴油价格均价为7.88元/升,利用综合燃料消耗量可计算出冷藏车单位里程运输成本;根据易虹 [3] 和本文调研情况,得出水果产品在运输过程及卸货过程中的货损率;依据王海丽 [19] 和钱光宇 [20] ,设定出车厢传热系数及单位制冷成本的参数值;通过实地调研Y公司水果产品价格,并依据商丘市2021年水果产品市场均价,设定出单位产品价格;此外假设冷藏车行驶速度保持在40 km/h,车厢内外温差为20℃,主要参数及参数值如表4所示。
![](Images/Table_Tmp.jpg)
Table 3. Parameters and parameter values of Futian Aoling refrigerated truck
表3. 福田奥铃冷藏车参数及参数值
数据来源: [19] [20] 和本文整理。
![](Images/Table_Tmp.jpg)
Table 4. Main parameters and parameter values
表4. 主要参数及参数值
5.2. 模型求解
依据改进C-W算法,以节约总成本最大为路径规划目标,从而实现配送成本的最小,在路径规划时应不违反时间窗及车辆载重的约束。在求解模型前需计算出冷藏车从A0行驶至各客户所需的时间(t0i) (表5)。此外还需计算冷藏车到达客户的时间点(bi) (表6),若配送车辆提前到达配送点,则bi = ETi,若配送车辆在客户要求的时间窗内到达,则bi = t0i,[ETi, RTi]为客户要求的时间窗。
接着,根据改进C-W算法求解。首先计算距离节约矩阵(式(16)),当配送车辆从A0出发分别为10个客户配送货物,形成10条配送路径,花费的配送成本如图2所示。根据式(1)至式(4),A0到A8的配送成本最小,且
,
,因此A8作为第一条路径的第一个配送对象不违反时间窗及车辆载重的约束。
而图3可看出合并A7到A8节约总成本最大,
,
,
,
,因此A7为第一条路径的第二个配送对象。同理,根据图4与图5结果,A6与A10分别为第一条路径的第三个与第四个配送对象。但是,为A10服务后的时间点为2.905,此时剩余客户仅有A9的时间窗符合条件,从A10行驶到达A9所需时间为0.5 h,已超过A10最晚时间窗限制,因此第一条配送路径规划结束。重复求解,共可规划出三条车辆配送路径(图6),而不考虑时间窗也得三条车辆配送路径(图7)。
5.3. 结果对比分析
从图6与图7来看,Y公司是否考虑时间窗约束所规划出的路径有较大差别,由于公司传统配送路径(图1)和不考虑时间窗的配送路径选择都违反个别客户的时间要求,为了便于比较配送成本差异,以下考虑违约成本对总配送成本的差异进行比较,违约成本 = 货物价值*惩罚比率,惩罚比率表示每超时送达货物0.1 h所需支付的比率(表7)。
![](Images/Table_Tmp.jpg)
Table 5. Vehicle travel time from the distribution center to all customers
表5. 车辆由配送中心到达各客户的行驶时间
![](Images/Table_Tmp.jpg)
Table 6. Time points at which the vehicle arrives at all customers from the distribution center
表6. 车辆由配送中心到达各客户的时间点
(16)
图1为原有配送路径依据司机的配送经验进行选择,图6考虑时间窗约束和载重约束,图7不考虑时间窗约束,仅考虑载重约束,此三种配送路径方案的成本对比如图11所示。结果显示,图6考虑时间窗约束和载重约束的配送路径方案,其总成本最小,且在运输成本、货损成本、制冷成本与违约成本皆是最小,表明冷链配送重视客户时间要求的必要性。(图8~11)
![](//html.hanspub.org/file/19-2330725x74_hanspub.png?20230728094037512)
Figure 2. Various costs of vehicles traveling from distribution center to each customer (unit: yuan)
图2. 车辆从配送中心行驶到各客户的各项成本(单位:元)
![](//html.hanspub.org/file/19-2330725x75_hanspub.png?20230728094037512)
Figure 3. Cost savings from merging remaining customers to A8
图3. 合并剩余客户到A8的各项节约成本
![](//html.hanspub.org/file/19-2330725x76_hanspub.png?20230728094037512)
Figure 4. Cost savings from merging remaining customers to A7
图4. 合并剩余客户到A7的各项节约成本
![](//html.hanspub.org/file/19-2330725x77_hanspub.png?20230728094037512)
Figure 5. Cost savings from merging remaining customers to A6
图5. 合并剩余客户到A6的各项节约成本
![](//html.hanspub.org/file/19-2330725x78_hanspub.png?20230728094037512)
Figure 6. Vehicle delivery path considering time window constraint
图6. 考虑时间窗的车辆配送路径
![](//html.hanspub.org/file/19-2330725x79_hanspub.png?20230728094037512)
Figure 7. Vehicle distribution path without considering time window constraint
图7. 不考虑时间窗的车辆配送路径
![](//html.hanspub.org/file/19-2330725x80_hanspub.png?20230728094037512)
Figure 8. Distribution cost analysis of original distribution path scheme
图8. 原配送路径方案的配送成本分析
![](//html.hanspub.org/file/19-2330725x81_hanspub.png?20230728094037512)
Figure 9. Distribution cost analysis of distribution path scheme considering time window constraint
图9. 考虑时间窗和载重约束的配送路径方案的配送成本分析
![](//html.hanspub.org/file/19-2330725x82_hanspub.png?20230728094037512)
Figure 10. Distribution cost analysis of distribution path scheme without considering time window constraint
图10. 仅考虑载重约束的配送路径方案的配送成本分析
6. 结论
本文以运输成本、货损成本以及制冷成本三者之和最小为优化目标,为满足客户时间窗要求及实现配送总成本最小,构建考虑时间窗的冷链物流配送路径优化模型,将时间窗约束加入传统C-W算法,并将传统C-W算法中节约里程改进为节约成本。根据分析结果显示,利用改进C-W算法求解出的两种配送方案与Y公司原配送路径相比,节约配送里程,降低配送成本,因此冷链配送应重视客户的时间窗要求。