一種基於時間與費用約束的動態拼車匹配方法

2023-04-28 21:38:51

一種基於時間與費用約束的動態拼車匹配方法
【專利摘要】本發明提出了一種較為通用的動態拼車匹配方法，解決了在乘客的拼車時間和拼車費用兩個約束條件下，為乘客實時匹配滿足條件的最優司機的問題。本發明中的動態拼車匹配方法共分為三個步驟，包括：步驟1，建立動態拼車匹配模型，包括時間、費用以及skyline關係模型；步驟2，建立動態拼車數據結構，包括DriverTable,MatchingTable,Grid索引等；步驟3，動態拼車匹配，其核心思想是通過儘量減少或延後最短路徑的計算來保證匹配的高效性；同時，通過設置司機的skyline約束，進一步減少匹配的計算量，而且保證了匹配到的司機與其他備選司機相比，時間或者費用方面是較優的。
【專利說明】一種基於時間與費用約束的動態拼車匹配方法

【技術領域】
[0001] 本發明屬於基於位置服務（LBS, Location Based Service)與地理信息系統 (Geographic Information System)交叉領域，主要針對現有拼車系統無法滿足乘客以及 司機對拼車實時性需求的問題，提出一種高效的、基於時間與費用約束的動態拼車匹配技 術，進而實時提供給乘客滿足其拼車要求的候選司機。

【背景技術】
[0002] 隨著城市車輛數量激增，與道路交通相關的問題日趨嚴重，如停車佔地需求增大、 石油消耗增多導致空氣品質下降、城市交通擁塞等，這些問題在世界範圍內被公認為是影 響人們生活質量的主要原因。儘管政策採取了一系列的方式來解決上述問題，如通過搖號 方式限購車輛、尖峰時段限制部分車牌號上路、修建新的高架道路或擴展現有道路等，但這 些方式不僅投入成本巨大，也給人們的日常生活帶來了新的不便。與上述方式相比，拼車系 統做為一種更加靈活且實施成本小的緩解交通問題的方法，在近年來被提上議程，並且引 起了產業界和學術界的廣泛關注。首先，拼車可有效降低汽車的空駛率，不僅緩解了交通擁 塞，也減少了車輛對環境的汙染。其次，拼車時乘客會付給司機一定的拼車費用，相對於乘 客自己駕車出行的費用，司機和乘客的出行成本均得到了降低。
[0003] 拼車系統一般通過將那些在出行時間和出行路徑上相似的乘客安排在相同的車 輛中，進而提高車輛的空座利用率。在實現方式上，拼車系統可分為兩類：靜態拼車與動態 拼車。靜態拼車是指司機、乘客提前一段較長的時間（多個小時或多天）在系統中發布相關 拼車信息，系統負責乘客和司機匹配工作。相對於靜態拼車，動態拼車是針對個別的出行， 而不是基於有規律的出行，其實現則更加靈活、實時，難度更大。一般來說，乘客通過智能手 機向系統發布拼車需求，動態拼車系統在接受請求的同時，利用GPS對乘客和正在駕駛的 司機分別定位，然後實時對乘客和司機進行匹配，並將結果實時返回給相應的司機和乘客。
[0004] 由於在具體的匹配過程當中涉及到道路交通網上最短路徑的計算，而實際中需要 對大量的司機與乘客對應的拼車中路線進行匹配，因此大規模的最短路徑計算使得動態拼 車難以實現。現有的動態拼車系統採用的匹配技術均在匹配模型上做了不同的限制，進而 產生了不同的缺陷：（1)僅返回乘客起始位置的k個近鄰司機，不考慮司機原始目的地，這 種情況下乘客可能會找到一個離其距離近的司機來乘車，但是司機路線的終點與乘客的終 點距離很遠，導致拼車費用高；(2)乘客的路線必須是司機路線的一部分，這樣的約束在實 際應用中不夠靈活而且可能錯失一些能夠通過適當的繞道提供給乘客合理拼車價格的司 機；（3)與公交車類似，司機需事先指定上客與下客點，乘客需要步行到相應的上客點上車 然後從下客點步行回目的地，這樣的拼車方式使得乘客受限於特定的上下車點，在實際應 用中並不靈活；(4)乘客與司機路線的起點與終點必須在一定的範圍內，不能偏離太遠，然 而，實際中一些司機的起點即使遠離乘客起點，他們也可能會提供一個更低更合理的拼車 費用。


