[發明專利]面向建筑內部的配送路徑優化方法及裝置

有效

• 申請號: 201810039882.0
• 申請日: 2018-01-16
• 公開（公告）號: CN108171387B
• 公開（公告）日: 2021-01-22
• 發明（設計）人: 崔峰銘;李樂飛
• 申請（專利權）人: 清華大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙) 11201
• 代理人: 張潤

1.一種面向建筑內部的配送路徑優化方法，其特征在于，包括以下步驟：

獲取建筑物的內部構造以生成所述建筑物的立體交通網絡圖；

對配送時間、配送人員的數量和配送人員的體力消耗分別賦予權重值，且對所述立體交通網絡圖設置邊權值以生成空間距離系數矩陣、通行時間系數矩陣和體力消耗系數矩陣；

獲取具有容量約束的模型的約束條件，并且將所述容量約束轉化為目標函數的懲罰項；以及

獲取所述建筑物的配送路徑優化模型，并通過兩階段算法和Tabu Search算法求解最優路線，以為配送人員提供當前最優的配送路線；

所述配送路徑優化模型為：

其中，N為網絡中的所有節點的集合，K為所有配送人員的集合，i為交通網絡中編號為i的節點，j為交通網絡中編號為j的節點，k為編號為k的配送人員，x_ijk為第k個配送人員是否經過i-j路段，y_jk為第k個配送人員是否配送了第j個顧客，為配送人員從i運動到j所要消耗的體力，為配送人員從i運動到j所花費的廣義時間，x_iok為第k個配送人員是否回到原點，V_f為網絡中的虛擬節點集合，S為網絡節點的任意子集。

2.根據權利要求1所述的面向建筑內部的配送路徑優化方法，其特征在于，通過將所述建筑物的CAD結構圖輸入系統模型獲取所述內部構造，以搭建出所述建筑物的立體交通網絡圖。

3.根據權利要求2所述的面向建筑內部的配送路徑優化方法，其特征在于，在所述立體交通網絡圖中，每個實心節點代表客戶位置，不同的顏色表示不同的樓層，空心節點表示交通路徑的分叉口，節點之間的連線表示兩點之間存在直接到達的交通路徑，樓層連邊表示樓層之間的交通路徑，其中，樓層實線代表樓梯，樓層虛線代表電梯。

4.根據權利要求1所述的面向建筑內部的配送路徑優化方法，其特征在于，懲罰值函數表示如下：

其中，C為配送人員實際攜帶的配送商品數量，C_m為配送人員能夠攜帶的最大商品數量，e為懲罰系數。

5.一種面向建筑內部的配送路徑優化裝置，其特征在于，包括：

獲取模塊，用于獲取建筑物的內部構造以生成所述建筑物的立體交通網絡圖；

生成模塊，用于對配送時間、配送人員的數量和配送人員的體力消耗分別賦予權重值，且對所述立體交通網絡圖設置邊權值以生成空間距離系數矩陣、通行時間系數矩陣和體力消耗系數矩陣；

優化模塊，用于獲取具有容量約束的模型的約束條件，并且將所述容量約束轉化為目標函數的懲罰項；以及

計算模塊，用于獲取所述建筑物的配送路徑優化模型，并通過兩階段算法和TabuSearch算法求解最優路線，以為配送人員提供當前最優的配送路線；

所述配送路徑優化模型為：

其中，N為網絡中的所有節點的集合，K為所有配送人員的集合，i為交通網絡中編號為i的節點，j為交通網絡中編號為j的節點，k為編號為k的配送人員，x_ijk為第k個配送人員是否經過i-j路段，y_jk為第k個配送人員是否配送了第j個顧客，為配送人員從i運動到j所要消耗的體力，為配送人員從i運動到j所花費的廣義時間，x_iok為第k個配送人員是否回到原點，V_f為網絡中的虛擬節點集合，S為網絡節點的任意子集。

6.根據權利要求5所述的面向建筑內部的配送路徑優化裝置，其特征在于，通過將所述建筑物的CAD結構圖輸入系統模型獲取所述內部構造，以搭建出所述建筑物的立體交通網絡圖。

7.根據權利要求6所述的面向建筑內部的配送路徑優化裝置，其特征在于，在所述立體交通網絡圖中，每個實心節點代表客戶位置，不同的顏色表示不同的樓層，空心節點表示交通路徑的分叉口，節點之間的連線表示兩點之間存在直接到達的交通路徑，樓層連邊表示樓層之間的交通路徑，其中，樓層實線代表樓梯，樓層虛線代表電梯。

8.根據權利要求5所述的面向建筑內部的配送路徑優化裝置，其特征在于，懲罰值函數表示如下：

其中，C為配送人員實際攜帶的配送商品數量，C_m為配送人員能夠攜帶的最大商品數量，e為懲罰系數。