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