基于圖論的最低風險水平線路方案自動搜索算法

李軍，徐志勝，宋占峰，楊峰，吳恩琦

(中南大學 土木工程學院，湖南 長沙 410075)

?

基于圖論的最低風險水平線路方案自動搜索算法

李軍，徐志勝，宋占峰，楊峰，吳恩琦

(中南大學 土木工程學院，湖南 長沙 410075)

摘要:以計算機圖論為基礎，研究線路方案拓撲關系，提出采用有向圖網(wǎng)絡表征線路局部方案間網(wǎng)絡拓撲關系。借鑒圖論最短路徑問題思想，構建一種最低風險水平線路方案搜索算法，實現(xiàn)在高速公路線路風險全局最優(yōu)的條件下，自動搜索出一條整體風險水平最低的推薦方案。

關鍵詞：高速公路；線路方案優(yōu)選；有向網(wǎng)絡；最低風險水平；自動搜索算法

道路線路設計是道路設計的基本工作和核心內(nèi)容。進行道路線路設計時，線路方案的優(yōu)選在很大程度上決定新建道路的工程和后續(xù)運營費用。多年來，研究人員圍繞線路方案計算機優(yōu)選進行了許多卓有成效的研究。Shaw等[1]采用微分法進行線路優(yōu)化，其缺點在于要求目標函數(shù)可微,具有局限性，并容易陷入局部最優(yōu)。Kang等[2]將遺傳算法與GIS進行集成運用于線路優(yōu)化中，取得了良好的效果。高速公路設計起點和終點明確，比選方案或者是直接連接起點或終點，或者可以通過其他比選方案到達起點或終點[3]。直接連接起點或終點的方案稱為貫通方案，其他方案則稱局部比選方案。由于所有的比選方案都必須最終能夠到達起點和終點，所以每一個比選方案都會同其他比選方案相互關聯(lián)。線路方案的優(yōu)選是在局部比選方案群中搜索最優(yōu)整體推薦方案的過程，研究局部方案間的邏輯關系，可以用圖來表征局部方案間的拓撲關系，線路方案的優(yōu)選從其本質(zhì)上講就是一個圖論的最短路徑搜索問題。最短路徑不僅僅指一般地理意義上的距離最短，還可以引申到其他的度量，如費用、時間、線路風險水平等[4]。人們及社會在受益于高速公路所帶來方便快捷的同時，對高速公路線路的安全度、風險水平提出了更高要求。由于高速公路建設周期長、規(guī)模大，各階段面臨的因素間關系復雜、不確定性高，使高速公路工程風險具有復雜、涉及面廣等特點[5]。如何在已有風險評估結果的基礎上，在眾多局部比選方案中搜索出一條整體風險水平最低的推薦方案，不僅是風險評估工作的延續(xù)擴展，而且能將設計者從繁重單調(diào)的計算統(tǒng)計工作中解脫出來，致力于方案間的分析評比，對工程實際的方案組合、評估工作意義重大。筆者借鑒圖論最短路徑問題思想，基于Dijkstra算法提出一種最低風險水平線路方案搜索算法，實現(xiàn)在高速公路線路風險全局最優(yōu)的條件下，自動搜索出一條整體風險水平最低的推薦方案。

1線路方案網(wǎng)絡拓撲關系

在可行性研究階段，線路起、終點間會設計出眾多具有拓撲關系的局部比選方案。由于局部比選方案都必須最終能到達線路起終點，因此，在眾多方案中，不同方案間不是孤立的，它們之間存在著相互關聯(lián)。為研究方便，此處引入子方案和父方案、引出方案和接入方案的概念。父方案：與局部方案的起點相關聯(lián)的方案。子方案：與局部方案的終點相關聯(lián)的方案。接入方案：以局部方案某個位置作終點的方案。引出方案：以局部方案某個位置作起點的方案。引出點與接入點分別是引出方案、接入方案的設計起點和設計終點，定義其為路徑控制點。研究發(fā)現(xiàn)，局部的線路方案間有一對多的關聯(lián)，每個局部方案都可能存在著子方案和父方案，及多個接入方案和引出方案。以圖1為例，方案1為連接起終點的貫通方案(定義為特殊的局部方案)，方案2，3，4，5和6為局部方案，共有6個局部方案，箭頭方向為線路前進方向，Qi和Zi為方案i的起終點。以局部方案2為例，其父方案為方案1，子方案也為方案1，無引出方案，接入方案為方案3和4。

