“貨到人”揀選系統(tǒng)機(jī)器人任務(wù)分配的魯棒雙層規(guī)劃模型

李 騰， 馮 珊， 宋 君， 劉金芳

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

0 引言

隨著互聯(lián)網(wǎng)經(jīng)濟(jì)的發(fā)展，電子商務(wù)行業(yè)在訂單呈現(xiàn)多品類、小批量，高頻次特點(diǎn)的背景下，為了提高消費(fèi)者對(duì)配送時(shí)效的需求，越來(lái)越關(guān)注高效的物流體系。揀選作業(yè)是占整個(gè)物流作業(yè)時(shí)間最多的環(huán)節(jié)，揀選效率的提高更加受到企業(yè)的重視，傳統(tǒng)的揀選方式是人工主導(dǎo)型，這種“人到貨”的揀選方式效率較低，因此新型的“貨到人”的揀選方式越來(lái)越受到青睞[1]。目前，應(yīng)用最廣泛的“貨到人”揀選系統(tǒng)為美國(guó)亞馬遜的Kiva系統(tǒng)。本文主要研究以Kiva為代表的基于移動(dòng)機(jī)器人的“貨到人”揀選系統(tǒng)。其機(jī)器人任務(wù)分配是指將每個(gè)任務(wù)分別分配給系統(tǒng)中的機(jī)器人執(zhí)行，由機(jī)器人將貨物所在的貨架搬運(yùn)至揀選臺(tái)以供揀選，即貨動(dòng)人不動(dòng)，在這種多機(jī)器人、多任務(wù)、并行作業(yè)的系統(tǒng)中如何調(diào)度機(jī)器人并將任務(wù)合理地分配給機(jī)器人決定著整個(gè)系統(tǒng)的運(yùn)行效率與成本[2]。

近年來(lái)，很多學(xué)者對(duì)不同應(yīng)用領(lǐng)域的機(jī)器人調(diào)度與任務(wù)分配問(wèn)題進(jìn)行了研究。Nielsen等[3]對(duì)配送能力約束下的機(jī)器人調(diào)度問(wèn)題進(jìn)行了研究，利用改進(jìn)的遺傳算法解決了機(jī)器人每次的配送量。周炳海等[4]考慮機(jī)器人之間的協(xié)同調(diào)度，以最小化機(jī)器人數(shù)量和降低能耗成本為目標(biāo)，利用聚類啟發(fā)式方法與自適應(yīng)大鄰域搜索算法驗(yàn)證了協(xié)同調(diào)度的優(yōu)勢(shì)。沈博聞等[5]將物流任務(wù)進(jìn)行分解，考慮了路徑成本與等待時(shí)間成本，對(duì)機(jī)器人調(diào)度進(jìn)行研究并驗(yàn)證了智能調(diào)度的有效性。

多機(jī)器人任務(wù)分配主要分為集中式任務(wù)分配與分布式任務(wù)分配，集中式任務(wù)分配不適于解決大規(guī)模任務(wù)分配問(wèn)題，所以許多學(xué)者分別利用基于市場(chǎng)機(jī)制方法、拍賣算法與群合作法等分布式任務(wù)分配方法解決該問(wèn)題。蘇麗穎等[6]提出了一種基于分布式的任務(wù)分配方法，利用組合拍賣的理論建立模型，證明了這種方法能夠得到合理的任務(wù)分配結(jié)果。周菁與慕德俊[7]針對(duì)多機(jī)器人系統(tǒng)任務(wù)分配問(wèn)題，通過(guò)設(shè)計(jì)分布式的多機(jī)器人系統(tǒng)，實(shí)現(xiàn)了以負(fù)載平衡為優(yōu)化目標(biāo)的任務(wù)分配。Arif等[8]將多機(jī)器人任務(wù)分配問(wèn)題表示為多旅行商問(wèn)題的一個(gè)推廣，并利用EA算法進(jìn)行最優(yōu)任務(wù)分配。Janati等[9]提出了一種基于聚類的多機(jī)器人任務(wù)分配方法，利用遺傳算法與模仿學(xué)習(xí)算法相結(jié)合進(jìn)行求解，節(jié)省了運(yùn)行時(shí)間。

