孫蘭會(huì) 成鋒 陸愈實(shí)

摘 要： 路徑規(guī)劃問題是地理信息系統(tǒng)（GIS）研究領(lǐng)域中的關(guān)鍵內(nèi)容之一，最短路徑的尋找更是熱點(diǎn)問題。在數(shù)據(jù)量較大時(shí)，傳統(tǒng)前K條最短路徑算法效率較低，且不能解決某些實(shí)際需求下規(guī)劃K條差異較大的路徑問題。在Dijkstra算法的基礎(chǔ)上，引入有利度與重復(fù)度的概念，通過對(duì)路徑結(jié)果重復(fù)度的檢測(cè)以及由有利度的改變所引起的圖的變化，循環(huán)尋找當(dāng)前圖中的最短路徑，從而實(shí)現(xiàn)了多條差異路徑的規(guī)劃。在上述算法的基礎(chǔ)上，對(duì)野外區(qū)域中帶狀區(qū)域的有利度及重復(fù)度進(jìn)行控制，解決了傳統(tǒng)前K條最短路徑算法難以滿足野外區(qū)域多條差異路徑規(guī)劃的問題。

關(guān)鍵詞： 路徑規(guī)劃； GIS； 有利度； 重復(fù)度

中圖分類號(hào)： TN911?34； TM417 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）05?0101?04

0 引 言

KSP問題是一個(gè)非常復(fù)雜的問題，而且根據(jù)不同的應(yīng)用場(chǎng)景以及具體需求要采用完全不同的算法來(lái)解決[1]。目前雖然存在多種KSP算法，但沒有一種算法能夠普遍適用于常規(guī)多條路徑規(guī)劃的問題，而且每種KSP算法都傾向于問題的某些方面對(duì)問題進(jìn)行解決[2]。

1 K優(yōu)路徑規(guī)劃算法及其擴(kuò)展

KSP問題是一個(gè)非常復(fù)雜的問題，根據(jù)不同的應(yīng)用場(chǎng)景以及具體的需求，KSP問題需要相應(yīng)的解決辦法?，F(xiàn)有的各種算法并不能很好地解決本文所面對(duì)的在大規(guī)模數(shù)據(jù)下尋找多條滿足一定差異性路徑的問題。因此，提出了大規(guī)模數(shù)據(jù)下滿足重復(fù)度要求的K優(yōu)路徑規(guī)劃算法（KPLR）[3]。

KPLR算法可有效解決在大規(guī)模數(shù)據(jù)下多條差異路徑規(guī)劃的問題。KPLR算法引入了有利度的概念，它是一種簡(jiǎn)單的啟發(fā)信息，是圖中每條邊的附加屬性，促使算法在每次循環(huán)中搜索有別于上次結(jié)果的其他路徑[4]。同時(shí)，KPLR算法引入了重復(fù)度的概念，它的使用保證了結(jié)果集的質(zhì)量。由于使用的啟發(fā)信息較為簡(jiǎn)單，算法得到的路徑結(jié)果犧牲了一定的精度，但大大提高了效率。考慮到在大規(guī)模數(shù)據(jù)下進(jìn)行路徑規(guī)劃的需求以及用戶注重路徑之間差異的特點(diǎn)，這樣的做法是較為合理的。由于需要解決的是實(shí)際中的問題，因此暫不考慮負(fù)邊值所帶來(lái)的問題[5]。

1.1 KPLR算法

使用path_current表示當(dāng)前分析路徑，path_current_vertex表示其頂點(diǎn)序列；path_current_edge表示其邊序列；path_result表示已經(jīng)得到的可用路徑結(jié)果集合；函數(shù)Repetition（path_current，path_result）計(jì)算當(dāng)前路徑與路徑結(jié)果集合中每條路徑的重復(fù)度是否滿足重復(fù)度限制系數(shù)[θ；][Kth]表示需要找到的路徑數(shù)量；Count表示在給定某[θ]值時(shí)算法可以進(jìn)行的循環(huán)次數(shù)上限；[Δθ]表示當(dāng)需要放寬重復(fù)度限制時(shí)的遞增步長(zhǎng)。KPLR算法如下：

