《遗传算法,配送计划,算法设计》由会员分享，可在线阅读，更多相关《遗传算法,配送计划,算法设计（20页珍藏版）》请在金锄头文库上搜索。
1、为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划遗传算法,配送计划,算法设计北京师范大学珠海分校本科生毕业论文开题报告学生姓名邱俊杰学号所在院系物流学院专业物流管理指导教师姓名邓小瑜指导教师职称讲师指导教师单位物流学院毕业论文题目基于遗传算法的配送路径优化研究开题报告内容选题依据选题经过：通过在大学四年里对物流知识的学习，让我对物流企业的运作和管理有了一定程度的了解和认识。目前，我国很大一部分运输企业和物流企业是采用人工操作方式来对配送车辆进行调度安排和行车线路的规划。这种依赖人工经验来调度车辆的方式，不仅会导致企业运输资源浪费运
2、输成本提高，而且也难以满足客户越来越多样性和不规则性的需求。在北师大珠海分校学习的这四年里，我还辅修了信息技术学院的“软件工程”学位课程，因此，希望在我毕业论文设计中，能结合自己在程序设计方面所学到的知识，应用现代数学方法及计算机技术来求解物流配送路径优化问题。国内外研究现状：配送路径优化问题属于强NP难题。国外对配送路径优化问题的研究始于50年代末，目前在理论研究和实际应用两方面都已取得了比较显著的成果。随着研究的深入发展，如何使研究的理论模型更贴近现实中的运输规划问题开始成为研究者们关注的焦点。而国内相关研究人员对旅行商问题的理论研究较多，对配送路径优化问题的研究在90年代以后才逐渐起步，
3、比国外相对落后。这几年来我国已有越来越多的研究人员开始关注车辆路径问题题的解决方法，也己取得了一定的成果但总体来说，我国目前对车辆路径问题的理论研究仍相对匾乏，有待进一步发展。初步设想：配送路径优化问题又叫做车辆调度问题VPR(VehicleRoutingProblem)，包含了配送车辆安排和每辆车行驶线路规划两个方面。本论文首先将对一定条件下的配送路径优化问题建立数学模型，然后用经过改良的遗传算法对该模型进行求解。整个算法会用JAVA语言编写一个桌面应用程序来实现。论文中会详细阐述数学模型建立思路以及算法求解该模型的整个流程，并简要介绍一下程序设计、实现的思路与步骤。还会对用JAVA语言实现
4、的遗传算法在求解不同规模的VPR问题时的性能进行分析。论文的最后会总结一下算法的局限性并对未来的研究方向做个展望。理论和实践的意义及可行性论述理论和实践的意义：当前，现代物流是企业继续降低物资消耗、提高劳动生产率后的第三利润源泉。但我国物流企业的运输成本普遍偏高。其中很重要一个原因就是对配送车辆运输路线规划不科学。要想降低运输成本，离不开对配送路线的优化和配送车辆的合理安排。对物流配送车辆行驶路径进行优化，可以降低物流成本，节约运输时间，是提高物流经济效益的有效手段。可行性论述：配送路径优化问题是典型的优化组合问题，具有很高的计算复杂性。但遗传算法解决作为一种有效的全局搜索方法具有隐并行性和较
5、强的鲁棒性，在解决非线性的大规模复杂问题上具有很好的适应性，适合于对VPR问题进行优化求解。标准遗传算法虽然未必每次都能找到最优解，但通过对标准遗传算法进行改进，完全可以在有限时间内对较复杂的VPR问题计算出次优解或可行解。因此，用遗传算法来解决物流车辆调度问题还是完全可行的。文献综述：1朱剑英.非经典数学方法M.武昌：华中科技大学出版社，XX2李敏强，寇纪淞，林丹，李书全.遗传算法的基本理论与应用M.北京：科学技术出版社，XX3孙丽丽.物流配送中车辆路径算法分析与研究D.上海：上海海事大学，XX4盖杉.基于遗传算法的物流配送调度系统D.长春：长春理工大学，XX5高运良，基于免疫遗传算法的物流
6、配送VRP求解D.武汉：武汉科技大学，XX6阎庆，邰蕾蕾.用混合遗传算法解决有时间窗的车辆路径规划问题J.安徽大学学报，XX(2)7张海刚，顾幸生.基于混合免疫遗传算法的车辆调度问题J.微电子学与计算机，XX(1)论文撰写过程中拟采取的方法和手段本论文主要采用遗传算法作为解决物流配送路径优化问题的主要算法。但由于标准遗传算法具有“早熟收敛”的缺陷，有可能使算法陷入局部最优解。论文还将尝试通过把其他算法和遗传算法相结合，来有效控制早熟现象的发生。为了快速得到任意两个配送点之间的最优路线。本论文还拟采用佛洛依德算法构造配送路线的地理数据库的方式来对路线网络进行预处理。从而减少整个算法的时间复杂度和
7、空间复杂度。论文撰写提纲一、绪论1.研究的背景和意义2.问题描述3.国内外相关研究状况二、遗传算法基础1.标准遗传算法的基本原理2.标准遗传算法的早熟现象3.遗传算法的改进三、配送路径问题数学模型的设计和求解1.配送路径优化问题数学模型的设计2.求解该数学模型的遗传算法设计四、基于遗传算法的车辆调度问题实现1.需求分析2.程序设计3.程序实现五、程序运行结果分析1.实验数据来源2.实验结果分析3.程序性能评估六、结束语1.算法和程序的局限性2.结论及展望计划进度XX年11月01日XX年11月30日：查找及收集资料XX年12月01日XX年12月31日：研究算法和建立数学模型XX年01月01日XX
8、年1月31日：编写程序实现，运行实验数据XX年02月01日XX年02月25日：撰写毕业论文XX年02月26日XX年02月26日：提交初稿XX年02月27日XX年04月11日：和导师讨论，并修改论文XX年04月12日XX年04月12日：提交论文定稿指导教师意见选题具体，有研究价值；提纲结构合理。同意开题。签名：XX年1月14日教学院长意见教学院长签名：年月日注：纸张填写不够可另加附页。基于遗传算法的TSP路径规划算法设计摘要TSP问题是一个经典的NP难度的组合优化问题,遗传算法是求解TSP问题的有效方法之一。针对这一问题,首先给出了基于遗传算法求解TSP问题的一般性流程，设计了基于遗传算法的求解
9、算法,包括编码设计、适应度函数选择、终止条件设定、选择算子设定、交叉算子设定以及变异算子设定等,然后设计并实现了基于遗传算法的TSP问题求解系统,并编制了完整的Matlab程序予以仿真实现。1.引言旅行商问题(TravelingSalemanProblem,TSP),又叫货郎担问题,是最基本的路线问题,该问题是在寻求单一旅行者由起点出发,通过所有给定的城市之后,最后再回到原点的最小路径成本。该问题具有广泛的应用性,如物流中的配送车辆调度问题就可看成一个约束性多路旅行商问题.因此,对TSP问题求解具有一定的现实意义。TSP问题属于组合优化问题,随着问题规模增大,其可行解空间也急剧扩大,有时在当前
10、的计算机上用枚举法很难甚至不能求出最优解,而用启发式算法求解这类问题的满意解是一个很好的方式,遗传算法就是寻求这种满意解的最佳工具之一。遗传算法模拟自然进化过程来搜索最优解,其本质是一种高效、并行、全局搜索的方法。本文采用遗传算法求解TSP问题并编制Matlab程序进行仿真试验。12.TSP问题的数学模型TSP问题即寻找一条最短的遍历n个城市的最短路径,使得:Td?di?1n?1i,i?1?dn,1取最小值,di,i+1表示两城市i和i+1之间的距离。3.遗传算法的运行过程遗传算法是一种生成+检测的迭代搜索算法。其运算流程可用图1来表示。图1遗传算法的程序4.TSP问题的遗传算法实现编码并生成
11、初始种群编码是应用遗传算法时要解决的首要问题,也是设计遗传算法时的一个关键环节。求解TSP问题时,采用所遍历城市的顺序排列来表示各个个体的编码是最自然的编码方法,而且这种表示方法无需解码过程,占用的内存空间较小。2适应度评估适应度用来度量群体中各个体在优化过程中达到或接近于或有助于找到最优解的优良程度。适应度较高的个体被选中遗传到下一代的概率较大；而适应度较低的个体被选中遗传到下一代的概率相对较小一些。本文用个体所表示的循环路线的倒数来作为适应度评估值,路线越短,个体适应度值越大。选择、交叉、变异选择操作。是从群体中选择生命力强的个体产生新种群的过程.选择操作以个体的适应度评估为基础。其主要目
12、的是避免有用遗传信息的丢失。从而提高算法的全局收敛性和计算效率。常用的选择算子有赌轮选择、联赛选择、最佳保留等。其中，最佳个体保存策略可保证迄今为止所得到的最优个体不会被交叉、变异等遗传操作所破坏。它是遗传算法收敛性的一个重要保证条件。但它也容易使得某个局部最优个体不易被淘汰反而快速扩散。从而使得算法的全局搜索能力不强。因此，最佳个体保存一般要与其他选择方法配合使用方可取得良好的效果3。交叉运算产生子代,子代继承父代的基本特征。交叉算子一般包括两个内容:一是对种群中的个体随机配对并按预先设定的交叉概率来确定需要进行交叉操作的个体对;二是设定个体的交叉点,并对的部分结构进行相互交换。交叉算子的设
13、计与编码方式有关。在TSP问题中几种有代表性的交叉算子如顺序交叉、类OX交叉等,这些交叉算子在产生新个体的过程中没有目的性,对于自然数编码的TSP问题,这些交叉可能破坏亲代的较优基因,从而使交叉算子的搜索能力大大降低。变异操作是对个体的某些基因值做变动。变异操作的目的有两个,一是使遗传算法具有局部的随机搜索能力,当经过交叉操作群体已接近最优解领域时,利用变异算子可以加速向最优解收敛;二是使遗传算法可维持群体的多样性,以防止早熟现象。变异算子的设计也与编码方法有关,对于自然数编码的TSP问题,可采用逆转变异、对换变异和插入变异等。逆转变异,也称倒位变异,是指在个体编码中,随机选择两点(两点间称为
14、逆转区域),再将这两点内的字串按反序插入到原位置中.倒位变异考虑了原有边的邻接关系,能将巡回路线上的优良基因性能较好地遗传到下一代,提高寻优速度。5.仿真结果ans=+003*Columns1through100Columns11through20000Columns21through30多物流配送中心路径优化问题及其遗传算法廖成林柳茂森摘要：论文建立了多物流配送中心路径优化问题的数学模型，并针对该问题的特点构造出求解该问题的遗传算法，把多物流配送中心路径优化问题综合起来用一个数学模型求解。本文提出了无效基因的概念，从而不局限于使得个体中每个基因都必须表达出来，因此增强了编码的灵活性。仿真实验
15、证明了该方法的有效性和可操作性。关键词：无效基因遗传算法物流配送1引言物流配送是物流管理中一个极其重要的环节，它是指按用户的订货要求,在配送中心进行分货、配货,并将配好的货物及时送交收货人的活动。物流配送主要研究车辆调度及路径安排问题。近年来，国内外学者对物流配送问题进行了大量的研究，这些研究主要集中在单物流配送中心的车辆调度及路径安排方面。由于配送路径优化问题是一个NP难题，因此，研究者大都使用启发式算法和智能算法或者是在智能算法优化过程中加入优化策略以构造混合智能算法来求解物流配送问题。但是，目前国内外对多个物流配送中心的物流配送问题的研究成果很少，而且现有研究成果大都是把多个配送中心问题通过任务分派转化为单物流配送中心问题来研究13，使用这种方法把需求点预先划分给各个配送中心，在求解过程中再作适当的调整，这种方法其实
