基于改进免疫优化算法的冷链多式联运路径优化研究
2022-10-28段力伟李震
段力伟,李震
(重庆交通大学交通运输学院,重庆 400064)
目前,随着冷链运输的迅速发展,冷链运输结构单一的问题也愈发明显。我国冷链运输90%以上由公路完成,而铁路占比不足1%[1],同时冷链运输路径不合理加剧了途中损耗。因此,优化冷链市场的运输结构,发展多式联运,发挥不同运输方式的优势,确保冷链货物的运输质量,能够更好地满足我国不断增长的冷链运输需求。
多式联运路径优化问题是一个NP-hard 问题,已有很多学者对该问题的求解做出了相关研究,如李飘等提出了一种综合k-最短路径算法和逼近理想解排序法的混合算法,以求解时变条件下的多目标路径优化模型[2];刘雪萍采用了模拟退火算法对多应急救援点、多受灾点的救援物资的运送路径选择问题进行了研究[3];刘松在蚁群算法中设计Ant-Cycle 模型来更新信息素,以最短时间为目标解决应急救援物资的路径优化问题[4];朱欣媛设计了基于遗传算法和粒子群算法的混合算法,探讨了碳排放约束下的时间模糊路径选择问题[5];Diabat 提出了一种基于禁忌搜索的周期性分配-库存问题(PDIP)的启发式算法,该算法性能优于95%以上基于列生成并考虑数据集的启发式算法[6]。
通过相关文献可以看出,目前启发式算法被广泛应用于求解多式联运路径优化问题,然而传统的启发式算法存在陷入局部最优解和优化效率低的问题。该文综合考虑冷链多式联运的特点和影响因素,采用Weibull 三参数分布函数来描述冷链货物运输途中的变质损耗变化情况,并提出了混合粒子群算法双寻优的免疫优化算法,对模型进行求解,通过对算例的分析计算表明,优化后的算法能够有效解决此类问题,并具有更快的收敛速度。
1 冷链多式联运路径优化模型构建
1.1 问题描述
以集装箱运送冷链货物,在中途节点可进行运输方式的中转,相邻节点之间有多种运输方式,中转会产生相应的时间、费用。同时,由于货物在途中运输时间不同,货物产生的损耗和制冷成本也不同。模型以总成本最小为目标,确定OD 间最佳的运输路径,并满足时限要求。
1.2 条件假设
1)货物在运输中始终处在冷藏集装箱中,作为一个整体不被分开运输。
2)运输工具与中转能力充足,能够满足这次运输。3)货物在节点能够及时开始转运工作。
1.3 符号说明
1.4 模型构建
目前在对多式联运路径优化问题的模型构建上,大多采用的是将路段选择和中转节点选择作为规划路径的(0,1)变量,以此构建目标函数为总成本最小的整数线性规划模型[7-8]。该文在现有研究的基础上,考虑损耗成本和制冷成本,以总物流成本最低,建立多式联运路径优化模型,相关成本分析如下:
1)基础运输成本CY
在使用运输工具在路径上运输时,基础运输费用与所选路径的运输距离呈正相关线性关系。
2)中转成本CZ
当时城市节点中转变量为1 时,产生中转成本。
3)损耗成本CS
该文参考Weibull 三参数分布函数来描述冷链货物途中的损耗变化情况,该函数被证明能够适用于各种情况,如物品的变质损耗情况、电子元件的失效、物品的销售寿命等[9],具有极强的普适性,其分布函数如下:
式中,α是函数的尺度因子,α>0;β是函数的形状因子,β>0;γ为函数的位置因子,t为时间。由该分布函数得到货物的损耗率,以计算损耗成本。
4)时间窗惩罚成本C(t)
约束时间内不收取惩罚费用,货物提前送达而没有超出允许最早时间时,收取相应的仓储费用,其他时间段惩罚成本无限大:
5)制冷成本CL
该文制冷成本参考相关文献[10-11]中的计算方法,通过计算冷藏车产生的热负荷换算成制冷所产生的燃油消耗,热负荷来源于车厢内外温度差,计算公式为:
其中,S为箱体表面积,通常通过车厢内表面积和外表面积求出,即。
根据以上各成本分析,加入相关约束条件,即可建立如下的冷链路径优化模型:
其中,式(4)为目标函数;式(5)表示总运输时间;式(6)为运输方式限制;式(7)为转运次数约束;式(8)-(9)为前后选择平衡约束。
2 算法设计
2.1 算法简介
免疫优化算法是利用免疫系统的多样性和维持机制来保持群体的多样性,并强调群体中个体间的信息交换,从而实现对解空间搜索的一种智能计算方法[12],在实际求解时,虽然将优秀抗体保存到记忆细胞中,使迭代全程收敛,但未能避免单个抗体的退化现象,使得算法的收敛速度受到影响。基于此,该文参考粒子群算法中双寻优的特性,创建个体最优抗体库,在每一次迭代中更新每一个抗体所经历的最优位置,并将其与每代形成的新抗体进行适应度值比较,从而更新抗体群,加快算法的收敛速度。
2.2 求解步骤
1)抗体编码。城市节点选用0 和1 编码,即经过该城市为1,否则为0;运输方式用1、2、3 进行编码,分别代表公路、铁路、水路。进行F 次编码初始化F 个抗体形成初始抗体群。抗体的编码示意图如图1 所示。
图1 粒子编码示意图
2)抗体的多样性评价。抗体适应度Av:将适应度函数设置为目标函数的倒数,并初始化抗体个体最优库。
抗体相似度Simv,s:当两个抗体编码中相同编码的位数大于设定的阈值ps,则表示这两种抗体相似。
抗体浓度Conv:由抗体与抗体之间的相似度来计算,每个抗体的浓度为群体中与该抗体相似个体占群体总数的比例。
期望繁殖概率:由抗体的适应度值和浓度计算每个抗体的期望繁殖概率,即:
其中,Av为抗体v的适应度值,θ为多样性评价参数。
形成父代群体:将抗体中期望繁殖概率最高的r个抗体存入记忆库中作为记忆细胞,期望繁殖概率最高的(F-r)个抗体构成父代群体。
3)遗传操作。遗传操作包括选择、交叉和变异。
4)更新抗体群。计算经过遗传操作形成的子代群体和记忆细胞的适应度值,更新抗体的个体最优库,并从个体最优中找出适应度最大的群体最优抗体并记录。将子代细胞的个体最优与记忆细胞结合生成新的抗体群,返回步骤2)进行下一次迭代。满足终止条件时,输出记录的群体最优抗体适应度值。
3 案例分析
3.1 案例设计
现假设有樱桃、海虾、柑橘三种农产品在运输网络中流通,运输具体信息如表1 所示,运输途中的损耗参数参考相关文献[11,13-14]。提前到达的货物将收取100 元/t·h 的仓储费用。制冷费用参数[13]中热传率R为2.49 kCal/(h·m2·℃),车厢内表面积为22.70 m2,外表面积24.67 m2,单位制冷成本e为1 元/kCal。
表1 冷链货物运输信息表
运输网络共有14 个节点城市,如图2 所示。各节点运输距离和各运输方式转运信息如表2 所示,各运输方式的具体参数如下:公路运输平均速度为90 km/h,费率为9.39 元/(TEU·km),铁路运输平均速度为60 km/h,费率基价一为572 元/(TEU·km),基价二为4.14 元/(TEU·km),水路运输平均速度为40 km/h,费率为2.34 元/(TEU·km);公路与铁路、水路互相转运的费用分别为150元/TEU、225元/TEU,时间都为0.5 h,铁路和水路转运的费用为826 元/TEU,时间为1 h。
表2 节点间路段各运输方式运输距离
图2 运输路径网络
3.2 案例求解
利用数学软件Matlab 对算例进行求解,设抗体种群规模为80 个,记忆库容量为20 个,交叉概率0.7,变异概率0.5,相似度阈值ps 为0.8,多样性评价参数θ为0.95,迭代次数100 次。同时,选用第一批货物为例使用免疫优化算法与改进后的算法进行对比,如图3 所示,路径优化结果见表3。
表3 路径优化结果
图3 算法迭代对比图
从图3 可以看出,改进的免疫优化算法可以通过对抗体染色体的变化,来描述运输方式和路段的选择优化,能够有效契合多式联运路径优化问题;与原算法相比,改进后的算法具有更快的收敛速度和更好的收敛效果。
4 结论
该文采用Weibull 分布函数来描述不同类型产品的损耗率,并构建冷链多式联运路径优化模型,进而利用粒子群算法双寻优的特点,对免疫优化算法进行改进,从而加快了算法的收敛速度。最后通过多OD 的算例进行模拟,结果证明改进后的算法能够有效地解决多式联运路径优化问题,并具有较快的收敛速度,同时在考虑损耗因素时,选用的Weibull三参数分布函数也能够对不同货物的损耗状况进行描述,具有很好的适用性。