從上述文獻(xiàn)可知，將機(jī)器人調(diào)度與任務(wù)分配問(wèn)題相結(jié)合的研究較少，現(xiàn)有研究多數(shù)以時(shí)間或運(yùn)行成本為優(yōu)化目標(biāo)，沒(méi)有考慮機(jī)器人的空閑成本，并且上述文獻(xiàn)都是在確定的環(huán)境下進(jìn)行決策，對(duì)不確定環(huán)境下的機(jī)器人調(diào)度與任務(wù)分配問(wèn)題尚未解決，而“貨到人”揀選系統(tǒng)中的環(huán)境往往是不確定的，系統(tǒng)中的不確定因素必須加以考慮。因此，本文將機(jī)器人的平均空閑率作為目標(biāo)函數(shù)進(jìn)行任務(wù)分配，參考了車輛調(diào)度問(wèn)題[10,11]，將二者結(jié)合建立了雙層規(guī)劃模型，在機(jī)器人完成所有任務(wù)平均空閑率最小的同時(shí)，通過(guò)機(jī)器人調(diào)度使其成本最小化，既可以解決機(jī)器人的調(diào)度問(wèn)題，同時(shí)也可以實(shí)現(xiàn)機(jī)器人的任務(wù)分配。考慮了機(jī)器人在完成任務(wù)過(guò)程中由于調(diào)度、避障、路徑規(guī)劃等導(dǎo)致的行走距離不確定因素，利用魯棒優(yōu)化的相關(guān)理論建立魯棒雙層規(guī)劃模型。進(jìn)而提高系統(tǒng)的魯棒性，降低成本。

1 問(wèn)題描述及符號(hào)定義

“貨到人”揀選系統(tǒng)機(jī)器人的任務(wù)分配問(wèn)題可以描述為：系統(tǒng)接受訂單后，將訂單按照一定規(guī)則分批處理，系統(tǒng)需要確認(rèn)每個(gè)訂單中貨物所在貨架的位置，然后調(diào)度系統(tǒng)中一定數(shù)量的機(jī)器人，并將任務(wù)進(jìn)行分配。在機(jī)器人完成任務(wù)的過(guò)程中，機(jī)器人首先從初始位置移動(dòng)到貨架所在位置并將其搬運(yùn)至揀選臺(tái)，揀選人員根據(jù)貨物的信息在該貨架上揀選貨物，將其放在指定的區(qū)域。當(dāng)系統(tǒng)中所有揀選臺(tái)都被其他機(jī)器人占用時(shí)，機(jī)器人就會(huì)進(jìn)行排隊(duì)等待，直到被揀選完畢。揀選完成后，機(jī)器人將貨架搬運(yùn)到該貨架的原來(lái)位置，在此位置等待下一次任務(wù)的分配。要求每個(gè)機(jī)器人同時(shí)只可以搬運(yùn)一個(gè)貨架，每個(gè)貨架同時(shí)只能由一個(gè)機(jī)器人進(jìn)行搬運(yùn)。圖1為機(jī)器人完成單個(gè)任務(wù)的流程，可以分解為3個(gè)步驟。

圖1 機(jī)器人完成單個(gè)任務(wù)的流程圖

為了便于構(gòu)建模型，本文做出以下假設(shè)：

(1)初始時(shí)刻，系統(tǒng)中所有的機(jī)器人處于空閑狀態(tài)。

(2)完成任務(wù)時(shí)，所有機(jī)器人的電量一直大于20%。

(3)系統(tǒng)中所有機(jī)器人的初始位置是隨機(jī)的。

(4)系統(tǒng)中所有的任務(wù)分布在不同的貨架中，并且不存在缺貨現(xiàn)象。

(5)機(jī)器人將貨架搬回后，在該貨架位置等待下一個(gè)任務(wù)的分配。

(6)忽略機(jī)器人在揀選臺(tái)的等待時(shí)間。

符號(hào)定義如下：

(1)R為機(jī)器人集，n為揀選系統(tǒng)中機(jī)器人的數(shù)量，Ri表示揀選系統(tǒng)中的第i個(gè)機(jī)器人，其中i∈[1,n]；Z為任務(wù)集，m為揀選系統(tǒng)中任務(wù)的數(shù)量，Zj表示揀選系統(tǒng)中的第j個(gè)任務(wù)，其中j∈[1,m]；P為揀選臺(tái)集，p為揀選系統(tǒng)中揀選臺(tái)的數(shù)量，Pk表示揀選系統(tǒng)中的第k個(gè)揀選臺(tái)，其中k∈[1,p]；

