基于洪泛算法的单线校车路径规划问题研究

薛伟莲，于 希，周 风，李倩影

（辽宁师范大学 管理学院，辽宁 大连 116029）

基于洪泛算法的单线校车路径规划问题研究

薛伟莲，于 希，周 风，李倩影

（辽宁师范大学 管理学院，辽宁 大连 116029）

针对单线校车路径规划问题，在对相关研究成果进行综述的基础上，考虑校车行驶过程中道路长度、道路属性和交通拥堵情况等影响因素，建立了单线校车路径规划模型，利用加入剪枝规则和禁忌表的改进洪泛算法进行求解，有效地提高了求解速度。以大连嘉汇阳光小学校车调度为例，对其某条线路进行优化，仿真结果表明，该算法可以求得最优解，且在求解效率上优于传统的精确算法。

校车路径规划；洪泛算法；剪枝算法

1 引言

进入21世纪以来，我国对中小学义务教育进行了结构性的调整，学校总数不断减少，由此带来学生因上下学的路程增加而导致的安全性降低问题，地方政府纷纷投资引进专业校车来保障学生就学的安全性。如何对校车路径进行合理规划，降低学生交通时间是校车运营者要考虑的问题。校车路径的规划要考虑资源、交通、资金、时间等很多复杂因素，在现有的研究中，已有很多学者借鉴求解车辆路径问题（VRP）的算法，但是校车路径规划问题（SBRP）与VRP不同，学生在路上的时间越长就会多一分危险，所以时间因素、安全性是最重要的目标。

校车在国外的发展较早，线路设计规划研究主要集中在车辆容载量、乘车站点、科学算法等单目标或者多目标的规划。E.M.Bronshtein等[1]以最小化学生平均乘车时间为目标，使用精确算法和简单的启发式算法解决问题。Corberán等[2]采用分散搜索算法，首先对数据进行分区，构造初始可行解，接着按照相同路径内或者不同路径间的站点互相交换的方式更新可行解，最终通过匹配组合形成不同的方案，经过比较得出最优解。Arias-Rojas等[3]综合车辆容量和数量因素，采用ACO优化了路径。Jalel Euchi和Rafaa Mraihi[4]将ACO与变邻域搜索算法进行结合，建立了混合算法。Kevin M.Curtin等[5]利用禁忌搜索算法，探讨针对站点的数量，用地

理信息系统（GIS）工具解决是否能得出最优或者次优的问题。Khalid A.ELDRANDALY等[6]结合GIS技术、聚类技术、网络切割技术、混合蚁群优化算法与改进的林和克尼汉启发式结合，创造了一种新的GIS决策框架，并在GIS 9.2网络环境下优化了11条路线问题。

国内学者最初关于SBRP研究的时间起步较晚，成果较少。符卓[7]提出最远者优先启发式算法，首先从离学校最远的站点开始指派，然后就近访问其余站点，直到满载，之后再调整实现车辆最少、线路最短。刘丞等[8]建立了车辆路径优化模型，结合局部优算方法2-opt方法，运用蚁群算法使运载路线相对均衡。吕腾捷[9]利用坐标拾取系统对学生进行坐标三点分析后划分出三个区域，然后按照路程中距离、拥堵情况和高速三个因素匹配权重，利用Prim算法得出较优的路径。陈小潘[10]设计了学校上学时间优化和校车调度的两阶段启发式求解算法，在模拟退火算法框架下，采用VRP局部搜索算子进行路径间和路径内的调整优化，实验结果表明,针对大规模案例，启发式算法的求解质量整体上优于精确求解。

虽然智能算法有许多优点，但它也存在一些缺陷。智能算法的研究起步较晚，理论研究滞后于应用研究，容易出现停滞现象，当搜索进行到一定程度，所有个体发现一致解时，容易陷入局部最优，不能进一步搜索，从而不能保证获得的解是最优解；对于大规模的求解问题，智能算法搜索时间较长。智能算法与其他传统优化技术相结合，一定程度上可以提高算法的性能，将会大大促进理论和计算方法在各个领域中的应用。

2 校车路径问题的模型建立和算法设计

为了准确描述本文的研究问题，本只选取一所学校的一条校车行驶路线，要求校车经过所有站点，以最短的时间将学生准时送达学校。

2.1 校车路径规划问题影响因素

在规划校车路线时，主要考虑以下五个方面的因素：

（1）道路条件。道路条件是由道路状况决定的，并能影响汽车行驶速率，这里只考虑道路等级。根据国家城市道路划分标准，道路被划分为4个等级，根据道路等级可以确定路质系数hij，见表1。

表1 路质系数hij的取值范围表

（2）道路拥堵因素。在城市交通中，影响道路通畅能力的主要因素是拥堵情况。拥堵程度用路况系数rij表示，见表2。

表2 路况系数rij的取值范围表

（3）节点间的路径。多数车辆路径规划问题用两个站点间的直线距离表示它们之间的距离，而现实中道路自身情况十分复杂，两个站点间需要经过多个节点、多条路段，选择走主干路或是次干路，是单行还是双行等，导致求出的实际时间与直线距离不同。本文中将所有的交叉口设置为节点，通过将每个路段实际距离dij与权系数相乘，得到拥堵距离见式（1）。

