一種揀貨集合單的生成方法、裝置及揀貨路徑優化方法
2023-05-26 14:50:36
一種揀貨集合單的生成方法、裝置及揀貨路徑優化方法
【專利摘要】本發明涉及揀貨作業相關【技術領域】，特別是一種揀貨集合單的生成方法、裝置及揀貨路徑優化方法。生成方法包括：獲取N個訂單的位置信息，其中N>1，以訂單作為樣本，以訂單的位置信息作為對應樣本的樣本二維坐標；計算所述揀貨集合單所包括的簇數目；從N個樣本中選擇c個樣本作為初始樣本；對初始樣本以外的N-c個樣本，計算樣本二維坐標到c個聚類中心的距離，以所述距離最短的聚類中心所在的簇作為待歸類簇，將樣本歸到所述待歸類簇；如果滿足迭代結束條件，則將每個簇生成對應的揀貨集合單，否則繼續執行迭代。本發明根據優化後的揀貨集合單所生成的揀貨路徑，其揀貨效率與以往相比得到了較大的提高。
【專利說明】一種揀貨集合單的生成方法、裝置及揀貨路徑優化方法
【技術領域】
[0001]本發明涉及揀貨作業相關【技術領域】，特別是一種揀貨集合單的生成方法、裝置及揀貨路徑優化方法。
【背景技術】
[0002]當今WMS系統(Warehouse Management System倉庫管理系統)對揀貨路徑都進行了一定了優化，例如利用遺傳算法、蟻群算法、S型啟發式算法等對集合單(待揀訂單的一個集合，一般一個批次的集合單裡的訂單數是一樣的)內的訂單進行路徑優化。在路徑優化算法確定的情況下，如何確定這個待優化的集合單就成為進一步提高揀貨作業效率的重要一步，這個待優化集合單選取的優劣直接影響著整個揀貨作業的效率。
[0003]當前生成這個待優化的集合單的通常做法是按照訂單的下單時間的先後順序截取，假設要生成的集合單的大小為m，每m個訂單構成一個集合單，對得到的這個大小為m的待優化集合單進行路徑優化。
[0004]如圖7所示為現有的揀貨作業流程圖，包括:
[0005]步驟S701，前臺下發訂單；
[0006]步驟S702，按照下單時間先後截取m個訂單，生成揀貨集合單；
[0007]步驟S703，根據揀貨集合單內每個訂單的位置信息，生成用於揀貨作業的優化揀貨路徑；
[0008]步驟S704，根據優化揀貨路徑，工人進行揀貨作業。
[0009]通過對揀貨路徑進行優化，提高了工人的揀貨速度。然而現有技術的揀貨集合單是按照下單時間的先後順序生成，其存在如下問題:
[0010]按照下單時間的先後順序生成待優化集合單，容易造成待優化集合單內的訂單分散，對分散的訂單集合進行路徑優化對整個揀貨作業的效率的提高非常有限。
【發明內容】
[0011]基於此，有必要針對現有技術揀貨集合單的設計不合理導致揀貨路徑並不是最優化的技術問題，提供一種揀貨集合單的生成方法、裝置及揀貨路徑優化方法。
[0012]一種揀貨集合單的生成方法，包括:
[0013]樣本獲取步驟，獲取N個訂單的位置信息，其中N>1，以訂單作為樣本，以訂單的位置信息作為對應樣本的樣本二維坐標，執行簇數目計算步驟；
[0014]簇數目計算步驟，計算所述揀貨集合單所包括的簇數目c=N/d，其中d為預設的每個簇所包括的樣本數，所述簇為由d個樣本構成的集合，執行聚類中心初始化步驟；
[0015]聚類中心初始化步驟，從N個樣本中選擇c個樣本作為初始樣本,每個簇包括一個初始樣本，以初始樣本的樣本二維坐標作為對應簇的聚類中心，執行樣本歸類步驟；
[0016]樣本歸類步驟，對初始樣本以外的N-C個樣本，計算樣本二維坐標到c個聚類中心的距離，以所述距離最短的聚類中心所在的簇作為待歸類簇，將樣本歸到所述待歸類簇，且根據待歸類簇所包括的所有樣本的樣本二維坐標計算待歸類簇的中心坐標，作為待歸類簇的聚類中心，執行迭代檢查步驟；
[0017]迭代檢查步驟，如果滿足迭代結束條件，則執行揀貨集合單生成步驟，否則繼續執行樣本歸類步驟；
[0018]揀貨集合單生成步驟，將每個簇生成對應的揀貨集合單，每個揀貨集合單所包括的訂單為對應簇所包括的樣本。
[0019]一種揀貨集合單的生成裝置，包括:
[0020]樣本獲取模塊,獲取N個訂單的位置信息,其中N>1,以訂單作為樣本，以訂單的位置信息作為對應樣本的樣本二維坐標，執行簇數目計算模塊；
[0021]簇數目計算模塊，計算所述揀貨集合單所包括的簇數目c=N/d，其中d為預設的每個簇所包括的樣本數，所述簇為由d個樣本構成的集合，執行聚類中心初始化模塊；
[0022]聚類中心初始化模塊，從N個樣本中選擇c個樣本作為初始樣本,每個簇包括一個初始樣本，以初始樣本的樣本二維坐標作為對應簇的聚類中心，執行樣本歸類模塊；
[0023]樣本歸類模塊，對初始樣本以外的N-C個樣本，計算樣本二維坐標到c個聚類中心的距離，以所述距離最短的聚類中心所在的簇作為待歸類簇，將樣本歸到所述待歸類簇，且根據待歸類簇所包括的所有樣本的樣本二維坐標計算待歸類簇的中心坐標，作為待歸類簇的聚類中心，執行迭代檢查模塊；
[0024]迭代檢查模塊，如果滿足迭代結束條件，則執行揀貨集合單生成模塊，否則繼續執行樣本歸類模塊；
[0025]揀貨集合單生成模塊，將每個簇生成對應的揀貨集合單，每個揀貨集合單所包括的訂單為對應簇所包括的樣本。
[0026]一種揀貨路徑優化方法，包括:
[0027]樣本獲取步驟，獲取N個訂單的位置信息，其中N>1，以訂單作為樣本，以訂單的位置信息作為對應樣本的樣本二維坐標，執行簇數目計算步驟；
[0028]簇數目計算步驟，計算所述揀貨集合單所包括的簇數目c=N/d，其中d為預設的每個簇所包括的樣本數，所述簇為由d個樣本構成的集合，執行聚類中心初始化步驟；
[0029]聚類中心初始化步驟，從N個樣本中選擇c個樣本作為初始樣本,每個簇包括一個初始樣本，以初始樣本的樣本二維坐標作為對應簇的聚類中心，執行樣本歸類步驟；
[0030]樣本歸類步驟，對初始樣本以外的N-C個樣本，計算樣本二維坐標到c個聚類中心的距離，以所述距離最短的聚類中心所在的簇作為待歸類簇，將樣本歸到所述待歸類簇，且根據待歸類簇所包括的所有樣本的樣本二維坐標計算待歸類簇的中心坐標，作為待歸類簇的聚類中心，執行迭代檢查步驟；
[0031 ] 迭代檢查步驟，如果滿足迭代結束條件，則執行揀貨集合單生成步驟，否則繼續執行樣本歸類步驟；
[0032]揀貨集合單生成步驟，將每個簇生成對應的揀貨集合單，每個揀貨集合單所包括的訂單為對應簇所包括的樣本，每個揀貨集合單的位置信息為對應的簇的聚類中心，執行揀貨路徑優化步驟；
[0033]揀貨路徑優化步驟，對每個揀貨集合單，根據揀貨集合單所包括的訂單的位置信息，生成每個集合單的用於揀貨作業的揀貨路徑。[0034]本發明根據訂單的位置信息，通過進行迭代運算，計算得到經過優化的揀貨集合單，由於經過優化後的揀貨集合單，同一揀貨集合單所包括的訂單，其在倉庫中的位置都是相鄰較為接近的，因此根據優化後的揀貨集合單所生成的揀貨路徑，其揀貨效率與以往相比得到了較大的提高。
【專利附圖】
【附圖說明】
[0035]圖1為本發明一種揀貨集合單的生成方法的工作流程圖；
[0036]圖2為本發明一個例子的樣本示意圖；
[0037]圖3為本發明一個例子的簇示意圖；
[0038]圖4為本發明一種揀貨集合單的生成裝置的結構模塊圖；
[0039]圖5為本發明一種揀貨路徑優化方法的工作流程圖；
[0040]圖6為本發明一種揀貨路徑優化方法一個例子的工作流程圖；
[0041]圖7為現有揀貨作業的流程圖。
【具體實施方式】
[0042]下面結合附圖和具體實施例對本發明做進一步詳細的說明。
[0043]如圖1所示為本發明一種揀貨集合單的生成方法的工作流程圖，包括:
[0044]樣本獲取步驟S101，獲取N個訂單的位置信息，其中N>1，以訂單作為樣本，以訂單的位置信息作為對應樣本的樣本二維坐標，執行簇數目計算步驟S102 ；
[0045]簇數目計算步驟S102，計算所述揀貨集合單所包括的簇數目c=N/d，其中d為預設的每個簇所包括的樣本數，所述簇為由d個樣本構成的集合，執行聚類中心初始化步驟
5103；
[0046]聚類中心初始化步驟S103，從N個樣本中選擇c個樣本作為初始樣本,每個簇包括一個初始樣本，以初始樣本的樣本二維坐標作為對應簇的聚類中心，執行樣本歸類步驟
5104；
[0047]樣本歸類步驟S104，對初始樣本以外的N-c個樣本，計算樣本二維坐標到c個聚類中心的距離，以所述距離最短的聚類中心所在的簇作為待歸類簇，將樣本歸到所述待歸類簇，且根據待歸類簇所包括的所有樣本的樣本二維坐標計算待歸類簇的中心坐標，作為待歸類簇的聚類中心，執行迭代檢查步驟S105 ；
[0048]迭代檢查步驟S105，如果滿足迭代結束條件，則執行揀貨集合單生成步驟S106，否則繼續執行樣本歸類步驟S104 ；
[0049]揀貨集合單生成步驟S106，將每個簇生成對應的揀貨集合單，每個揀貨集合單所包括的訂單為對應簇所包括的樣本。
[0050]本發明所生成的揀貨集合單，通過路徑優化方法，可以得到針對每個揀貨集合單的經過優化的揀貨路徑，由於經過優化後的揀貨集合單，同一揀貨集合單所包括的訂單，其在倉庫中的位置都是相鄰較為接近的，每個揀貨人員在獲得揀貨集合單後，根據對應的揀貨路徑，則可以輕鬆地完成揀貨集合單所包括的訂單的揀貨作業。
[0051]其中，步驟S101，獲取到N個訂單的位置信息，該N個訂單通過前臺下發訂單獲取。雖然訂單的下單時間有先後順序，但是訂單的出庫時間點一般都是固定的幾個。在每一個出庫時間點出庫的訂單，都是出庫時間點前一段時間內的訂單，所以只要保證在出庫時間點之前將這個時間段內的訂單揀完即可，沒有必要嚴格按照下單時間的先後順序進行揀貨。
[0052]其中，步驟S102計算簇的數目，採用預設的每個簇所包括的樣本數進行計算，從而使得簇的樣本數一致。每個簇最終會轉化為揀貨集合單，工人會依據該揀貨集合單進行揀貨，簇的樣本數一致使得最終的揀貨集合單包括的訂單數目也一致，從而使得每個揀貨人員的工作量一致，滿足庫房生產的實際要求。該預設的每個簇所包括的樣本數可以通過在配置文件中進行定製，例如在XML文件中設置一個用於表示每個簇所包括的樣本數的參數，通過XML解析技術，對XML文件進行解析獲取參數。XML是一種可擴展標記語言，用於標記電子文件使其具有結構性的標記語言，可以用來標記數據、定義數據類型，是一種允許用戶對自己的標記語言進行定義的源語言。XML解析技術用於對XML文件進行解析的技術集合，包括文檔對象模型(DOM, Document Object Model)、XML 簡單接口(SAX, Simple APIfor XML)、針對於 XML 的流式 API (StAX, The Streaming API for XML)等。
[0053]其中，步驟S103中，所選擇的c個樣本，可以隨機選擇，也可以通過設定一定的規則進行選擇，規則可以定義為:樣本坐標之間的距離超過預設閾值，或者樣本坐標之間的距離在預設範圍內。
[0054]訂單的位置信息即訂單的貨物在倉庫中的坐標，作為一個例子，如圖2所示，每個黑點表示的是訂單的貨物在倉庫中的位置，包括訂單2101、2102、2103、2104、2105、2106、2107、2108、2109、2110、2111、2112、2113、2114、2115。本發明一種揀貨集合單的生成方法的一個例子的流程如下，可以通過計算機程式語言，例如Java語言實現:
[0055]執行步驟S101，得到15個訂單的位置信息，以該15個訂單作為樣本，以該15個訂單的位置信息作為樣本二維坐標；
[0056]執行步驟S102，d設定為5，則c=15/5=3，d為預設的每個簇所包括的樣本數，可以從預設的配置文件中獲取，例如在程序運行開始的時候，將這些定製的參數從XML文件中讀取；
[0057]執行步驟S103，從15個樣本中選擇3個樣本作為3個初始樣本，例如選擇訂單2101,2103和2107對應的樣本，每個簇包括一個初始樣本，以初始樣本的樣本二維坐標作為對應簇的聚類中心221、222和223，如圖2中的「 + 」，執行步驟S104 ；
[0058]執行步驟S104，對初始樣本以外的15-3個樣本，即12個樣本,計算每個樣本二維坐標到3個聚類中心的距離，以所述距離最短的聚類中心所在的簇作為待歸類簇，將樣本歸到所述待歸類簇，且根據待歸類簇所包括的所有樣本的樣本二維坐標計算待歸類簇的中心坐標，作為待歸類簇的聚類中心，執行步驟S105 ；
[0059]執行步驟S105，如果滿足迭代結束條件，則執行步驟S106，否則繼續執行步驟
S104；
[0060]執行步驟S106，經過步驟S104和S105，得到3個簇，如圖3所示，圖中每個圓形代表一個簇，即簇311、312和313，每個簇是聚類之後相似元素(位置相近)的集合，每個簇包括5個樣本，每個簇中的「 + 」為該簇的聚類中心，即聚類中心321、322和323，將3個簇生成對應的揀貨集合單，每個揀貨集合單所包括的訂單為對應簇所包括的樣本。
[0061]在其中一個實施例中，所述根據待歸類簇所包括的所有樣本的樣本二維坐標計算待歸類簇的中心坐標，作為待歸類簇的聚類中心，具體包括:
[0062]計算待歸類簇所包括的所有樣本的樣本二維坐標的橫坐標平均值，將所述橫坐標平均值作為待歸類簇的中心坐標的橫坐標，計算待歸類簇所包括的所有樣本的樣本二維坐標的縱坐標平均值，將所述縱坐標平均值作為待歸類簇的中心坐標的縱坐標；
[0063]更新待歸類簇的聚類中心為所述中心坐標。
[0064]步驟S104需要一個迭代結束條件，在其中一個實施例中，所述迭代結束條件包括:
[0065]執行樣本歸類步驟的次數大於或等於預設的迭代次數，或者
[0066]執行樣本歸類步驟後c個聚類中心與上一次執行樣本歸類步驟的c個聚類中心的偏移值在預設的偏移範圍之內。
[0067]本實施例所提出的迭代結束條件，使得步驟S104的迭代步驟能夠迅速收斂。迭代結束條件的各種參數也可以預先設置在配置文件，例如XML文件中，在程序運行開始的時候，將這些定製的參數從XML文件中讀取。定製的參數包括:迭代次數和偏移範圍。
[0068]在其中一個實施例中，所述N個訂單的出庫時間一致。具有同一出庫時間點的訂單，則工人根據揀貨集合單完成揀貨作業後，能夠在統一的出庫時間點一起出庫。
[0069]如圖4所示為本發明一種揀貨集合單的生成裝置的結構模塊圖，包括:
[0070]樣本獲取模塊401，獲取N個訂單的位置信息，其中N>1，以訂單作為樣本，以訂單的位置信息作為對應樣本的樣本二維坐標，執行簇數目計算模塊402 ；
[0071]簇數目計算模塊402，計算所述揀貨集合單所包括的簇數目c=N/d，其中d為預設的每個簇所包括的樣本數，所述簇為由d個樣本構成的集合，執行聚類中心初始化模塊
403；
[0072]聚類中心初始化模塊403，從N個樣本中選擇c個樣本作為初始樣本,每個簇包括一個初始樣本，以初始樣本的樣本二維坐標作為對應簇的聚類中心，執行樣本歸類模塊
404；
[0073]樣本歸類模塊404，對初始樣本以外的N-c個樣本，計算樣本二維坐標到c個聚類中心的距離，以所述距離最短的聚類中心所在的簇作為待歸類簇，將樣本歸到所述待歸類簇，且根據待歸類簇所包括的所有樣本的樣本二維坐標計算待歸類簇的中心坐標，作為待歸類簇的聚類中心，執行迭代檢查模塊405 ；
[0074]迭代檢查模塊405，如果滿足迭代結束條件，則執行揀貨集合單生成模塊406，否則繼續執行樣本歸類模塊404 ；
[0075]揀貨集合單生成模塊406，將每個簇生成對應的揀貨集合單，每個揀貨集合單所包括的訂單為對應簇所包括的樣本。
[0076]在其中一個實施例中，所述根據待歸類簇所包括的所有樣本的樣本二維坐標計算待歸類簇的中心坐標，作為待歸類簇的聚類中心，具體包括:
[0077]計算待歸類簇所包括的所有樣本的樣本二維坐標的橫坐標平均值，將所述橫坐標平均值作為待歸類簇的中心坐標的橫坐標，計算待歸類簇所包括的所有樣本的樣本二維坐標的縱坐標平均值，將所述縱坐標平均值作為待歸類簇的中心坐標的縱坐標；
[0078]更新待歸類簇的聚類中心為所述中心坐標。
[0079]在其中一個實施例中，所述迭代結束條件包括:[0080]執行樣本歸類模塊的次數大於或等於預設的迭代次數，或者
[0081]執行樣本歸類模塊後c個聚類中心與上一次執行樣本歸類模塊的c個聚類中心的偏移值在預設的偏移範圍之內。
[0082]在其中一個實施例中，所述N個訂單的出庫時間一致。
[0083]如圖5所示為本發明一種揀貨路徑優化方法的工作流程圖，包括:
[0084]樣本獲取步驟S501，獲取N個訂單的位置信息，其中N>1，以訂單作為樣本，以訂單的位置信息作為對應樣本的樣本二維坐標，執行簇數目計算步驟S502 ；
[0085]簇數目計算步驟S502，計算所述揀貨集合單所包括的簇數目c=N/d，其中d為預設的每個簇所包括的樣本數，所述簇為由d個樣本構成的集合，執行聚類中心初始化步驟
5503；
[0086]聚類中心初始化步驟S503，從N個樣本中選擇c個樣本作為初始樣本,每個簇包括一個初始樣本，以初始樣本的樣本二維坐標作為對應簇的聚類中心，執行樣本歸類步驟
5504；
[0087]樣本歸類步驟S504，對初始樣本以外的N-c個樣本，計算樣本二維坐標到c個聚類中心的距離，以所述距離最短的聚類中心所在的簇作為待歸類簇，將樣本歸到所述待歸類簇，且根據待歸類簇所包括的所有樣本的樣本二維坐標計算待歸類簇的中心坐標，作為待歸類簇的聚類中心，執行迭代檢查步驟S505 ；
[0088]迭代檢查步驟S505，如果滿足迭代結束條件，則執行揀貨集合單生成步驟S506，否則繼續執行樣本歸類步驟S504 ；
[0089]揀貨集合單生成步驟S506，將每個簇生成對應的揀貨集合單，每個揀貨集合單所包括的訂單為對應簇所包括的樣本，每個揀貨集合單的位置信息為對應的簇的聚類中心，執行揀貨路徑優化步驟507 ；
[0090]揀貨路徑優化步驟S507，對每個揀貨集合單，根據揀貨集合單所包括的訂單的位置信息，生成每個集合單的用於揀貨作業的揀貨路徑。
[0091]以往的揀貨路徑，是基於所有的訂單生成，因此其揀貨路徑非常長，導致揀貨的效率降低。即使將所有訂單分成多個揀貨集合單，其分配方式也是按照下單時間的先後進行下單，因此，所不同的揀貨集合單所生成的揀貨路徑很有可能重合，以圖2為例，假設訂單的下單時間按照以下順序:
[0092]2101<2102<2103<2104<2105<2106<2107<2108<2109<2110<2111<2112<2113<2114〈2115。
[0093]則按照以往的方式將其分成三個揀貨集合單，則會成為第一揀貨集合單:2101、2102、2103、2104、2105，第二揀貨集合單:2106、2107、2108、2109、2110，第三揀貨集合單:2111、2112、2113、2114、2115。第一揀貨集合單的揀貨路徑，將會是2101->2102->2013->2104->2105，第二揀貨集合單的揀貨路徑，將會是2106->2107->2109->2110->2108，第三揀貨集合單的揀貨路徑，將會是2115->2111->2112->2113->2114。從圖 2 中可以看出，2112->2113_>2114 與 2101_>2102的路徑重合，而2102->2103的路徑較遠，因此採用以往的方式所生成的揀貨路徑並不是最優。考慮一直更極端的方式，假設訂單的下單時間按照以下順序:
[0094]2101<2102<2103<2104<2108<2106<2107<2115<2109<2113<2111<2112<2110<2114〈2105。
[0095]則按照以往的方式將其分成三個揀貨集合單，則會成為第一揀貨集合單:2101、2102、2103、2104、2108，第二揀貨集合單:2106、2107、2115、2109、2113，第三揀貨集合單:2111、2112、2110、2114、2105。第一揀貨集合單的揀貨路徑，將會是2101->2102->2013->2104->2108，第二揀貨集合單的揀貨路徑，將會是2113->2115->2106->2107->2109，第三揀貨集合單的揀貨路徑，將會是
2110->2111->2112->2114->2105。從圖2 中可以看出，2104->2108、2110_>2111，以及2114->2105的距離都非常遠，揀貨效率非常低下。
[0096]而根據本發明實施例所生成的揀貨集合單所生成的揀貨路徑則效率大大提高，如圖3所示，本發明實施例所生成的揀貨集合單為:根據簇311生成的第一揀貨集合單:2101、2102、2112、2113、2114，根據簇 312 生成的第二揀貨集合單:2103、2104、2105、2106,2115,根據簇313生成的第三揀貨集合單:2107、2108、2109、2110、2111。第一揀貨集合單的揀貨路徑，將會是:2101->2102->2112->2113->2114，第一揀貨集合單的揀貨路徑，將會是:2115->2103->2104->2105->2106，第三揀貨集合單的揀貨路徑，將會是:
2111->2107->2109->2110->2108。從圖3中可見，每條揀貨路徑都是最優路徑，其揀貨效率得到很大提高。
[0097]同時，在以往的揀貨路徑生成過程中，由於某些訂單的位置距離較遠，因此需要特別為其設計路徑，從而導致算法收斂速度較慢，運算時間較長，如果人為設定收斂次數以提高運算速度，則容易導致計算出來的揀貨路徑並未達到最優，計算效率和效果都較差。而本發明實施例，由於每個揀貨集合單所包括的訂單，其位置均靠得較近，生成揀貨路徑時，由於剔除了需要較長運算時間的距離較遠的訂單，因此其運算速度及效率都得到了較大提聞。
[0098]在其中一個實施例中，所述根據待歸類簇所包括的所有樣本的樣本二維坐標計算待歸類簇的中心坐標，作為待歸類簇的聚類中心，具體包括:
[0099]計算待歸類簇所包括的所有樣本的樣本二維坐標的橫坐標平均值，將所述橫坐標平均值作為待歸類簇的中心坐標的橫坐標，計算待歸類簇所包括的所有樣本的樣本二維坐標的縱坐標平均值，將所述縱坐標平均值作為待歸類簇的中心坐標的縱坐標；
[0100]更新待歸類簇的聚類中心為所述中心坐標。
[0101]在其中一個實施例中，所述迭代結束條件包括:
[0102]執行樣本歸類步驟的次數大於或等於預設的迭代次數，或者
[0103]執行樣本歸類步驟後c個聚類中心與上一次執行樣本歸類步驟的c個聚類中心的偏移值在預設的偏移範圍之內。
[0104]在其中一個實施例中，所述N個訂單的出庫時間一致。
[0105]如圖6所示為本發明一種揀貨路徑優化方法一個例子的工作流程圖，包括:
[0106]步驟S601，前臺下發某一時間段內的訂單，即某一出庫時間點前的訂單；
[0107]步驟S602，從XML文件中讀取各種參數，包括每個簇所包括的樣本數，以及迭代結束條件的各種參數，包括迭代次數和偏移範圍；
[0108]步驟S603，採用上述步驟S501?S506的方式，生成揀貨集合單；
[0109]步驟S604，對每個揀貨集合單生成揀貨路徑；[0110]步驟S605，根據揀貨路徑對揀貨集合單所包括的訂單進行揀貨作業。
[0111]以上所述實施例僅表達了本發明的幾種實施方式，其描述較為具體和詳細，但並不能因此而理解為對本發明專利範圍的限制。應當指出的是，對於本領域的普通技術人員來說，在不脫離本發明構思的前提下，還可以做出若干變形和改進，這些都屬於本發明的保護範圍。因此，本發明專利的保護範圍應以所附權利要求為準。
【權利要求】
1.一種揀貨集合單的生成方法，其特徵在於，包括: 樣本獲取步驟，獲取N個訂單的位置信息,其中N>1,以訂單作為樣本，以訂單的位置信息作為對應樣本的樣本二維坐標，執行簇數目計算步驟； 簇數目計算步驟，計算所述揀貨集合單所包括的簇數目c=N/d，其中d為預設的每個簇所包括的樣本數，所述簇為由d個樣本構成的集合，執行聚類中心初始化步驟； 聚類中心初始化步驟,從N個樣本中選擇c個樣本作為初始樣本,每個簇包括一個初始樣本，以初始樣本的樣本二維坐標作為對應簇的聚類中心，執行樣本歸類步驟； 樣本歸類步驟，對初始樣本以外的N-c個樣本，計算樣本二維坐標到c個聚類中心的距離，以所述距離最短的聚類中心所在的簇作為待歸類簇，將樣本歸到所述待歸類簇，且根據待歸類簇所包括的所有樣本的樣本二維坐標計算待歸類簇的中心坐標，作為待歸類簇的聚類中心，執行迭代檢查步驟； 迭代檢查步驟，如果滿足迭代結束條件，則執行揀貨集合單生成步驟，否則繼續執行樣本歸類步驟； 揀貨集合單生成步驟，將每個簇生成對應的揀貨集合單，每個揀貨集合單所包括的訂單為對應簇所包括的樣本。
2.根據權利要求1所述的揀貨集合單的生成方法，其特徵在於，所述根據待歸類簇所包括的所有樣本的樣本二維坐標計算待歸類簇的中心坐標，作為待歸類簇的聚類中心，具體包括: 計算待歸類簇所包括的所有樣本的樣本二維坐標的橫坐標平均值，將所述橫坐標平均值作為待歸類簇的中心坐標的橫坐標，計算待歸類簇所包括的所有樣本的樣本二維坐標的縱坐標平均值，將所述縱坐標平均值作為待歸類簇的中心坐標的縱坐標； 更新待歸類簇的聚類中心為所述中心坐標。
3.根據權利要求1所述的揀貨集合單的生成方法，其特徵在於，所述迭代結束條件包括: 執行樣本歸類步驟的次數大於或等於預設的迭代次數，或者 執行樣本歸類步驟後c個聚類中心與上一次執行樣本歸類步驟的c個聚類中心的偏移值在預設的偏移範圍之內。
4.根據權利要求1所述的揀貨集合單的生成方法，其特徵在於，所述N個訂單的出庫時間一致。
5.一種揀貨集合單的生成裝置，其特徵在於，包括: 樣本獲取模塊，獲取N個訂單的位置信息，其中N>1，以訂單作為樣本，以訂單的位置信息作為對應樣本的樣本二維坐標，執行簇數目計算模塊； 簇數目計算模塊，計算所述揀貨集合單所包括的簇數目c=N/d，其中d為預設的每個簇所包括的樣本數，所述簇為由d個樣本構成的集合，執行聚類中心初始化模塊； 聚類中心初始化模塊，從N個樣本中選擇c個樣本作為初始樣本，每個簇包括一個初始樣本，以初始樣本的樣本二維坐標作為對應簇的聚類中心，執行樣本歸類模塊； 樣本歸類模塊，對初始樣本以外的N-c個樣本，計算樣本二維坐標到c個聚類中心的距離，以所述距離最短的聚類中心所在的簇作為待歸類簇，將樣本歸到所述待歸類簇，且根據待歸類簇所包括的所有樣本的樣本二維坐標計算待歸類簇的中心坐標，作為待歸類簇的聚類中心，執行迭代檢查模塊； 迭代檢查模塊，如果滿足迭代結束條件，則執行揀貨集合單生成模塊，否則繼續執行樣本歸類模塊； 揀貨集合單生成模塊，將每個簇生成對應的揀貨集合單，每個揀貨集合單所包括的訂單為對應簇所包括的樣本。
6.根據權利要求5所述的揀貨集合單的生成裝置，其特徵在於，所述根據待歸類簇所包括的所有樣本的樣本二維坐標計算待歸類簇的中心坐標，作為待歸類簇的聚類中心，具體包括: 計算待歸類簇所包括的所有樣本的樣本二維坐標的橫坐標平均值，將所述橫坐標平均值作為待歸類簇的中心坐標的橫坐標，計算待歸類簇所包括的所有樣本的樣本二維坐標的縱坐標平均值，將所述縱坐標平均值作為待歸類簇的中心坐標的縱坐標； 更新待歸類簇的聚類中心為所述中心坐標。
7.根據權利要求5所述的揀貨集合單的生成裝置，其特徵在於，所述迭代結束條件包括: 執行樣本歸類模塊的次數大於或等於預設的迭代次數，或者 執行樣本歸類模塊後c個聚類中心與上一次執行樣本歸類模塊的c個聚類中心的偏移值在預設的偏移範圍之內。
8.根據權利要求5所述的揀貨集合單的生成裝置，其特徵在於，所述N個訂單的出庫時 間一致。
9.一種揀貨路徑優化方法，其特徵在於，包括: 樣本獲取步驟，獲取N個訂單的位置信息,其中N>1,以訂單作為樣本，以訂單的位置信息作為對應樣本的樣本二維坐標，執行簇數目計算步驟； 簇數目計算步驟，計算所述揀貨集合單所包括的簇數目c=N/d，其中d為預設的每個簇所包括的樣本數，所述簇為由d個樣本構成的集合，執行聚類中心初始化步驟； 聚類中心初始化步驟,從N個樣本中選擇c個樣本作為初始樣本,每個簇包括一個初始樣本，以初始樣本的樣本二維坐標作為對應簇的聚類中心，執行樣本歸類步驟； 樣本歸類步驟，對初始樣本以外的N-c個樣本，計算樣本二維坐標到c個聚類中心的距離，以所述距離最短的聚類中心所在的簇作為待歸類簇，將樣本歸到所述待歸類簇，且根據待歸類簇所包括的所有樣本的樣本二維坐標計算待歸類簇的中心坐標，作為待歸類簇的聚類中心，執行迭代檢查步驟； 迭代檢查步驟，如果滿足迭代結束條件，則執行揀貨集合單生成步驟，否則繼續執行樣本歸類步驟； 揀貨集合單生成步驟，將每個簇生成對應的揀貨集合單，每個揀貨集合單所包括的訂單為對應簇所包括的樣本，每個揀貨集合單的位置信息為對應的簇的聚類中心，執行揀貨路徑優化步驟； 揀貨路徑優化步驟，對每個揀貨集合單，根據揀貨集合單所包括的訂單的位置信息，生成每個集合單的用於揀貨作業的揀貨路徑。
10.根據權利要求9所述的揀貨路徑優化方法，其特徵在於，所述根據待歸類簇所包括的所有樣本的樣本二維坐標計算待歸類簇的中心坐標，作為待歸類簇的聚類中心，具體包括: 計算待歸類簇所包括的所有樣本的樣本二維坐標的橫坐標平均值，將所述橫坐標平均值作為待歸類簇的中心坐標的橫坐標，計算待歸類簇所包括的所有樣本的樣本二維坐標的縱坐標平均值，將所述縱坐標平均值作為待歸類簇的中心坐標的縱坐標； 更新待歸類簇的聚類中心為所述中心坐標。
11.根據權利要求9所述的揀貨路徑優化方法，其特徵在於，所述迭代結束條件包括: 執行樣本歸類步驟的次數大於或等於預設的迭代次數，或者 執行樣本歸類步驟後c個聚類中心與上一次執行樣本歸類步驟的c個聚類中心的偏移值在預設的偏移範圍之內。
12.根 據權利要求9所述的揀貨路徑優化方法，其特徵在於，所述N個訂單的出庫時間一致。
【文檔編號】G06Q10/08GK103440566SQ201310378987
【公開日】2013年12月11日 申請日期:2013年8月27日 優先權日:2013年8月27日
【發明者】郭永強 申請人:北京京東尚科信息技術有限公司