基于模因演化算法的有限容量弧路径问题研究

摘要

有限容量弧路径问题（Capacitated Arc Routing Problem，CARP）是一个经典的带有约束条件的组合优化问题，在现实生活中有非常广泛的应用，如城市道路撒盐与洒水路径规划，垃圾回收线路规划，物流配送网络优化，输气、输电线路检修规划等等，因此也得到了许多研究者的关注。由于该问题是NP-hard问题，对于精确算法，要在可接受的时间内得到问题的最优解是非常困难的，并且计算成本非常之大。因此，本文旨在利用元启发式方法在给定时间内取得性能更优的次优解，为有限容量弧路径问题提供更加有效实用的解决方案。
　　首先，本文以目前求解CARP较为领先的算法—基于扩展邻域搜索的模因演化算法(MAENS)为基础算法，提出了三种改进方法，即：
　　(1)使用锦标赛选择算子筛选父代(MAENS-T);
　　(2)基于个体适应度的自适应搜索概率(MAENS-Pls);
　　(3)基于动态参数的随机排序算法(MAENS-Pf)。结合三种改进方法，形成了本文所提出的基于自适应扩展邻域搜索的模因演化算法(MAENS-C)。然后利用C语言编程实现算法，并采用研究领域内的通用测试集—Egl数据集中的三个实例对三种改进算法分别进行测试，证明了本文所设计算法的有效性。
　　其次，针对设计的各版本算法中包含的参数，利用统计赛车技术(RacingAlgorithm)与统计检验中的非参数检验方法对所有算法在全部的实验用例上(Egl数据集的八个实验用例)进行了参数优化，大大节省了参数优化的计算成本，最终得到了各算法的优化参数组合，为算法评价、应用奠定了基础。
　　再次，基于改进算法与其相应的优化参数组合，利用平均总成本，收敛可靠性，全局寻优能力，鲁棒稳定性，以及时间复杂度五个评价指标，在Egl数据集的八个实例上进行了定量与定性的算法评价。本文主要从相同演化代数和相同时间复杂度水平两个角度进行了比较总结，得出了MAENS-Pls以及三种改进方法的结合算法MAENS-C显著的优于基础算法MAENS，并且发现了13个针对CARP问题的新型最优解，进一步验证了本文提出的算法能有效地对局部搜索频率与深度进行双重优化，证明了算法的优异性能。
　　最后，将本文的理论研究成果应用于路径规划实例中，利用英国兰开夏郡Egl数据集的路径服务需求与地理信息，对兰开夏郡的路网进行了实例验证，为路径规划与车辆分配提供了优化的规划方案，并进行了优化解的可视化呈现，为交通领域内的路径规划提供了有效的解决方案。

目录

声明

致谢

摘要

表目录

图目录

1 引言

1．1 问题概述

1．2 研究现状

1．2．1 构造型启发式算法

1．2．2 元启发式算法

1．2．3 模因演化算法

1．2．4 算法评估

1．3 研究思路与论文结构

2 有限容量弧路径问题模型与算法

2．1 有限容量弧路径问题模型定义

2．2 模因演化算法框架

2．3 基于扩展邻域搜索的模因演化算法

2．3．1 处理约束条件

2．3．2 算法的搜索能力

2．3．3 基于扩展邻域搜索的模因演化算法

2．3．4 当前算法缺陷分析

3 基于自适应扩展邻域搜索的模因演化算法设计

3．1 基于锦标赛选择机制的父代选择算子

3．2 基于个体适应度的自适应局部搜索概率

3．2．1 递增式局部搜索概率

3．2．2 递减式局部搜索概率

3．3 基于动态参数的随机排序算法

3．4 算法实现与测试

3．5 结果与讨论

4 基于统计赛车技术的参数优化

4．1 参数优化方法论

4．2 MAENS-Pf的参数优化

4．2．1 参数设定

4．2．2 实验及结果分析

4．3 MAENS-Pls的参数优化

4．3．1 参数设定

4．3．2 实验及结果分析

4．4 MAENS-C的参数优化

4．4．1 参数设定

4．4．2 实验及结果分析

4．5 MAENS的参数优化

4．6 结果与讨论

5 算法评价与比较

5．1 实验分析

5．2 统计方法分析

5．3 结果与讨论

6 算法求解路径优化方案实例

6．1 英国兰开夏郡实例信息

6．2 路径优化方案可视化

6．3 分析与讨论

7 总结与展望

7．1 研究结论

7．2 研究创新点

7．3 研究局限性

7．4 未来展望

参考文献

附录

作者简历及攻读硕士学位期间取得的研究成果

学位论文数据集