校车最优路径规划算法研究

薛 瑞 张永显

(1.信阳师范学院计算机与信息技术学院， 河南 信阳 464000；2.信阳师范学院城市与环境科学学院， 河南 信阳 464000)



校车最优路径规划算法研究

薛 瑞1张永显2

(1.信阳师范学院计算机与信息技术学院， 河南 信阳 464000；2.信阳师范学院城市与环境科学学院， 河南 信阳 464000)

校车最优路线的规划直接影响全校师生的工作、学习和生活。采用Dijkstra算法和GIS技术相结合的方式，根据对校园师生问卷调查的结果确定停靠站点，建立最优路径规划算法的前提条件;从起点到终点及中间的连接点，计算校园各乘车站点之间的最优路径规划方案,提高校车利用率，在保证校园师生安全的前提下，节省广大师生的时间，提高获取教育资源的便捷程度，降低校园能耗。

最优路径； Dijkstra算法； GIS

随着高等教育的发展，高校招生规模的扩大，校园占地面积越来越大，教学楼、学生宿舍、餐厅、体育场等分布更加分散，因此，交通的安全与便捷问题成为校园师生最为关注的问题。越来越多的高校采取校园公共交通的方式。校园公交车不仅能够更加有效地保障校园师生的安全，节省校园师生在路途上花费的时间，同时还能够有效利用现有资源，降低校园能耗，为建立节约型校园作出贡献。本次研究以信阳师范学院为例，对当前校园公交车的路线满意度进行校园问卷调查和网上问卷调查，结合实际情况开展校园公交车最优路径分析，制定一套优化的校车运行路线方案，更好地满足师院师生的需求。

信阳师范学院占地面积79.5万m2，校舍建筑面积49.8万m2。目前在校学生有2万多人，校内公交车运行路线只有2条。以学校规划图为底图，进行校园观光车最优路径规划研究。

1 校园公交车最优路径规划算法

用于解决最短路径问题的算法被称做“最短路径算法”。到目前为止，解决最短路径常用的算法有Dijkstra算法[1]和Floyd算法[2]、以及启发式A*算法[3]等。在这些算法中，Dijkstra算法是典型的单源最短路径算法。

1.1 Dijkstra算法概述

Dijkstra算法的主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。设置并逐步扩充一个集合S，存放已求出其最短路径的顶点，尚未确定最短路径的顶点集合是V-S，其中V为网中所有结点集合，按最短路径长度递增的顺序逐个把V-S中的顶点加到S中，直到V-S为空,令M(Vi,Vj)表示点Vi到点Vj的最短距离，具体步骤为：

Step1，设定起点V1，标号M(1)=0；

Step2，求出所有M(Vi,Vj)，其中Vi为已标号点或起点，Vj为标号点，如果已无未标号点，则计算结束；

Step3，计算M(j)=min{M(j),M(i)+M(Vi,Vj)}；

Step4，计算min[M(j)]=M(j0),给Vj以标号，若M(j0)=M(j),则返回第一步。

1.2 校园公交车路线网络与结点处理

在校园公交车最优路径规划算法中确定起点、终点和所要经过的中间点、中间连线，求最短路径[4]。在实际中由于客流量、坡度、交通安全等因素的影响，仅由最短路径算法求出的最佳路径并不能满足师生的需要。为此，根据经过结点的学生流量计算客流量最大的点，并将其设置为相应的乘车结点，然后记录起始点到该点的最短路径信息。

2 最优路径规划算法在校园公交车中的实现

2.1 建立矢量图

利用GPS与ArcGIS软件完成校园规划平面图的矢量化工作。具体步骤：(1)将底图加载到ArcGIS中，打开catalog相应位置，建立shp文件，放大矢量化的结果；(2)利用editor软件编辑刚刚建立的shp文件；(3)矢量保存，选择刚完成的矢量文件，输入文件的指定路径和文件名称，建立矢量化的校园地图(图1)。

图1 信阳师范学院校园矢量图

在矢量地图上标绘出餐厅、教学楼、宿舍楼、图书馆等具体位置并建立相对应的属性数据(表1),针对每一图斑进行面积和周长的计算[5]。

表1 行车线路属性表

2.2 建立校园道路分布图

从校园矢量地图的属性表中，查找属性为道路的图。由于校园平面图为大比例尺的地图，因此以多边形为单位进行矢量化，利用ArcGIS软件，将得到的道路面转化为线，然后利用callapse dual lines centerline软件提取道路中线，进行道路拓扑查询分析，最终生成信阳师范学院道路分布图。

2.3 建立阻抗矩阵

以信阳师范学院师生为对象，对校园公交车进行问卷调查。结果表明：目前校园公交车行车路线较为单一，仅有“师院正门 — 师院东门”、 “师院正门 — 海苑”2条行车路线。虽然有时在行驶过程中，司机考虑师生的需求，适时改变行车路线，但是这一做法虽能在一定程度上满足乘车人的需求，但不固定的行车路线，为大学校园带来了一定的安全隐患。固定站点的设立和选择是保障师生安全的重要手段之一。目前信阳师范学院校园公交车1号线的行车路径：正门 — 26#宿舍楼 — 科技馆 — 社科楼 — 八餐 — 九餐 — 东门。根据矢量地图上标绘出的餐厅、教学楼、宿舍楼、图书馆等具体位置并建立相对应的属性数据。1号线的属性如表2所示。

