0 引言

目前，我国农村交通发展总体上比较落后，校车服务在农村地区并不完善．与城市校车站点的短距离线路长度、高密度站点覆盖模式不同的是，农村校车站点多呈现为纵向延伸、分散布点的需求模式，农村校车路径规划有待改善．校车路径问题（School Bus Routing Problem，SBRP）是在满足校车容量、时间窗等约束条件下，合理地规划校车线路将学生从乘车站点送到学校（或从学校返回乘车站点），并达到特定目标的组合优化问题．自多校SBRP问题的提出者Newton等^[1]基于启发式算法的生成校车路线和时刻表，使用二次规划的方法规划校车路网以来，众多学者一直在探索相关的数学模型、优化算法及其应用．为解决校车路径问题，Jaradat等^[2]以校车容量、最大乘车时间和学校时间窗为目标，采用智能水滴算法（Intelligent Water Drops，IWD）优化求解．Calvete等^[3]提出一种局部分配局部搜索算法，求解带有停车位选择的校车路径问题．高巍等^[4]侧重于校车的最少运营数问题，对校车问题进行定义和描述，将问题分为极限情况和一般情况，针对不同情况设计了SBLS（School Bus Limit Situation）算法和SBGS（School Bus General Situation）算法．关于混载SBRP，Hargroves等^[5]指明了研究方向，但未构建相关模型与算法进行求解．Hou等^[6]构建了一种混合迭代局部搜索（ILS）元启发式算法，可用于具有多种规划场景的 SBRP，包括同质或异构车队、单载或混载运行模式．Park等^[7]提出一种将多校SBRP问题分解为单校SBRP问题，使用扫描算法优化单校路线，再合并优化的单校线路结果的新型混载改进算法．Semba等^[8]运用模拟退火（Simulated Annealing，SA）、禁忌搜索（Tabu Search，TS）和蚁群优化（Ant Colony Optimization，ACO）三种元启发式算法求解多校SBRP问题的模型，对三种算法性能进行了实证比较．

上述文献对多校SBRP进行了研究，但对农村地区校车服务过于重视校车运营方成本，而服务质量问题未能深度探讨．本文针对学生出行成本，即学生对校车服务的感知度，建立一种基于学生出行成本和服务协调的不混载校车路网布局模型，在保证校车服务质量的条件下，优化校车路径减少校车运营里程从而降低校方运营成本; 混载情景下，则是从校车购置和运营成本两方面出发，建立混载优化模型．引入不同搜索算子的模拟退火算法（SA）和遗传算法（Genetic Algorithm，GA）在国际基准案例上的测试结果表明，SA算法具有良好的适用性，两种情景下构建的模型能够提高农村地区校车服务质量、降低校方运营成本．

1 问题描述与数据介绍

1.1 问题描述

某学区内有若干学校，每所学校拥有一辆或多辆校车，学生只允许在本校站点上下车．学校、乘车站点、场站的数量与坐标已知，每个站点学生数量及该站点学生的目标学校已知，校车数量和校车容量已知．每个站点仅能由一辆校车进行服务且至少一名学生候车．在不混载情景下，同一校车上不能同时乘坐去往不同学校的学生，需要考虑校车到站点的上下车服务时间，以及所有学生在学校规定的时间窗内到达，保证学生出行成本最小，降低校方运营成本; 在混载情景下，每辆校车为不同的学校提供服务，同样需要考虑上下车服务时间，设置学生的最大乘车时间．

1.2 数据介绍

Park等^[7]于2012年提出了校车路网布局问题的通用数据测试集，并将校车站点与学校布局的共性总结为RSRB与CSCB两种类型，其中“R”与“C”分别意为随机和聚集，“S”与“B”分别表示学校与站点，即RSRB的学校与站点坐标的分布是随机的，而CSCB将去往不同学校的学生站点进行站点布置时，形成数个集群中心，且不同的学校也集中在同一区域中．

