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

发布时间：2018-01-10 22:15

本文关键词：大规模混载校车路径问题优化算法研究　出处：《河南大学》2014年博士论文　论文类型：学位论文

【摘要】：为中小学校学生提供校车服务是县市级地方政府的一项重要职能，也是我国当前义务教育发展中面临的新问题。校车运营管理中，合理规划校车路径能减少所需的校车数量和总体行驶里程，从而节约运营成本。针对多个学校进行校车路径规划是一项复杂度极高的任务，与其关系密切的校车路径问题(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算法设计策略，包括算子组合、目标设置、搜索策略、解接受策略等，为进一步的算法设计奠定了基础。
[Abstract]:......
【学位授予单位】：河南大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：P208;U492.22

【参考文献】