李 勝 鄭成龍 劉 源 孫 強(qiáng) 邢宗義

(1. 南京理工大學(xué)自動化學(xué)院， 210094， 南京；2. 中車青島四方機(jī)車車輛股份有限公司， 266111， 青島∥第一作者， 副教授)

路徑規(guī)劃指的是在有障礙物的環(huán)境下根據(jù)某種指標(biāo)尋找一條從起點(diǎn)到目標(biāo)點(diǎn)的無碰撞路徑[1]。規(guī)劃的目的是為了找到起點(diǎn)和目標(biāo)點(diǎn)之間在時間上或距離上的最短路徑，目前主流的最短路徑算法包括Dijkstra算法、Floyd算法[2]、A*算法[3]等。

在地鐵站封閉復(fù)雜環(huán)境內(nèi)，常規(guī)的最短路徑規(guī)劃算法并不適用于視力障礙(以下簡稱“視障”)人群。視障人士在室內(nèi)環(huán)境下的移動不僅要考慮起點(diǎn)和目標(biāo)點(diǎn)之間距離的遠(yuǎn)近，循著路標(biāo)的無障礙路徑更為適用。因此，應(yīng)選取影響視障乘客通行能力的因素作為路徑權(quán)值的定量。

1 視障乘客通行影響因素及當(dāng)量表示

1.1 視障乘客通行影響因素

根據(jù)調(diào)查，影響視障乘客在地鐵站內(nèi)通行的因素如下：

1) 路徑的沿墻長度。在路徑權(quán)值計(jì)算中，路徑長度占據(jù)了重要地位。而對于視障乘客而言，沿墻行走是其傾向的行走方式，因此引入沿墻長度因子k1。

2) 路徑的非沿墻長度。非沿墻路徑也是決定視障乘客室內(nèi)路徑權(quán)值的重要因素，引入非沿墻長度因子k2。

3) 路徑中的直角彎。視障人群對角度沒有清晰的概念，他們更加傾向直角彎，故對其進(jìn)行量化，引入直角彎因子k3。

4) 路徑的非直角彎。路徑中的非直角彎對視障人群會產(chǎn)生負(fù)面的影響，因此同時引入非直角彎因子k4。

5) 路徑的樓扶梯。通過對盲校同學(xué)的調(diào)查，他們對樓扶梯的信任度很低，因而引入樓扶梯因子k5，使其區(qū)別于普通路徑。

6) 路徑的垂直電梯。無障礙電梯通常配有盲文提示，可認(rèn)為是視障乘客出行的不二選擇，因而在路徑選擇時將乘坐垂直電梯考慮在內(nèi)，引入垂直電梯因子k6。

7) 路徑的特殊地形和障礙物。地鐵站內(nèi)存在凸起、斜坡、凹陷等特殊地形，路徑上存在垃圾桶等障礙物，這些對視障乘客的行走不利。因此，引入路徑的障礙物和特殊地形因子k7。

1.2 視障乘客通行影響因子的當(dāng)量表示

上文歸納出影響視障乘客站內(nèi)通行的7個影響因子，但這些影響因子的單位不盡相同，因此要用當(dāng)量對其進(jìn)行表示，設(shè)矩陣P=[k1,k2,k3,k4,k5,k6,k7]，ni、nj分別為拓?fù)淠Ｐ椭械趇個、第j個頂點(diǎn)。a=(ni，nj)，a表示連接這2個頂點(diǎn)的邊。

1.2.1 沿墻長度和非沿墻長度的當(dāng)量表示

設(shè)d(ni，nj)為2個頂點(diǎn)ni、nj之間的歐幾里得距離。若邊a沿墻，則k1=d(ni，nj)；若邊a不沿墻，則k2=d(ni，nj)。

1.2.2 直角彎和非直角彎的當(dāng)量表示

若邊a連接的2個頂點(diǎn)方向與a的上一條路徑呈直角，則k3=2；若呈非直角，則k4=5。

