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

有效

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

本發明為一種可預約的出租車匹配方法，包括以下幾個步驟：1)初始化路網數據，構建時間依賴的速度網絡；2)車輛狀態實時更新到系統，乘客發起出行請求并發送到中心服務器進行處理；3)服務器將已就緒請求和空載的出租車抽象成節點建立匹配二分圖，并計算乘客請求和出租車配對的效能；4)將系統中的出租車匹配問題轉化成最小代價流問題，產生最佳的“出租車?乘客”匹配方案；5)根據匹配方案，系統發送通知給請求成功的乘客，出租車則前往指定地點接乘客；6)跳轉到步驟2)，周期性地增量更新請求和匹配。本方法和系統可求解出租車預約請求和實時請求的調配問題，減少乘客等車時間，提高出租車的行駛效率，提高效益。

技術領域

本發明涉及響應式交通領域，特別是一種可預約的出租車匹配方法。

背景技術

需求響應式交通系統(Demand Responsive Transit System)是公交、傳統出租車等出行方式的重要的替代方案。系統由乘客、車輛以及調度服務商三方組成。調度服務商，如Uber和滴滴打車，對接大量的車輛和乘客。乘客實時發出請求，通過系統匹配，尋找最合適的車輛進行提供“一對一”的服務。

然而，目前大多數的調度服務系統，都僅能處理隨機和實時的顧客請求，對于顧預約請求則支持得還很不夠。這主要是由于預約調度具有一些內在的困難和挑戰性。首先，預約出行很重要的一點就是要接送準時。人們使用預約車的通常原因，是有一些重要的活動(如乘火車或飛機)需要安排。若車輛遲到使得乘客等待，預約乘客的服務體驗會相當差。其次，城市道路的復雜性，使得目前仍然很難精確的預估車輛在路上的行駛時間。因此，預約的車輛如果要準時到達，必須在安排的時候預留了較寬松的時間提早到達。但這同時也帶來另外的一些問題。比如提前到達的預約車輛需要尋找停車場所，但停車場所有限；而且，預約車服務需要更多的時間和精力，成本也會增加，這會減少它的市場份額。所有這些因素，使得目前的車輛調度系統要么不支持預約車服務，要么該服務是獨立于目前調度系統來進行的。

本發明方法把預約請求和實時請求統一納入考慮范圍，全局求解的“乘客-車輛”的匹配問題，合理分配出租車資源，可減少乘客的等待時間，提高出租車的行駛效率。

發明內容

本發明的主要目的在于克服現有技術中的上述缺陷，提出一種可預約的出租車匹配方法，能夠滿足乘客預約乘車的需求，全局地調配出租車資源，合理地安排行駛路線。

本發明采用如下技術方案：

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

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

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

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

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

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

6)跳轉到步驟(2)。

步驟2)中，所述出行請求的數據格式包括如下：