求解双层车辆路径问题的改进人工蜂群算法

作     者：林镇泽 

作者单位：华南理工大学 

学位级别：硕士

导师姓名：黄翰

授予年度：2014年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：大规模邻域搜索 人工蜂群算法 双层次车辆路径问题 破坏与修复操作 

摘      要：本文提出了一种基于大规模邻域搜索的改进人工蜂群算法，用以求解带载重量限制的车辆路径问题（Capacitated vehicle routing problem, CVRP）和双层车辆路径问题（2E-VRP）。CVRP是传统的单层车辆路径问题，而2E-VRP问题来源于当代城市物流中的双层运输系统。与CVRP直接配送至目标客户不同，在双层运输系统中，货物先到达配送中心，经过卫星平台中转后运送到目标客户。CVRP问题和2E-VRP问题都是属于NP-Hard难题，对算法的局部搜索能力和全局搜索能力都有很高的要求。大规模邻域搜索（Large neighborhood search, LNS）方法通过使用启发式规则搜索非常复杂的邻域，近年来在运输和调度问题上的应用表现突出，而人工蜂群算法（Artifical Bee Colony,ABC）是一种新兴的仿生群体智能算法，具有较强的全局寻优能了，我们将大规模邻域搜索方法应用于人工蜂群算法中，融合了两者的优点，使算法有更强的搜索能力。 由于CVRP问题是2E-VRP问题的基础，所以研究首先对CVRP问题进行了求解。我们设计了一种基于大规模邻域搜索的改进人工蜂群算法用于求解该问题，实验表明该算法对CVRP问题有较强的搜索性能，并且当客户规模比较大时，改进后ABC算法跟原ABC相比，算法更加稳定，性能表现更好。双层车辆路径问题是本文的研究重点，结合双层车辆路径问题的分层特点，本文同样设计了一种基于大规模邻域搜索的改进人工蜂群算法用于求解该问题。算法通过对第一层的路径和第二层的路径进行破坏与修复从而找到一个更优的邻域。实验的对比结果表明，当客户规模比较大时，我们的算法跟现有的算法比较非常有竞争力，另外改进后的ABC算法也优于原ABC算法。