（1） int k=0（用整數(shù)[k]記錄已經(jīng)得到的路徑數(shù)目）；int c=0（用整數(shù)[c]記錄在當(dāng)前[θ]值下算法已循環(huán)的次數(shù)）；path_result=[?。]

（2） 若[k>Kth]或者[θ≥1，]算法退出，否則轉(zhuǎn)步驟（3）。

（3） 若[c>Count，]置[c=0；]對(duì)所有[ei∈E，]重置[ei.u=]1；同時(shí)[θ=θ+Δθ，]即放寬重復(fù)度的限制。

（4） path_current=Dijkstra（G，s，e）；c=c+1。

（5） 按順序遍歷path_current_edge中所有的邊[ei，]降低其有利度，使[ei.u=ei.uα。]

（6） 若Repetition（path_current，path_result）為真，即對(duì)任意path∈path_result，Repetition（path，path_current）<[θ，]則當(dāng)前路徑滿足重復(fù)度要求，path_result=path_result∪{path_current}，同時(shí)[k=k+1，]轉(zhuǎn)步驟（2）；若Repetition（path_current，path_result）為假，無(wú)操作，直接轉(zhuǎn)步驟（2）。

在步驟（5）中，對(duì)當(dāng)前路徑path_current中所有邊降低其有利度，這樣就改變了當(dāng)前圖[G，]并降低了path_current在下次循環(huán)中的有利度，促使Dijkstra在新圖[G]中尋找有別于它的最短路徑。

在具體的實(shí)現(xiàn)過程中，可以通過有利度懲罰因子[α]以及重復(fù)度限制系數(shù)[θ]對(duì)算法進(jìn)行一定的控制。

1.2 擴(kuò)展的多點(diǎn)規(guī)劃KPLR算法

在實(shí)際應(yīng)用場(chǎng)景中的路徑規(guī)劃往往不僅限于兩點(diǎn)之間，經(jīng)常會(huì)有在多點(diǎn)之間規(guī)劃路線的需求，而上述KPLR算法無(wú)法滿足這種需求，因此需要將其擴(kuò)展，以便滿足這種需求[6]。

擴(kuò)展的KPLR算法（EKPLR）可用于進(jìn)行多點(diǎn)之間的K優(yōu)路徑規(guī)劃。在實(shí)際應(yīng)用中的多點(diǎn)規(guī)劃除起始點(diǎn)和終止點(diǎn)外，還有必經(jīng)點(diǎn)、禁止點(diǎn)以及危險(xiǎn)區(qū)域等[7]。

用ViaNode表示必經(jīng)點(diǎn)序列，F(xiàn)orbiddenNode表示禁止點(diǎn)集合，DangerousArea表示危險(xiǎn)區(qū)域集合，[vi∈]ForbiddenNode表示點(diǎn)[vi]為禁止點(diǎn)，[vi]∈DangerousArea表示點(diǎn)[vi]在危險(xiǎn)區(qū)域中。使用 Edge（[vi]）表示以點(diǎn)[vi]為某一端點(diǎn)的所有邊的集合。使用 ForbiddenEdge表示某一禁止點(diǎn)或位于危險(xiǎn)區(qū)域中的點(diǎn)[vi]為某一端點(diǎn)的所有邊的集合。其他符號(hào)同上文描述。帶必經(jīng)點(diǎn)、禁止點(diǎn)和危險(xiǎn)區(qū)域的KPLR算法如下：

（1） 對(duì)任意[vi∈V，]若[vi∈]ForbiddenNode或[vi∈]DangerousArea，則對(duì)所有[ei∈]Edge（[vi]），做[ei.u=1∞，]使其任意小，同時(shí)將[ei]加入ForbiddenEdge。

（2） 將起點(diǎn)[s]加入ViaNode開頭，終點(diǎn)[e]加入ViaNode末尾。

（3） int k=0（用整數(shù)[k]記錄已經(jīng)得到的路徑數(shù)目）； int c=0（用整數(shù)[c]記錄在當(dāng)前[θ]值下算法已循環(huán)的次數(shù)）； path_result=?。

（4） 若[k>Kth]或者θ≥1，算法退出，否則轉(zhuǎn)步驟（5）。

（5） 若[c>Count，]置[c=0；]對(duì)所有[ei∈E]且[ei∈]ForbiddenEdge，重置 [ei.u=1；]同時(shí)[θ=θ+Δθ，]即放寬重復(fù)度的限制。

