交通运输最短路径分析系统的设计与实现

张晓楠，任志国，曹一冰，刘瑞雪

(1.信息工程大学 地理空间信息学院，河南 郑州 450052；2.中华测绘服务公司，北京 100088；3.78155部队，四川 成都 610036)

交通运输最短路径分析系统的设计与实现

张晓楠1，任志国2，曹一冰1，刘瑞雪3

(1.信息工程大学 地理空间信息学院，河南 郑州 450052；2.中华测绘服务公司，北京 100088；3.78155部队，四川 成都 610036)

针对目前交通运输效力发挥不足的问题，研究道路网络模型构建和道路数据库设计，探讨分析交通运输最短路径分析流程，基于Dijkstra算法的基本原理，设计实现交通运输最短路径分析系统，从而优化运输资源配置，实现高质高效的交通运输。

交通运输;道路网络;GIS;最短路径分析

当前，我国城市交通的发展速度已经远远滞后于经济增长的速度，交通运输问题涉及和影响到人们生活和经济的各个方面，成为社会发展中亟待解决的重要问题。但是，交通运输业的发展需要聚集大量的财力物力，考虑到我国目前尚处于资金短缺这一实际情况，大规模建设新的交通干线，并不实际[1]。因此，有必要立足现有的交通资源，进行运输的合理规划与有效配置，最大限度地发挥运输效力。为了达到这一目标，最短路径的分析与获取就成为关键所在。这里所指的最短路径，不仅仅局限于空间意义上的最短距离，还引申为诸如最短时间、最短线路容量、最低耗费成本等度量。如何才能使得运输货物经历最短时间、以最短路径到达指定的目的地，是交通运输最短路径分析的最终目标。本文结合GIS技术，在.NET环境下进行GIS产品的二次开发，实现网络化环境下交通运输的最短路径分析，用户还可以根据任务的实际情况，查询和搜索相应的运输路线。

1 道路网络模型构建

1.1 道路网络模型

城市道路交通网错综复杂，纵横交织，由成百上千条道路相连、相交构成。每条道路的地理位置以及道路与道路之间的相互位置关系，都会影响交通运输网的结构和组成。仅以道路相连的情况来看，一条道路可能就与若干条道路相连，且相连的模式多种多样。为此，本文抽取交通网中道路之间的交叉口作为单独分析的对象，然后使用交叉口作为节点将每条道路分割成段，从而避免道路之间复杂多样的拓扑关系，最终构建基于路段连接的道路网络模型。基于该模型，整个交通网络图由路口交叉节点和路段构成，交叉口节点构成网络的节点，道路路段构成网络的弧。

如图1所示，路网中的节点为道路交叉口，路网中的弧段为与道路交叉口相连的若干条道路路段，二者共同组成了道路交通网的结构。

图1 道路网络模型

实施道路的最短路径分析，离不开道路交通要素之间的拓扑关系。如图2所示，本文定义了如下拓扑关系来表征GIS地理要素之间的连通性、相邻性等空间关系。基于该空间关系，各个道路路段之间的连通以及道路交叉口节点与道路路段的关联得以充分地表达，最短路径的查找与分析得以顺利实施。

图2 道路网的拓扑关系描述

1.2 道路数据库设计

城市道路交通网主要由道路路段和路段交叉口两类要素构成，其中道路路段要素包括：平均车速、双行、单行、禁行和分时通行等，有快速路、主干道、次干道和支路之分；而路段交叉口要素则包括：等候时间、禁止左转、禁止右转等参数[2]。针对道路交通网的复杂性，本文采用道路信息表(见表1)和交叉口信息表(见表2)来描述城市交通道路面貌，以满足系统进行路径分析的需要。

表1 道路信息表

表2 交叉口信息表

1.3 最短路径分析

最短路径分析问题作为图论问题中的典范，已被应用于计算机科学、运筹学、地理信息系统等众多学科领域。其根本目的是研究如何安排及筹划一项网络工程并且使其运行的效果达到最佳[3]。最短路径问题最直观的应用就是在地理信息科学领域，比如制定一项运输方案，如何使得从A地到B地的运输费用最低、时间最短、路径最优。针对最短路径问题，求解的算法有很多，基本分为静态最短路径算法和动态最短路径算法两类。其中，静态最短路径算法主要应用于外界环境条件保持不变的情况，典型的有Dijkstra算法和A*算法等。动态最短路径算法主要应用于外界环境不断发生变化的情况，最为典型的有D*算法。交通运输区域确定的情况下，可以根据运输的具体要求来确定所求路径的目的点，因此可以归结为单源最短路径分析问题。Dijkstra算法[4]是典型的单源最短路径算法，按照路径长度递增生成各个节点，计算任意一个节点到其他所有节点的最短路径。本文基于Dijkstra算法进行系统的开发实践。

2 交通运输最短路径分析系统设计

2.1 系统总体架构

为实现交通运输指挥的灵活和信息的共享，交通运输最短路径分析系统的总体架构如图3所示。

图3 系统总体架构

系统分为客户端和服务器端两部分，客户端使用web浏览器作为用户界面，服务器端包括web服务器和GIS服务器，web服务器负责与客户端之间的通信，GIS服务器负责提供最短路径分析功能。客户端发送分析请求给web服务器，web服务器通过代理对象将请求发送至GIS服务器，GIS服务器运行业务逻辑和控制数据访问，将最终的GIS分析结果返回到客户端浏览器。其中，地理数据库负责存储管理基础地理数据，道路数据库负责存储管理交通运输方面的业务数据(道路、道路交叉口等)。

