1.本站不该用户上传的文档完整性，不预览、不比对内容而直接下载产生的问题本站不予受理。
基于改进遗传算法的包装件物流配送 车辆径规划 摘要：本文描述包装件物流配送车辆径规划的问题，并建立相应的数学模型，并通过对遗传算法的研究，构造一种较为适合包装件车辆径问题的改进遗传算法，结果表明：能够运用该算法更好的解决VRP问题，为包装件在物流配送的径规划问题中提供决策支持。 关键词：包装件物流;车辆径规划; 改进遗传算法;物流配送 The vehicle path planning for packages logistics based on improved genetic algorithm Abstract:The description of the VRP problem for Packages logistics is given,as well as the related math model。In addition，via the research of genetic algorithm,a kind of improved genetic algorithm which is more suitable for vehicle routing problem of packages is constructed.The result shows that The algorithm can solve the VRP problem better,which provides decision support for path planning in the distribution of packaging logistics. Key words: packaging logistics, VRP, improved genetic algorithm; distribution 引言 物流是一门新兴的交叉性综合学科，研究物流的目的是有效的管理和控制物流的全过程，在服务质量的前提下，实现消耗总费用最小。物流配送是指根据客户的需求，将物品准确及时的送到目的地。作为配送方，要对物流配送系统实现优化，以节约成本、提高效率。在配送实务中，物流配送系统实现优化的核心工作是进行配送车辆径的优化。选取恰当的车辆径，可以加快对客户需求的响应速度，提高服务质量，增强客户对物流环节的满意度，降低服务商运作成本。因此，作为物流系统优化中关键的一环，车辆径问题的研究受到了人们的广泛关注.[1-3] 物流产业迅猛发展的同时，包装件的配送逐渐趋向于小批量、多批次、短周期发展，因此针对包装件的物流管理具有现实意义。包装件物流管理包括对包装件的仓储、装载、配送、卸货等一系列环节的优化和控制过程[4]。包装件物流配送是以包装件为配送对象的物流管理模式，具有产品的安全、方便储运装卸、加速交接和检验等作用，本文就其中的车辆径规划进行分析和研究。 本文旨在通过对遗传算法的研究，构造一种较为适合VRP问题的改进遗传算法，能够运用该算法更好的解决VRP问题，为包装件及其它物品在物流配送的径规划问题中提供决策支持 包装件物流配送车辆径规划的问题描述和数学模型 在物流配送决策中，带时间窗约束的车辆径规划问题(VRPTW)具有现实意义。VRPTW问题可以描述为，给定了各客户点需求量和允许服务的时间范围，要求确定一组行车线，使总径最短。遗传算法近年来在求解VRPTW问题中受到了较大的关注。 包装件物流配送车辆径规划问题可以描述为:设包装件配送中心仓库有9辆车，车辆承载能力为k，要为n个客户送货，客户需求量为k;，行驶平均速度为v,ti表示第i个客户的送达时间，[ai,bi]表示配送点i的时间窗，要求合理安排车辆线，使行车总径最短。本课题采用的处理约束的方法:如果违反了车辆的容量，则要加乘惩罚因子c2;如果了时间窗要求，则要加乘惩罚因子c3和c4。根据上述要求，建立以下的数学模型: 目标函数： （1） 约束条件： （2） （3） （4） （5） （6） （7） 式(1)表示目标函数为总程最短，(2)为车辆容量约束，(3)为每个客户的配送任务仅由一辆车完成，(4) (5)到达和离开某一客户点的汽车有且仅有一辆，(6)表示车s是否由i驶向j. (7)表示客户点i的任务是否由车s完成。 改进遗传算法的设计与实现 由于VRP问题的编码特征和标准遗传算法的设计特征存在内在冲突，因而大大影响了遗传算法在解决该问题上的效果[5]。但是，要改变VRP问题编码方式目前尚无有效手段，因此，本文着重对标准遗传算法进行改进设计，力求通过改进后的遗传算法，既发挥其适合于大规模群体搜索的优点，又要避免其随机性过强的缺点，这是本次改进设计所遵循的根本原则。 单目标VRPTW问题染色体的编码形式 在研究遗传算法时，确定染色体编码是第一个关键步骤。我们采用自然数编码的方式来确定染色体。一条可可编为一条长度为(n+q+1) (n为需求点数量，q为车辆数)的染色体，式为(0，i11，i12，i13，… i1i，0，i21 ，i22，i23，… i2i，0, …,0,i21 ，i22，i23，… i2i)其中0表示出发点，ikj表示第ikj个客户。 例如，染色体“70，表示有3辆车为9个客户送货，配送径为: 第一条径:配送中心－客户2－客户3－客户1－配送中心; 第二条径:配送中心－客户8－客户9－客户5－配送中心; 第径:配送中心－客户4－客户6－客户7－配送中心。 编码方式确定以后，讨论各个设计算子对优化性能的影响。 射线] 标准遗传算法产生的染色体和初始种群是随机的，内部排列是无规律的，在很大程度上增加了搜索的难度。本文采用射线扫描法来生成染色体及初始种群，根据车辆径规划问题的特点，通过射线扫描的方法，产生经初步优选的种群，使遗传算法能更好的发挥其全局搜索的优点。 射线扫描法原理可具体描述如下:按照地理确定各点坐标后，将配送中心和收货客户组成一个二维平面，以配送中心为坐标原点，将各收货点按照与X轴的倾斜角关系重新排序，再由原点引出一条射线，以原点为中心，作逆时针扫描，以此来确定染色体和初始种群。 扫描时，先从新编号中随机选取一点，再由原点引出一条过该点的射线，以原点为中心逆时针旋转，所经过的第二点即为染色体第二点，继续旋转，直至不满足车辆容量，此时射线返回原点，以此段为染色体的第一段子径;再由原点引出射线至下一点，作为第二段子径的起始点，继续逆时针旋转扫描，产生第二段子径，依此方法将射线旋转一周，即可经过所有收货点，即组成了一条完整染色体。该方法产生的染色体及初始种群线较为清晰，不存在交叉段，更接近最优线，加快了遗传算法的搜索速度。 程序实现步骤如下： 输入种群规模Z，车辆数4，各点坐标值S 计算各点与X轴的倾斜角，存放于数组t 对数组t排序，从中随机选取一点，以该点为第一点，按2中顺序排列，形成一条染色体di 重复Step3，直到达到种群规模 适应度函数 本文采用以下函数作为适应度函数 （8） 其中式中:fi为第i个染色体的适应度，Z0为初始种群中最好染色体的运输距离，Zi为当前染色体所对应的运输距离。 选择算子的改进设计 为了种群的优秀个体不被，保持平均适应度不被降低，同时也为了加快算法的性，提高算法的效率，本文采用“最优保存策略”的选择算子，该选择算子的实现过程是，当前种群适应度最高的个体，不参与交叉和变异运算，而是用它来替代本代种群中经过交叉、变异等操作后所产生的适应度最低的个体。 最优保存策略进化模型的具体操作过程是: 找出当前种群中适应度最高和最低的个体; 若当前种群中最佳个体的适应度比总的到今的最好个体适应度要高，则以当前种群的最佳个体替代新的最好个体; 用当前最好个体替代当前种群的最差个体，事实上，最优保存策略是选择算子的一部分，这种选择方式可以最优个体不被，是加快遗传算法的一个重要条件。 由于在生成初始种群的时候，采用了射线扫描法，初始种群的适应度相对比较高，而前面已经证明过，由于交叉变异算子的影响，在种群平均适应度高的时候，其性反而有增大的趋势，造成算法过慢。因此，采用最优保存策略就成为一种比较适合于解决VRP问题的选择方式，因为该选择算子可以直接使优秀个体进入下一代，并替代适应度较低的个体，这样就尽量降低了交叉和变异对优秀个体的，有效的了优秀个体，有利于提高算法的速度。 交叉算子的改进设计 本文提出一种基于单亲遗传算法的“进化逆向操作”的方法对标准遗传算法中的交叉算子进行改进设计。改进原理如下: 先在父代染色体P1中随机选取1个子径，将该子径的元素和0删去，此时将产生1个字符串，然后将该字符串按逆序重新排列，最后再插入P1中的空位。该改进方法在继承射线扫描法优点的基础上，弥补其自身缺点。因为射线扫描法是单方向的，在扫描过程中可能造成漏掉优秀个体，而对部分染色体实行进化逆操作，相当于在局部范围内，将射线由逆时针变为顺时针扫描，这样既保留了射线扫描法“不走回头和交叉”的优点，又可以在此基础上增加种群的多样性，加强局部搜索能力，同时可以优秀的个体不被交叉运算。 在上例采用该方法，在父代P1中选取子径0-3-9-1-0，将该子径的元素和0删去，得到字符串12-5-11-8-6-2-10-7-4，将该字符串逆操作，即对该字符串按逆序重新排列，该字符串变为4-7-10-2-6-8-11-5-12，最后再插入Pl中的空位，得到的新个体P2为: 父代:P1=0-3-9-1-0-12-5-11-8-0-6-2-10-7-4-0 子代:P2=0-3-9-1-0-4-7-10-2-0-6-8-11-5-12-0 由于遗传算法的编码方式具有“组内有序，组间无序”的特点，所以在插入空位的时候，可以随机的插入任何一个空位，所得到的都是同一条染色体。 编程实现步骤如下: 在染色体di中随机找出一条子径P 将该子径P和0从di中去掉，产生字符串P2 将P2逆序排列 将逆转后的n2插入原染色体的非0位 变异算子的改进设计 通常的变异方法是随机取两点，再进行交换，原本变异可以增加种群多样性，但是在VRP问题，变异是以改变径环为代价的，这样在接近的时候，由于种群内很多径都己经形成大致不相交的子环，但是，变异算子可能环，因为，突然改变径所经过的点，极有可能造成新的线交叉，不利于算法。 因此本文采用指定变异的方法，尽量环不被。例如:对染色体进行指定的变异，首先找到两个“0，然后指定“0”的后面的两个数互换，得到染色体。 实例分析 采用改进遗传算法在包装件物流配送应用中的实例[8]:假设某配送中心为0，坐标为(0,0)，所需配送的客户数n为10，车辆数q为3，单车载重量为10，各需求点的坐标、需求量和时间如表1所示，要求在符合容量约束及时间窗要求下，合理安排车辆行驶线，使行车径最短。 表1 实例的已知条件 收获点编号 X坐标 Y坐标 需求量 时间窗开始 时间窗结束 1 1 6 3 1 4 2 -10 13 5 2 5.5 3 6 -19 1 2 7 4 8 1 1 1 4 5 9 0 2 1 3 6 -3 5 2 1.5 4 7 -4 -16 1 4 8.5 8 0 12 4 2 4 9 14 -7 3 2 5 10 -9 -1 2 1 6.5 这是一个有10个需求点和1个配送中心的车辆径问题，应用MATLAB语言编制遗传算法程序来求解此实例。编程实现步骤如下: 选用0, 1,…n编码，0为中心车场，1, ….n代表客户点，设置终止条件和种群规模，即输入坐标s，种群规模Z，进化代数ds 迭代次数t=0，射线扫描法产生初始种群d 计算种群中每一个个体的适应度函数j1 :最优选择，保留当前适应度值最高个体 对d实行交叉、变异操作，生成下一代种群 若满足算法条件则终止，否则令迭代次数t=t+1，回step3，直至ds达到进化代数 参数设定:群体规模m=20，进化代数N=200，交叉概率0.9，变异概率0.02 Matlab中运行10次，结果如下图： 图1 实例优化结果 在第5次运算中，获得最优解为126，对应线。计算结果表明，用MATLAB对基于遗传算法的物流配送径优化进行仿真，可以方便有效地求得问题的最优解或近似最优解。上例的配送线 配送线结果 结论 本文描述包装件物流配送车辆径规划的问题，并建立相应的数学模型，通过采用射线扫描法优选初始种群，减少径交叉，加快遗传算法的搜索速度;通过对选择、交叉算子进行改进设计，在改进算法优点的前提下，加强算法的局部搜索能力。对改进遗传算法进行应用研究表明，改进后的遗传算法可以实现优选车辆径的效果，为包装件物流配送径规划提供了新的方法。 参考文献 李军，郭耀煌.物流配送车辆优化调度理论与方法[M].:中国物资出版社，2001: 5-10. 宋伟刚.物流工程及其应用[M].:机械工业出版社，2003: 3-5. 都渊晓.现代物流配送管理[M].上海:中山大学出版社，2001: 4-6. 黄颖为，培，孙德强.改进遗传算法在包装件物流调度中应用的研究[J].包装工程，2008.29(1):105-107. 许星.物流配送径优化问题的研究[D]薄熙莹黄菊自杀真相.浙江:浙江大学，2006, 5: 7-8. Billy E.Gillet,Leland R.Mi11er.A Heuristic Algorithm for thevehicle dispatch Problem[J].Operation Research, 1974, 22: 340-349. Willard J.A. Gvehicle Routing using P-optimal TabuM.S.thesis[M]. Management School, Imperial College ,London. 1989: 10-15. Michel Gendreau, Alain Hertz, Gilbert Laporte. A TabuHeuristic for Vehicle Routing Problem[J].Management Science, 1994. 40 (10):1276-1290.
请自觉遵守互联网相关的政策法规，严禁发布、、的言论。用户名:验证码:匿名?发表评论