（6） 對(duì)每?jī)蓚€(gè)相鄰必經(jīng)點(diǎn)[vi]和[vi+1，]其中[i=0，]1，…，|ViaNode|-2， pathi=Dijkstra（G，vi，vi+1）。

（7） path_current=[pathi；]c=c+1。

（8） 按順序遍歷path_current_edge中所有的邊[ei，]降低其有利度，使[ei.u=ei.uα。]

（9） 若Repetition（path_current，path_result）為真，即對(duì)任意path∈path_result，Repetition（path，path_current）<[θ，]則當(dāng)前路徑滿足重復(fù)度要求，path_result= path_result+path_current，同時(shí)[k=k+1，]轉(zhuǎn)步驟（4）；若Repetition（path_current，path_result）為假，無(wú)操作，直接轉(zhuǎn)步驟（4）。

在步驟（1）中，首先對(duì)禁止點(diǎn)和危險(xiǎn)區(qū)域進(jìn)行處理，對(duì)所有禁止點(diǎn)以及在危險(xiǎn)區(qū)域中的點(diǎn)，將其所屬的所有邊的有利度降低為任意小，從而其權(quán)值為任意大，也即標(biāo)記為該邊不可行。

在步驟（2）中，將起點(diǎn)和終點(diǎn)作為必經(jīng)點(diǎn)加入ViaNode可以簡(jiǎn)化程序代碼，同時(shí)仍保持程序的正確性。

在步驟（6）中，首先求出每?jī)蓚€(gè)相鄰必經(jīng)點(diǎn)之間的最短路徑段，然后在步驟（7）中將這些路徑段依次連接，從而得到最終的當(dāng)前路徑path_current。

2 野外區(qū)域路徑規(guī)劃

2.1 問題概述

野外區(qū)域是指沒有路網(wǎng)覆蓋的區(qū)域，由于野外區(qū)域并沒有路網(wǎng)覆蓋，而常規(guī)的路徑規(guī)劃算法是在從路網(wǎng)抽象而成的圖中利用點(diǎn)和線的關(guān)系進(jìn)行搜索的，因此常規(guī)算法無(wú)法直接應(yīng)用于野外區(qū)域的路徑規(guī)劃，在野外區(qū)域中進(jìn)行路徑規(guī)劃之前，需要根據(jù)所采用的算法對(duì)野外區(qū)域進(jìn)行一定的預(yù)處理[8]。

2.2 多路徑野外規(guī)劃

在對(duì)野外區(qū)域進(jìn)行網(wǎng)格化處理后，便可采取相應(yīng)的KSP算法對(duì)多路徑的野外區(qū)域規(guī)劃問題進(jìn)行求解。在選用相應(yīng)的算法時(shí)，結(jié)合野外區(qū)域的特點(diǎn)，要重點(diǎn)考慮網(wǎng)格的密度和路徑的重復(fù)程度。

提出的KPLR算法較適用于求解該問題，但需要結(jié)合野外區(qū)域的上述幾個(gè)特點(diǎn)對(duì)KPLR算法進(jìn)行如下改進(jìn)：

（1） 在算法的每次循環(huán)后，不僅僅是對(duì)本次循環(huán)所得臨時(shí)路徑進(jìn)行有利度的衰減，而是將衰減范圍擴(kuò)展到包括圖中所有以臨時(shí)路徑中的節(jié)點(diǎn)為某一端點(diǎn)的所有邊。

（2） 在計(jì)算路徑之間的重復(fù)程度時(shí)，也將被對(duì)比的路徑擴(kuò)展為包括其上各節(jié)點(diǎn)的所有相鄰8個(gè)節(jié)點(diǎn)，即將重復(fù)度的計(jì)算改為如下公式：

設(shè)path1和path2為兩條野外路徑，設(shè)Vertex（path1）為path1中所有節(jié)點(diǎn)與其中每個(gè)節(jié)點(diǎn)的所有8個(gè)相鄰節(jié)點(diǎn)組成的集合，則path2相對(duì)于path1的路徑重復(fù)度為path2與集合Vertex（path1）中相同節(jié)點(diǎn)的數(shù)目占path2中所有邊數(shù)的比重，記為YeWaiRepetition（path1，path2）：

