[發明專利]一種可預約的出租車匹配方法

有效

• 申請號: 201811281523.2
• 申請日: 2018-10-23
• 公開（公告）號: CN109657820B
• 公開（公告）日: 2020-10-20
• 發明（設計）人: 賴永炫;楊詩鵬;楊帆
• 申請（專利權）人: 廈門大學;廈門大學深圳研究院
• 主分類號: G06Q10/02
• 分類號: G06Q10/02;G06Q10/04;G06Q30/06;G06Q50/30
• 代理公司: 廈門市首創君合專利事務所有限公司 35204
• 代理人: 張松亭;林燕玲

1.一種可預約的出租車匹配方法，其特征在于，包括如下步驟；

1)初始化路網數據，根據出租車歷史軌跡數據，構建時間依賴的速度網絡；

2)出租車實時更新所在的位置信息，空載/重載的狀態信息，當乘客發起出行請求至中心服務器，中心服務器根據出行請求的時間窗，將出行請求分為實時請求和預約請求，其中實時請求以及部分滿足條件的預約請求為已就緒請求，即可被調配；

3)中心服務器將已就緒請求和空載的出租車抽象成節點建立匹配二分圖，并計算已就緒請求和空載的出租車配對的效能；若該空載的出租車可在已就緒請求對應的時間窗內到達上車點，則將該空載的出租車和該已就緒請求對應的節點連上一條邊，并以該配對的效能的負值作為該邊的權重；

4)往匹配二分圖中加上兩個點Source和Sink，其中Source連接所有出租車節點，Sink連接所有已就緒請求節點，計算匹配二分圖的最小代價流方案，從而產生最佳的出租車-乘客匹配方案；

5)根據出租車-乘客匹配方案，發送通知給出行請求成功的乘客，出租車則前往指定的上車點接乘客，并送達目的地；

6)跳轉到步驟(2)。

2.如權利要求1所述的一種可預約的出租車匹配方法，其特征在于：步驟2)中，所述出行請求的數據格式包括如下：

q(o_lon，o_lat，d_lon，d_lat，t1，t2，t0)

其中，o_lon表示上車點經度，o_lat表示上車點緯度，d_lon表示終點經度，d_lat表示終點緯度，時間窗[t1,t2]表示乘客希望出租車來接送的最佳時間段，t0表示出行請求生成的時間；

根據出行請求q中的時間窗[t1,t2]，將出行請求分為兩類：實時請求Q₁和預約請求Q₂

其中T1是預設值，為作出預約請求的最小時間差；

通過另外一個預設值T2T1，將預約請求Q₂進行進一步劃分：

t′表示當前的系統時間，根據出行請求的分類，定義出已就緒請求的集合：

為等待請求，所述已就緒請求可進入匹配系統尋找合適的出租車并被匹配服務，等待請求處于等待狀態，直至其轉換為已就緒請求方可進行匹配。

3.如權利要求2所述的一種可預約的出租車匹配方法，其特征在于：在步驟3)中，所述效能公式如下：

u(c，q，t)＝α*serv(c，q，t)+(1-α)*trac(c，q，t)

其中，c表示出租車，u(c,q,t)表示匹配效能，serv(c,q,t)表示服務水平，trac(c,q,t)表示軌跡效能，α表示一個固定的比例系數，其取值范圍為[0,1]，t表示所述空載的出租車開始匹配給一個已就緒出行請求的時刻。

4.如權利要求3所述的一種可預約的出租車匹配方法，其特征在于：所述實時請求的服務水平serv(c,q,t)的計算方式如下：

其中，pt(c，q，t)為預估出租車接到乘客的時刻：

pt(c，q，t)＝t+w(c，q，t)+δ

其中，w(c，q，t)為預估出租車駛往所述上車點所用時間，δ≥0為出租車等待時間，其定義如下

等待時間δ表示若出租車在q.t1時刻前到達上車點，出租車需要等待的時間。

5.如權利要求3所述的一種可預約的出租車匹配方法，其特征在于：所述預約請求的服務水平serv(c,q,t)的計算公式如下：

其中，K是一個大于等于1的參數。

6.如權利要求3所述的一種可預約的出租車匹配方法，其特征在于：所述軌跡效能的計算公式如下：

其中，U是預設的固定參數，設置為出租車接到出行請求到接到乘客之前空駛的平均時間。