MGASA算法求解物流中货物最佳运输路线

0 引言

随着我国经济建设的发展,我国的交通越来越便利,从一个城市到另一个城市,我们有各种交通工具盒路径可供选择,虽然便利了出行,但同时也给当前的物流公司设置了难题。那就是如何在各种交通工具、运输路径中选择,才能在保证及时的前提小尽量减少成本,已使利润最大化。这也是本文所要研究的内容。

1 最优路径查询问题的数学模型

我们首先将问题抽象,假定我国交通地图上的每个城市为一个节点,城市与城市之间连线标识两个城市之间的一种交通运输方式。当然如果A地与B地之间有多种运输方式那汕头到清远物流么将会有多条连线。每种运输方式都有他的时间消耗值与运输成本。如图所示。

对于没有直接运输方式可达的两个城市,我们也假定有一种运输方式,置其运输成本和运输时间为无穷大。这样,从我们的网络图上,任意连个点之间都有连接,那么我们寻求A到B路径的时候就可以随机生成,例如A-B,或A-C-B,或A-D-B,或A-D-E-B等等,然后我们只要计算他们的时间、成本,找出满足时间限制的最低成本的运输路径即可。各个节点以及他们之间的运输成本和时间成本我们将存储在两个三维维数组中。

运输成本Costs[i][j][k]标识节点i到节点j之间的第k中运输方式的运输成本,Time[i][j][k]标识节点i到节点j之间的地k中运输方式的时间成本。在实际中Costs[j][i][k]标识虽然是同一条路段的同一种运输方式,但是由于运输方向的不同,其成本也可能存在很大的差异。

生成路径步骤:

随机生成0=

For I 从0 到 CountT

begin

随机获得一个不再tempPat广州到昌吉物流hT,且不等于S和E的节点tempT

tempPathT=tempPathT+tempt

end

PathS-E=S+tempPathT+E,至此,路径已经生成完毕,下一步就是随机选择路径上两个节点之间的路径,设置起始运输的其实城市节点为S,目的地节点为E,中间节点为T,按照离S节点的深度分为T1,T2,T3……,那么构成一条的从S到E的一条完整的路径我们就可以表示为: PathS-E=S-T1-T2-……Tn-E。从S-T1两节点之间我们随机选择第r中运输方式,那么从S-T1的运输成本CostS-T1通过查询Costs[i][j][k]可以获得,并且标识为P0Cost,从S-T1的时间成本TimeS-T1通过查询Time[i][j][k]可以获得,并且标识为P0Time,那么以此类推,从S到E的总的运输成本可以标识为PCost=P0Cost+P1Cost+……+PnCost,其时间总成本可以标识为PTime=P0Time+P1Time+……+PnTime。

假定约束为货物必须在N天抵达

目标min∑Cost[i][j][k]

约束∑Time[i][j][k]<=N

2 算法分析

模拟退火算法是模拟对固体退火的过程,采用Meteropolis接受准则,并用一组称为冷却进度表的参数控制算法进程,使算法在多项式时间里给出一个近似最优解。模拟退火算法能以一定的概率接收目标函数值不太好的状态。即算法不但往好的方向走也可向差的方向走;这使得算法即便落入局部最优的陷阱中,理论上经过足够长的时间后也可跳出来从而收敛到全局最优解。模拟退火算法的主要缺点是为得到一个好的近似最优解,需要进行反复迭代运算,当问题的规模很大时缺乏可行的解决途径。

遗传算法(Genetic Algorithms, GA)的优点是:不受搜索空间的限制性假设的约束,不必要求诸如连续性、导数存在和单峰的假设,并且具有内在的并行性,收敛速度快。遗传算法在搜索的初期,由于优良个体急剧增加使种群失去多样性,容易造成程序陷入局部,达不到全局最优解的现象。遗传算法的另一个缺陷是“GA欺骗”问题,即在GA的搜索过程中,有可能搜索到最优解然后又发散出去的现象。

本文将模拟退火算法和遗传算法结合来构造一种混合遗传模拟退火算法(Mixed Genetic-Simulated Annealing Algorithms, MGASA)。把遗传算法运行早期也作为模拟退火算法的初期,给适应度添加一个系数λ,使λ与模拟退火的温度成一定程度的反比关系,取λ=exp -(fj-fi)tk」,由于模拟退火算法早期温度比较高,λ较小,这样就使个体适应度差异缩小,避免初期个别好的个体的后代充斥整个种群,导致早熟;在遗传算深圳到武威物流法后期,模拟退火的温度也在不断的下降,从而使得λ的值不断增大,使适应度相近的个体适应度差异放大,从而使得优秀大额个体优势更明显。从而避免了由于遗传算法后期适应度趋向一致,优秀的个体在产生后代时,优势不明显,使整个种群进化停滞不前。在遗传算法中种群的选取时,以模拟退火的接受概率Aij(tk)=min{1,exp(-)}接受或拒绝群体邻域的某一状态是否作为新种群的一员。另在遗传算法基因发生变异时,发生变异的概率也是选取了模拟退火的接受概率。

3 求解最低运输成本的混合遗传模拟退火算法

3.1 模拟退火参数的选择设定

在进行模拟退火操作时,冷却进度表的选取是一个关键。他包括如下参数:控制参数t的初值t0、控制参数t的衰减系数α、控制参数t的终值tf。其中控制参数t的初值t0由t0=Δf-inχ0,其中Δf-为适应度的平均减小量,χ0为初始接受率。第k次迭代时的控制参数为:tk=αtk-1,α=0.91控制参数t的终值取tf=t020000。

3.2 初始化染色体,构造初始种群

在寻径问题中采用自然编码,用矢量Asign(a1,a2,…,an)表示染色体G,其中基因ai=1,2,…,n是路径的编号,ai=j表示路径i上选中j节点,同时取得相应的代价值Value[g][i][j],这样就构成了该问题的一个可行解,用同样的方法就可以产生一组染色体Gh(h=1,2,…,N),N为种群大小。其中染色体各不相同,此为第一代种群。

3.3 评价个体适应度函数

适应函数采用目标函数,以保证较优的解有较大的生存机会。另采用加速适应度函数:λ=exp -(fj-fi)tk」,式中tk是当前第k代的温度,k是遗传代数。

3.4 交叉与变异的方法

对当前的种群进行交配,采取双亲单子法,这使得一对双亲只有一个后代,根据优胜劣汰的自然法则从后代中选一个好的。在具体交配时采用变化交配法(string-of-change crossover)。如:父代A为(0|1|1|0100),父代B为(0|1|1|1001),如果交配位选在1,2,3位进行交配,子代的A与子代B与其父代完全相同。因此,应该避开这三个位置,可以此采用的方法是从头开始比较它们的基因,从不同的位置按照常规方法随机选择交配位。如本例,比较可得到0001101,其中0表示相同,1表示不同。交配位可在4,5,6中随机选取。这样可以避免常规交配方法可能造成的父亲与子代的完全相同,以至于影响收敛速度和搜索范围。