YewaiRepetition（pathi，pathj）=|SameVertex（Vertex（pathi），pathj）[||pathj|]

其中|pathj|表示路徑pathj中節(jié)點(diǎn)的數(shù)目；集合SameEdge（Vertex（pathi），pathj）={[ei|ei]∈Vertex（pathi）∧[ei∈]pathj}，|SameEdge（Vertex（pathi），pathj）|表示該集合中元素的個(gè)數(shù)。

采用上述兩種改進(jìn)是為盡可能防止算法所得各結(jié)果路徑出現(xiàn)如圖1所示的情況，即各路徑雖不相同，但其均通過相同的一片區(qū)域，并無(wú)實(shí)際意義。

將結(jié)合野外區(qū)域的特點(diǎn)進(jìn)行上述改進(jìn)后的KPLR算法稱作WKPLR算法。因此，野外區(qū)域中的多路徑規(guī)劃問題的解決步驟大體如下：首先，根據(jù)選擇的所有必經(jīng)點(diǎn)（包含起始點(diǎn)和終止點(diǎn)）劃定一個(gè)矩形框，將該矩形框作為搜索范圍；其次，將該矩形框按步長(zhǎng)或按數(shù)量劃分為網(wǎng)格，并將該劃分好的網(wǎng)格拓?fù)錇橐粡垐D；最后，在該圖中應(yīng)用WKPLR算法進(jìn)行路徑規(guī)劃。

野外區(qū)域規(guī)劃WKPLR算法在對(duì)野外區(qū)域進(jìn)行上述預(yù)處理之后，就可以應(yīng)用WKPLR算法在處理得到的圖中進(jìn)行路徑規(guī)劃。使用path_current表示當(dāng)前分析路徑，path_current_vertex表示其頂點(diǎn)序列；path_current_edge表示其邊序列；path_result表示已經(jīng)得到的可用路徑結(jié)果集合；函數(shù)YewaiRepetition（path_current，path_result）計(jì)算當(dāng)前路徑與路徑結(jié)果集合中每條路徑的重復(fù)度是否滿足重復(fù)度限制系數(shù)[θ； Kth]表示需要找到的路徑數(shù)量；Count表示在給定某[θ]值時(shí)算法可以進(jìn)行的循環(huán)次數(shù)上限；[Δθ]表示當(dāng)需要放寬重復(fù)度限制時(shí)的遞增步長(zhǎng)。野外區(qū)域WKPLR算法如下：

（1） int k=0（用整數(shù)[k]記錄已經(jīng)得到的路徑數(shù)目）；int c=0（用整數(shù)c記錄在當(dāng)前[θ]值下算法已循環(huán)的次數(shù)）；path_result=?。

（2） 若[k>Kth]或者θ≥1，算法退出，否則轉(zhuǎn)步驟（3）。

（3） 若c>Count，置c=0；對(duì)所有ei∈E，重置[ei.u=1；]同時(shí)θ=θ+Δθ，即放寬重復(fù)度的限制。

（4） path_current=Dijkstra（G，s，e）；[c=c+1。]

（5） 按順序遍歷path_current_edge中所有的節(jié)點(diǎn)[vi，]降低以[vi]為某一端點(diǎn)的所有邊[eii]的有利度，即做[eii.u=][eii.uα。]

（6） 若YewaiRepetition（path_current，path_result）為真，即對(duì)任意path∈path_result，YewaiRepetition（path，path_current）<θ，則當(dāng)前路徑滿足重復(fù)度要求，path_result=path_result∪{path_current}，同時(shí)[k=k+1，]轉(zhuǎn)步驟（2）；若YewaiRepetition（Path_current，path_result）為假，無(wú)操作，直接轉(zhuǎn)步驟（2）。

上述WKPLR算法與KPLR算法基本相同，區(qū)別在于降低有利度的邊的范圍有所擴(kuò)展，以及計(jì)算重復(fù)度時(shí)有所改變。

3 實(shí)現(xiàn)設(shè)計(jì)及分析

基于GIS系統(tǒng)，以Microsoft VC++ 6.0為軟件開發(fā)平臺(tái)，實(shí)現(xiàn)了基于某地域道路信息網(wǎng)及野外區(qū)域的多條差異路徑選取功能。

