0 引言

冷链物流是指易腐易变质产品在从产品生产、加工、贮藏、运输、销售，最终直至消费的各个环节始终处于符合产品属性要求的温度、湿度环境，以有利于保证产品质量，减少产品损耗，防止污染的特殊供应链系统[1]．冷链物流配送对象主要有农产品、加工食品以及特殊商品，具有易腐性的特点，对冷链物流配送的时效性要求较高．然而，日益严峻的城市道路拥挤问题延迟了配送车辆在途时间，增加了货物在途损失成本和配送车辆能耗成本，降低了配送服务质量．

目前，理论界对冷链物流配送路径规划问题作了一定程度的研究．针对冷链配送中温度监控及货物质量的变化，Kuo等[2]提出了冷链物流中的多温共同配送系统，在保证产品质量和运输安全的同时提高车辆利用率，降低配送成本;Ron等[3]提出食品质量退化建模方法，将食品质量水平整合到生产与配送成本中，运用混合整数线性规划模型为设计和优化食品供应链提供决策支持;Li等[4]提出运用无线传感器模块和网络监控冷链物流过程中货物温度;汪庭满等[5]基于无线射频识别技术和编码技术开发了罗非鱼冷链物流温度监控系统．针对时变条件下的冷链物流配送路径优化，Brito等[6]建立了在途时间、卸货时间及服务时间窗不精确条件下的冷冻食品配送模型，并运用模糊方法和混合GRASP-VNS算法优化配送模型;李锋等[7]考虑冷链物流配送过程中车辆行驶速度为时变函数，通过计算机建模方法建立问题模型，并运用遗传算法求解评价值;石兆等[8]根据服务时间窗设计了客户满意度函数，建立时变网络条件下的冷链配送车辆路径优化模型，并采用最小包络聚类分析法与混合遗传算法相结合的两阶段法求解算例．

综上所述，针对冷链物流配送路径优化方面的研究主要集中在配送货物温度监控及质量变化或改进优化模型方法上，虽有少数文献在优化过程中考虑了时变性，但并未建立道路通行状况与冷链配送优化模型间的联系．本文在上述研究基础上，研究考虑道路通行状况下的冷链物流配送路径选择的优化问题，将配送路段距离矩阵转化为通行状况下的运输时间矩阵，以道路通行状况矩阵和运输时间矩阵为基础，构造运输成本、货损成本、能耗成本和惩罚成本，建立优化数学模型．采用遗传算法与2-opt局部搜索算法相结合的混合遗传算法求解实例，并与文献[7]中优化方法的求解结果进行比较．结果表明，本文算法具有求解优势．

1 问题描述

本文研究的冷链配送优化问题是指由单一配送中心使用多台同类型的冷藏车辆为多位客户配送单一生鲜产品，在配送道路通行状况及通行时间已知条件下优化车辆路径，从而使配送总成本最少．

基于道路畅通度[9]和道路畅通模糊综合评价法[10]理论，道路畅通状况由实际数据确定，用矩阵S表示，具体有5类评估词[10]:“非常畅通”s1、“标准畅通”s2、“基本畅通”s3、“不甚畅通”s4和“不畅通”s5．基于美国公路局提出的路段阻抗函数理论，通行时间由路段距离矩阵计算而来，用矩阵T表示．

本文设定以下建模条件:

(1)配送中心能够满足所有客户需求;

(2)每辆车只进行送货作业，且均由配送中心出发，在服务结束后返回配送中心;

(3)每位客户有且仅由一辆车服务;

(4)不考虑车辆外部温度随时间的变化以及装卸过程中的货物损失;

(5)各路段的通行状况互不干扰;

(6)车辆在途匀速行驶．

2 基于道路通行状况的配送路径优化建模

2.1 符号描述

参数:

K:冷链配送中心能够调配的用于进行冷链运输的车辆总数，k∈{1,2，…，K};

m:冷链配送中心所服务的客户总数;

N:客户集合，N={1,2，…，i，…m};

di:客户i的货物需求量;

Q:配送车辆的装载能力;

c1:配送车辆单位时间内的变动运输成本;

P:配送的生鲜产品单位价格;

β1:运送过程中生鲜产品单位时间的货损比例;

c2:运送过程中单位时间的能耗成本;

lt:车辆的卸货效率，即单位时间内的卸货量;

S:关于路段在任意时段的通行状况矩阵;

T:当路段处于某种畅通状况时车辆的通行时间矩阵;

