基于改进遗传算法的冷链物流配送路径优化

近年来，我国电商行业的蓬勃发展，使得网上购物成为人们的主要购物消费渠道，人们不仅在网上购买日用品、美妆产品，还购买生鲜食物产品。网购的渠道也从淘宝、京东等大型购物平台，逐渐向直播带货平台进行分流，此种网购趋势使得对物流行业的需求逐渐增加。物流运输作为整个网购流程的核心枢纽，占据着较为重要的位置。冷链物流是指在冷藏条件下进行的物流活动，它涉及食品、药品等易腐、需要恒温保存的商品。冷链物流配送路径优化是物流管理中的一个重要环节，直接影响物流成本、时效和服务质量。遗传算法作为一种启发式搜索算法，具有良好的全局寻优能力，已被广泛应用于各类优化问题。冷链物流配送路径优化问题可描述为：在满足冷藏商品质量约束的条件下，规划一组最优的配送路径，使得总的配送成本（包括运输成本、冷藏成本、时间惩罚成本等）最小化。该问题具有多约束、非线性等特点，传统的优化方法难以有效求解。

 

基于此，本文将以冷链物流配送路径作为研究对象，通过优化配送车辆的路线，降低冷链运输造成的成本问题，进而提高物流运输的配送效率，且一定程度上减少碳排放量，降低物流运输对环境的污染，具有较为重要的现实意义。本文中构建的模型算法设计，融合了遗传算法和烟花算法，设计出一种改进型烟花遗传算法（IFWGA），该算法可以有效地解决冷链物流配送的车辆路径问题。借助Matlab2021a进行编码运算，并通过算例对结果进行验证，可得出此算法研究的应用结论。该算法能够跟随快速发展的物流行业趋势，借助软时间窗的约束条件，为冷链配送提供全新的优化路径，借此增强物流企业的运输效益，帮助电商企业降低运输成本，使物流企业凝练核心竞争力，有效地推动物流行业的快速发展。

 

二、模型构建与算法设计

1. 问题描述

本文进行的冷链物流配送模型研究中，需要从多个成本方面进行考量，其中已知运送生鲜农产品的冷链物流配送车型及相关车型数量，同时要保证算法研究中能够满足客户的运输需求，并需在客户要求的期望送达时间内完成运送。基于上述条件方可建立运输路径问题的数学模型。确保研究能够将运输成本控制在最低范围内，并规划和计算出科学的物流配送方案，借此降低运输过程中产生的碳排放，并尽量减少由于车辆开关门造成的货物损耗，其中需要从成本控制等方面创建模型，并从以下四个方面进行综合考量。

 

