基于幾何代數的多類型約束路網最優路徑分析算法

俞 肇 元，胡 勇，朱 曉 林，閭 國 年

（1.虛擬地理環境教育部重點實驗室／南京師范大學，江蘇 南京 210023；2.江蘇省大規模復雜系統數值模擬重點實驗室／南京師范大學，江蘇 南京 210023；3.南京師范大學計算機科學與技術學院，江蘇 南京 210023）

0 引言

網絡分析是交通路徑規劃的基石。LBS（Location Based Service）、地圖服務等快速發展對網絡分析算法提出了新的要求［1，2］。為滿足不同類型用戶的個性化分析需求，需要發展支撐多約束條件下網絡最優路徑分析的求解算法。多約束最優路徑問題（Multiple Constraints Optimal Path，MCOP）是在給定網絡拓撲結構與網絡中各節點／邊／路徑的各種約束條件下，尋找自起點到終點滿足所有約束條件的最優路徑［3］。常見的最短路徑問題、多約束路徑問題均可看做是多約束最優路徑的一個特例［4］。一般性MCOP問題是NP－難問題［4］。常見的最優路徑算法（如Dijkstra′s算法、Floyd算法、A＊算法等）多用于處理數值類約束，并要求各約束在路徑上的疊加為加性約束，隨著約束條件的增加，算法的數據結構與算法流程的復雜度也可能大幅增加［5］。近年來也發展了部分專門面向MCOP問題的路徑算法（如HMCOP［6］、EHMCOP方法［7］等），總體上在算法性能、算法的普適性與統一性及參數選取規則等方面仍有待進一步提升［3］。

從約束條件看，MCOP算法在考慮數值型、節點型及路徑結構等約束［8］的網絡分析算法對上述約束的處理方面缺乏統一性。不同算法在網絡表達、數據結構與路徑搜索策略上的不一致性，既導致了現有交通路徑規劃在體系結構上的復雜性，也難以有效提升面向復雜路徑規劃應用的適用性。因此，需要針對不同類型的約束進行多方法集成求解［9，10］，發展結構統一、可同時支撐不同類型約束、具有較好的并發與海量數據支持能力及可擴展性的多約束路徑規劃算法。從底層數學理論出發，構建網絡表達、關系計算與路徑搜索過程相統一的網絡表達與計算模型，進而實現對路徑約束的統一表達與綜合集成是實現多約束路徑規劃問題的可行途徑。

幾何代數以維度運算為核心，通過維度的縮進與拓展實現復雜的幾何與代數運算［11，12］。多重向量作為幾何代數的基本結構可以有效支撐多維度的統一表達，并實現幾何表達、對象結構、屬性特征的統一運算與表達［13，14］。基于幾何代數構建多約束路徑規劃算法，將可能突破現有路徑規劃算法的不足，在統一的分析框架下實現不同類型約束的路徑規劃分析的統一集成。本文擬從MCOP問題的數學定義及所需討論的主要約束類型出發，利用幾何基編碼構建網絡的幾何代數表達模型，并通過定義幾何代數框架下網絡節點、邊及路徑的幾何表達、路徑延拓與聯通關系計算以及權重的嵌入與計算方法，以此構建基于幾何代數的多約束路徑規劃算法。最后，將該算法應用于江蘇道路網絡數據來驗證其精確性、可能應用前景與改進途徑。

1 MCOP問題

1.1 問題定義

給定有向圖G＝（V，E），圖中每個節點、邊及路徑均包含主代價權重（Wm（Li），Li∈G）和約束權重（Wc（Li），Li∈G）。給定 m 個數值型路徑約束｛Wv1，…，Wvm｝及n個非數值型約束｛Wnv1，…，Wnvn｝，則 MCOP問題可以定義為：尋找一條從起始節點s到終止節點t之間的路徑p（s，t），同時滿足：

①對于任意i＝1，2，…，m，Wc（p（s，t））≤Wvi；

