復雜路網情況下路徑清分算法研究

郝建明，　李長亮

(中海網絡科技股份有限公司，上海 200135)

復雜路網情況下路徑清分算法研究

郝建明，李長亮

(中海網絡科技股份有限公司，上海 200135)

摘要:為使高速公路中的通行費清分更加公平、公正、高效，從復雜路網入手，參考國內多個省份的路徑清分算法，結合貴州路網結構，提出一種基于二義性區域的路徑清分算法。將該算法應用于實際中，很好地解決了在二義性區域內拆分給最短路徑業主帶來的不公平問題。其同樣適用于相似路網結構的聯網收費清分系統。

關鍵詞:清分算法；最短路徑；二義性區域

0引言

近年來，我國的高速公路產業隨著經濟的發展得到了迅猛發展，大部分省、市、自治區的高速公路都已陸續實現聯網收費、統一清分。但在統一清分過程中，經營業主最關心的是通行費清分是否公平、公正、高效，因此，對從入口站到出口站有多條路徑情況下的通行費清分算法和原則進行研究顯得尤為重要。

通行費的計算大多采用的最小費額法，即按路網中從入口到出口所有可能的行駛路徑中收費最少的路徑(簡稱最小費額路徑)收取的原則進行計算；通行費清分則根據所有可能的行駛路徑中的最短路程(簡稱最短路徑)進行。若路網結構中最小費額路徑與最短路徑不相同且兩者的業主不一致，則按照最短路徑清分就顯得不夠公平。

二義性區域是指同一個入口點到出口點中存在著兩條具有競爭性且分屬不同的業主的路徑。二義性區域內的各條路徑統稱“二義性”路徑，現有路網結構中普遍存在。在二義性區域中合理清分以做到公平公正是一個難題。對此，參考國內多個省份的路徑清分算法，結合貴州路網結構，提出一種基于二義性區域的路徑清分算法，在實際運行過程中起到了良好的效果。

1國內外研究現狀

國外對高速公路進行呈規模收費的不多，且營運公司或單位比較單一，研究重點主要是電子不停車收費，甚至結合全球定位系統(Global Positioning System,GPS)，屬于精確跟蹤定位，不存在“二義性”路徑問題。

近幾年，由于重型卡車的增加導致高速公路的建設和維護成本增加，德國開始對此類車征收通行費，采取GPS與移動通信相結合的技術方案，在車上安裝一個帶有GPS導航功能的移動通信終端，當車輛在高速公路上行駛時，此設備就將該車的行駛狀態發送到數據處理中心，這樣其“二義性”路徑問題就可以直接從GPS導航信息中獲取。

目前我國許多省份的聯網收費里程都已有幾千公里，路網結構越來越復雜，“二義性”路徑問題也越來越突出。在解決“二義性”路徑問題的方案中，不同省份采用的方式各不相同，總體來說技術路線分為以下兩種。

1) 射頻識別法：基于RFID技術，在高速公路的路徑識別點安裝射頻識別設備，當車輛經過采集點時，將標識站點信息寫入通行介質，同時將車輛信息上傳至收費中心系統。采用該方法的省份有廣東、四川。

2) 車牌識別法：即在高速公路的路徑識別點安裝車牌識別設備，用于采集車牌號碼，將車牌信息上傳至收費中心系統，通過后臺匹配出入口車牌和路徑識別點上傳車牌來確定車輛的行駛路徑。采用該方法的省份有湖北、江西、貴州等。

2清分算法研究

2.1路徑清分算法研究

2.1.1路徑清分算法的核心問題

在高速公路實施聯網收費后，確定車輛行駛路徑成為了通行費清分的核心問題。待車輛的行駛路徑確定后，再按照各經營路段所占通行費的比例進行通行費的清分工作。但是，受設備損壞、設備識別精度等因素影響，無論是射頻識別法還是車牌識別法，都無法完全定位車輛的行駛路徑。

基于上述提出的劃分二義性區域方法，在進行通行費清分工作時，對于經過二義性區域的車輛，首先將通行費清分到二義性區域上(即得出二義性區域總的清分金額)，然后對二義性區域內部的各路徑進行二次清分。清分算法分為以下兩種情況:

(1) 在二義性區域內車輛行駛路徑明確，該種情況下按照普通車輛清分規則清分；

(2) 在二義性區域內車輛行駛路徑不明確，該種情況下需采用模糊清分算法清分。

2.1.2模糊路徑清分算法

