[發明專利]拼車訂單分配方法及系統

在審

• 申請號: 201711397930.5
• 申請日: 2017-12-21
• 公開（公告）號: CN109948874A
• 公開（公告）日: 2019-06-28
• 發明（設計）人: 鄭立彬;陳雷;葉杰平
• 申請（專利權）人: 北京嘀嘀無限科技發展有限公司
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q50/30
• 代理公司: 成都七星天知識產權代理有限公司 51253
• 代理人: 楊永梅

1.一種拼車訂單分配方法，其特征在于，包括：

獲取待分配的拼車訂單集合；

獲取待分配的車輛集合；

基于訂單總收益從待分配的拼車訂單集合和待分配的車輛集合中，確定滿足預定限制條件的訂單-車輛對。

2.根據權利要求1所述的方法，其特征在于，所述訂單總收益為分配得到的所有訂單-車輛對的收益總和。

3.根據權利要求1或2所述的方法，其特征在于，所述預定限制條件，包括至少以下條件之一：

將所述訂單分配給相應的車輛后，繞路率不大于繞路閾值；

將所述訂單分配給相應的車輛后，接駕時間不大于時間閾值；以及

車輛中的乘客數不大于所述車輛的容量。

4.根據權利要求1或2所述的方法，其特征在于，根據至少以下算法之一，確定所述訂單-車輛對：

貪心算法；或

基于二分圖的訂單包與車輛匹配算法。

5.根據權利要求4所述的方法，其特征在于根據貪心算法，確定所述訂單-車輛對包括：

步驟a：將待分配的拼車訂單集合中的訂單逐一與待分配的車輛集合中的車輛進行配對，得到全部的可行配對，所有的可行配對構成一個配對池，計算每個可行配對的收益，所述可行配對指訂單-車輛對滿足所述預定限制條件；

步驟b：確定配對池中收益最大的訂單A-車輛A對，將訂單A分配給車輛A，從配對池中移除所述訂單A-車輛A對，更新該車輛A的行駛線路；

步驟c：將配對池中所有包含所述訂單A的其他配對移除；對于配對池中所述車輛A的其他配對：根據所述更新后的行駛路線更新其收益，并移除不再可行的配對；

對配對池中剩余的配對重復執行步驟b和步驟c，每執行一次步驟b和步驟c，得到一個最優配對，直到某次循環中配對池中收益最大的訂單-車輛對的收益為負數時，結束循環。

6.根據權利要求4所述的方法，其特征在于，基于二分圖的訂單包與車輛匹配算法，確定所述訂單-車輛對包括：

在所述預定限制條件下，根據訂單包的總收益將所述待分配的訂單集合中的訂單進行組合，得到多個訂單包，每個訂單包是多個訂單的組合或只包含一個不適宜與其他訂單組合的單個訂單；

基于訂單包與待分配的車輛集合中的車輛構建二分圖；和

計算所述二分圖的最大匹配權重，將每個訂單包與其最大邊權對應的車輛進行配對。

7.根據權利要求2所述的方法，其特征在于，訂單-車輛對的收益為訂單價格與支付給司機的成本之間的差值。

8.一種拼車訂單的分配系統，其特征在于，包括：

訂單獲取模塊，用于獲取待分配的拼車訂單集合；

車輛獲取模塊，用于獲取待分配的車輛集合；

配對模塊，用于基于訂單總收益從待分配的拼車訂單集合和待分配的車輛集合中，確定滿足預定限制條件的訂單-車輛對。

9.根據權利要求8所述的系統，其特征在于，所述訂單總收益為分配得到的所有訂單-車輛對的收益總和。

10.根據權利要求8或9所述的系統，其特征在于，所述預定限制條件，包括至少以下條件之一：

將所述訂單分配給相應的車輛后，繞路率不大于繞路閾值；

將所述訂單分配給相應的車輛后，接駕時間不大于時間閾值；以及

車輛中的乘客數不大于所述車輛的容量。

11.根據權利要求8或9所述的系統，其特征在于，根據至少以下算法之一，確定所述訂單-車輛對：

貪心算法；或

基于二分圖的訂單包與車輛匹配算法。