具有訂單完成時間約束的揀選機器人調度仿真

李 騰，馮 珊

(哈爾濱商業大學管理學院，黑龍江 哈爾濱 150028)

1 引言

揀選作業是整個物流作業的關鍵環節，直接影響企業的服務水平。通過揀選機器人代替傳統的人工揀選的智能倉儲系統得到了越來越多的應用[1-2]。目前，許多智能倉儲系統，特別是電商平臺使用的智能倉儲系統，體現出“揀選為主，存儲為輔”的特點，其關鍵在于如何高效地完成揀選作業以滿足消費者對配送時效的要求[3]。科學合理地調度揀選機器人完成任務直接影響智能倉儲系統的運作效率，已經成為智能倉儲系統的研究重點[4-5]。

目前，機器人調度問題已經受到國內外學者的廣泛關注，Luo等[6]針對集裝箱碼頭的機器人調度問題，同時考慮裝載與卸載過程，以船舶的泊位時間最小為目標函數建立混合整數規劃模型，利用遺傳算法進行求解，實現了機器人的調度。Angeloudis等[7]開發了一種新的機器人調度方法，將不確定因素加以考慮，解決了集裝箱碼頭作業的分配并降低了成本。Chaudhry等[8]考慮了柔性制造系統中設備與機器人的同時調度，提出了一種改進的遺傳算法，降低了完工時間。周炳海等[9]研究了物料配送機器人調度問題，考慮了機器人之間的協同調度，以投入成本和能耗成本為優化目標建立模型，利用自適應大鄰域搜索算法進行求解，通過算例驗證了協同調度不僅可以減少機器人的數量，還可以降低能耗成本。沈博文等[10]對倉儲物流機器人調度問題進行研究，以倉儲物流機器人完成任務的總代價最小為目標函數，并考慮了系統的擁塞程度，實現了倉儲物流機器人的智能調度。袁瑞萍等[11]研究了“貨到人”訂單揀選系統中的任務調度問題，最小化所有任務的完成時間，對比多個揀選工作站同步揀選與異步揀選兩種揀選方式，利用改進遺傳算法對兩調度模型進行求解，通過實例仿真得出同步揀選具有更高的效率。

目前，對于機器人調度問題的相關研究主要集中于集裝箱碼頭系統、生產制造系統與物流倉儲系統，對于機器人調度問題，部分訂單對完成時間有嚴格的要求，而上述文獻中沒有考慮任務的時間窗約束，并且上述有關智能倉儲系統機器人調度文獻中，沒有考慮到機器人的等待時間。因此，本文針對智能倉儲系統，在不改變已有任務下發順序的情況下，以揀選機器人執行所有任務所花費的總成本最小為優化目標，任務分配結果為決策變量，同時考慮揀選機器人在揀選工作站的排隊等待時間，分別建立硬時間窗約束與軟時間窗約束下的揀選機器人調度模型。

2 揀選機器人調度模型

2.1 問題描述

“貨到人”智能倉儲系統布局如圖1所示，主要由貨架、揀選機器人、揀選區域、揀選機器人停車區域，揀選機器人充電區域以及揀選機器人行走通道組成。其中，貨架的放置原則為背靠背放置，每個貨架的規格相同，并且每層貨架上存儲不同種類的貨物。貨架之間為揀選機器人的行走通道，揀選區域由多個揀選工作站組成，每個揀選工作站配有一名工作人員將指定的貨物從貨架中揀出。智能倉儲系統的主要工作流程為：倉庫管理系統接收訂單后，按照搬運貨架次數最少的原則對訂單進行分批，然后將處理后的訂單發送至調度系統，調度系統需要確認訂單中任務所在貨架的位置以及各個揀選機器人的位置，其次調度揀選機器人來執行任務。此時，揀選機器人將移動到貨架位置，并將貨架托運至規定的揀選工作站進行排隊等待，該揀選工作站的工作人員按照揀選機器人到達的順序將訂單中的貨物從貨架中取出，然后放置在指定的貨箱中，同時揀選機器人將貨架托運至原來位置，并在此位置等待調度系統為其再次分配任務。

