具有訂單完成時(shí)間約束的揀選機(jī)器人調(diào)度仿真

李 騰，馮 珊

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

1 引言

揀選作業(yè)是整個(gè)物流作業(yè)的關(guān)鍵環(huán)節(jié)，直接影響企業(yè)的服務(wù)水平。通過(guò)揀選機(jī)器人代替?zhèn)鹘y(tǒng)的人工揀選的智能倉(cāng)儲(chǔ)系統(tǒng)得到了越來(lái)越多的應(yīng)用[1-2]。目前，許多智能倉(cāng)儲(chǔ)系統(tǒng)，特別是電商平臺(tái)使用的智能倉(cāng)儲(chǔ)系統(tǒng)，體現(xiàn)出“揀選為主，存儲(chǔ)為輔”的特點(diǎn)，其關(guān)鍵在于如何高效地完成揀選作業(yè)以滿足消費(fèi)者對(duì)配送時(shí)效的要求[3]。科學(xué)合理地調(diào)度揀選機(jī)器人完成任務(wù)直接影響智能倉(cāng)儲(chǔ)系統(tǒng)的運(yùn)作效率，已經(jīng)成為智能倉(cāng)儲(chǔ)系統(tǒng)的研究重點(diǎn)[4-5]。

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

目前，對(duì)于機(jī)器人調(diào)度問(wèn)題的相關(guān)研究主要集中于集裝箱碼頭系統(tǒng)、生產(chǎn)制造系統(tǒng)與物流倉(cāng)儲(chǔ)系統(tǒng)，對(duì)于機(jī)器人調(diào)度問(wèn)題，部分訂單對(duì)完成時(shí)間有嚴(yán)格的要求，而上述文獻(xiàn)中沒(méi)有考慮任務(wù)的時(shí)間窗約束，并且上述有關(guān)智能倉(cāng)儲(chǔ)系統(tǒng)機(jī)器人調(diào)度文獻(xiàn)中，沒(méi)有考慮到機(jī)器人的等待時(shí)間。因此，本文針對(duì)智能倉(cāng)儲(chǔ)系統(tǒng)，在不改變已有任務(wù)下發(fā)順序的情況下，以揀選機(jī)器人執(zhí)行所有任務(wù)所花費(fèi)的總成本最小為優(yōu)化目標(biāo)，任務(wù)分配結(jié)果為決策變量，同時(shí)考慮揀選機(jī)器人在揀選工作站的排隊(duì)等待時(shí)間，分別建立硬時(shí)間窗約束與軟時(shí)間窗約束下的揀選機(jī)器人調(diào)度模型。

2 揀選機(jī)器人調(diào)度模型

2.1 問(wèn)題描述

“貨到人”智能倉(cāng)儲(chǔ)系統(tǒng)布局如圖1所示，主要由貨架、揀選機(jī)器人、揀選區(qū)域、揀選機(jī)器人停車區(qū)域，揀選機(jī)器人充電區(qū)域以及揀選機(jī)器人行走通道組成。其中，貨架的放置原則為背靠背放置，每個(gè)貨架的規(guī)格相同，并且每層貨架上存儲(chǔ)不同種類的貨物。貨架之間為揀選機(jī)器人的行走通道，揀選區(qū)域由多個(gè)揀選工作站組成，每個(gè)揀選工作站配有一名工作人員將指定的貨物從貨架中揀出。智能倉(cāng)儲(chǔ)系統(tǒng)的主要工作流程為：倉(cāng)庫(kù)管理系統(tǒng)接收訂單后，按照搬運(yùn)貨架次數(shù)最少的原則對(duì)訂單進(jìn)行分批，然后將處理后的訂單發(fā)送至調(diào)度系統(tǒng)，調(diào)度系統(tǒng)需要確認(rèn)訂單中任務(wù)所在貨架的位置以及各個(gè)揀選機(jī)器人的位置，其次調(diào)度揀選機(jī)器人來(lái)執(zhí)行任務(wù)。此時(shí)，揀選機(jī)器人將移動(dòng)到貨架位置，并將貨架托運(yùn)至規(guī)定的揀選工作站進(jìn)行排隊(duì)等待，該揀選工作站的工作人員按照揀選機(jī)器人到達(dá)的順序?qū)⒂唵沃械呢浳飶呢浖苤腥〕觯缓蠓胖迷谥付ǖ呢浵渲校瑫r(shí)揀選機(jī)器人將貨架托運(yùn)至原來(lái)位置，并在此位置等待調(diào)度系統(tǒng)為其再次分配任務(wù)。