（4）行驶时间。本文的目标是车辆行驶时间最短,已知平均速度v0，路段通行时间的计算方式为：

（5）红绿灯节点延迟时间。转弯时等待信号灯的时间较长，所以纳入考虑范围。为方便研究，本文将每条路段延迟时间阻碍delay定为10s。陈虓[11]于2012年提出，通常节点可以概括为丁字节点和十字节点，不同的位置转向在不同方向所受阻碍是不同的，按照国内右手交通规则，详细说明这两种情况。

当同样等级的路段相交形成交叉口：

tr为右转向阻碍，ts为直行阻碍，tl为左转向阻碍，delay为阻碍单位。

当交叉的路段有主次分别时，如图1所示，主要道路是123方向，而次要路是24方向时，此时转向阻碍计算如下：

对于丁字节点（图1a）：

对于十字节点（图1b）：

tijq表示ij转向iq的阻碍；delayij表示ij路段方向造成的阻碍。

图1 节点结构示意图

2.2 模型设计

为了使问题简化，对模型做出如下假设：

（1）只考虑路段拥堵情况和道路本身的情况，不考虑不同时间段数据的变化，也就是假设hij、rij数据是稳定的；

（2）每条路径的路线不重复出现；

（3）假设车辆从较远的学生乘车站点出发，开始时刻为0时刻，目标地点是学校。

交通网络可以简化成一个带权的有向图，要求从源节点出发，经过所有乘车站点集合C，到达目的节点des。路网中的目的节点、乘车站点和交叉点构成图的节点的集合，各个节点间的路径作为图的链路，链路有方向性。路网可描述为G=(V,E)，V是所有节点的集合点的坐标表示为乘车节点集合道路交叉口节点集合校车访问完所有乘车点后直接返回学校。E是所有节点间链路的集合，对于每个eij，用三个值表示。禁忌表tabuk初始状态包括全部乘车点，即tabuk=C，当路径k经过某站点后则将该站点从其禁忌表中移除，具体的参数见表3。

表3 参数及说明

目标函数：

约束条件：

式（6）是目标函数，求解用时最短的路径，式（7）表示路径k必须满足容量约束，式（8）表示路径k行驶时间约束Tc，式（9）是路径k的总长度。

在地图上标出学生乘车站点和交叉口道路节点，得出每段路的路长dij、路质系数hij，参考实时动态地图得出路况系数rij,分别从距离学校最远的站点中选取起点，记录每个起点运行所用时间、总路程和路径，每个乘车站点仅访问一次，最后比较不同起点的结果，选取最优方案。

2.3 算法设计

随着节点数增多，洪泛算法的时间和空间复杂度成指数增长。本文提出一种改进算法，通过引入剪枝算法和禁忌表来降低洪泛算法的盲目性和冗余性,有效减少候选解的规模。其核心思想是通过洪泛算法设定起点

和禁忌表后求解路径，利用剪枝规则和禁忌表删去不符合条件的路径，最先到达目的节点的有效路径即为最优路径，洪泛算法的详细流程如图2所示。

图2 算法流程

剪枝规则：

（1）记录路径访问过的节点，到达终点后禁忌表为空的路径为有效路径，若禁忌表不为空，表示有乘车点没有经过，则剪枝该路径；

（2）将重复出现相同的节点的路径剪枝；

（3）每条路径行驶时间大于Tc时剪枝；

（4）减少回溯洪泛的方式：

将刚经过的节点记为j，若为乘车点则将此站点从tabuk中删除，判断 j的纵坐标是否大于tabuk中所有点的纵坐标，若全部大于，说明j上方没有乘车节点，其余tabuk中的点在下方，此时，洪泛范围定义为 j的纵坐标向上延伸w（回溯范围变量）千米范围内的点；若j的纵坐标不大于tabuk中所有点的纵坐标，则说明还有乘车点在j的上方，此时不加限制。

3 案例分析—以大连嘉汇阳光小学为例

3.1 案例描述

大连嘉汇教育发展有限公司主要从事基础教育，是一个全面综合现代化的教育公司，嘉汇阳光小学是公司管辖的五所中小学校之一，其良好的教育师资吸引了众多学子。为保障学生上下学安全，学校专门配备了校车，本文选取校车路线中的一条进行优化。参考地图，图中五角星标明了嘉汇·阳光学校—幸福E家线路中的8个乘车点，编号和乘车人数见表4。从站点0到8的总长为3.7km，其余交叉口节点编号为9到110，如图3所示。为节省篇幅，其中图3(a)是图的上半部分，图3(b)是图的下半部分，五角星代表乘车点。

嘉汇阳光小学根据经验设定的路线为：1→16→15→24→4→25→29→30→3→81→91→90→89→2→88→82→83→84→85→98→102→9→33→47→31→48→74→5→72→71→42→43→6→44→46→50→49→70→7→69→8→0。实际总长度为：12.31km，全程行驶时间约为44min。

