一种基于改进遗传模拟退火算法的多式联运路径优化方法

摘要

本发明公开了一种基于改进遗传模拟退火算法的多式联运路径优化方法，属于多式联运路径优化技术领域，通过多种运输方式组合的方式处理货运工作，而多种运输方式的组合方案通过如下步骤得到：S1、依据运输路线图，列出各节点间不同运输方式的运输距离，得到距离矩阵；S2、建立多式联运路径优化模型；S3、通过改进的遗传模拟退火算法求解S2建立的多式联运路径优化模型，从而得到最优运输方案。本发明的有益效果：通过深度优先搜索算法对初始解进行优化，能够有效提高初始解质量，减少最优解不稳定情况的发生，提升优秀子代出现的速度，进而加快算法的收敛速度，提高算法效率，优化货物运输成本和运输效率。

说明书

技术领域：

本发明属于多式联运路径优化技术领域，具体涉及一种基于改进遗传模拟退火算法的多式联运路径优化方法。

背景技术：

路径优化技术是多式联运研究领域的一个重要组成部分，主要目的是减少货运过程中的运输时间和运输费用，选择一条总成本最优的多种运输方式组合的运输路径。

路径优化技术的发展在一定程度上标志着我国多式联运运输水平的高低，而路径优化方法的优劣直接影响路径优化效果。

目前，国内外许多专家学者都在致力于路径优化算法的研究，常用的优化算法主要有遗传算法、粒子群算法、模拟退火算法、蚁群优化算法、神经网络、鱼群算法、狼群算法等。

其中，遗传算法(Genetic Algorithm，GA)属于进化算法的一种，它通过模仿自然界的选择与遗传的机理来寻找最优解。遗传算法有三个基本算子：选择、交叉和变异。相比较其他优化算法，遗传算法具备与问题领域无关且快速随机的搜索能力、搜索使用评价函数启发，过程简单、具有可扩展性，容易与其他算法结合等优点。但同时，遗传算法的缺点也十分明显，如算法对初始种群的选择有一定的依赖性，在运算过程中容易陷入局部优化从而导致“早熟”现象的发生，缺乏对新空间的搜索能力。模拟退火算法(SimulatedAnnealing，SA)的思想借鉴于固体的退火原理，当固体的温度很高的时候，内能比较大，固体的内部粒子处于快速无序运动，当温度慢慢降低的过程中，固体的内能减小，粒子的慢慢趋于有序，最终，当固体处于常温时，内能达到最小，此时，粒子最为稳定。模拟退火算法便是基于这样的原理设计而成。相比较其他优化算法，模拟退火算法计算过程简单，通用，鲁棒性强，适用于并行处理，可用于求解复杂的非线性优化问题。但同时，模拟退火算法的缺点也十分明显，其收敛速度慢，执行时间长，算法性能与初始值有关及参数敏感等缺点。

针对这些不足，国内外诸多学者都尝试着提出混合算法对其进行改进，取长补短，如利用模拟退火算法的随机搜索性能和全局搜索能力来优化遗传算法，设计遗传模拟退火算法(GASA)来改善遗传算法的缺点。虽然大量的仿真结果表明了该方法的改进策略是可行且有效的，但是不足之处是，在求解多式联运路径优化的启发式算法中发现，初始解的生成通常是随机的，其中包括了诸多的不可行解，虽然在算法优化过程中通过罚函数进行惩罚，淘汰了大量不可行解，但是这种生成初始解以及对不可行解淘汰的方式，占用了大量计算资源，导致求解速度慢，最优解不稳定等问，并且在求解大规模或者可行方案数较少等情况时效果更难以接受。

发明内容

基于上述问题，本文发明提出一种改进的遗传模拟退火算法(IGASA)，通过利用深度优先搜索算法(Depth First Search，DFS)对以上混合算法的初始解生成进行了改进。

本发明的目的在于提供一种基于改进遗传模拟退火算法的多式联运路径优化方法，该方法能够既能提高货物运输效率降低运输成本，又能克服传统遗传模拟退火算法初代解质量低、收敛速度慢、最优解不稳定等不足。

为实现上述目的，本发明采用的技术方案如下：

一种基于改进遗传模拟退火算法的多式联运路径优化方法，通过多种运输方式组合完成运输作业的运输方案通过以下步骤得到：

S1、依据货物运输路线图，确定图中各站点的位置，列出站点之间的距离；

S2、建立用于多式联运路径优化的多目标模型；

S3、通过改进的遗传模拟退火算法求解步骤S2建立的多式联运路径优化模型，从而得到最优运输方案。

