基于洪泛算法的单线校车路径规划问题研究

摘要

校车是专门接送幼儿园、小学和中学学生上下学的具有特殊用途的车辆。作为教育资源的辅助设施，校车在保障学生上学和放学路上的安全问题上具有非常重要的作用。随着生活水平的提高，很多家庭拥有私家车，因为担心孩子的安全问题，家长就亲自开车接送学生，这样不仅耽误了自己的上班时间，也增加了交通的负载量，间接地也增加了很多交通安全隐患。校车的使用既能保障学生的出行安全，又可以减少学校附近的交通流量。合理的规划校车路线，不仅能进行有效的资源配置，降低校车的运营成本，还能缩短车辆行程或者是学生的乘车时间。本文的研究工作主要包括以下几个方面:
　　(1)参考了大量的相关文献，并进行整理归纳，从车辆路径规划、洪泛算法和剪枝等方面进行详细阐述。
　　(2)综合校车路径规划的实际问题，选取了几个主要的影响因素:道路自身的属性、道路拥堵情况和交叉路口等，以车辆行驶时间最短为目标，建立了单线校车路径规划模型，并用洪泛算法求解模型。针对洪泛算法求解速度较慢问题，设计了剪枝规则，有效地提高了求解速度。算法仿真结果表明，该算法可以求得最优解，并在求解效率上优于传统的精确算法;虽然求解效率不如启发式算法，但是每次都可以求得最优解，证明了算法的有效性。
　　(3)以大连嘉汇阳光小学为实例，对学校单线校车的交通网络进行了详细的考察，包括节点的选取、道路长度、路况系数和路质系数、交叉路口等，使用文中的校车路径规划模型，以车辆行驶时间最短为目标，得出优化结果。实验表明，原来单线校车的行驶时间为44.08分钟，经过优化后的时间为41.67分钟，减少了近2.4分钟。车辆行驶时间缩短，降低了危险程度，有利于保障学生的安全。
　　最后，对研究工作进行了总结，讨论了论文的主要研究成果和创新之处，并对未来的研究工作进行了展望。

目录

声明

摘要

1 绪论

1．1 研究背景

1．2 研究的目的和意义

1．3 国内外相关研究现状

1．3．1 国外研究现状

1．3．2 国内研究现状

1．4 论文结构

2 基本理论

2．1 车辆路径问题

2．1．1 车辆路径问题的定义

2．1．2 车辆路径问题分类

2．1．3 车辆路径问题算法综述

2．2 洪泛算法

2．2．1 传统洪泛模型

2．2．2 洪泛算法的优缺点

2．3 剪枝算法

2．4 本章小结

3 单线校车路径问题的模型建立和算法设计

3．1 单线校车路径问题的描述

3．2 单线校车路径规划问题影响因素分析

3．2．1 影响因素

3．2．2 相关因素关系分析

3．3 模型的设计

3．3．1 假设条件

3．3．2 参数的设定

3．3．3 步骤

3．4 算法设计

3．4．1 算法流程

3．4．2 算法解析

3．5 本章小结

4 案例应用——以大连嘉汇阳光小学为例

4．1 案例描述

4．2 试验结果及分析

4．2．1 实验结果

4．2．2 回溯范围变数w分析

4．3 本章小结

5 总结

5．1 主要结论及创新点

5．2 研究局限与展望

参考文献

附录

攻读硕士学位期间发表学术论文情况

致谢