[發明專利]一種公共自行車站點車輛優化配置的方法及裝置

有效

• 申請號: 202010317985.6
• 申請日: 2020-04-21
• 公開（公告）號: CN111523723B
• 公開（公告）日: 2023-04-28
• 發明（設計）人: 田志勇;霍靈瑜
• 申請（專利權）人: 北京物資學院
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q30/0645;G06Q50/30
• 代理公司: 北京卓嵐智財知識產權代理有限公司 11624
• 代理人: 郭智

1.一種公共自行車站點車輛優化配置的方法，其特征在于，所述方法包括：

根據站點的租車歷史數據和還車歷史數據，確定所述站點在當前配置周期中各個時段的租車概率分布和還車概率分布；

根據所述站點在當前配置周期中各個時段的租車概率分布和還車概率分布以及在租車需求和還車需求發生時站點車輛數量的變化規則，確定所述站點在當前配置周期中各個時段的車輛數量的狀態轉移概率矩陣；

根據所述站點在當前配置周期中各個時段的車輛數量的狀態轉移概率矩陣，確定在當前配置周期中各個時段進行不同車輛數量的配置下的損失服務成本；

根據所述在當前配置周期中各個時段進行不同車輛數量的配置的損失服務成本以及在當前配置周期中在各個時段進行車輛配置的單次成本，確定在當前配置周期的最優配置成本，以及最優車輛配置時段和最優配置數量；

所述根據在租車需求和還車需求發生時站點車輛數量的變化規則以及所述站點在當前配置周期中各個時段的租車概率分布和還車概率分布，建立所述站點在當前配置周期中各個時段的車輛數量的狀態轉移概率矩陣，包括：

根據所述站點在當前配置周期中各個時段的租車概率分布和還車概率分布，確定在當前配置周期中的時段t的租車概率分布的期望λ_t以及還車概率分布的期望μ_t；其中，t∈[1，T]，T為當前配置周期中劃分的總時段數；

建立所述站點在當前配置周期中的時段t中車輛數量的狀態轉移概率矩陣Q_t，Q_t表為：

其中，

p_t為時段t中一個需求事件發生，此事件為還車的概率，有

q_t＝1-p_t為時段t中一個需求事件發生，此事件為租車的概率，有

所述站點在當前配置周期中各個時段的租車概率分布和還車概率分布均為泊松分布，所述租車概率分布的期望λ_t為租車概率的泊松分布的泊松參數，所述還車概率分布的期望μ_t為還車概率的泊松分布的泊松參數；

所述根據所述站點在當前配置周期中各個時段的車輛數量的狀態轉移概率矩陣，確定在當前配置周期中各個時段進行不同車輛數量的配置下的損失服務成本，包括：

通過以下公式表示當前配置周期中在時段s配置車輛數量為i時，從s時段到t時段結束期間的損失服務成本U_s，t+1，i，i∈[0，N]，s∈[1，T]，t∈[s，T]，t+1表示t時段結束，且s≤t；N為所述站點的車樁數量：

U_s，t+1，i＝U_{s，t+1，i，0}+U_{s，t+1，i，N}；

其中，表示當前配置周期中在時段s配置車輛數量為i時，從s時段到t時段結束期間的租車損失服務成本，從s＝1..T、t＝s..T依次迭代計算出從s時段到t時段結束時的租車需求損失成本U_{s，t+1，i，0}，且有U_{s，s，i，0}＝0；

表示當前配置周期中在時段s配置車輛數量為i時，從s時段到t時段結束期間的還車損失服務成本，從s＝1..T、t＝s..T依次迭代計算出從s時段到t時段結束時的還車需求損失成本U_{s，t+1，i，N}，且有U_{s，s，i，N}＝0；其中，

表示當前配置周期中在時段s配置車輛數量為i時，到t時段結束時車輛數量為j的期望轉移概率，從s＝1..T、t＝s..T依次迭代計算出從s時段到其后每一時段的轉移概率，j∈[0，N]，當j＝0時，當j＝N時，

t∈[1，T]，為矩陣的元素，是Q_t矩陣的n次方，表示租車和還車需求共發生n次時的轉移概率矩陣；P{X_t＝n}是租車還車需求總數X_t為n的概率，

α_t表示時段t租車的單位損失服務成本；

β_t表示時段t還車的單位損失服務成本；

所述根據所述在當前配置周期中各個時段進行不同車輛數量的配置的損失服務成本以及在當前配置周期中在各個時段進行車輛配置的單次成本，確定在當前配置周期的最優配置成本，以及最優車輛配置時段和最優配置數量，包括：

通過下式確定在當前配置周期的從時段1到時段t結束時的最優配置成本V_1，t+1：

V_1，t+1＝min_i，s{V_1，s+C_s+U_s，t+1，i：i＝0..N，s∈[1，t]}，

