CN114529057B 一种基于大规模领域搜索的多场站校车路径求解方法 （河南大学）

一种基于大规模领域搜索的多场站校车路本发明公开一种基于大规模领域搜索的多校车路径安排方案。首先建立MDSBRP的数学模2的乘车站点、可用车型信息和最大乘车时间约束条件,使用广义插入法构造多条到达该学步骤103:针对所有未插入到封闭环路上的站点，找到步骤104:随机选择一个不在环路中的站点，评估该站点Lnr=0,vieD,KEM,确保从场站i出发或者回到场站i时车辆k上学生数量Lik为0；s.t.zjevxyh一zjeviux=0,viEP,KEM,其中V表示所有站点；xijx表示车辆k是否保证车辆k经过站点i后的学生人数Lik大于等于站点i上3步骤302：对场站附近的站点采用destroy场站操作算2.根据权利要求1所述的一种基于大规模领域搜索的多场站校车路径求解方法，其特3.根据权利要求2所述的一种基于大规模领域搜索的多场站校车路径求解方法，其特步骤2011：使用创建领域节点列表方法创建节点j、即站点估方法评估将节点j插入到节点k的移动是否满足约束，使用CheckMove方法评估此次移动产生的新解是否能够接受，按照启发规则确定此次移动对象M是否比目前的最好的移动对4.根据权利要求1所述的一种基于大规模领域搜索的多场站校车路径求解方法，其特采用randomdestroy算子随机从当前解中移除一定比例的站点，采用worstdestroy45将学生从乘车站点送到学校(或从学校送回乘车站点)，并达到特定目标的组合优化问题。[0003]依据校车场站的数量，可以将校车分为单场站校车路径问题(Singledepotschoolbusroutingproblem,SDSBRP)和多场站校车路径问题(Multipledepotschool的多场站校车路径求解方法，能够寻找多场站运营模式下总成本最小的校车路径安排方6学校的乘车站点、可用车型信息和最大乘车时间约束条件,使用广义插入法构造多条到达7[0038]步骤2012：获取领域节点列表中的节点k，创建记录此次移动的对象M，使用Evaluate评估方法评估将节点j插入到节点k的移动是否满足约束，使用CheckMove方法评估此次移动产生的新解是否能够接受，按照启发规则确定此次移动对象M是否比目前的最[0046]采用randomdestroy算子随机从当前解中移除一定比例的站点，采用worst8[0051]本发明针对站点和场站分别采用了不同的算子进行搜索：针对站点采用了swap[0052]图1为本发明实施例一种基于大规模领域搜索的多场站校车路径求解方法的基本9[0071]满足对场站的约束条件Lik＝0,vieD,k∈M，确保从场站i出发或者回到场站i时[0073]满足学生站点和学校站点之间的关系Tik+sti+tis(i)≤Ts(i)k，其量不能超过校车容量。车辆经过站点i后的累积学生人数Lik大于等于站点i的学生人数qi，[0075]满足对车辆到达站点的时间约束条件使用Evaluate评估方法评估将节点j插入到节点k的移动是否满足约束，使用CheckMove方法评估此次移动产生的新解是否能够接受，按照启发规则确定此次移动对象M是否比目前[0091]使用两种destroy算子对解进行破坏，采用randomdestroy算子随机从当前解中移除一定比例的站点，采用worstdestroy算子从当前解中移除引起目标函数增幅较大的[0093]以最小化校车数量和最小化运营里程为优化目标，其中校车数量为第一优化目+[0095]测试案例基于SBRP领域首个公开的基准测试案例集，包括RSRB和CSCB两类案例66情形相比最好解的提升程度。行的运营里程最好解和平均解与单场站的情形相比最好解的提[0107]使用LNS算法求解RSRB类测试案例，对LNS在MDSBRP和SDSB[0113]通过CSCB和RSRB对比分析LN