(2)(xAi,yAi)表示機(jī)器人Ri的位置坐標(biāo)，(xBj,yBj)表示任務(wù)Zj的位置坐標(biāo)，(xPk,yPk)表示揀選臺(tái)Pk的位置坐標(biāo)；

(3)d1ioj表示機(jī)器人Ri從初始位置到任務(wù)Zj所行走的距離的標(biāo)稱值，d2ijk表示機(jī)器人Ri從任務(wù)Zj到揀選臺(tái)Pk時(shí)所行走的距離的標(biāo)稱值，d3ikj表示機(jī)器人Ri從揀選臺(tái)Pk回到任務(wù)Zj時(shí)所行走的距離的標(biāo)稱值，本文所有距離計(jì)算均采用曼哈頓距離，即

d1ioj=|xAi-xBj|+|yAi-yBj|

(1)

d2ijk=|xBj-xPk|+|yBj-yPk|

(2)

d3ikj=|xPk-xBj|+|yPk-yBj|

(3)

(4)Dij為機(jī)器人Ri完成任務(wù)Zj所行走的總距離，即

Dij=d1ioj+d2ijk+d3ikj

(4)

(5)W為所有機(jī)器人Ri和所有任務(wù)Zj之間距離段集合；

(6)Vi表示機(jī)器人Ri的行走速度；

(7)T0為所有機(jī)器人完成任務(wù)的時(shí)間；

(8)Tij為機(jī)器人Ri完成任務(wù)Zj所花費(fèi)的時(shí)間，即

(5)

(9)αi表示機(jī)器人Ri的空閑率，則

(6)

(7)

(11)Di表示機(jī)器人Ri完成所有任務(wù)的行走距離；

(12)決策變量Yi表示是否調(diào)度機(jī)器人Ri來(lái)完成任務(wù)，則

(8)

(13)Cr為機(jī)器人行走單位距離所花費(fèi)的成本，Cf為單位時(shí)間每臺(tái)機(jī)器人的空閑成本，Cp為每臺(tái)機(jī)器人的固定成本即購(gòu)買成本，C為n個(gè)機(jī)器人完成m個(gè)任務(wù)所花費(fèi)的總成本；

(14)決策變量Xij表示機(jī)器人Ri是否完成任務(wù)Zj，則

(9)

2 模型構(gòu)建與求解

2.1 不考慮距離變化的任務(wù)分配雙層規(guī)劃模型

雙層規(guī)劃模型具有主從遞階結(jié)構(gòu)，最早由Bracken和McGill[12]提出。其上層問(wèn)題的決策變量制約下層問(wèn)題的最優(yōu)結(jié)果，下層問(wèn)題的決策變量影響上層問(wèn)題的最優(yōu)結(jié)果[13]。雙層規(guī)劃具有層次性、沖突性、獨(dú)立性、優(yōu)先性、自主性、制約性等特點(diǎn)，其研究的系統(tǒng)是分層的，上層決策者首先進(jìn)行決策，下層決策者需要對(duì)其決策結(jié)果做出反應(yīng)并且具有一定的自主決策權(quán)，上層決策者需要根據(jù)下層的反應(yīng)再次進(jìn)行決策[14]。雙層優(yōu)化能很好地描述分層系統(tǒng)優(yōu)化問(wèn)題，該方法多用于解決設(shè)施選址、生產(chǎn)計(jì)劃以及應(yīng)急物資運(yùn)輸?shù)葐?wèn)題。如Yegane等[15]針對(duì)配送中心選址問(wèn)題建立雙層規(guī)劃模型，提出了自適應(yīng)雙層蟻群算法進(jìn)行求解，實(shí)現(xiàn)了利潤(rùn)最大化。Calvete等[16]對(duì)生產(chǎn)分配問(wèn)題進(jìn)行研究，考慮了不同決策者分別控制生產(chǎn)與分配問(wèn)題，以成本最小為目標(biāo)建立雙層規(guī)劃模型，利用蟻群算法進(jìn)行求解，解決了生產(chǎn)分配問(wèn)題。Camacho-Vallejo等[17]針對(duì)應(yīng)急物資運(yùn)輸問(wèn)題建立雙層規(guī)劃模型，對(duì)運(yùn)輸成本進(jìn)行優(yōu)化，解決了災(zāi)難后國(guó)際救援分配的決策問(wèn)題。

