基于幾何代數(shù)的多類型約束路網(wǎng)最優(yōu)路徑分析算法

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

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

0 引言

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

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

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

1 MCOP問題

1.1 問題定義

給定有向圖G＝（V，E），圖中每個節(jié)點、邊及路徑均包含主代價權(quán)重（Wm（Li），Li∈G）和約束權(quán)重（Wc（Li），Li∈G）。給定 m 個數(shù)值型路徑約束｛Wv1，…，Wvm｝及n個非數(shù)值型約束｛Wnv1，…，Wnvn｝，則 MCOP問題可以定義為：尋找一條從起始節(jié)點s到終止節(jié)點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問題的求解一方面要求最終獲得的路徑必須滿足所有的數(shù)值型與非數(shù)值型約束條件，同時還要求所獲得的路徑在滿足約束條件的所有可行路徑中，其主代價權(quán)重之和最小。

1.2 常見約束分類

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

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

2 MCOP中網(wǎng)絡圖的幾何代數(shù)表達

2.1 網(wǎng)絡圖的幾何代數(shù)編碼

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

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

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

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

2.2 網(wǎng)絡路徑延拓的矩陣外積方法

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

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

圖1 網(wǎng)絡圖的幾何代數(shù)表達Fig.1 The geometric algebra expression of networks

2.3 網(wǎng)絡圖中多重權(quán)重的嵌入與計算方法

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

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

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

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

3 MCOP問題的幾何代數(shù)統(tǒng)一算法

3.1 構(gòu)建思路

以幾何鄰接矩陣的自外積運算進行路徑延拓，并根據(jù)各類約束條件進行路徑篩選，進而構(gòu)建MCOP問題的幾何代數(shù)統(tǒng)一算法。

在網(wǎng)絡圖的幾何代數(shù)表達中，假設pij表示圖G中由節(jié)點i到節(jié)點j的路徑，由幾何代數(shù)框架下的鄰接矩陣表達及路徑生成規(guī)則易知：

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

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

3.2 不同約束的處理方法

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

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

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

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

3.3 多約束最優(yōu)路徑求解算法

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

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

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

4 案例分析

4.1 數(shù)據(jù)與實驗方案

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

4.2 實驗結(jié)果

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

5 結(jié)論與討論

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

圖3 系統(tǒng)界面及多約束最優(yōu)路徑求解結(jié)果Fig.3 The application interface and the results of MCOP problems

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

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

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

［2］ 任剛，王煒.轉(zhuǎn)向約束網(wǎng)絡中的對偶最短路徑樹原理及其原型算法［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網(wǎng)絡分析的圖簡化方法研究［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代數(shù)的混合型傳感器網(wǎng)絡覆蓋理論分析［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］ 胡勇，宗真，羅文，等.多條件約束應急疏散路徑分析的幾何代數(shù)方法［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.