圖1 智能倉儲系統布局

智能倉儲系統揀選機器人調度是指在調度系統的控制下，以某個參數為優化目標，確定各個揀選機器人將要執行的任務以及各自執行任務的順序，在滿足一定的約束條件下提高揀選效率，降低智能倉儲系統的運行成本。具有時間窗約束的揀選機器人調度問題是指在傳統的揀選機器人調度問題基礎上加入時間窗的約束，即智能倉儲系統要求任務在一定時間范圍內完成揀選工作。在智能倉儲系統中，任務的下發順序取決于任務的到達時間，本文針對智能倉儲系統揀選機器人調度問題，在不改變任務序列的情況下，以最大限度滿足系統對時間的嚴格要求進而提高消費者滿意度。

針對智能倉儲系統揀選機器人調度問題，本文做出以下假設：

1)初始時刻，智能倉儲系統中所有揀選機器人處于空閑狀態；

2)智能倉儲系統中所有揀選機器人的行駛速度相同，不考慮揀選機器人的加減速；

3)揀選機器人在完成任務的過程中，電量始終充足；

4)貨架上的貨物是隨機放置的；

5)揀選機器人在完成任務后，將貨架托運至原來位置，并在此位置等待下一個任務；

6)每個揀選工作站的揀選人員每次的揀貨時間相同，分貨時間相同。

2.2 數學模型

為建立數學模型，本文定義了如下參數：

1)m表示揀選機器人的總數量，i表示第i臺揀選機器人，取值范圍為i∈[1，m]；n表示任務的總數量，j為第j個任務，取值范圍為j∈[1，n]，其中有w個任務具有時時間窗約束，k表示第k個具有時間窗約束的任務，取值范圍為k∈[1，w]；

2)(xAi，yAi)表示第i臺揀選機器人的位置坐標，(xTj，yTj)表示第j個任務的位置坐標，(xP，yP)表示揀選工作站的位置坐標；d1ij表示第i臺揀選機器人從初始位置到第j個任務所行駛的最小距離，d2ij表示第i臺揀選機器人從第j個任務到揀選工作站所行駛的最小距離，d3ij表示第i臺揀選機器人從揀選工作站回到第j個任務所行駛的最小距離，其中所有最小距離均為曼哈頓距離；

3)v表示揀選機器人的行駛速度；

4)t1表示揀選人員的揀貨時間，t2表示揀選人員的分貨時間；

5)r表示每次下發任務的數量，每次下發的時刻為上一批任務中最早到達該揀選工作站的時刻，取值范圍為r∈[1，n]；

6)l表示任務到達揀選工作站的順序，取值范圍為l∈[1，n]；

7)tjc表示第j個任務被下發的時刻；

8)tlj表示第l個到達揀選工作站的第j個任務到達該揀選工作站的時刻；

9)t(l-1)jp表示第l-1個到達揀選工作站的第j個任務被揀選完成的時刻，tlkp表示第l個到達揀選工作站的第k個具有時間窗約束的任務被揀選完成的時刻；

10)tiljq表示由第i臺揀選機器人完成的第l個到達揀選工作站的第j個任務在該揀選工作站的等待時間；

11)Ti為第i臺揀選機器人完成被分配任務所花費的總時間，T為所有任務的完成時間；

12)Cr表示每臺揀選機器人單位時間內的運行成本，C表示揀選機器人完成所有任務的總成本；

13)[tETk，tLTk]表示第k個任務最早最晚揀選完成的時間要求；

14)決策變量Xij表示第i臺揀選機器人是否完成第j個任務；

在智能倉儲系統中，揀選機器人完成所有任務的總時間為所有揀選機器人完成各自任務所耗費的最長時間。本文以揀選機器人完成所有任務的總成本最小為目標函數，以揀選機器人調度為決策變量，考慮了部分任務的時間窗約束以及揀選機器人在揀選工作站的排隊等待時間，分別建立硬時間窗的揀選機器人調度模型與軟時間窗的揀選機器人調度模型：