圖1　方案關聯(lián)Fig.1 Solution association

2線路有向網(wǎng)絡圖的構建

在線路眾多局部方案中，不同方案間不是孤立的，它們之間存在著某種關聯(lián)，即存在著某種二元關系?？陀^世界中的事物如果存在二元關系，就能通過圖來記錄此事物間的相互關聯(lián)[6]。在深入研究線路局部方案間邏輯關系的基礎上，提出采用有向網(wǎng)絡圖對局部方案間的拓撲關系進行表征。由于局部方案不是組成整體方案的最小單位，為了使計算機智能化地對線路方案進行有向網(wǎng)絡圖的構建，需要在路徑控制點處對局部方案進行打斷，將局部方案分解為更小單位的線元方案。線元方案是指局部方案的起點、終點與對應的路徑控制點將該局部方案按里程增加方向分割成多段線路，局部方案的設計數(shù)據(jù)及其他屬性信息按里程范圍離散到各段線路中，每段線路稱為一個線元方案。綜上所述，線路方案構建網(wǎng)絡拓撲關系的方法是：局部方案的起點、終點當作有向網(wǎng)絡圖中的節(jié)點，線元方案當作有向網(wǎng)絡圖中的弧段。以圖1線路方案網(wǎng)為例，局部方案1中其被離散為Q→Q3，Q3→Q2，Q2→Q5，Q5→ Z2，Z2→ Z5和Z5→Z 6個線元方案。由其局部方案所構建的有向網(wǎng)絡圖如圖2所示。

圖2　線元方案有向網(wǎng)絡圖Fig.2 Directed network of line element solution

3最低風險水平線路方案自動搜索算法

3.1最短路徑問題

最短路徑問題是圖論應用的經(jīng)典問題，很多實際問題，如行程規(guī)劃、物流規(guī)劃、交通模擬、行車導航、社交網(wǎng)絡以及基于位置的服務(Location-Based Service)等問題，都可以通過建立最短路徑問題模型來進行求解[7]。所謂最短路問題，就是在賦權圖N=(V,E,W)中指定的一對頂點間眾多的路徑中，搜索一條權和最小的路徑。最短路徑問題一般是在賦權圖(網(wǎng)絡圖)中討論，本質(zhì)是網(wǎng)絡流問題的一類特殊問題。根據(jù)求解對象的不同，最短路徑問題一般可以分為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)。找出圖中每對頂點之間的最短路徑。

本文所涉及的最低風險水平線路方案搜索問題，是在給定的線路起、終點間搜索出一條風險水平的整體推薦方案，其實質(zhì)是點到點最短路徑問題。Dijkstra算法是經(jīng)典的點到點最短路徑求解算法，是目前解決最短路徑問題的理論基礎[9-10]。筆者基于Dijkstra算法思想，構建了一種最低風險水平線路方案搜索算法(Automatic Searching Algorithm of Line，簡稱LAS算法)，實現(xiàn)在高速公路線路風險水平整體最優(yōu)的條件下，自動搜索出一條整體風險水平最低的推薦方案。

3.2最低風險水平線路方案自動搜索算法流程

若各線元方案風險評估結果已知，并且已量化，假定以線路風險指數(shù)(HARI)對線元方案風險大小進行表征，HARI數(shù)值的大小表示線元方案風險水平的高低。

設有向網(wǎng)絡圖N=(V,E,W)。其中V為節(jié)點集合，E為弧段集合，對于任意有向弧段∈N，均存在弧權HARI，W為弧權集合，Q和Z為線路起終點。由于線路有向網(wǎng)絡圖有可能為非簡單圖，兩相鄰節(jié)點間可能存在多條弧段，定義d(ui,uj)為相鄰節(jié)點間最短邊弧權。

d(ui,uj)=min{HARIi}

(1)

式中：i為兩相鄰節(jié)點間弧段編號。

為保證HARI全局最優(yōu)，定義如下路徑評價函數(shù)：

