基于改进遗传算法的复杂网络路径优化问题毕业设计说明书(编辑修改稿)

基于改进遗传算法的复杂网络路径优化问题毕业设计说明书(编辑修改稿)内容摘要：

对象，建立了考虑环境指标和经济指标的车辆路径优化问题的多目标数学模型，以车辆的运输时间和中转时间为约束条件来确定最短路径降低成本，之后设计了求解该问题的改进遗传算法，最后用标准的车辆路 径优化问题算例做了仿真实验，通过对实验结果的分析验证了算法的正确性。 本文结构路线图如图 所示： 天津理工大学 20xx 届本科毕业设计说明书 5 V R P 问 题 优 化 研 究研 究 背 景 、 意 义 和现 状V R P 求 解 方 法V R P 问 题 概 述 V R P 模 型 构 建V R P 描 述 组 成 、 模型 、 分 类求 解 算 法 设 计遗 传 算 法 介 绍遗 传 算 法 原 理 、 工作 过 程 、 特 点G A 具 体 方 案 ： 染 色体 、 种 群 、 适 应度 、 遗 传 算 子 等算 例 分 析时 间 窗 描 述 、 分 类总 结 及 展 望 图 结构路线图 本文的 结构安排 本文共分为五章，各章的主要内容安排如下： 第一章介绍了 复杂网络下的路径优化问题 的研究背景，相关技术的发展概况 、研究的目的和意义 以及国内外在 遗传算法进化过程中 等领域的研究现状。 并分析了在这些前提下，基于改进遗传算法的复杂路径优化问题 的优势。 天津理工大学 20xx 届本科毕业设计说明书 6 第二章介绍了实现 基于改进遗传算法的复杂网络路径优化问题 时所使用的关 键技术，详细地阐述了 在遗传算法中编码，生成初始种群，适应性值评估，选择，交叉，变异，确定最优解等 实现遗传算法 等技术的工作原理以及 仿真实验的介绍。 第三章 复杂网络路径优化问题的 描述了该 优化问题的符号含义 ，并设计了该 优化问题所使用的数据 模型 ，并深入地描述了 该优化问题的求解方法。 第四章具体地说明了对基于 改进遗传算法的复杂网络路径优化问题 进行了 改进遗传算法的设计。 第五章通过算例分析进行仿真实验 ，通过详细的测试对该 问题 进行了可行性验证 以及对结果的分析。 第 六 章总结了在开发 基于改进遗传算法的复杂网络路径优化问题时 所 遇到的各种问题，在总结的过程中对这些问题进行深入的思考，提出了未来可以进一步改进的解决方案。 天津理工大学 20xx 届本科毕业设计说明书 7 第二章 系统关键技术介绍 遗传算法 遗传算法（ Geic Algorithm， GA）是 Holland 和 Bagley 于 1975 年提出，它是一种借鉴生物进化机制演化而来的自适应随机搜索算法。 遗传算法从一定的初始群体开始进化，从中筛选出优良的染色体，通过一代一代的进化，使整个群体适应性更好，经过一定代数的进化之后，最终找到最优的个体。 其中 在每一代的群体中，按照每个染色体的适应性优劣，选择出一些良好的染色体复制到下一代种群中，接着通过染色体之间的交叉、变异生成新的染色体。 在遗传（ GA） 算法中，首先通过一定的编码方式生成初始群体，然后在每个染色体上执行选择算子（ Selection Operator）、交叉算子（ Crossover Operator）、变异算子（ Mutation Operator）这些操作，并从中选出适应度高的染色体进化，从而实现优胜劣汰的进化过程，算法的具体操作过程如下： （ 1） 染色体编码： GA 不能对问 题的一些参数进行直接处理，所以需要将问题的解通过一定的编码方式编码为染色体，染色体编码的好坏直接影响计算消耗的时间，算法运行的快慢，所以一般情况下为节省算法运行时间采用自然数直接编码的方式。 （ 2） 初始化：对问题的参数进行初始化，并按照一定的方法生成初始的染色体群体，一个染色体对应着一个配送方案。 （ 3） 计算适应度值：适应度函数用来判定染色体的优良程度，常常根据问题的特点，选取一定的函数作为适应度函数。 为了能迅速判定染色体的优良程度，就要拉大优良个体的适应度值，基于序的评价函数就有利于拉大个体之间的适应度值，基于序的评 价函数首先就是对种群中所有的个体按照总距离的大小进行排序，每一个个体要给与一个队列序号，总的距离越小，序号越靠前。 （ 4） 选择策略：其是为了从当前的群体中选出优良的染色体复制到下一代群体中，染色体的适应度越高，被复制到下一代的可能性就大，适应度差的染色体被遗传到下一代的可能性就越小。 （ 5） 交叉算子：根据选择操作得到的两个染色体个体，以一定的概率按照某种方式互换一些基因，从而得到子代染色体的过程即形成新的子代种群。 （ 6） 变异算子：对染色体个体的某些基因按照一定的概率进行变换即改变自身染色体的基因位。 （ 7） 终止条件：染色体群体经 过选择、交叉、变异，在进化一定的代数后，满足终止的条件就停止计算，并输出所得到的结果。 否则返回步骤（ 3）。 GA 算法的流程图如图 所示： 天津理工大学 20xx 届本科毕业设计说明书 8 开 始产 生 初 始 种 群计 算 个 体 适 应 度 值选 择交 叉变 异满 足 终 止 条件。 输 出 最 优 解结 束否是 图 遗传算法流程图 MATLAB 仿真技术 MATLAB 是一种以矩阵作为基本数据单远的程序设计语言，其具备数据分析、算法实现以及应用开发的交互式开发环境。 MATLAB 分为总包和若干个工具箱，具有强大的数值计算天津理工大学 20xx 届本科毕业设计说明书 9 能力、数据可视化能力与符号计算能力，逐步发展成为各种学科、多种工作平台下功能强大的大型 软件，可以方便实现数值分析、优化分析、数据处理、自动控制、信号处理等领域的数学计算，也可以快捷实现计算可视化、图形控制、场景创建和渲染、图像处理、虚拟现实和地图制作等分析处理工作。 MATLAB 已经成为线性代数、自动控制理论、概率论及数理统计、数字信号处理、时间序列分析、动态系统仿真等课程的基本教学工具。 其中 MATLAB仿真技术在工程上和科学实验上起到很大影响，可以用来完成 系统的设计、性能评估、测试 、 进行数学模型、专业模型的模拟，复杂数值计算等工作。 同时 在经济领域，可以进行数据评价， 高等数值计算、 数值分析和 预测等。 这些功能强大的仿真软件 ,使得 物流系统 仿真的设计和分析过程变得相对直观和便捷 ,由此也使得 车辆路径优化 系统仿真技术得到了更快的发展。 车辆路径优化 系统仿真贯穿着 车辆路径优化 系统工程设计的全过程 ,对 车辆路径优化 系统的发展起着举足轻重的作用。 车辆路径优化 系统仿真具有广泛的适应性和极好的灵活性 ,有助于我们更好地研究 车辆路径优化 系统性能。 天津理工大学 20xx 届本科毕业设计说明书 10 第三章 复杂路径优化问题 问题的描述 车辆路径优化问题可以描述为：从发货中心用一辆汽车向一个收货点送货，这个收货点的位置和需求量一定 ，这辆汽车的负载重量一定，运输方式有三种车 1 运输，车 2 运输，车三运输，合理安排汽车路线，使总运距最短，并满足一下条件：每天送货路径上只有一个收货点和送货点，且只能由一辆汽车送货。 通过分析上述车辆路径优化问题的约束条件和优化目标可知，车辆路径优化问题可以归结为最短路径问题。 本问题为单量汽车的送货路径优化，求得满足经济指标和环境指标的单辆汽车的最优送货路径后。 因此，为便于问题的讨论，本文对单辆汽车的送货路径优化进行研究。 其模型如图 所示： v 0v 2v 1v 3v 4v 5v 6v 7cbcbcbaabcbaaaabcbc6553432363224242314 — a— ：车 1 运输 — b— ：车 2 运输 — c— ：车 3 运输 图 车辆路径优化 VRP 模型 为了更清楚地描述车辆路径问题，我们可以用 ( , , )G V A B 来表示联运网络结合图 的 VRP 模型，其中 V 表示各个节点的集合，而 A 表示节点之间的运输方案集合， B 表示节点之间的中转方案集合，以图 为例，节点有 0V 、 1V 、 2V 3V 、 4V 、 5V 、 6V 以及 7V ，运输方式有车 1 运输，车 2 运输和车 3 运输，中转方案包括中转时间和中转成本，每条路径上的数字 表示各运输方式所需要花费的运输成本，如 0V → 1V 车 1 运输成本 1（万元），车 2运输成本 4（万元），车 3运输成本 6（万元）。 而本文研究的是将运输任务分解成一系列的有顺序的分段运输任务，每个分段运输任务有多个运输者。 相邻的分段运输任务之间存在任务的中转和衔接。 用图 ( , , )G V A B 表示天津理工大学 20xx 届本科毕业设计说明书 11 联运网络； V 表示节点集合， ivV  1,..., 1in表示中转节点、 0v 表示起点、 nv 表示终点；A 表示节点间的运输方案的集合，  ,ijv v m A 表示节点 iv 、 jv 之间的一个运输方案，其中 ，,m M M 表示运输方式集合（同一种运输方式下，若有多个运输者可选择， m 可表示不同的运输者）；当节点 iv 处发生转运时，需要一定的中转时间和中转成本，不同运输方式之间的中转时间、成本存在差异， B 表示中转方案集合，  ,iv p m B 表示在节点 iv 的承运方式 p 和 m 进行转运的中转方案。 在对问题进行进一步研究之前，根据问题的特点，作以下假设： （ 1）只有一个车场且车场与收货点的位置是确定的。 （ 2）收货点的需求量己知。 （ 3）每辆车在进行送货时，其装载量不能超过其最大容量。 （ 4）车场的车辆是同一车型，车辆数目和车辆最大容量事先知道。 （ 5）忽略不确定性因素的影响，认为运输方案和中转方案是已知的、确定性的。 （ 6）不考虑由于受天气状况、 交通状况、路况、节点能力等因素的影响。 问题 的 符号表示 ijms ：运输方式 m 在节点 iv 、 jv 之间运输的碳排放量（ g） ； ijmd ：燃油消耗量（ kg）； me ： 运输方式 m 的碳排放因子（ g/kgfuel）； ijmr ：运输方式 iv 、 jv 之间的平均运输速度； ijl ：节点 iv 、 jv 之间的距离；  ,BTFT ：运输任务时间窗约束，即 货物运达 nv 的时刻应处在时间窗  ,BTFT 内； ipm ：在节点 iv 处自 p 到 m 的中转成本； ijm ：运输者 m 针对节点 iv 、 jv 间的运输成本； ipm ：在节点 iv 处自 p 到 m 的中转时间； ijmt ：运输者 m 针对节点 iv 、 jv 间的运输时间； ijma ： 01 变量，若经营者选择运输方案 ( , , )ijv v m ，则 ijma =1，否则 ijma =0； ipmb ： 01 变量，若在 iv 处 p 和 m 之间存在中转，则 ipmb =1，否则， ipmb =0； 问题的 数学模型 （ 1）碳排放计量为： ijm ijm ms d e， ( , , )ijv v m A ， mM （ ） （ 2）对于一种 给定的运输方式，其单位距离下的燃油消耗量和速度的二次方成正比 [3233]，所以燃油消耗和运输速度之间。