從t＝1..T依次計算，直到t＝T結束，此時V_1，T+1即為當前配置周期的最優成本，其中V_1，1＝0，C_s為在當前配置周期中在時段s進行車輛配置的單次成本；

獲取在當前配置周期的最優成本V_1，T+1確定時，每一次迭代計算中s和i的取值；

將每一次迭代計算中s和i的取值確定為當前配置周期內的車輛配置時段和數量。

2.一種公共自行車站點車輛優化配置的裝置，其特征在于，所述裝置包括：

概率分布確定單元，用于根據站點的租車歷史數據和還車歷史數據，確定所述站點在當前配置周期中各個時段的租車概率分布和還車概率分布；

狀態轉移概率矩陣建立單元，用于根據所述站點在當前配置周期中各個時段的租車概率分布和還車概率分布以及在租車需求和還車需求發生時站點車輛數量的變化規則，建立所述站點在當前配置周期中各個時段的車輛數量的狀態轉移概率矩陣；

損失服務成本單元，用于根據所述站點在當前配置周期中各個時段的車輛數量的狀態轉移概率矩陣，確定在當前配置周期中各個時段進行不同車輛數量的配置下的損失服務成本；

配置確定單元，根據所述在當前配置周期中各個時段進行不同車輛數量的配置的損失服務成本以及在當前配置周期中在各個時段進行車輛配置的單次成本，確定在當前配置周期的最優配置成本，以及最優車輛配置時段和最優配置數量；

所述狀態轉移概率矩陣建立單元具體用于：

根據所述站點在當前配置周期中各個時段的租車概率分布和還車概率分布，確定在當前配置周期中的時段t的租車概率分布的期望以及還車概率分布的期望；其中，t∈[1，T]，T為當前配置周期中劃分的總時段數；

建立所述站點在當前配置周期中的時段t中車輛數量的狀態轉移概率矩陣Q_t，Q_t表為：

其中，

p_t為時段t中一個需求事件發生，此事件為還車的概率，有

q_t＝1-p_t為時段t中一個需求事件發生，此事件為租車的概率，有

所述站點在當前配置周期中各個時段的租車概率分布和還車概率分布均為泊松分布，所述租車概率分布的期望λ_t為租車概率的泊松分布的泊松參數，所述還車概率分布的期望μ_t為還車概率的泊松分布的泊松參數；

所述損失服務成本單元具體用于：

通過以下公式表示當前配置周期中在時段s配置車輛數量為i時，從s時段到t時段結束期間的損失服務成本U_s，t+1，i，i∈[0，N]，s∈[1，T]，t∈[s，T]，t+1表示t時段結束，且s≤t；N為所述站點的車樁數量：

U_s，t+1，i＝U_{s，t+1，i，0}+U_{s，t+1，i，N}；

其中，表示當前配置周期中在時段s配置車輛數量為i時，從s時段到t時段結束期間的租車損失服務成本，從s＝1..T、t＝s..T依次迭代計算出從s時段到t時段結束時的租車需求損失成本U_{s，t+1，i，0}，且有U_{s，s，i，0}＝0；

表示當前配置周期中在時段s配置車輛數量為i時，從s時段到t時段結束期間的還車損失服務成本，從s＝1..T、t＝s..T依次迭代計算出從s時段到t時段結束時的還車需求損失成本U_{s，t+1，i，N}，且有U_{s，s，i，N}＝0；其中，

表示當前配置周期中在時段s配置車輛數量為i時，到t時段結束時車輛數量為j的期望轉移概率，從s＝1..T、t＝s..T依次迭代計算出從s時段到其后每一時段的轉移概率，j∈[0，N]，當j＝0時，當j＝N時，

t∈[1，T]，為矩陣的元素，是Q_t矩陣的n次方，表示租車和還車需求共發生n次時的轉移概率矩陣；P{X_t＝n}是租車還車需求總數X_t為n的概率，

α_t表示時段t租車的單位損失服務成本；

β_t表示時段t還車的單位損失服務成本；

所述配置確定單元包括最優成本模塊，用于：

通過下式確定在當前配置周期的從時段1到時段t結束時的最優配置成本V_1，t+1：

V_1，t+1＝min_i，s{V_1，s+C_s+U_s，t+1，i：i＝0..N，s∈[1，t]}，

從t＝1..T依次計算，直到t＝T結束，此時V_1，T+1即為當前配置周期的最優成本，其中V_1，1＝0，C_s為在當前配置周期中在時段s進行車輛配置的單次成本；

獲取在當前配置周期的最優成本V_1，T+1確定時，每一次迭代計算中s和i的取值；

將每一次迭代計算中s和i的取值確定為當前配置周期內的車輛配置時段和數量。