详情

原文传递改进蚁群算法求解多目标校车路径优化问题

论文题名：	改进蚁群算法求解多目标校车路径优化问题
关键词：	校车路径问题;调度问题;蚁群算法;Python语言;数学模型
摘要：	随我国社会经济的发展，为中小学学生提供校车服务成为教育主管部门和学校面临的新问题。校车路径规划是校车运营管理中的一个重要环节，但路径规划涉及学校、学生、车队和交通网络，是一项难度极高的任务。与校车路径规划密切相关的校车路径问题(SBRP)是在满足学生交通服务各种约束条件的前提下，寻求最优的校车路径方案，将学生从乘车站点运送到学校，达到一定的服务质量目标和校车运营效率目标。　　针对一个区域内多个学校校车路径规划问题，通常将SBRP分解单校SBRP和校车调度问题(SBSP)分别进行求解。本文在建立单校SBRP和SBSP数学模型的基础上，分别改进蚁群系统算法（ACS）和改进最大最小蚂蚁算法（MMAS）进行求解，使用基准案例数据集测试算法的性能。主要完成了以下工作：　　(1)建立了单校SBRP和SBSP数学模型。　　由于SBRP属于车辆路径问题（VRP）的范畴，本文针对单校 SBRP建立了开放VRP整型线性规划数学模型；SBSP建立了混合整形规划数学模型。　　(2)针对单校SBRP和SBSP分别设计了改进ACS算法和改进MMAS算法。　　根据单校SBRP的特性，在校车容量和学生最大乘车时间约束下，将减少路径数量作为第一目标，缩减路径总长度为第二目标。按照制定的优化目标，着重探讨了使用改进 ACS算法进行校车路径构造方法、与优化目标相关的信息素更新策略、局部搜索的路径改进等内容；本文将单校SBRP生成的每条路径转化为虚拟站点，将SBSP转换为有时间窗的车辆路径问题（VRPTW），同时设定了以减少车辆数为主要目标同时兼顾降低车辆的总行车里程为优化目标。依据优化目标，在MMAS和局部搜索的策略的基础上，设计了针对SBSP的改进MMAS。　　(3)使用基准案例数据集，测试和分析了ACS算法和MMAS算法的性能。　　使用改进ACS求解SBRP的结果与Cplex精确算法求解结果对比表明：对于Cplex能获得最优路径数量的案例，改进ACS算法也能获得相同的路径数量,而针对Cplex仅能获得可行解的大规模案例，改进 ACS算法在求解路径数量和计算效率方面具有明显的优势；使用改进MMAS求解SBSP的结果与文献41报道的结果进行对比表明：对于Park Heuristic能获得最优校车数量的案例，改进MMAS算法也能获得相同的校车数量；而针对Park Heuristic不能获得最优校车数量的案例，改进MMAS算法在求解校车数量具有优势。　　(4)校车路径优化案例研究。　　将改进ACS算法、改进MMAS算法，在ArcGIS的Geoprossing框架下，通过Python语言，进行算法与GIS平台的集成。使用河南省巩义市初级中学数据，进行校车路径优化案例的研究。　　本文的主要研究结论如下：　　(1)本研究对于SBRP建立了开放VRP整型线性规划数学模型进行求解，通过实际案例的研究，表明该模型在实际的应用中有很强的实用性，符合现实情况；对于SBSP建立了混合整形规划数学模型求解，通过实验表明，这个模型能够很好的表达SBSP。　　（2）使用改进ACS算法求解单校SBRP是可行的，在算法的设计过程中，根据多目标组合优化的特点，使用两阶段结构，同时加入逐点插入和两点交换等局部搜索策略，求解结果与Cplex使用精确算法求解的结果比较具有一定的优势，表明了本算法具有更强的性能，更贴近实际问题；　　（3）采用改进MMAS算法求解SBSP是有效的，在算法的设计过程中，使用最大最小信息素策略，与优化目标相关的信息素更新策略，同时引入逐点插入和两点交换等局部搜索策略，实验结果与文献41报道的结果比较具有一定的优势，表明本算法在求解多目标组合优化问题上具有更加强劲的性能，具有更好的实际应用价值。　　（4）在 ArcGIS的 Geoprocessing框架下，使用 Python脚本语言，实现了算法与GIS平台的集成，很好的发挥了GIS平台在空间数据管理和空间可视化方面的强大功能，同时也为学校制定校车管理方案，提供了理论和现实的依据。
作者：	牛宁
专业：	地理学与地理信息系统
导师：	孔云峰
授予学位：	硕士
授予学位单位：	河南大学
学位年度：	2015
正文语种：	中文