城市路網(wǎng)最優(yōu)路徑的不等式約束算法

楊 娟，陶葉青

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

1 引言

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

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

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

2 不等式約束算法模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

罰函數(shù)P（x）的取值通過定義零權和無限權實現(xiàn)，令

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

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

3 實驗

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

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

圖1 兩種算法路徑規(guī)劃對比圖

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

表1 本文算法與經(jīng)驗知識模型算法統(tǒng)計結果比較

4 結論

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

［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］ 陸 鋒，盧冬梅，崔偉宏.交通網(wǎng)絡限制搜索區(qū)域時間最短路徑算法［J］.中國圖象圖形學報，1999，4（10A）：849－853.

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

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

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

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

［9］ 唐爐亮、常曉猛、李清泉.出租車經(jīng)驗知識建模與路徑規(guī)劃算法［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.