[摘要]针对单线校车路径规划问题，在对相关研究成果进行综述的基础上，考虑校车行驶过程中道路长度、道路属性和交通拥堵情况等影响因素，建立了单线校车路径规划模型，利用加入剪枝规则和禁忌表的改进洪泛算法进行求解，有效地提高了求解速度。以大连嘉汇阳光小学校车调度为例，对其某条线路进行优化，仿真结果表明，该算法可以求得最优解，且在求解效率上优于传统的精确算法。
　　[关键词]校车路径规划；洪泛算法；剪枝算法
　　1引言
　　进入21世纪以来，我国对中小学义务教育进行了结构性的调整，学校总数不断减少，由此带来学生因上下学的路程增加而导致的安全性降低问题，地方政府纷纷投资引进专业校车来保障学生就学的安全性。如何对校车路径进行合理规划，降低学生交通时间是校车运营者要考虑的问题。校车路径的规划要考虑资源、交通、資金、时间等很多复杂因素，在现有的研究中，已有很多学者借鉴求解车辆路径问题（VRP）的算法，但是校车路径规划问题（sBRP）与VRP不同，学生在路上的时间越长就会多一分危险，所以时间因素、安全性是最重要的目标。
　　校车在国外的发展较早，线路设计规划研究主要集中在车辆容载量、乘车站点、科学算法等单目标或者多目标的规划。E.M.Bronshtein等以最小化学生平均乘车时间为目标，使用精确算法和简单的启发式算法解决问题。Corberan等翻采用分散搜索算法，首先对数据进行分区，构造初始可行解，接着按照相同路径内或者不同路径间的站点互相交换的方式更新可行解，最终通过匹配组合形成不同的方案，经过比较得出最优解。Arias-Roias等综合车辆容量和数量因素，采用ACO优化了路径。Jalel Euchi和Rafaa Mraihit～将ACO与变邻域搜索算法进行结合，建立了混合算法。Kevin M.Curtin等利用禁忌搜索算法，探讨针对站点的数量，用地理信息系统（GIs）工具解决是否能得出最优或者次优的问题。Khalid A.ELDRANDALY等结合GIS技术、聚类技术、网络切割技术、混合蚁群优化算法与改进的林和克尼汉启发式结合，创造了一种新的GIS决策框架，并在GIS 9.2网络环境下优化了11条路线问题。
　　国内学者最初关于SBRP研究的时间起步较晚，成果较少。符卓提出最远者优先启发式算法，首先从离学校最远的站点开始指派，然后就近访問其余站点，直到满载，之后再调整实现车辆最少、线路最短。刘丞等建立了车辆路径优化模型，结合局部优算方法2-opt方法，运用蚁群算法使运载路线相对均衡。吕腾捷利用坐标拾取系统对学生进行坐标三点分析后划分出三个区域，然后按照路程中距离、拥堵情况和高速三个因素匹配权重，利用Prim算法得出较优的路径。陈小潘设计了学校上学时间优化和校车调度的两阶段启发式求解算法，在模拟退火算法框架下，采用VRP局部搜索算子进行路径间和路径内的调整优化，实验结果表明，针对大规模案例，启发式算法的求解质量整体上优于精确求解。
　　虽然智能算法有许多优点，但它也存在一些缺陷。智能算法的研究起步较晚，理论研究滞后于应用研究，容易出现停滞现象，当搜索进行到一定程度，所有个体发现一致解时，容易陷入局部最优，不能进一步搜索，从而不能保证获得的解是最优解；对于大规模的求解问题，智能算法搜索时间较长。智能算法与其他传统优化技术相结合，一定程度上可以提高算法的性能，将会大大促进理论和计算方法在各个领域中的应用。
　　2校车路径问题的模型建立和算法设计
　　为了准确描述本文的研究问题，本只选取一所学校的一条校车行驶路线，要求校车经过所有站点，以最短的时间将学生准时送达学校。
　　2.1校车路径规划问题影响因素
　　在规划校车路线时，主要考虑以下五个方面的因素：
　　（1）道路条件。道路条件是由道路状况决定的，并能影响汽车行驶速率，这里只考虑道路等级。根据国家城市道路划分标准，道路被划分为4个等级，根据道路等级可以确定路质系数hij，见表1。