圖1 智能倉(cāng)儲(chǔ)系統(tǒng)布局

智能倉(cāng)儲(chǔ)系統(tǒng)揀選機(jī)器人調(diào)度是指在調(diào)度系統(tǒng)的控制下，以某個(gè)參數(shù)為優(yōu)化目標(biāo)，確定各個(gè)揀選機(jī)器人將要執(zhí)行的任務(wù)以及各自執(zhí)行任務(wù)的順序，在滿足一定的約束條件下提高揀選效率，降低智能倉(cāng)儲(chǔ)系統(tǒng)的運(yùn)行成本。具有時(shí)間窗約束的揀選機(jī)器人調(diào)度問(wèn)題是指在傳統(tǒng)的揀選機(jī)器人調(diào)度問(wèn)題基礎(chǔ)上加入時(shí)間窗的約束，即智能倉(cāng)儲(chǔ)系統(tǒng)要求任務(wù)在一定時(shí)間范圍內(nèi)完成揀選工作。在智能倉(cāng)儲(chǔ)系統(tǒng)中，任務(wù)的下發(fā)順序取決于任務(wù)的到達(dá)時(shí)間，本文針對(duì)智能倉(cāng)儲(chǔ)系統(tǒng)揀選機(jī)器人調(diào)度問(wèn)題，在不改變?nèi)蝿?wù)序列的情況下，以最大限度滿足系統(tǒng)對(duì)時(shí)間的嚴(yán)格要求進(jìn)而提高消費(fèi)者滿意度。

針對(duì)智能倉(cāng)儲(chǔ)系統(tǒng)揀選機(jī)器人調(diào)度問(wèn)題，本文做出以下假設(shè)：

1)初始時(shí)刻，智能倉(cāng)儲(chǔ)系統(tǒng)中所有揀選機(jī)器人處于空閑狀態(tài)；

2)智能倉(cāng)儲(chǔ)系統(tǒng)中所有揀選機(jī)器人的行駛速度相同，不考慮揀選機(jī)器人的加減速；

3)揀選機(jī)器人在完成任務(wù)的過(guò)程中，電量始終充足；

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

5)揀選機(jī)器人在完成任務(wù)后，將貨架托運(yùn)至原來(lái)位置，并在此位置等待下一個(gè)任務(wù)；

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

2.2 數(shù)學(xué)模型

為建立數(shù)學(xué)模型，本文定義了如下參數(shù)：

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

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

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

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

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

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

7)tjc表示第j個(gè)任務(wù)被下發(fā)的時(shí)刻；

8)tlj表示第l個(gè)到達(dá)揀選工作站的第j個(gè)任務(wù)到達(dá)該揀選工作站的時(shí)刻；

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

10)tiljq表示由第i臺(tái)揀選機(jī)器人完成的第l個(gè)到達(dá)揀選工作站的第j個(gè)任務(wù)在該揀選工作站的等待時(shí)間；

11)Ti為第i臺(tái)揀選機(jī)器人完成被分配任務(wù)所花費(fèi)的總時(shí)間，T為所有任務(wù)的完成時(shí)間；

12)Cr表示每臺(tái)揀選機(jī)器人單位時(shí)間內(nèi)的運(yùn)行成本，C表示揀選機(jī)器人完成所有任務(wù)的總成本；

13)[tETk，tLTk]表示第k個(gè)任務(wù)最早最晚揀選完成的時(shí)間要求；

14)決策變量Xij表示第i臺(tái)揀選機(jī)器人是否完成第j個(gè)任務(wù)；

在智能倉(cāng)儲(chǔ)系統(tǒng)中，揀選機(jī)器人完成所有任務(wù)的總時(shí)間為所有揀選機(jī)器人完成各自任務(wù)所耗費(fèi)的最長(zhǎng)時(shí)間。本文以揀選機(jī)器人完成所有任務(wù)的總成本最小為目標(biāo)函數(shù)，以揀選機(jī)器人調(diào)度為決策變量，考慮了部分任務(wù)的時(shí)間窗約束以及揀選機(jī)器人在揀選工作站的排隊(duì)等待時(shí)間，分別建立硬時(shí)間窗的揀選機(jī)器人調(diào)度模型與軟時(shí)間窗的揀選機(jī)器人調(diào)度模型：