由于“貨到人”揀選系統(tǒng)中的機(jī)器人調(diào)度與任務(wù)分配之間的決策存在著上述層次關(guān)系，所以本節(jié)借鑒慶艷華等[18]利用此方法研究選址問(wèn)題的模型，考慮了機(jī)器人調(diào)度與機(jī)器人任務(wù)分配問(wèn)題，建立雙層規(guī)劃模型，以機(jī)器人完成所有任務(wù)的總成本為目標(biāo)函數(shù)，機(jī)器人調(diào)度為決策變量，建立上層模型；考慮機(jī)器人在完成任務(wù)過(guò)程中處于空閑狀態(tài)時(shí)所花費(fèi)的成本，以機(jī)器人的平均空閑率為目標(biāo)函數(shù)，任務(wù)分配為決策變量，建立下層模型。上層的機(jī)器人調(diào)度結(jié)果制約下層的機(jī)器人平均空閑率，下層的任務(wù)分配結(jié)果影響上層的總成本，上下層結(jié)果共同決定了機(jī)器人的配置決策。

上層模型：

(10)

下層模型：

(13)

s.t.Xij∈{0,1},i=1,2,3,…,n;j=1,2,3,…,m

(14)

(15)

(16)

下層模型中，Xij為決策變量，表示機(jī)器人Ri是否完成任務(wù)Zj，αi表示在單批訂單完成的時(shí)間內(nèi)，機(jī)器人Ri的空閑率，式中將機(jī)器人完成一個(gè)任務(wù)所行走的距離分為三個(gè)部分。式(15)表示一個(gè)任務(wù)只允許由一個(gè)機(jī)器人完成，式(16)表示被調(diào)度的機(jī)器人至少完成一個(gè)任務(wù)。

2.2 考慮距離變化的任務(wù)分配魯棒雙層規(guī)劃模型

在現(xiàn)實(shí)的優(yōu)化問(wèn)題中，一些數(shù)據(jù)往往是具有不確定性的，傳統(tǒng)的不確定優(yōu)化方法通常采用先驗(yàn)知識(shí)和不確定數(shù)據(jù)的分布假設(shè)解決不確定性問(wèn)題，但數(shù)據(jù)發(fā)生變化時(shí)，最優(yōu)解也會(huì)變化。魯棒優(yōu)化是針對(duì)傳統(tǒng)的不確定優(yōu)化方法的不足而提出的一種更有效的不確定優(yōu)化方法，對(duì)不確定數(shù)據(jù)的分布沒(méi)有規(guī)定，其關(guān)鍵在于構(gòu)建不確定參數(shù)的集合，可用于解決最壞情況下的最優(yōu)績(jī)效[19,20]。當(dāng)參數(shù)在集合范圍內(nèi)發(fā)生變化時(shí)，最優(yōu)解不發(fā)生變化，使得優(yōu)化的模型具有一定的魯棒性，對(duì)參數(shù)的變化不敏感，最優(yōu)解具有一定的穩(wěn)健性[21]。目前魯棒優(yōu)化方法被應(yīng)用到各個(gè)領(lǐng)域，如Bertsimas等[22]研究了呼叫中心人員配置問(wèn)題，考慮了呼叫中心顧客到達(dá)的不確定性，建立人員配置的魯棒優(yōu)化模型，實(shí)現(xiàn)了人員的合理配置并降低了系統(tǒng)的成本。Leung等[23]對(duì)多站點(diǎn)生產(chǎn)計(jì)劃問(wèn)題進(jìn)行研究，考慮了生產(chǎn)過(guò)程中各個(gè)站點(diǎn)的需求、勞動(dòng)成本等不確定因素，以成本最小為優(yōu)化目標(biāo)，利用魯棒優(yōu)化方法解決了不確定環(huán)境下的多站點(diǎn)生產(chǎn)計(jì)劃問(wèn)題。Akbari[24]等對(duì)供應(yīng)鏈網(wǎng)絡(luò)進(jìn)行優(yōu)化，利用魯棒優(yōu)化方法解決了生產(chǎn)過(guò)程中的不確定因素，降低了運(yùn)輸與庫(kù)存成本。