1.2.3 樓扶梯、垂直電梯的當(dāng)量表示

若a的端點(diǎn)連接樓扶梯或垂直電梯，則給邊a賦予樓扶梯或電梯當(dāng)量。如果a邊有一端為路徑的終點(diǎn)，則k5=10，k6=4。如果a邊的端點(diǎn)均不是終點(diǎn)，則此樓扶梯或垂直電梯為站臺層和站廳層的連接點(diǎn)，為了避免站臺層和站廳層對樓扶梯和電梯的重復(fù)計(jì)算，此時的當(dāng)量應(yīng)減半，即k5=5，k6=2。

1.2.4 不規(guī)則地形和障礙物的當(dāng)量表示

給不規(guī)則地形的不規(guī)則程度賦值，如較平坦、較粗糙、上下坡分別賦予危險指數(shù)2、4、6。典型障礙物柱子、垃圾桶、自動售貨機(jī)、椅子的危險指數(shù)分別為5、2、4、3。由此可得：

(1)

式中：

m——邊a中不規(guī)則地形和障礙物的總個數(shù)；

rp——第p個對象的危險指數(shù)。

2 多目標(biāo)決策

計(jì)算最優(yōu)路徑，其本質(zhì)屬于多目標(biāo)決策問題。解決此類問題的主要方法有：① 直接加權(quán)法；② 間接加權(quán)法，包括 VEGA算法、有序比較與隨機(jī)比較法、概率向量選擇法[4]、層次分析法等；③ 基于Pareto最優(yōu)解集的方法。

本文的最優(yōu)路徑計(jì)算是個典型的最優(yōu)目標(biāo)決策問題，所選用的層次分析法[5]是在對決策問題的本質(zhì)、影響因子及其內(nèi)在關(guān)系等進(jìn)行深入分析的基礎(chǔ)上，使決策的思維過程數(shù)學(xué)化，為難于完全定量的復(fù)雜決策問題提供了簡便的決策方法。

2.1 層次分析法

采用層次分析法來解決視障乘客在地鐵站內(nèi)的路徑規(guī)劃計(jì)算，其具體步驟如下。

2.1.1 確定指標(biāo)

根據(jù)上文，確定視障乘客路徑選擇時的影響因子。

2.1.2 建立層次結(jié)構(gòu)模型

本文所建立的層次結(jié)構(gòu)模型如圖1所示,分為4個層次，其中：目標(biāo)層為路徑權(quán)值；指標(biāo)層Q為路徑長度和路徑不安全性；指標(biāo)層K為上述的7個影響因子；方案層則為具體的站內(nèi)走行路徑設(shè)計(jì)方案。

圖1 層次結(jié)構(gòu)模型Fig.1 Hierarchical structure model

2.1.3 構(gòu)造判斷矩陣

根據(jù)層次結(jié)構(gòu)模型，構(gòu)建目標(biāo)層、指標(biāo)層2個層次的判斷矩陣。判斷矩陣的值通過兩兩互比來設(shè)置。針對路徑的總加權(quán)目標(biāo)W，構(gòu)造出目標(biāo)層的判斷矩陣WQ：

(2)

同理，針對指標(biāo)層Q的q1、q2指標(biāo)，分別構(gòu)建出指標(biāo)層指標(biāo)Q的2個判斷矩陣Q1,K和Q2,K：

(3)

(4)

2.1.4 計(jì)算單排序權(quán)向量并做一致性檢驗(yàn)

根據(jù)正互反矩陣和一致性矩陣定義,WQ、Q1,K和Q2,K均為正互反矩陣，但WQ是一致性矩陣，Q1,K和Q2,K不是一致性矩陣，故需對這3個矩陣的不一致程度進(jìn)行衡量，定義一致性指標(biāo)IC的計(jì)算式為：

(5)

式中：

