基于改进遗传算法的复杂网络路径优化问题毕业设计说明书.doc

基于改进遗传算法的复杂网络路径优化问题 摘要摘要 随着全球化进程的不断加快 各类型跨国企业在世界范围内的生产 销售 及售后服务推动了原材料 产品及配件在全球的有序流动 在这种全球供应链 的大背景下 大型国际物流公司纷纷依托其覆盖全球的综合运输服务网络为货 主提供 门到门 的物流服务 而各个中小型物流公司也依托该网络开展自己 的业务 在这其中 如何针对日趋复杂的运输网络制定最优的运输路线 无疑 是提高物流公司竞争力和经济效益的关键所在 而我国虽然在交通网的基础设 施建设方面取得了一定进展 但是管理体制和信息化程度的落后严重制约着综 合运输服务的进一步发展 随着我国的集装箱路径优化日趋国际化 这些问题 导致的影响日益突出 而从定量的角度对复杂网络下的路径优化问题进行研究 对于提高我国综合运输服务效率和水平 具有很强的理论价值和广阔的应用前 景 讨论了考虑燃油消耗和碳排放的车辆路径优化问题 以燃油消耗与碳排放 成本最小化为目标 建立了问题的数学模型 根据问题的特点 设计了求解该 问题的改进遗传算法 数据实例的实验计算结果分析表明 应用本文中的模型 及其求解算法 可以得到环境友好的路径规划方案 有效降低运输过程中的碳 排放量 该模型主要考虑运输时间和中转时间的影响 对参与送货的车辆路径 进行优化 从而选取最短路径 设计了一种基于变长染色体改进的遗传算法对 问题进行求解 该算法采用有效的编码方式和特定的交叉算子 成功地实现了 对该问题的求解 此外 应用仿真数据实例的实验计算验证了本文中所提出的 方法的有效性 所得到的近似最优解能够为物流配送企业提供一个令人满意的 车辆调度与路径规划的方案 关键词 碳排放 路径优化 遗传算法 燃油消耗 Complex path optimization problem based on improved genetic algorithm ABSTRACT Along with the accelerating of the globalization process the various types of multinational companies in the world within the scope of the production sale and after sale service to promote the raw materials products and accessories in the global orderly flow in the context of the global supply chain large international logistics companies are relying on its global integrated transport service network for the shipper to provide door to door logistics services and various small and medium sized logistics companies are relying on the network to carry out their business In it how to develop the optimal in view of the increasingly complex network of transport routes is undoubtedly the key to enhance the competitiveness of logistics companies and economic benefits And although in the network infrastructure construction in China has made some progress but the backward management system and information level seriously restricts the further development of comprehensive transportation service Along with the increasingly international container path optimization these problems lead to the influence of the increasingly prominent and from the Angle of quantitative research on the path optimization problem under complex network to improve service efficiency and comprehensive transportation in China has the very strong theory value and broad application prospects Discussed considering fuel consumption and emissions of VRP problems in which the minimum fuel consumption and emissions cost into the goal to establish the mathematical model of the problem According to the characteristics of the problem the improved genetic algorithm is designed to solve the problem Data instance analysis of the experiment results show that application model and its algorithm in this paper can be environment friendly path planning scheme effectively reduce carbon emissions in the process of transportation This model mainly consider the influence of the transportation time and transit time involved in the delivery of the vehicle routing optimization so as to choose the shortest path Designed a kind of improved genetic algorithm based on variable length chromosomes to solve the problem the algorithm adopts effective encoding and specific crossover operator to successfully implement the solution of the problem In addition the application experiment of simulation data instance calculation to verify the effectiveness of the method proposed in this paper the approximate optimal solution can be got by for logistics enterprise to provide a satisfactory vehicle scheduling scheme with path planning Key Words Carbon emission Fuel consumption Path optimization Genetic algorithm 目目 录录 第一章第一章 绪论绪论 1 1 1 1 研究背景及发展概况 1 1 2 研究目的和意义 2 1 2 1 研究目的 2 1 2 2 研究意义 2 1 3 国内外研究现状 2 1 4 本文的研究内容 4 1 5 本文的结构安排 5 第二章第二章 系统关键技术介绍系统关键技术介绍 7 7 2 1 遗传算法 7 2 1 1 遗传算法的基本原理 7 2 1 2 遗传算法的基本步骤 7 2 2 MATLAB 仿真技术 8 第三章第三章 复杂路径优化问题复杂路径优化问题 1010 3 1 问题的描述 10 3 2 问题的符号表示 11 3 3 问题的数学模型 11 第四章第四章 改进遗传算法设计改进遗传算法设计 1313 4 1 染色体编码方式 13 4 2 初始种群的生成 13 4 3 适应度函数的建立 13 4 4 选择策略 14 4 5 交叉算子 14 4 6 变异算子 14 4 7 终止条件 14 4 8 算法步骤 15 第五章第五章 算例分析算例分析 1717 5 1 验证算法 17 5 2 仿真实验 18 第六章第六章 总结总结 2020 I 参考文献参考文献 2121 致谢致谢 2323 天津理工大学 2015 届本科毕业设计说明书 0 第一章 绪论 1 1 研究背景及发展概况 社会主义市场经济的发展带动了物流运输业的飞速发展 物流运输业已经成为经济发展 的主要推动力 因而被誉为 第三利润源泉 越来越多的企业关注物流 在这其中 如何 针对日趋复杂的运输网络制定最优的运输路线 无疑是提高物流公司竞争力和经济效益的关 键所在 物流业融合多种产业形成一种复合型服务产业 是国民经济的重要组成部分 涉及领域 广 吸纳就业人数多 促进生产 拉动消费作用大 在经济方式的转变和加快产业结构调整 等方面发挥着重要作用 我国物流业已进入转型升级的新阶段 但是 物流业发展总体水平 还不高 发展方式比较粗放 其物流成本较高 效率较低 条块分割严重 阻碍物流业发展 的体制机制障碍仍未打破且政策法规体系还不够完善 市场秩序不够规范 已经出台的一些 政策措施有待进一步落实 一些地方针对物流企业的乱收费 乱罚款问题突出 信用体系建 设滞后 物流业从业人员整体素质有待进一步提升 1 在社会经济中 物流的位置是无法替代的 它是经济中的流通 经济中的物流以及运输 同时 随着经济的快速发展 环境问题越来越严重 许多国家开始实施节能减排政策 以减 少对环境的污染 企业也更加关注在进行货物运输过程中车辆的燃油消耗和碳排放 减少车 辆在运输过程中的碳排放有助于减少对环境的污染 绿色出行的观念已经深入人心 可以为 企业带来巨大的社会效益 并且碳排放交易已经走进中国市场 减少碳排放就是在节约金钱 因此提升物流经济效益成为关键 遗传算法是由美国 Michigan 大学的 J Holland 教授于 1975 年首先提出的一种模拟自然 界生物进化过程的全局随机优化算法 遗传算法结合了计算机科学与进化论思想 根据于生 物进化机制与遗传学原理 依据 优胜劣汰 和 适者生存 的原则 通过模拟自然界中生 物群体由低级 简单到高级 复杂的生物进化过程 使所要解决的问题从初始解逐渐逼近最 优解或准最优解 2 遗传算法是以自然选择和遗传理论为基础 以一种群体的所有个体为对象 将生物进化 过程中适者生存规则与染色体信息交换机制有效的结合起来 利用随机化技术对一个被编码 的参数空间进行高效搜索 能自动获得和积累搜索过程中的空间知识 是一种高效的全局寻 优方法 在遗传算法中 问题不同解被假设成 种群 中不同个体 即染色体 各染色体 通过交叉 变异产生下一代染色体 即后代 适应值高的染色体具有比较高的选中概率 经过若干代操作将产生最好的染色体 遗传操作主要包括选择 交叉和变异 遗传算法的核心内容包括参数编码 初始群体设 定 是适应度函数设计 遗传操作设计和控制参数设定 3 天津理工大学 2015 届本科毕业设计说明书 1 1 2 研究目的和意义 1 2 1 研究目的 在车辆调度送货的作业中 大的物流公司一般提前若干时间 向收货点发货 物流公司 根据计划期内 对车辆进行调度安排 每辆车为了顺利完成装卸任务 保证其在计划时刻到 收货点 必然会出现选择较短的出行路线以减少路上消耗的能源等 这就要求对车辆路径进 行合理的规划 由于遗传算法属于一种基于自然选择和遗传变异等生物进化机制而发展起来的高度并行 随机 自适应的智能全局搜索算法 遗传算法 GA 的应用范围非常广泛 4 5 用于来解决 传统搜索方法无法解决的非线性问题 由于遗传算法能在解决组合优化问题上展现出良好的 特性 将遗传算法应用到车辆调度与路径优化问题中去 有助于解决其车辆路径的复杂度 使得求解车辆最短路径问题得到很大进步 优化车辆路径 实现对现有资源合理分配 有效 利用以及减少了环境污染 达到成本最低或效率最高的目标 本课题的研究目的是对车辆路径的选择与规划问题进行研究 以车辆的最短路径为研究 对象 以车辆的碳排放量费用和成本为约束条件来确定最短路径 从而降低成本 1 2 2 研究意义 在送货过程中 核心内容就是送货了 在物流活动中 货物的运输就是送货的实际形态 可是远距离的运输和配送运输还是有本质的区别 他们的送货路程是不相同的 远距离运输 属于长途运输 也就是不同区域之间的运输 配送运输是属于短途运输 送货路线短但较繁 杂 即便是同一条线路的短途运输可能会因为线路复杂 碳排放量多等问题造成总成本过高 所以合理规划运输路线对送货成本的影响要比一般的运输大很多 合理的规划配送路线有利 于对送货速度 成本等实现有效的控制 因此 设计合理有效的路径方案对企业和社会具有 十分重要的意义 对企业来讲 1 合理规划了送货路径有利于节省成本 2 降低了碳排放量 减少 了环境污染 有利于提高企业的社会形象 3 有利于企业提高经济效益 对社会来讲 随着全球气候变暖以及大气污染的不断加剧 人们对环境问题越来越关注 降低能源消耗 减少碳排放逐渐引起大家的重视 全球气候变暖的主要原因是来自于二氧化 碳的排放 而二氧化碳的排放主要是来源于化石燃料的燃烧 研究车辆调度与路径规划问题 对于减少碳排放 抑制气候变暖以及缓解交通堵塞 减少噪声等有重要意义 1 3 国内外研究现状 车辆路径优化问题 Vehicle Routing Problem 是经典的优化组合问题 最早由 Dantizing 和 Ramser 6 在 1959 年提出 涉及到很多领域和应用 而且 VRP 及其变种已经被 广泛的研究 直到 Min 7 意识到在实际情况中同一结点同时取送货的可能性 介绍了同时取 送货车辆路径问题 vehicle routing problem with simultaneous pickups and deliveries VRPSPD 同时取送货车辆路径问题已经成了物流运输中非常普遍的问题 例 天津理工大学 2015 届本科毕业设计说明书 2 如快递员在送货的同时进行取货 配送对环境污染大的电子产品的同时 对废旧产品进行回 收 这就要求企业在规划车辆路径时 同时考虑顾客的送货和取货需求 以最小化运营成本 以及减少环境污染 Montane 和 Galvao 8 研究了 VRPSPD 问题 提出了一个基于 VRPSPD 的货 物流模型 Dell Amico et al 9 在 Montane 和 Galvao 提出的数学模型的基础上 采用分支 定价方法成功的对中小规模的 VRPSPD 问题进行了求解 对于规模较大的 VRPSPD 问题 目前 的研究主要采用启发式或者元启发式的方法 Dethloff 10 研究了车辆行驶距离 TD 车辆 剩余的负载量 RC 辐射附加费 RS 以及三者的组合 RCRS 这四种不同的插入准则 Nagy 和 Salhi 11 在考虑车辆路径变化和可行解之间关系的基础上 设计了一个综合启发式算 法解决了 VRPSPD 问题 在算法运行过程中 先找到一个 VRP 问题的可行解 然后按照 VRPSPD 问题的特点进行修改 使其也适合于 VRPSPD 问题 最后采用复合的改进的启发式算 法对解进行改进 Chen 和 Wu 12 采用成本最小化的启发式算法生成初始解 接着采用 TS 算法 和车辆路径改进程序对解进行了改进 Bianchessi 和 Righini 13 进行了大量的数值仿真实验 提出了一些比较新颖的 TS 算法 然后对这些算法进行了比较 随着物流业的高速发展 国内越来越多的学者和专家开始研究 VRP 问题以及其变种问题 一些主要的研究如下 肖健梅 李军军 王锡淮 14 研究了 VRP 问题 设计了一种新颖的编码 方式 并通过对微粒群算法进行改进 成功对该问题进行了求解 符桌 15 研究了开放式的 VRP 问题 考虑了车辆的装载容量的约束 并用禁忌搜索算法对问题进行了求解 马建华 房勇 袁杰 16 以最快完成为目标研究了 VRP 问题 考虑了多种车辆型号和多个配送中心等约 束条件 用变异的蚁群算法对问题进行了求解 彭春林 梁春华 周泓 17 研究了 VRPSPD 问题 并设计了改进的遗传算法 算法采用边 重组的交叉操作 成功对该问题进行了求解 张涛 余绰娅 刘岚 18 等人建立了 VRPSPD 问 题的机会约束规划模型 并根据问题的特点 设计了改进的分散搜索算法对问题进行了求解 张涛 田文馨 张杰 刘士新 19 研究了 VRPSPD 问题 考虑了车辆的最大行程约束条件 建 立了问题的混合整数规划数学模型 并设计了改进的蚁群算法 对该问题进行了求解 张涛 张春梅 张玥杰 20 针对 VRPSPD 问题 建立了问题的数学模型 设计了协同粒子群 模拟退火 算法 成功对该问题进行了求解 胡大伟 陈诚和郭晓汾 21 研究了多车场 VRPSPD 问题 采 用多阶段方法得到了最优解 龙磊 陈秋双等 22 研究了 VRPSPD 问题 并建立了数学模型 设计了改进的 GA 算法 算法采用特定的交叉算子和种群更新方法 成功解决了该问题 曹二保 23 研究了 VRP SPDTW 问题 建立了问题的模型 对 GA 算法进行了改进 算法采 用特殊的交叉变异操作 蓝伯雄 24 等人研究了 VRP SPDTW 问题 并设计了一种改进的 TS 算 法 殷佳林 25 等人在蚁群算法的基础上进行了改进 研究了 VRP SPDTW 问题 最后进行了仿 真实验 结果证明了算法可以成功的解决此类问题 段凤华 26 针对 VRPSPDTW 问题 考虑了 硬时间窗约束条件 设计了改进 TS 算法 郎茂祥 27 采用了 TS 算法和模拟退火算法对 VRPSPDTW 问题进行了研究 研究中考虑的是软时间窗约束 郭耀煌和李军 28 研究了车辆满 载情况下 VRPSPDTW 问题 并用启发式方法得到了车辆路线 张燕 周支力和翟斌 29 对传 统标号算法进行了改进 研究了 VRPSPDTW 问题 天津理工大学 2015 届本科毕业设计说明书 3 遗传算法在车辆路径优化问题 VRP 中的应用十分有利 并且遗传算法是一种全局优 化概率算法 葛继科 30 等人介绍了遗传算法的基本工作原理和主要特点 概述了遗传算法 的常见应用领域 分析了近五年国内对遗传算法的研究现状 赵振勇 31 等人给出了遗传算法 的改进方法 并对系统进行了分析和研究 1 4 本文的研究内容 本课题从车辆路径的选择与规划问题进行研究 以车辆的最短路径为研究对象 建立了 考虑环境指标和经济指标的车辆路径优化问题的多目标数学模型 以车辆的运输时间和中转 时间为约束条件来确定最短路径降低成本 之后设计了求解该问题的改进遗传算法 最后用 标准的车辆路径优化问题算例做了仿真实验 通过对实验结果的分析验证了算法的正确性 本文结构路线图如图 1 1 所示 天津理工大学 2015 届本科毕业设计说明书 4 VRP问题优化研究 研究背景 意义和 现状 VRP求解方法VRP问题概述VRP模型构建 VRP描述组成 模 型 分类 求解算法设计遗传算法介绍 遗传算法原理 工 作过程 特点 GA具体方案 染色 体 种群 适应 度 遗传算子等 算例分析 时间窗描述 分类 总结及展望 图 1 1 结构路线图 1 5 本文的结构安排 本文共分为五章 各章的主要内容安排如下 第一章介绍了复杂网络下的路径优化问题的研究背景 相关技术的发展概况 研究的目 的和意义以及国内外在遗传算法进化过程中等领域的研究现状 并分析了在这些前提下 基 于改进遗传算法的复杂路径优化问题的优势 天津理工大学 2015 届本科毕业设计说明书 5 第二章介绍了实现基于改进遗传算法的复杂网络路径优化问题时所使用的关键技术 详 细地阐述了在遗传算法中编码 生成初始种群 适应性值评估 选择 交叉 变异 确定最 优解等实现遗传算法等技术的工作原理以及仿真实验的介绍 第三章复杂网络路径优化问题的描述了该优化问题的符号含义 并设计了该优化问题所 使用的数据模型 并深入地描述了该优化问题的求解方法 第四章具体地说明了对基于改进遗传算法的复杂网络路径优化问题进行了改进遗传算法 的设计 第五章通过算例分析进行仿真实验 通过详细的测试对该问题进行了可行性验证以及对 结果的分析 第六章总结了在开发基于改进遗传算法的复杂网络路径优化问题时所遇到的各种问题 在总结的过程中对这些问题进行深入的思考 提出了未来可以进一步改进的解决方案 天津理工大学 2015 届本科毕业设计说明书 6 第二章 系统关键技术介绍 2 1 遗传算法 2 1 1 遗传算法的基本原理 遗传算法 Genetic Algorithm GA 是 Holland 和 Bagley 于 1975 年提出 它是一种借 鉴生物进化机制演化而来的自适应随机搜索算法 遗传算法从一定的初始群体开始进化 从 中筛选出优良的染色体 通过一代一代的进化 使整个群体适应性更好 经过一定代数的进 化之后 最终找到最优的个体 其中在每一代的群体中 按照每个染色体的适应性优劣 选 择出一些良好的染色体复制到下一代种群中 接着通过染色体之间的交叉 变异生成新的染 色体 2 1 2 遗传算法的基本步骤 在遗传 GA 算法中 首先通过一定的编码方式生成初始群体 然后在每个染色体上执 行选择算子 Selection Operator 交叉算子 Crossover Operator 变异算子 Mutation Operator 这些操作 并从中选出适应度高的染色体进化 从而实现优胜劣汰 的进化过程 算法的具体操作过程如下 1 染色体编码 GA 不能对问题的一些参数进行直接处理 所以需要将问题的解通过 一定的编码方式编码为染色体 染色体编码的好坏直接影响计算消耗的时间 算法运行的快 慢 所以一般情况下为节省算法运行时间采用自然数直接编码的方式 2 初始化 对问题的参数进行初始化 并按照一定的方法生成初始的染色体群体 一个染色体对应着一个配送方案 3 计算适应度值 适应度函数用来判定染色体的优良程度 常常根据问题的特点 选取一定的函数作为适应度函数 为了能迅速判定染色体的优良程度 就要拉大优良个体的 适应度值 基于序的评价函数就有利于拉大个体之间的适应度值 基于序的评价函数首先就 是对种群中所有的个体按照总距离的大小进行排序 每一个个体要给与一个队列序号 总的 距离越小 序号越靠前 4 选择策略 其是为了从当前的群体中选出优良的染色体复制到下一代群体中 染 色体的适应度越高 被复制到下一代的可能性就大 适应度差的染色体被遗传到下一代的可 能性就越小 5 交叉算子 根据选择操作得到的两个染色体个体 以一定的概率按照某种方式互 换一些基因 从而得到子代染色体的过程即形成新的子代种群 6 变异算子 对染色体个体的某些基因按照一定的概率进行变换即改变自身染色体 的基因位 7 终止条件 染色体群体经过选择 交叉 变异 在进化一定的代数后 满足终止 的条件就停止计算 并输出所得到的结果 否则返回步骤 3 GA 算法的流程图如图 2 1 所示 天津理工大学 2015 届本科毕业设计说明书 7 开始 产生初始种群 计算个体适应度值 选择 交叉 变异 满足终止条 件 输出最优解 结束 否 是 图 2 1 遗传算法流程图 2 2 MATLAB 仿真技术 MATLAB 是一种以矩阵作为基本数据单远的程序设计语言 其具备数据分析 算法实现 以及应用开发的交互式开发环境 MATLAB 分为总包和若干个工具箱 具有强大的数值计算 天津理工大学 2015 届本科毕业设计说明书 8 能力 数据可视化能力与符号计算能力 逐步发展成为各种学科 多种工作平台下功能强大 的大型软件 可以方便实现数值分析 优化分析 数据处理 自动控制 信号处理等领域的 数学计算 也可以快捷实现计算可视化 图形控制 场景创建和渲染 图像处理 虚拟现实 和地图制作等分析处理工作 MATLAB 已经成为线性代数 自动控制理论 概率论及数理统 计 数字信号处理 时间序列分析 动态系统仿真等课程的基本教学工具 其中 MATLAB 仿真技术在工程上和科学实验上起到很大影响 可以用来完成系统的设计 性能评估 测试 进行数学模型 专业模型的模拟 复杂数值计算等工作 同时在经济领域 可以进行数据评价 高等数值计算 数值分析和预测等 这些功能强大的仿真软件 使得物 流系统仿真的设计和分析过程变得相对直观和便捷 由此也使得车辆路径优化系统仿真技术 得到了更快的发展 车辆路径优化系统仿真贯穿着车辆路径优化系统工程设计的全过程 对 车辆路径优化系统的发展起着举足轻重的作用 车辆路径优化系统仿真具有广泛的适应性和 极好的灵活性 有助于我们更好地研究车辆路径优化系统性能 天津理工大学 2015 届本科毕业设计说明书 9 第三章 复杂路径优化问题 3 1 问题的描述 车辆路径优化问题可以描述为 从发货中心用一辆汽车向一个收货点送货 这个收货点 的位置和需求量一定 这辆汽车的负载重量一定 运输方式有三种车 1 运输 车 2 运输 车 三运输 合理安排汽车路线 使总运距最短 并满足一下条件 每天送货路径上只有一个收 货点和送货点 且只能由一辆汽车送货 通过分析上述车辆路径优化问题的约束条件和优化目标可知 车辆路径优化问题可以归 结为最短路径问题 本问题为单量汽车的送货路径优化 求得满足经济指标和环境指标的单 辆汽车的最优送货路径后 因此 为便于问题的讨论 本文对单辆汽车的送货路径优化进行 研究 其模型如图 3 1 所示 v0 v2 v1 v3 v4 v5 v6 v7 c b c b c b a a b c b a a a a b c b c 6 5 5 3 4 3 2 3 6 3 2 2 4 2 4 2 3 1 4 a 车 1 运输 b 车 2 运输 c 车 3 运输 图 3 1 车辆路径优化 VRP 模型 为了更清楚地描述车辆路径问题 我们可以用来表示联运网络结合图 3 1 GV A B 的 VRP 模型 其中表示各个节点的集合 而表示节点之间的运输方案集合 表示节点VAB 之间的中转方案集合 以图 3 1 为例 节点有 以及 运输方 0 V 1 V 2 V 3 V 4 V 5 V 6 V 7 V 式有车 1 运输 车 2 运输和车 3 运输 中转方案包括中转时间和中转成本 每条路径上的数 字表示各运输方式所需要花费的运输成本 如 车 1 运输成本 1 万元 车 2 运输成 0 V 1 V 本 4 万元 车 3 运输成本 6 万元 而本文研究的是将运输任务分解成一系列的有顺序的分段运输任务 每个分段运输任务 天津理工大学 2015 届本科毕业设计说明书 10 有多个运输者 相邻的分段运输任务之间存在任务的中转和衔接 用图表示联 GV A B 运网络 表示节点集合 表示中转节点 表示起点 表示终点 V i vV 1 1in 0 v n v 表示节点间的运输方案的集合 表示节点 之间的一个运输方案 其中 A ij v v mA i v j v 表示运输方式集合 同一种运输方式下 若有多个运输者可选择 可表示不同 mM M m 的运输者 当节点处发生转运时 需要一定的中转时间和中转成本 不同运输方式之间 i v 的中转时间 成本存在差异 表示中转方案集合 表示在节点的承运方式B i v p mB i v 和进行转运的中转方案 pm 在对问题进行进一步研究之前 根据问题的特点 作以下假设 1 只有一个车场且车场与收货点的位置是确定的 2 收货点的需求量己知 3 每辆车在进行送货时 其装载量不能超过其最大容量 4 车场的车辆是同一车型 车辆数目和车辆最大容量事先知道 5 忽略不确定性因素的影响 认为运输方案和中转方案是已知的 确定性的 6 不考虑由于受天气状况 交通状况 路况 节点能力等因素的影响 3 2 问题的符号表示 运输方式在节点 之间运输的碳排放量 g ijm sm i v j v 燃油消耗量 kg ijm d 运输方式的碳排放因子 g kg fuel m em 运输方式 之间的平均运输速度 ijm r i v j v 节点 之间的距离 ij l i v j v 运输任务时间窗约束 即货物运达的时刻应处在时间窗内 BT FT n v BT FT 在节点处自到的中转成本 ipm i vpm 运输者针对节点 间的运输成本 ijm m i v j v 在节点处自到的中转时间 ipm i vpm 运输者针对节点 间的运输时间 ijm tm i v j v 0 1 变量 若经营者选择运输方案 则 1 否则 0 ijm a ij v v m ijm a ijm a 0 1 变量 若在处和之间存在中转 则 1 否则 0 ipm b i vpm ipm b ipm b 3 3 问题的数学模型 1 碳排放计量为 3 1 ijmijmm sde ij v v mA mM 2 对于一种给定的运输方式 其单位距离下的燃油消耗量和速度的二次方成正比 32 33 所以燃油消耗和运输速度之间的非线性关系为 3 2 2 ijmmijmij drl 则目标函数为 3 3 1 min iji ijmijmipm ipm v vmAv p mB fab 天津理工大学 2015 届本科毕业设计说明书 11 3 4 2 min ij ijmijm v vmA fs a s t 3 5 iji ijmijmipm ipm v vmAv p mB BTt abFT 3 6 j Vj V jimijm vm Mvm M aa 0 0 1 1 0 i in in vv vv vVv v 3 7 1 ipm p M m M b 0 in vVv v 3 8 ipm p M m M b j V ijm vm M a 0 in vVv v 3 9 0 0b 0 n b 3 10 0 1 ijm a ij v v mA 3 11 0 1 ipm b ip v vmB 其中 模型包含两个指标 式 3 3 表示考虑成本指标 式 3 4 表示考虑碳排放指 标 式 3 5 表示关于时间窗的约束 式 3 6 表示节点流量平衡约束 式 3 7 3 8 表示每个节点至多被访问一次 式 3 9 表示在起点 终点处不计时间和成本 式 3 10 3 11 表示决策变量的取值约束 天津理工大学 2015 届本科毕业设计说明书 12 第四章 改进遗传算法设计 4 1 染色体编码方式 染色体的编码对遗传算法的实现尤为重要 不同的染色体编码决定了算法的运行时间 以及解码的难易程度 常用的编码方式有两种 用二进制数表示和用自然数表示 用二进制 表示染色体 解码很困难 运算消耗时间长 算法效率低 本文根据所要研究问题的特点采 用自然数来进行染色体编码 自然数编码比二进制编码更加简单 直接 路径中节点数目的 不确定性也要求染色体的长度具有可变性 处于简单表示 计算机处理方便这里运用整数编码方式 假设为中从到的一条hG 0 v n v 路径 为一个染色体编码 如图 4 1 所示 其染色体编码包含了运输方式和中 0 n hvv 转方式的选择 图 4 1 网络图 G 4 2 初始种群的生成 为了保持个体的多样性 使初始种群尽可能均匀地分布在整个解空间 采用随机方式生 成初始种群 采用基于通道最短路径法 具体步骤如下 1 以 作为网络 G 中边和节点上的时间参数 求解出条时间最短路 即 ijm E t ipm E 1 L 条染色体 1 L 2 以 作为网络 G 中边和节点上的成本参数 求解出条成本最短路径 ipm ijm 2 L 3 随机生成条路径 3 L 4 初始种群的染色体数量 123 LLLL 4 3 适应度函数的建立 GA 算法通过适应度函数来判定一个染色体的好坏程度 而本问题中 目标函数是最小 化总成本 即适应度函数值越小 对应的染色体的适应度就越大 所以直接采用目标函数值 的倒数作为适应度函数 天津理工大学 2015 届本科毕业设计说明书 13 设 分别表示路径 h 的运输成本 运输时间和碳排放量 h t h s h max min 分别表示 的上限 下限 max s min s h t h 路径 h 的适应度函数为 4 1 1 f h z h 其中 4 2 ijiij ijmijmipm ipmijmijm v vmAv p mBv vmA z habs a 4 4 选择策略 选择策略是为了从当前的群体中选出优良的染色体复制到下一代群体中 染色体的适应 度越高 被复制到下一代的可能性就就大 适应度差的染色体被遗传到下一代的可能性就越 小 本论文采用轮盘赌和最佳保留相结合的方法为选择个体的依据 4 5 交叉算子 交叉算子又称重组 Recombination 是用根据选择操作得到的两个染色体个体 以 一定的概率按照某种方式互换一些基因 从而得到子代染色体的过程 当有 2 个以上的公共 节点时 按照等概率选择其中之一作为交叉点 本文采用的交叉算子 在进行交叉过程中进行互换的最小整体为线路 如 父染色体为 11235610 hv v v v v v 2134710 hv v v v v 交叉点为 子染色体为 3 v 112310 hv v v v 213456710 hv v v v v v v 4 6 变异算子 变异算子是通过一定的方式改变染色体个体的一些基因位 从而产生新的染色体 在 GA 算法中 变异可以扩大算法的搜索空间 保持群体中染色体个体的多样化 从而避免了 局部最优解的产生 本文针对送货车辆路径问题的特点 采用基因插入 新网络删除 变换等操作 设 中是从到的一条路径 具体的操作如下 GVA 0 fghn hvvvvv 0 v n v 1 基因插入 若 则 gj vv jh v vA 0 fgjhn hvvvv vv 2 基因删除 若 则 fh vvA 0 fhn hvvvv 3 基因变换 若 且 则 fj vv jh v vA gj vv 0 fjhn hvvv vv 4 7 终止条件 本文设计的算法终止条件如下 当某一解连续进化一定的代数后 其适应度值仍然没有变化 就终止算法 把得到的结 天津理工大学 2015 届本科毕业设计说明书 14 果输出 如果一直进化 当算法运行到预先设定的最大的进化代数时 就终止算法 把得到 的结果输出 4 8 算法步骤 改进遗传算法的步骤如下 表示当前代数 表示个体计数器 geni Step 1 把车辆的可行的路径按照本文的编码方式编码为染色体 Step 2 初始化算法的参数 Step 3 生成初始的染色体种群 Step 4 0 gen Step 5 0 i Step 6 计算群体中第 个染色体个体的适应度 i Step 7 1 ii Step 8 若 n 回到 Step 6 否则跳转到 Step 9 i Step 9 根据适应度选择父代 Step 10 进行交叉和变异操作 Step 11 1 gengen Step 12 如果满足算法的终止条件 则停止 否则跳转到 Step 5 改进 GA 算法的流程图如图 4 2 所示 天津理工大学 2015 届本科毕业设计说明书 15 使用整数编 码 构造可行 线路的染色体 设置控制 参数 产生初始群体 P 0 是否满足 终止条件 计算适应度 输出结果 结束 i N 选择遗传算子 gen gen 1 选择两个个体 执行交叉 将两个子代串 插入到新群体 i i 1 选择一个个体选择一个个体 执行复制执行变异 插入到新群体插入到新群体 是 否 i 0 是 gen 0 否 i i 1 Pc Pm 图 4 2 改进遗传算法流程图 天津理工大学 2015 届本科毕业设计说明书 16 第五章 算例分析 5 1 验证算法 本文是依据实际数据的取值范围 问题实例随机产生 对随机模型以及求解方法的有效 性进行验证 实验以中国内陆 A 城市到中国内陆城市 B 的综合网络为例 参考某集团的近期 中国交通网络数据 运输路线为中国交通网络运输 在节点数为 16 的情况下 生成综合网 络拓扑结构 如图 5 1 所示 承运人 其中 表示车 1 运输承运人 表示中国内陆 1234567 Pp pppppp 1 p 2 p 铁路承运人 表示车 2 运输承运人 表示中国内陆公路承运人 表示车 3 p 4 p 5 p 6 p 7 p 3 运输承运人 为简化计算 将一小时作为一个时间单位 十公里作为一个距离单位 1 4 3 2 10 9 8 7 6 516 15 14 12 13 11 图 5 1 综合网络拓扑结构 按照实际距离的取值范围 生成节点间的距离 某集团采用了表 1 给出的 IPCC 国家 ij d 温室气体清单指南发布的不同运输方式的排放因子 单位为 g kg fuel p p 表 1 各种运输方式的碳排放因子 运输方式IPCC 车 1车 2车 3 p 311031473185 根据上述情景进行仿真实验 在 BT FT 500 560 的情况下 按照均匀分布在指定参 数区间内随机生成 10 实例 表示随机生成的一组 1 M 2 M 10 M i M ipm 即联运网络 算法采用 Matlab7 0 编程实现 所得结果在平台下测试得到 ijm ipm ijm t 本文为验证算法的有效性 采用贪婪算法和遗传算法 利用适应度函数公式 4 1 4 2 来进行验证 当 0时 即不考虑碳排放量 比较贪婪算法和遗传算法的求解时间 和方案成本 time 表示求解时间 cost 表示方案成本 则验证算法如表 2 天津理工大学 2015 届本科毕业设计说明书 17 表 2 贪婪算法与遗传算法相比较 贪婪算法遗传算法实例 timecosttimecost 13 66544 673 70 518 73 21 17565 941 18 538 99 33 70588 053 74 560 05 44 35571 804 39 544 57 53 11557 043 14 530 51 63 10552 813 13 526 49 73 36591 113 39 562 96 82 54554 352 57 527 95 93 19580 513 22 552 87 100 43565 620 43 538 69 从表 2 可以看出 在求解时间方面 贪婪算法和遗传算法求解时间相接近 但在方案成 本方面 相比采用贪婪算法 采用遗传算法的方案成本明显较低 5 2 仿真实验 根据验证算法的比较结果得出采用遗传算法更具有效性 则设初始种群为 10 进化次 数为 50 交叉 变异概率分别为 0 7 和 0 1 在考虑碳排放指标 0 和不考虑碳排放指 标 1 情况下进行模拟 M C 表示运输成本 单位为万元 M S 表示碳排放量 单位为 kg 结果如表 3 所示 表 3 求解质量 考虑碳排放指标不考虑碳排放指标实例 M CM SM CM S 1523 9235263 98 518 73 43535 77 2544 3829926 30 538 99 29376 71 3554 5019185 25 560 05 26645 79 4550 0224519 77 544 57 31843 88 5535 8241214 64 530 51 43845 36 6531 7537778 89 526 49 43423 94 7557 3922683 14 562 96 31948 08 8533 2330885 80 527 95 42896 96 9558 4020849 78 552 87 23965 21 10544 0822372 89 538 69 30647 80 天津理工大学 2015 届本科毕业设计说明书 18 490 500 510 520 530 540 550 560 570 123456789 实例 万元 考虑碳排放指标M C不考虑碳排放指标M C 图 5 2 考虑与不考虑碳排放量的成本比较 0 10000 20000 30000 40000 50000 123456789 实例 千克 考虑碳排放指标M S不考虑碳排放指标M S 图 5 3 考虑与不考虑碳排放量的比较 从仿真结果可以看出 一方面考虑碳排放指标下求解结果可以减排2 63 12 02 吨 2 CO 另一方面由于碳排放指标中对运输速度的考虑 而导致相比不考虑碳排放的情况 运输成本 增加幅度较小 天津理工大学 2015 届本科毕业设计说明书 19 第六章 总结 随着经济的发展 环境问题严峻 全球各国日益重视碳排放 车辆在运输过程中碳排放 量被更多消费者和物流企业所关注 如何合理安排车辆的路径 在不显著改变物流企业运作 成本的情况下 使得燃油消耗和碳排放成本得到明显的降低 已经成为多数企业的选择 本 文针对考虑燃油消耗和碳排放的 VRP 问题进行了研究 主要的研究工作总结如下 1 首先针对考虑燃油消耗和碳排放的 VRP 问题 然后建立了相应的数学模型 并设计 了改进 TS 算法 算法中采用有效的解的表示方式 初始解的产生 解的评价方法 终止条 件以及算法的框架 最后进在标准的 VRP 算例上行了仿真实验 并对结果进行了分析 2 接着在前人的工作基础上 着重研究了带时间窗的同时取送货绿色车辆调度与路径 规划问题 重点关注了燃油消耗和碳排放成本 3 以燃油消耗与碳排放 成本的最小化为目标 建立了取送货绿色车辆调度与路径规 划问题的数学模型 该模型主要考虑行驶距离对燃油消耗和碳排放量的影响 对以车辆的运 输时间和中转时间为约束条件来确定最短路径降低成本进行决策 4 设计了一种改进的遗传算法对取送货绿色车辆调度与路径规划问题进行求解 该算 法采用有效的编码方式和特定的交叉算子 成功的实现了该问题的求解 5 仿真实验结果表明该方法可以得到一个令人满意的车辆调度与路径规划的方案 此 方案可以在不显著改变物流企业运作成本的情况下使得燃油消耗和碳排放成本得到了明显的 降低 为企业在进行车辆调度时提供了有益的参考思路 天津理工大学 2015 届本科毕业设计说