基于GIS 的Dijkstra算法在运输系统的应用

于 斌

（武汉科技大学 城市学院，湖北 武汉 430083）

0 引言

随着定位导航技术、数据通信技术、自动控制技术、图像分析技术以及计算机网络和信息处理技术的快速发展，运输调度系统成为智能交通系统（ITS）的一个重要组成部分，常用的或者比较成熟的算法已经开始运用到实际运输调度系统中。

1 车辆路径问题概述

研究运输过程中车辆调度及路线安排的车辆路径问题VRP（Vehicle Routing Problem），是目前运筹学领域中的一个热点问题。VRP的一般描述是：对一系列集货点或送货点，组织适当的行车路线，使车辆有序地通过它们，在一定的约束条件，如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等情况下，达到一定的目标，如路程最短、费用最少、时间尽量少、使用车辆数尽量少等。其中，一般把最小的车辆数作为第一目标，而最低的行驶成本作为第二目标。

当不考虑时间要求，仅根据空间位置安排线路时，称为车辆路径问题（VRP），考虑时间要求安排线路时称为车辆调度问题（VSP），本文不作严格区分，统称为 VRP。现在VRP问题的研究主要集中于寻找一些高效的启发式算法。

2 GIS在交通领域的应用研究[1]

2.1 GIS和GPS

地理信息系统（GIS）[2-3]是一种空间性数据库管理系统，除了具备一般数据管理系统的数据输入、存储、查询和显示输出等基本功能外，能够进行空间查询和空间分析，用户可以根据需要建立一个应用分析模型，通过动态分析为评价、管理和决策服务。如一段公路，起迄点是它的地理特征，公路的造价、技术标准以及交通量等又具有统计数据特征。这些统计数据在纸介质地图上是难以描述的。

全球卫星定位系统（GPS）已广泛应用于城市交通管理领域，实现定位、导航、车辆监控以及调度管理等功能，并且与GIS技术集成，以实现不同的具体应用目标。目前，有关GIS和GPS的主要研究方向有数据采集技术和数据库维护技术。

交通决策要求GIS提供的数据范围在不断扩大，要求数据采集技术也不断发展，这些技术包括 GPS、视频技术、数码摄像技术、高清晰卫星图像、高清晰度扫描技术以及实时数据处理系统和传感器。这些实时数据来自气象雷达、车辆身份证条码、交通量计数器、路面温度传感器、ITS中的车辆导航系统等，所有这些技术均对GIS的设计实施产生影响。在进行数据库选择决策时，需要考虑采用大型的、一致性好的数据库，支持动态更新和维护。

2.2 GIS解决方案——Arc GIS

GIS系统软件的选择，直接影响数据库管理软件的选择，影响系统解决方案，也影响着系统建设周期和效益。Arc GIS[4]作为一个可伸缩的平台，无论是在桌面，在服务器，在数据组织使用，为个人用户也为群体用户提供优良的GIS服务。Arc GIS是基于一套由共享GIS组件组成的通用组件库实现的，这些组件被称为Arc Objects。使用Arc Objects建成的Arc GIS平台为开发者提供了一个应用开发的容器，包括桌面GIS（ArcGIS Desktop），嵌入式GIS（ArcGIS Engine）以及服务端GIS（ArcGIS Server）。

ArcGIS Server是一个发布企业级GIS应用程序的综合平台，支持的GIS软件可以集中管理并且支持多用户。ArcGIS Server包含了空间数据管理技术，用于通过多种关系型数据库来管理基于多用户和事务的地理数据库。ArcGIS Server提供了用于.NET和Java的应用程序开发框架（ADF），可以满足各种客户端的各种需求。ADF可以帮助用户创建和配置.NET或者Java桌面和网络应用，它们在GIS Server中运行时需要调用ArcObjects。

面向Java的ArcGIS Server ADF可以在微软的Windows Server和各种UNIX平台上运行，且支持很多网络服务器。另外，ArcGIS Server可以在单CPU或者多个CPU组成的分布式服务器系统上运行。

3 Dijkstra算法在运输调度系统中的应用

3.1 最短路径问题和Dijkstra算法

