基于改进蚁群算法的医药冷链物流运输路径优化

陈鑫影,朱子青,胡明捷

(大连交通大学 计算机与通信工程学院,辽宁 大连 116028)

目前,我国医药冷链物流运输仍处于初级发展阶段,在基础设施、冷链质量控制标准等方面存在较多不足,尚未形成完整的医药冷链物流体系[1],因此,有不少学者开始研究如何改变这种现状。Qi等[2]以应急冷链物流资源调度最短时间为目标,构建了应急冷链物流调度模型。Zhang等[3]考虑到如何实现将绿色低能碳经济产品物流与现代绿色冷链物流体系优化相结合,建立了模型。Xiong[4]考虑到传统的算法优化方法搜索的时间长,提出一种改进蚁群优化算法。Liu等[5]以节约综合经济分析系统成本最低限度为系统设计主要目的,建立整数规划模型。Zhang等[6]以配送成本最小、顾客满意值最大为目标,进行求解。Ning等[7]根据其提出新的信息素平滑,增强信息素加强机制构建出新的蚁群算法。Luan等[8]将蚁群和遗传算法融合,解决供应商选择问题。Yue等[9]将惩罚策略融入蚁群算法,以解决无人汽车路径规划问题。Li等[10]将GA与TS算法相结合,解决了所提出的选址路由问题。Wang等[11]设计了一款基于启发式规则的混合GA算法求解以最小成本为目标的函数。Zhu等[12]以再次生成停止进化粒子为目标,改进了粒子群算法。Ba等[13]在需求不定的紧急情况下建立了具有时间窗的物流配送模型。

以上研究在路径优化模型方面取得了一定进展,但并没考虑到预冷环节对总成本的影响,这在一定程度上影响了最优路径的求解。为使总成本更加合理化,本文构建了医药冷链配送路径优化模型,包括车辆的固定、运输、惩罚、货损、碳排放以及制冷成本,同时采用基于遗传算法改进的蚁群优化算法(Improved Ant Colony Optimization Algorithm Based On Genetic Algorithm, IGACO)对该模型进行求解。由于IACO算法[4]存在收敛速度较慢以及易陷入局部最优的问题,本文在原算法基础上加入轮盘赌规则、单点交叉操作、变异因子,保证IGACO可以搜索的范围更广、收敛速度更快,最后通过仿真试验证明了IGACO算法的有效性。

1 模型约束条件

本文所提出医药冷链物流运输路径优化模型的问题描述如下:

(1)

(2)

(3)

(4)

(5)

其对应的约束条件为:

qi≥0,∀i∈V

(6)

eti≤Ati≤lti,i∈n

(7)

eti-Ati>0, ∀i∈V

(8)

lti-Ati<0, ∀i∈V

(9)

式中:式(1)为车辆从配送点出发服务,完成后返回配送点;式(2)为每个用户只可接受一个车的服务;式(3)为配送中心的车辆数有限,上限值为J;式(4)为路线客户总需求小于车辆自身载重上限;式(5)为决策变量,值为0或1;式(6)为客户需求量不得为负;式(7)为时间窗要求;式(8) 、式(9)为车辆或早或晚到达配送地。

2 数学模型的建立

在追求低碳大环境下,本文不仅将碳排放考虑进模型中,同时还将所需使用制冷剂的每个环节细化,从而构成改进后的制冷成本,以下为改进后的冷链配送路径模型组成。

2.1 固定成本

固定成本费用包括但却不仅仅局限在司机工资、车辆的磨损、折旧费等,因此固定成本C1可定义为:

(10)

2.2 运输成本

运输成本指车辆在实际配送服务过程中所产生的所有相关费用,包括但不局限于行驶中产生的燃油消耗以及车辆维修费用等,因此运输成本C2可定义为:

(11)

式中:Wc代表每单位重量运费价格;dij为客户i到j的距离;qi为客户需求量。

2.3 惩罚成本

惩罚成本随客户的满意度呈线性变化,同时满意度被定义为配送车辆响应客户需求所需时间的度量,若在客户期望时间中,满意度则为最高。客户的期望时间周期为[eti,lti],且每个客户都有自己单独的时间窗要求,因此惩罚成本C3可定义为:

(12)

式中:Ati表示车辆配送到达时间;n为客户数量,配送的客户满意度总值设为100;ε1、ε2代表早到、晚到对时间的窗敏感度。

2.4 碳排放成本