(1）固定成本

本研究中固定成本主要有车辆费用、驾驶员人工费用及一系列车辆固定成本等，若该配送中心共有K辆车，则配送过程中的固定成本可用C1表示，见式（1）。

 

 

(2）运输成本

由于本研究需要对运输路径进行规划，因此运输成本属于变量，需要根据车辆的行驶距离进行确定，将由距离决定的运输成本表示为C2，见式（2）。

 

 

式中：ckij是客户i与客户j由k车配送需要产生的成本；dij是客户i与客户j的间距。

 

(3）惩罚成本

该数学模型构建中，软时间窗概念定义为客户可接受的迟到时间范围，惩罚成本C3见式(3)。

 

式（3）中：[eti,lti]为硬时间窗；[ei,li]为软时间窗；yik的值决定j车是否派送了客户i(i取值为0或1,1表示配送，0表示不配送）；P1为单价；tik是实际配送过程中k车到达坐标点i的时间；μ1、μ2是预先设置的惩罚系数；qi是i客户对生鲜农产品的需求量；M表示一个极大值。

 

(4）制冷成本

该成本计算可引入转化系数作为参考，将热负荷作为关门状态下制冷剂的消耗成本，其中用Qk1来表示k车运行中产生的热负荷，Qk2表示k车开门状态产生的热量，C51表示关门状态下的制冷成本，C52表示开关门过程中的制冷成本，见式（4）-式（7）。

 

式（4）-式（7）中：P2表示标准距离行驶成本；S为车厢的表面积；Sw、Sn分别为外、内部的车厢面积；R表示传热系数；Tw、Tn分别为外、内部的温度；tij表示客户i到客户j的时间；α代表了开门的频率，其取值见表1。

 

  

 

表1 开门频度系数  下载原图

 

 

因此，总制冷成本C5见式（8）。

 

 

2. 改进遗传算法设计

由于车辆路径问题中具有多种构成因素，且跟随构成因素的不同组合，可形成不同的目标。本研究中选择遗传算法进行改进设计，是因为遗传算法作为具有较强全局搜索能力的强智能算法，其应用范围更为广泛。因此在传统遗传算法基础上引入改进策略，可有效避免遗传操作过程中丢失潜在的最优解，且能够借此弥补出现的局部搜索不到位情况，另外该算法中存在的易早熟收敛、局部陷落等不足之处，可通过烟花算法进行补足，借助其自身具有的高强寻优能力，辅助遗传算法的改进。

 

所谓遗传算法是模仿自然界中繁衍的数学运算方法，其具有操作简单，寻优能力强的特性。本文采用遗传算法为主框架，力求利用遗传算法优势特点，结合烟花算法爆炸性优势，进行巧妙的改进，在众多解决方式中选择最接近最优解的途径，并进行综合比较选择适宜的路径。本研究中的烟花算法的变异算子设计为两种步长，根据步长长短分别定义为LSMO和SSMO。将在后文中进行变异算子的形态切换，用以计算动态概率值，且研究中根据迭代规律，前期将多使用LSMO，后期多使用SSMO。

 

3. 算法操作

遗传算法作为常用的全局搜索算法之一，可将可行性解决方案按照一定的编码顺序进行组合编码，形成染色体组合，并在计算中针对每个染色体进行适应度的计算，最终通过交叉、变异等操作得出全新的结论，此研究过程中可发现具有最大适应度函数的染色体。此种算法操作过程，在种群的不断繁衍中，能够逐渐淘汰适应度低的个体，而将适应度高的个体进行保存，便于后续进行复制操作。因此，遗传算法也包含上述染色体复制繁殖的特性。

 

(1）染色体编码

作为遗传算法的第一步骤，其需根据实际问题进行相应的数据处理，便于选择编码方式，为后续的交叉等操作提供依据。其中函数模型构建中，常用的编码方式有二进制编码、自然数编码、浮点数编码等。其中利用数字1和0进行组合的二进制编码较为容易实现，但编码长度会受到搜索效率的影响，而自然数编码也较为常用，能够对问题进行直接编码，能够使编码结果明确清晰，亦具有更大的操作空间，搜索效果较好。因此，对遗传算法进行改进中，本研究采用的编码方式为自然数编码。

 

(2）选择

该操作亦是遗传算法中的染色体复制环节，符合优胜劣汰标准，被选中的个体可直接进行复制，考量个体方案的适应度，其中适应度大的方案被选择的几率相应升高，常见的选择操作方法有轮盘赌选择策略、精英保留策略、锦标赛选择策略等，本研究中选择采用轮盘赌选择策略，并在适当的时候引入精英保留策略。其中轮盘赌选择策略能够对具有较高适应度的个体进行选择，但其亦存在错选的概率，易导致优秀的路径被遗漏，此选择方法的最大优势是可使局部最优化。而精英保留策略则主要是为了保证最优秀的个体存留，采用直选的方式，防止优秀的方案被交叉变异，此种选择方法虽能够解决局部最优，但易使全局的搜索能力变差。将上述两种操作方法进行组合，可形成优势互补效果。

 

(3）交叉

交叉操作的本质是重组，即对两个个体进行交叉操作，使其能够形成全新的算法，通过此种交叉方式能够对问题的解法空间进行不断的搜索，便于得出最优答案，并且此种交叉操作能够便于个性化的设计。常见的交叉方式有单点、多点、均匀交叉等。其中单点交叉操作较为简单，只需进行一次交叉，针对某一节点和条件进行交叉即可，适应性较小。多点交叉则是在单点交叉基础上进行的交叉点的变量增加，能够进行全局的优化操作。均匀交叉主要指增加问题的多样性条件，并基于全局搜索能力的考量，进行交叉选择，此种交叉结果的质量难以控制。本研究中采用多点交叉的方式，进行反复对比选择。

 

(4）变异

变异操作中为增强个体方案的适应度，可对全局进行搜索，并给予交叉操作，进行有效的交叉变异，其往往与交叉共同利用，形成对遗传算法的改进，提升其全局搜索能力及局部搜索能力。其中常用的变异方式有基本位变异、均匀变异、高斯变异等。

 

(5）烟花算法

利用烟花算法对遗传算法进行改进。具体步骤如下。

 

①计算爆炸数目。

爆炸数目的确定及半径的计算需根据烟花种群及适应度进行计算，其中爆炸数目越多，适应度越强，呈正比关系。爆炸火花数目si见式（9）。

 

公式（9）中：f(xi)表示个体的适应度值；ymax是当前种群中适应度的最大值；M为控量常数（M≤10）；常数ε为防止除数为0而存在。

 

其中Smax为最大火花数目，Smin为最小火花数目，见式（10）、式（11）。

 

 

②计算爆炸半径。

为常量值，爆炸半径Ai见式（12）。

 

③产生变异火花。

变异火花可根据路径优化特点，起到平衡搜索能力的作用。因此本研究中涉及两种步长差异条件，第一种变异算子步长为1(SSMO），第二种变异步长为6(LSMO）。其中maxgen表示最大迭代次数，计算见式（13）。

 

4. 改进要素

(1）约束条件

在改进遗传算法进行车辆路径问题研究中，需要将约束条件作为求解问题的限定标准，算法的改进需在约束条件基础上进行操作，不得出现超出约束条件的情况。约束条件的存在，使不同问题求解的方法有了限定标准。在车辆路径问题研究中，常见的约束条件有：①车辆载重约束。装载的货物不得超出车辆的最大载物重量，此为国家标准的运输硬性要求。②车辆行驶距离约束。此要求主要是限定车辆的行驶距离，确保运送路线规划中不超出最大行驶距离，避免影响配送效率。③客户点服务约束。需要根据整体的运送要求，确保每个客户点都能够有运输的车辆，保证冷链运输的覆盖率。④车辆出发点约束。所有车辆的起始点都应从货物中心出发，并在完成运输任务后即刻返回中心停车区域。⑤客户服务时间约束。对于客户特定规定的配送运输时间，要进行单独的算法设定，不可过早或过晚，避免影响冷链运输的服务质量。

 

(2）目标函数

在遗传算法改进过程中，设定的目标函数需要跟最终的运输目标具有一致性，并根据不同的运输条件及需求，建立不同的函数目标，函数目标具有不唯一性，可由一个或多个组成，在改进算法中常见的目标函数有：①配送距离最短化。该目标主要是要求所有车辆在运输过程中能够保证总距离最短。②配送成本最小化。此目标是优化运输路径的最终目的，即降低运输成本，其中成本包括车辆维护的固定成本，车辆运输成本，以及其他成本等。③车辆数目最少化。该目标力求在完成配送任务过程中，尽量提升车辆的装载能力，利用最少的车辆数目完成运输任务。

 

(3）客户需求

在路径问题构成中，其可作为算法函数的限定条件，为求解问题进行特殊性设定，计算中需依据不同客户需求进行算法调整，建立算法模型。其中客户需求可总结如下：①确定客户需求量。货物需求量决定着车辆运输的路径及车辆数目，其能够决定车辆的实际算法设定。②货物装载需求。该需求决定着车辆的路径，在交叉筛选中，可设定可装载和不装载两种限定条件，并分别制定路线规划，其中装载的卸货时间需计算在总体规划内容中。③客户的时间窗需求。该需求决定着路线规划问题，可作为算法中的必要条件和优先级，为路线整体算法进行时间范围限定。④多辆车服务需求。客户有权利要求进行单车冷链运输服务，此种服务要求一定程度上增加了车辆的运输成本，但也会同样减少多车服务的条件限定。

 

三、实例分析

1. 实验数据

实验以某生鲜连锁超市为载体，利用IFWGA算法尝试优化超市的生鲜货物物流配送路径问题，探究此种算法的优化可行性。由于该生鲜连锁超市根据GPS导航地图数据反馈，检索出分店区域范围，选定中点位置为配送中心，并模拟设定客户需求及时间窗，根据市面上对于生鲜冷链的配送要求进行配送，保证每日上午完成配送。因此，时间可限定为6:00-12:00之间，并根据车容量实载情况，随机生成需求量派单，货物运送的计数单位为吨。

 

2. 实验结果

实验中根据不同算法截取的不同结果路径图（图1），分别代表着GA、FWA-EI、IFWGA和FWGA算法的结果路径演示结果，且进行了十次求解，便于进行数据对比。

 

质量结果对比分析可发现IFWGA多次求解均获得最优解，相比GA、FWA-EI和FWGA结果都有明显的优化，仅一次略逊于FWGA的运行结果；总成本结果分析中（表2),IFWGA比GA优化了39.8%，比FWA-EI优化了16.9%，比FWGA优化了16.2%，具有较大的成本控制优势。运行时间对比可见表3。各算法的平均运行时间如下：GA=54.38s;FWA-EI=76.23s;FWGA=65.72s;IFWGA=63.44s。IFWGA运行时间较FWGA及FWA-EI算法有明显优化效果，但却比GA运行时间稍长，但IFWGA在实际运行中的求解质量高于其他算法。

  

 

 

 

 

  

 

 

 

 

图1 4种算法路径图   

 

四、结语

通过对遗传算法进行改进，借助适应度的调整及烟花算法的优化，能够通过上述函数总结出种群的最优解，为实验寻求到最佳适应度方案。通过时间结果对比分析，可发现传统遗传算法收效甚微，只能得出局部最优解，且求得的质量不高。而采用烟花算法对遗传算法进行改进之后，能够得到多数函数收敛，更具适应性，可实现全局搜索能力和局部搜索能力的提升，增强算法的性能。

 

基于上述算法模型的改进研究，将其应用到物流运输领域中，可以有效的解决车辆路径规划问题，为生鲜冷链的运输寻求到最佳运输路径。通过将改进后的遗传算法应用到冷链物流配送路径优化中，在容量约束条件下，若客户未提出加急服务要求，可应用此改进算法进行路线规划；该算法的应用能够有效的为物流行业提供全新的配送思路，增强冷链运送的服务质量；并通过改进算法应用，为物流运输寻找到更加高效的配送方式，借助数据模型的计算，能够快速为物流公司提供最佳配送路线，减少规划路线的时间，减少运输成本，有助于提高物流冷链的收益。此外，此种路线上的优化，能够有效的增加客户冷链运送的满意度，优化客户的消费体验。