基于运营和出行成本的校车路径问题研究

李开雷　白翰　燕翔　朱漫兮　王修光

摘要 为解决农村地区校车路网布局中校方运营成本过高，以及乘车站点分布散乱导致校车服务质量差的问题，建立混载与不混载场景下多目标校车路径规划问题（SBRP）模型．在不混载情景下，构建以学生出行成本和校方运营成本为优化目标的融合校车服务水平的SBRP数学模型;在混载情景下，构建考虑校车投入成本与运营成本的SBRP数学模型．通过对比多个启发式算法，确定基于模拟退火算法的求解流程和基于遗传算法求解结果的横向比对．最后，在国际基准案例上进行了测试，基于模拟退火算法引入不同搜索算子求解不同场景下构建的SBRP数学模型，应用于山东日照五莲县校车路径优化设计，结果表明不混载SBRP情景下，提出的方法较原校车运营方式，校车投入量、行驶里程、行程成本分别减少28.6％、37.8％、35.6％，考虑到学生的校车服务感知度，学生出行成本降低4.3％;由于混载情景的复杂性，难以有效兼顾出行成本，提出的方法较原校车运营方式的学生出行成本增加了0.5％，但校车投入量、行驶里程、行程成本分别减少37.5％、42.0％、35.8％，更好地验证了构建模型的有效性及模拟退火算法相较于遗传算法，能够更大程度提高农村地区校车服务质量和降低校方运营成本．关键词 公路运输管理;校车路径问题;混载;模拟退火算法;多目标;出行成本

中图分类号U492.4

文献标志码A

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 参数和决策变量

2.2 构建模型

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

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

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］，评价函数为

4 实验验证及数据测试

4.1 测试案例及参数设定

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

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

由于现有文献无同情景下不混载、站点需求不拆分的闭合回路服务模式使用测试集计算的数据，因此构建模型的求解结果对比数据为不混载情景下仅选取运营里程为优化目标的一般模型所得出的结果，如表3所示．其中N1，Dm1，Dc1，Tc1分别表示一般模型求解结果的校车数量、行驶里程、行驶和学生出行成本，N2，Dm2，Dc2，Tc2分别表示构建模型求解结果的校车数量、行驶里程、行驶和学生出行成本．由表3可知，构建的模型综合考虑了校车运营时的行驶成本与学生出行成本情况，校车的投入数量平均减少14.1％，行驶里程平均降低14.4％，行驶成本平均降低14.2％，校方运营成本大部分来源于校车的购入，因此校车投入量的减少也从根本上降低了校方的投入成本．考虑使学生出行成本尽可能地达到最优，但到校模式下每辆校车服务具有很强的针对性，故学生出行成本平均降低0.26％．

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

多校混载情景下构建模型求解结果的对比数据选择测试集在同情景下单一模型求解结果，如表4所示．其中Ni，Dmi，Dci，Tci（i=1，2）含义同上．从表4可知，以校车数量与运行里程为目标优化后的模型比单一目标模型总体上更具有优势，以及PD三种搜索算子的加入使站点之间实现更多的可行交换，对路线的优化明显提升，因此校车的平均投入量减少7.9％，校车行驶里程平均下降7.6％，行程成本平均下降7.5％，学生出行成本平均上升0.11％．

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

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

参考文献 References

［1］Newton R M，Thomas W H.Bus routing in a multi-school system［J］.Computers ＆ Operations Research，1974，1（2）：213-222

［2］ Jaradat A S，Shatnawi M Q.Solving school bus routing problem by intelligent water drops algorithm［J］.Journal of Computer Science，2020，16（1）：25-34

［3］ Calvete H I，Galé C，Iranzo J A，et al.A partial allocation local search matheuristic for solving the school bus routing problem with bus stop selection［J］.Mathematics，2020，8（8）：1214

［4］ 高巍，陈泽颖，李大舟.基于校车数量的无混载校车路线问题模型优化实现［J］.沈阳化工大学学报，2021，35（1）：82-89GAO Wei，CHEN Zeying，LI Dazhou.Optimization of the model of unmixed school bus route based on the number of school bus［J］.Journal of Shenyang University of Chemical Technology，2021，35（1）：82-89

［5］ Hargroves B T，Demetsky M J.A computer assisted school bus routing strategy：a case study［J］.Socio-Economic Planning Sciences，1981，15（6）：341-345

［6］ Hou Y，Zhao N，Dang L，et al.A hybrid metaheuristic algorithm for the school bus routing problem with multi-school planning scenarios［J］.Engineering Letters，2021，29（4）：1-10

［7］ Park J，Tae H，Kim B I.A post-improvement procedure for the mixed load school bus routing problem［J］.European Journal of Operational Research，2012，217（1）：204-213

［8］ Semba S，Mujuni E.An empirical performance comparison of meta-heuristic algorithms for school bus routing problem［J］.Tanzania Journal of Science，2019，45（1）：81-92

［9］ Braca J，Bramel J，Posner B，et al.A computerized approach to the New York City school bus routing problem［J］.IIE Transactions，1997，29（8）：693-702