硬時(shí)間窗揀選機(jī)器人調(diào)度模型：

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)為揀選機(jī)器人調(diào)度模型的目標(biāo)函數(shù)，表示揀選機(jī)器人完成所有任務(wù)的總成本最小。式(2)表示揀選機(jī)器人完成所有任務(wù)所花費(fèi)的總時(shí)間。式(3)中揀選機(jī)器人完成任務(wù)的時(shí)間取決于揀選機(jī)器人的行走時(shí)間與在揀選工作站的排隊(duì)等待時(shí)間，并按照揀選機(jī)器人每次完成任務(wù)所停留的位置將其行走距離分為三個(gè)部分。式(4)表示揀選機(jī)器人在揀選工作站的排隊(duì)等待時(shí)間與揀選機(jī)器人到達(dá)揀選工作站的時(shí)刻和該揀選機(jī)器人所在排隊(duì)隊(duì)列中的前一臺(tái)揀選機(jī)器人被揀選完成的時(shí)刻有關(guān)。式(5)表示揀選機(jī)器人被揀選完成的時(shí)刻，取決于揀選機(jī)器人到達(dá)揀選工作站的時(shí)刻、揀選機(jī)器人在揀選工作站的排隊(duì)等待時(shí)間、工作人員的揀貨時(shí)間與分貨時(shí)間。式(6)表示智能倉(cāng)儲(chǔ)系統(tǒng)要求部分任務(wù)的揀選完成時(shí)間需要滿足時(shí)間窗約束。式(8)表示一個(gè)任務(wù)同時(shí)只能由一臺(tái)揀選機(jī)器人托運(yùn)。

軟時(shí)間窗揀選機(jī)器人調(diào)度模型

(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)

與硬時(shí)間窗揀選機(jī)器人調(diào)度模型相比較，軟時(shí)間窗揀選機(jī)器人調(diào)度模型中智能倉(cāng)儲(chǔ)系統(tǒng)對(duì)任務(wù)被揀選完成的時(shí)間要求沒(méi)有那么嚴(yán)格[12-13]，本文采用線性懲罰函數(shù)，即對(duì)沒(méi)有在系統(tǒng)希望時(shí)間范圍內(nèi)完成的任務(wù)予以懲罰。式(9)表示揀選機(jī)器人完成所有任務(wù)花費(fèi)的總成本，其中Cpk表示第k個(gè)具有時(shí)間窗約束的任務(wù)被揀選完成所造成的懲罰成本。式(14)中fk1與fk2分別表示具有時(shí)間窗約束的任務(wù)被提前或延遲揀完的單位懲罰成本，任務(wù)被延遲揀完產(chǎn)生的懲罰成本大于被提前揀完的懲罰成本，即fk2>fk1，tMETk表示任務(wù)k的可接受最早揀完時(shí)間，tMLTk表示任務(wù)k的可接受最晚揀完時(shí)間。

3 模型求解

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

1)設(shè)置初始種群的個(gè)數(shù)，確定一次下發(fā)任務(wù)的數(shù)量，將訂單中的任務(wù)按照每次的下發(fā)數(shù)量進(jìn)行分組，規(guī)定每組任務(wù)內(nèi)不能調(diào)用同一臺(tái)揀選機(jī)器人執(zhí)行任務(wù)，利用實(shí)數(shù)對(duì)染色體進(jìn)行編碼，染色體的長(zhǎng)度表示任務(wù)的總數(shù)，染色體中每個(gè)基因位表示任務(wù)的序號(hào)，基因位上的實(shí)數(shù)表示該序號(hào)的揀選機(jī)器人完成對(duì)應(yīng)基因位的任務(wù)。利用實(shí)數(shù)進(jìn)行編碼可以直接觀察到各個(gè)揀選機(jī)器人執(zhí)行的任務(wù)以及依次執(zhí)行的任務(wù)序列。

2)計(jì)算種群內(nèi)所有染色體的適應(yīng)度值。首先計(jì)算揀選機(jī)器人完成所有任務(wù)所花費(fèi)的運(yùn)行成本，其次觀察每個(gè)任務(wù)完成揀選的時(shí)刻是否符合其時(shí)間窗要求，計(jì)算由于不符合時(shí)間窗要求所造成的懲罰成本，最終染色體的適應(yīng)度值為揀選機(jī)器人執(zhí)行所有任務(wù)所花費(fèi)的總成本的倒數(shù)，以硬時(shí)間窗揀選機(jī)器人調(diào)度模型為例，其適應(yīng)度函數(shù)為：