②對于任意j＝1，2，…，n，p（s，t）滿足條件Wnvj；

③Wm（p（s，t））是所有可行路徑中最小的。

上述定義顯示MCOP問題的求解一方面要求最終獲得的路徑必須滿足所有的數值型與非數值型約束條件，同時還要求所獲得的路徑在滿足約束條件的所有可行路徑中，其主代價權重之和最小。

1.2 常見約束分類

結合交通路徑規劃分析的一般需求及常見的網絡分析算法應用情況，對MCOP問題中常見的約束類型進行抽象與提煉。本文考慮的主要約束包括數值型約束、節點型約束和網絡結構型約束三類。其中數值型約束要求最終獲得路徑的約束指標必須在指定的數值范圍內，可表達為閾值型約束，即當特定的指標超過可接受的閾值（gmax）時，則該道路為非可行解；節點型約束主要包括必經節點約束及所經節點個數約束等；而結構型約束則主要通過路徑的封閉性（如折線型或環路）加以限定。

由于上述三類約束同時涉及網絡的拓撲結構、路徑搜索的結構信息及網絡路徑的數值和非數值型權重信息，很難在現有算法框架下進行統一求解。而基于幾何代數的網絡表達可為網絡節點、路徑、權重以及約束條件的集成表達與統一運算提供數學結構，并可通過統一的計算算子進行網絡路徑的篩選與運算，因而可在集成上述三類約束基礎上進行MCOP問題的統一求解。

2 MCOP中網絡圖的幾何代數表達

2.1 網絡圖的幾何代數編碼

網絡圖表達是路徑分析的前提，并直接影響網絡分析的算法結構與復雜度。Staples等提出利用冪鄰接矩陣（Nilpotent Adjacency Matrices）進行網絡表達，可生成與網絡拓撲結構相對應的代數系統［15］。任意經過n個節點的路徑可表達為由n個節點有序連接而成的n階對象，可與由n個向量外積構成的n－Blade相對應。因此可利用幾何基進行網絡節點編碼，根據網絡拓撲結構定義，生成相應的幾何代數運算空間，進而利用幾何代數運算實現網絡路徑的生成、遍歷與篩選。

對于包含n個節點的無向圖G（V，E），定義幾何代數空間En，利用其基向量｛e1，e2，…，en｝有序標定網絡各節點，根據節點間的連通性定義各幾何基之間的外積運算規則：

根據式（1）可定義基于網絡的幾何鄰接矩陣A。其中，第i行第j列元素Aij滿足：

在鄰接矩陣中的第i行第j列的元素可表征從節點i到節點j的通路。與傳統鄰接矩陣類似，矩陣的對角線元素為0，且有eij＝eji，i≠j。由于基于幾何代數的鄰接矩陣同時記錄了圖的連通關系和節點信息，并不滿足對稱性。

2.2 網絡路徑延拓的矩陣外積方法

在幾何代數中，外積可用于維度擴張，假定u＝（u1，u2，…，un），則有eu＝eu1∧eu2∧…∧eun，且有運算規則：

當u、v滿足正交性條件時，其結果為u＋v階的Blade。因此在基于幾何代數的網絡表達中，可以利用外積運算進行路徑延拓。在幾何鄰接矩陣中，任一節點對應的列向量和行向量分別代表了以該節點為起點和終點的路徑。因此利用幾何鄰接矩陣與自身的外積運算來獲得整個網絡上任意節點的路徑延拓的所有信息。圖1給出了一個簡單網絡的幾何代數編碼及基于外積的路徑延拓。在幾何鄰接矩陣自身外積結果矩陣的第i行第j列的元素記錄了從節點i到節點j的所有通路信息（多條通路間以“＋”連接）。可見，任意經過k個節點（實際路徑長度為k＋1，此處省略終點）的所有通路均可通過Ak直接獲得。此外，在上述運算中，當任意節點自身可以成環時，其對角線元素不為0，而是記錄了經過k點回到該點的一個環路信息，從而實現了對網絡中節點、路徑、環路等對象的統一表達與計算。基于幾何代數的網絡表達和路徑延拓可以統一整合節點個數、網絡結構為環路等特殊約束條件，并為上述條件約束下的最優路徑求解提供統一的數學結構與運算規則。