山东省日照市五莲县位于山东半岛中南部，总面积为1 497 km²，常住人口49.98 万．本文选取五莲县城区进行校车路网的布局实例研究．研究区道路众多，但部分道路过窄、路面质量不佳．研究区实例学校6 所，在读学生共4 522人，其中乘坐校车的学生795 名．由图1可知，实例学区属于学校分散站点分散型案例，即RSRB．

2 建立数学模型

2.1 参数和决策变量

校车路网布局问题中，主要从场站、学生、站点、校车等4个方面对模型中使用到的参数与变量进行符号定义．由于场站设定在某个学区内，若校车全部停放在一个已知场站，场站作为一个站点，用0表示; 若校车停放在不同的场站，则可以设置一个场站的集合D．通常使用P⁺与P^-分别表示学生、学校站点的集合，且P指学生与学校站点的并集，表示为P=P⁺∪P^-．场站、学生的站点、学校的站点的集合为V，以单一场站0为例，集合可表示为V=P∪{0}．每个站点对应需要到达的学校s（i）已知．当服务于不同学校时，学校有自身的时间窗，对最早到校时间e_i和最晚到校时间l_i做出描述．在校车运营中使用的校车k的集合为K，即k∈K．

考虑到校车路网布局模型构建的抽象性，将校车从站点i至站点j行驶路径表示为c_ij，每个站点的候车人数i≥1．每个站点的学生人数因实例的不同而不同，因此站点i的学生人数为n_i，根据站点i性质的不同，分别表示搭乘校车或者从校车上下车的学生人数．学生上下车需要消耗一定的服务时间，t_i为校车在站点i的停滞服务时间，根据学生数量的变化而变化．另外，在不同校车路网布局模型建设中，由于优化目标的不同，所选用的决策变量也存在差异，一般模型通常选取的决策变量如x_ijk，T_ik，L_ik等．

综上，将校车路网布局问题模型中常用的参数与决策变量整理，如表1所示．

2.2 构建模型

2.2.1 不混载情景下线性规划数学模型

模型构建时，选取从校方和学生（乘客）两个角度出发，以校方运营成本和学生出行成本最低为优化目标．校方只考虑车辆运营中的变动成本和因购置校车投入的固定成本．车辆运营中的变动成本为校车的行驶成本和校车到达站点时学生上下车产生的停滞服务成本之和; 由于不考虑校车的维护、场站的建设等投入，固定成本变化的主导因素为校车的数量，因此校方运营成本F₁可表达为

$F_1={\alpha }_1\sum _{i\in P^{+}i\in P^{-}}{x}_{0jk}+{\alpha }_2\sum _{i\in V}\sum _{j\in V}\sum _{k\in K}{x}_{ijk}\cdot c_{ij}+$

校车k到达站点i后的服务时间t_i与该站点的n_i和站点i的服务性质有关，其中t_i依据已开发的回归模型进行定义^[9]．

为保证n_i符合定义域，候车站点的n_i表示上车人数，$\mathrm{}{n}_i^{\mathrm{\text{'}}}$为正数，此时学生上车停滞时间t_i=19+2.6·$n_i^{\mathrm{\text{'}}}$; 学校站点的n_i表示下车人数，$\mathrm{}{n}_i^{\mathrm{\text{'}}}$ 为负数，此时学生下车停滞时间t_i=29-1.9·$n_i^{\mathrm{\text{'}}}$．即:

从作为乘客的学生角度分析时，考虑到学生对校车服务水平的满意程度，而服务水平受各种因素影响难以确定，文中从校车与公交的相似性中获得启发，将广义出行成本概念引入校车路网布局^[10-11]，选取时间与票价作为评价指标，将学生对服务的满意程度简化为对时间和票价的感知反应．