表4 站点编号和上车人数

3.2 试验结果及分析

模型假设条件与主要参数的设定同上，定义学校为目的节点，des={0}，学生乘车站点共8个，C={1,2,3,4,5,6, 7,8}，交叉节点为J={9,10，…，110}，定义Tc=45min= 0.75h。

3.2.1 实验结果。将大连嘉汇阳光小学的交通数据导入Matlab中，因站点1、2、3、4距离学校都比较远，因此分别设定为起点，0为终点，综合各方面因素，设定w= 1。行驶路径见表5，路程和时间见表6。

分析试验结果发现，以1为起点得到的优化后路线和学校人工制定的相同，以4为起点用时最少，而以1和2为起点的路线走的是所有路线中的外围，即83→84→85→98→102→9→33→47→31→48→74→5，而不是直接 从 83→86→96→99→100→103→105→107→108→109→32→73→48→74→5，分析可得，由于图3中内侧道路的拥堵程度较大，模拟时间偏长，所以走外围的时间相对短。综上，最优的选择是以4为起点的路线，比原路线减少了2.4min。

3.2.2 回溯范围变量w分析。当w取值减小，算法的运

行时间t也会随之减少，以本文案例中1为起点进行说明。

图3 参考路线和节点

表5 仿真结果

表6 路程和时间

表7 w和t的对照表

采用基本的洪泛算法，没有w限制时，运行时间很长；本文算法中w为0.2时，不能保证得到最优解，大于0.5时可以得到最优解；用蚁群算法求解时，一共运行20次，平均每次运行时间为178s，但只有5次得出最优解，正确率只有25%。因此当设定的w值适当时，能以较少的时间代价得到最优解。

4 结语

本文考虑校车行驶过程中道路长度、道路属性和交通拥堵情况等影响因素，构建了单线校车路径规划模型，并用融入了禁忌表和剪枝算法的改进洪泛算法进行求解，选取大连嘉汇阳光小学的一条校车路线，对模型算法进行验证，将路程行驶时间缩短了2.4min。虽然相对于元启发算法效率偏低，但是通过控制回溯因子，可以较低的代价获得最优解，为路径规划问题的求解提供了一个新思路。

[1]E M Bronshtein,D M Vagapova,A V Nazmutdinova.On constructing a family of student delivery routes in minimal time[J]. Automation and Remote Control,2014,75(7):1 195-1 202.

[2]Corberán A,Fernández E,Laguna M,et al.Heuristic solutions to the problem of routing school buses with multiple objectives[J].Journal of Operational Research Society,2002,53: 427-435.

[3]Arias-Rojas J S,Jiménez,Montoya-Torres J R.Solving of school bus routing problem by ant colony optimization[J].Revista EIA,2012,(17):193-208.

[4]Jalel Euchi,Rafaa Mraihi.The urban bus routing problem in the Tunisian case by the hybrid artificial ant colony algorithm[J]. Swarm and Evolutionary Computation,2011,(2):15-24.[5]Kevin M Curtin,Gabriela Voicu,Matthew T Rice,Anthony Stefanidis.A Comparative Analysis of Traveling Salesman Solutions from Geographic Information Systems[J].Transactions in GIS,2014,18(2):286-301.

[6]K Eldrandaly,A M Abdallah.A novel GIS-based decisionmaking framework for the school bus routing problem[J].Geospatial Information Science,2012,15(1):51-59.

[7]符卓.开放式车辆路径问题及其应用研究[D].长沙:中南大学,2003.

[8]刘丞,乔金友,金鑫.基于蚁群算法的通勤车路径问题优化研究[J].物流技术,2013,32(3):278-280.

[9]吕腾捷.校车路径规划问题分析[J].新经济,2014,(23):15-16.

[10]陈小潘,孔云峰,牛宁,等.一种基于学校上学时间调整的校车调度算法[J].小型微型计算机系统,2015,36(9):2 159-2 165.

[11]陈虓.交通网络最优路径分析研究[D].郑州:解放军信息工程大学,2012.

Study on Single-track School Bus Route Planning Problem Based on Flooding Algorithm

Xue Weilian,Yu Xi,Zhou Feng,Li Qianying
(School of Management,Liaoning Normal University,Dalian 116029,China)

In this paper,in view of the single-track school bus route planning problem,on the basis of a review of relevant literatures, we considered the major influence factors such as route length,road attribute and traffic congestion,etc.,established the single-track school bus route planning model and solved it using the flooding algorithm modified by the addition of the pruning rule and tabu list.Then in the case of the Dalian Jiahui Sunshine Elementary School,we optimized one of its school bus routes and demonstrated that the efficiency of the method proposed in this paper was superior to the traditional exact algorithm.

school bus route planning;flooding algorithm;pruning algorithm

U116.2;F224.0

A

1005-152X(2016)10-0048-05

10.3969/j.issn.1005-152X.2016.10.013

2016-09-03

国家自然科学基金项目（61272417）

薛伟莲（1966-），女，回族，辽宁营口人，教授，博士，研究方向：无线网络、智能计算。