基于人工蜂群算法的考虑碳排放的带时间窗车辆路径问题研究

摘要

带时间窗车辆路径问题（Vehicle Routing Problem with Time Windows，VRPTW）作为VRP（Vehicle Routing Problem，VRP）的一个主要分支，一直是运筹学领域的热点研究问题，同时也是关乎到国计民生的物流领域的热点和难点问题。它要求车辆在规定的时间将确定的货物送到指定的地点，是研究最小运输成本的货物配送问题。
　　在如今倡导低碳经济的大背景下，绿色物流受到了政府和商业组织越来越多的关注，因为从长远来看当前的物流战略是不可持续的。因此在设计物流策略时除了传统的经济成本，环境、生态、社会效益也应该考虑在内。交通运输在物流中占主要部分，这点不可否认，因此环境敏感的物流政策需要改变其自身的运输方案，使其转变成对生态环境有更少负面影响的可持续的配送网络。研究VRPTW问题的碳排放具有十分重要的现实意义。
　　本文一开始对车辆路径问题的定义及模型进行了简单回顾，并对其扩展问题进行了分类介绍，重点介绍了VRPTW的特点及其模型，并总结了当前求解VRPTW的常规方法。然后引入一种群集智能算法-人工蜂群算法(ABC)，作为本文提及模型的求解方法。算法设计可以分为两部分:第一部分根据VRPTW的时间窗以及车辆容量约束，结合当前应用比较成功的初始解生成方法以及局部搜索方法，设计适合于此问题的ABC算法(ABC1)，并用标准测试集验证可行性。最后从跟随蜂以及侦查蜂选择，邻域搜索三方面对ABC算法进行改进(ABC2)，用相同的测试集比较，证明改进后算法的优越性。第二部分针对考虑碳排放的带时间窗车辆路径问题（Emission Vehicle RoutingProblem with Time Windows，EVRPTW）建立相应模型，在相同参数下，用ABC2对两个模型进行求解，对结果进行比较。实验结果分为两方面:第一通过Solomon标准测试集证明了ABC2在求解VRPTW的有效性;第二通过对两个模型计算结果的对比说明尽管在考虑碳排放的情况下行驶距离略有增加，但碳排放量有较明显的减少，证明通过改变优化目标来降低碳排放有一定的理论可操作性。

目录

声明

摘要

1 绪论

1．1 研究背景及意义

1．1．1 研究背景

1．1．2 研究意义

1．2 国内外研究现状

1．2．1 带时间窗车辆路径问题国内外研究现状

1．2．2 考虑碳排放的车辆路径问题国内外研究现状

1．3 研究内容

1．4 技术路线

2 车辆路径问题概述

2．1 车辆路径问题概述

2．1．1 旅行商问题

2．1．2 车辆路径问题介绍

2．1．2 经典车辆路径问题模型

2．1．2 车辆路径问题分类

2．2 带时间窗车辆路径问题概述

2．2．1 带时间窗车辆路径定义

2．2．2 带时间窗车辆路径问题模型

2．3 VRPTW问题的求解算法

2．3．1 启发式算法

2．3．2 元启发式算法

2．3．3 各种算法的比较

2．4 本章小结

3 人工蜂群算法及其VRPTW中的初步应用

3．1 人工蜂群算法

3．1．1 群集智能算法的一般特性

3．1．2 人工蜂群算法的基本原理

3．2 人工蜂群算法在VRPTW中的简单应用

3．2．1 初始解生成

3．2．2 可行性检查方法

3．2．3 邻域搜索

3．2．4 侦查蜂过程

3．2．5 实验数据

3．2．6 实验结果

3．3 本章小结

4 人工蜂群算法改进及在EVRPTW中的应用

4．1 人工蜂群算法改进

4．1．1 邻域搜索策略改进

4．1．2 跟随蜂选择以及侦查蜂选择改进

4．1．3 改进人工蜂群算法流程

4．1．3 结果比较

4．2 考虑碳排放的带时间窗车辆路径问题

4．2．1 基于两种不同目标函数的简单对比

4．2．2 ABC2求解EVRPTW

4．3 本章小结

结论

参考文献

攻读硕士学位期间发表学术论文情况

致谢