“貨到人”揀選系統機器人任務分配的魯棒雙層規劃模型

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

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

0 引言

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

近年來，很多學者對不同應用領域的機器人調度與任務分配問題進行了研究。Nielsen等[3]對配送能力約束下的機器人調度問題進行了研究，利用改進的遺傳算法解決了機器人每次的配送量。周炳海等[4]考慮機器人之間的協同調度，以最小化機器人數量和降低能耗成本為目標，利用聚類啟發式方法與自適應大鄰域搜索算法驗證了協同調度的優勢。沈博聞等[5]將物流任務進行分解，考慮了路徑成本與等待時間成本，對機器人調度進行研究并驗證了智能調度的有效性。

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

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

1 問題描述及符號定義

“貨到人”揀選系統機器人的任務分配問題可以描述為：系統接受訂單后，將訂單按照一定規則分批處理，系統需要確認每個訂單中貨物所在貨架的位置，然后調度系統中一定數量的機器人，并將任務進行分配。在機器人完成任務的過程中，機器人首先從初始位置移動到貨架所在位置并將其搬運至揀選臺，揀選人員根據貨物的信息在該貨架上揀選貨物，將其放在指定的區域。當系統中所有揀選臺都被其他機器人占用時，機器人就會進行排隊等待，直到被揀選完畢。揀選完成后，機器人將貨架搬運到該貨架的原來位置，在此位置等待下一次任務的分配。要求每個機器人同時只可以搬運一個貨架，每個貨架同時只能由一個機器人進行搬運。圖1為機器人完成單個任務的流程，可以分解為3個步驟。

圖1 機器人完成單個任務的流程圖

為了便于構建模型，本文做出以下假設：

(1)初始時刻，系統中所有的機器人處于空閑狀態。

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

(3)系統中所有機器人的初始位置是隨機的。

(4)系統中所有的任務分布在不同的貨架中，并且不存在缺貨現象。

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

(6)忽略機器人在揀選臺的等待時間。

符號定義如下：

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

(2)(xAi,yAi)表示機器人Ri的位置坐標，(xBj,yBj)表示任務Zj的位置坐標，(xPk,yPk)表示揀選臺Pk的位置坐標；

(3)d1ioj表示機器人Ri從初始位置到任務Zj所行走的距離的標稱值，d2ijk表示機器人Ri從任務Zj到揀選臺Pk時所行走的距離的標稱值，d3ikj表示機器人Ri從揀選臺Pk回到任務Zj時所行走的距離的標稱值，本文所有距離計算均采用曼哈頓距離，即

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

(1)

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

(2)

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

(3)

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

Dij=d1ioj+d2ijk+d3ikj

(4)

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

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

(7)T0為所有機器人完成任務的時間；

(8)Tij為機器人Ri完成任務Zj所花費的時間，即

(5)

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

(6)

(7)

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

(12)決策變量Yi表示是否調度機器人Ri來完成任務，則

(8)

(13)Cr為機器人行走單位距離所花費的成本，Cf為單位時間每臺機器人的空閑成本，Cp為每臺機器人的固定成本即購買成本，C為n個機器人完成m個任務所花費的總成本；

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

(9)

2 模型構建與求解

2.1 不考慮距離變化的任務分配雙層規劃模型

雙層規劃模型具有主從遞階結構，最早由Bracken和McGill[12]提出。其上層問題的決策變量制約下層問題的最優結果，下層問題的決策變量影響上層問題的最優結果[13]。雙層規劃具有層次性、沖突性、獨立性、優先性、自主性、制約性等特點，其研究的系統是分層的，上層決策者首先進行決策，下層決策者需要對其決策結果做出反應并且具有一定的自主決策權，上層決策者需要根據下層的反應再次進行決策[14]。雙層優化能很好地描述分層系統優化問題，該方法多用于解決設施選址、生產計劃以及應急物資運輸等問題。如Yegane等[15]針對配送中心選址問題建立雙層規劃模型，提出了自適應雙層蟻群算法進行求解，實現了利潤最大化。Calvete等[16]對生產分配問題進行研究，考慮了不同決策者分別控制生產與分配問題，以成本最小為目標建立雙層規劃模型，利用蟻群算法進行求解，解決了生產分配問題。Camacho-Vallejo等[17]針對應急物資運輸問題建立雙層規劃模型，對運輸成本進行優化，解決了災難后國際救援分配的決策問題。

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

上層模型：

(10)

下層模型：

(13)

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

(14)

(15)

(16)

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

2.2 考慮距離變化的任務分配魯棒雙層規劃模型

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

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

Bertsimas將不確定性組合優化問題進行如下轉換:

mincTx

(17)

s.t.x∈X

(18)

上述模型不能直接求解，需要進行魯棒對等轉換，因此引入魯棒控制參數Γ0表示不確定參數的個數，Γ0通常取整數，因此，組合優化問題的魯棒模型為:

(20)

假定d1≥d2≥…≥dn，令dn+1=0，Bertsimas將式(19) 轉化為對n+1個標稱問題進行求解，其目標函數為:

(22)