Soyster[25]提出了魯棒優(yōu)化理論，用來(lái)解決具有不確定性的線性優(yōu)化問(wèn)題。之后Ben-Tal、Nemirovski[26～28]深入研究了魯棒優(yōu)化理論，但提出的魯棒優(yōu)化方法增加了求解的復(fù)雜度。Bertsimas等[29]提出的魯棒優(yōu)化理論可以解決線性問(wèn)題與離散型問(wèn)題，其最終的魯棒對(duì)等式仍為線性優(yōu)化問(wèn)題，便于求解且控制了優(yōu)化解的保守程度。因此，本文利用了Bertsimas的魯棒離散優(yōu)化理論將不確定問(wèn)題進(jìn)行轉(zhuǎn)換。

Bertsimas將不確定性組合優(yōu)化問(wèn)題進(jìn)行如下轉(zhuǎn)換:

mincTx

(17)

s.t.x∈X

(18)

上述模型不能直接求解，需要進(jìn)行魯棒對(duì)等轉(zhuǎn)換，因此引入魯棒控制參數(shù)Γ0表示不確定參數(shù)的個(gè)數(shù)，Γ0通常取整數(shù)，因此，組合優(yōu)化問(wèn)題的魯棒模型為:

(20)

假定d1≥d2≥…≥dn，令dn+1=0，Bertsimas將式(19) 轉(zhuǎn)化為對(duì)n+1個(gè)標(biāo)稱問(wèn)題進(jìn)行求解，其目標(biāo)函數(shù)為:

(22)

在機(jī)器人完成任務(wù)的過(guò)程中，如果多個(gè)任務(wù)同時(shí)聚集在一定的區(qū)域內(nèi)，會(huì)使得多個(gè)機(jī)器人之間的行走路徑發(fā)生沖突，為了減少機(jī)器人之間發(fā)生碰撞或減少機(jī)器人的等待時(shí)間，調(diào)度系統(tǒng)會(huì)調(diào)度機(jī)器人行走其他路徑完成任務(wù)，無(wú)論機(jī)器人選擇等待還是改變路徑，都會(huì)影響任務(wù)的完成時(shí)間，進(jìn)而影響機(jī)器人完成任務(wù)的效率，因此考慮了機(jī)器人在完成任務(wù)過(guò)程中由于調(diào)度、避障、路徑規(guī)劃等導(dǎo)致的行走距離不確定因素，將機(jī)器人等待的時(shí)間與路徑的改變轉(zhuǎn)換為行走距離的增加，由此可見(jiàn)，機(jī)器人完成任務(wù)的實(shí)際行走距離不一定是機(jī)器人完成任務(wù)的曼哈頓距離，所以采用區(qū)間值的形式表示機(jī)器人完成任務(wù)的實(shí)際行走距離。

引入?yún)?shù)J，J表示受不確定距離影響的路段集合,|J|表示受不確定距離影響的路段的個(gè)數(shù)，|J|∈「0,|W|?。

引入?yún)?shù)Γ，?！省?,|J|?，用來(lái)控制不確定距離的保守度，這里令Γ取整數(shù)，當(dāng)Γ=0時(shí)，不考慮距離偏差的影響，此時(shí)任務(wù)分配模型與2.1節(jié)中模型一致，對(duì)不確定距離最敏感；隨著Γ值的增大，增加了魯棒性，模型對(duì)不確定距離的敏感程度會(huì)下降；當(dāng)Γ=|W|時(shí)，所有路段的距離均為不確定距離，這時(shí)模型對(duì)不確定距離最不敏感，其任務(wù)分配結(jié)果最保守。

機(jī)器人任務(wù)分配魯棒雙層規(guī)劃模型：

上層模型：

(23)

(25)

下層模型:

(26)

s.t.Xij∈{0,1},i=1,2,3,…,n,j=1,2,3,…,m

(27)

(28)

(29)

式(26)考慮了機(jī)器人在完成任務(wù)時(shí)不確定距離的偏差，表示在不確定距離偏差最大的情況下進(jìn)行任務(wù)分配，進(jìn)而使得機(jī)器人的平均空閑率最小。目標(biāo)函數(shù)中含有max項(xiàng)，不能直接求解，本文利用魯棒離散轉(zhuǎn)換規(guī)則，將下層模型的目標(biāo)函數(shù)進(jìn)行如下轉(zhuǎn)換：

