详情

原文传递大规模混载校车路径问题优化算法研究

论文题名：	大规模混载校车路径问题优化算法研究
关键词：	混载校车;路径问题;数学模型;元启发求解算法
摘要：	为中小学校学生提供校车服务是县市级地方政府的一项重要职能，也是我国当前义务教育发展中面临的新问题。校车运营管理中，合理规划校车路径能减少所需的校车数量和总体行驶里程，从而节约运营成本。针对多个学校进行校车路径规划是一项复杂度极高的任务，与其关系密切的校车路径问题(SBRP)研究虽然取得了明显的进展，但与现实中实际需求相比，仍有诸多难题尚未解决。　　SBRP是在保证满足校车服务各种约束条件的前提下，合理地安排校车路径方案，达到特定目标的组合优化问题，它属于车辆路径问题(VRP)的一个分支。在针对一个区域规划校车路径时，若允许校车混载不同学校的学生，能够显著地减少所需校车数量和行驶里程。本文针对求解大规模混载SBRP这一难题，重点研究相关的数学模型和元启发求解算法。　　本文研究思路是:①分析混载SBRP的基本构成要素，将校车服务质量和公平性指标作为模型约束条件，将效率作为优化目标，提出一般化的混载SBRP数学模型。②基于SBRP模型进行算法设计。首先，设计适合多种应用场景的校车路径问题算法框架，包括问题数据结构、常用函数和基本算法库。其次，基于该框架设计SBRP求解算法。为提升算法求解质量和计算效率，引入时空邻域、搜索策略等进行算法改进。③使用案例数据对算法进行性能测试，分析各种策略及参数设置对算法的影响，并基于优化结果分析对算法进行优化。④最后将算法与GIS进行集成，在GIS中管理数据、调用算法、输出结果。　　本文的主要工作和结论如下: 　　(1)完成了混载SBRP算法框架设计。算法框架提供通用的数据结构、常用函数、邻域算子和常见启发式算法，也包含模拟退火、变邻域搜索和大规模邻域搜索等多种元启发算法。该框架支持邻域算子的选择和组合，能调整算法执行过程中解的接受策略、邻域搜索策略和算法参数等，具有通用性和可扩展性。　　(2)完成了两阶段混载SBRP算法设计。以最小化校车数量为主要目标的记录更新法(RRT)元启发算法，引入求解带时间窗的装卸一体化问题(PDPTW)时使用的单个点对路径间移动(SPI)、两个点对路径间交换(SBR)和单个点对路径内调整(WRI)三个邻域算子优化路径数，减少使用的校车数量。以优化总运营里程为主要目标的大规模邻域搜索算法(LNS)，通过站点对的移除和再插入对现有解进一步改进，缩减了总的运营里程。在邻域搜索过程中引入时空距离概念，基于站点间的时空相关度减小了邻域搜索的规模，提高了算法的执行效率。利用国际上的标准案例对混载SBRP算法进行测试，结果表明基于PDPTW邻域算子的RRT算法在求解质量上明显优于国际上的现有算法。在循环30次的情况下，站点随机分布的案例(RSRB)车辆数平均减少了10.14％;站点聚集分布的案例(CSCB)车辆数平均减少10.61％。RRT算法在减少车辆数的同时，使两类案例的平均运营里程分别下降了7.34％和6.30％。继续执行LNS算法之后，运营里程下降程度分别达到10.84％和9.91％。时空相关的邻域搜索算法能在保持解的质量基本不降低的情况下，算法的平均执行时间下降50％左右。　　(3)完成了大规模混载SBRP算法策略和参数设置探讨。针对算法中不同算子组合、参数设置的实验表明:①SPI算子能有效减少路径数量，WRI和SBR本身不能缩减路径数量，但是所做的站点调整使得SPI缩减路径数的机会增加。整体上三个算子按照SPI、WRI和SBR的顺序执行效果最好。②邻域搜索过程中，优先选择短路径上的站点对优于随机选择策略。③解的接收策略上最优接受和最先接受各有优劣，在大规模案例中解的接受策略规律性并不明显。④增加循环次数有进一步减少车辆数和运营里程的机会，表明在延长算法执行时间的情况下，可能会得到更好的解。　　(4)完成了一个案例实验。收集巩义市初级中学的学校、学生和道路网络数据，使用ArcGIS10进行数据管理、道路网络分析和混载SBRP建模，调用SBRP算法进行求解。案例研究表明:本文算法在求解质量方面优于ArcGIS10网络分析模块的车辆路径问题算法。　　本文在多个方面拓展了大规模混载SBRP算法设计:首次验证了基于PDPTW算子进行混载SBRP算法设计的可行性;与现有算法相比，本算法显著地提高了求解的质量（所需车辆数和运营里程）;引入时空相关的邻域搜索提高了算法的求解效率;分析了混载SBRP算法设计策略，包括算子组合、目标设置、搜索策略、解接受策略等，为进一步的算法设计奠定了基础。
作者：	党兰学
专业：	地图学与地理信息系统
导师：	孔云峰
授予学位：	博士
授予学位单位：	河南大学
学位年度：	2014
正文语种：	中文