硬時間窗揀選機器人調度模型：

minC=T·Cr·n

(1)

T=max{Ti，i=1，2，…，m}

(2)

(3)

(4)

t(l-1)jp=t(l-1)j+ti(l-1)jq+t1+t2

(5)

tETk≤tlkp≤tLTk

(6)

Xij∈{0，1}，i=1，2，…，m，j=1，2，…，n

(7)

(8)

上述模型中，式(1)為揀選機器人調度模型的目標函數，表示揀選機器人完成所有任務的總成本最小。式(2)表示揀選機器人完成所有任務所花費的總時間。式(3)中揀選機器人完成任務的時間取決于揀選機器人的行走時間與在揀選工作站的排隊等待時間，并按照揀選機器人每次完成任務所停留的位置將其行走距離分為三個部分。式(4)表示揀選機器人在揀選工作站的排隊等待時間與揀選機器人到達揀選工作站的時刻和該揀選機器人所在排隊隊列中的前一臺揀選機器人被揀選完成的時刻有關。式(5)表示揀選機器人被揀選完成的時刻，取決于揀選機器人到達揀選工作站的時刻、揀選機器人在揀選工作站的排隊等待時間、工作人員的揀貨時間與分貨時間。式(6)表示智能倉儲系統要求部分任務的揀選完成時間需要滿足時間窗約束。式(8)表示一個任務同時只能由一臺揀選機器人托運。

軟時間窗揀選機器人調度模型

(9)

T=max{Ti，i=1，2，…，m}

(10)

(11)

(12)

t(l-1)jp=t(l-1)j+ti(l-1)jq+t1+t2

(13)

(14)

Xij∈{0，1}，i=1，2，…，m，j=1，2，…，n

(15)

(16)

與硬時間窗揀選機器人調度模型相比較，軟時間窗揀選機器人調度模型中智能倉儲系統對任務被揀選完成的時間要求沒有那么嚴格[12-13]，本文采用線性懲罰函數，即對沒有在系統希望時間范圍內完成的任務予以懲罰。式(9)表示揀選機器人完成所有任務花費的總成本，其中Cpk表示第k個具有時間窗約束的任務被揀選完成所造成的懲罰成本。式(14)中fk1與fk2分別表示具有時間窗約束的任務被提前或延遲揀完的單位懲罰成本，任務被延遲揀完產生的懲罰成本大于被提前揀完的懲罰成本，即fk2>fk1，tMETk表示任務k的可接受最早揀完時間，tMLTk表示任務k的可接受最晚揀完時間。

3 模型求解

遺傳算法是模擬生物自然選擇與進化的一種啟發式算法，該算法不受約束條件的限制，具有并行性、高效性等特點，通過利用遺傳的基本操作，如染色體之間進行交叉和變異，提高種群的多樣性，進而尋找問題的全局最優解[14-15]。由于本文所研究的是具有時間窗約束的揀選機器人調度問題，因此采用遺傳算法進行求解，其流程如圖2所示，具體求解步驟如下：

1)設置初始種群的個數，確定一次下發任務的數量，將訂單中的任務按照每次的下發數量進行分組，規定每組任務內不能調用同一臺揀選機器人執行任務，利用實數對染色體進行編碼，染色體的長度表示任務的總數，染色體中每個基因位表示任務的序號，基因位上的實數表示該序號的揀選機器人完成對應基因位的任務。利用實數進行編碼可以直接觀察到各個揀選機器人執行的任務以及依次執行的任務序列。

2)計算種群內所有染色體的適應度值。首先計算揀選機器人完成所有任務所花費的運行成本，其次觀察每個任務完成揀選的時刻是否符合其時間窗要求，計算由于不符合時間窗要求所造成的懲罰成本，最終染色體的適應度值為揀選機器人執行所有任務所花費的總成本的倒數，以硬時間窗揀選機器人調度模型為例，其適應度函數為：

(17)

3)在上述種群中，將染色體按照適應度值進行排序，采用精英保存策略選擇出一定數量的適應度值較高的優良染色體作為父代。

