校车最优路径规划算法

参考文献
[1] Michael J de Smith，Michael FGoodchild，PaulA Long-ley，杜 培军，等译.地理空间分析--原理、技术与软件工具[M].北京: 电 子 工 业 出 版 社 ，2009
[2] Dijkstra E W. A Note on Two Problems in Connection with Graphs[J]. Numerical Mathematics，1959(1):269-271
图 4 北京市东城区灯市口学区
本文设置每个乘车节点的学生数为 50，每辆校车
的载客量为 60，共生成 21 条最优路径。如果每条线路
按照算法搜索乘车节点直至装满 1 辆车，那么应共有
17 条，且只有第 17 条线路运载的学生数不满 1 辆车，
为 40。但因为算法中的优化处理，当为充分利用车辆
资源而增加距离时，判断其同时增加的运送距离成本
图 3 遍历多个乘车节点的最优路径方案
的空间范围内选取参与计算的乘车节点，这样就避免 了大量的地理数据带来的巨大计算量。
3 应用实例
图 2 遍历最短路径上的全部乘车节点的最短路径方案
当一辆车所要运送的学生所在乘车节点都在最短 路径上时，重复步骤二、三便可处理得到校车路径方 案。但是，如果一条路径上的所有学生数也没有装满 一辆车的载客容量，却又按照最短路径到达学校时，便 造成了资源的浪费，这时则需要改变对路径的计算方 法，采用下列步骤进行计算，以提高资源利用率。
步骤五：若经过 n 个节点仍不满 1 辆车，则循环 计算出经过（n+1）、（n+2）... 直至装满 1 辆车的乘车节 点数 n'，其最短路径为 Length [n ']，此时对比所有的 Length [n]。若 Length [n '] 与所有的 Length [n]（n=1,2，...） 中最小值的差值小于路径搜索常量 K 值（K 代表了控 制最优路径搜索上限值），则取 n'个乘车节点的路径方 案；否则选取比 K 值小的且装载学生数最多的路径方 案。如图 3 所示，从起始节点出发，遍历多个乘车节 点，并将这些节点的学生送至学校。 2.2 算法优化
步骤 2：若起始乘车节点的学生数大于一辆车的容 量，也就是该节点的学生装满一辆车后其学生数仍不 为 0，则该车次不再进行其他计算直接按照最短路径直 至学校，如图 1 所示；并且第二辆车仍然以该点为起 始乘车节点继续计算；若不为 0，则继续步骤三。
图 1 从起始节点至学校的最短路径方案
收 稿 日 期 ：2011-01-21 项目来源：北京市教育委员会基金资助项目 (082070004)。
本文中，路网节点分为 2 类：一是道路与道路的交点； 二是学生乘车节点，它是根据居民地数据在与其最近 的道路上设置相应的乘车节点，然后记录报名到该节 点乘车的学生人数以及该点到学校的最短路径长度等 信息，这样就可以在规划校车路径时，将经过节点的 学生数计算到该条乘车线路的总名额中。 2 算法实现 2.1 校车路径规划
摘 要：提出一个基于 GIS 网络分析的校车路径方案规划算法。算法采用 Dijkstra 最短路径算法结合道路网络拓扑分析。
以 高 效 利 用 各 种 资 源 为 目 的 ，通 过 限 制 搜 索 范 围 提 高 算 法 效 率 ，并 用 空 间 分 析 选 择 最 佳 起 始 节 点 ，计 算 将 学 区 内 路 网 上 各
[3] 陆锋.最短路径算法:分类体系与研究进展[J].测绘学报，2001， 30(3):269-275
[4] 严寒冰，刘迎春.基于 GIS 的城市道路网最短路径算法探讨 [J].计算机学报，2000，23(2): 210-215
是否超出了路径搜索的上限值，以防止出现距离大幅
增加的问题。
在表 1 中，路径 1 共经过 2，3，5，8，7，12，15，
22，29，36 共 10 个节点，其中 2，12，22 为乘车节点，
分别将 2 节点的 50 名学生、12 节点的 10 名学生运送
到学校。路径 15 由于增加的运送成本超出范围，所以
２０１１ 年 ８ 月 第 ９ 卷第 ４ 期
地理空间信息
ＧＥＯＳＰＡＴＩＡＬ ＩＮＦＯＲＭＡＴＩＯＮ
Ａｕｇ．， ２０１１ Ｖｏｌ． ９， Ｎｏ． ４
校车最优路径规划算法
许文龙，李小娟，宫辉力，孙永华
(首都师范大学 资源环境与旅游学院 三维信息获取与应用教育部重点实验室 资源环境与地理信息系统北京市重点实验室, 北京 100048)
4结语
与最短路径算法相比，作者实现的校车最优路径 算法能够在追求尽可能缩短起始点到达目标点距离的 同时，更多考虑交通运输能力，提升人力、交通等各 种资源的利用率，从而实现一个最佳路径方案。该算 法能够为学校、学生提供解决乘车上学问题的最佳方 案，同时为学校、社区以及区域交通规划提供具有科 学性的参考。
只装载了 50 名学生，但也不再遍历邻近的其他乘车节
点。路径 33 为最后 1 条，将最后 1 个非空乘车节点 33
的 30 名学生运送致学校。
（下转第 71 页）
第 ９ 卷第 ４ 期
姚 远等：ArcGIS 平台下土地利用规划中的信息化管理
71
数据采用的是 80 西安坐标系，部分区（县）的图斑数 据采用的是 54 北京坐标系，而城市规划部门提供的规 划数据采用的是连云港市坐标系。
由于城市交通网的密集性以及走向的规律性，在 进行多个点的循环计算过程中，遵循地理空间分布规 律，优先在与起始点和目标点之间构成夹角小于 60 °
为了验证最优路径算法的高效性和科学性，作者 以北京市东城区灯市口小学学区为例，计算每条最优 路径组成校车方案。图 4 为该学区内的部分道路网，节 点 36 为代表灯市口小学的目标节点，共有道路网节点 53 个，乘车节点 20 个。
乘车节点处的学生送至学校的最优路径方案。实验结果验证了该算法的高效性和有用性。
关 键 词 ： 最 短 路 径 ； 路 网 分 析 ；GIS； 校 车
中 图 分 类 号 ：P208
文献标志码: B
文章编号: 1672-4623 (2011) 04-0067-02
随着社会经济发展和城市化进程的加快，尤其在 一些大城市，交通问题逐渐成为日常生活中的一个主 要问题，而年龄较小的中小学生以及学前儿童的上学、 放学安全问题也就成为众多家长和教育管理部门迫切 希望能够妥善解决的问题。由于年龄导致的安全问题， 以及随之带来的大量私家车接送导致学校周边交通压 力更加严重的问题都要求能有一套既能保证学生安全， 又能将对各种资源的占用降低的方法来解决。根据此 需求，作者利用 GIS 网络分析，设计针对校车路径方 案的规划算法，实现一套校车系统解决方案。
1 算法原理
1.1 经典 Dijkstra 算法 最短路径算法是解决在具有拓扑关系的连通网络
中寻找两点间最优路线问题的有效方法，它除了能够 计算最短路径距离外，还能通过给每条边赋不同的权 重值来满足不同的搜索条件，例如耗时最少路径 。 [1-3] Dijkstra 算法的思想是从起始点开始遍历计算与其相邻 的节点，找出其中距离最短的点并标记该点，再遍历 这个新标记点与其相邻且未标记过的点，然后重复之 前的搜索计算步骤，直至目标点被标记，即得到起始 点到目标点的最短路径 。 [4-5] 1.2 交通网络与节点处理
在经典Dijkstra 算法中两点间最短路径的搜索范围 基本上是以起始点为原点，以起始点与目标点的连线 长度为半径的一个圆，这样就会具有很大的盲目性 。 [6-8] 而本文中将每条道路都设一个学区字段来表示其所属 学区，在计算一个学区内一点到学校的最短路径时就 能将其搜范围限定在学区内，从而提高算法效率。在
参考文献
[1] 张雅彬，孙在宏，吴长彬. 基于 GIS 的土地利用总体规划管 理信息系统的开发与研究[J]. 南京师大学报：自然科学版， 2004, 27(2): 107-110
[2] 陈奇，李满春，余有胜，等. 关于土地利用总体规划 MIS 的若 干思考[J]. 计算机应用研究，1999(05): 80-82
积极开发运用信息技术、构架网络公众参与平台 可以使土地利用规划部门的决策更符合广大人民的切 身利益，它无疑是未来土地利用规划的一种重要方式， 而目前我国土地管理过程中公众参与程度仍处于较低 水平，部门领导和学者顾问依旧是土地利用规划管理 中的主体，社会公众对土地利用规划的认知和参与很 少。随着 GPS、GIS 技术的发展成熟，在土地利用总体 规划中，运用以上技术建立规划的模拟方案，不仅使 规划具体直观，而且易于公众对规划的理解，并形成 较为具体的认识；而且运用信息技术、构架网络公众 参与平台还能有效提高效率 。 [10]
步骤四：当 1 条路径上的所有乘车节点的学生数 也没有装满 1 辆车时，在学区范围内的道路网中计算 出距起始点和目标点最近的 1 个乘车节点，将该点作 为 1 个必经点，再计算过此 3 点的最短路径，即计算 经过 n 个乘车节点（n=2）后，到达目标点的最短路径 Length [n]，对学生数的计算方法参照步骤二、三。
[3] 刘志宏. 土地信息系统建立的理论与实践[D]. 西安：长安大 学，2005
[4] 李琦. 构建土地利用数据库系统的探讨[J]. 科学论坛，2007: 52
[5] 钱乐祥，余明全. 土地信息系统的几个基本问题[J]. 测绘通 报，1999(10): 18-20
[6] 李沙. 土地利用总体规划公众参与机制研究[D]. 西安：西北 农 林 科 技 大 学 ，2008
68
地理空间信息
第 ９ 卷第 ４ 期
步骤 3：计算起始点到学校的最短路径长度及经过 的节点，按顺序遍历全部节点（包括普通道路节点和 乘车节点），如果是乘车节点的话，先计算经过的第一 个乘车节点的学生数，若该点的剩余学生数小于该车 次的剩余容量，那就将该点的学生数全部计入该车的 容量中，并把这些人数从该节点的学生数中减去，继 续计算下一个乘车节点；若经过一个乘车节点时，它 的学生数大于该车次的剩余容量，那么就将该点的学 生数减去剩余名额，并将这个人数计入该车的总数使 其满额，然后按照最短路径直至学校，重复步骤一，选 择新的起始点（如图 2 所示）。
在基础教育阶段，每个学校都有 1 个与之对应的 规划学区范围，而且学校基本都是位于这个学区的几 何中心位置。在本文中将校车路径的起始节点就应该 选择距离学校最远的乘车点开始，由远及近将沿途节 点的学生送至学校。
步骤 1：确定起始点，计算所有乘车节点距离代表 目标学校道路节点的最短路径长度值，按照算法从中 寻找该学区内距学校最远的乘车节点作为起始点。
4结语
地理信息系统的运用，能够提升土地管理部门的 工作效率。在引入 ArcGIS 平台前提下，土地利用规划 信息化管理可应用于规划用地整理、地类图斑查询与 统计、成果图表输出三方面。为早日实现信息化管理， 我国国土部门应从加强系统化、网络化开发建设，制 定统一的数据标准，重视公众参与环节着手建设。在 今后的土地利用规划管理过程中，信息化的广泛应用 是未来的趋势，统一式土地利用规划管理系统的构建 也是很重要的发展方向，这方面需要运用计算机语言 和服务器的支持，也是将来有待解决的课题。
第 一 作 者 简 介 ：姚 远 ，硕 士 ，主 要 研 究 方 向 为 土 地 利 用 与 规 划 。
（上接第 68 页）
路径编号 1 15 21
表 1 最优路径结果 经过节点编号
(2:50),3,5,8,7,(12:10),15,22,29,36 (16:30),17Biblioteka Baidu(19:10),26,30,31,36 (33:30),35 ,36
其次，统一数据格式。由于计算机制图软件众多， 形 成 了 不 同 的 数 据 格 式，如 标 准 栅 格 图 像 （*.bmp、* . jpeg），ArcGIS 矢量图像（*.shp）、MapGIS 矢量图像 （*.wp、*.wl、*.wt）、AutoCAD 矢 量 图 像（*.dwg）、 MapInfo 矢量图像（*.map）等，因此若对数据编辑就 需要将其格式转换为相应 GIS 格式。但产生的弊端是， 造成信息丢失，转换过程占用大量时间，所以通用数 据格式为数据共享就带来了便利。 3.3 重视公众参与环节