冷链配送车辆所产生的碳排放主要包括两个方面,首先是车辆行驶过程中燃油消耗所产生的碳排放,其次就是车辆的制冷设备所产生的碳排放。车辆的燃油消耗所产生的碳排放量与车辆自身装载重量以及配送距离的远近相关。当车辆装载量为X时,燃油消耗由e(X)表示,因此e(X)可表示为:

(13)

式中:Q为车辆满载重量;e*为满载时燃油消耗量;e0为空载时燃油消耗量。

有装载的配送车在行驶过程中所产生的碳排放量,E1可表示为:

(14)

式中:CA为二氧化碳排放系数;dij为行驶距离;vij为车辆从i到j的行驶速度。

制冷设备所产生的碳排放量E2与载重、车辆行驶距离也有密切关系,可表示为:

(15)

式中:F为制冷设备所产生的碳排放。因此,总碳排放成本C4可表示为:

(16)

式中:c0为每单位碳税价格。

2.5 货损成本

货损成本主要包含以下几个部分:在装载货物之前,应当将制冷设备进行预冷,以达到提前降低货舱温度的目的,从而降低货物因过高温度而导致的损坏。同时,设备预冷时间、卸载货物时间与货损成本有直接关系,本文设置一个腐败率函数:

R(t)=R0K-θt

(17)

式中:R0为货物初始状态时的质量;t为车辆配送货物所需要的时间;θ为货物质量对温度的敏感系数;K为产品在某个衡定温度下变质的常规速率。因此,货损成本可表示为:

(18)

式中:t0表示的是车辆出发时的时间点;t1为车辆到达目的地的时间点;θ为进行预冷后货物质量对温度的敏感系数;θ1为卸货过程中货物对温度的敏感系数;q1为每件货物的单价;tj为卸货时间。

2.6 制冷成本

制冷成本是冷链配送过程中配送车辆消耗制冷剂的成本,包括车辆提前预冷以及配送过程中制冷所产生的制冷剂消耗的费用总和。预冷操作时产生的制冷费用C61、运输过程中固定产生的制冷费用C62以及卸货过程中产生的制冷费用C63可表示为:

(19)

(20)

(21)

(22)

(23)

(24)

C6=C61+C62+C63

(25)

综上所述,冷链物流配送优化路径的总成本目标函数可表示为:

Z=Min(C1+C2+C3+C4+C5+C6)

(26)

3 基于遗传算法改进的蚁群优化算法(IGACO)

本文将Xiong等[4]所提出的IACO算法中的启发式因子放置于ACO算法中,并与遗传算法相结合,使用改进后的ACO算法作为基础解,在此基础上进行单点交叉算子的操作,并将轮盘赌策略加入其中,这种方式可以扩大搜索范围,从而达到筛选出不同适应度值的解,最后对适应度较低的解集,进一步进行变异操作,直到所有解集都达到理想的适应度值。通过遗传算法的独有特性,进而提高改进蚁群算法全局搜索能力,从而有效避免了过早陷入局部搜索最优化,同时进一步加快了算法全局的搜索收敛速度。

3.1 交叉变异策略

采取交叉操作有助于将优良的染色体传给下一代,同时起到全局搜索作用,减少局部最优可能,例如将来自两条不同的组合在随机选择位置进行分割,并交换右侧部分的元素,从而得到全新的组合,见图1。

图1 单点交叉演示图

采取变异操作对算法寻优与算法进化有着非常重要的作用,若当算法陷入局部最优时,采取变异的操作,可以跳出局部的最优算法时,变异的操作则是直接将染色体序列中的某一部分进行随机变异,对适应度较高的地区加强搜索,同时对适应度较低的部分继续进行变异操作,直到达到给定的适应度阈值,从而终止变异操作。此操作在一定程度上增加了选择的可能性,从而进一步防止算法过早陷入局部最优状态,同时提高了算法的收敛度。

在信息素更新策略中,加入一个不断变化的随机函数q*,该参数将在给定的迭代范围内随机变化,从而增加选择多样性。基于以上策略,蚁群算法信息素浓度更新将更改为:

(27)

(28)

(29)

启发式因子为:

用户检索后，进入二级目录，网页左侧为数据库分类，右侧为该数据库中包含的检索结果，此种设计可提高用户的检索效率，如图3所示。

(30)

式中:Li为蚂蚁已经到达i点的距离总长;dij为地点i到地点j的距离;djp为将来走过各点之间的距离。

综上所述,基于遗传算法改进的蚁群算法可表示为:

(31)

3.2 IGACO算法流程

IGACO算法具体操作步骤如下:

步骤一:对算法初始解进行构建,并将此解作为算法初始解集。

步骤二:对初始解进行适应度值的求解,并根据适应度设置范围筛选适应度较高的解。