ΔT:划分时间段的区间长度，为常量，以分钟为单位;

S(t,(i,j)):配送车辆在t时段通行路段(i,j)时在道路畅通状况矩阵中所对应的通行状况，i，∈{0,1,2，…，m};

T(S(t,(i,j)),(i,j)):当路段(i,j)处于通行状况S(t,(i,j))时配送车辆在通行时间矩阵中所对应的道路通行时间，i,j∈{0,1,2，…，m};

sik:车辆k从客户i出发的时刻;

wik:车辆k到达客户i后未能立即服务而造成的等待时间;

tik:车辆k到达客户i的时刻;

[ETi,LTi]:客户i的最佳服务时间窗;

[Ei,Li]:客户i所能接受的服务时间窗;

E0:配送中心最早提供配送服务时间;

λ:车辆在时间区间[LT,L]到达服务客户所造成的单位时间机会损失成本;

γ:车辆在时间区间[LT,L]到达服务客户所造成的单位时间惩罚成本;

M:违反可接受服务时间时足够大的惩罚常数;

s0k:车辆k从配送中心出发的时刻;

决策变量:

2.2 目标函数与约束条件

2.2.1 目标函数

本文界定的冷链物流配送总成本包括运输成本、货损成本、能耗成本及惩罚成本四部分．

(1)运输成本

只考虑运输可变成本，表达式如下:

(2)货损成本

只考虑由于运输环境不满足运输要求或货物已经变质等原因造成的在途货损，表示为

(3)能耗成本

能耗成本与在途时间等因素有关，其表达式为

(4)惩罚成本

由于生鲜产品有其特定的销售时段，因而各客户均规定了各自的服务时间窗，分别由客户最佳服务时间窗[ETi,LTi]和客户所能接受的服务时间窗[Ei,Li]组成．惩罚成本函数表达式如下:

2.2.2 约束条件

目标函数:

约束条件:

式(5)表示最小化总配送成本;式(6)表示每辆车所装载的货物量不能超过车辆装载能力;式(7)表示所使用的车辆数不能超过最大可调用车辆数;式(8)表示每位客户只能由一辆车服务;式(9)表示服务时间窗约束;式(10)表示等待时间的计算公式;式(11)表示在同一配送任务序列中相邻客户间车辆到达时刻的递推关系式;式(12)表示在同一任务序列中相邻客户间车辆出发时刻的递推关系式;式(13)划分了车辆k服务完客户j后前往客户i的出发时刻所处的时间段，式中:表示取车辆由客户i出发时刻中以小时为单位的数值，表示取车辆出发时刻中以分钟为单位的数值，如车辆k由客户i出发时刻.

3 混合遗传算法设计

3.1 编码

染色体编码采用实数编码形式，如图1所示．其中:非0实数表示客户点，即ikt表示车辆k服务的第t个客户，实数0表示“隔板”．该染色体解码可得:车辆k服务配送路线

图1 染色体编码   

Fig.1 Chromosome coding

3.2 适应值函数

以Fn=1/fn作为适应值函数，当各染色体的目标函数值fn差距较小时，各染色体的选择概率相差不大，因此降低了优良染色体进入下一代的概率．为避免该种情况，本文依据选择压力理论[11]，采用作为适应值函数，从而增大各染色体间目标函数值的差距．式中，α为大于1的常数．

3.3 遗传算子

运用轮盘赌的方法进行选择操作，其染色体的选择概率为

交叉操作采用双点交叉，在区间[1,col]内生成两随机数(col为染色体长度)，也即交叉基因位，两数值间的基因(包含两基因位上的基因)参与交叉操作．以染色体1:1-4-0-2-6-3-0-5-0-0-0和染色体2:2-3-1-0-5-0-4-6-0-0-0交叉为例，在区间[1,11]内生成随机数4和8，即生成交叉基因位4和8，如图2(a)所示．

图2 染色体交叉示意图 

Fig.2 Chromosome cross schematic diagram

当交叉产生的染色体中出现重复非零基因时，在交叉部分确定重复基因的基因对，并根据基因对替换非交叉部分的重复非零基因．在替换过程中，首先选择基因对中不重复非零基因，其次选择基因对中零基因，避免选择重复非零基因．经交叉，染色体1:1-4-0-0-5-0-4-6-0-0-0中出现重复基因4，染色体2:2-3-1-2-6-3-0-5-0-0-0中出现重复基因2和3，如图2(b)所示．