下層模型：

(30)

由此可得機(jī)器人任務(wù)分配魯棒雙層規(guī)劃模型：

上層模型:

(33)

下層模型：

(34)

(35)

s.t.Xij∈{0,1},i=1,2,3,…,n;j=1,2,3,…,m

(36)

(37)

(38)

2.3 模型求解

遺傳算法是模擬生物自然選擇與遺傳進(jìn)化過(guò)程的一種優(yōu)化算法，該算法是在初始種群中根據(jù)適應(yīng)度函數(shù)選擇較優(yōu)的個(gè)體，通過(guò)對(duì)染色體進(jìn)行交叉變異等操作，按照優(yōu)勝劣汰的原則更新種群，最終得到適應(yīng)度值最高的染色體[30]。遺傳算法具有并行性、高效性與自適應(yīng)等特點(diǎn)，便于求解組合優(yōu)化問(wèn)題[31]。鑒于多機(jī)器人調(diào)度與任務(wù)分配問(wèn)題為NP-hard問(wèn)題，當(dāng)任務(wù)的數(shù)量增加時(shí)，精確算法所需求解時(shí)間增加，遺傳算法在求解該類問(wèn)題時(shí)，績(jī)效表現(xiàn)良好。因此利用雙層遺傳算法與迭代相結(jié)合進(jìn)行模型求解。

模型的求解具體計(jì)算步驟如下：

Step1確定機(jī)器人調(diào)度的最小數(shù)量。

Step2確定所調(diào)度的機(jī)器人的序號(hào)，采用機(jī)器人序號(hào)對(duì)調(diào)度問(wèn)題進(jìn)行編碼產(chǎn)生初始種群，計(jì)算這些機(jī)器人到所有任務(wù)的平均距離。

Step3在上層確定機(jī)器人調(diào)度數(shù)量及調(diào)度結(jié)果的基礎(chǔ)上，利用遺傳算法對(duì)下層模型進(jìn)行求解。首先設(shè)置控制參數(shù)；采用所調(diào)度的機(jī)器人序號(hào)對(duì)任務(wù)分配情況進(jìn)行編碼來(lái)產(chǎn)生初始種群，即每條染色體中的元素值都是所調(diào)度機(jī)器人的序號(hào)，代表該序號(hào)的機(jī)器人完成該位置的任務(wù)，并保證所調(diào)度機(jī)器人的序號(hào)在染色體中至少出現(xiàn)一次；計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度值，適應(yīng)度值為機(jī)器人完成所有任務(wù)所行走的總距離的倒數(shù)，即機(jī)器人完成所有任務(wù)所行走的總距離越小，該個(gè)體的適應(yīng)度值越大；選擇一定數(shù)量的優(yōu)良個(gè)體進(jìn)入下一代種群作為父代；按照交叉概率選擇兩個(gè)父代個(gè)體，并使染色體的隨機(jī)一段基因進(jìn)行交叉從而生成新的個(gè)體； 按照變異概率對(duì)選擇個(gè)體進(jìn)行變異，變異時(shí)只可以將染色體的某個(gè)基因變異成所調(diào)度的某個(gè)機(jī)器人的序號(hào)；如果達(dá)到了設(shè)置的最大迭代次數(shù)，則停止迭代并輸出機(jī)器人完成所有任務(wù)所行走的最短距離、任務(wù)的分配結(jié)果以及機(jī)器人的平均空閑率，否則繼續(xù)計(jì)算。

Step4將Step 2得到的計(jì)算結(jié)果與Step 3得到的機(jī)器人平均空閑率帶入上層模型，求出機(jī)器人完成所有任務(wù)所花費(fèi)的總成本。直到最小成本不再發(fā)生變化，找到調(diào)度該數(shù)量機(jī)器人下的最小總成本，并得到了任務(wù)的調(diào)度結(jié)果與任務(wù)分配結(jié)果。

Step5將機(jī)器人的調(diào)度數(shù)量增加一個(gè)，返回Step 1。

Step6機(jī)器人的調(diào)度數(shù)量等于系統(tǒng)中機(jī)器人的最大數(shù)量，停止計(jì)算，輸出歷史最優(yōu)成本作為最終結(jié)果。