(17)

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

4)確定交叉概率，本文將染色體按照每次下發(fā)任務(wù)的數(shù)量進(jìn)行分段，在染色體的段數(shù)范圍內(nèi)隨機(jī)生成兩個(gè)實(shí)數(shù)作為兩父代染色體的交叉位置，其次，兩父代染色體對(duì)應(yīng)交叉位置的基因段進(jìn)行交叉操作，產(chǎn)生新的個(gè)體，采用這種交叉方式保證了每組內(nèi)不會(huì)調(diào)用相同的揀選機(jī)器人執(zhí)行任務(wù)。

5)確定變異概率，在染色體長(zhǎng)度范圍內(nèi)，隨機(jī)生成一個(gè)實(shí)數(shù)作為父代染色體的變異位置，將此位置的基因變異成揀選機(jī)器人的序號(hào)，該序號(hào)不能與同一段基因位上的序號(hào)相同，代表不能同時(shí)調(diào)度一臺(tái)揀選機(jī)器人完成一組內(nèi)的多個(gè)任務(wù)。

6)設(shè)置最大迭代次數(shù)，如果迭代次數(shù)達(dá)到最大迭代次數(shù)，停止迭代，輸出揀選機(jī)器人完成所有任務(wù)所花費(fèi)的總成本、揀選機(jī)器人的調(diào)度結(jié)果與所有任務(wù)的揀選完成時(shí)間。

4 仿真與結(jié)果分析

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

表1 揀選機(jī)器人位置坐標(biāo)

表2 任務(wù)位置坐標(biāo)

首先對(duì)硬時(shí)間窗約束下的揀選機(jī)器人調(diào)度進(jìn)行仿真。若任務(wù)沒(méi)有在要求時(shí)間內(nèi)完成，懲罰成本設(shè)置為一個(gè)較大數(shù)值，相較于運(yùn)行成本，這里選擇懲罰成本為10元。仿真結(jié)果如圖2所示，揀選機(jī)器人調(diào)度結(jié)果見(jiàn)表3，任務(wù)的硬時(shí)間窗以及完成揀選的時(shí)刻見(jiàn)表4。

圖2 硬時(shí)間窗約束下完成所有任務(wù)所花費(fèi)的總成本

表3 硬時(shí)間窗約束下揀選機(jī)器人調(diào)度結(jié)果

表4 任務(wù)的硬時(shí)間窗以及完成揀選的時(shí)刻

圖2表示硬時(shí)間約束下揀選機(jī)器人完成所有任務(wù)所花費(fèi)的總成本，圖中可以看出隨著迭代次數(shù)的增加，成本不斷減少，最終得到最優(yōu)調(diào)度結(jié)果使其成本達(dá)到最小值，說(shuō)明遺傳算法能夠?qū)υ撃Ｐ瓦M(jìn)行求解。表3中揀選機(jī)器人調(diào)度結(jié)果的第一位數(shù)字表示揀選機(jī)器人的序號(hào)，后面為揀選機(jī)器人依次執(zhí)行的任務(wù)的序號(hào)。從表4中可以看出，所有具有硬時(shí)間窗約束的任務(wù)被揀完的時(shí)刻均在各自的硬時(shí)間窗范圍內(nèi)。

為進(jìn)一步驗(yàn)證硬時(shí)間窗約束的揀選機(jī)器人調(diào)度模型，將具有硬時(shí)間窗約束的任務(wù)數(shù)量增加，揀選機(jī)器人完成所有任務(wù)所花費(fèi)的總成本如圖3所示。

圖3 具有硬時(shí)間窗約束的任務(wù)總數(shù)不同情況下揀選機(jī)器人完成所有任務(wù)所花費(fèi)的總成本

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

因此，本文通過(guò)增加揀選機(jī)器人的調(diào)度數(shù)量來(lái)完成上述任務(wù)，將揀選機(jī)器人的數(shù)量分別取11、12、13、14、15，結(jié)果如圖4所示。

圖4 19個(gè)任務(wù)具有硬時(shí)間窗約束下調(diào)度不同數(shù)量的揀選機(jī)器人完成所有任務(wù)所花費(fèi)的總成本