目前各省份所用的模糊路徑清分算法不盡相同，比較常用的為以下兩種:

(1) 最短路徑法，即認為車輛在二義性區域內總是按照最短的路徑行駛，將通行費分配給最短路徑上的經營業主；

(2) 按比例分配法，即認為車輛在二義性區域內選擇哪條路徑行駛存在比例分配，通常用各路徑上精確識別的車輛清分金額比例來分配模糊路徑的通行費金額，比例的取值范圍通常采用當天的清分金額比例。

2.1.3貴州復雜路網路徑清分算法

在進行二義性區域內明確路徑的通行費清分時，清分規則與普通路徑清分規則一致。

在進行二義性區域內模糊路徑的通行費清分時，最短路徑法適用于二義性區域內的競爭性路徑里程差距較大的情況。貴州的二義性區域內各條路徑的里程差距較小，因此不適合采用最短路徑法。

對于按比例分配法，考慮到車牌識別設備的故障率等因素，采用當天的比例可能導致某車牌識別設備損壞的業主模糊通行費損失較大。因此，提出采用清分日前30天的平均比例作為模糊路徑通行費的清分比例，以此降低設備故障對通行費清分的影響，保證各家經營業主的合法權益。

2.2路網結構分析

目前貴州全省高速公里建設里程已經突破4 000 km，隨著建設里程逐漸增加，路網的復雜度也隨之成幾何倍數增加。

1) 簡單二義性路徑，即同一出入口之間存在兩條競爭性收費路徑。圖1為貴陽-晴興組成的簡單二義性區域示意圖，為使示意圖簡潔，貴陽周邊的8個相關收費站沒有全部標出。

2) 嵌套二義性區域，即一個二義性區域內的某條路徑上存在一個嵌套子二義性區域。圖2為貴陽-思南組成的二義性區域(以下簡稱外層二義性區域)示意圖，其中貴陽-劍河-思南線上還有一個貴陽-都勻的嵌套子二義性區域(以下簡稱內層子二義性區域)，為使示意圖簡潔，貴陽、遵義周邊的25個收費部沒有全部標出。

圖1　貴陽-晴興組成的簡單二義性區域示意圖

圖2　貴陽周邊、遵義周邊、思南、劍河組成的嵌套二義性區域示意圖

3) 交叉二義性區域，即兩個相鄰二義性區域有重疊部分。圖3為貴陽-思南及貴陽-晴興兩個二義性區域組成的交叉二義性區域示意圖，為使示意圖簡潔，貴陽周邊的19個收費站沒有全部標出。

圖3　思南-貴陽-晴興組成的交叉二義性區域示意圖

3復雜路網清分算法說明

3.1普通路徑拆分

普通路徑是指同一出/入口之間不存在二義性區域的路徑，其清分原則比較明確、統一，即按照最小費額路徑進行收費，按照最短路徑上的各路段的應收費額比例進行拆分。在拆分通行費金額時，需要精確計算，將計算結果直接四舍五入到分，并將尾差調整給最后1個有收益的業主。計算公式為

(1)

式(1)中：L為路段應收費額。

例如：某一型車從甲收費站駛入高速公路，從乙收費站駛出，共行駛了75 km，先后經過A公司20 km(應收費額為10.67元)、B公司15 km(應收費額為8.1元)；C公司40 km(應收費額為21.33元)、D公司1 km(應收費額為0.55元),收費站實際收費額為40元。其拆分步驟為：

(1) 計算：總應收費額=10.67元+8.1元+21.33元+0.55元=40.65元；

(2) 按照式(1)進行拆分，可得A公司通行費XA=10.50元，B公司通行費XB=7.97元，C公司通行費XC=20.99元，D公司通行費XD=0.54元；

(3) 計算已拆分金額=10.50元+7.97元+20.99元+0.54元=40元；

(4) 進行尾差調整，已拆分金額等于已收金額，無需進行尾差調整。

3.2簡單二義性區域拆分

對于簡單二義性區域(如圖1)，其外部的路段業主收益不能因為車輛在二義性區域內選擇的行駛路徑不同而有變化，因此需要進行兩次拆分。

1) 計算整個二義性區域應拆分的金額。把二義性區域作為一個虛擬業主，其應收費額取其最小費額路徑上的路段應收費額之和。

2) 在二義性區域內部，根據車輛精確識別路徑或按照該二義性區域前30天精確識別的拆分通行費金額比進行二次拆分。

