[發明專利]用于分配服務資源的方法、裝置和計算機存儲介質

有效

• 申請號: 201810378529.5
• 申請日: 2018-04-25
• 公開（公告）號: CN110399993B
• 公開（公告）日: 2023-07-04
• 發明（設計）人: 馮文中
• 申請（專利權）人: 蔚來（安徽）控股有限公司
• 主分類號: G06Q10/02
• 分類號: G06Q10/02;G06Q10/0631
• 代理公司: 中國專利代理(香港)有限公司 72001
• 代理人: 李湘;劉春元

1.一種用于分配服務資源的方法，其中，所述服務資源由一個或多個資源點在多個時間窗口內提供，其特征在于，包含下列步驟：

A)基于多個分配方案的調整成本確定優選的分配方案，其中，在每個所述分配方案中，多個服務請求的每一個被分配一個資源點的多個可用的時間窗口的其中一個，每個所述分配方案的調整成本取決于服務請求在該分配方案中所分配的時間窗口相對于先前分配方案中所分配的時間窗口的變化；以及

B)輸出優選的分配方案，

其中，步驟A)包括下列步驟：

A1)基于每個服務請求的所期望的時間窗口，構建該服務請求與一個或多個資源點的可用的時間窗口的組合，其中，每個所述分配方案包含關聯于每個服務請求的單個組合；

A2)賦予每個組合相應的權重因子以反映當前分配的時間窗口相對于先前分配方案中所分配的時間窗口的變化

A3)對于每個所述分配方案，基于該分配方案內的各組合的權重因子確定相應的調整成本；以及

A4)確定對應于最小調整成本的分配方案并將其作為優選的分配方案，

其中，將所述服務請求和所述資源點的可用的時間窗口表示為網絡流圖中的節點，將服務請求與資源點的可用的時間窗口的組合表示為網絡流圖中的有向邊，并且通過在所述網絡流圖中求解最小費用最大流來確定對應于最小的調整成本的分配方案。

2.如權利要求1所述的方法，其中，包含先于步驟A)執行的下列步驟：

如果確定所述多個服務請求的每一個都能夠被分配至少一個可用的時間窗口，則執行步驟A)。

3.如權利要求1所述的方法，其中，所述服務資源為提供更換電動汽車電池的服務的能力，所述資源點為用于更換電動汽車電池的換電設備，并且所述時間窗口對應于用戶預約的換電時間段。

4.如權利要求3所述的方法，其中，每個換電設備在一個時間窗口內能夠為一輛或多輛電動汽車更換電池。

5.如權利要求1所述的方法，其中，在步驟A2)中，對于當前分配的時間窗口相對于先前分配方案中所分配的時間窗口無變化的服務請求，其被賦予第一權重因子，對于當前分配的時間窗口相對于先前分配方案中所分配的時間窗口發生變化的服務請求，其被賦予第二權重因子，所述第一權重因子小于第二權重因子。

6.如權利要求1所述的方法，其中，通過利用下列算法中的一種在所述網絡流圖中求解最小費用最大流：Bellman-Ford算法、SPFA算法、Dinic算法和ISAP算法。

7.一種用于分配服務資源的裝置，其中，所述服務資源由一個或多個資源點在多個時間窗口內提供，其特征在于，所述裝置包含：

第一模塊，用于確定多個分配方案的調整成本的優化值，其中，在每個所述分配方案中，多個服務請求的每一個被分配一個資源點的多個可用的時間窗口的其中一個，每個所述分配方案的調整成本取決于服務請求在該分配方案中所分配的時間窗口相對于先前分配方案中所分配的時間窗口的變化；以及

第二模塊，用于將與所述優化值相關聯的分配方案確定為優選的分配方案，

其中，所述第一模塊通過執行下列步驟確定所述優化值：

A1)基于每個服務請求的所期望的時間窗口，構建該服務請求與一個或多個資源點的可用的時間窗口的組合，其中，每個所述分配方案包含關聯于每個服務請求的單個組合；

A2)賦予每個組合相應的權重因子以反映當前分配的時間窗口相對于先前分配方案中所分配的時間窗口的變化

A3)對于每個所述分配方案，基于該分配方案內的各組合的權重因子確定相應的調整成本；以及

A4)確定對應于最小調整成本的分配方案并將其作為優選的分配方案，

其中，將所述服務請求和所述資源點的可用的時間窗口表示為網絡流圖中的節點，將服務請求與資源點的可用的時間窗口的組合表示為網絡流圖中的有向邊，并且通過在所述網絡流圖中求解最小費用最大流來確定對應于最小的調整成本的分配方案。