圖1 網絡圖的幾何代數表達Fig.1 The geometric algebra expression of networks

2.3 網絡圖中多重權重的嵌入與計算方法

網絡權重信息是MCOP問題求解的主要依據。網絡表達過程中權重的處理與集成對網絡路徑規劃分析算法的性能與效率具有重要影響。對于一般的MCOP問題，每條網絡邊上可能包括路徑長度、花費、路徑類型、通過性等多種類型的網絡權重。從分類上看，網絡權重信息可分為數值型權重和非數值型權重，由于非數值型權重可以通過網絡預處理過程中直接進行篩選［16］，本文僅考慮如何在基于幾何代數的網絡表達中對數值型權重進行表達與嵌入。

在基于幾何代數的網絡表達中，可以通過在表達網絡各元素的Blade前添加系數進行對象權重的表達。以式（1）為基礎，對各節點／路徑賦予權重信息，當ei和ej權重分別為m、n時，其外積表達為：

由于直接基于外積計算的權重在路徑延拓過程中表現為乘積關系，而常見的權重計算與約束集成多表現為加性（如時間、距離等），因此可引入指數變換：gij→exp（gij），將權重信息轉化為加和關系。此時，包含權重運算的網絡路徑延拓定義為：

由于式（4）與式（5）中權重與路徑聯通關系的計算是獨立的，均統一至外積運算中，且當任意網絡對象包含多個不同類型權重時亦成立。為此可構建面向MCOP問題的多權重網絡權重嵌入模型如下：

3 MCOP問題的幾何代數統一算法

3.1 構建思路

以幾何鄰接矩陣的自外積運算進行路徑延拓，并根據各類約束條件進行路徑篩選，進而構建MCOP問題的幾何代數統一算法。

在網絡圖的幾何代數表達中，假設pij表示圖G中由節點i到節點j的路徑，由幾何代數框架下的鄰接矩陣表達及路徑生成規則易知：

式中：pij包含由點i到點j的所有路徑。

鄰接矩陣的自外積可以直接獲得所有節點的后續路徑，其結果矩陣中包含有路徑節點數、路徑權重信息及路徑結構信息，且在基于幾何代數的路徑計算中，道路連通性判定與權重計算是統一的，因此可以在幾何鄰接矩陣的自外積過程中嵌入多重約束，并根據約束條件對pij中路徑進行篩選，獲得滿足所有約束的可行路徑，從中進一步尋找最優路徑。

3.2 不同約束的處理方法

在基于幾何代數的MCOP算法中，基于不同約束的路徑篩選是本算法的關鍵之一，對各類不同約束的處理方法分述如下：

（1）節點型約束處理：主要包括必須經過多少個節點（K－Path問題）和必須經過特定節點（Special－Node問題）兩類。對于必須經過的節點，通過定義取維度算子＜＞g，有＜pij＞g＝Ag（ij），表示取節點i到節點j中所有維度為g的路徑（實際為經過g＋1個節點的路徑）；而對于必須經過的特定節點的約束，可以通過對路徑下標進行搜索判定加以實現。

（2）數值型約束處理：不失一般性，數值型約束可以轉化為閾值型約束。為此可定義minw＜pij＞g表示以i為起點、j為終點的g階，權w最小代價路徑可以在路徑生成過程中，通過排序算法直接實現。當綜合考慮多個權重影響時，可通過預先設定最優函數f（w1，w1，…，wn）求解。加入權重的判斷，可得幾何代數框架下的g階多約束最優路徑的求解為：

（3）結構型約束處理：主要考慮路徑為開放型和環路兩種情況。在基于幾何鄰接矩陣的網絡分析算法中，k階環路直接對應于幾何鄰接矩陣對角線的路徑，因此僅需檢索對角線元素即可獲得，而非對角線元素均為開放型路徑。

