车辆路径问题是物流配送领域的重要问题,蚁群算法是一种新的元启发算法。本文研究的就是把改造后的蚁群算法用于特殊的车辆路径问题——有时间窗和在前约束车辆路径问题的求解。 本文对蚁群算法进行了改进。通过深入分析蚁群优化机制,针对时间窗车辆路径问题,提出了基于单位节约值和时间紧迫性的可见度以及基于K优解的信息素浓度更新规则,并综合运用了推广的2-交换法进行邻域搜索。对基准问题的仿真实验表明,能在3个循环内得到优良结果。 本文还对在前约束提出明确定义,分析了含有在前约束的车辆路径问题研究的实际价值。在给定了在前约束的数学表示法的基础上,根据约束关系的不同,对在前约束进行了系统的分类。 本文实现了在前约束问题的算法。包括剖析在前约束关系、确定不可分集合,将问题初始化为相对普通的问题。实现时,充分发挥禁忌表的禁忌作用,变在前约束为禁忌约束并引入信息素突变规则来实现禁忌点解除禁忌后的搜索道路畅通性。通过在基准问题Solomon’s VRPTW C101.25基础上加入不同的在前约束构造问题后,进行仿真实验,结果十分理想。 本文探讨了特殊邻域搜索策略。在在前约束的限制下,给出了路段保护边交换法的思想,描述了路径保护3-交换法词典搜索的实现原理及详细过程,实验验证了与蚁群算法相结合的可行性,对比表明能使算法在较少的循环次数下收敛。