进一步地，所述步骤S2中，建立的用于求解多式联运路径优化问题的多目标模型，建立过程如下：

S2-1、设定目标函数，使总成本最小化，包括货物运输的运输成本、中转成本和时间成本：

式(1)中，P为运输节点的集合，i,j∈P；K为铁路运输、公路运输、水路运输三种运传输方式的集合；

S2-2、约束条件：

其中，式(3)代表在两个节点之间只能够选取一种运送方式；式(4)表示在任意节点转换运送方式时，只能由一种运送方式转换成另一种运送方式；式(5)表示运输总时间要小于客户需求时间；式(6)为决策变量约束；式(7)～式(8)表示决策变量的取值范围非1即0。

进一步地，所述步骤S3的具体过程如下：

S3-1、输入参数：运输距离、运输箱数、中转费用、运输费用、中转时间；

S3-2、初始化遗传模拟退火算法相关参数；

S3-3、用深度优先搜索算法寻找初始化可行解域，产生二分之一的初始种群，剩下的二分之一随机生成。用深度优先搜索法生成的初始种群质量优于随机生成的，能够降低搜寻种群最优的时间，但无法保证种群的多样化，所以加入二分之一随机产生的初始种群就能够保证群体的多样化；生成多条路径，设置迭代次数，k＝0；

深度优先搜索优化初始解集，寻找多式联运的可行解方法如下：

S331、输入不同运输方式对应的距离矩阵(对角线元素为0，其他位置不连通为一个极大值)D1，D2，D3；

S332、将距离矩阵D1，D2，D3，输入到get_M_P函数中得到M和P元胞数组，其中M数组为任意两点之间可选择的运输方式编号，P数组中存储的是每个点可以到达的其他节点的编号集合；

S333、通过深度搜索法构造的函数proM搜索得到若干可行解，并通过test函数判断是否经过重复的节点，若经过则放弃改解，重新搜索；

S334、得到的若干可行解构成初始化可行解域；

S3-4、计算每条当前路径的适应度；

S3-5、依据适应度选出适应度最高的初始路径；

S3-6、通过选择交叉变异方式得到的遗传种群mupop；

S361、mupop中选择最优秀的R个子代组成SS种群；

S362、基于SS种群，通过模拟退火优化算子得到temp种群；

(1)针对SS中每一个个体S1，在相同的温度下，生成H(链长)个领域解；

(2)在Metropolos函数中输入原解S1、S2；

(3)通过Metropolos准则选择性的接受新解，得到SS1，加入到temp种群中；

(4)按照降温速率进行降温；

S363、将temp和mupop组成newpop种群，计算其目标函数值，为了保持遗传种群数量popsize不变，选择最优前popsize子代构成新的mupop；

S364、开启下一轮迭代循环；

S365、选择总成本最低即目标函数最小的候选解决方案；

S366、判断k是否大于设定的迭代次数L，若是，则步骤S365得到的候选解决方案为最终最佳的解决方案，否则，返回步骤S3-4。

进一步地，所述步骤S3-4中，计算的适应度用于评估当前的解决方案，计算公式如下：

式(9)中，f

由于采用了上述技术方案，本发明取得的的有益效果是：

通过使用深度优先搜索算法来构建遗传模拟退火算法所需的初使种群，能有效提高初代解的质量，降低最优解的不稳定情况，一定程度上提高了算法效率，进而提高了多式联运路径优化的货物运输效率，降低运输成本。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的服务作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1本发明的流程示意图；

图2运输网络图；

图3传统遗传模拟退火算法运行结果；

图4传统遗传模拟退火算法迭代曲线图；

图5改进遗传模拟退火算法运行结果；

图6改进遗传模拟退火算法迭代曲线图；

图7传统遗传模拟退火算法和改进遗传模拟退火算法迭代曲线对比图。

具体实施方式

本发明的目的在于提供一种基于改进遗传模拟退火算法的多式联运路径优化方法，该方法能够克服传统遗传模拟退火算法初代解质量低、收敛速度慢、最优解不稳定等不足，不仅改善了获得多式联运路径优化的全局最优解，而且提高了收敛的速度。

下面结合具体实施例对本发明作进一步说明：

本实例所述的一种使用改进模拟退火算法处理多式联运问题的方法，通过多种运输方式组合优化完成货物运输工作，具体的路径优化方案通过如下步骤得到：

S1、依据货物运输路线图，确定图中各站点的位置，列出站点之间的距离；

S2、建立用于多式联运路径优化的多目标模型；

S3、通过改进的遗传模拟退火算法求解步骤S2建立的多式联运路径优化模型，从而得到最优运输方案。