在二義性區域內，車輛選擇通行哪條路徑都是有可能的。因此，在兩條路徑上分別安裝車牌捕捉識別儀器，對于識別到的車輛，認為其對于精確識別路徑的車輛；對于兩個車牌識別儀器都未識別到的車輛，認為其是未識別路徑的車輛。此時的第二次拆分可分為以下兩種情況。

(1) 對于精確識別路徑車輛的通行費，把二義性區域應拆分總金額二次拆分給精確路徑上的各個業主；

(2) 對于未識別路徑車輛的通行費，首先計算該二義性區域內每條路徑上前30天的精確識別車輛所拆分的金額合計，用兩者的比例把該二義性區域應拆分總金額分到兩條路徑上，在每條路徑上進行二次拆分。

3.3嵌套二義性區域拆分

1) 把外層二義性區域作為一個虛擬業主(其應收費額是該二義性區域的最小費額路徑上各個路段的應收費額之和)，第一次拆分計算出該虛擬業主的應拆分總金額。

2) 根據外層二義性區域的車牌識別情況把外層二義性區域的應拆分總金額拆分到精確識別的路徑上或按照比例拆分到兩條路徑上。如果路徑上有內層子二義性區域，把內層子二義性區域作為一個獨立的虛擬業主，其應收費額是該內層子二義性區域的最小費額路徑各個路段的應收費額之和。

3) 如果含有內層之二義性區域，按照該二義性區域的車牌識別情況把該二義性區域的應拆分總金額拆分給精確識別的路徑上或按照該二義性區域前30天精確識別車輛所拆分的合計金額比例拆分給兩條路徑，內層子二義性區域的拆分可視為1個簡單二義性區域的拆分。

3.4交叉二義性區域拆分

對于交叉二義性區域，其含有兩個無法精確拆分的二義性區域(分別稱為A二義性區域和B二義性區域)，因此需要有4個車牌識別點。根據兩對車牌識別點識別的情況，可把交叉二義性區域的拆分分成以下三種情況處理。

1) 對于A和B兩個二義性區域都精確識別的，交叉二義性區域的應拆分總金額直接拆分給精確識別的路徑(即拆分給A區域的識別路徑和B區域的識別路徑)。

2) 對于A和B兩個二義性區域只有1個精確識別的，精確識別的二義性區域對應的應拆分總金額直接拆分給該二義性區域的精確識別路徑，未精確識別的二義性區域對應的應拆分總金額按照該二義性區域前30天精確識別車輛所拆分的金額比例拆分給兩條路徑。

3) 對于A和B兩個二義性區域都未精確識別的，按照前兩種情況過去30天內各業主的實際拆分金額比例拆分該區域應拆分總金額。

4算法應用

所提出的算法從2014年7月開始正式啟用，取2014-07-05/2014-07-13貴陽-晴興二義性區域的真實現金流水數據進行對比，原拆分金額(即最短路徑拆分)和二義性拆分金額對比表見表1。可見，采用該算法的實際清分結果更公平，更能保障各經營業主的合法權益。

表1　原拆分金額和二義性拆分金額對比表

5結語

該清分路徑算法以貴州省高速公路聯網收費路徑清分系統為對象設計，很好地解決了在二義性區域內拆分給最短路徑業主帶來的不公平問題。由于貴州省高速公路路網結構在國內較為典型，因此該算法有一定的通用型，適用于其他相似路網結構的清分。對于有嵌套二義性區域和八字形區域組成的路網結構，均可使用該算法提高拆分公平性，提升工作效率。

參考文獻：

[1]李猛.基于RFID技術多義性路徑識別系統在高速公路聯網收費中的應用[J].廣東科技,2013(16):155-156.

[2]徐青松,王力鵬,陳健華.典型高速公路路網的清分路徑算法[J].上海船舶運輸科學研究所學報,2011,34(12)：168-171.

中圖分類號：U495

文獻標志碼：A

A Route Clearing Algorithm in Complex Highway Tolling System

HaoJianming,LiChangliang

(China Shipping Network Technology Co., Ltd, Shanghai 200135, China)

Abstract:The existing highway toll clearing algorithms distribute the toll income according to the principle of the shortest path, which may not fair in some ambiguous areas of complex highway networks. In view of such a problem a new highway toll clearing algorithm is designed based on route distinguishing. The algorithm has been successfully used in highway network in Guizhou province. The algorithm is equally applicable to the clearing systems for similar network structures.

Key words:clearing algorithm; shortest path algorithm; ambiguous section