3.1 KPLR對(duì)比實(shí)驗(yàn)

將該算法與候選消除邊算法（下稱對(duì)比算法）進(jìn)行對(duì)比實(shí)驗(yàn)，其為各前K條最短路徑算法中最精確的算法。對(duì)比算法所得數(shù)據(jù)作為參考來(lái)說(shuō)明本文算法在上述特定需求下的有效性。其中，以前5條路徑為例，且本文算法各系數(shù)設(shè)置為：[θ=0.5，][Δθ=0.1，][α=1.1。]

采用1[∶]50 000比例尺地圖，選取的起訖點(diǎn)直線距離約為200 km，采用Dijkstra算法找到的最短路徑長(zhǎng)度均為229.70 km。經(jīng)過對(duì)地圖數(shù)據(jù)處理后得到的圖包含201 070條邊，145 029個(gè)節(jié)點(diǎn)。圖2為本文算法得到的5條差異路徑，圖3為對(duì)比算法得到的前5條最短路徑。表1為兩種算法得到的路徑之間的重復(fù)度系數(shù)。表2為兩種算法得到的路徑長(zhǎng)度信息（單位：km）以及算法運(yùn)行時(shí)間（單位：ms）。

實(shí)驗(yàn)中數(shù)據(jù)量大幅增加，由103級(jí)增長(zhǎng)為105級(jí)。此時(shí)，本文算法所得路徑之間重復(fù)度最大值為0.286，小于重復(fù)度初始閾值0.5，對(duì)比算法重復(fù)度均在0.97以上。運(yùn)行時(shí)間方面，本文算法約為13 s，考慮到數(shù)據(jù)量之大，在實(shí)際應(yīng)用中，這是較為合理的時(shí)間；對(duì)比算法耗時(shí)約為85 min，僅作參考。

在路徑長(zhǎng)度方面，兩種算法得到的路徑1長(zhǎng)度相同，本文算法得到的剩余4條路徑長(zhǎng)度值也較為合理，其中路徑5與對(duì)比算法差值最大為13.43 km，占總長(zhǎng)度比重不到10%。

本次實(shí)驗(yàn)較好地體現(xiàn)了在大量數(shù)據(jù)下本文算法的有效性。在運(yùn)行時(shí)間上，本文算法有著絕對(duì)的優(yōu)勢(shì)，同時(shí)13 s的運(yùn)行時(shí)間在實(shí)際應(yīng)用中也是較合理的時(shí)間。在大幅度提升效率的同時(shí)，本文算法并未損失太多精度，同時(shí)考慮到對(duì)差異度的要求本身就是對(duì)一部分精度的放棄，因此本文算法較好地滿足了大量數(shù)據(jù)、一定重復(fù)度要求以及合理的運(yùn)行時(shí)間的綜合需求。

3.2 WKPLR對(duì)比實(shí)驗(yàn)

下面進(jìn)行野外區(qū)域中多條差異路徑規(guī)劃的對(duì)比實(shí)驗(yàn)，對(duì)比算法為針對(duì)野外區(qū)域進(jìn)行改進(jìn)的WKPLR算法與雙向搜索算法。實(shí)驗(yàn)以前3條路徑為例，且WKPLR算法各系數(shù)設(shè)置為：[θ=0.5，][Δθ=0.1，][α=1.1。]

采用1[∶]250 000比例尺地圖，選取的起訖點(diǎn)直線距離約為13 km。由于起訖點(diǎn)距離長(zhǎng)度較為合適，因此實(shí)現(xiàn)中網(wǎng)格劃分采用按步長(zhǎng)的方式，以保證路徑結(jié)果的精確程度。在具體實(shí)現(xiàn)中，步長(zhǎng)設(shè)置為200 m。圖4為WKPLR算法所得的3條差異路徑，圖5為對(duì)比算法所得的3條差異路徑。表3為兩種算法得到的路徑之間重復(fù)度系數(shù)。

由圖4，圖5可以看到WKPLR算法和對(duì)比算法在野外區(qū)域中規(guī)劃所得路徑的直觀效果。對(duì)比算法所得3條路徑全部通過同一條帶狀區(qū)域，且3條路線交織在一起，這樣的3條路線在實(shí)際應(yīng)用中其實(shí)可看做是同一條路線，并無(wú)太多實(shí)際應(yīng)用價(jià)值。而針對(duì)野外區(qū)域改進(jìn)后的WKPLR算法所得3條路徑能夠找到規(guī)劃區(qū)域中的3個(gè)差別較大的帶狀區(qū)域，從直觀效果來(lái)看，3條路線之間的差異度較大，效果也較好。

