论文部分内容阅读
自然界中存在着一类被称为NP完全的问题,由于其目标解的搜索涉及解空间的组合爆炸,因此,求解大规模的NP完全问题已经成为当今计算机科学、人工智能等领域的瓶颈任务之一。对于这类问题,分支定界、动态规划等传统的优化方法难以求其精确解,因此通常采用启发式算法,目标是在可接受的时间内找到问题尽可能好的解。车辆路径问题是一类NP完全问题。实际生活中的物流配送车辆调度、公共汽车路线制定、信件和报纸投递、航空和铁路时间表安排、废品收集、校车路线安排等问题都可抽象为车辆路径问题。因此,研究车辆路径问题的启发式算法有着重要的理论价值和现实意义。本文研究了启发式算法及其在车辆路径问题中的应用,结合不同元启发式算法搜索策略的优势提出混合启发式算法,解决带容量约束车辆路径问题、开放式车辆路径问题、多车型车辆路径问题和卸装一体车辆路径问题。本文工作得到了国家重点基础研究发展规划（973）项目基金（No.2006CB705500）的资助。本文取得的主要研究成果如下:（1）针对带容量约束的车辆路径问题,提出了一个混合迭代局部搜索算法HILS。该算法设计了一种迭代局部搜索和变邻域下降的结合方式,在变邻域搜索中使用多邻域算子扩大其搜索范围的同时,基于“粒邻域”的思想提出一种受限邻域,减少了不必要的搜索,提高了搜索效率;设计了一种基于cross-exchange算子的扰动策略。算法HILS结构简单、易实现,并且具有较好的灵活性。在通用的34个基准测试问题上进行实验,讨论了参数设置问题和算法各要素对算法性能的影响。实验结果表明,算法HILS能够有效求解带容量约束的车辆路径问题,性能和效率与表现最好的其它启发式算法相当。（2）针对开放式车辆路径问题,提出了一种扩展的混合迭代局部搜索算法cHILS。在利用变邻域下降搜索优化当前解时,通过优先接受路径数较少的解来满足开放式车辆路径问题的多目标优化的要求。在通用的16个基准测试问题上的实验结果表明,算法eHILS能够获得13个问题的已知最好解,并更新了其中3个问题的已知最好解。（3）针对多车型车辆路径问题,提出了一种变邻域搜索算法VNSFSM。该算法设计了实现抖动过程的邻域结构组合,并提出了一种新的车型调整策略。本文在通用的基准测试问题上的实验验证了算法的有效性,并给出问题G07至G12的正确解。结果表明,该算法能够获得大多数测试问题的已知最好解。与现有的启发式算法相比,该算法性能相当或更优,是当前求解多车型车辆路径问题表现最好的算法之一。（4）针对卸装一体车辆路径问题,基于蚁群优化和变邻域下降,提出了一个混合蚁群优化算法HACS。基于对卸装一体车辆路径问题可行解性质的分析,本文提山了一种可行解生成方式,即先生成问题的弱可行解,继而转换为强可行解。这种解生成方式的优点是构造方法简单,而且能有效避免使用过多的车辆。改进蚁群优化算法中解的构造方式,提出了一种基于插入的构造方法生成弱可行解。利用变邻域下降对蚁群中构造的质量最好的解进行优化,以加快算法的收敛。55个通用基准测试问题上的仿真实验结果表明,该算法能够获得52个基准测试问题的已知最好解,并更新了其中44个问题的已知最好解,从而验证了算法的有效性。此外,与最近提出的三个启发式算法相比,该算法的性能相当或更优。这表明算法HACS是当前求解卸装一体车辆路径问题的最好算法之一。