出行时间包括学生在站点候车时的等待时间以及学生乘坐校车至学校的车内时间．为达到简化模型的目的，把车内时间近似为校车行驶总里程与速度之比，校车的服务时间等于校车到达站点后的停滞时间．对于学生而言，等待时间和车内时间二者在时间消耗上所产生的时间价值是不同的，因此对乘车时间和等车时间的处理上增加时间权重，等待时间权重为车内时间权重的3倍．综上，为使学生出行成本最低，考虑乘客车内时间成本、等车时间成本和票价成本，则学生出行成本F₂可表达为

式中:z为学生的单位时间价值; m为当地人均小时收入; η为不同出行目的价值比值，取0.15; M为单位学生的票价，为定值; μ₁，μ₂分别为出行时间成本和票价成本权重系数^[12]．

函数约束则从站点、时间窗、容量、场站4个角度进行．

1）站点约束:每个站点仅由1辆校车进行服务，保证当校车k驶入站点完成服务后驶离站点，且校车k对学生进行服务时考虑对学生的接送顺序，保证校车k在运营中先服务站点，再驶向站点相对应的学校站点，最后是对决策变量x_ijk的约束．

$\sum _{k\in K}\sum _{i\in V}{x}_{ijk}=1,{\forall }_j\in P^{+}$

$\sum _{j\in V}{x}_{ijk}-\sum _{j\in V}{x}_{jik}=0,i\in P,$

$T_{ik}+t_i+T_{is\left(i\right)}⩽T_{s\left(i\right)k},i\in P^{+},s\left(i\right)\in P^{-},k\in K,$

2）时间窗约束:在校车k服务范围内，保证所有校车将学生在学校规定的最早到达时间e_i与最晚到达时间l_i内送达．

3）容量约束:确保当校车k行至服务站点完成服务后，车上的学生总人数大于等于站点的上车人数且小于等于校车规定容量Q．

4）场站约束:保证校车k从场站0出发完成学生接送服务后回到原场站，形成一个闭合的回路．

综上所述，不混载情景下校车路径规划数学模型为

$minF={\alpha }_1\sum _{i\in P^{+}}\sum _{i\in P^{-}}{x}_{0jk}+\left({\alpha }_2+z{\mu }_1/v\right)\sum _{i\in V}\sum _{j\in V}\sum _{k\in K}{x}_{ijk}\cdot c_{ij}+$

$\left({\alpha }_3+3z{\mu }_1\right)\left(\sum _{i\in P^{+}}\left|n_i\right|\cdot t_i-\sum _{i\in P^{-}}\left|n_i\right|\cdot t_i\right)+$

2.2.2 混载情景下线性规划数学模型

混载情景下校车路网布局优化模型受约束的复杂性限制，模型构建时引入的出行成本最小优化目标无法实现，因此以校车购置成本与运营花费为优化目标进行构建．其中，校车购置成本与校车投入量有关，校车数量与校车的单位价格α₁相乘即为购置成本，而校方运营成本受总运营行驶里程影响，总里程与单位里程行驶成本α₂之积即为校方运营成本:

函数约束则从站点、时间、容量、场站4个角度进行．

1）站点约束:保证的是每个站点有且仅有一辆校车服务，且当校车k驶入站点结束服务后离开．由于校车在进行服务的过程中，校车k可以同时接送去往不同学校的学生，需要对校车运营中一些动态变化进行约束，确保当校车k服务站点i后需要经过站点i对应的学校，最后是对决策变量x_ijk，y_ik的约束．

$\sum _{k\in K}{y}_{ik}=1,i\in P^{+}$

$\sum _{j\in V}{x}_{ijk}-\sum _{j\in V}{x}_{jik}=0,i\in P,k\in K,$

$\sum _{j\in V}{x}_{jik}-\sum _{j\in V}{x}_{js\left(i\right)k}=0,i\in P^{+},k\in K$

$T_{ik}+t_i+T_{is\left(i\right)}⩽T_{s\left(i\right)k},i\in P^{+},s\left(i\right)\in P^{-},k\in K$

$x_{ijk}\in \left\{\mathrm{0,\; 1}\right\},i,j\in P,k\in K,$

