城市路網最優路徑的不等式約束算法

楊 娟，陶葉青

（安徽省宿州學院 地球科學與工程學院，安徽 宿州 234000）

1 引言

城市經濟體的繁榮使得城市交通變得日益惡化，嚴重影響公眾出行與社會發展。如何在復雜的城市路網中選擇最優的行車路徑，成為學者關心和研究的熱點問題。國內外學者對城市路網最優路徑的算法進行討論與闡述，文獻 ［1－5］研究尋找時間與距離最短路徑算法，文獻 ［6－9］研究顧及轉向延誤、道路等級、人的認知角度等因素的最優路徑算法。規劃路徑的算法應解決公眾出行對選擇路徑的時間或距離等方面的要求，但是對時間、距離這樣的先驗信息在路徑規劃算法中往往不被顧及。傳統的最優路徑算法不能滿足人們對出行路徑時間或距離等方面同時的限制要求，只能在時間或距離某一方面找出最優的要素，這與公眾出行往往對時間與距離這兩個要素都有要求的情況相背。

不等式約束能使有效的先驗信息參與平差計算，較好地改善平差結果并提高解的精度。文獻［10－13］將不等式約束引入大地測量領域，并在變形檢驗、GPS數據處理、大地控制網的優化等方面取得了一定的應用成果。文獻 ［14－16］對應用Bayes、罰函數等方法對不等式約束的具體解法進行了研究。針對不等式約束在城市路網最優路徑規劃方面的應用沒有引起人們的關注。

根據傳統最優路徑算法存在的缺陷，應用不等式約束的基本思想，建立能同時顧及時間與距離要素的最優路徑模型，應用罰函數與零權和無限權的思想給出模型的算法，使得應用不等式約束的最優路徑規劃算法能夠滿足人們對出行路徑的要求。

2 不等式約束算法模型

最優路徑的模型眾多，多數是以轉向延誤、道路等級等客觀因素為參數建立的模型［6－8］。本文主要討論從滿足出行者對路徑選擇的時間與距離要求建立的路徑規劃模型問題，因此從人的認知角度建立路徑規劃基本模型［9］，解決規劃的路徑能夠滿足出行者主觀要求，更適合于本文所要解決的問題。應用浮動車建立的經驗知識模型為［9］

式中，RoutePlane（V，E）為根據路徑尋徑函數E［T（t），S，C（t）］確定的自主出行函數，S、T（t）、C（t）分別表示確定尋徑函數的出行距離、某時間段t內出行時間、某時間段t內路段通行等級三個因素。

路徑規劃模型的算法目標方程為［9］

式中，Wi（t）為城市路網中各路段的經驗知識值；T為路段平均通過時間；S為路段長度；C為道路經驗等級；N為路徑所包含的路段總數；Bt為時間經驗等級指數；Bs為距離經驗等級指數；為平均路權。

建立最優路徑模型與算法的最終目的是尋找起點至終點間一條平均路權數值為最小的路線，因此，可以根據式（2）將尋找路徑的最優問題轉化為數值處理的最小問題，將式（2）表示為最小二乘平差間接模型

式中，觀測值L為經驗知識值Wi（t），V為觀測值改正數，B為時間或距離參數X的系數陣。根據最小二乘原理，式（3）的解可由下式求得

由式（4）求出的時間或距離參數在數值上為最小，最小參數所對應的路徑認為是最優。在實際生活中，人們選擇出行路徑不僅僅希望某一參數為最小，往往對兩個或幾個要素都提出一定的限制要求。比如要求所規劃的路徑不僅距離較短，而且路徑行使時間保持在一定的數值范圍之內。而應用模型（4）顯然不能解決這樣的問題。根據部分參數的人為限制條件這樣的先驗信息，建立某種不等式形式的約束，可以解決部分先驗信息被忽略的實情。

不等式約束的模型可表示為

式中，G為行滿秩矩陣；W為常量，表示由參數X為變量所構成的函數最大限值，是對參數取值的約束。

以出行路徑距離參數為間接模型（模型（5）式一）參數，最優距離路徑對應的時間參數為不等式約束（模型（5）式二）參數，式（5）的不等式約束最優路徑算法具體模型為

式中，T′（Si）為路徑中各路段距離，Si為變量的時間函數。

模型（6）的算法可通過罰函數與零權和無限權的思想實現，將不等式約束轉化為等式約束。令

當V′≤0時，參數X滿足不等式約束，則不等式為無效約束；當V′≥0時，參數X不滿足不等式約束，則不等式為有效約束。令

P（x）為罰函數，當V′≤0時，即不等式為無效約束時，罰函數值為零；當V′≥0時，即不等式為有效約束時，罰函數值不為零。P′為罰函數P（x）的權值。不等式約束模型（式（6））通過優化計算中的罰函數方法轉化為無約束最優化問題［16］

罰函數P（x）的取值通過定義零權和無限權實現，令

不等式為有效約束時，權值P′取一很大數值k；不等式為無效約束時，權值P′取值為零。

應用不等式約束對城市路網最優路徑進行規劃的基本方法是：應用一定的模型，結合式（4），在最小二乘準則下計算最優路徑；將最優路徑各路段距離為變量的時間函數作為參數代入模型（6）式二，如果滿足條件則應用其路徑，如果不滿足條件則應用模型（9）重新進行平差計算。

3 實驗