［10］ 刘梦琪，瞿何舟.基于轨道交通与常规公交组合的出行路径选择研究［J］.交通运输工程与信息学报，2018，16（4）：63-68LIU Mengqi，QU Hezhou.Study on the route choice using the combination of rail and bus transit［J］.Journal of Transportation Engineering and Information，2018，16（4）：63-68

［11］ 冯焕焕，邓建华.基于前景值和乘客最优理论的居民公交出行选择模型［J］.科学技术与工程，2019，19（5）：307-311

FENG Huanhuan，DENG Jianhua.Model of public transport choice based on prospect value and passenger optimal theory［J］.Science Technology and Engineering，2019，19（5）：307-311

［12］ Levin M W，Boyles S D.Practice summary：improving bus routing for KIPP charter schools［J］.Interfaces，2016，46（2）：196-199

［13］ 洪越，殷利平.基于遗传算法的非高斯系统随机分布控制［J］.南京信息工程大学学报（自然科学版），2020，12（4）：504-509HONG Yue，YIN Liping.Genetic algorithm-based stochastic distribution control for non-Gaussian systems［J］.Journal of Nanjing University of Information Science ＆ Technology （Natural Science Edition），2020，12（4）：504-509

［14］ Minocha B，Tripathi S.Solving school bus routing problem using hybrid genetic algorithm：a case study［M］／／Advances in Intelligent Systems and Computing.New Delhi：Springer India，2014：93-103

［15］ 李燕，季建楠，沈葭栎，等.基于改进蚁群算法的移动机器人路径规划方法［J］.南京信息工程大学学报（自然科学版），2021，13（3）：298-303LI Yan，JI Jiannan，SHEN Jiali，et al.Mobile robot path planning based on improved ant colony algorithm［J］.Journal of Nanjing University of Information Science ＆ Technology （Natural Science Edition），2021，13（3）：298-303

［16］ 鄧绍强，郭宗建，李芳，等.基于Metropolis准则的自适应模拟退火粒子群优化［J］.软件导刊，2022，21（6）：85-91DENG Shaoqiang，GUO Zongjian，LI Fang，et al.Adaptive simulated annealing particle swarm optimization algorithm based on metropolis［J］.Software Guide，2022，21（6）：85-91

［17］ 李朝迁，裴建朝.新型模拟退火遗传算法在路径优化的应用［J］.组合机床与自动化加工技术，2022（3）：52-55LI Chaoqian，PEI Jianchao.Application of new simulated annealing genetic algorithm in path optimization［J］.Modular Machine Tool ＆ Automatic Manufacturing Technique，2022（3）：52-55

［18］ Yu V F，Jewpanya P，Redi A A N P，et al.Adaptive neighborhood simulated annealing for the heterogeneous fleet vehicle routing problem with multiple cross-docks［J］.Computers ＆ Operations Research，2021，129：105205

［19］ Li H B，Lim A.A metaheuristic for the pickup and delivery problem with time windows［J］.Proceedings 13th IEEE International Conference on Tools with Artificial Intelligence （ICTAI 2001）.November 7-9，2001，Dallas，TX，USA.IEEE，2001：160-167

［20］ Bent R，Hentenryck P V.A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows［J］.Computers ＆ Operations Research，2006，33（4）：875-893

［21］ Liu W W，Li X，Qin X N，et al.A metropolis criterion based fuzzy Q-learning flow controller for high-speed networks［J］.Applied Mechanics and Materials，2012，241／242／243／244：2327-2330

School bus routing considering operation and travel costs

LI Kailei BAI Han YAN Xiang ZHU Manxi WANG Xiuguang

1School of Transportation and Logistics Engineering，Shandong Jiaotong University，Jinan 250357

Abstract In order to solve the problems of high operating cost and poor service quality of school bus due to the scattered distribution of bus stops in rural areas，multi-objective SBRP （School Bus Routing Problem） models were developed for the mixed-load and non-mixed-load scenarios.In the non-mixed-load scenario，a model of the SBRP was developed to optimize the students travel cost and school operating cost，while in the mixed-load scenario，another model of the SBRP was developed to consider the input cost and operation cost of the school bus.Several heuristic algorithms were compared，based on which the simulated annealing algorithm was selected to solve the models，and the horizontal comparison of the solution results based on genetic algorithm were determined.Tests were conducted on an international bench mark case and the constructed models were solved by introducing different search operators into the simulated annealing algorithm，then the proposed approach was applied to the optimal design of school bus routes in Wulian county，Rizhao，Shandong province.The results showed that in the non-mixed-load scenario，compared with the original school bus operation mode，the school bus input，mileage and travel cost were reduced by 28.6％，37.8％ and 35.6％，respectively，and students travel cost was reduced by 4.3％ considering the students perception of school bus service.While in the mixed-load scenario，the proposed approach reduced the school bus input，mileage and travel cost by 37.5％，42.0％ and 35.8％，respectively;due to the complexity of the mixed-load scenario，it is difficult to take the travel cost into account，thus the students travel cost was increased by 0.5％.The proposed SBRP models were verified to be effective and the simulated annealing approach can optimize service quality and reduce operation cost of rural school bus to a greater extent than the genetic algorithm.

Key words highway transportation management;school bus routing problem （SBRP）;mixed-load;simulated annealing;multi-objective;travel cost