2）时间约束:考虑到不同学校之间校铃的差异，确保所有校车将学生在学校规定的最早到达时间e_i与最晚到达时间l_i内送达．确定一个最大乘车时间t_max避免学生的车内时间过长，出现校车服务水平过低的情况．

$e_i⩽T_{ik}⩽l_i,i\in P^{-},k\in K,$

3）容量约束:保证在任何时间节点车上人数都在容量Q之内及不同站点之间车内容量的变化进行约束．

$\left|n_i\right|⩽L_{ik}⩽Q,i\in P^{+},k\in K\text{,}$

$x_{ijk}\left(L_{ik}+\left|n_i\right|-L_{jk}\right)=0,i,j\in P,k\in K,$

4）场站约束:保证校车k从场站出发时车内无学生，完成学生接送服务后又回到原场站．

$L_{0k}=0,k\in K,$

综上所述，混载情景下校车路径规划数学模型可以表达为

$min{F}_3={\alpha }_1\sum _{j\in P+k\in K}\sum _{0,kj}+{\alpha }_2\sum _{i\in V}\sum _{j\in V}\sum _{k\in K}{x}_{ijk}\cdot c_{ij},$

3 求解算法

3.1 算法框架选取

遗传算法是校车问题中最常用的，因为遗传算法将目标函数定为搜索信息，故求解多目标函数具有优势．遗传算法在搜索时遵循概率，全局性较强，具有一定的随机性和灵活性，能大大减少参数对结果的干扰，但存在容易陷入过早收敛、对约束条件的表达不全面、对初始种群依赖性较强等缺点，影响多校问题结果的准确性^[13-14]．蚁群算法（ACO）虽然在使用上更加灵活，还可通过和其他启发式算法结合提升算法的求解能力，但是计算量大、求解时间长，无法适应大规模问题，而且在进行搜索时，容易因所有个体得出的解一致性造成运算终止，不利于得出最优解^[15]．模拟退火算法相较于上述两种算法具有更高的运算效率、更短的运算时间，且不受初始解的影响，并且该算法可以使模型中复杂的约束直观明了地展示在算法结构中^[16-18]．当然，模拟退火算法在搜索过程中容易陷入局部最优，很难保证一次输出最优解，但可以通过多次代入求解取最优解决这一问题．综合考虑研究数据量大、模型约束条件多、计算复杂等因素，故不混载与混载情景下构建的模型均以基于模拟退火算法为框架，并引入不同邻域搜索算子求解模型．为了更好地验证文中构建模型采用模拟退火算法的优越性，将求解结果与遗传算法求解模型结果进行横向对比．

3.2 邻域搜索算子

不混载情景下采用shift、swap、2-opt三种常规搜索算子，而混载情景下算法求解时路径间以及路径内的邻域搜索算子都是成对移动的．因此，结合问题特性引入PD-Shift、PD-Exchange、PD-Rearrange三种邻域算子^[19]，其主要描述如下:

1）PD-Shift:将一对点“P”与“D”从路线1移动至路线2，在移动时需要受到优化目标模型中所有约束的限制，并禁止不可行的移动，其操作示意如图2所示．

2）PD-Exchange:交换两条线路中的“P”与“D”点对．如图3所示，“P1”与“D1”是线路1中的点对，“P2”与“D2”是线路2中的点对，首先从线路1与线路2中将这两组点对删除，继而将“P1”与“D1”插入线路2中的可行位置，“P2”与“D2”插入线路1的可行位置．

3）PD-Rearrange:在相同的路径中，通过重新排列，将“P”与“D”点对放置到最佳位置，从而最大限度地降低目标函数的值．如图4所示，“P”与“D”是某线路的一组点对，通过PD-Rearrange操作，将其在线路中删除，然后将它们插入到同一线路中新的可行位置．

