[發明專利]合乘動態匹配多級篩選方法

有效

• 申請號: 200810056015.4
• 申請日: 2008-01-11
• 公開（公告）號: CN101216913B
• 公開（公告）日: 2010-11-10
• 發明（設計）人: 陳艷艷;王東柱
• 申請（專利權）人: 北京工業大學
• 主分類號: G06Q10/00
• 分類號: G06Q10/00;G06Q50/00;G08G1/00
• 代理公司: 北京思海天達知識產權代理有限公司 11203
• 代理人: 張慧

1.合乘動態匹配多級篩選方法，其特征在于：本方法借助互聯網或移動無線網絡作為信息交互平臺，開車人和搭車人向提供搭乘信息服務的服務器發出查詢請求并提供相應信息，由服務器進行匹配處理，并將搭乘組合匹配結果和搭乘路徑發送回查詢人；

服務器進行匹配處理時，以用戶輸入的實時信息及服務器上的地圖信息為依據，根據搭乘點對相互間地理位置關系，通過多級的優化篩選過程來保證自動搭乘匹配組合的最優；

本方法所用電子地圖須包含以下路段屬性信息：路段編號、路段名稱、左右端節點坐標、路段長度，路段速度，路段類型；以及地址數據信息：地址編號，地址名稱、與之對應的地址坐標信息和該地址的類型，數據庫中通過地址名稱得到該地址的坐標；

動態匹配多級篩選的具體步驟如下：

1)注冊

開車人及搭車人向服務器發送“姓名、電話號碼、家庭住址、常去地址”，并設置用戶名及密碼完成注冊；

2)發出匹配請求

當有合乘需求時，開車人或搭車人提交用戶名及密碼登陸服務器，發出匹配請求，并提供相關信息；搭車人和開車人的請求信息通過數據庫形式存于服務器上；

開車人發送匹配請求的信息包括：出行的起點地址和終點地址、開車人出發時間T_i、繞行距離約束；

搭車人發送匹配請求的信息包括：出行的起點地址和終點地址、搭車人期望出發時間T_j、搭車人可接受的推前或推后時間約束T₀；

開車人繞行距離約束包括相對約束條件值C_c和絕對約束條件值C_e；其中，絕對約束條件值是繞行搭乘的絕對距離，以米或分鐘為單位；相對約束條件值是實際繞行距離與自己起點終點的直接距離的比值；

3)動態裝載搭乘信息網絡

將搭乘信息網絡裝入系統；

4)動態合乘匹配

服務器用繞行路權優選、就近原則優選和最后用戶挑選的三級優選的方法使用戶得到最優的搭乘組合；

具體步驟如下：

(1)虛擬搭乘網絡的構建

服務器將開車人和搭車人的請求分別處理，建立搭乘網絡及開車網絡；

所述的搭乘網絡的構建方法是將系統中所有搭車人出行起點與該開車人出行起點相連，所有搭車人終點與該開車人終點相連；

所述的開車網絡的構建方法是將系統中所有開車人的起點與該搭車人的起點相連，所有開車人的終點與該搭車人的終點相連；

(2)動態合乘組合分級篩選匹配算法；

服務器對開車人的匹配請求和搭車人的匹配請求分別進行處理；

服務器對開車人的匹配請求按如下步驟進行處理：

步驟0：初始化及數據準備

對任一開車請求點α_i，起點記為i，終點記為i’，搭車請求點β_j，起點為j，終點為j’；假設系統中所有開車人的個數為N，所有搭車人的個數為M；

步驟1，裝載數據庫中所有搭車人β_j搭乘數據到內存，通過查詢地圖數據庫，將搭車人的起點和終點的地址信息轉換為平面坐標為：(x_j，y_j)、(x_j’，y_j’)；

將開車人α_i的起始地址和終點地址，通過查詢地圖數據庫，轉換為平面坐標(x_i，y_i)、(x_i’，y_i’)；

步驟2：計算開車人起點α_i經過搭車起點β_j及搭車終點β_j′到目的地α_i’的繞行權重估計值，其中：j，j’＝1，2...M；

令L_ii’為α_i到α_i’的直接距離估計，L_ij為α_i到β_j的距離估計，L_jj’為β_j到β_j’的距離估計，L_j’i’為β_j’到α_i’的距離估計，L’_ii’為α_i經β_j到β_j’到α_i’的繞行距離估計；

以L_ij為例，其值用下式計算：

L_ij＝|(x_j-x_i)|+|(y_j-y_i)|

L_jj’＝|(x_j’-x_j)|+|(y_j’-y_j)|

L_j’i’＝|(x_i’-x_j’)|+|(y_i’-y_j’)|

繞行權重估計值為：

L’_ii’＝L_ij+L_jj’+L_j’i’

步驟3：根據時間及繞行約束條件進行初級篩選；

判斷：|T_i+L_ij/V-T_j|＜＝_T₀????????????(1)

??????L_ij+L_jj’+L_j’i’＜C_c·L_ii’????(2)

??????|L_ij+L_jj’+L_j’i’-L_ii’|＜C_e???(3)

其中：T_i為開車人出發時間，V為α_i到β_j的平均車速，T_j為搭車人期望出發時間，T₀為搭車人可接受的推前或推后時間；C_c為相對約束條件值，無量綱，1＜C_c≤1.5，C_e為絕對約束條件值，市區范圍內，0公里＜C_e＜10公里；

記錄L’_ii’值，將所有的同時滿足(1)、(2)或同時滿足(1)(3)條件的β_j按L’_ii’值從小到大的順序排序，其中j＝1，2...M，取前n個L’_ii’較小值點，其中：n＝5～10，放入一級合理點集U₁；

步驟4：根據就近搭乘原則進一步篩選最佳搭乘組合

將U₁點集中L_ij＞L₀的搭乘點刪除，其中：L₀為系統設定的開車人起點到搭車人起點的距離上限；并把剩余的搭乘點按L_ij值由小到大的順序，將排在前m個的搭乘點，其中m＜n，放入二級合理點集U₂；若剩余的搭乘點過少，則取消此約束，或增加L₀；

步驟5：計算搭乘路徑，根據用戶選擇進行三級篩選

根據二級篩選后得到的搭乘匹配組合結果，即m對開車人和搭車人的起始點和終點信息，用A^*或Dijkstra算法計算相應的實際搭乘最短路徑及路長，供用戶參考，并作最終選擇；

5)匹配結果發布

包括匹配成功的搭車人、開車人信息和路徑的匹配結果通過網絡發送給查詢人，同時存入搭乘數據庫作為存檔；

當服務器接收到的搭車請求時，與開車請求處理方法一樣。

2.根據權利要求1所述的合乘動態匹配多級篩選方法，其特征在于：所述的動態裝載搭乘信息網絡，當服務器接收到的是搭車請求時，則只將所有開車人的數據信息裝入系統；當服務器接收到的是開車人請求時，則只將所有搭車人的數據信息裝入系統。