λmax——對應(yīng)于判斷矩陣的最大特征根；

n——判斷矩陣的階數(shù)。

如果IC=0，則說明該判斷矩陣完全一致；IC越接近0，則該判斷矩陣的一致性越高；IC的值越大，則該判斷矩陣的一致性越低。

引入隨機(jī)一致性指標(biāo)IR，用以衡量IC的大小。IR由隨機(jī)構(gòu)造的500個成對比較矩陣所得，其值可查表獲得，表1給出了判斷矩陣不同階數(shù)下所對應(yīng)的IR值。

表1 不同階數(shù)對應(yīng)的IR值Tab.1 IR values corresponding to different orders

定義一致性比率RC為:

RC=IC/IR

(6)

一般地，當(dāng)RC≤0.1時，認(rèn)為矩陣的不一致程度在合理范圍之內(nèi)，可用歸一化特征向量作為權(quán)向量；如果RC>0.1，則認(rèn)為矩陣的不一致程度過高，需要重新構(gòu)造成對比較矩陣。

2.1.4.1WQ單排序權(quán)向量與一致性檢驗(yàn)

WQ是一致性矩陣，設(shè)nQ為WQ的特征值，ωQ為WQ的單排序權(quán)向量，根據(jù)一致性和正互反矩陣性質(zhì)可得：

WQωQ=nQωQ

(7)

2.1.4.2Q1,K單排序權(quán)向量與一致性檢驗(yàn)

矩陣Q1,K不是一致性矩陣，需將Q1,K的列向量進(jìn)行量剛一化，由此可得：

(8)

設(shè)λQ1,K為Q1,K對應(yīng)的最大特征值，對Q1,K進(jìn)行一致性檢驗(yàn)，則有：

(9)

Q1,KωQ1,K=λQ1,KωQ1,K

(10)

(11)

計(jì)算可得IC=0.006 7。查表1可得，n=4時，IR=0.90。將IC、IR代入式(6)，可得RC=0.007 4。由于計(jì)算所得RC小于0.1，矩陣Q1,K通過一致性檢驗(yàn)。

2.1.4.3Q2,K單排序權(quán)向量與一致性檢驗(yàn)

同理，設(shè)ωQ2,KQ1,K對應(yīng)的最大特征值，將矩陣Q2,K列向量量綱一化, 按行進(jìn)行量綱一化后，可得ωQ2,K=[0.027 0.095 0.047 0.013 7 0.310 0.074 0.310]T。

對Q2,K做一致性檢驗(yàn)，可得RC=0.015<0.100，矩陣Q2,K通過一致性檢驗(yàn)。

2.1.5 層次總排序權(quán)重及其一致性檢驗(yàn)

層次總排序權(quán)重是指計(jì)算某一層次所有因素對于總目標(biāo)相對重要性的權(quán)值。設(shè)指標(biāo)層K的第x個因子kx對于總目標(biāo)的權(quán)值為wkx,Q，其計(jì)算式為：

(12)

式中：

wQ,l——指標(biāo)層Q中第l個元素對總目標(biāo)的單排序權(quán)值；

wKp,Ql——指標(biāo)層K層中第p個元素對指標(biāo)層Q中第l個元素的單排序權(quán)值；

m——自然數(shù)序列。

由式(12)可得層次總排序權(quán)重如表2所示。

表2 層次總排序權(quán)重Tab.2 Calculation result of the total ranking weight wKp,Ql of hierarchy

層次總排序權(quán)重的一致性檢驗(yàn)方法為：設(shè)wa為指標(biāo)層Q第y個元素qy對總目標(biāo)的單排序權(quán)值,設(shè)指標(biāo)層K第i個因子kx對qy的層次一致性指標(biāo)為ICq，隨機(jī)一致性為IRq，則層次總排序的一致性比率RC,z為：

(13)