4)確定交叉概率，本文將染色體按照每次下發任務的數量進行分段，在染色體的段數范圍內隨機生成兩個實數作為兩父代染色體的交叉位置，其次，兩父代染色體對應交叉位置的基因段進行交叉操作，產生新的個體，采用這種交叉方式保證了每組內不會調用相同的揀選機器人執行任務。

5)確定變異概率，在染色體長度范圍內，隨機生成一個實數作為父代染色體的變異位置，將此位置的基因變異成揀選機器人的序號，該序號不能與同一段基因位上的序號相同，代表不能同時調度一臺揀選機器人完成一組內的多個任務。

6)設置最大迭代次數，如果迭代次數達到最大迭代次數，停止迭代，輸出揀選機器人完成所有任務所花費的總成本、揀選機器人的調度結果與所有任務的揀選完成時間。

4 仿真與結果分析

為了驗證遺傳算法求解揀選機器人調度模型的有效性，將初始種群的個數設置為100個，交叉概率與變異概率分別設置為0.9和0.08。對于每一個算例，均采用相同參數，運行10次取其最小值作為最終結果。假設實驗在50m× 50m的智能倉儲系統中進行，揀選工作站的位置坐標為(5，2)，以10臺揀選機器人和60個任務為例，其位置坐標分別見表1和表2，該批任務中有10個任務具有時間約束。其中揀選工作站對應工作人員的揀貨時間為8s，分貨時間為6s，按照每臺揀選機器人每小時的功率為100W，電費為0.86元/千瓦時計算，得出系統中每臺揀選機器人每秒內的運行成本為0.00083元。每3個任務為一組下發一次，下發時間為上一組任務中最早到達該揀選工作站的時刻。該批任務的完成時間為所有揀選機器人完成各自任務耗時最長的時間。

表1 揀選機器人位置坐標

表2 任務位置坐標

首先對硬時間窗約束下的揀選機器人調度進行仿真。若任務沒有在要求時間內完成，懲罰成本設置為一個較大數值，相較于運行成本，這里選擇懲罰成本為10元。仿真結果如圖2所示，揀選機器人調度結果見表3，任務的硬時間窗以及完成揀選的時刻見表4。

圖2 硬時間窗約束下完成所有任務所花費的總成本

表3 硬時間窗約束下揀選機器人調度結果

表4 任務的硬時間窗以及完成揀選的時刻

圖2表示硬時間約束下揀選機器人完成所有任務所花費的總成本，圖中可以看出隨著迭代次數的增加，成本不斷減少，最終得到最優調度結果使其成本達到最小值，說明遺傳算法能夠對該模型進行求解。表3中揀選機器人調度結果的第一位數字表示揀選機器人的序號，后面為揀選機器人依次執行的任務的序號。從表4中可以看出，所有具有硬時間窗約束的任務被揀完的時刻均在各自的硬時間窗范圍內。

為進一步驗證硬時間窗約束的揀選機器人調度模型，將具有硬時間窗約束的任務數量增加，揀選機器人完成所有任務所花費的總成本如圖3所示。

圖3 具有硬時間窗約束的任務總數不同情況下揀選機器人完成所有任務所花費的總成本

圖3表示具有硬時間窗約束的任務總數不同情況下揀選機器人完成所有任務所花費的總成本，從圖中可以明顯看出，隨著具有硬時間窗的任務數量增加，揀選機器人調度問題的可行解數量減少，成本呈緩慢上升趨勢，直至具有硬時間窗約束的任務數量為19時，成本明顯上升。仿真結果顯示，第58個任務的揀選完成時間不在其硬時間窗約束范圍內，意味著此時揀選機器人不能在硬時間窗約束下順利完成所有任務。

因此，本文通過增加揀選機器人的調度數量來完成上述任務，將揀選機器人的數量分別取11、12、13、14、15，結果如圖4所示。

圖4 19個任務具有硬時間窗約束下調度不同數量的揀選機器人完成所有任務所花費的總成本

