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

《大规模混载校车路径问题优化算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、OptimizationAlgorithmsforLargeScaleMixedLoadSchoolBusRoutingProblemADissertationSubmittedtotheGraduateSchoolofHenanUniversityinPartialFulfillmentoftheRequirementsfortheDegreeofDoctorofPhilosophyinScienceByDANGLanxueSupervisor：Prof．KONGYunfengMarch2014关于学位论文独创声明和学术诚信承诺fIlllllrllIJIlllllrllllllll

2、lllllllllrlllllJJJlllfY2542416本人向河南大学提出博士学位申请。本人郑重声明：所呈交的学位论文是本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰写过的研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书而使用过的材料。与我一同工作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。在此本人郑重承诺：所呈交的学位论文不存在舞弊作伪行为，文责自负。学位申请人(学位论文作者)签名：20，红且／，∥日关于学位论文著作权使用授权书本人经河南大学审核批准授予

3、博士学位。作为学位论文的作者，本人完全了解并同意河南大学有关保留、使用学位论文的要求，即河南大学有权向国家图书馆、科研信息机构、数据收集机构和本校图书馆等提供学位论文(纸质文本和电子文本)以供公众检索、查阅。本人授权河南大学出于宣扬、展览学校学术发展和进行学术交流等目的，可以采取影印、缩印、扫描和拷贝等复制手段保存、汇编学位论文(纸质文本和电子文本)。(涉及保密内容的学位论文在解密后学位获得者(学位论文作者)201学位论文指导教师签名：2。，坼S月l臼摘要为中小学校学生提供校车服务是县市级地方政府的一项重要职能，也是我国当前义务教育发展中面临的新问题。校车运营管理中，合理规划校车路径

4、能减少所需的校车数量和总体行驶里程，从而节约运营成本。针对多个学校进行校车路径规划是一项复杂度极高的任务，与其关系密切的校车路径问题(SBRP)研究虽然取得了明显的进展，但与现实中实际需求相比，仍有诸多难题尚未解决。SBRP是在保证满足校车服务各种约束条件的前提下，合理地安排校车路径方案，达到特定目标的组合优化问题，它属于车辆路径问题(VRP)的一个分支。在针对一个区域规划校车路径时，若允许校车混载不同学校的学生，能够显著地减少所需校车数量和行驶里程。本文针对求解大规模混载SBRP这一难题，重点研究相关的数学模型和元启发求解算法。本文研究思路是：①分析混载SBRP的基本构成要素，将校

5、车服务质量和公平性指标作为模型约束条件，将效率作为优化目标，提出一般化的混载SBRP数学模型。②基于SBRP模型进行算法设计。首先，设计适合多种应用场景的校车路径问题算法框架，包括问题数据结构、常用函数和基本算法库。其次，基于该框架设计SBRP求解算法。为提升算法求解质量和计算效率，引入时空邻域、搜索策略等进行算法改进。③使用案例数据对算法进行性能测试，分析各种策略及参数设置对算法的影响，并基于优化结果分析对算法进行优化。④最后将算法与GIS进行集成，在GIS中管理数据、调用算法、输出结果。本文的主要工作和结论如下：(1)完成了混载SBRP算法框架设计。算法框架提供通用的数据结构、常

6、用函数、邻域算子和常见启发式算法，也包含模拟退火、变邻域搜索和大规模邻域搜索等多种元启发算法。该框架支持邻域算子的选择和组合，能调整算法执行过程中解的接受策略、邻域搜索策略和算法参数等，具有通用性和可扩展性。(2)完成了两阶段混载SBRP算法设计。以最小化校车数量为主要目标的记录更新法(RRT)元启发算法，引入求解带时间窗的装卸一体化问题(PDPTW)时使用的单个点对路径间移动(SPI)、两个点对路径间交换(SBR)和单个点对路径内调整(WRI)--个邻域算子优化路径数，减少使用的校车数量。以优化总运营里程为主要目标的大规模邻域搜索算法(LNS)，通过站点对的移除和再插入对现有解进一

7、步改进，缩减了总的运营里程。在邻域搜索过程中引入时空距离概念，基于站点间的时空相关度减小了邻域搜索的规模，提高了算法的执行效率。利用国际上的标准案例对混载SBRP算法进行测试，结果表明基于PDPTW邻域算子的RRT算法在求解质量上明显优于国际上的现有算法。在循环30次的情况下，站点随机分布的案例(RSRB)车辆数平均减少了10．14％；站点聚集分布的案ff!f(CSCB)车辆数平均减少10．61％。RRT算法在减少车辆数的同时，使两类案例的平均运营里程分别