圖4表示19個(gè)任務(wù)具有硬時(shí)間窗約束下調(diào)度不同數(shù)量的揀選機(jī)器人完成任務(wù)所花費(fèi)的總成本，圖中可以看出當(dāng)調(diào)度11臺(tái)揀選機(jī)器人時(shí)，上述任務(wù)可以順利完成。隨著揀選機(jī)器人的調(diào)度數(shù)量的增加，揀選機(jī)器人在揀選工作站的等待時(shí)間增加，使得完成所有任務(wù)的總時(shí)間也會(huì)增加，進(jìn)而導(dǎo)致成本上升。

通過(guò)以上結(jié)果看出，對(duì)于具有硬時(shí)間窗約束的揀選機(jī)器人調(diào)度問(wèn)題，當(dāng)具有硬時(shí)間窗的任務(wù)增加到一定程度時(shí)，揀選機(jī)器人不能順利完成任務(wù)，可以通過(guò)增加揀選機(jī)器人的調(diào)度數(shù)量完成任務(wù)。但需要考慮機(jī)器人的硬件投入成本。

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

圖5 19個(gè)任務(wù)具有軟時(shí)間窗約束下揀選機(jī)器人完成所有任務(wù)所花費(fèi)的總成本

表5 軟時(shí)間窗約束下揀選機(jī)器人調(diào)度結(jié)果

表6 具有時(shí)間約束的任務(wù)軟時(shí)間窗以及完成揀選的時(shí)刻

圖5表示19個(gè)任務(wù)具有軟時(shí)間窗約束下揀選機(jī)器人完成所有任務(wù)所花費(fèi)的總時(shí)間，采用軟時(shí)間窗約束時(shí)所有的任務(wù)都可以順利完成，從表6中可以看出，只有第11個(gè)任務(wù)與第19個(gè)任務(wù)沒(méi)有在各自希望的時(shí)間范圍內(nèi)完成，造成了一定的懲罰成本，其總成本為12.2885元，但該成本低于硬時(shí)間窗約束下調(diào)度11臺(tái)揀選機(jī)器人時(shí)所花費(fèi)的總成本。

為了驗(yàn)證軟時(shí)間窗約束下的揀選機(jī)器人調(diào)度模型，將具有時(shí)間約束的任務(wù)數(shù)量增加，仿真結(jié)果如圖6所示。

圖6 具有軟時(shí)間窗約束的任務(wù)總數(shù)不同情況下揀選機(jī)器人完成所有任務(wù)所花費(fèi)的總成本

圖6為具有軟時(shí)間窗約束的任務(wù)總數(shù)不同情況下揀選機(jī)器人完成所有任務(wù)所花費(fèi)的總成本，圖中可以明顯看出，隨著具有時(shí)間約束的任務(wù)數(shù)量增加，總成本呈緩慢上升趨勢(shì)，當(dāng)有22個(gè)任務(wù)具有時(shí)間約束時(shí)，其總成本依然小于硬時(shí)間窗約束下調(diào)度11臺(tái)揀選機(jī)器人時(shí)所花費(fèi)的總成本。

綜上分析，當(dāng)智能倉(cāng)儲(chǔ)系統(tǒng)對(duì)部分任務(wù)采用硬時(shí)間窗約束時(shí)，隨著有時(shí)間約束的任務(wù)數(shù)量增加，揀選機(jī)器人完成所有任務(wù)所花費(fèi)的總成本增加，當(dāng)具有時(shí)間約束的任務(wù)數(shù)量增加到一定程度時(shí)，揀選機(jī)器人不能順利完成所有任務(wù)，因此只能通過(guò)增加揀選機(jī)器人的調(diào)度數(shù)量使得任務(wù)能夠在其硬時(shí)間窗內(nèi)順利完成。而當(dāng)智能倉(cāng)儲(chǔ)系統(tǒng)對(duì)部分任務(wù)采用軟時(shí)間窗約束時(shí)，所有任務(wù)都可以順利完成，可能會(huì)造成一定的懲罰成本，但其總成本低于采用硬時(shí)間窗約束時(shí)增加揀選機(jī)器人的調(diào)度數(shù)量所花費(fèi)的總成本。由于智能倉(cāng)儲(chǔ)系統(tǒng)中揀選機(jī)器人的數(shù)量有限，通過(guò)增加揀選機(jī)器人的調(diào)度數(shù)量來(lái)完成更多具有時(shí)間約束的任務(wù)不切實(shí)際，因此，采用軟時(shí)間窗約束的方式進(jìn)行調(diào)度不僅可以完成所有任務(wù)，還可以降低智能倉(cāng)儲(chǔ)系統(tǒng)運(yùn)行的總成本。

5 結(jié)束語(yǔ)

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