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

俞 肇 元，胡 勇，朱 曉 林，閭 國(guó) 年

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

0 引言

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

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

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

1 MCOP問題

1.1 問題定義

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

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

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

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

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

1.2 常見約束分類

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 構(gòu)建思路

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

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

式中：pij包含由點(diǎn)i到點(diǎn)j的所有路徑。

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

3.2 不同約束的處理方法

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

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

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

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

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

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

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

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

4 案例分析

4.1 數(shù)據(jù)與實(shí)驗(yàn)方案

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

4.2 實(shí)驗(yàn)結(jié)果

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

5 結(jié)論與討論

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

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

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

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

［1］ 于德新，楊薇，楊兆升.重大災(zāi)害條件下基于GIS的最短路徑改進(jìn)算法［J］.交通運(yùn)輸工程學(xué)報(bào)，2011，11（4）：123－126.

［2］ 任剛，王煒.轉(zhuǎn)向約束網(wǎng)絡(luò)中的對(duì)偶最短路徑樹原理及其原型算法［J］.交通運(yùn)輸工程學(xué)報(bào)，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ìn)的多約束最佳路徑算法研究［J］.電子學(xué)報(bào)，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)絡(luò)分析的圖簡(jiǎn)化方法研究［J］.測(cè)繪學(xué)報(bào)，2001，30（3）：263－268

［10］ 陸峰.最短路徑算法：分類體系與研究進(jìn)展［J］.測(cè)繪學(xué)報(bào)，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)絡(luò)覆蓋理論分析［J］.中國(guó)科學(xué)（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］ 胡勇，宗真，羅文，等.多條件約束應(yīng)急疏散路徑分析的幾何代數(shù)方法［J］.地理與地理信息科學(xué)，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.