圖4表示19個任務具有硬時間窗約束下調度不同數量的揀選機器人完成任務所花費的總成本，圖中可以看出當調度11臺揀選機器人時，上述任務可以順利完成。隨著揀選機器人的調度數量的增加，揀選機器人在揀選工作站的等待時間增加，使得完成所有任務的總時間也會增加，進而導致成本上升。

通過以上結果看出，對于具有硬時間窗約束的揀選機器人調度問題，當具有硬時間窗的任務增加到一定程度時，揀選機器人不能順利完成任務，可以通過增加揀選機器人的調度數量完成任務。但需要考慮機器人的硬件投入成本。

因此，針對上述任務，采用軟時間窗約束的方式，允許在可接受最早時刻前揀完和可接受最晚時刻后揀完，但通過加入懲罰成本對其進行懲罰。當18個任務具有時間窗約束時，采用硬時間窗約束的方式可以順利完成任務，因此按照軟時間窗約束方式與硬時間窗約束方式完成上述任務的時間相同，將max1與max2分別取0.5元、0.6元。仿真結果如圖5所示，揀選機器人調度結果見表5，表6為任務的軟時間窗以及完成揀選的時刻。

圖5 19個任務具有軟時間窗約束下揀選機器人完成所有任務所花費的總成本

表5 軟時間窗約束下揀選機器人調度結果

表6 具有時間約束的任務軟時間窗以及完成揀選的時刻

圖5表示19個任務具有軟時間窗約束下揀選機器人完成所有任務所花費的總時間，采用軟時間窗約束時所有的任務都可以順利完成，從表6中可以看出，只有第11個任務與第19個任務沒有在各自希望的時間范圍內完成，造成了一定的懲罰成本，其總成本為12.2885元，但該成本低于硬時間窗約束下調度11臺揀選機器人時所花費的總成本。

為了驗證軟時間窗約束下的揀選機器人調度模型，將具有時間約束的任務數量增加，仿真結果如圖6所示。

圖6 具有軟時間窗約束的任務總數不同情況下揀選機器人完成所有任務所花費的總成本

圖6為具有軟時間窗約束的任務總數不同情況下揀選機器人完成所有任務所花費的總成本，圖中可以明顯看出，隨著具有時間約束的任務數量增加，總成本呈緩慢上升趨勢，當有22個任務具有時間約束時，其總成本依然小于硬時間窗約束下調度11臺揀選機器人時所花費的總成本。

綜上分析，當智能倉儲系統對部分任務采用硬時間窗約束時，隨著有時間約束的任務數量增加，揀選機器人完成所有任務所花費的總成本增加，當具有時間約束的任務數量增加到一定程度時，揀選機器人不能順利完成所有任務，因此只能通過增加揀選機器人的調度數量使得任務能夠在其硬時間窗內順利完成。而當智能倉儲系統對部分任務采用軟時間窗約束時，所有任務都可以順利完成，可能會造成一定的懲罰成本，但其總成本低于采用硬時間窗約束時增加揀選機器人的調度數量所花費的總成本。由于智能倉儲系統中揀選機器人的數量有限，通過增加揀選機器人的調度數量來完成更多具有時間約束的任務不切實際，因此，采用軟時間窗約束的方式進行調度不僅可以完成所有任務，還可以降低智能倉儲系統運行的總成本。

5 結束語

在“貨到人”智能倉儲系統中，科學合理地調度揀選機器人完成任務是提高物流效率，降低物流成本的主要途徑。本文從揀選機器人調度角度進行優化，通過使系統的運行成本最小，即揀選機器人完成所有任務所花費的總成本最小，利用時間窗理論，以最大限度滿足系統對部分任務完成時間的要求，同時考慮揀選機器人在揀選工作站的排隊等待時間，分別建立硬時間窗約束下與軟時間窗約束下的揀選機器人調度模型。利用遺傳算法對兩模型進行求解，解決了揀選機器人的調度與揀選序列問題。仿真結果表明當具有時間約束的任務增加到一定數量時，采用軟時間窗約束的方式能夠使得所有任務順利完成，并且可以降低系統運行的成本，進而為“貨到人”智能倉儲系統的應用實踐提供了參考。