[發明專利]基于分區協同優化策略的自動分揀系統訂單處理方法

在審

• 申請號: 201710304637.3
• 申請日: 2017-05-03
• 公開（公告）號: CN107274246A
• 公開（公告）日: 2017-10-20
• 發明（設計）人: 肖亮;陳庭貴;王璐雅
• 申請（專利權）人: 浙江工商大學
• 主分類號: G06Q30/06
• 分類號: G06Q30/06;G06Q10/08
• 代理公司: 杭州天正專利事務所有限公司33201
• 代理人: 王兵,黃美娟

1.基于分區協同優化策略的自動分揀系統訂單處理方法，包括以下步驟：

步驟1，構建分區協同優化分揀系統訂單處理的數學分析模型：訂單處理問題關鍵是如何使總處理時間最少，而為得到訂單處理總時間的結構組成，需要分析分區揀選策略下的系統布局與工作流程；分區揀選策略下，分揀機系統劃分為多個獨立揀貨區，一條主輸送帶連接各揀貨區末端的緩沖區；處理訂單時，各揀貨區內分揀機共同揀選同一訂單貨物并送入緩沖區，然后在合流輸送上完成貨物合流并送至包裝系統；由于各揀貨區內的分揀機并行工作，故降低了訂單處理總時間；根據貨到訂單揀選系統中的訂單隊列特點，設計排隊系統描述分揀機系統工作流程；在該排隊系統中，訂單理解為顧客，分揀機中各通道、緩沖區、包裝機理解為服務員；

排隊系統中的訂單處理流程包括：①訂單拆分：在輸入端是一訂單隊列，各訂單根據揀貨區數量以及所有品項在各揀貨區分配情況拆分為子訂單，并分配給各揀貨區；②貨物揀選：在各揀貨區內部，分揀機各通道和緩沖區根據先到先服務(First Come First Served，FCFS)的規則處理子訂單隊列中各品項貨物；③緩存積放：在各揀貨區內，緩沖區暫存揀出的子訂單貨物，由于緩沖區常設計為重力式滑道或動力式輸送帶，貨物在緩存等待過程中可實現密集積放；④合流與輸送：通過控制緩沖區末端的擋板，將屬于同一訂單的緩存貨物按照某種規則從不同緩沖區進入合流輸送帶，并送入包裝系統；在實際應用中，訂單拆分工作由電腦系統快速完成，故耗費時間可忽略，基于以上分析，可知分揀機系統的訂單處理時間由三部分組成：貨物揀選時間、貨物合流時間、緩沖區已滿導致的分揀機暫停時間；為從數學上表達任一揀貨區的訂單處理總時間構成，需要的變量包括：訂單數量r；揀貨區數量z；k號揀貨區處理i號訂單貨物的完成時刻它等于貨物由緩沖區流入合流輸送帶的結束時刻；k號揀貨；

區分揀機在處理i號訂單貨物的揀選時間t^p_ik；k號揀貨區分揀機處理i號訂單貨物時的暫停時間，即該訂單貨物在緩沖區開始合流前的等待時間t^w_ik；貨物合流時間，即訂單貨物從緩沖區流入主輸送帶耗費的時間t^m；各揀貨區訂單處理總時間均為貨物揀選時間、分揀機暫停時間、貨物合流時間之和，則任一揀貨區k處理訂單i的完成時刻可由下式表示：

Tikf=T(i-1)kf+tikp+tikw+tm,1≤i≤r,1≤k≤z---(1)]]>

遞歸調用式(1)可求得各揀貨區處理最后r號訂單的完成時刻如下式所示：

Trkf=(Σi=1rtikp+tikw+tm),1≤k≤z---(2)]]>

步驟2，分揀機分區協同優化問題的轉化：將分揀機綜合優化問題簡化后可轉化為并行機派尋問題(PMS)；設定訂單總數量r等于1，貨物合流時間t^m等于0秒，揀貨區數量z，各品項揀選量n^s_ij，品項拆分數量p均為已知常量，經過以上簡化，各品項相當于PMS問題中各工件，揀貨區相當于PMS問題中的處理機，揀貨區內的訂單處理時間相當于處理機加工工件時間，優化目標相當于工件加工總時間最短；由于PMS屬于NP完全問題，由此可知：不簡化的分揀機系統綜合優化問題更屬于NP完全問題；為降低問題求解難度，設計合理的啟發式算法，首先應當根據分揀機分區協同優化問題特點，轉變優化目標；然后，將分揀機分區協同優化問題拆分為若干子問題，采取單獨討論后再確定綜合求解方法的研究思路；

步驟3，品項分配子問題的構建及其層次聚類算法設計：品項分配子問題指如何分配所有品項到各揀貨區的問題；若以最小化訂單處理總時間為目標，難以提出針對性的優化算法；這里采用聚類分析方法求解品項分配子問題，根據分揀機系統品項分配子問題特點，提出一種類似連通法的層次聚類算法，該算法采用自底向上的聚類順序，聚類步驟如下：步驟31，根據品項總數s+p構建等量空類，即z＝s+p，并為每個類分配一個品項；步驟32，建立一個z行z列的類關系矩陣，矩陣中對角元素設為0，其余各元素表示不同類間的相關性，該矩陣為對稱矩陣，取其上半角或下半角共(z-1)z/2個元素，將最小值元素對應的兩個類合并為1個類，類的數量z減1：z＝z-1；步驟33，若類的數量大于預定的揀貨區數量，轉步驟32，否則結束；

步驟4，基于馬爾科夫的訂單最優排序的確定：由于一個訂單的等待時間只取決于前面N-1個訂單的處理時間和等待時間，因此系統具有馬爾可科夫性；將訂單看作是一個個追加到排好順序的訂單隊列中，在某個訂單即將追加到隊列的時刻點觀察系統，用隊列末尾N-1個訂單各自的處理時間和等待時間之和作為一個N-1維向量表示系統的狀態，則系統具有歷史無關性，可以看作一個狀態連續時間離散的馬爾科夫鏈；對于這種連續的狀態，通過積分和微分進行分析非常困難，因而采用離散化的方式將連續狀態轉變成離散狀態，進而研究離散狀態的最優決策，決策變量為下一個要處理的訂單，然后分析離散化帶來的誤差。