所述步骤S2中，建立的用于求解多式联运路径优化问题的多目标模型，建立过程如下：

S2-1、设定目标函数，使总成本最小化，包括货物运输的运输成本、中转成本和时间成本：

式(1)中，P为运输节点的集合，i,j∈P；K为铁路运输、公路运输、水路运输三种运输方式的集合；

S2-2、约束条件：

其中，式(3)代表在两个节点之间只能够选取一种运送方式；式(4)表示在任意节点转换运送方式时，只能由一种运送方式转换成另一种运送方式；式(5)表示运输总时间要小于客户需求时间；式(6)为决策变量约束；式(7)～式(8)表示决策变量的取值范围非1即0。

进一步地，所述步骤S3的具体过程如下：

S3-1、输入参数：运输距离、运输箱数、中转费用、运输费用、中转时间；

S3-2、初始化遗传模拟退火算法相关参数；

S3-3、用深度优先搜索算法寻找初始化可行解域，产生二分之一的初始种群，剩下的二分之一随机生成。用深度优先搜索法生成的初不始种群质量优于随机生成的，能够降低搜寻种群最优的时间，但无法保证种群的多样化，所以加入二分之一随机产生的初始种群就能够保证群体的多样化；生成多条路径，设置迭代次数，k＝0；

深度优先搜索优化初始解集，寻找多式联运的可行解方法如下：

S321、输入不同运输方式对应的距离矩阵(对角线元素为0，其他位置不连通为一个极大值)D1，D2，D3；

S322、将距离矩阵D1，D2，D3，输入到get_M_P函数中得到M和P元胞数组，其中M数组为任意两点之间可选择的运输方式编号，P数组中存储的是每个点可以到达的其他节点的编号集合；

S323、通过深度搜索法构造的函数proM搜索得到若干可行解，并通过test函数判断是否经过重复的节点，若经过则放弃改解，重新搜索；

S324、得到的若干可行解构成初始化可行解域。

S3-4、计算每条当前路径的适应度；

S3-5、依据适应度选出适应度最高的初始路径；

S3-6、通过选择交叉变异方式得到的遗传种群mupop；

S361、mupop中选择最优秀的R个子代组成SS种群。

S362、基于SS种群，通过模拟退火优化算子得到temp种群；

(1)针对SS中每一个个体S1，在相同的温度下，生成H(链长)个领域解；

(3)在Metropolos函数中输入原解S1、S2；

(3)通过Metropolos准则选择性的接受新解，得到SS1，加入到temp种群中；

(4)按照降温速率进行降温。

S363、将temp和mupop组成newpop种群，计算其目标函数值，为了保持遗传种群数量popsize不变，选择最优前popsize子代构成新的mupop。

S364、开启下一轮迭代循环。

S365、选择总成本最低即目标函数最小的候选解决方案；

S366、判断k是否大于设定的迭代次数L，若是，则步骤S365得到的候选解决方案为最终最佳的解决方案，否则，返回步骤S3-4。进一步地，所述步骤S3-4中，计算的适应度用于评估当前的解决方案，计算公式如下：

式(9)中，f

本发明的效果可以通过以下仿真实验进一步说明：

为验证本方法的正确性和合理性，运用Matlab语言编程，在图2的路径网络模型下对该算法进行仿真，并与基本遗传模拟退火算法进行比较。设置算法的初始种群popsize＝100，最大迭代次数L＝200,交叉概率Pc＝0.8，变异概率Pm＝0.1，惩罚系数pentcof＝300；初始退火温度T

表1仿真结果对比

由表1可知，传统遗传模拟退火算法在第176次迭代找到最优解22545.08，而本文改进的遗传模拟退火算法仅在第16次迭代就找到最优解18755.45。因此，无论是寻解效果还是收敛速度，本文改进的遗传模拟退火算法相对传统遗传模拟退火算法都有着明显的优势。

通过上述对比仿真实验可以得出结论：使用本发明改进遗传模拟退火算法的路径规划效率明显优于传统遗传模拟退火算法，这说明了本发明提出的改进遗传模拟退火算法在路径优化方面的具备一定的可行性与实用性。

以上所述，仅是本发明的较佳实施例而已，并非对本发明作任何形式上的限制；任何熟悉本领域的技术人员，在不脱离本发明技术方案范围情况下，都可利用上述揭示的方法和技术内容对本发明技术方案做出许多可能的变动和修饰，或修改为等同变化的等效实施例。因此，凡是未脱离本发明技术方案的内容，依据本发明的技术实质对以上实施例所做的任何简单修改、等同替换、等效变化及修饰，均仍属于本发明技术方案保护的范围内。