2.2 系统功能结构

根据交通运输路径分析功能需求目标，整个系统分为数据处理、地图控制、路径规划和交通应用4个功能模块。系统的总体功能结构如图4所示。

图4 系统功能结构

1)数据处理：该模块包括数据入库、数据拓扑、数据查询和数据编辑等几个子模块。能够将空间相关信息和道路交通数据导入到数据库中，并进行有效地组织，完成数据的拓扑、查询和编辑操作。

2)地图控制：该模块实现窗口的显示控制和图层的相关操作，能够对图层图形进行平移、缩放、显示控制等处理，并完成图层的输出打印。

3)路径规划：该模块是整个系统的核心模块。针对具体的运输任务和实际的应用需求，划分执行任务的运输单位，设置每个运输单位的相关属性，比如：运输车队的车辆总数、车辆的最大载重、最大高度、车队的行进速度等。在地图上勾选必经的相关节点(起始点、装载点、卸载点、终止点等)并执行最短路径分析，输出最终的分析结果并生成报表。

4)交通应用：该模块通过对交通运输属性信息、运力统计情况和运输单位情况进行交互式查询，选中所需的图层，根据用户需要选择相应的字段，最终以统计图表和word报表的形式输出结果。

2.3 交通运输最短路径分析流程

在交通运输的过程中，为了提高送运效率，降低送运成本，需要通过计算起始点与目的点之间的最短路径来决定最佳的运输路线。对于运输单位来说，应该按照任务的要求，沿最短路径前往运送地点。交通运输最短路径分析的流程如图5所示。

根据实际应用需求，接受运输任务，明确划分运输单位，设置运输任务及每一运输单位的相关属性，具体包括车队的车辆总数、人员总数、车辆的最大载重量、最大高度、车队行进速度等，在地图上勾选必经的相关节点(起始点、装载点、卸载点、终止点等)并执行最短路径分析，输出最终的分析结果并生成报表、输出报告。

图5 交通运输最短路径分析流程

3 交通运输最短路径分析系统实现

根据系统设计方案，采用Microsoft Visual Studio.Net2008(.NET)为平台，基于某地理信息系统二次开发的工具软件包和应用开发包，实现交通运输最短路径分析系统。该系统中，最短路径分析组件采用动态链接库形式进行集成，系统工程中各个功能的类结构如图6所示。

图6 系统主要类结构图

图7 系统分析结果

图中，CDemo_ShortPathCommand类、CDemo_ShortPathCom类、CDemo_ShortPathTool类以及CDemo_ShortPathUIProcessor类，主要负责整个系统内部命令的处理；CShowNodeDlg类主要用于辅助选点窗口的设置及弹出，显示最短路径分析执行前所选节点的类型以及相关备注说明；CAnalyseDlg类用于最短路径分析窗口的显示及弹出，设置最短路径分析的相关参数、执行分析并显示最终的路线情况。图7为系统运行后，执行最短路径分析的可视化结果。

除此之外，系统设计时还采取了形态各异的符号加以标识类型各异的节点，形象直观地反映了执行最短路径分析时相关节点的类型，方便用户的查询和使用，如图8所示。

图8 不同节点符号说明

4 结束语

本文针对交通运输问题设计的最短路径分析系统，能够为运输单位提供最佳的运输处理方案和为客户提供实时货物送运情况的直观、可视化查询功能，充分发挥了GIS为交通运输服务的优势。事实上，交通运输最短路径分析涉及很多方面内容，在具体的应用实践中还需要进一步补充和优化。比如扩充算法中的权重值，包括距离、路面情况、交通条件等，实时跟踪与共享送运车辆的数据、轨迹回放等，都是下一步研究的重点。

[1]胡吉平,魏际刚,王红梅.基于GIS的交通运输规划[J].铁道学报,2000,22(4):12-15.

[2]李旭华,王建中.基于数据库的城市道路中最短路径搜索[J].电脑开发与应用,2005,18(1):14-21.

[3]邬伦,刘瑜,张晶,等.地理信息系统——原理、方法和应用[M].北京:科学出版社,2001.

[4]司连法,王文静.快速Dijkstra最短路径优化算法的实现[J].测绘通报,2005(8):15-18.

[5]JAMES W COOPER.C#Design Patterns[M].BeiJing:Publishing House of Electronics Industry,2003.

[6]华一新,吴升,赵军喜.地理信息系统原理与技术[M].北京:解放军出版社,2001.

[7]周长发.C#面向对象编程[M].北京:电子工业出版社,2006.

[责任编辑：刘文霞]

Designandimplementationofthetransportationshortestpathanalysissystem

ZHANG Xiao-nan1,REN Zhi-guo2,CAO Yi-bing1,LIU Rui-xue3

(1.School of Geographic Space Information，Information Engineering University，Zhengzhou 450052,China；2.Chinese Surveying and Mapping Service Corporation，Beijing 100088,China；3.Troops 78155，Chengdu 610036,China)

In view of the insufficient effectiveness of present transportation，it presents a preliminary study of road network model building and road database design，and discusses the process of transportation shortest path analysis.The transportation shortest path analysis system is designed and implemented based on the basic principle of Dijkstra algorithm in order to optimize the resource allocation and realize the high quality and efficiency transportation.

transportation;road network;GIS;shortest path analysis

2012-10-19

张晓楠(1986-)，男，博士研究生.

P208

：A

：1006-7949(2014)01-0025-06