[發明專利]計算揀貨路徑的方法及系統

有效

• 申請號: 201611199025.4
• 申請日: 2016-12-22
• 公開（公告）號: CN108229717B
• 公開（公告）日: 2022-01-28
• 發明（設計）人: 秦恒樂
• 申請（專利權）人: 北京京東乾石科技有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08
• 代理公司: 中科專利商標代理有限責任公司 11021
• 代理人: 任巖

1.一種計算區域中的揀貨路徑的方法，所述區域包括至少一排貨格，每排貨格對應于一條巷道，通過所述巷道可以到達相應的貨格，至少一條巷道的兩個巷道口各自連接到相應的一條主干道，所述方法包括：

讀取電子訂單數據；

根據所述電子訂單數據，確定目的地貨格，所述目的地貨格存放有要揀取的貨品；

根據每條主干道上的待進入巷道口的數量、從該主干道進入待進入巷道口能夠揀取的貨品數量、該主干道上待進入巷道口之間的最遠距離、以及從該主干道上的待進入巷道口到相應巷道中最遠目的地貨格之間的距離，確定待進入主干道，其中，待進入巷道是目的地貨格對應的巷道，待進入巷道口是待進入巷道與主干道相交處的巷道口；

根據待進入主干道、待進入主干道上的待進入巷道口和目的地貨格，計算揀貨路徑；以及

將所述揀貨路徑以電子數據的形式輸出；

其中，所述確定待進入主干道，包括：

根據每條主干道上的待進入巷道口的數量、從該主干道進入待進入巷道口能夠揀取的貨品數量、該主干道上待進入巷道口之間的最遠距離、以及從該主干道上的待進入巷道口到相應巷道中最遠目的地貨格之間的距離，對該主干道打分；

將得分最高的主干道確定為待進入主干道；

判斷所述待進入主干道上的待進入巷道口所對應的巷道在另外一條主干道上是否有另一個待進入巷道口，如果是，則所述另一個待進入巷道口不再作為待進入巷道口；以及

對其余主干道重復所述打分、確定和判斷操作，直到所有待進入巷道口都在待進入主干道上為止。

2.根據權利要求1所述的方法，其中，所述對每條主干道打分包括：

式中，S_j表示第j條主干道的得分，j表示第j條主干道，N_j表示第j條主干道上的待進入巷道口的數量，n表示在第j條主干道上的目的地貨格總數，p_i表示每個目的地貨格可以揀到的貨品數量，i＝1,2,3，…，n，D_j表示在第j條主干道上巷道口之間最遠的距離，d_j表示在相應巷道中目的地貨格距離與待進入巷道口之間的最遠距離。

3.根據權利要求2所述的方法，其中，還包括：

若存在幾條主干道得分相同，則判斷揀貨起始位置到所述幾條主干道中點位置的距離，取距離最小的主干道為待進入主干道。

4.根據權利要求1所述的方法，其中，所述根據待進入主干道、待進入主干道上的待進入巷道口和目的地貨格，計算揀貨路徑，包括：

根據待進入主干道和待進入主干道上待進入巷道口計算主干道上的揀貨路徑，以及

根據待進入巷道口和目的地貨格，計算巷道中的揀貨路徑。

5.根據權利要求4所述的方法，其中，所述計算主干道上的揀貨路徑以及計算巷道中的揀貨路徑，還包括：

若計算主干道上的揀貨路徑有一條最短路徑，則選取該最短路徑為揀貨路徑；

若計算主干道上的揀貨路徑有多條最短路徑，則比較不同主干道上的揀貨路徑下，巷道中的揀貨路徑，選取巷道中的揀貨路徑最短所對應的主干道上的路徑為揀貨路徑。

6.根據權利要求5所述的方法，其中，根據待進入主干道和待進入主干道上待進入巷道口計算主干道上的揀貨路徑，包括：

以揀貨員起始位置為起點，待進入巷道口為必須經過的點，構建在區域上的旅行商問題；

解旅行商計算得出主干道上的揀貨路徑。

7.根據權利要求5所述的方法，其中，所述根據待進入巷道口和目的地貨格，計算巷道中的揀貨路徑，包括：

按照從距離待進入巷道口最遠的目的地貨格開始揀貨，依次揀完該巷道內所有目的地貨格，再返回所述待進入巷道口的方式，計算巷道內的揀貨路徑。