模型的求解流程如圖2所示：

圖2 雙層遺傳算法求解流程圖

3 實(shí)例仿真與分析

3.1 實(shí)例描述

仿真環(huán)境設(shè)定為一個(gè)某50m×50m 的倉(cāng)庫(kù)，如圖3所示。機(jī)器人的速度為1米/秒，按照每臺(tái)機(jī)器人的折舊費(fèi)用為2萬(wàn)/年計(jì)算得出，每臺(tái)機(jī)器人在單位時(shí)間內(nèi)的空閑成本為0.0006元/秒，按照每臺(tái)機(jī)器人的功率為100w/小時(shí)，電費(fèi)為0.86元/千瓦時(shí)計(jì)算得出，其行走單位距離所花費(fèi)的成本為0.00083元/米，每臺(tái)機(jī)器人的固定成本為7萬(wàn)元，機(jī)器人的最大數(shù)量為8個(gè)，模擬單批訂單，其任務(wù)數(shù)量為30個(gè)，揀選臺(tái)的位置為(20,10)，隨機(jī)指定機(jī)器人的初始位置如表1所示，任務(wù)所在的貨架位置如表2所示。

表1 機(jī)器人坐標(biāo)

圖3 仿真?zhèn)}庫(kù)布局

3.2 雙層規(guī)劃模型的機(jī)器人任務(wù)分配仿真結(jié)果與分析

首先，對(duì)雙層規(guī)劃模型的機(jī)器人任務(wù)分配問(wèn)題進(jìn)行仿真，遺傳算法參數(shù)中，初始種群個(gè)數(shù)為700個(gè)，最大迭代次數(shù)設(shè)為100次，交叉概率與變異概率分別為0.9和0.8。調(diào)度3～8個(gè)機(jī)器人來(lái)完成所有任務(wù)，由于機(jī)器人數(shù)量較少，所以本節(jié)將上層模型采用遍歷方式進(jìn)行仿真，由于機(jī)器人的固定成本相同，因此以下仿真結(jié)果只包括機(jī)器人的運(yùn)行成本以及空閑成本。仿真結(jié)果如圖4所示。

通過(guò)圖4可以得出調(diào)度不同數(shù)量的機(jī)器人，其最小成本不同，當(dāng)調(diào)度6個(gè)機(jī)器人時(shí)，機(jī)器人完成所有任務(wù)所花費(fèi)的總成本最小，此時(shí)，得到的不同調(diào)度結(jié)果對(duì)應(yīng)的成本如圖5所示，圖4中調(diào)度7個(gè)或8個(gè)機(jī)器人時(shí)所花費(fèi)的成本高于調(diào)用6個(gè)機(jī)器人的成本，是由于隨著機(jī)器人調(diào)度的數(shù)量增加，機(jī)器人的平均空閑率增大，所花費(fèi)的成本增加。

圖4 調(diào)度不同數(shù)量機(jī)器人完成任務(wù)所花費(fèi)的最小成本

圖5 不同調(diào)度方案下機(jī)器人完成任務(wù)所花費(fèi)的成本

圖5表示調(diào)度6個(gè)機(jī)器人時(shí)，不同調(diào)度方案下機(jī)器人完成任務(wù)所花費(fèi)的成本，其中橫坐標(biāo)表示調(diào)度方案共28種，縱坐標(biāo)表示成本。仿真結(jié)果顯示調(diào)用第1、2、3、4、5、7個(gè)機(jī)器完成任務(wù)時(shí)，所花費(fèi)的成本最小，此時(shí)機(jī)器人行走的總距離如圖6所示。

圖6 成本最優(yōu)下機(jī)器人行走總距離

因此，雙層規(guī)劃模型的機(jī)器人任務(wù)分配問(wèn)題得到的機(jī)器人配置、調(diào)度以及任務(wù)分配結(jié)果如表3所示。

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

表3 雙層規(guī)劃模型的機(jī)器人配置、調(diào)度以及任務(wù)分配結(jié)果

表中任務(wù)分配結(jié)果的第一個(gè)數(shù)字代表調(diào)度的機(jī)器人序號(hào)，后面數(shù)字則代表該機(jī)器人所完成的任務(wù)序號(hào)。

3.3 魯棒雙層規(guī)劃模型的機(jī)器人任務(wù)分配仿真結(jié)果與分析