在交叉部分，4对应0、2对应0、3对应0，得基因对0-2-3-4;选择2替换4得，染色体1:1-2-0-0-5-0-4-6-0-0-0,4替换2、0替换3，得染色体2:4-0-1-2-6-3-0-5-0-0-0，如图2(c)所示．

当染色体不存在重复非零基因或者存在重复非零基因经修复时，检查染色体是否缺失非零基因，若缺失则在非交叉部分随机选择0基因位并替换为缺失基因;经修复后染色体1中缺少基因3，此处选择第一个0基因并替换，得染色体1:1-2-3-0-5-0-4-6-0-0-0，如图2(d)所示．

在交叉操作完成后，判断生成的染色体是否满足客户服务时间窗、车辆装载能力或车辆总数限制．

对交叉产生的染色体采用2-opt算法进行局部优化操作，以提高遗传算法的局部搜索能力．图3为2-opt算法的操作示意图，以染色体1-3-2-4-6-5-1为例，随机选取边1-3和5-6，将这两条边打开并交叉连接1-6、3-5，得1-6-4-2-3-5-1;运用2-opt算法后需判断新染色体是否满足客户服务时间窗约束、车辆装载能力约束以及车辆数约束．

图3 2-opt算法示意图   

Fig.3 2-opt algorithm diagram

4 数值实验与分析

以某冷链物流配送公司为例，运用本文开发的混合遗传算法求解模型，并与现有研究[7]方法的求解结果进行对比分析．结果表明，本文所提优化算法在求解考虑道路通行状况的冷链物流配送路径优化问题上具有优势．

4.1 实验设置

某冷链物流配送公司拥有4辆载重量为3吨的冷藏车，为市内10位客户提供冷链配送服务．运用Matlab依次进行如下操作:

(1)在(0,20)内随机生成配送点间的距离，如表1所示．

表1 配送距离矩阵  

Tab.1 Distribution distance matrix

km

(2)生成10位客户的最佳服务时间窗，根据固定的时段长度生成可接受服务时间窗，并在(0,2)之间随机生成10位客户的需求量，如表2所示．

表2 客户需求量及服务时间窗要求

Tab.2 Customer demand and service time windows

(3)最后，在(0,1]之间随机生成各配送点之间路段畅通度值，如表3所示．

表3 配送区域各路段畅通度 

Tab.3 Road unblocked degree of distribution area

配送参数c1,P，β1,c2，λ，γ，lt，ΔT,E0，取值分别如下:60元/h,12000元/t,0.14%,16.7元/h,50元/h,90元/h,3 t/h,15 min，早上5:00．冷藏车辆在标准通行条件下的行驶速度均为60km/h.

4.2 结果分析

基于道路畅通度[9]和道路畅通模糊综合评价法[10]理论，将表3中道路畅通度转化为道路通行状况，如表4所示．基于美国公路局提出的路段阻抗函数理论，将配送距离转化为路段通行状况下的车辆通行时间，如表5所示．

依据冷藏品配送的具体要求，对模型进行求解．

根据求解公式确定所需车辆数为．利用提出的混合遗传算法，设定种群规模为N=100，最大迭代次数C=200，交叉概率为Pc=0.9，变异概率Pm=0.2，α=1.2，借助Matlab7.0得到优化配送路线为:0-1-4-0、0-3-2-0、0-7-6-8-0、0-5-9-10-0，也即车辆1配送客户1、4，车辆2配送2、3，车辆3配送6、7和8，车辆4配送5、9和10，配送总成本为429.28元．

若采用文献[7]提出的优化算法，可得配送路径:0-1-4-0、0-3-2-0、0-5-6-8-0、0-7-9-10-0，也即由车辆1服务客户1、4，车辆2服务客户2、3，车辆3服务客户5、6和8，车辆4服务客户7、9和10，总成本为470.86元．

较文献[7]优化算法的求解结果，本文算法优化比例如表6所示．对比结果表明，本文算法在求解考虑道路通行状况的冷链物流路径优化方面具有优势．

表4 路段通行状况  

Tab.4 Road traffic conditions

表5 路段通行时间  

Tab.5 Road traffic time

min

表6 算法对比分析

Tab.6 Algorithm analysi

5 结语

本文探讨了冷链物流配送车辆路径优化问题，考虑了道路通行状况这一现实因素对配送时间的影响，建立了冷链物流配送车辆路径优化模型，开发了混合遗传算法，并通过与现有方法比较，验证了模型的合理性和算法的有效性