3.3 多約束最優路徑求解算法

基于上述求解思路，建立基于幾何代數的多約束最優路徑算法流程（圖2）。其中A為基于幾何代數的網絡圖鄰接矩陣，通過鄰接矩陣的自外積運算實現任意節點向下一節點的路徑延拓，并在此過程中，同步實現權重關系的計算。在已知不同路徑的約束前提下，通過對可行路徑的篩選和對應結果矩陣行列元素的選取，獲得滿足起、終點條件的所有路徑，進而得到滿足約束條件的所有可行路徑。在所有可行路徑中，根據主導目標，通過簡單的權重排序方法即可獲得最優路徑。

圖2 基于幾何代數的多約束最優路徑求解算法Fig.2 The multi－constrained optimal path algorithm based on geometric algebra

與傳統的基于貪心思路的逐步分析算法相比，基于幾何代數鄰接表達的最短路徑求解流程更為清晰簡潔，且在所有約束的集成均是在路徑搜索過程中通過簡單的條件判斷加以實現的，因而可有效支撐大規模約束限制條件下最優路徑的分析。同時，算法求解過程實際還求出了所有滿足約束的可行路徑，賦予了本文算法很好的靈活性與可擴展性。

4 案例分析

4.1 數據與實驗方案

采用Visual C＋＋語言在CAUSTA系統［12］中構建基于幾何代數的MCOP分析模塊，開發基于幾何代數算子的多約束表達式構造與生成器（圖3a）。以江蘇省道路網絡數據為基礎，提取道路節點與路徑，模擬生成主要權重及約束數據。約束權重可分為數值型和分類型兩大類：其中數值型權重包括距離、花費、油耗等加性權重和車輛損耗等乘性權重；分類型權重包括道路類型（收費／不收費）、道路等級（高速／國道／省道／縣鄉道）和道路是否為受管制狀態等。對上述網絡進行幾何代數編碼等預處理后，進行多約束最優路徑實驗，分別測試在包含數值約束、節點型約束及結構型約束條件下算法的正確性。

4.2 實驗結果

不同約束條件下最優路徑的計算結果如圖3b－圖3d所示。將本文計算結果與拉格朗日松弛遍歷算法［17］、Yen′s K－Path算法［18］進行對比，對同時包含上述三類約束的最優路徑計算，由于缺乏現有算法進行對比驗證，采用人工判別的方法進行驗證，結果顯示本文方法可較好處理數值約束、節點型約束、結構型約束，并正確地計算了同時包含三種約束條件下的最優路徑。

5 結論與討論

MCOP算法是交通路徑規劃分析的重要算法。條件約束的多樣性與復雜性使得現有算法很難在統一的框架下進行問題求解。本文利用幾何代數的多維統一表達特性，構建了基于幾何代數的網絡統一表達，實現了網絡拓撲結構、權重信息及約束條件的統一表達與運算，進而利用幾何鄰接矩陣的自外積運算，實現了同時包含數值型約束、節點型約束及結構型約束條件的MCOP問題的統一求解。

圖3 系統界面及多約束最優路徑求解結果Fig.3 The application interface and the results of MCOP problems

基于幾何代數的鄰接矩陣表達將網絡圖的連通關系與節點信息統一表達，實現直接基于鄰接矩陣的路徑求解，在算法結構上，基于幾何代數的路徑判定與搜索具有統一的數學形式與幾何意義，可支撐不同類型的網絡分析算法的構建，從而可實現不同網絡分析算法結構上的統一。基于幾何代數的權重表達與嵌入方法可實現包含權重的路徑遍歷，權重的分離性可支撐權重或約束條件動態變動條件下路徑的快速檢索與分析。鄰接矩陣自外積運算的獨立性與統一性則為基于幾何代數的網絡分析算法的批量／并行計算提供了計算基礎。上述特征為發展支撐多條件、多約束、多用戶環境下大規模網絡分析算法提供了支撐。