表2 校园公交车1号线属性表

为此，将已有行车路线的站点与师生建议增加的行车路线的站点作为建立阻抗矩阵的站点，作为校园公交车的固定站点。结合DEM坡度模型[6]，正门到东门1号线的阻抗矩阵M1为:

校园公交车2号线行车路径：正门 — 理科楼 — 西操场 — 体育馆 — 新图书馆 — 教九楼 — 东门，属性如表3所示。

表3 校园公交车2号线属性表

则正门到东门2号线的阻抗矩阵M2为:

利用Dijkstra算法得出1号线最短路径为1 214.11m，中间站点为科技馆、社科楼、八餐和九餐；2号线最短路径为1 412.71m，中间站点为理科楼、新图书馆、教九楼；此外，根据调查问卷结果，为满足广大师生需求，增设新的校园公交车路线为正门 — 理科楼 — 人文楼 — 逸夫楼 — 八餐 — 东操场 — 30#宿舍楼 — 海苑，故确定这些地方为站点位置，考虑连通所有站点的情况下，正门到海苑的最短路径，利用ArcGIS软件计算从正门到所有站点的最优路径，新增路线属性如表4。

表4 新增路线属性表

新增路线的阻抗矩阵M3为:

利用Dijkstra算法及阻抗矩阵M3，增设的校园公交车起始点为正门，中间站点为理科楼、人文楼、逸夫楼、八餐、东操场和30#宿舍楼，终点站为海苑。连接各站点，正门到海苑的最短路径为1 472.53m，同时计算出各个站点到海苑的最短路径和任意两站点之间的最短路径。

2.4 校园公交车最优路径规划

利用正门到东门，且连接各站点的最短路径分析建立阻抗矩阵，结合GIS可视化地图实现从正门到东门的最短路径的寻优，并借助GIS技术实现最优路径的查询。2条校园公交线路优化如下：

1号线最优路径为：正门 — 新民大道 — 思齐路 — 桃李路 — 东门；沿途停靠点为：正门(起点)、科技馆、社科楼、1#宿舍楼、八餐、九餐、东门(终点)；

2号线最优路径为：正门 — 景明大道 — 博学路 — 东坡路 — 东门；沿途停靠点为：正门(起点)、理科楼、文科楼、新图书馆、东门(终点)；

新增路线最优路径为：正门 — 新民大道 — 思齐路 — 海苑路 — 海苑；沿途停靠点：正门(起点)、科技馆、社科楼、1#宿舍楼、30#宿舍楼、海苑(终点)。

3 结 语

最优路径规划算法是GIS网络分析在交通上最重要的应用之一。以信阳师范学院校园公交路线的建立为例,实现校园最短路径的优化,减少校车运行总时间，降低交通成本。

[1] Dijkstra E W .A Note on Two Problems in Connexion with Graphs[J].Numberische Mathematik,1959,1(1)：269-271.

[2] Hougardy S. The Floyed-Warshall Algorithm on Graphm on Graphs with Negative Cycles[J].Information Processing Letter,2010,4:279-281.

[3] Nicosia G，Oriolo G. An Approximate A*Algorithm and Its Application on the SCS Problem[J].Theoretical Computer Science，2003,290(3):2021-2029.

[4] 龚健雅.地理信息系统[M].北京：科学出版社，2001:180-187.

[5] 刘桂萍,张晓帆,陈川.最短路径在ArcGIS空间分析中的实现[J].新疆大学学报(自然科学版)，2008,25(3):353-355.

[6] 刘学军,张平,朱莹.DEM坡度计算的适宜窗口分析[J].测绘科学,2009,38(3):264-271.

The Optimal Path Planning Algorithm for Campus Bus

XUERui1ZHANGYongxian2

(1. School of Computer Science, Xinyang Normal University, Xinyang Henan 464000, China;2. College of Urben and Environment Science, Xinyang Normal University, Xinyang Henan 464000, China)

The optimal route planning of the campus bus directly affects the teachers′ and students′ work, study and life. Based on Dijkstra algorithm and GIS technology, we could establish the optimal route planning algorithm after we determined the docking sites according to the results of a questionnaire for the teachers and students. The optimal route planning would be set up according to the starting point to the end and intermediate connection points, to improve the campus bus utilization rate. Considering the safety of teachers and students on campus, it could save the time of teachers and students, increase the convenient degree of access to educational resources, and reduce the energy consumption of the campus.

optimal path; Dijkstra algorithm; GIS

2015-05-25

河南省自然科学基金项目“若干网络优化模型及算法研究”(142300410393)

薛瑞(1979 — ),女,硕士,讲师,研究方向为智能计算。

U116.2

A

1673-1980(2015)05-0068-04