[發(fā)明專利]派單方法、裝置及存儲介質(zhì)

在審

• 申請?zhí)枺?/td>: 202110040388.8
• 申請日: 2021-01-13
• 公開（公告）號: CN112749899A
• 公開（公告）日: 2021-05-04
• 發(fā)明（設(shè)計）人: 李世偉;劉恬恬;寧忠忠;宋子龍
• 申請（專利權(quán)）人: 叮當快藥科技集團有限公司
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q10/08;G06Q30/06;G06K9/62
• 代理公司: 北京知果之信知識產(chǎn)權(quán)代理有限公司 11541
• 代理人: 卜榮麗;朱靜謙

本發(fā)明提供一種派單方法、裝置及存儲介質(zhì)，包括：獲取當前各個未分配訂單的剩余考核時間以及可用騎手；將所述未分配訂單作為節(jié)點，對各個節(jié)點按照其自身類別進行聚類，過濾掉只有一個節(jié)點且剩余考核時間大于預(yù)設(shè)值的訂單，得到訂單的最終聚類；基于最終聚類與可用騎手得到成本矩陣，將最小成本對應(yīng)的類別訂單交付至成本矩陣選取的最佳騎手配送后，更新成本矩陣，直到遍歷完所有的類別。本發(fā)明方案，利用基于地理信息的層次聚類算法進行訂單合包，然后生成成本矩陣進而選取最佳騎手配送。派單結(jié)果更符合騎手行為習(xí)慣，提升騎手體驗和騎手執(zhí)行配送任務(wù)的效率。并且派單目標函數(shù)預(yù)估更準確，提升調(diào)度系統(tǒng)KPI指標及訂單送達的準時率。

技術(shù)領(lǐng)域

本發(fā)明涉及派單技術(shù)，尤其涉及一種派單方法、裝置及存儲介質(zhì)。

背景技術(shù)

外賣配送主要的特點是并發(fā)高、延時低。在騎手智能調(diào)度系統(tǒng)中，新訂單需要實時指派給最合適的騎手。騎手身上一般背負多個訂單，派新單之前需要對當前騎手身上的舊訂單和可能的新訂單進行計算，根據(jù)成本矩陣結(jié)果選擇超時最少、路程最短的訂單分給相應(yīng)的騎手。所以成本矩陣的定義對調(diào)度系統(tǒng)派單的準確性有重要影響。

現(xiàn)有的訂單分配方法使用貪婪啟發(fā)式方法，以騎手執(zhí)行路徑中所有取送任務(wù)的總超時時長與總路程的加和作為目標函數(shù)，通過計算當前時刻未分配訂單與可用騎手之間構(gòu)成的成本矩陣，找出目標函數(shù)的最小值，并將該筆訂單指派給最合適的騎手。然后，刪除已分配訂單，更新成本矩陣，直到遍歷完所有未分配訂單。

在實際配送場景中，因為訂單的時效要求存在差異性，區(qū)域運力與時間存在相關(guān)關(guān)系，配送實際情況變得復(fù)雜。現(xiàn)有的基于貪婪的啟發(fā)式算法無法準確評估配送的成本，從而無法為派單提供準確的依據(jù)，導(dǎo)致派單結(jié)果不準確。這將降低調(diào)度系統(tǒng)的運行效率，造成騎手運力浪費，降低用戶體驗。現(xiàn)有配送派單方法還存在運算時間長的問題，即運算時間隨路徑中任務(wù)點的增加呈現(xiàn)指數(shù)增長，若路徑中任務(wù)點數(shù)量過多則運算時間會很長，進而導(dǎo)致派單時間較長。

發(fā)明內(nèi)容

本發(fā)明實施例提供一種派單方法、裝置及存儲介質(zhì)，可以提升調(diào)度派單的準確度、減少系統(tǒng)的派單時間、提升配送調(diào)度系統(tǒng)的配送效率，改善用戶體驗。

本提案提出一種基于兩階段快速啟發(fā)式的藥品配送派單方法，。

本發(fā)明實施例的第一方面，提供一種派單方法，包括：

獲取當前各個未分配訂單的剩余考核時間以及可用騎手；

將所述未分配訂單作為節(jié)點，對各個節(jié)點按照其自身類別進行聚類，過濾掉只有一個節(jié)點且剩余考核時間大于預(yù)設(shè)值的訂單，得到訂單的最終聚類；

基于所述最終聚類與可用騎手得到成本矩陣，將最小成本對應(yīng)的類別訂單交付至成本矩陣選取的最佳騎手配送后，更新成本矩陣，直到遍歷完所有的類別。

可選地，在第一方面的一種可能實現(xiàn)方式中，所述獲取當前各個未分配訂單的剩余考核時間包括：

獲取訂單的預(yù)計到達時間ETA以及當前時刻T，基于以下公式計算所述剩余考核時間auditTime，

auditTime＝ETA–T。

可選地，在第一方面的一種可能實現(xiàn)方式中，獲取當前各個未分配訂單的剩余考核時間以及可用騎手包括：

獲取當前時刻每個騎手的背單量，將背單量小于預(yù)設(shè)量的騎手作為可用騎手。

可選地，在第一方面的一種可能實現(xiàn)方式中，所述將所述未分配訂單作為節(jié)點，對各個節(jié)點按照其自身類別進行聚類，過濾掉只有一個節(jié)點且剩余考核時間大于預(yù)設(shè)值的訂單，得到訂單的最終聚類包括：

將當前未分配的訂單作為節(jié)點，設(shè)節(jié)點的約束條件為范圍與剩余考核時間的加權(quán)之和，公式如下，

D＝λ₁dist+λ₂auditTime