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

1、北京师范大学珠海分校 本科生毕业论文（设计）开题报告 学生姓名 邱俊杰 学 号0411010209所在院系 物流学院 专业物流管理指导教师姓名 邓小瑜指导教师职称 讲 师指导教师单位物流学院毕业论文题目基于遗传算法 的配送路径优化研究 开题报告内容选题依据（选题 经过，国内、 国外研究现 状，初步设 想及创 新点 等）选题经过：通过在大学四年里对物流知识的学习， 让我对物流企业的运作和管理有了一定程度的了解和认识。目前，我国很大一部分运输企业和物流企业是采用人工操作方式来对配送车辆进行调度安排和行车线路的规划。 这种依赖人工经验来调度车辆的方式，不仅会导致企业运 输资源浪费运输成本提高，而且也

2、难以满足客户越来越多样性和不规则性的需求。在北师大珠海分校学习的这四年里，我还辅修了信息技术学院的软件工程”学位课程，因此，希望在我 毕业论文设计中，能结合自己在程序设计方面所 学到的知识，应用现代数学方法及计算机技术来求解物流配送路径优化问题。国内外研究现状：配送路径优化问题属于强NP难题。国外对配送路径优化问题的研究始于50年代末，目前在理论研究和实际应用两方面都已取得了比较 显著的成果。随着研究的深入发展，如何使研究的理论模型 更贴近现实中的运 输规划问题开始成为研究者们关注的焦 点。而国内相关研究人员对旅行商问题的理论研究较多，对配送路径优化问题 的研究在90年代以后才逐渐起步，比国外

3、相对落后。这几年来我国已有越来越多的研究人员开始关注车辆路径问题题的解决方法，也己取得了一定的成果 但总体来说，我国目前对车辆路径问题的理论研究仍相对匾 乏，有待进一步发 展。初步设想：配送路径优化问题又叫 做车辆调度问题 VPR(Vehicle Routing Problem)，包含了配 送车辆安排和每辆车行驶线路规划两个方面。本论文首先 将对一定条件下的配送路径优化问题建立数学模型，然后用 经过改良的遗传算 法对该模型进行求解。整个算法会用JAVA语言编写一个桌面应用程序来实现。论文中会详细阐述数学模型建立思路以及算法求解该模型的整个流程，并简要 介绍一下程序设计、实现的思路与步骤。还会对

4、用语言实现的遗传算法 在求解不同规模的 VPR问题时的性能进行分析。论文的最后会总结一下算法的局限性并对未 来的研究方向做个展望。 理论和实践的意义及可行性 论 述(包括文献 综述) 理论和实践的意义：当前，现代物流是企业继续降低物资消耗、提高劳动生产率后的第三利润源泉。但我国物流企业的运输成本普遍偏高。其中很重 要一个 原因就是对配送车辆运输路线规划不科学。要想降 低运输成本，离不开对配送路线的优化和配送车辆的合理安排。对物流配送车辆行驶路径进行优化，可以降低物流成本，节约运输时间，是提高物流经济效益的有效手段。 可行性论述：配送路径优化问题是典型的优化组合问题，具有 很高的计算复杂 性。但

5、遗传算法解决作为一种有效的全局 搜索方法具有隐并行性和较强的鲁棒性，在解决非线性的大规模复杂问题上具有很好的适应性，适合于对VPR问 题进行优化求解。标准遗传算法虽然未必每次都能找到最优 解，但通过对标准 遗传算法进行改进，完全可以在有限时 间内对较复杂的 VPR问题计算出次优 解或可行解。因此， 用遗传算法来解决物流车辆调度问题还是完全可行的。文献综述：1朱剑英.非经典数学方法M.武昌：华中科技大 学出版社，2001 2李敏强，寇纪淞，林丹，李书全 遗传算 法的基本理论与应用M.北京：科 学技术出版社，2002 3 孙丽丽.物流配送中车辆路径算法分析与研究D.上海：上海海事大学，2007 4

6、盖杉.基于遗传算法的物流配送调度系 统D.长春：长春理工大学，2007 5高运良，基于免疫遗传算法的物流配送 VRP求解D.武汉：武汉科技大学，2007 阎庆，邰蕾蕾.用混合遗传算法解决有时间窗的车辆路径 规划问题J.安徽 大学学报，2007(2) 7张海刚，顾幸生. 基于混合免疫遗传算法的车辆调度问题J.微电子学与计算机，2007(1)论文撰写过 程中拟采取 的方法和手 段 本论 文主要采用遗传算法作为解决物流配送路径优化问题的主 要算法。但 由于标准遗传算法具有早熟收敛”的缺陷，有可能使算法陷入局部最优解。论文还将尝试通过把其他算法和遗传算法相结合，来有效控制早熟现象的发生。为了快速得到任

7、意两个配送点之间的最优路线。本论文还拟采用佛 洛依德 算法构造配送路线的地理数据库的方式来对路线网 络进行预处理。从而减少整个算法的时间复杂度和空间复杂度。论文撰写 提 纲一、绪论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日