基于图论的最低风险水平线路方案自动搜索算法
2016-05-26李军徐志胜宋占峰杨峰吴恩琦
李军，徐志胜，宋占峰，杨峰，吴恩琦
(中南大学 土木工程学院，湖南 长沙 410075)
基于图论的最低风险水平线路方案自动搜索算法
李军，徐志胜，宋占峰，杨峰，吴恩琦
(中南大学 土木工程学院，湖南 长沙 410075)
摘要:以计算机图论为基础，研究线路方案拓扑关系，提出采用有向图网络表征线路局部方案间网络拓扑关系。借鉴图论最短路径问题思想，构建一种最低风险水平线路方案搜索算法，实现在高速公路线路风险全局最优的条件下，自动搜索出一条整体风险水平最低的推荐方案。
关键词：高速公路；线路方案优选；有向网络；最低风险水平；自动搜索算法
道路线路设计是道路设计的基本工作和核心内容。进行道路线路设计时，线路方案的优选在很大程度上决定新建道路的工程和后续运营费用。多年来，研究人员围绕线路方案计算机优选进行了许多卓有成效的研究。Shaw等[1]采用微分法进行线路优化，其缺点在于要求目标函数可微,具有局限性，并容易陷入局部最优。Kang等[2]将遗传算法与GIS进行集成运用于线路优化中，取得了良好的效果。高速公路设计起点和终点明确，比选方案或者是直接连接起点或终点，或者可以通过其他比选方案到达起点或终点[3]。直接连接起点或终点的方案称为贯通方案，其他方案则称局部比选方案。由于所有的比选方案都必须最终能够到达起点和终点，所以每一个比选方案都会同其他比选方案相互关联。线路方案的优选是在局部比选方案群中搜索最优整体推荐方案的过程，研究局部方案间的逻辑关系，可以用图来表征局部方案间的拓扑关系，线路方案的优选从其本质上讲就是一个图论的最短路径搜索问题。最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其他的度量，如费用、时间、线路风险水平等[4]。人们及社会在受益于高速公路所带来方便快捷的同时，对高速公路线路的安全度、风险水平提出了更高要求。由于高速公路建设周期长、规模大，各阶段面临的因素间关系复杂、不确定性高，使高速公路工程风险具有复杂、涉及面广等特点[5]。如何在已有风险评估结果的基础上，在众多局部比选方案中搜索出一条整体风险水平最低的推荐方案，不仅是风险评估工作的延续扩展，而且能将设计者从繁重单调的计算统计工作中解脱出来，致力于方案间的分析评比，对工程实际的方案组合、评估工作意义重大。笔者借鉴图论最短路径问题思想，基于Dijkstra算法提出一种最低风险水平线路方案搜索算法，实现在高速公路线路风险全局最优的条件下，自动搜索出一条整体风险水平最低的推荐方案。
1线路方案网络拓扑关系
在可行性研究阶段，线路起、终点间会设计出众多具有拓扑关系的局部比选方案。由于局部比选方案都必须最终能到达线路起终点，因此，在众多方案中，不同方案间不是孤立的，它们之间存在着相互关联。为研究方便，此处引入子方案和父方案、引出方案和接入方案的概念。父方案：与局部方案的起点相关联的方案。子方案：与局部方案的终点相关联的方案。接入方案：以局部方案某个位置作终点的方案。引出方案：以局部方案某个位置作起点的方案。引出点与接入点分别是引出方案、接入方案的设计起点和设计终点，定义其为路径控制点。研究发现，局部的线路方案间有一对多的关联，每个局部方案都可能存在着子方案和父方案，及多个接入方案和引出方案。以图1为例，方案1为连接起终点的贯通方案(定义为特殊的局部方案)，方案2，3，4，5和6为局部方案，共有6个局部方案，箭头方向为线路前进方向，Qi和Zi为方案i的起终点。以局部方案2为例，其父方案为方案1，子方案也为方案1，无引出方案，接入方案为方案3和4。
图1 方案关联Fig.1 Solution association
2线路有向网络图的构建
在线路众多局部方案中，不同方案间不是孤立的，它们之间存在着某种关联，即存在着某种二元关系。客观世界中的事物如果存在二元关系，就能通过图来记录此事物间的相互关联[6]。在深入研究线路局部方案间逻辑关系的基础上，提出采用有向网络图对局部方案间的拓扑关系进行表征。由于局部方案不是组成整体方案的最小单位，为了使计算机智能化地对线路方案进行有向网络图的构建，需要在路径控制点处对局部方案进行打断，将局部方案分解为更小单位的线元方案。线元方案是指局部方案的起点、终点与对应的路径控制点将该局部方案按里程增加方向分割成多段线路，局部方案的设计数据及其他属性信息按里程范围离散到各段线路中，每段线路称为一个线元方案。综上所述，线路方案构建网络拓扑关系的方法是：局部方案的起点、终点当作有向网络图中的节点，线元方案当作有向网络图中的弧段。以图1线路方案网为例，局部方案1中其被离散为Q→Q3，Q3→Q2，Q2→Q5，Q5→ Z2，Z2→ Z5和Z5→Z 6个线元方案。由其局部方案所构建的有向网络图如图2所示。
图2 线元方案有向网络图Fig.2 Directed network of line element solution
3最低风险水平线路方案自动搜索算法
3.1最短路径问题
最短路径问题是图论应用的经典问题，很多实际问题，如行程规划、物流规划、交通模拟、行车导航、社交网络以及基于位置的服务(Location-Based Service)等问题，都可以通过建立最短路径问题模型来进行求解[7]。所谓最短路问题，就是在赋权图N=(V,E,W)中指定的一对顶点间众多的路径中，搜索一条权和最小的路径。最短路径问题一般是在赋权图(网络图)中讨论，本质是网络流问题的一类特殊问题。根据求解对象的不同，最短路径问题一般可以分为4类[8]：
1)单源最短路径问题(Single Source Shortest Path Problem)。给定一个源点s，找出s到图中其他顶点vk∈V-{s}的最短路径。
2)点到点最短路径问题(Point-to-point Shortest Path Problem)。给定一个源点s和一个目的点e，找出一条s到e的最短路径。
3)多源点多汇点最短路径问题(Many-to-many Shortest Path Problem)。给定一个源点集合S⊆V和一个目的点集合E⊆V，找出S到E中每对顶点间的最短路径。
4)全源最短路径问题(All-pairs Shortest Path Problem)。找出图中每对顶点之间的最短路径。
本文所涉及的最低风险水平线路方案搜索问题，是在给定的线路起、终点间搜索出一条风险水平的整体推荐方案，其实质是点到点最短路径问题。Dijkstra算法是经典的点到点最短路径求解算法，是目前解决最短路径问题的理论基础[9-10]。笔者基于Dijkstra算法思想，构建了一种最低风险水平线路方案搜索算法(Automatic Searching Algorithm of Line，简称LAS算法)，实现在高速公路线路风险水平整体最优的条件下，自动搜索出一条整体风险水平最低的推荐方案。
3.2最低风险水平线路方案自动搜索算法流程
若各线元方案风险评估结果已知，并且已量化，假定以线路风险指数(HARI)对线元方案风险大小进行表征，HARI数值的大小表示线元方案风险水平的高低。
设有向网络图N=(V,E,W)。其中V为节点集合，E为弧段集合，对于任意有向弧段
d(ui,uj)=min{HARIi}
(1)
式中：i为两相邻节点间弧段编号。
为保证HARI全局最优，定义如下路径评价函数：
(2)
定义NS为节点状态(Node State)，NS={node,H,F,n,fnode,edge}。节点状态NS第1项(node)代表当前节点，第2项(H)代表当前节点对应的汇入最短边弧权(即HARI)，第3项(F)代表当前节点对应的当前最短路径评价函数值，第4项(n)代表当前最短路径弧度数，第5项(fnode)代表当前节点对应的父节点，第6项(edge)代表当前节点与其父节点间的最小弧权边。
I. 若NSx∈Ω，Ω=Ω-{NSx}；
II. 否则，Ω=Ω。
②否则：
I. 若NSx∈Ω，Ω=Ω-{NSx}；
II. 否则，Ω=Ω。
②否则：
3)否则，构建节点x的节点状态NSx：
①若NSx.node=Z，NSx加入Si中；
图3 LAS算法流程Fig.3 LAS algorithm flow
4实例分析
以图4线路方案网为例，对最低风险水平路线方案自动搜索算法(LAS算法)流程进行详细介绍，图5为其有向网络图N=(V,E,W)。其中V为节点集合，V={s,s2,s3,…,e}，E为弧段集合，W为弧权集合(HARI)，s和e为线路起终点。
图4 某线路方案网Fig.4 A route plan network
图5 某线路方案网有向网络图Fig.5 Directed network of a route plan
表1 搜索第1步
图6 搜索第1步示意Fig.6 Schematic diagram of the first step in search
i当前节点状态S2中节点状态S2中节点状态i=1NS1s2NS1s={s,0,0,0,null,null}NS1s2={s2,75,75,1,s,1}NS1s3={s3,74,74.5,2,s2,3}NS1s6={s6,60,67.5,2,s2,2}
图7 搜索第2步示意Fig.7 Schematic diagram of the second step in search
i当前节点状态S3中节点状态S3中节点状态i=2NS1s3NS1s6NS1s={s,0,0,0,null,null}NS1s2={s2,75,75,1,s,1}NS1s3={s3,74,74.5,2,s2,3}NS1s6={s6,60,67.5,2,s2,2}NS1e3={e3,63,70.7,3,s3,6}NS1s4={s4,66,71.7,3,s3,7}NS1e6={e6,58,64.3,3,s6,5}
图8 搜索第3步示意Fig.8 Schematic diagram of the third step in search
i当前节点状态S4中节点状态S4中节点状态i=3NS1e3NS1s4NS1e6NS1s={s,0,0,0,null,null}NS1s2={s2,75,75,1,s,1}NS1s3={s3,74,74.5,2,s2,3}NS1s6={s6,60,67.5,2,s2,2}NS1s4={s4,66,71.7,3,s3,7}NS1e6={e6,58,64.3,3,s6,5}NS1e3={e3,63,70.7,3,s3,6}NS1s5={s5,73,71.25,4,e3,11}NS2e2={e2,73,66.5,4,e6,8}
图9 搜索第4步示意Fig.9 Schematic diagram of the fourth step in search
i当前节点状态S5中节点状态S5中节点状态i=4NS1e3NS1s5NS2e2NS1s={s,0,0,0,null,null}NS1s2={s2,75,75,1,s,1}NS1s3={s3,74,74.5,2,s2,3}NS1s6={s6,60,67.5,2,s2,2}NS1s4={s4,66,71.7,3,s3,7}NS1e6={e6,58,64.3,3,s6,5}NS1e3={e3,63,70.7,3,s3,6}NS2e2={e2,73,66.5,4,e6,8}NS1s5={s5,73,71.25,4,e3,11}NS1e5={e5,55,68,5,s5,14}NS2e4={e4,69,67,5,e2,12}
图10 搜索第5步示意Fig.10 Schematic diagram of the fifth step in search
i当前节点状态S6中节点状态S6中节点状态i=5NS1s5NS1e5NS2e4NS1s={s,0,0,0,null,null}NS1s2={s2,75,75,1,s,1}NS1s3={s3,74,74.5,2,s2,3}NS1s6={s6,60,67.5,2,s2,2}NS1s4={s4,66,71.7,3,s3,7}NS1e6={e6,58,64.3,3,s6,5}NS1e3={e3,63,70.7,3,s3,6}NS2e2={e2,73,66.5,4,e6,8}NS1e={e,58,66.3,6,e5,16}NS1s5={s5,73,71.25,4,e3,11}NS2e5={e5,59,65.7,6,e4,15}NS2e4={e4,69,67,5,e2,12}
图11 搜索第6步示意Fig.11 Schematic diagram of the sixth step in search
i当前节点状态S6中节点状态S6中节点状态i=6NS1e5NS2e4NS1s={s,0,0,0,null,null}NS1s2={s2,75,75,1,s,1}NS1s3={s3,74,74.5,2,s2,3}NS1s6={s6,60,67.5,2,s2,2}NS1s4={s4,66,71.7,3,s3,7}NS1e6={e6,58,64.3,3,s6,5}NS1e3={e3,63,70.7,3,s3,6}NS2e2={e2,73,66.5,4,e6,8}NS2e={e,58,64.6,7,e5,16}NS1s5={s5,73,71.25,4,e3,11}NS2e4={e4,69,67,5,e2,12}NS2e5={e5,59,65.7,6,e4,15}
图12 搜索第7步示意Fig.12 Schematic diagram of the seventh step in search
i当前节点状态S8中节点状态S8中节点状态i=7NS1e5NS1s={s,0,0,0,null,null}NS1s2={s2,75,75,1,s,1}NS1s3={s3,74,74.5,2,s2,3}NS1s6={s6,60,67.5,2,s2,2}NS1s4={s4,66,71.7,3,s3,7}NS1e6={e6,58,64.3,3,s6,5}NS1e3={e3,63,70.7,3,s3,6}NS2e2={e2,73,66.5,4,e6,8}NS2e={e,58,64.6,7,e5,16}NS1s5={s5,73,71.25,4,e3,11}NS2e4={e4,69,67,5,e2,12}NS2e5={e5,59,65.7,6,e4,15}ϕ
图13 搜索第8步示意Fig.13 Schematic diagram of the eighth step in search
5结论
1)可行性研究阶段，线路起、终点间存在众多具有拓扑关系的局部比选方案，根据局部方案间的内在关联，研究线路方案拓扑关系，提出线路局部方案间网络拓扑关系有向图网络结构。为使计算机智能化地对线路方案进行有向网络图的构建，在路径控制点处对局部方案进行分隔，将局部方案分解为更小单位的线元方案。
2)将最短路径抽象为高速公路线路风险指数全局最优的度量，在构建的方案网络图中按高速公路线路风险指数为指标搜索线路起、终点间最优整体推荐方案，构建了一种最低风险水平线路方案搜索算法(LAS算法)，实现在高速公路线路风险指数(HARI)全局最优的条件下，线路起、终点间整体风险水平最优方案的有效搜索。其不仅是风险评估工作的延续扩展，而且能将设计者从繁重单调的计算统计工作中解脱出来，致力于方案间的分析比选。
参考文献：
[1] Shaw J F B, Howard B E. Expressway route optimization by OCP [J]. Journal of Transportation Engineering, 1982, 108(3): 227-243.
[2] Kang M, Jha M K, Schonfeld P. Applicability of highway alignment optimization models[J]. Transportation Research Part C: Emerging Technologies, 2012, 21(1): 257-286.
[3] 蒲浩，赵海峰，李伟. 基于动态规划的铁路三维空间智能选线方法[J]. 铁道科学与工程学报, 2012,9(2): 55-61.
PU Hao, ZHAO Haifeng, LI Wei. A 3D spatial intelligent route selection approach for railway alignments based on dynamic programming [J]. Journal of Railway Science and Engineering, 2012,9(2): 55-61.
[4] 张得志，钱奇，李双艳，等. 基于CO2排放的车辆路径优化模型及其算法研究[J]. 铁道科学与工程学报,2015,12(2):424-429.
ZHANG Dezhi，QIAN Qi，LI Shuangyan, et al. Research on an optimization model and its algorithm for vehicle routing problem based on CO2emission [J]. Journal of Railway Science and Engineering, 2015,12(2):424-429.
[5] 杨永顺，陈宝强，陈志明，等. 高速公路安全管理风险及对策措施研究[J]. 公路交通科技(应用技术版),2012(8): 2-4.
YANG Yongshun,CHEN Baoqiang,CHEN Zhiming, et al. Research on highway safety management risk and countermeasures [J]. Journal of Highway and Transportation Research and Development, 2012(8):2-4.
[6] 韦斯特. 图论导引[M].北京：机械工业出版社, 2006:474.
West. Introduction to graph theory[M]. Beijing: China Machine Press, 2006: 474.
[7] 蒋腾飞.网络最短路径问题与应用研究[D].南京：南京邮电大学, 2013.
JIANG Tengfei. Problems and application research of network shortest path[D]. Nanjing: Nanjing University of Posts and Telecomunications, 2013.
[8] 柴登峰，张登荣. 前N条最短路径问题的算法及应用[J]. 浙江大学学报(工学版),2002(5): 61-64.
CHAI Dengfeng , ZHANG Dengrong. Algorithm and its application to N shortest paths problem [J]. Journal of Zhejiang University ( Engineering Science), 2002(5):61-64.
[9] 张渭军，王华. 城市道路最短路径的Dijkstra算法优化[J]. 长安大学学报(自然科学版)，2005(6):62-65.
ZHANG Weijun, WANG Hua. Optimination dijkstra arithmetic for shortest path of urban traffic net [J]. Journal of Chang'an University(Natural Science Edition)，2005(6):62-65.
[10] 王树西，李安渝. Dijkstra算法中的多邻接点与多条最短路径问题[J]. 计算机科学，2014，41(6):217-224.
WANG Shuxi,LI Anyu. Multi-adjacent-vertexes and multi-shortest-paths problem of Dijkstra algorithm[J]. Computer Science, 2014，41(6):217-224.
Automatically algorithm for searching the lowestrisk level route scheme based on graph theory
LI Jun, XU Zhisheng, SONG Zhanfeng, YANG Feng, WU Enqi
(School of Civil Engineering, Central South University, Changsha 410075, China)
Abstract:Based on computer graph theory and the study of route plan's topology relationship, directed graph network is proposed to characterize the topology relationship between local scheme by the author. By using the shortest path problem of graph theory, a line search algorithm is proposed with the lowest risk level. In highway route risk of the global optimal conditions, it can automatically search out a recommendation with the lowest overall risk level.
Key words:highway; line scheme optimization; directed network; minimum risk level; automatic search algorithm
中图分类号：U412
文献标志码：A
文章编号：1672-7029(2016)04-0619-07
通讯作者：李军(1973-)，男，山东泰安人，副教授，从事公路建设项目风险评估理论与方法、线路精测技术研究；E-mail:609835905@qq.com
基金项目：国家自然科学基金资助项目(50708117) ; 交通运输建设科技项目(20113187851460)
收稿日期：2016-02-26
