改进迭代局部搜索算法求解需求拆分的校车路径问题

《改进迭代局部搜索算法求解需求拆分的校车路径问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、单位代码１〇４７５学号１０４７５３］３０７５２分类号ＴＰ３化郑杂乂聲硕壬学位论文中－改进迭代局部搜索算法求解需求祝分的校车路径问题－产Ｌ－学科、专业：计算机应用技术研究方向：智能优化算法申请学位类别：理学硕±申请人：李双星指导教师：郑逢斌教授二〇－六年六月ImprovedIteratedLocalSearchAlgorithmsforSplitDemandSchoolBusRoutingProblemADissertationSubmittedtotheGraduateSchoolofHenanUnive

2、rsityinPartialFulfillmentoftheRequirementsfortheDegreeofMasterofScienceByLiShuangxingSupervisor:Prof.ZhengFengbinJune2016关于学位论文独创齊明和学术诚信承诺泰人向巧南大孚巧出頌壬学位申请，本人择重声明：所呈交的学位论文是本人在夺鄉的拍导下巧立完成的，对所巧定的巧题资新的見解。据我所知，除文中特莉加ａ说明、株注和致编的地方外，託文中不狂括其他人史经发表女誤写过的研完成《，也不包括乂化人为获得妊何教育一巧王作的巧事对、料研机巧的学化或化书

3、病使满过的材料，与我本研完所化的任何贡献均巳么论文中作了巧确的说巧并表示了谢素，在化本人新重承诺：巧至交的学化论文不每在舞奔作约行污，义责自资．Ａ雲学往申请人（学拉论文作者）签名：名？２０！／年备月义曰关于学位论支著作巧使用授极书衣人巧河南大学审棱扯难巧子巧去学位。作话学位谁文的作者，本人完全了解并巧，枯《巧南太学有关保留、巧巧怎、使巧学位论文的要求，邮河南大学有化向国《里书巧化构、數绝化集机婚和本校图书馆等提供学位论文（包泌紙廣文本和电子文本）ａ供公众检索、查闲，本人搜权河南欠学出于畫巧、展览学较学术发展和进巧学术交流等ａ的，可＆采

4、巧巧印、巧印、担巧和轉男等复制手段巧存、汇編学位论文（包括化巧文本和电子文本）。（涉义保密内容的学位络义在解密后连用本巧杖书）学位巧巧者？呈（学位论文巧者）症名２０１＾卑食月文日ｉ学位论文指导教師签名；２０１＾年《月３ｇ摘要随着我国经济社会的发展，近年来越来越多的地区和学校开始为中小学生提供校车服务。然而与发达国家相比，校车服务在我国起步较晚，校车的运营方式及路线规划手段等都在探索之中。校车路线规划是校车运营管理的关键环节，合理地安排校车路线，既能节约校车服务成本，又能提高校车服务质量。与校车路线规划密切相关的学术问题是校车路径问题

5、(SBRP)，该问题是组合优化领域的NP-hard问题。经典的SBRP问题中同一站点乘车的学生必须由一辆校车服务，在一定程度上影响了校车的利用率。在我国人口密度大，居住相对集中。学生的乘车站点一般设置在居民区附近，导致在一个站点乘车的学生人数较多，甚至可能超过校车最大载客量，使得经典的SBRP无法直接应用于该情形下的路径规划。已有的关于需求拆分的车辆路径问题研究表明，允许需求拆分能够进一步减低服务成本。因此，本文将SBRP扩展为站点乘车需求拆分的校车路径问题(SDSBRP)，优化目标包括最小化校车数量和最小化校车的行驶距离两个目标，并设计改进的迭代局部搜索算法进行求解。本

6、文所做的工作主要包括以下几个方面：（1）对需求拆分车辆路径问题及单校校车路径问题进行了系统的梳理分析，将经典的SBRP扩展为需求拆分的校车路径问题，在此基础上设计了求解SDSBRP的启发式算法所需要的邻域算子。（2）设计了求解SDSBRP问题的改进迭代局部搜索算法针对已有关于SDSBRP研究偏少，已有的启发式算法难以获取高质量解的问题，设计了基于迭代局部搜索算法(ILS)的元启发式求解算法。ILS算法的关键在于局部搜索和扰动，合理的局部搜索和扰动策略能够提高算法的性能。局部搜索易于陷入局部最优，使问题偏离最优解。本文考虑到模拟退火算法具有较强的局部搜索能力，在局部搜索算法

7、过程中邻域解的目标值评估时以最小化校车数量为首要目标，最小化校车行驶距离为第二目标，在进行第二目标的判断时采用了模拟退火算法思想，允许接受一部分使目标值变差的解。本文采用了一种基于破坏重建思想的扰动策略，从当前解中删除一部分路径，然后进行重建，增加ILS算法跳出局部最优解的概率。（3）用本文所提出的算法具有广泛的适用性，能够求解站点乘车需求拆分和不拆I分两种情形下的校车路径问题。针对设计的算法进行了仿真实验与分析，验证了算法的有效性。关键词：校车路径问题；迭代局部搜索算法；需求拆分；元启发式算法IIAbstractWithth