在機器人完成任務的過程中，如果多個任務同時聚集在一定的區域內，會使得多個機器人之間的行走路徑發生沖突，為了減少機器人之間發生碰撞或減少機器人的等待時間，調度系統會調度機器人行走其他路徑完成任務，無論機器人選擇等待還是改變路徑，都會影響任務的完成時間，進而影響機器人完成任務的效率，因此考慮了機器人在完成任務過程中由于調度、避障、路徑規劃等導致的行走距離不確定因素，將機器人等待的時間與路徑的改變轉換為行走距離的增加，由此可見，機器人完成任務的實際行走距離不一定是機器人完成任務的曼哈頓距離，所以采用區間值的形式表示機器人完成任務的實際行走距離。

引入參數J，J表示受不確定距離影響的路段集合,|J|表示受不確定距離影響的路段的個數，|J|∈「0,|W|?。

引入參數Γ，Γ∈「0,|J|?，用來控制不確定距離的保守度，這里令Γ取整數，當Γ=0時，不考慮距離偏差的影響，此時任務分配模型與2.1節中模型一致，對不確定距離最敏感；隨著Γ值的增大，增加了魯棒性，模型對不確定距離的敏感程度會下降；當Γ=|W|時，所有路段的距離均為不確定距離，這時模型對不確定距離最不敏感，其任務分配結果最保守。

機器人任務分配魯棒雙層規劃模型：

上層模型：

(23)

(25)

下層模型:

(26)

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

(27)

(28)

(29)

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

下層模型：

(30)

由此可得機器人任務分配魯棒雙層規劃模型：

上層模型:

(33)

下層模型：

(34)

(35)

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

(36)

(37)

(38)

2.3 模型求解

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

模型的求解具體計算步驟如下：

Step1確定機器人調度的最小數量。

Step2確定所調度的機器人的序號，采用機器人序號對調度問題進行編碼產生初始種群，計算這些機器人到所有任務的平均距離。

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

Step4將Step 2得到的計算結果與Step 3得到的機器人平均空閑率帶入上層模型，求出機器人完成所有任務所花費的總成本。直到最小成本不再發生變化，找到調度該數量機器人下的最小總成本，并得到了任務的調度結果與任務分配結果。

Step5將機器人的調度數量增加一個，返回Step 1。

Step6機器人的調度數量等于系統中機器人的最大數量，停止計算，輸出歷史最優成本作為最終結果。

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

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

3 實例仿真與分析

3.1 實例描述

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

表1 機器人坐標

圖3 仿真倉庫布局

3.2 雙層規劃模型的機器人任務分配仿真結果與分析

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

通過圖4可以得出調度不同數量的機器人，其最小成本不同，當調度6個機器人時，機器人完成所有任務所花費的總成本最小，此時，得到的不同調度結果對應的成本如圖5所示，圖4中調度7個或8個機器人時所花費的成本高于調用6個機器人的成本，是由于隨著機器人調度的數量增加，機器人的平均空閑率增大，所花費的成本增加。

圖4 調度不同數量機器人完成任務所花費的最小成本

圖5 不同調度方案下機器人完成任務所花費的成本

圖5表示調度6個機器人時，不同調度方案下機器人完成任務所花費的成本，其中橫坐標表示調度方案共28種，縱坐標表示成本。仿真結果顯示調用第1、2、3、4、5、7個機器完成任務時，所花費的成本最小，此時機器人行走的總距離如圖6所示。

圖6 成本最優下機器人行走總距離

因此，雙層規劃模型的機器人任務分配問題得到的機器人配置、調度以及任務分配結果如表3所示。

表2 任務坐標

表3 雙層規劃模型的機器人配置、調度以及任務分配結果

表中任務分配結果的第一個數字代表調度的機器人序號，后面數字則代表該機器人所完成的任務序號。

3.3 魯棒雙層規劃模型的機器人任務分配仿真結果與分析

將不確定距離分為三段，在本仿真實例中，機器人完成任務可能行走的距離共1200段，Γ表示不確定距離的個數，當Γ=0時，所有距離不變，與原來模型計算結果一致，這里分別取Γ=0,40,80,120,160,200,300，表4為機器人配置、調度及任務分配結果，圖7為對應的成本。

圖7 魯棒雙層規劃模型的機器人完成任務的最小成本

表4 魯棒雙層規劃模型的機器人的配置、調度以及任務分配結果

從表中看出，發生變化的距離個數不同，機器人完成所有任務所花費的成本不同、其數量配置、調度方案、以及任務的分配結果也會發生變化。

在本仿真實例中，完成30個任務需要行走90段距離，為了驗證魯棒雙層規劃模型的有效性，使機器人的行走距離在指定范圍內隨機發生變化，取，表示從1段距離發生變化直到30段距離發生變化，兩個模型的仿真結果如圖8所示。

圖8 兩個模型下機器人完成所有任務行走總距離

圖8中橫坐標為不確定距離段的個數，縱坐標為機器人完成所有任務行走的總距離，虛線為雙層規劃模型的機器人完成所有任務行走的總距離，實線為魯棒雙層規劃模型的機器人完成所有任務行走的總距離。隨著不確定距離數量的增加，使用雙層規劃模型得到的機器人完成所有任務行走的總距離明顯多于使用魯棒雙層規劃模型得到的機器人完成所有任務行走的總距離并且呈上升趨勢，而魯棒雙層規劃模型的曲線波動范圍較小，相對穩定；圖中開始部分，魯棒雙層規劃模型的優勢不明顯，對不確定距離比較敏感，隨著不確定距離數量的增加，降低了模型對不確定距離的敏感程度，其行走距離比較穩定，意味著此時的分配結果比較保守，但增加了解的魯棒性。

4 結論

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