【發明內容】

[0005] 為了克服現有技術的上述確定啊，本發明提出了一種高效動態拼車匹配方法，該 技術從乘客角度出發，旨在高效地匹配出滿足乘客拼車需求的候選司機集合。
[0006] 該集合中的候選司機具有如下兩個特點：（1)集合中的司機均能在乘客的最大等 待時間（Ma X_Wait_Time)內從其起點趕到乘客的起點，其產生的拼車費用也低於乘客所能 接受的最大費用；(Max_Ridesharing_Cost) ;(2)集合中的司機與司機間在乘客等待時間 與拼車費用兩個屬性上是skyline關係，即任意一個司機無法同時在等待時間和拼車費用 上優於另一個集合中的司機。
[0007] skyline司機的提出是出於如下考慮：實際中若存在兩個候選司機，其中一個司 機在等待時間和拼車費用上均比另外一個司機與乘客匹配後的相應值要大，那麼選擇該司 機則沒有實際意義，因此本發明匹配技術在匹配過程當中，也對這一類的司機進行了相應 的過濾處理。下面，從拼車匹配模型和匹配方法兩個方面進行敘述。
[0008] 本發明所述的一種基於時間與費用約束的動態拼車匹配方法，包括：
[0009] 步驟1，建立動態拼車匹配模型
[0010] 作為動態拼車僅有的兩個參與角色，司機與乘客在匹配時均有各自的起始位置與 終點位置，默認起點與終點間的路線為最短路徑。為方便描述，使用d表示司機，r表示乘 客，RiderTrip和DriverTrip分別對應司機與乘客在匹配前各自的路線，路線長度又可轉 換成相應的費用成本。在匹配過程中，乘客和司機拼車費用的計算方式決定了匹配方法的 設計。考慮到司機可能需要偏離原計劃路線，通過繞道去接乘客或送乘客到目的地，最終乘 客應付給司機的費用中不僅包含拼車後走的路程，還要包含司機繞道所產生的成本，下面 給出拼車費用的表示方式：
[0011] Price (d,r) = RiderTrip+Detour
[0012] 其中，Price (d, r)表示拼車費用；RiderTrip表示拼車後共同走的路程，即乘客的 路線；Detour表示司機相對其原始路線多走的路程，即繞道路程，其計算方式如下：
[0013] Detour (d, r) = Pickup+RiderTrip+Return - DriverTrip
[0014] 其中，Pickup是司機起點與乘客起點間的路程，即司機去接乘客時的費用； Return表示司機目的地與乘客目的地間的路程距離，即司機在送完乘客時返回的費用。
[0015] 基於上述關係，可進一步得到計算拼車費用的如下公式：
[0016] Price (d, r) = Pickup+2*RiderTrip+Return - DriverTrip (1)
[0017] 公式1中右邊的計算單元均是拼車匹配模型中的基本費用單元，在隨後的匹配方 法設計當中將被使用。下面，從乘客角度出發，給出拼車匹配模型的定義。
[0018] 定義1.給定一個司機集合D和一個乘客r，動態拼車匹配旨在D中找到一個子集 合D'，並且對於D '中的任意一個司機，需要滿足如下約束：
[0019] ?時間約束：Pickup (d, r) <rmax_Time
[0020] ?費用約束：Price (d, r) <rmax_Price
[0021] · Skyline 約束：D' 需要經過對 Pickup (d, r)與 Price (d, r)的 skyline 處理
[0022] 上述定義中，r_ Tinie表示乘客的最大等待時間，r_ 表示乘客的最大拼車費用。 基於定義1中的匹配模型，下面介紹本發明所需要用到的相關數據結構。
[0023] 步驟2,建立動態拼車數據結構
[0024] 在執行動態拼車匹配時需要涉及到相關數據的存儲、排序等工作，因此需要根據 定義1所述拼車問題模型設計合適的數據結構以支撐匹配過程的運算。
[0025] Driver Table (司機表）.拼車匹配過程中需要維護每個司機的4個欄位：（1) ID : 司機d的唯一標識；（2)CurrentL〇Cati〇n :d的當前位置，由於匹配時司機可能處在移動狀 態，因此該值將會隨著時間的不同而可能發生變化，且該變化可由特定的終端設備來捕獲 並更新，如 GPS ; (3) DestinationLocation :d 的目的地位置；（4) DriverTrip :d 的起點（即 CurrentLocation)與目的地間的最短路徑。
[0026] Matching Table (匹配表）.該表為動態拼車匹配過程中用來匹配一個乘客與多 個司機的主要依據。它包含了一對乘客r與司機d的6個欄位內容：（1) ID :司機d的唯 一標識；（2)Pickup :d起點與r起點間的最短路徑，該值也可經換算表示成乘客r的實際 等待時間；（3)EuclideanPickup :d起點與r起點間的歐式距離；（4)Return :d目的地與 i目的地間的的最短路徑；（5)EUClideanRetUrn :d目的地與r目的地間的歐式距離；（6) DriverTrip :Driver Table中的第4個欄位，即d的起點與目的地間的最短路徑。
[0027] 步驟3,動態拼車匹配
[0028] 相對最短路徑距離，兩點間歐式距離的計算複雜度要低的多。因此，作為本發明中 的核心部分-動態拼車匹配方法就是基於Driver Table與Matching Table,利用歐式距 離作為出發點，設計一系列的邊界條件，通過提前過篩選掉一些不需要計算所有最短路徑 的司機，進而提高匹配效率，得到滿足乘客需求的候選司機列表。匹配方法從整體上可分為 兩個階段：歐氏距離匹配與半歐式距離匹配。
[0029] 3. 1 歐氏距離（Euclidean Distance)匹配過程
[0030] 歐氏距離匹配的思路是使用歐氏距離代替實際距離進行預估算和篩選。因為司機 與乘客間的歐氏距離小於實際距離，因此可以利用不等式的傳遞性，初步排除一些不滿足 要求的司機。具體步驟如下：
[0031] 3. 1. 1時間篩選。
[0032] 以乘客的起點r為圓心，將乘客最大等待時轉化的歐氏距離作為半徑畫 一個圓QR，即執行一個範圍查詢（range query)。所有不包含在QK內的司機將會被排除。 原因是他們在最短距離（歐氏距離）的條件下也無法及時趕到乘客出發點。
[0033] 3. 1. 2拼車成本篩選。
[0034] 將拼車費用的公式1中的Pickup和Return分別用歐氏距離EuclideanPickup和 EuclideanReturn進行替換，得到新的費用公式
[0035] Price (d, r) = EuclideanPickup+2氺RiderTrip+EuclideanReturn - DriverTrip (公式2)
[0036] 因為歐氏距離在地圖上兩點間最短，根據不等式的傳遞性，若司機d使用公式2計 算出的理想拼車費用大於rmax ，那麼d用公式1得出的實際也必然大於rmax 。所以將 這部分不符合條件的司機排除。
[0037] 3. 2 半歐氏距離（Semi-Euclidean Distance)匹配過程
[0038] 為了找出正確的候選司機列表，在歐氏距離匹配結果的基礎上，需要進一步篩選， 同時還要減少最短路徑計算和skyline比較的次數。思路是在公式2的基礎上，分步將歐 氏距離用實際的最短路徑距離代替來計算拼車費用Price (d，r)，並進行篩選，以達到篩選 司機的同時儘可能減少計算的目的。半歐氏距離匹配法步驟如下：
[0039] 3. 2. 1 公式 2 中 Pickup 替換
[0040] 將 EuclideanPickup 用實際 Pickup 代替，得到：
[0041] Price (d, r) = Pickup+2*RiderTrip+EuclideanReturn - DriverTrip (公式 3)
[0042] 3· 2· 2匹配表排序
[0043] 將匹配表中的每位司機根據EuclideanReturn-DriverTrip的值按遞增進行排 序。接著設置一個閥值MAX，初始化其值為乘客提出拼車請求時的費用約束r maxMre，作為最 終成為匹配成功司機的拼車成本的上邊界。基於skyline計算過程（即拼車費用與等待時 間），MAX值將逐漸縮小，這樣使得更多的滿足乘客時間和費用約束的司機被過濾掉，即這 些司機不能作為skyline結果返回。
[0044] 3. 2. 3候選司機篩選
[0045] 該篩選過程是迭代式的。在每一次迭代過程當中，需要首先從匹配表中挑選離乘 客最近的一個司機d，可在路網上執行增量K近鄰算法（Incremental K nearest neighbor) 獲取。然後計算他的實際Pickup值。司機d的Pickup值只可能是以下四種情況之一：
[0046] A1.司機d的PickUp>rmax Time，即司機d無法按時接到乘客。此情況下會立即終止 接下來的篩選流程，將匹配表中包括d在內的所有司機刪除。因為其他司機相比於司機d， 離乘客的起點更遠，無法滿足乘客的時間約束。
[0047] A2.司機d的Pickup〈rmax_Time;，但d根據公式3所計算出的拼車費用大於MAX。因 為不滿足費用約束，司機d將會被從匹配表中刪除。一同被排除的還有匹配表中位於司機 d之後的所有司機。因為根據公式3計算，雖然其他司機的RiderTrip值與司機d相同，但 是他們的Pickup和EuclideanReturn-DriverTrip的值都大於d，所以總拼車費用也必然大 於d和MAX。
[0048] A3.司機d的Pickup〈rmax_Time，且d根據公式3所計算出的拼車費用也小於MAX,但 是d使用公式1 (需要計算實際Return)計算出的拼車費用大於MAX。因此，d不能滿足拼 車費用約束，不能成為候選司機。
[0049] A4.以上三種情況之外。d將成為既能滿足時間約束又能滿足費用約束的候選司 機。接著我們將MAX的值改為司機d的實際的拼車費用（根據公式1計算得到）。然後將 該司機從匹配表中刪除，最後進入下一個迭代篩選過程。更改MAX的值是因為最終返回的 匹配結果要求是skyline關係，即新的候選司機相對前一個候選司機來說，由於其等待時 間要比前一個司機長，所以其造成的拼車費用要比上一個候選司機小才能作為最終結果返 回。
[0050] 為了解決上述拼車匹配過程中所面臨的難點和克服現有拼車技術的不足，本發明 在充分總結實際拼車需求的基礎上，開創性地提出了一種高效的動態拼車匹配技術。該匹 配技術需要乘客提供其起點（可由智能終端GPS設備自動提供）、目的地、最大等待上車時 間（Max_Wait_Time)以及願意付給司機的最大拼車費用（Max_Ridesharing_Cost);對於司 機，僅需要其提供當前所在位置信息以及目的地地址。雖然實際情況中，司機也會有額外的 拼車服務需求，如最遠繞道距離，最大接乘客時間等，這些需求約束均可基於本發明進行簡 單擴展而實現。為保證本發明所提技術的一般性，更多額外的拼車約束及其實現不在本專 利的討論範圍內。
[0051] 本發明的優點是：設計了通用的、基於乘客等待時間和拼車費用的動態拼車匹配 方法，通過歐式、半歐式距離的過濾方法，有效地解決了當前動態拼車匹配方法中因大量 最短路徑計算所帶來的效率低問題，保證了匹配的實時性；此外，在滿足乘客時間和費用 約束的條件下，為進一步找到在時間和費用兩方面是skyline關係的司機集合，本發明將 sky 1 ine操作嵌入到了匹配過程當中，不僅沒有對整個匹配過程造成額外的計算開銷，反而 使得整個匹配過程更加高效，最終達到了又快又好的匹配效果。