步骤三:对信息素值进行更新,同时定义信息素矩阵,将矩阵中的信息素进行更新,并更新解向量,最后判断是否达到算法设定迭代次数,若没达到,返回步骤二,若达到则进行下一步。

步骤四:将信息素矩阵进行输出,并进行交叉、变异操作。进行完交叉、变异后对矩阵进行拆解,最后判断是否满足算法终止条件,若满足则输出最优解,若不满足则继续进行此步骤。

图2 IGACO算法流程图

4 试验设置与分析

本文分析了IGACO算法解决改进冷链模型的性能。IGACO的相关试验参数设置:蚂蚁数量为30只,迭代次数为500次,信息素蒸发量设置为0.2,信息素强度设置为l×108,交叉概率设置为0.8,变异概率设置为0.1。

改进模型参数见表1。

表1 模型相关的参数

4.1 收敛度对比

使用本文所提出的IGACO算法与现有的IACO算法、ACO算法、GA算法做试验对比,从对比结果可以看出IGACO算法的收敛速度更快,可以看出IGACO相对其他算法更具优势,算法收敛度对比如图3所示。可知,IGACO算法迭代数为在187次时,就已经达到最优状态,而IACO算法、ACO算法、GA算法迭代数分别于第249、385、439次时才达到最优状态。

图3 算法收敛度对比

4.2 行走路径对比

本文通过四种算法,对试验数据集进行求解,并绘制车辆配送路线图见图4～图7,可知IGACO算法配送路线所用成本相较于其余3种算法更低。

图4 IGACO算法路径图

图4试验共使用9辆车,对30个收货点进行产品配送,验证配送所用成本。每辆车配送路线分别为:0→19→10→29→0,0→13→21→5→22→0,0→15→20→9→0,0→4→24→26→7→0,0→16→23→28→27→0, 0→18→6→0, 0→1→3→23→0, 0→25→2→14→0,0→8→30→12→17→0。

图5试验共使用9辆车对30个收货点进行产品配送,验证配送所用成本。每辆车配送路线分别为: 0→18→11→17→22→0,0→10→2→19→0,0→16→9→0, 0→25→3→23→24→27→0, 0→26→24→1→30→12→0,0→13→21→15→0, 0→7→8→29→28→0,0→4→20→0,0→6→5→0。

图5 IACO算法路径图

图6试验共使用9辆车对30个收货点,进行产品配送,验证配送所用成本。每辆车配送路线分别为:0→25→12→23→3→11→0,0→13→7→14→0,0→16→5→0, 0→17→1→10→29→0,0→21→15→0,0→28→8→0,0→2→24→4→20→23→0,0→18→27→26→22→0,0→19→9→6→0。

图6 ACO算法路径图

图7试验共使用9辆车对30个收货点进行产品配送,验证配送所用成本。每辆车配送路线分别为:0→13→15→20→21→0,0→5→11→4→0,0→28→23→0,0→9→6→27→12→0,0→16→22→8→0,0→14→10→24→26→2→0,0→18→30→1→0,0→29→17→25→3→0,0→7→19→0。

以上 4 种算法中,IGACO、IACO、ACO、GA 算法求解模型总成本分别为 5 661.460 4、 5 940.018 5、6 636.764 5、 7 281.553 5 元。IGACO算法在总成本方面,较IACO、ACO、GA算法分别减少了4.9%、17.2%、28.6%。

4.3 运行时间对比

分别对IGACO算法、IACO算法、ACO算法、GA算法进行运行时间对比,每种算法均运行6次,对比结果见表2。

表2 4种算法运行时间对比 s

由表2可以看出, IGACO算法较ACO算法、GA算法、IACO算法分别提高了4.57、4.84、0.74 s,IGACO算法从运行时间上看是有提升的。

5 结论

本文对医药冷链物流运输成本模型进行改进,在制冷成本中加入预冷参数,使制冷成本的组成因素更加合理化,同时提出的IGACO算法对传统蚁群算法启发式因子进行改进,并将解作为基础解加上遗传算法中的交叉操作以及变异因子,从而扩大算法搜索范围,进一步避免算法陷入局部最优的可能。试验发现,在运行速度、总成本计算、迭代次数方面,IGACO算法均优于其他几种对比算法,具有较好的优越性和可靠性。

本文在某些方面考虑的并不是很充足,在今后工作中,冷链运输模型参数可能会得到一定程度上的优化,随着研究的继续深入,新的算法模型或许也将考虑引进新的因子,以使算法效率进一步提升,本文没有将多目标作为最终的求解目标,这将是下一个研究目标。