邻域搜索的最终结果往往过度关注总里程^[20]，与校车行驶路径优化相比，校车的投入数目才是影响校方运营成本的首要因素．因此每个局部搜索算子完成搜索产生新的邻域解后，实现Metropolis判断准则^[21]，评价函数为

式中，C（R）为路网的校车运营总成本，|R|为解中路径的数量，|r|²为解中路径r上校车停靠的站点个数，c（r）为路径r的里程．其中$\alpha \gg \beta \gg \lambda$，即三个量按照字典序依次进行评价.随着|r|²增大，优化方案中某些路径正向服务更多的站点的方向发展，更有利于路径的合并减少．

4 实验验证及数据测试

4.1 测试案例及参数设定

参数设置为校车容量Q为66 人，校车平均行驶速度v约32 km/h，考虑到服务水平，规定学生在校车上允许的最大乘车时间为2 700 s，最后设置一个位于中心位置的校车场站0．数据集提供学校坐标、站点坐标以及站点需求等，如表2所示．

考虑到模拟退火算法具有随机性，测试结果取10次结果中最优值．算法使用MATLAB2016a版本进行编程，实验电脑配置为Intel Core i5-7360U，CPU2.3 GHz，系统为Windows10．

各项参数设置如下:单位校车的购入价格α₁为20 万/辆，校车单位距离行驶成本α₂为0.001 95 元/m，单位时间停滞成本α₃为0.010 5元/s，时间价值z为0.000 27元/s．全区域乘坐校车的收费标准为150 元/月，单程的车票价格为1.25元，校车平均车速40 km/h，每辆校车的最大行驶时间设定为40 min，学生出行成本权重系数μ₁取0.37，票价成本权重系数μ₂取0.63．

4.2 不混载情景下实验结果分析

由于现有文献无同情景下不混载、站点需求不拆分的闭合回路服务模式使用测试集计算的数据，因此构建模型的求解结果对比数据为不混载情景下仅选取运营里程为优化目标的一般模型所得出的结果，如表3所示．其中N₁，D_m1，D_c1，T_c1分别表示一般模型求解结果的校车数量、行驶里程、行驶和学生出行成本，N₂，D_m2，D_c2，T_c2分别表示构建模型求解结果的校车数量、行驶里程、行驶和学生出行成本．

由表3可知，构建的模型综合考虑了校车运营时的行驶成本与学生出行成本情况，校车的投入数量平均减少14.1%，行驶里程平均降低14.4%，行驶成本平均降低14.2%，校方运营成本大部分来源于校车的购入，因此校车投入量的减少也从根本上降低了校方的投入成本．考虑使学生出行成本尽可能地达到最优，但到校模式下每辆校车服务具有很强的针对性，故学生出行成本平均降低0.26%．

4.3 混载情景下模型实验结果分析

多校混载情景下构建模型求解结果的对比数据选择测试集在同情景下单一模型求解结果，如表4所示．其中N_i，D_mi，D_ci，T_ci（i=1，2）含义同上．

从表4可知，以校车数量与运行里程为目标优化后的模型比单一目标模型总体上更具有优势，以及PD三种搜索算子的加入使站点之间实现更多的可行交换，对路线的优化明显提升，因此校车的平均投入量减少7.9%，校车行驶里程平均下降7.6%，行程成本平均下降7.5%，学生出行成本平均上升0.11%．

4.4 实例验证：五莲县校车路径优化设计

经过实地调研获得实例区域内路网情况、站点信息等数据，如表5所示．“现有路径”列下，0代表场站，1，2，···，6表示不同学校，1.1，1.2，···，2.1，···，6.12表示校车服务站点．现有校车服务模式为单校，6 所学校共配有校车14 辆，每辆校车均安排有一条线路进行接送学生服务，共有线路共14条，行驶里程265.224 km，行驶成本为587.85 元，出行成本为630.301 元．实例区域有校车停放场站一处，所有校车均从场站0出发，服务结束后回到原场站．每个站点均有固定数量的学生前往指定的学校，站点上所有学生均上车，无学生滞留现象．另外，各项参数设置除校车标准容量为46 人，其余均与测试案例相同．