表3的數(shù)據(jù)也證實(shí)了這種差異性。由于在計(jì)算野外區(qū)域中路線的重復(fù)度時(shí)采用了改進(jìn)的帶狀區(qū)域重復(fù)度計(jì)算方式，不僅計(jì)算路線上的點(diǎn)，而且包括這些點(diǎn)的所有相鄰節(jié)點(diǎn)，也即被對(duì)比的點(diǎn)集合為路線所經(jīng)過的一條帶狀區(qū)域，因此對(duì)比算法的3條路徑之間差異度均在0.98以上，雖然它們經(jīng)過的點(diǎn)有一定的區(qū)別，但這些點(diǎn)均在同一帶狀區(qū)域中。而改進(jìn)的KPLR算法所得重復(fù)度均在0.5以下。因此，實(shí)驗(yàn)數(shù)據(jù)也進(jìn)一步證實(shí)了WKPLR算法在野外區(qū)域中進(jìn)行多條差異路徑規(guī)劃的有效性。

4 結(jié) 論

KSP問題是路徑規(guī)劃領(lǐng)域中的重點(diǎn)問題之一，也是近些年研究的熱點(diǎn)問題。KSP應(yīng)用場(chǎng)景非常廣泛，它是GIS中的重點(diǎn)研究?jī)?nèi)容，同時(shí)也應(yīng)用到路由選擇、圖像分割以及語(yǔ)音識(shí)別等領(lǐng)域。KSP問題是一個(gè)非常復(fù)雜的問題，針對(duì)不同的應(yīng)用場(chǎng)景及需求往往需要不同的解決辦法。

本文從實(shí)際應(yīng)用的角度，結(jié)合大規(guī)模數(shù)據(jù)以及路徑差異度的需求提出了KPLR算法及其野外區(qū)域版本W(wǎng)KPLR，其中KPLR算法是解決大規(guī)模數(shù)據(jù)下進(jìn)行多條差異路徑規(guī)劃問題的有效算法，同時(shí)，WKPLR算法結(jié)合野外區(qū)域的特點(diǎn)對(duì)KPLR算法進(jìn)行改進(jìn)，可有效解決野外區(qū)域中的多條差異路徑規(guī)劃問題，具有實(shí)際的應(yīng)用價(jià)值。

參考文獻(xiàn)

[1] 牛振東，師雪霖，葉成林.數(shù)字圖書館支撐技術(shù)領(lǐng)域標(biāo)準(zhǔn)規(guī)范的現(xiàn)狀和發(fā)展[J].我國(guó)數(shù)字圖書館標(biāo)準(zhǔn)規(guī)范建設(shè)，2003（7）：11?12.

[2] 蔡俊，李欽富，王金泉.一種Dijkstra優(yōu)化算法的研究與實(shí)現(xiàn)[J].信息技術(shù)，2011，35（4）：104?107.

[3] 王開義，趙春江，胥桂仙，等.GIS領(lǐng)域最短路徑搜索問題的一種高效實(shí)現(xiàn)[J].中國(guó)圖象圖形學(xué)報(bào)，2003，8（8）：951?956.

[4] 高松，陸峰.K則最短路徑算法效率與精度評(píng)估[J].中國(guó)圖象圖形學(xué)報(bào)，2009，14（8）：1677?1683.

[5] 柴登峰，張登榮.前N條最短路徑問題的算法及應(yīng)用[J].浙江大學(xué)學(xué)報(bào)，2002，36（5）：531?534.

[6] 袁紅濤，朱美正.K優(yōu)路徑的一種求解算法與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2004，40（6）：51?53.

[7] 馬炫，劉慶.求解K條最短路徑問題的混合蛙跳算法[J].信息與控制，2011，40（5）：614?618.

[8] 賈應(yīng)煒.云計(jì)算環(huán)境下的GIS軟件工程設(shè)計(jì)分析[J].現(xiàn)代電子技術(shù)，2015，38（17）：133?134.