1. 引言
1.1. 研究背景
冷链物流是确保食品和药品等温控商品质量与安全的关键环节。随着全球化和电商的发展,冷链物流需求激增,但面临配送路径优化和传统方法效率低下的挑战。我国政府通过基础设施建设、运输网络优化和信息化建设等措施推动冷链物流发展[1]。
2024年,国家强调科技创新和智能化手段提升冷链物流管理水平。蚁群算法因其优越的全局搜索能力被关注,但其应用多限于理论和小规模问题[2] [3]。结合模拟退火算法可增强蚁群算法的全局搜索能力,形成混合算法,解决冷链物流中局部最优问题。
本研究结合蚁群算法与SA的冷链物流配送路径优化,兼具理论和现实意义[4]。优化配送路径可降低成本和时间,提高资源利用率,保障温控商品质量和安全。智能化优化算法有助于企业在竞争中增强灵活性和应变能力,推动冷链行业的现代化和可持续发展。
1.2. 国内外研究现状
近年来,国内外学者在冷链物流领域取得显著进展。方文婷等提出一种混合蚁群算法,融合A算法和蚁群算法优势,创新信息素初始化和避免局部最优解,显著提升算法的收敛速度和优化效果[5]。郭鹏等设计了优化系统框架和数学模型,采用遗传算法求解,减轻规划人员负担[6]。郑兴无提出基于改进蚁群算法的低碳冷链物流模型,结合遗传算法变异算子,提升收敛速度[7]。
Krsti’c M等提出决策框架,用于选择冷链物流服务供应商,采用混合多准则决策模型,整合模糊因素关系与模糊轴向距离聚合测量,提高选择过程的准确性和稳健性[8]。Banglei Z等构建多目标优化模型,涵盖温度变化、货物损坏和碳约束,设计改进蚁群算法解决多目标问题,生成更多帕累托最优解。这些研究展现了冷链物流领域的创新潜力和实际应用价值[9]。
2. 问题描述
国际形势变化使物流运输在经济中的作用更突出。冷链物流配送车辆路径优化问题核心,直接影响成本和质量,涉及合理组织行车路线以实现最短里程和最低费用。
冷链物流网络复杂,节点众多。蚁群算法处理大规模优化,利用分布式计算和集群智能寻找方案[10]。适应动态变化,根据实时数据调整策略,提供动态优化方案。多目标优化,兼顾运输时间、成本和货物质量,找到综合效果最优方案。蚁群算法通过信息传递平衡新路径探索和已知路径开发,避免局部最优,找到全局最优解。
3. 建模过程
3.1. 初始建模
目标是找到运输成本和路线最优解。问题可视为旅行商问题,即从任意仓库出发,经过所有仓库后返回起点,使路径最短。然而,直接比较所有路径(n − 1)!条,很快会超过人力和一般计算器的计算能力,计算量大大增加,因计算量大而不实际。蚁群算法可用于寻找最优解。我们通过Matlab绘制以下数量图1:
Figure 1. Scheme number map of different numbers of cities
图1. 不同城市数量的方案数量图
3.2. 概念界定
以下为本问题变量在蚁群算法下的定义与解释:
1) 运输热力度:对应于蚁群算法中的信息素。指示路径优劣,影响着选择路径的概率,热力度越高,则路径会被更频繁的选择。
2) 运输热力衰减系数:对应于蚁群算法中的信息素挥发系数。此系数取值通常在(0fi1)区间内,此系数决定运输热力度在每次迭代后减少的比例。较大的衰减系数对应着较大的热力度衰减程度。
3) 运输热力留置量:对应于信息素增量。此值与路径的质量(此文中指路径长度)相关。路径留置量越大,说明司机更倾向于选择这些路径。
4) 启发式因子:用于指导运输车辆的搜索方向,通常与实际成本相关(如距离、时间)。此因子的合适选择可以提高算法效率。
5) 热力度倾向值:可描述为热力度在路径选择中的影响程度。较大的热力度倾向值会使得热力度对路径选择的影响更大,较小的热力度倾向值则会使得启发式因子的作用更加显著。
6) 启发式信息倾向值:可描述为启发式因子在路径选择中的影响程度。较大的启发式信息倾向值会使得启发式因子对路径选择的影响更大,较小的启发式信息倾向值则会使得热力度的作用更加显著。
7) 货车数量:指的是算法在每次迭代中需要参与搜索的货车数量。货车的数量直接影响搜索的全面性和收敛速度。
8) 迭代次数:指的是算法的总迭代次数。迭代次数决定了算法的运行时间和解的精确程度。
3.3. 目标函数
我们所设计的运输优化模型如下:
(1)
(2)
(3)
(4)
(5)
3.4. 假设
由于变量的条件比较多,所以此篇论文的数学模型需要建立在假设的条件下。本文假设如下:
1) 配送路线为封闭的,货物运输为单向运输。
2) 仓库的地理坐标是已知的。
3) 每辆货车有且仅运输一条线路。
4) 所有货物都符合货车的最大载重量。
5) 运输车辆的车型相同,各类配件、运输成本均相同。
6) 出发时的油箱均是满油状态。
7) 冷链制冷箱的温度在运输时是恒定的,冷联商品的损害只与运输时间有关。
8) 车辆行驶速度为匀速行驶。
9) 油箱可以支撑整体行程。
10) 所有运输路线为海拔变化幅度极低的路线。
11) 所有路线为铺装路面。
4. 符号定义
以下为本文公式表达上的符号定义(表1):
Table 1. Symbol definition
表1. 符号定义
参数 |
说明 |
C |
运输总成本 |
C1 |
固定成本 |
C2 |
货损成本 |
C3 |
制冷成本 |
C4 |
运输成本 |
T1 |
单位车辆运营成本 |
Xij |
如果货车从i行驶到j,则Xij = 1,反之为0 |
续表
T2 |
货损单位成本 |
T3 |
单位时间制冷成本 |
q |
客户需求量 |
t |
运输时间 |
T0 |
初始温度 |
5. 车辆成本与相关成本
以下为某冷链公司的车辆运输成本及其相关的成本的具体标准(表2):
Table 2. Prime cost
表2. 成本
项目 |
单价 |
燃油费用 |
7.3元/L (12 L/100km) |
人工费用 |
230.0元(含装卸费50元,含吃饭话费等费用) |
车辆折旧费用 |
115元/天 |
GPS折旧及服务费 |
8.22元每天 |
其他费用 |
58元/天(保险费用15,000元/年,轮胎费用6000元/年) |
税费 |
58元/天 |
6. 算法分析与设计
6.1. 算法设计
我们所研究的问题是典型的TSP问题以及NP-hard问题,传统算法难以对此类问题进行快速求解,所以启发式算法求解的方式是必要的。蚁群算法具有自我调节性和正反馈性,我们在选择这个算法时发现蚁群算 法可以很好的解决此类问题。但是我们在实际操作过程中发现蚁群算法会陷入局部最优解,所以我们会引入一部分模拟退火算法的思想进行融合求解[11]。
6.2. 模拟退火算法
此算法是用于寻找全局最优解的优化算法。它的灵感来自于物理学中的退火过程,即通过加热和慢慢冷却金属或玻璃以达到最稳定的结构。具体流程如下所示。
首先,我们需要给定初始温度和初始解集,然后在当前给定的温度下得出新解,计算当前函数的增量
,如果
< 0,则接受新解,反之则不接受,之后判断在此温度下是否充分搜索,如果已经充分搜索,则输出最优解,反之则降低温度重新再进行搜索[12]。
6.2.1. 温度更新公式
模拟退火算法中,温度更新公式为:
(6)
其中
是第
次迭代的温度,
是第
次迭代的温度,
是降温系数。
6.2.2. 接受概率公式
接受一个较差解的概率由以下公式给出:
(7)
其中
是当前解与新解之间的能量差(目标函数值差异),
是当前的温度。
6.2.3. 目标函数
优化问题中的目标函数通常表示为:
其中
是优化变量。
6.2.4. 初始化
算法的初始设置包括:
T0 = 初始温度
α = 降温系数
6.3. 蚁群算法
燃油货车的里程焦虑一般会低于电力货车,但是在长距离配送情况下,这种里程焦虑会普遍散播在司机之中,成本也是公司重点考虑的指标之一,因此,最近的配送路线被公司和司机选择的概率也会增加。当仓库
时货车从仓库i配送到仓库j的概率为:
(8)
否则,概率为0。
α为信息素因子,可以表示货车运动过程中路径上积累的运输热力度在指示货车搜索中的相对重要程度。取值范围通常在[1, 4]之间,如果选择的数值过大,选择已经走过的路可能性会变大,随机搜索性可能会减弱,若选择过小,就容易陷入纯粹的随机搜索,并且陷入局部最优的情况会大幅度升高。
β为启发式因子,可以表示为启发式信息在指导蚁群搜索中的相对重要程度,在货车的探索过程中,其取值范围在[0, 5]之间,如果数值选择过大,会加快收敛速度,但是会更容易地陷入局部最优解,若数值选择过小,则很难选择到最优解的情况。
为在时间t时的运输热力度(信息素浓度),
表示货车未访问的仓库集合。
为仓库i
与仓库j之间距离的倒数,可以用以下方程表示:
(9)
货车选择下一个仓库的影响因素主要由
与
决定。而(5)式中的分母所代表的含义为货车可能访
问的所有仓库的数量之和。
当货车有了这个选择的概率能力后,我们需要控制下流程问题,就能解决基本的问题了。我们需要回顾下蚁群算法的流程:
1) 初始化
与
。
2) 每一辆货车通过以上概率公式选择下一个可能配送的仓库。
3) 记录下货车行驶的路线与距离。
4) 更新信息素矩阵。
5) 若未达到终止条件,则返回第二步。
此算法更新信息素的公式为:
(10)
是运输热力留置量的挥发速度。
为运输热力度的值,m为货车数量。在每个迭代周期后更新信息素便可。
6.4. 混合算法
6.4.1. 前期准备
首先,我们选取了京津冀地区的几个运输仓库作为运输节点。见下图2:
Figure 2. Satellite coordinate map of the Beijing-Tianjin-Hebei warehouse
图2. 京津冀仓库卫星坐标图
如图3所示,我们将几个仓库等比例缩放,并标注了相应的坐标,这样可以方便我们去进行计算。
Figure 3. Warehouse node coordinate diagram
图3. 仓库节点坐标图
6.4.2. 计算默认最短距离
我们通过将城市坐标数据导入至MATLAB,并利用蚁群算法进行路径优化。在这次实验中,我们没有预设起点,而是让算法在所有城市之间自由选择路径,以寻找最短距离。蚁群算法通过模拟蚂蚁在城市间的移动,并根据每次路径搜索中得到的信息素更新来优化路径。经过多次迭代和计算,我们得出了最终的最短路径图。在这一过程中,经过算法的优化处理,我们计算出的最短路径长度为41.59单位距离,约合415.9公里。这一结果表明,在不设置起点的情况下,蚁群算法能够有效地寻找出一个接近最优的解决方案,并且能够准确地计算出城市间的最短路径。
Figure 4. Unoptimized fitness curves of the ant colony algorithm
图4. 未经优化的蚁群算法适应度曲线
Figure 5. Unoptimized ant colony algorithm shortest path map
图5. 未经优化的蚁群算法最短路径图
6.4.3. 适应度进化曲线
我们同时得到了此个路线迭代的适应度进化曲线,适应度曲线表示每一代蚁群算法迭代过程中,最佳路 径的长度(即总距离)随迭代次数的变化情况。在代码中,Lbest数组记录了每一代的最佳路径长度。
算法初期,随机路径选择使信息素作用渐显,蚂蚁发现更短路径,适应度曲线显著下降。随着迭代,信息素更新使路径选择集中,适应度曲线下降减缓,算法趋于收敛。适应度曲线平稳时,最佳路径长度稳定,表明算法达到接近最优解。适应度曲线分析显示初期快速下降、随后平稳收敛及可能的局部最优问题,提供算法性能信息,需调整参数或改进策略以提高性能。图4显示图5适应度曲线无异常,41.59单位距离可视为最短运输距离。
6.4.4. 加入起点计算
多次运行蚁群算法后,分析路径并绘制适应度曲线,确定41.59单位距离为最优标准。验证算法有效性,选择仓库(6.5, 7.1)为起点,保持参数不变,计算结果为41.93单位距离,与最优距离相差0.34单位,显示特定起点下算法性能与全局最优解的差异。
这个差距虽然相对较小,但仍然值得关注,因为它可能反映出算法在特定起点下的性能表现与全局最优解之间的差异。最终的结果如下图6所示:
Figure 6. Unoptimized colony algorithm and select the shortest path map of the starting point
图6. 未经优化的蚁群算法并选取起点的最短路径图
Figure 7. Unoptimized ant colony algorithm and pick the fitness curve of the starting point
图7. 未经优化的蚁群算法并选取起点的适应度曲线
在前置条件不变时出现异常,需考虑蚁群算法是否陷入局部最优解。这种情况下,适应度进化曲线显示突然平稳,如图7,表明可能陷入局部最优解。0.34差距在全国范围内成本巨大,运输公司难以承担。为跳出局部最优解,我们采用模拟退火算法优化蚁群算法。
6.4.5. 混合优化算法设计
该混合算法结合了蚁群算法(ACO)和模拟退火算法(SA),以提高路径优化的效果。以下是详细的流程内容和对混合算法的分析。
6.4.6. 设置参数
1) 仓库数量:定义问题中的仓库总数。
2) 货车数量:设置参与路径搜索的货车数量。
3) 迭代次数:定义算法运行的总迭代次数。
4) 信息素重要性因子:信息素对路径选择的影响程度。
5) 启发式因子:启发式信息对路径选择的影响程度。
6) 运输热力衰减量:运输热力度的挥发速率,控制信息素衰减。
7) 运输热力留置量:信息素的增加强度。
8) 模拟退火初始温度:模拟退火算法的初始温度。
9) 模拟退火最终温度:模拟退火算法的结束温度。
10) 模拟退火降温系数:模拟退火算法的温度衰减系数。
11) 生成仓库坐标:生成每个仓库的坐标,用于计算仓库间的距离。
12) 计算距离矩阵:根据仓库坐标计算每对仓库之间的距离矩。
13) 初始化信息素矩阵:设置信息素矩阵的初始值。
14) 初始化最优路径:设定初始的最优路径为无解或无路径。
15) 初始化适应度变化记录:用于记录每次迭代的适应度值变化情况。
6.4.7. 流程
以下为整体算法的操作流程图(图8):
Figure 8. Flow chart was calculated using the ant colony algorithm optimized by simulated annealing
图8. 利用模拟退火优化后的蚁群算法计算流程图
6.4.8. 混合算法计算
在将模拟退火算法的思想融合进蚁群算法的过程中,我们对算法进行了多次实验,以评估这种混合方法的效果。具体的流程包括在蚁群算法的每一轮迭代后应用模拟退火策略,对路径进行进一步优化。这种融合旨在结合蚁群算法在全局搜索中的优势和模拟退火算法在局部优化中的特长,以提高最终解的质量和算法的整体性能。经过了多次计算,得到了多次实验结果,而实验结果的值均与第一次结果相同。第一次的优化算法最短路径实验结果如图9所示,优化算法适应度曲线如图10所示。
第一次实验结果:
Figure 9. Results of the optimization algorithm shortest path
图9. 优化算法最短路径实验结果
Figure 10. Experimental results of the optimization algorithm fitness curves
图10. 优化算法适应度曲线实验结果
7. 结果分析
在将模拟退火算法引入蚁群算法的过程中,我们进行了四次独立的实验,以评估这一混合算法的性能和稳定性。每次实验均获得了相同的结果,即最终路径长度稳定在41.59个单位距离,这个值正是我们最初设定的期望值。这表明,通过模拟退火算法的优化,我们成功地达到了全局最优解,并且每次实验的一致性验证了混合算法的可靠性。
具体的来说,我们的实验结果显示出以下内容:
1) 一致的最优解:在四次实验中,每次运行均成功找到了全局最优解,即路径长度为41.59。这说明模拟退火算法有效地增强了蚁群算法的全局搜索能力,使得每次运行都能避开局部最优,找到全局最优解。
2) 适应度进化曲线观察:尽管适应度进化曲线在第四次实验中出现了突然趋于平稳的现象,并且存在一些异常值,但这一现象并未影响最终的全局最优解的获取。模拟退火算法在局部搜索中发挥了重要作用,即使在面对曲线的异常波动时,仍能够保持全局最优解的稳定性。
通过将415.9 km与419.3 km以及相关车辆成本带入(1) (4)式可以得出相关成本:
415.9 km:运输成本C = 1551.2元
419.3 km:运输成本C = 1554.22元
成本节约:
通过计算得知,利用模拟退火优化后的蚁群算法,比最初的蚁群算法计算出的成本每公里节约成本0.88元,每1000公里节约约880元。
根据实验结果,我们可以做出以下分析:
引入模拟退火算法于蚁群算法,旨在利用其局部搜索优化能力,避免陷入局部最优。实验表明,模拟退火的引入显著增强了全局优化能力,确保每次实验找到相同全局最优解。适应度曲线的异常波动不改全局最优解的稳定性,显示算法在复杂情况下仍高效。适应度进化曲线的异常适应度进化曲线的突然趋于平稳以及出现异常值,可能是由于以下几个原因:
1) 算法收敛性:在某些情况下,适应度曲线的平稳现象可能表明算法已经收敛到某个局部最优解的稳定状态。但由于模拟退火算法的局部优化功能,这种情况并没有阻止我们找到全局最优解。
2) 异常值的影响:虽然第四次实验中出现了异常值,但这些异常值并未影响最终的全局最优解。这说明即使存在异常情况,模拟退火算法的强大优化能力仍然能够保证最终解的质量。
8. 结论与应用
8.1. 结论
结合模拟退火算法和蚁群算法的混合方法展示了其在路径优化问题中的显著优势,不仅在全局最优解的寻找上表现出色,而且在处理复杂问题时展现了良好的稳定性。
我们利用模拟退火算法所改进的蚁群优化算法在实际应用中表现出色。通过实验对比分析,我们可以看出,优化算法显著降低了运输成本,表明其优化效果良好。除了直接的成本节省,优化算法还可能带来其他好处,如提高运输效率、减少车辆使用时间、降低燃料消耗等。这些额外的优势进一步提升了算法的实际应用价值。
8.2. 应用
在我们的实验中,我们随机生成了50个点,这些点被视为城市或仓库,构成了我们要解决的路径优化问题的基础。这些城市/仓库的坐标通过MATLAB生成,并且坐标在二维平面上随机分布,确保了问题的多样性和复杂性。这些点的具体位置对于路径规划问题的难度和复杂度有着直接的影响,随机分布的点能有效地模拟实际应用中的多变环境。
如图11所示,在这些50个点中,我们进一步随机选取了一个点作为起点。起点的选择是路径优化问题中的一个关键环节,它决定了算法的起始位置和初始条件。在实际应用中,起点的选择可能会影响路径的规划和优化结果。因此,我们通过随机选择起点来引入一定的随机性,以便测试算法在不同初始条件下的表现和稳定性。
Figure 11. Coordinate plot of random 50 position points
图11. 随机50个位置点坐标图
8.3. 蚁群算法
通过运行蚁群算法,并经过多次迭代和优化,我们最终得到了一个长度为525.37个单位的最优路径。这个路径是算法在多次搜索和比较中得出的,它表示了从起点出发,依次访问所有点并返回起点的最短可能路线。
然而,尽管我们得到了这个看似最优的路径,但我们必须承认,我们无法直接判断这个解是否确实是全局最优解。蚁群算法虽然具有强大的全局搜索能力,但在复杂的搜索空间中,仍然存在陷入局部最优的风险。此外,由于问题的复杂性和计算资源的限制,我们无法穷举所有可能的路径来验证当前解的全局最优性。
Figure 12. The fitness evolution curves obtained using the initial ant colony algorithm
图12. 利用初始蚁群算法得到的适应度进化曲线
如图12所示,适应度曲线的斜率变化突然较大,可能表明算法的收敛速度过快。虽然这看似是一种积极的结果,但在实际情况中,过快的收敛有时会导致算法在搜索空间中停留在局部最优解附近,而未能充分探索整个解空间。
8.4. 混合算法求解
在模拟退火优化阶段,我们设置了适当的初始温度和降温速率,以确保搜索过程既能够避免陷入局部最优,又能在全局范围内逐渐收敛。我们采用了在蚁群算法生成的路径基础上进行扰动和调整的策略,通过模拟退火的随机跳跃和接受概率机制,探索可能的更优解。
我们得到了更加优质的全局最优解,如图13所计算出的最短路线单位长度为510.85,我们所得到的最优路径,展示了这一优化策略在解决复杂路径问题中的潜力和优势。
Figure 13. The shortest path diagram after solved by the hybrid algorithm
图13. 混合算法求解后的最短路径图
8.5. 成本节约
我们首先将通过优化算法得到的最优路径带入到成本计算模型中。假设该模型由若干公式组成,标记为(1)至(4),用于计算每条路径的运输成本。这些公式可能包括固定成本、变量成本、距离成本等。根据这些公式,我们将得到优化后的路径对应的具体成本。这一步骤涉及将优化算法提供的路径信息(如每个城市之间的距离、行驶时间等)输入到成本计算模型中,从而得出实际的运输费用。
通过将优化算法应用于实际的运输成本计算,我们验证了算法在减少运输费用方面的有效性。在假设的30天运输周期中,算法所得到的最优路线能够为公司每辆运输车辆节省约928.6元的成本。
致 谢
在此,衷心感谢高校对项目资金的大力扶持,资助为研究工作提供了坚实物质基础,助力项目顺利推进。向无私资助项目的支持者深表谢意。
特别感谢项目中给予指导和帮助的专家、老师,你们的宝贵建议助我们快速解决困难与挑战,专业与热情给我们诸多启发。
另还要感谢允许我们转载、引用资料、图片、文献的研究者和机构,你们的开放与共享提供了丰富素材与广阔视野,让工作更深入全面。对提供研究设想的同僚也满怀感激,你们的创意和智慧点燃我们思维,为项目注入创新活力。
总之,感谢所有在项目过程中支持、帮助、鼓励我们的人们,是你们的共同努力让项目取得如今成果。