將不確定距離分為三段，在本仿真實(shí)例中，機(jī)器人完成任務(wù)可能行走的距離共1200段，Γ表示不確定距離的個(gè)數(shù)，當(dāng)Γ=0時(shí)，所有距離不變，與原來(lái)模型計(jì)算結(jié)果一致，這里分別取Γ=0,40,80,120,160,200,300，表4為機(jī)器人配置、調(diào)度及任務(wù)分配結(jié)果，圖7為對(duì)應(yīng)的成本。

圖7 魯棒雙層規(guī)劃模型的機(jī)器人完成任務(wù)的最小成本

表4 魯棒雙層規(guī)劃模型的機(jī)器人的配置、調(diào)度以及任務(wù)分配結(jié)果

從表中看出，發(fā)生變化的距離個(gè)數(shù)不同，機(jī)器人完成所有任務(wù)所花費(fèi)的成本不同、其數(shù)量配置、調(diào)度方案、以及任務(wù)的分配結(jié)果也會(huì)發(fā)生變化。

在本仿真實(shí)例中，完成30個(gè)任務(wù)需要行走90段距離，為了驗(yàn)證魯棒雙層規(guī)劃模型的有效性，使機(jī)器人的行走距離在指定范圍內(nèi)隨機(jī)發(fā)生變化，取，表示從1段距離發(fā)生變化直到30段距離發(fā)生變化，兩個(gè)模型的仿真結(jié)果如圖8所示。

圖8 兩個(gè)模型下機(jī)器人完成所有任務(wù)行走總距離

圖8中橫坐標(biāo)為不確定距離段的個(gè)數(shù)，縱坐標(biāo)為機(jī)器人完成所有任務(wù)行走的總距離，虛線為雙層規(guī)劃模型的機(jī)器人完成所有任務(wù)行走的總距離，實(shí)線為魯棒雙層規(guī)劃模型的機(jī)器人完成所有任務(wù)行走的總距離。隨著不確定距離數(shù)量的增加，使用雙層規(guī)劃模型得到的機(jī)器人完成所有任務(wù)行走的總距離明顯多于使用魯棒雙層規(guī)劃模型得到的機(jī)器人完成所有任務(wù)行走的總距離并且呈上升趨勢(shì)，而魯棒雙層規(guī)劃模型的曲線波動(dòng)范圍較小，相對(duì)穩(wěn)定；圖中開(kāi)始部分，魯棒雙層規(guī)劃模型的優(yōu)勢(shì)不明顯，對(duì)不確定距離比較敏感，隨著不確定距離數(shù)量的增加，降低了模型對(duì)不確定距離的敏感程度，其行走距離比較穩(wěn)定，意味著此時(shí)的分配結(jié)果比較保守，但增加了解的魯棒性。

4 結(jié)論

在“貨到人”揀選系統(tǒng)中，提高作業(yè)效率的關(guān)鍵取決于如何調(diào)度機(jī)器人并進(jìn)行任務(wù)分配，進(jìn)而影響著整個(gè)系統(tǒng)的運(yùn)行效率與成本，本文考慮了機(jī)器人在完成任務(wù)過(guò)程中由于調(diào)度、避障、路徑規(guī)劃等導(dǎo)致的行走距離不確定因素，建立了基于行走距離不確定性的魯棒雙層規(guī)劃模型，以機(jī)器人完成任務(wù)成本最小作為上層模型目標(biāo)函數(shù)，以機(jī)器人平均空閑率最小為下層目標(biāo)函數(shù)，通過(guò)雙層遺傳算法對(duì)模型進(jìn)行求解，解決了機(jī)器人的調(diào)度問(wèn)題，并同時(shí)實(shí)現(xiàn)了機(jī)器人的任務(wù)分配。通過(guò)算例研究，驗(yàn)證了魯棒雙層規(guī)劃模型的有效性，得到魯棒雙層規(guī)劃模型的機(jī)器人調(diào)度結(jié)果與任務(wù)分配結(jié)果使得機(jī)器人完成所有任務(wù)的總成本對(duì)不確定距離因素不敏感，也就意味著這種情況下的分配結(jié)果最為保守，在一定程度上提高了系統(tǒng)的運(yùn)行效率，降低了系統(tǒng)的運(yùn)作成本。