基于Dijkstra算法的突发事件下列车最短径路的设计与实现

文/张海艳

1.引言

突发事件（比如：①自然灾害：暴风雨、洪涝、地震、暴雪、台风等导致的线路故障或车站能力不足②事故灾难导致的线路故障或车站能力不足③其他因素）的影响，对铁路运输造成了巨大的经济损失。研究突发事件下列车运行径路选择问题，有助于在突发事件下快速找出最短路径，及时完成铁路客货运输任务，减少突发事件给铁路运输带来的一系列损失。

2.Dijkstra算法求最短径路

2.1 Dijkstra算法基本思想

Dijkstra算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层扩展，直到扩展到终点为止[1]。Dijkstra算法计算一个点到其他各点最短路径时，其算法复杂度是O（n2），n为网络顶点数[2]。Dijkstra算法的基本思想：令P=（K，R）为一个带有权重的有向图（如图1所示），设集合K={0，1，2，3，4}，将集合K分成两个组别，第一组设为集合M，M={已求出最短路径的顶点}，初始时M中只有源节点，当每求出一条最短路径时，就将应的顶点加入集合M 中，直到全部的顶点都加入集合M 中；第二组是设为集合N，N={未确定最短路径的顶点}。在加入过程中，总保持从源节点K到M 中各顶点的最短路径长度不大于从源节点K到N中任意顶点间的最短路径长度。

图1 有向图

2.2 Dijkstra算法流程图

如图2所示。

图2 Dijkstra算法流程图

3.开发环境与系统功能设计

VisualStudio2012以Windows平台应用开发环境，它具有一套完整的开发工具集，支持多种语言，本文系统选择C#语言进行编程实现，在具备ArcGISEngine的开发环境条件下，结合VS工具箱中的ArcGIS的相关控件，实现界面的整体布局，在布局完之后，添加License控件获得ArcGISEngine的许可。通过所需要的功能分析，将所有的功能大体划分成了3个模块，分别是窗体创建、地图操作与工具栏和路径查询。对每个模块下面的具体功能又做了分支，对每个分支又进行了详细的阐述，得出最终的成果。窗体创建：包括地图导出和空间查询两个窗体。地图导出窗体涉及导出设置和导出路径两方面的内容，根据导出设置里的输出分辨率选择用户所需要的分辨率，选择导出路径，则可以将地图按照图片的格式输出。空间查询窗体主要根据地图上的图层要素，通过空间查询窗体，选择要查询的图层，查询结果将在主窗体高亮显示。地图操作与工具栏：地图操作主要包括鹰眼、制图的查看及右键菜单的实现。鹰眼功能主要实现用户可以在鹰眼窗体中控制主地图的显示范围，制图的查看功能为主窗体地图和制版地图的同步显示，为后续功能的完善做好铺垫，右键菜单主要针对图层，主要对图层进行移除、主地图缩放至图层及打开图层的属性表等功能。工具栏主要是对地图的操作，如对地图的放大缩小工具、测量工具等，本文对路径分析专门设计了路径分析工具条，点击路径显示图标，可以在地图上显示所查找的路径。地图的基本操作主要利用TOCControl和MapControl控件来实现。路径查询：包括最短路的查询、绕过故障线路和绕过故障车站的最短路的查询三方面的内容。在菜单栏里选择起始点按钮，在地图上标记起始点，进行最短路的查询，同样，在菜单栏里选择故障车站和故障线路按钮，可以得到绕过故障车站和故障线路的最短路径。在解决方案资源管理器中右击铁路应急处置系统，添加类，在添加新项里选择ArcGIS里的ExtendingArcObjects、选择BaseTool、新建AddNetBarriesTool类和AddNetStopsTool类，用于在地图上添加站点和障碍点[4]。同样，在添加新项里选择ArcGIS里的ExtendingArcObjects，选择BaseCommand，新建ShortPathSolveCommand类，用于最短路分析。

4.系统功能的设计与实现

4.1 属性数据库设计

本文系统是建立在ArcGISEngine平台上的，在ArcCatalog10.2里建立地理数据库：铁路.gdb，在数据库里建立要素数据集：各省省会及地级市、各省市界和铁路线路。

4.2 系统主要功能的实现

启动铁路应急处置系统，输入用户名、密码及相对应的验证码，即可进入系统主界面，点击径路分析模块，列车运行径路搜索与展示的主界面展示出来，主要由菜单栏、工具栏、鹰眼窗口、主地图窗口、图层控制等构成。系统的主要功能包括两方面的内容，一是对地图的一些基本操作，二是最短路径的实现。其中，最短路径的实现是本系统最为核心的功能，在拥有铁路地图数据资料的基础上，在主窗口界面实现最短路的搜索与展示。界面显示以神黄铁路（神池南—黄骅港）为例，实现最短路径的搜索与显示。点击菜单里的“起始点”按钮，添加路径的起始点，在地图显示光标，可以在地图上标注起始点，点击“求解路径”按钮，此时网络工具条转为可用状态，点击路径生成，则在地图上显示神黄铁路的最短路径，如图3所示。

图3 神池南—黄骅港铁路最短路径

添加障碍点“滴流磴”，查询路径，得到绕过“滴流磴”的最短路径如图4所示。

图4 绕过障碍点的最短路径

添加障碍线路，查询路径，得到绕过障碍线路的最短路径如图5所示。

图5 绕过障碍线路的最短路径

5.结论

本文详细阐述了Dijkstra算法的基本思想，实现了基于部分铁路网的最短路径的查询功能。对突发事件下列车运行径路的选择起到至关重要的作用。我国的铁路运输优先考虑最短路径，其次才是迂回径路和特定径路。本文系统的最短路径的查询包括两方面的内容，一是绕过障碍车站的最短路径查询，主要考虑了实际运输过程中车站运输能力不足或车站能力产生故障等情况；二是绕过障碍线路的最短路径的查询，线路障碍涉及突发事件下的水害断道、铁路交通事故导致的线路区间能力不足等实际情况。

引用出处

[1]成惠.铁路运输特定经由算法的研究与实现[D].中南大学，2007.

[2]李引珍，顾守淮.铁路网络两顶点间最短路径定向搜索算法[J].铁道学报，1997，19(2):25-27.