應用ArcGIS為平臺軟件，采用C＋＋開發語言，選取宿州市城市道路導航電子地圖為實驗數據，進行本文的算法實現。為應用文獻 ［9］定義的以出租車經驗知識建立的最優路徑規劃模型為基本模型，由于缺乏有效的浮動車軌跡數據，通過綜合路段的道路等級、道路通行的區域特征、道路轉向延遲等方面的因素，對城市路網的主要路段的通行距離、通行時間、通行等級3個參數進行數值模擬。

比較應用式（2），在最小二乘準則下建立間接平差模型（式（4））求取的最優路徑，與不等式約束模型（式（6））求取的最優路徑在路線長度、行駛時間、道路等級三個方面的差異。以宿州市第六中學為出發點，在圖中用三角星表示（見圖1）；以宿州學院（西區）為終點，在圖1中用五角星表示，進行最優路徑的規劃比較。根據出發點至終點所經過區域的道路狀況，結合各路段的通行距離、通行等級、以及所處的地段對通行時間進行數值模擬。各路徑的通行距離與通行時間作為不等式約束模型（式（6））的平差參數與約束參數，參數X為變量所構成的函數最大限值W為10min 在最小二乘準則下，根據間接平差模型求取的最優路徑以淺色路線表示；以不等式約束模型，應用無限權與零權理論求解模型的參數，求取的最優路徑以深色路線表示。

圖1 兩種算法路徑規劃對比圖

兩個算法在路線長度、行駛時間、道路等級三方面的數值統計與對比如表1。結果表明，應用不等式約束算法實現路徑規劃對基于經驗知識模型而言，路徑長度有所增加（增加值為0.4km）。基于不等式約束算法的路徑規劃行駛路段等級為四、五、六級，相對在最小二乘準則原則下選擇的路徑規劃行駛路段等級為四、五級而言，行駛路段等級不太連續。基于不等式約束算法的路徑規劃行駛時間符合模型中不等式約束值的限定要求。這往往與實際生活中，公眾要求在限定時間內通過較短路徑到達目的地的現況相符合。因此，應用不等式約束模型進行最優路徑的規劃更符合人們的出行要求。

表1 本文算法與經驗知識模型算法統計結果比較

4 結論

根據最小二乘的基本思想，給出城市路網最優路徑規劃的不等式約束模型及算法。以宿州市城市路網為例，分別應用浮動車經驗知識模型的規劃最優路徑算法、具有不等式約束的規劃最優路徑算法實現最優路徑選擇。結果表明，應用不等式約束的最優路徑算法能夠顧及公眾出行對距離與時間中的某一因素有要求的同時，對另一因素也有限制條件的實際情況。應用不等式約束算法實現最優路徑的規劃更符合公眾出行的實際需求。

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

［2］ FISHER P.A Primer of Geographic Search Using Artificial Intelligence［J］.Computers ＆ Geosciences，1990，16（6）：753－776.

［3］ CHERKASSKY B V，GOLDBERG A V，RADZIK T.Shortest Paths Algorithms：Theory and Experimental Evaluation［J］.Mathematical Programming，1996，73（2）：129－174.

［4］ 陸 鋒，盧冬梅，崔偉宏.交通網絡限制搜索區域時間最短路徑算法［J］.中國圖象圖形學報，1999，4（10A）：849－853.

［5］ 韓 剛，蔣 捷，陳 軍.車載導航系統中顧及道路轉向限制的弧段 Dijkstra算法［J］.測繪學報，2002，31（4）：366－368.

［6］ 任 剛，王 煒，鄧 衛.帶轉向延誤和限制的最短路徑問題及其求解方法［J］.東南大學學報：自然科學版，2004，34（1）：104－108.

［7］ 鄭年波，李清泉，徐敬海，等.基于轉向限制和延誤的雙向啟發式最短路徑算法［J］.武漢大學學報：信息科學版，2006，31（3）：256－259.

［8］ 孫晉麟.基于浮動車GPS／GIS的車輛行駛路徑優化研究［D］.北京：北京交通大學，2006.

［9］ 唐爐亮、常曉猛、李清泉.出租車經驗知識建模與路徑規劃算法［J］.測繪學報，2010，39（4）：404－409.

［10］ SCHAFFRIN B.Ausgleichung mit Bedingungs－Ungleichungen［J］.Allgemeine Vermessungs－Nachrichten（AVN），1981，88（6）：227－238.

［11］ KOCH K R，RIESMEIER K.Bayesian Inference for the Derivation of Less Sensitive Hypothesis Tests［J］.Journal of Geodesy，1985，59（2）：167－179.

［12］ REMONDI B W.Real－time Centimeter－accuracy GPS：Initializing While in Motion（Warm Start Versus Cold Start）［J］.Navigation，1993，40（2）：199－208.

［13］ UENO M，SANTERRE R，LANGELIER D，etal.Improvement of GPS Ambiguity Resolution Using Height Constraint for the Support of Bathymetric Surveys［C］∥Proceedings of the IAIN／ION Conference.San Diego：［s.n.］，2000：842－850.

［14］ ZHU J J，SANTERRE R，CHANG Xiao－wen.A Bayesian Method for Linear Inequality Constrained Adjustment an Its Application to GPS Positioning［J］.Journal of Geodesy，2005，78（9）：528－534.

［15］ PENG J H，ZHANG H P，SHONG S L，etal.An Aggregate Constraint Method for Inequality－constr－ained Least Squares Problem［J］.Journal of Geodesy，2006，79（12）：705－713.

［16］ 朱建軍，謝 建.附不等式約束平差的一種簡單迭代算法［J］.測繪學報，2011，40（2）：209－212.