交通网络可以用带权图表示，带权图的最短路径问题即求两个顶点间长度最短的路径。其中，路径长度不是指路径上边数的总和，而是指路径上各边的权值总和。

Dijkstra算法是典型最短距离算法，用于计算一个节点到其他所有节点的最短路径。Dijkstra算法的基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。因此，用 Dijkstra求最短距离的图不能有负权边。

Dijkstra算法的主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止，结果是总能得出最短路径的最优解。

3.2 Dijkstra算法在运输调度系统中的应用

运输调度系统是集 GPS、GIS以及无线通信技术于一体的软、硬件综合系统。其主要由三部分组成：车载终端、无线数据链路和监控中心软件系统，可对移动车辆进行统一集中管理和实时监控调度指挥。安装在车辆上的GPS定位仪可以实时确定车辆的位置信息，通过车载无线数据通信系统，将信息传送到指挥监控中心，监控中心把车辆的位置显示在监控中心的电子地图上。监控中心系统软件利用获取的实时车辆信息和GIS交通道路信息，在交通网络中根据实时道路交通状况、交通流量、交通费用或途中所需的时间信息等，比照原有统计数据计算出各条交通道路路径的权值，使用Dijkstra算法，计算出车辆到达目的地的最短路径。车载无线数据通信系统还可将指挥中心的命令传送到移动车辆上，从而实现对运输车辆的管理控制和调度。

4 智能运输调度系统开发与应用

4.1 系统结构

基于上述ArcGIS软件和Dijkstra算法，用Java开发应用于大型物流企业的运输调度系统，完成 Unix系统下基于 Oracle的应用软件开发，全面支持物流企业多种运输模式的运行要求[5]。

系统分为硬件设备和软件系统两大部分。硬件设备包括车载信息终端、服务器、终端计算机、互联网、无线通信网等，如图1所示。软件系统分为业务管理、客户服务、车辆监控、车辆调度四个子系统。为了提高业务数据安全性，业务管理子系统和客户服务子系统采用B/S架构，将数据库服务器放于中心内网，将应用服务器放于中心外网，严格区分用户的操作权限及范围。此外，系统还采用在线用户监控、用户重要操作记录、用户同时登录次数限制、用户 Session定时失效等措施进一步加强系统安全性管理。

图1 智能运输系统硬件设备结构

4.2 系统数据流程

系统采用标准的三层结构，即页面显示、业务逻辑处理和数据库操作，数据流程如下页图2所示。系统前端页面请求使用统一的前端控制器进行转发，便于理清系统工作流程、权限管理和编码转换等。针对每一个业务流程中的对象建立模块，对每一个操作建立类，通过数据访问对象（DAO）获得数据库支持。在整个应用程序中DAO可以将底层数据访问逻辑与业务逻辑分离开来，在数据库和业务逻辑中间设置中间接口（Bean），便于升级为EJB。

图2 智能运输系统数据流程

4.3 系统布署和应用

系统有多种监控方式，已应用于某大型物流企业，客户可以方便地通过车载终端或者手机访问。系统已经覆盖中国大部分地区，目前已经开通多个区域，通过一年多的实际运行，系统稳定性、安全性等满足设计要求。系统的应用对促进物流企业的信息化、规范化管理，降低成本，提高效益起到了重要作用。

5 结语

运输调度系统建立起了车辆与系统用户之间迅速、准确、有效的信息传递通道。进一步的研究工作是在丰富数据和积累经验的基础上制定更合理的交通道路路径权值，和加强基于ArcGIS的开发应用。

[1]许焕明,王贵恩,孙永林.内河船舶监督预警通信管理系统运行模式的研究[J].通信技术,2008,41(09):227-229.

[2]吴立新，史文中.地理信息系统原理与算法[M].北京：科学出版社，2003.

[3]张超.地理信息系统应用教程[M].北京：科学出版社，2007.

[4]吴秀芹，张洪岩,李瑞政,等.ArcGIS 9地理信息系统应用与实践(上下册)[M].北京：清华大学出版社，2007.

[5]Horst R, Pardalos P M, Thoai N V.全局优化引论[M].北京：清华大学出版社，2003.