基于遗传算法的配送路径优化研究开题报告.doc

北京师范大学珠海分校本科生毕业论文（设计）开题报告学生姓名邱俊杰学 号 0411010209所在院系物流学院专 业 物流管理指导教师姓名邓小瑜指导教师职称讲 师指导教师单位物流学院毕业论文题目基于遗传算法的配送路径优化研究开 题 报 告 内 容选题依据（选题经过，国内、国外研究现状，初步设想及创新点等）选题经过：通过在大学四年里对物流知识的学习，让我对物流企业的运作和管理有了一定程度的了解和认识。目前，我国很大一部分运输企业和物流企业是采用人工操作方式来对配送车辆进行调度安排和行车线路的规划。这种依赖人工经验来调度车辆的方式，不仅会导致企业运输资源浪费运输成本提高，而且也难以满足客户越来越多样性和不规则性的需求。在北师大珠海分校学习的这四年里，我还辅修了信息技术学院的“软件工程”学位课程，因此，希望在我毕业论文设计中，能结合自己在程序设计方面所学到的知识，应用现代数学方法及计算机技术来求解物流配送路径优化问题。国内外研究现状：配送路径优化问题属于强NP难题。国外对配送路径优化问题的研究始于50年代末，目前在理论研究和实际应用两方面都已取得了比较显著的成果。随着研究的深入发展，如何使研究的理论模型更贴近现实中的运输规划问题开始成为研究者们关注的焦点。而国内相关研究人员对旅行商问题的理论研究较多，对配送路径优化问题的研究在90年代以后才逐渐起步，比国外相对落后。这几年来我国已有越来越多的研究人员开始关注车辆路径问题题的解决方法，也己取得了一定的成果但总体来说，我国目前对车辆路径问题的理论研究仍相对匾乏，有待进一步发展。初步设想：配送路径优化问题又叫做车辆调度问题VPR(Vehicle Routing Problem)，包含了配送车辆安排和每辆车行驶线路规划两个方面。本论文首先将对一定条件下的配送路径优化问题建立数学模型，然后用经过改良的遗传算法对该模型进行求解。整个算法会用JAVA语言编写一个桌面应用程序来实现。论文中会详细阐述数学模型建立思路以及算法求解该模型的整个流程，并简要介绍一下程序设计、实现的思路与步骤。还会对用JAVA语言实现的遗传算法在求解不同规模的VPR问题时的性能进行分析。论文的最后会总结一下算法的局限性并对未来的研究方向做个展望。理论和实践的意义及可行性论述（包括文献综述）理论和实践的意义：当前，现代物流是企业继续降低物资消耗、提高劳动生产率后的第三利润源泉。但我国物流企业的运输成本普遍偏高。其中很重要一个原因就是对配送车辆运输路线规划不科学。要想降低运输成本，离不开对配送路线的优化和配送车辆的合理安排。对物流配送车辆行驶路径进行优化，可以降低物流成本，节约运输时间，是提高物流经济效益的有效手段。可行性论述：配送路径优化问题是典型的优化组合问题，具有很高的计算复杂性。但遗传算法解决作为一种有效的全局搜索方法具有隐并行性和较强的鲁棒性，在解决非线性的大规模复杂问题上具有很好的适应性，适合于对VPR问题进行优化求解。标准遗传算法虽然未必每次都能找到最优解，但通过对标准遗传算法进行改进，完全可以在有限时间内对较复杂的VPR问题计算出次优解或可行解。因此，用遗传算法来解决物流车辆调度问题还是完全可行的。文献综述：1朱剑英.非经典数学方法M.武昌：华中科技大学出版社，20012李敏强，寇纪淞，林丹，李书全.遗传算法的基本理论与应用M.北京：科学技术出版社，20023孙丽丽. 物流配送中车辆路径算法分析与研究D.上海：上海海事大学，20074盖杉.基于遗传算法的物流配送调度系统D.长春：长春理工大学，20075高运良，基于免疫遗传算法的物流配送VRP求解D.武汉：武汉科技大学，20076 阎庆，邰蕾蕾.用混合遗传算法解决有时间窗的车辆路径规划问题J.安徽大学学报，2007(2)7张海刚，顾幸生.基于混合免疫遗传算法的车辆调度问题J.微电子学与计算机，2007(1)论文撰写过程中拟采取的方法和手段本论文主要采用遗传算法作为解决物流配送路径优化问题的主要算法。但由于标准遗传算法具有“早熟收敛”的缺陷，有可能使算法陷入局部最优解。论文还将尝试通过把其他算法和遗传算法相结合，来有效控制早熟现象的发生。为了快速得到任意两个配送点之间的最优路线。本论文还拟采用佛洛依德算法构造配送路线的地理数据库的方式来对路线网络进行预处理。从而减少整个算法的时间复杂度和空间复杂度。论文撰写提 纲一、 绪论1. 研究的背景和意义2. 问题描述3. 国内外相关研究状况二、 遗传算法基础1. 标准遗传算法的基本原理2. 标准遗传算法的早熟现象3. 遗传算法的改进三、 配送路径问题数学模型的设计和求解1. 配送路径优化问题数学模型的设计2. 求解该数学模型的遗传算法设计四、 基于遗传算法的车辆调度问题实现1. 需求分析2. 程序设计3. 程序实现五、 程序运行结果分析1. 实验数据来源2. 实验结果分析3. 程序性能评估六、 结束语1. 算法和程序的局限性2. 结论及展望计划进度2009年11月01日2009年11月30日：查找及收集资料2009年12月01日2010年12月31日：研究算法和建立数学模型2010年01月01日2010年1月31日：编写程序实现，运行实验数据2010年02月01日2010年02月25日：撰写毕业论文2010年02月26日2010年02月26日：提交初稿2010年02月27日2010年04月11日：和导师讨论，并修改论文2010年04月12