|
职称论文发表 | 职称论文发表 专业提供:发表论文、论文发表、毕业论文、职称论... | |
住在汉口网 | 住在汉口网是一个专业提供汉口房产信息、车辆服务、生活服务、招... | |
职称论文网 | 职称论文网提供:发表论文、论文发表、毕业论文、职称论等服务。 | |
|
1 引言
车辆路径问题(VRP)作为物流配送系统优化的重要组成部分,而VRPTW问题就是研究在满足客户对货物、服务时间等要求的前提下,使车辆运行成本尽可能最优。因此研究VRPTW问题对企业制订运输具体路径具有更为现实意义。
2 车辆路径问题(VRP)问题描述
2.1 带时间窗的车辆路径问题定义
如果客户对物品的配送有时间限制,即要在一定的时间窗内完成配送,则VRP被称之为有时间窗的车辆路径问题(Vehicle Routing Problems with Time Window,VRPTW)。
2.2 带时间窗的车辆路径问题(VRPTW)的数学描述
假定运输中心有一规模为K的车队,即有K辆容量均为Q的同质车辆为所有客户发送货物。问题的目标是设计一个车辆路径的集合,使得在给定时间约束,车辆容量约束以及其它相关参数的前提下,最小化为所有客户提供服务耗费的总成本。这里的成本度量包含距离或时间。下面首先对VRPTW的约束条件和研究目标加以语言上的描述,以便稍后的数学建模。从图论的角度来看,VRPTW可表述如下:G=(V,A)是一完全无向图(如图1),其中V{V0, V1V2...,VN} 是一节点集合,,代表N个待访问的客户,V0代表运输中心。则带时间窗的车辆路径问题(VRPTW)可描述为下述目标函数的求解问题,其中,目标函数可描述为:,其中,下列符号分别代表:K:车队规模即总的车辆数目;N:有待访问的总的客户数目;:从到的成本;:到达客户的时间;:客户要求的准点到达时间;:客户需求点i的缓冲时间;F:车辆早到或者迟到的惩罚系数;为虚拟变量,当车辆路径k中不存在从客户i到客户j的连接时,,否则。VRPTW是包含了TSP以及VRP问题的更为一般性的问题。如果没有关于时间窗的约束那么就成为一个VRP问题。这也可以通过将所有客户的F设为0,
或将设为M(在这里M是一个足够大的数)来实现;如果只有一辆车可以使用(K=1),那么问题又成为了TSP的描述;如果令,对于所有的,而令,对于其它的i,j组合,则这又成为了装箱问题(Bin-packing problem)。也就是相当于访问客户的顺序已经不再重要(由于路上费用为0),而目标是将尽可能多的货物装入尽量少的车(箱)中。可见,车辆路径问题是物流运输中的基本问题,而带时间窗的车辆路径问题则是实际应用当中经常遇到的更为一般问题。
2.3 遗传算法对VRP问题的解决方法
对于确定型的各类VRP问题,其解法可以分为两类:精确算法和启发式算法。精确算法只能有效求解中小规模的确定性VRP,无法解决指数巨量计算问题。启发式算法主要应用于大规模的VRP求解问题,可以分为初始过程启发式算法和改进过程启发式算法,都不能有效解决优化问题。将遗传算法应用于VRPTW的求解中,可以在不违背车辆容量限制和车辆行驶时间以及客户时间窗的前提下,最小化被服务客户的成本。
传统的遗传算法虽然为解决VRP问题提供了可能性,但其缺点也非常明显:编码问题的单调性、遗传算子的简单性、参数设置的不通用性、算法局部搜索能力弱、容易发生“早熟”、在算法的前后期进化速度不一致等等。因此,在求解具体问题时,必须依照具体问题的特性,对算法的上述问题进行改进,使之符合具体问题的情况,只有这样,才能发挥遗传算法作为问题求解思路的强大优势,得到比较好的求解效果。
3 用改进的遗传算法解决VRPTW
通过对遗传算法的各种改进方法的比较和分析,以及对有时间窗的车辆路径问题的理解
本文运用基于精英个体的二次遗传、自适应的混合遗传算法来改进传统遗传算法在VRPTW问
题上的不足。
3.1 具体的算法设计步骤
1.开始->2.算法参数初始化->3.读取问题描述信息—>4.按照编码机制随机生成初始种群—>5.对种群进行遗传操作保留当代最优个体到精英种群—>6.是否达到终止遗传代数
—>7.如果没有达到,则返回步骤5;如果达到继续步骤8—>8.进行精英种群遗传操作—>9.得到二次遗传最优个体—>10. 对得到的最优个体进行爬山搜索—>11. 输出问题最优解
—>12.结束
3.2 相对于传统的遗传算法对VRPTW问题的解决方法,主要改进方面
1. 在染色体可行性模块中引入精英种群概念。精英种群指的是:在以往进化各代的基础上,把以往各代进化所得到的最优个体组合起来,得到的种群称为精英种群。由于精英种群的初始个体都是以往种群进化得到的最优个体,相比一般种群来说,具有更好的总体平均性能。根据遗传模式定理的思想,具有良好评价性能的染色体必然具有良好的基因片,所以,在优良个体之间进行优良基因片的组合、交叉,可以产生更为优良的染色体。这是精英种群的思想基础。具体实现过程如下:步骤1,对每代的种群Gi进行Max次的选择、交叉和变异等遗传操作,获取在该代进化得到的最优解;步骤2,保存最优解;到精英种群Goodgenes中;步骤3,当进行n代遗传进化后,得到精英种群Goodgenes;步骤4, 对精英种群Goodgenes独立进行最大次数的遗传操作,获取问题最优解。
2. 基于精英种群的二次遗传。“早熟”现象是遗传算法的主要缺陷,使得遗传算法容易陷入局部最优解而不能继续朝全局性最优解方向搜索。通过对遗传算法的参数的改进来加快算法的收敛速度,起到一般性全局搜索算法的功能,这就是“二次遗传”的概念,在系统的执行过程中存在着二次遗传算法的进化流程,其中第二次的遗传算法执行最优解的全局性搜索,是系统的核心框架,第一次的遗传算法主要是进行局部性搜索,得到一个局部的最优解或者满意解,第二次遗传操作是第一次遗传算法的有力补充,通过第二次遗传算法,既可以充分发挥遗传算法全局性搜索强的特点,又可以通过参数改变,充分利用遗传算法出现“早熟”的缺陷,加强遗传算法局部性搜索能力。这样,整个算法在全局性搜索和局部性搜索双层层面上具备了对全局最优解的搜索能力。
3. 混合遗传算法。由于遗传算法局部性搜索能力不足,所以通过引入局部行搜索强的爬山法算法来弥补。爬山法是一种贪心算法,它通过对一个问题解点周围一定范围内的解进行比较,当发现一个质量优良的解时,则与当前保存的最优解进行比较,如果质量更优,则用当前的更优解来替代现在的最优解。
4 数据实验结果对比分析
为了比较改进算法与传统算法在性能上的差异,下面就同一的参数设置,用不同的遗传算法进行运算。具体的参数设置为:每次遗传的代数都为100代,选择的染色体组数目为100,变异率为0.005,交叉率为0.45,需求点数目与配送车辆的数目分别为:100和30,在同样的条件下运行50次,总结改进算法与传统算法的结果,得到下面表1的结果:
表1改进算法与传统算法结果指标比较
传统算法 无爬山操作 无二次遗传 改进算法
平均解 1973.26 1660.62 1723.94 1614.5
最优解及偏移率 1870/5.23% 1565/5.76% 1630/5.45% 1532/5.11%
最差解及偏移率 2082/5.51% 1736/4.54% 1809/4.93% 1668/3.31%
均方差 345.13 224.4 297.27 232.68
对表中指标进行分析,除了均方差一项指标外,在改进算法中,其他指标均为几个算法中最优的。虽然在运行时间上来讲改进遗传算法所需时间最多,但是那是在指定遗传代数的前提下所需的运行时间,在实际操作中操作者一般会根据具体情况事先确定可以接受的满意解范围,如果遗传操作得到的结果达到用户要求,操作者就可以终止遗传操作的进行,当然,如果时间允许也可以持续运行程序,直至最后得到最终的满意解。
5 结论
1. 改进的混合遗传算法相对于其他算法能够以较大的概率得到质量更优的满意解;
2. 经过多次运算,改进的混合遗传算法所得到的满意解总体的抖动性比较小,换句话说就是算法的稳定性比较好;
3. 利用改进的混合遗传算法,我们仅仅能以相对较大的概率得到比较满意的最优解,但是不能以绝对的概率得到全局最优解 职称论文发表网http://www.issncn.com
职称论文发表网http://www.issncn.com
|
|
|
|