【專利附圖】

【附圖說明】
[0052] 圖1為本發明步驟3. 1的過程圖
[0053] 圖2為本發明步驟3. 2的過程圖
[0054] 圖3表示基於乘客等待時間歐式距離的範圍查詢示例
[0055] 圖4表示基於圖3範圍查詢結果的匹配表
[0056] 圖5表示基於歐氏距離的拼車成本篩選示例圖
[0057] 圖6為匹配表排序示意圖
[0058] 圖7為替換EuclideanPickup為真實路徑Pickup後的篩選示意圖
[0059] 圖8為半歐氏距離匹配司機skyline篩選示意圖 圖9為skyline司機篩選示意圖

【具體實施方式】
[0060] 參照附圖：
[0061] 本發明所述的一種基於時間與費用約束的動態拼車匹配方法，包括：
[0062] 步驟1，建立動態拼車匹配模型
[0063] 作為動態拼車僅有的兩個參與角色，司機與乘客在匹配時均有各自的起始位置與 終點位置，默認起點與終點間的路線為最短路徑。為方便描述，使用d表示司機，r表示乘 客，RiderTrip和DriverTrip分別對應司機與乘客在匹配前各自的路線，路線長度又可轉 換成相應的費用成本。在匹配過程中，乘客和司機拼車費用的計算方式決定了匹配方法的 設計。考慮到司機可能需要偏離原計劃路線，通過繞道去接乘客或送乘客到目的地，最終乘 客應付給司機的費用中不僅包含拼車後走的路程，還要包含司機繞道所產生的成本，下面 給出拼車費用的表示方式：
[0064] Price (d,r) = RiderTrip+Detour
[0065] 其中，Price (d, r)表示拼車費用；RiderTrip表示拼車後共同走的路程，即乘客的 路線；Detour表示司機相對其原始路線多走的路程，即繞道路程，其計算方式如下：
[0066] Detour (d, r) = Pickup+RiderTrip+Return - DriverTrip
[0067] 其中，Pickup是司機起點與乘客起點間的路程，即司機去接乘客時的費用； Return表示司機目的地與乘客目的地間的路程距離，即司機在送完乘客時返回的費用。 [0068] 基於上述關係，可進一步得到計算拼車費用的如下公式：
[0069] Price (d, r) = Pickup+2*RiderTrip+Return - DriverTrip (1)
[0070] 公式1中右邊的計算單元均是拼車匹配模型中的基本費用單元，在隨後的匹配方 法設計當中將被使用。下面，從乘客角度出發，給出拼車匹配模型的定義。
[0071] 定義1.給定一個司機集合D和一個乘客r，動態拼車匹配旨在D中找到一個子集 合D'，並且對於D '中的任意一個司機，需要滿足如下約束：
[0072] ?時間約束：Pickup (d, r) <rmax_Time
[0073] ?費用約束：Price (d, r) <rmax_Price
[0074] · Skyline 約束：D' 需要經過對 Pickup (d, r)與 Price (d, r)的 skyline 處理
[0075] 上述定義中，rmax Time表示乘客的最大等待時間，rmax 表示乘客的最大拼車費用。 基於定義1中的匹配模型，下面介紹本發明所需要用到的相關數據結構。
[0076] 步驟2,建立動態拼車數據結構
[0077] 在執行動態拼車匹配時需要涉及到相關數據的存儲、排序等工作，因此需要根據 定義1所述拼車問題模型設計合適的數據結構以支撐匹配過程的運算。
[0078] Driver Table (司機表）.拼車匹配過程中需要維護每個司機的4個欄位：（1) ID : 司機d的唯一標識；（2)CurrentL〇Cati〇n :d的當前位置，由於匹配時司機可能處在移動狀 態，因此該值將會隨著時間的不同而可能發生變化，且該變化可由特定的終端設備來捕獲 並更新，如 GPS ; (3) DestinationLocation :d 的目的地位置；（4) DriverTrip :d 的起點（即 CurrentLocation)與目的地間的最短路徑。
[0079] Matching Table (匹配表）·該表為動態拼車匹配過程中用來匹配一個乘客與多 個司機的主要依據。它包含了一對乘客r與司機d的6個欄位內容：（1) ID :司機d的唯 一標識；（2)Pickup :d起點與r起點間的最短路徑，該值也可經換算表示成乘客r的實際 等待時間；（3)EuclideanPickup :d起點與r起點間的歐式距離；（4)Return :d目的地與 i目的地間的的最短路徑；（5)EUClideanRetUrn :d目的地與r目的地間的歐式距離；（6) DriverTrip :Driver Table中的第4個欄位，即d的起點與目的地間的最短路徑。
[0080] 步驟3,動態拼車匹配
[0081] 相對最短路徑距離，兩點間歐式距離的計算複雜度要低的多。因此，作為本發明中 的核心部分-動態拼車匹配方法就是基於Driver Table與Matching Table,利用歐式距 離作為出發點，設計一系列的邊界條件，通過提前過篩選掉一些不需要計算所有最短路徑 的司機，進而提高匹配效率，得到滿足乘客需求的候選司機列表。匹配方法從整體上可分為 兩個階段：歐氏距離匹配與半歐式距離匹配。
[0082] 3. 1 歐氏距離（Euclidean Distance)匹配過程
[0083] 歐氏距離匹配的思路是使用歐氏距離代替實際距離進行預估算和篩選。因為司機 與乘客間的歐氏距離小於實際距離，因此可以利用不等式的傳遞性，初步排除一些不滿足 要求的司機。具體步驟如下：
[0084] 3. 1. 1時間篩選。
[0085] 以乘客的起點r為圓心，將乘客最大等待時轉化的歐氏距離作為半徑畫 一個圓QR，即執行一個範圍查詢（range query)。所有不包含在QK內的司機將會被排除。 原因是他們在最短距離（歐氏距離）的條件下也無法及時趕到乘客出發點。
[0086] 3. 1. 2拼車成本篩選。
[0087] 將拼車費用的公式1中的Pickup和Return分別用歐氏距離EuclideanPickup和 EuclideanReturn進行替換，得到新的費用公式
[0088] Price (d, r) = EuclideanPickup+2氺RiderTrip+EuclideanReturn - DriverTrip (公式2)
[0089] 因為歐氏距離在地圖上兩點間最短，根據不等式的傳遞性，若司機d使用公式2計 算出的理想拼車費用大於rmax ，那麼d用公式1得出的實際也必然大於rmax 。所以將 這部分不符合條件的司機排除。
[0090] 3. 2 半歐氏距離（Semi-Euclidean Distance)匹配過程
[0091] 為了找出正確的候選司機列表，在歐氏距離匹配結果的基礎上，需要進一步篩選， 同時還要減少最短路徑計算和skyline比較的次數。思路是在公式2的基礎上，分步將歐 氏距離用實際的最短路徑距離代替來計算拼車費用Price (d，r)，並進行篩選，以達到篩選 司機的同時儘可能減少計算的目的。半歐氏距離匹配法步驟如下：
[0092] 3. 2. 1 公式 2 中 Pickup 替換
[0093] 將 EuclideanPickup 用實際 Pickup 代替，得到：
[0094] Price (d, r) = Pickup+2*RiderTrip+EuclideanReturn - DriverTrip (公式 3)
[0095] 3· 2· 2匹配表排序
[0096] 將匹配表中的每位司機根據EuclideanReturn-DriverTrip的值按遞增進行排 序。接著設置一個閥值MAX，初始化其值為乘客提出拼車請求時的費用約束r maxMre，作為最 終成為匹配成功司機的拼車成本的上邊界。基於skyline計算過程（即拼車費用與等待時 間），MAX值將逐漸縮小，這樣使得更多的滿足乘客時間和費用約束的司機被過濾掉，即這 些司機不能作為skyline結果返回。
[0097] 3. 2. 3候選司機篩選
[0098] 該篩選過程是迭代式的。在每一次迭代過程當中，需要首先從匹配表中挑選離乘 客最近的一個司機d，可在路網上執行增量K近鄰算法（Incremental K nearest neighbor) 獲取。然後計算他的實際Pickup值。司機d的Pickup值只可能是以下四種情況之一：
[0099] A1司機d的PickUp>rmax Time，即司機d無法按時接到乘客。此情況下會立即終止 接下來的篩選流程，將匹配表中包括d在內的所有司機刪除。因為其他司機相比於司機d， 離乘客的起點更遠，無法滿足乘客的時間約束。
[0100] 42司機(1的？^1〇1口〈1'_^，但(1根據公式3所計算出的拼車費用大於]\^乂。因為 不滿足費用約束，司機d將會被從匹配表中刪除。一同被排除的還有匹配表中位於司機d 之後的所有司機。因為根據公式3計算，雖然其他司機的RiderTrip值與司機d相同，但是 他們的Pickup和EuclideanReturn-DriverTrip的值都大於d，所以總拼車費用也必然大於 d 和 MAX。
[0101] A3司機d的Pickup〈rmax_Time，且d根據公式3所計算出的拼車費用也小於MAX,但 是d使用公式1(需要計算實際Return)計算出的拼車費用大於MAX。因此，d不能滿足拼 車費用約束，不能成為候選司機。
[0102] A4以上三種情況之外。d將成為既能滿足時間約束又能滿足費用約束的候選司 機。接著我們將MAX的值改為司機d的實際的拼車費用（根據公式1計算得到）。然後將 該司機從匹配表中刪除，最後進入下一個迭代篩選過程。更改MAX的值是因為最終返回的 匹配結果要求是skyline關係，即新的候選司機相對前一個候選司機來說，由於其等待時 間要比前一個司機長，所以其造成的拼車費用要比上一個候選司機小才能作為最終結果返 回。
[0103] 圖1表示動態拼車匹配方法第一階段過程圖。首先以乘客r的起點為圓心，按最 大等待時間轉化的歐氏距離作為半徑，將該圓Q K內所有司機的選出，並將這些司機的信息 加入到匹配表中。然後，對於匹配表中的每一位司機，根據公式2計算他們的拼車費用。費 用大於r max_P_的司機，將會被從匹配表中刪除。
[0104] 圖2表示動態拼車匹配方法第二階段過程圖。首先計算出匹配表中每一位司機的 EuclideanReturn-DriverTrip值，然後依據此值的遞增順序對所有司機進行排序，並設置 MAX的值為乘客的rMx p_。然後，使用K近鄰算法計算出表中離乘客最近的司機d，並算出 d的Pickup值，若此Pickup不能滿足乘客的時間約束rmax_pHee,篩選過程將立即停止，並將 當前的候選司機（或者無候選司機）的信息返回乘客。這是因為剩下的司機必然比司機d 的位置更遠，無法滿足乘客的時間約束。通過上一步篩選後，d將會被按照公式3計算拼車 費用，如果費用不滿足MAX約束，則將匹配表中d和位於d以下的所有司都機排除。對於通 過了 Pickup階段篩選的司機d，需要計算他們的實際Return值，並根據公式1重新計算拼 車費用，如果不滿足MAX約束，d也將被刪除。通過Pickup和Return階段篩選的司機d將 會成為第一位候選司機（或替換原候選司機），然後被從匹配表中刪除。接著將MAX的值更 新為d的實際拼車費用。至此，司機d的半歐式距離篩選結束。系統將使用K近鄰算法選 擇下一個司機進行Pickup，Return和skyline篩選。以此過程篩選匹配表中的所有司機， 直到匹配表為空。最後並將候選司機（一個或沒有）的信息返回給乘客。
[0105] 下面，通過圖3-圖9對一個具體的例子進行整個匹配過程的具體實施描述。
[0106] 圖3表示基於乘客等待時間歐式距離的範圍查詢示例。假設乘客r (白點表示） 的最大等待時間為15分鐘，那麼按照司機（黑點表示）和乘客之間的歐氏距離計算，圓QK 中能夠15分鐘內到達的司機為.. d6。
[0107] 圖4表示基於圖3範圍查詢結果的匹配表。在圖3中所選出的dlCl2d 3. ..d6將會被 填入到匹配表中。匹配表中司機的RiderTrip欄位可以由司機表中的對應欄位直接複製而 來。
[0108] 圖5表示基於歐氏距離的拼車成本篩選示例圖。乘客的rmax_time = 15, rmax_pHee = 30, RiderTrip = 12 ;司機的 EuclideanPickup，EuclideanReturn 和 DriverTrip 分別如表 中所示。司機屯將會因拼車費用大於30被從匹配表中刪除。
[0109] 圖6為匹配表排序示意圖。由於乘客的rmax_time = 15,rmax_pHee = 30,RiderTrip = 12。因此設置MAX = rmaxJttiee = 30。將所有匹配表中的司機按EuclideanReturn-DriverTrip 值進行遞增排序後，d6排在了匹配表的第一個。
[0110] 圖7為替換EuclideanPickup為真實路徑Pickup後的篩選示意圖。圖中以逆時 針的順序分別展示了初始條件，公式2,公式3,公式1和原匹配表和篩選之後的匹配表。首 先用K近鄰算法找到離乘客距離最小的司機d 3，並計算d3的Pickup = 8. 7〈15,因此d3可 以準時接到乘客。下一步，按照公式3計算d3的拼車費用（8. 7+2*12+7. 5-10) >30 (MAX)。d3 因為不能滿足乘客的拼車費用約束被排除。而匹配表中位於d3之下的司機也被排除。此 時匹配表中僅剩下司機d 6和d2。
[0111] 圖8為替換EuclideanReturn為真實路徑Return後的篩選示意圖。用K近鄰算 法選出匹配表中離乘客最近的司機d5,（15能夠通過Pickup階段篩選。於是接著計算(1 5的 Return，並按照公式1計算d5的新拼車費用9. 1+2*12+7. 6-10 = 30. 7>30 (MAX)，因此將d5 也從匹配表中排除。
[0112] 圖9為skyline司機篩選示意圖。司機d6能夠通過之前所有步驟的篩選，成為 了第一個出現的備選司機。d 6的拼車費用為27. 2, Pickup為9. 3,因此將MAX的值設置為 27. 2。如圖，假設下一個產生的候選司機為d2，顯然d2的Pickup大於d6。接著計算d 2拼車 費用9. 4+2*12+5-9. 2>MAX(27. 2)。根據skyline比較法，因為d2的Pickup值已經大於d6， 若(1 2的拼車費用比d6還大的話，d2自然就不會被考慮。因此將(12從匹配表中刪除。將此 時匹配表為空，半歐式距離篩選結束。返回候選司機d 6。
【權利要求】
1. 一種基於時間與費用約束的動態拼車匹配方法，包括： 步驟1，建立動態拼車匹配模型 作為動態拼車僅有的兩個參與角色，司機與乘客在匹配時均有各自的起始位置與終點 位置，默認起點與終點間的路線為最短路徑；為方便描述，使用d表示司機，r表示乘客， RiderTrip和DriverTrip分別對應司機與乘客在匹配前各自的路線，路線長度又可轉換成 相應的費用成本；在匹配過程中，乘客和司機拼車費用的計算方式決定了匹配方法的設計； 考慮到司機可能需要偏離原計劃路線，通過繞道去接乘客或送乘客到目的地，最終乘客應 付給司機的費用中不僅包含拼車後走的路程，還要包含司機繞道所產生的成本，下面給出 拼車費用的表示方式 ： Price (d, r) = RiderTrip+Detour 其中，Price(d，r)表示拼車費用；RiderTrip表示拼車後共同走的路程，即乘客的路 線；Detour表示司機相對其原始路線多走的路程，即繞道路程，其計算方式如下： Detour (d, r) = Pickup+RiderTrip+Return - DriverTrip 其中，Pickup是司機起點與乘客起點間的路程，即司機去接乘客時的費用；Return表 示司機目的地與乘客目的地間的路程距離，即司機在送完乘客時返回的費用； 基於上述關係，可進一步得到計算拼車費用的如下公式： Price (d, r) = Pickup+2*RiderTrip+Return - DriverTrip (1) 公式1中右邊的計算單元均是拼車匹配模型中的基本費用單元，在隨後的匹配方法設 計當中將被使用；下面，從乘客角度出發，給出拼車匹配模型的定義； 定義1.給定一個司機集合D和一個乘客r，動態拼車匹配旨在D中找到一個子集合D'， 並且對於D '中的任意一個司機，需要滿足如下約束： ?時間約束：Pickup (d, r) rmax Time，即司機d無法按時接到乘客；此情況下會立即終止接下來 的篩選流程，將匹配表中包括d在內的所有司機刪除；因為其他司機相比於司機d，離乘客 的起點更遠，無法滿足乘客的時間約束； A2司機d的Pickup〈rmax_Time，但d根據公式3所計算出的拼車費用大於MAX ;因為不滿 足費用約束，司機d將會被從匹配表中刪除；一同被排除的還有匹配表中位於司機d之後 的所有司機；因為根據公式3計算，雖然其他司機的RiderTrip值與司機d相同，但是他們 的Pickup和EuclideanReturn-DriverTrip的值都大於d，所以總拼車費用也必然大於d和 MAX ； A3司機d的Pickup〈rmax_Time，且d根據公式3所計算出的拼車費用也小於MAX,但是d 使用公式1計算出的拼車費用大於MAX;因此，d不能滿足拼車費用約束，不能成為候選司 機； A4以上三種情況之外；d將成為既能滿足時間約束又能滿足費用約束的候選司機；接 著我們將MAX的值改為根據公式1計算得到的司機d的實際的拼車費用；然後將該司機從 匹配表中刪除，最後進入下一個迭代篩選過程；更改MAX的值是因為最終返回的匹配結果 要求是skyline關係，即新的候選司機相對前一個候選司機來說，由於其等待時間要比前 一個司機長，所以其造成的拼車費用要比上一個候選司機小才能作為最終結果返回。
【文檔編號】G08G1/00GK104217249SQ201410311685
【公開日】2014年12月17日 申請日期:2014年7月2日 優先權日:2014年7月2日
【發明者】曹斌, 趙立為, 範菁 申請人:浙江工業大學