在本文提出的MCOP算法的幾何代數統一算法中，對基于鄰接矩陣自外積路徑生成的優化是提升基于幾何代數網絡分析算法效率的關鍵。主要途徑有：1）構建適用于大規模網絡的通用數據模型與數據結構，如可采用稀疏矩陣等結構降低大規模網絡鄰接矩陣的時、空間占用；2）構建適用于鄰接矩陣自外積運算的快速并行算法，如通過引入矩陣分塊或預乘的方式加快路徑搜索速度；3）優化路徑生成過程中約束的集成與路徑篩選規則，在幾何鄰接矩陣自外積過程中進行路徑篩選可大幅降低算法的計算復雜度，并可支撐具有更高復雜性約束條件的網絡分析。

［1］ 于德新，楊薇，楊兆升.重大災害條件下基于GIS的最短路徑改進算法［J］.交通運輸工程學報，2011，11（4）：123－126.

［2］ 任剛，王煒.轉向約束網絡中的對偶最短路徑樹原理及其原型算法［J］.交通運輸工程學報，2008，8（4）：84－89.

［3］ GARROPPO R G，GIORDANO S，TAVANTI L.A survey on multi－constrained optimal path computation：Exact and approximate algorithms［J］.Computer Networks，2010，54：3081－3107.

［4］ 王晟，李樂民.一種改進的多約束最佳路徑算法研究［J］.電子學報，2004，32（4）：529－535.

［5］ RAITH A，EHRGOTT M.A comparison of solution strategies for biobjective shortest path problems［J］.Computers ＆ Operations Research，2009，36：1299－1331.

［6］ KORKMAZ T，KRUNZ M.Multi－constrained optimal path selection［A］.Proc of the IEEE INFOCOM 2001［C］.2001.834－843.

［7］ DELL′OLMO P，GENTILI M，SCOZZARI A.On finding dissimilar Pareto－Optimal paths［J］.European Journal of Operational Research，2005，162：70－82.

［8］ KWAN M P，LEE J.Emergency response after 9／11：The potential of real－time 3DGIS for quick emergency response in micro－spatial environments［J］.Computers，Environment and Ur－ban Systems，2005，29（2）：93－113.

［9］ 王杰臣，張偉，毛海城.GIS網絡分析的圖簡化方法研究［J］.測繪學報，2001，30（3）：263－268

［10］ 陸峰.最短路徑算法：分類體系與研究進展［J］.測繪學報，2001，30（3）：269－275.

［11］ YUAN L，YU Z，CHEN S，et al.CAUSTA：Clifford Algebra based unified spatio－temporal analysis［J］.Transactions in GIS，2010，14（S1）：59－83

［12］ 謝維信，曹文明，蒙山.基于Clifford代數的混合型傳感器網絡覆蓋理論分析［J］.中國科學（E輯），2007，37（8）：1018－1031

［13］ YUAN L，YU Z，LUO W，et al.A 3DGIS spatial data model based on conformal geometric algebra［J］.Sci.China Earth Sci.，2011，54：101－112.

［14］ YUAN L，Lü G，LUO W，et al.Geometric algebra method for multidimensionally－unified GIS computation［J］.Chinese Science Bulletin，2012，57（7）：802－811.

［15］ 胡勇，宗真，羅文，等.多條件約束應急疏散路徑分析的幾何代數方法［J］.地理與地理信息科學，2012，28（5）：47－50.

［16］ NEVE H D，MEGHEM P V.TAMCRA：A tunable accuracy multiple constraints routing algorithm［J］.Computer Communications，2000，23（11）：667－678.

［17］ CARLYL W M，WOOD，R K.Lagrangian relaxation and enumeration for solving constrained shortest－path problems［J］.Networks，2008，52（4）：256－270.

［18］ YEN J Y.Finding the K shortest loopless paths in a network［J］.Management Science，1971，17：712－716.