[發明專利]適于乘客等待時間分布隨時間變化的網約車訂單分配方法

有效

• 申請號: 202011050958.3
• 申請日: 2020-09-29
• 公開（公告）號: CN112288233B
• 公開（公告）日: 2023-09-12
• 發明（設計）人: 鄭嘉琦;陳偉榮;陳貴海
• 申請（專利權）人: 南京大學
• 主分類號: G06Q10/0631
• 分類號: G06Q10/0631;G06Q30/0601;G06Q30/0645;G06N3/049;G06N3/084;G06N3/092
• 代理公司: 南京鐘山專利代理有限公司 32252
• 代理人: 陳月菊

本發明公開了一種適于乘客等待時間分布隨時間變化的網約車訂單分配方法，包括：根據乘客等待時間分布變化范圍計算出該分布變化范圍下批處理算法對應的最優的匹配間隔并對不同的乘客等待時間分布訓練不同的深度強化學習模型，將上述具有不同匹配間隔的批處理算法和適應不同乘客等待時間分布的深度強化學習模型合并為一個算法集合；當有訂單到來時，采用預設的選擇模型在算法集合中選擇其中一個算法進行分配訂單，根據收益反饋對選擇模型中的參數進行更新；結合收益反饋檢測乘客等待時間分布是否變化，若發生變化則重啟選擇模型并清空反饋記錄。本發明能夠隨乘客等待時間和數目分布變化而不斷調整分配從而最大化網約車平臺收益。

技術領域

本發明涉及調度規劃技術領域，具體而言涉及一種適于乘客等待時間分布隨時間變化的網約車訂單分配方法。

背景技術

隨著經濟的飛速發展，公共交通存在的不夠自主性和個性化的短板日益凸顯。在已有的公共交通無法滿足所有人的需求下，網約車平臺的出現，滿足了人們的個性化出行需求并且填補了公共交通的短板。如何高效地分配訂單給網約車不僅影響乘客的體驗，也會影響網約車平臺的收益。

網約車訂單分配問題可以被視為在線二分匹配問題：等待的乘客屬于二分圖的一邊的節點，等待的網約車屬于另一邊的節點，當網約車和乘客之間存在匹配可能時對應節點直接存在邊相連接，其匹配的收益作為邊的權重，當等待時間內還未給節點進行匹配，則節點消失(即乘客取消訂單)，其目標在于將兩邊的節點進行不可撤回的匹配使得總收益最大。可以預見到，乘客的等待時間分布將直接影響匹配策略的選擇。當愿意等待較長時間的乘客較多時，等待較長的一段時間再進行匹配獲取的收益會高于直接的貪心匹配。

因此考慮等待時間分布來制定分配方案能夠有效地提升網約車平臺的收益以及乘客的體驗。當在早高峰時，打車的乘客大多需要盡早到達公司單位，因此并不愿意等待較長的匹配時間，而當在中午時，乘客大多并無急事因此愿意等待較長匹配時間的乘客也較多。關于等待時間分布的變化已有較多的研究，即等待時間會被天氣等難以預測的因素影響。同時相比于數量分布，由于不知道已匹配乘客的剩余等待時間，等待時間分布總是難以直接進行統計的。因此想通過直接觀察或者統計長時間的歷史數據來預測等待時間分布變化進行匹配策略的調整是難以實行的。

由于等待時間的分布難以被直接統計，因此傳統的匹配策略總是不考慮等待時間分布發生變化的問題。換而言之，傳統的訂單匹配策略總在某些分布下表現較好而當分布變化時則無法保持原有的高效性。從另一方面，傳統的難以適應變化的分布的匹配策略也極大的影響了乘客的使用體驗。

發明內容

本發明針對現有技術中的不足，提供一種適于乘客等待時間分布隨時間變化的網約車訂單分配方法，當檢測到分布發生變化時重新在算法集合中選擇匹配算法以達到在乘客時間分布不斷變化下仍能最大化網約車平臺收益的目的。

為實現上述目的，本發明采用以下技術方案：

一種適于乘客等待時間分布隨時間變化的網約車訂單分配方法，所述訂單分配方法包括以下步驟：

S1，根據乘客等待時間分布變化范圍計算出該分布變化范圍下批處理算法對應的最優的匹配間隔并對不同的乘客等待時間分布訓練不同的深度強化學習模型，將上述具有不同匹配間隔的批處理算法和適應不同乘客等待時間分布的深度強化學習模型合并為一個算法集合；

S2，當有訂單到來時，采用預設的選擇模型在步驟S1合并得到的算法集合中選擇其中一個算法進行分配訂單，根據收益反饋對選擇模型中的參數進行更新；

S3，結合步驟S2的收益反饋檢測乘客等待時間分布是否變化，若發生變化則重啟選擇模型并清空反饋記錄。

為優化上述技術方案，采取的具體措施還包括：

進一步地，步驟S1中，所述對不同的乘客等待時間分布訓練不同的深度強化學習模型的過程包括：