(2)

定義NS為節(jié)點狀態(tài)(Node State)，NS={node,H,F,n,fnode,edge}。節(jié)點狀態(tài)NS第1項(node)代表當前節(jié)點，第2項(H)代表當前節(jié)點對應的匯入最短邊弧權(即HARI)，第3項(F)代表當前節(jié)點對應的當前最短路徑評價函數(shù)值，第4項(n)代表當前最短路徑弧度數(shù)，第5項(fnode)代表當前節(jié)點對應的父節(jié)點，第6項(edge)代表當前節(jié)點與其父節(jié)點間的最小弧權邊。

I. 若NSx∈Ω，Ω=Ω-{NSx}；

II. 否則，Ω=Ω。

②否則：

I. 若NSx∈Ω，Ω=Ω-{NSx}；

II. 否則，Ω=Ω。

②否則：

3)否則，構建節(jié)點x的節(jié)點狀態(tài)NSx：

①若NSx.node=Z，NSx加入Si中；

圖3　LAS算法流程Fig.3 LAS algorithm flow

4實例分析

以圖4線路方案網(wǎng)為例，對最低風險水平路線方案自動搜索算法(LAS算法)流程進行詳細介紹，圖5為其有向網(wǎng)絡圖N=(V,E,W)。其中V為節(jié)點集合，V={s,s2,s3,…,e}，E為弧段集合，W為弧權集合(HARI)，s和e為線路起終點。

圖4　某線路方案網(wǎng)Fig.4 A route plan network

圖5　某線路方案網(wǎng)有向網(wǎng)絡圖Fig.5 Directed network of a route plan

表1　搜索第1步

圖6　搜索第1步示意Fig.6 Schematic diagram of the first step in search

i當前節(jié)點狀態(tài)S2中節(jié)點狀態(tài)S2中節(jié)點狀態(tài)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當前節(jié)點狀態(tài)S3中節(jié)點狀態(tài)S3中節(jié)點狀態(tài)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當前節(jié)點狀態(tài)S4中節(jié)點狀態(tài)S4中節(jié)點狀態(tài)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當前節(jié)點狀態(tài)S5中節(jié)點狀態(tài)S5中節(jié)點狀態(tài)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當前節(jié)點狀態(tài)S6中節(jié)點狀態(tài)S6中節(jié)點狀態(tài)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當前節(jié)點狀態(tài)S6中節(jié)點狀態(tài)S6中節(jié)點狀態(tài)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當前節(jié)點狀態(tài)S8中節(jié)點狀態(tài)S8中節(jié)點狀態(tài)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)可行性研究階段，線路起、終點間存在眾多具有拓撲關系的局部比選方案，根據(jù)局部方案間的內(nèi)在關聯(lián)，研究線路方案拓撲關系，提出線路局部方案間網(wǎng)絡拓撲關系有向圖網(wǎng)絡結構。為使計算機智能化地對線路方案進行有向網(wǎng)絡圖的構建，在路徑控制點處對局部方案進行分隔，將局部方案分解為更小單位的線元方案。

2)將最短路徑抽象為高速公路線路風險指數(shù)全局最優(yōu)的度量，在構建的方案網(wǎng)絡圖中按高速公路線路風險指數(shù)為指標搜索線路起、終點間最優(yōu)整體推薦方案，構建了一種最低風險水平線路方案搜索算法(LAS算法)，實現(xiàn)在高速公路線路風險指數(shù)(HARI)全局最優(yōu)的條件下，線路起、終點間整體風險水平最優(yōu)方案的有效搜索。其不僅是風險評估工作的延續(xù)擴展，而且能將設計者從繁重單調(diào)的計算統(tǒng)計工作中解脫出來，致力于方案間的分析比選。

參考文獻：

[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] 蒲浩，趙海峰，李偉. 基于動態(tài)規(guī)劃的鐵路三維空間智能選線方法[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排放的車輛路徑優(yōu)化模型及其算法研究[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].北京：機械工業(yè)出版社, 2006:474.

West. Introduction to graph theory[M]. Beijing: China Machine Press, 2006: 474.

[7] 蔣騰飛.網(wǎng)絡最短路徑問題與應用研究[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算法優(yōu)化[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