當(dāng)RC,z<0.1時，認(rèn)為層次總排序通過一致性檢驗(yàn)。根據(jù)式(13)，可得RC,z=0.023 6，由此可認(rèn)為層次總排序通過一致性檢驗(yàn)。

綜上，指標(biāo)層Q的層次總排序權(quán)重wQ=[0.031 1 0.102 5 0.041 8 0.121 8 0.346 1 0.081 1 0.275 6]T。

2.2 綜合權(quán)值計(jì)算

設(shè)邊a的權(quán)值為w(ni,nj)，P為影響因子的當(dāng)量矩陣，則其計(jì)算式為：

w(ni,nj)=Pω

(14)

3 Dijkstra算法的計(jì)算步驟

大部分的位置服務(wù)系統(tǒng)都采用Dijkstra算法作為路徑規(guī)劃算法的基礎(chǔ)。該算法分為以下7個步驟。

步驟一：初始化。為頂點(diǎn)集N中的所有頂點(diǎn)g生成兩個屬性：d(g)和p(g)。其中：d(g)表示為從起點(diǎn)到g點(diǎn)的最短距離值；p(g)表示g點(diǎn)的父節(jié)點(diǎn)。若該頂點(diǎn)為起點(diǎn)，則此時的d(g)=0，p(g)等于起點(diǎn)本身。

步驟二：生成1個空集S，用于存放所有已求出的到起點(diǎn)最短距離的節(jié)點(diǎn)。

步驟三：生成1個集合T，將頂點(diǎn)集中的所有節(jié)點(diǎn)都放到T集合中。

步驟四：從T集合中找出d(g)最小值對應(yīng)的節(jié)點(diǎn)U，將U作為當(dāng)前的選中節(jié)點(diǎn)，將其從T中移出后，移入到S集合中。

步驟五：判斷U是不是目的地。如果U是目的地，則算法結(jié)束；如果不是，則繼續(xù)進(jìn)行步驟六。

步驟六：令d(V)表示從起點(diǎn)到V點(diǎn)的最短距離值，d(U)表示從起點(diǎn)到U點(diǎn)的最短距離值，p(V)表示V點(diǎn)的父節(jié)點(diǎn)，w(U,V)表示連接U、V兩個節(jié)點(diǎn)之間的權(quán)值。計(jì)算所有節(jié)點(diǎn)U指向的節(jié)點(diǎn)V的最短距離值。若d(V)>d(U)+w(U,V)，則d(V)=d(U)+w(U,V)，p(V)=U。

步驟七：本輪計(jì)算結(jié)束。返回步驟四，開始下一輪的計(jì)算。

4 仿真分析

本文對視障乘客在地鐵站內(nèi)的通行能力影響因素進(jìn)行分析，得到各邊的權(quán)值后，基于Dijkstra算法，將各邊的權(quán)值由距離變?yōu)楸疚乃蟮玫木C合權(quán)值，進(jìn)而得到相應(yīng)的最優(yōu)路徑。在地鐵站模型基礎(chǔ)上得到的站臺層部分路徑規(guī)劃結(jié)果如圖2所示。從圖2可看出，相對于最短路算法，綜合了路線距離和乘客安全性所得到的通行路徑更加符合視障乘客的行走習(xí)慣。

圖2 路徑規(guī)劃仿真結(jié)果Fig.2 Simulation results of path planning

5 結(jié)語

本文首先分析了在地鐵站內(nèi)影響視障乘客通行能力的因素，并給出各因素的當(dāng)量表達(dá)。在分析視障乘客通行影響因素的基礎(chǔ)上，提出了一種基于層次分析法的多目標(biāo)決策方法，該方法綜合了路徑距離和乘客安全性兩個指標(biāo)，得到了拓?fù)淠Ｐ透鱾€邊的權(quán)值。利用基于綜合權(quán)值的Dijkstra算法對最優(yōu)路徑進(jìn)行了驗(yàn)算，結(jié)果證明，該方法更適用于視力障礙人群。