整數規劃

建立數學模型,從全局角度出發,一次性為多個任務分配多輛車。以下為一種經典的任務-運力匹配模型:

其中 表示機器人被指派去取貨架,表示機器人距離貨架的距離，我們可以將問題中約束松弛為，求解松弛后的問題可以直接得到整數最優解．通過求解上述多對多指派問題獲得多個機器人和任務之間的匹配關系，從全局角度進行整體優化，降低系統總搬運成本。該模型簡化了搬運成本，以及特定AGV執行特定任務的成本，且不考慮業務上的復雜約束。

考慮業務約束下匹配

在多對多模式下，如果考慮跨運力組、運力配比或自定義約束等等，則需將相應信息加入模型中，例如考慮運力配比的情形，令表示第個AGV執行第種任務，可添加約束及來限制第種任務的配比。

以上兩種模式并無絕對好壞之分,一般來說一堆多模式原理簡單,開發維護容易,計算開銷較小,但不保證全局最優;多對多模式相對復雜,且計算開銷較大,但解的最優性更好。

搬運任務分發

搬運成本

一般來說,搬運任務的起訖點在下發任務時就已確定,因此某個指定運力執行某個指定搬運任務的成本可以明確地定義。常見的定義方式包括搬運距離、搬運時間。

考慮到倉內AGV的行駛方向一般為二維平面的水平、垂直兩個正交方向,常見的距離定義方式包括歐式距離或曼哈頓距離,該定義方式較為簡單。

另一種更精確的方法為調用路徑規劃算法(等)，計算AGV→任務起點→任務終點的最短路徑的完整距離。

該方法尤其適用于路網中存在單向路的情形。考慮到實時計算成本較高,可將地圖中所有完整路徑的距離存儲下來,直接查詢即可。在考慮路線擁堵的情況下,可根據地圖熱點信息為每條邊定義不同成本。搬運距離和搬運時間可以相互轉化,例如對于完整路徑內的每一段直線路徑,可根據AGV的加速度信息,求出基于速度規劃的行駛時間,并為每個轉彎行為加入轉彎時間。

搬運任務分發

任務執行

對于以掛載任務隊列或多中轉點任務的情形,為使機器人可以執行任務,還需要確定任務涉及的順序問題,具體來說包括:

如果存在多個中轉點或者目的點,需要確定他們之間到達服務順序；

如果采用任務隊列模式,需要確定多任務之間的執行順序.確定執行順序在不同場景下方式不盡相同,主要考慮因素包括距離和工作站當時負載情況等。

下面我們通過對一些具體問題場景的討論來進行闡述。

每個機器需要指派一個或多個搬運任務,并且需要確定每個機器人分別需要搬運的貨架以及搬運順序,使得所有機器人總搬運距離最短或者使得所有任務的完成時間最短。

在這一場景下任務的指派和順序的確定是通過求解一個變種車輛路徑問題(VRP) 同時確定的。而對于上一節介紹的揀選支持機器人系統,確定機器人對揀選點(也就是多個中轉點) 的前往順序可以抽象為一個在倉儲路網結構下的經典旅行商問題(Traveling Salesman Problem,TSP) 或其變種問題,通過最小化行駛路徑長度確定各個揀選點的到達順序。

在搬運機器人場景下,可能多個工作站都需求同一個貨架上的物品,也就是一條搬運任務有多個目的地的情況。雖然可以通過TSP類方法確定各個工作站的到達順序從而最小化整體搬運距離,但同時還需要根據工作站當時的任務負載情況進行調整,可以優先前往相對需求急迫或者當前較空閑的工作站,減少工作站的等待,雖然會增加一部分搬運成本但是可以提高整體系統作業效率。

搬運任務分發

評價及靈敏度分析

任務分配和執行的策略會依據不同場景不同需求而有所不同,而在同一場景下面對同樣的業務需求,通常也會有多種不同的調度策略可供選擇,即便同一種策略也會因為不同的內置參數選擇而產生不同表現,現實中通常很難完全確定某一單一環節如何影響整體系統生產效率。

盡管如此,通過對一些特定統計量的分析,我們也可以大致了解策略對系統性能的影響。對于本節所介紹的搬運任務分配和執行,在訂單揀選場景例如揀選和揀選支持機器人系統,可用若干用于評價調度策略性能的統計量,其中包括:

1. 訂單生產效率:一定時間內生產完成訂單數量與接受訂單數量的比例

2. 響應時間:任務等待機器人執行的時間與機器人空駛時間之和

3. 生產時間:訂單在系統中生產的時間

4. 機器人平均利用率:機器人執行任務的時間(包括空駛和滿載時間與總時間的比值)

現實生產系統中還會計算和監控更多統計量用于后續性能分析,其中包括工作站揀選等待時間、機器人平均搬運距離以及搬運任務平均耗時等。對于分揀場景,則會統計包裹投遞效率等。

除去上面提及的系統性能表現以外,另一方面我們還需要關注算法策略本身屬性。具體來說,隨著機器人技術的不斷普及和業務場景的不斷擴大,系統中機器人數量和待處理的任務量會進一步提升,這會使得調度問題規模變得很大,而同時業務對于系統的響應可能要求很高,在這種場景下,需要算法策略有很好的計算性能。

機器人系統不可避免會出現異常故障,算法策略也需要有足夠的魯棒性可以進行快速調整。另外,對不同時間段內可能的不同調度目標,調度策略也需要有足夠的柔性可以滿足不同要求。總體而言,需要通過對運營效率、計算性能、魯棒性和柔性等方面綜合對所考慮的任務調度策略進行評價。