[發明專利]一種生成揀貨路徑的方法和裝置

在審

• 申請號: 201911094901.0
• 申請日: 2019-11-11
• 公開（公告）號: CN112785215A
• 公開（公告）日: 2021-05-11
• 發明（設計）人: 柯恒;董紅宇;李朝陽
• 申請（專利權）人: 北京京邦達貿易有限公司;北京京東振世信息技術有限公司
• 主分類號: G06Q10/08
• 分類號: G06Q10/08
• 代理公司: 中原信達知識產權代理有限責任公司 11219
• 代理人: 張一軍;王安娜

1.一種生成揀貨路徑的方法，其特征在于，包括：

根據各個巷道口點覆蓋的巷道和各個待揀儲位所在的巷道，得到初始巷道口點集合；

根據所述初始巷道口點集合中的各個巷道口點及其覆蓋的待揀儲位，生成初始的揀貨路徑；其中，所述揀貨路徑包括巷道口點路徑和儲位路徑；

對所述初始的揀貨路徑進行求解，迭代生成多條揀貨路徑，并從所述多條揀貨路徑中篩選出距離最短的揀貨路徑。

2.根據權利要求1所述的方法，其特征在于，根據各個巷道口點覆蓋的巷道和各個待揀儲位所在的巷道，得到初始巷道口點集合，包括：

根據各個巷道口點覆蓋的巷道和各個待揀儲位所在的巷道，分別確定覆蓋所述各個待揀儲位的巷道口點；

根據覆蓋所述各個待揀儲位的巷道口點，確定每個巷道口點覆蓋的待揀儲位；

基于每個巷道口點覆蓋的待揀儲位的數量，得到初始巷道口點集合。

3.根據權利要求2所述的方法，其特征在于，基于每個巷道口點覆蓋的待揀儲位的數量，得到初始巷道口點集合，包括：

按照每個巷道口點覆蓋的待揀儲位的數量由大到小的順序，對所述巷道口點進行排序；

篩選出覆蓋的待揀儲位的數量最大的巷道口點，將該巷道口點加入到初始巷道口點集合中，刪除該巷道口點覆蓋的待揀儲位；

重復執行篩選、加入和刪除的步驟，直到剩余的待揀儲位的數量為零，從而得到初始巷道口點集合。

4.根據權利要求1所述的方法，其特征在于，根據所述初始巷道口點集合中的各個巷道口點及其覆蓋的待揀儲位，生成初始的揀貨路徑，包括：

采用蟻群算法對所述初始巷道口點集合中的各個巷道口點進行求解，以生成巷道口點路徑；

采用枚舉方式或者節約算法對所述初始巷道口點集合中的各個巷道口點覆蓋的待揀儲位進行求解，以生成儲位路徑；

將所述巷道口點路徑和所述儲位路徑組合，得到初始的揀貨路徑。

5.根據權利要求1所述的方法，其特征在于，對所述初始的揀貨路徑進行求解，迭代生成多條揀貨路徑，包括：

判斷迭代次數或者迭代時長是否達到最大迭代次數或者最大迭代時長；若是，則停止迭代；若否，則采用分離算子、合并算子和/或刪除與重建算子并基于禁忌鄰域搜索算法對前一次迭代生成的揀貨路徑進行求解，生成至少一條揀貨路徑；

經過多次迭代，生成多條揀貨路徑。

6.根據權利要求5所述的方法，其特征在于，所述分離算子描述為：將某一個巷道口點刪除，獲取該巷道口點覆蓋的待揀儲位，將這些待揀儲位分配到與該巷道口點相鄰的兩個巷道口點；

所述合并算子描述為：將某兩個巷道口點刪除，獲取所述兩個巷道口點覆蓋的待揀儲位，將這些待揀儲位分配到一個新的巷道口點；

所述刪除與合并算子描述為：分別計算刪除各個待揀儲位后揀貨路徑的距離減少量，按照距離減少量由大到小的順序，對所述各個待揀儲位進行排序；刪除距離減少量靠前的待揀儲位，并將刪除的待揀儲位分配到巷道口點。

7.根據權利要求6所述的方法，其特征在于，將刪除的待揀儲位分配到巷道口點，包括：

新增一個巷道口點，將刪除的待揀儲位分配到該巷道口點，計算揀貨路徑的距離；

將刪除的待揀儲位分配到已有的巷道口點，計算揀貨路徑的距離；

選擇兩者中距離最短的方案進行分配。