4.4.1 横向对比结果

不混载情景下遗传算法和模拟退火算法求解规划结果如表6所示，混载情景下遗传算法和模拟退火算法求解规划结果如表7所示．

将模拟退火算法求解模型结果和求解结果横向对比，不混载情景下，模拟退火算法比遗传算法的校车数量、行驶里程、行驶成本、出行成本分别平均下降14.28%、19.67%、20.96%、3.60%; 混载情景下，模拟退火算法比遗传算法的校车数量、行驶里程、行驶成本、出行成本分别平均下降7.14%、15.17%、17.14%、2.72%．虽然遗传算法相对于原校车服务模式不论是混载和不混载情景下校车数量、行驶里程、行驶成本均有所改善，但是相较于模拟退火算法求解结果的优势略显不足．

4.4.2 纵向对比结果

不混载和混载情景下校车路网布局结果分别如图5和图6所示，输出的路网布局站点与站点之间为直线连接，需要与实例区域的现状可通行路网相结合，在输出的路网布局结果为基础进行调整，排除无法通行的站点连接路段．

不混载情景下的校车路网布局较原校车服务模式纵向对比，校车的投入数量减少28.6%，而校车运营的成本很大部分都来源于校车的购入，因此校车投入量的减少也从根本上降低了校车投入成本．在运营里程上，不混载情景下优化不同学校服务路径之间的衔接，使校车行驶里程降低37.8%，行驶成本降低35.6%．考虑使学生出行成本尽可能达到最优，使学生获得更好的乘车体验，但到校模式下每辆校车服务具有很强的针对性，故学生出行成本降低4.3%．

混载情景下的校车路网布局较原校车服务模式纵向对比，无论是校车的投入还是校车运营过程中的资金投入都具有较大优势，校车的投入数量和行驶里程分别减少37.5%、42.0%．而且此情景下校车调用更加灵活，路径方案之间的交替变换也产生更多的可能，行驶成本下降35.8%．但由于混载情景的复杂性，难以同时兼顾出行成本，也产生了最多的出行时间，在一定程度上降低了校车的服务水平，因此学生出行成本上略微高于原校车服务模式，增加了0.5%．

在不混载与混载两种情景下，基于模拟退火算法和遗传算法的校车路网布局结果与原校车服务模式纵横向差异性对比，如图7所示．

5 结论

文中以农村地区多校SBRP为研究对象，考虑不同情景和优化目标，建立了基于校方运营成本和学生出行成本的不混载SBRP数学模型; 考虑校方运营成本，建立了以校方运营成本和投入成本最低为目标的混载SBRP数学模型．利用模拟退火算法和遗传算法在国际基准测试案例和国内实例进行分析，得出以下结论:

1）横向对比分析，无论是不混载情景还是混载情景下，模拟退火算法比遗传算法的校车数量、行驶里程、行驶成本、出行成本均有所下降，引入不同搜索算子的模拟退火算法求解构建模型的结果较遗传算法求解结果更具有优势，对文中构建考虑多种优化目标的模型具有更强的针对性．

2）纵向对比分析，文中建立的不混载SBRP模型在兼容降低运营成本的同时可以有效提高农村校车的服务水平，保证优化校车的投入和总里程，平均降低行驶里程37.8%，降低校方运营成本分别为28.6%、35.6%，同时考虑学生的出行感知度，减少学生出行成本为4.3%，学生获得更好的乘车体验．建立的混载SBRP模型能够最大程度缩减运营成本分别为37.5%、35.8%，行驶里程降低了42.0%，且校车调用更加灵活，路径方案之间的交替变换产生更多的可能，更有利于校方运营．

3）值得指出的是，对于站点需求拆分及校车多车型的情景、求解模型的算法的进一步改进，以及混载情景下，不同的校车路网布局对学生等车时间的影响等，这将是下一步的研究方向．

参考文献