赫雪婷，鎮(zhèn) 璐

（上海大學(xué) 管理學(xué)院，上海 200444）

1 引言

為滿足小批量、多品種、短配送周期和不斷變化的工作量的需求，大量電商企業(yè)采用自動(dòng)化倉(cāng)庫(kù)系統(tǒng)提升作業(yè)效率［1］。自動(dòng)化倉(cāng)庫(kù)系統(tǒng)的應(yīng)用提高了訂單分揀效率，使電商倉(cāng)庫(kù)能夠更好地提供高效、準(zhǔn)時(shí)、個(gè)性化的物流服務(wù)，從而提升客戶體驗(yàn)。

傳統(tǒng)自動(dòng)化分揀系統(tǒng)通?；趥魉蛶Х謷C(jī)實(shí)現(xiàn)包裹的分揀。對(duì)于此類(lèi)系統(tǒng)的布局設(shè)計(jì)和系統(tǒng)操作，Boysen等［2］已經(jīng)進(jìn)行了深入研究。此類(lèi)系統(tǒng)中傳送帶分揀格口分配問(wèn)題也吸引了許多學(xué)者的關(guān)注。Zenker和Boysen［3］將分揀格口的目的地分配問(wèn)題擴(kuò)展為多個(gè)目的地可共享一個(gè)出庫(kù)口的問(wèn)題，提出了一種混合整數(shù)線性規(guī)劃模型，并設(shè)計(jì)一種貪心局部搜索和禁忌搜索相結(jié)合的算法求解該問(wèn)題。Hou等［4］對(duì)自動(dòng)分揀系統(tǒng)中訂單指派問(wèn)題進(jìn)行研究，以均衡分揀任務(wù)為目標(biāo)建立數(shù)學(xué)模型，通過(guò)實(shí)例驗(yàn)證了模型的有效性。張貽弓和吳耀華［5］研究了并行自動(dòng)分揀系統(tǒng)，確定品項(xiàng)分配優(yōu)化目標(biāo)從而建立一個(gè)聚類(lèi)模型，并設(shè)計(jì)了一種啟發(fā)式聚類(lèi)算法求解該問(wèn)題。Briskorn等［6］對(duì)閉環(huán)傾斜托盤(pán)分揀輸送機(jī)展開(kāi)研究，以最小化時(shí)間跨度為目標(biāo)，提出一個(gè)短期確定性調(diào)度問(wèn)題，并評(píng)估了不同分揀機(jī)布局的性能水平。

隨著KIVA自動(dòng)搬運(yùn)機(jī)器人的應(yīng)用，基于自動(dòng)引導(dǎo)車(chē)（automated guided vehicle，AGV）的自動(dòng)化分揀系統(tǒng)也廣泛用于自動(dòng)訂單揀選［1，7］。國(guó)內(nèi)外學(xué)者對(duì)依托AGV的分揀系統(tǒng)開(kāi)展了豐富的研究。秦虎［8］為自動(dòng)化倉(cāng)庫(kù)系統(tǒng)中AGV的優(yōu)化調(diào)度以及仿真提供了有效建議。Saidi-Mehrabad等［9］提出了一種基于AGV系統(tǒng)的無(wú)沖突路由和作業(yè)車(chē)間調(diào)度的集成模型。Lee和Murray［10］以最小化運(yùn)送物品到包裝站的時(shí)間為目標(biāo)，定義了一個(gè)新的路徑規(guī)劃問(wèn)題，并研究了不同設(shè)備的組合以及倉(cāng)庫(kù)的布局設(shè)計(jì)對(duì)系統(tǒng)性能的影響。陳方宇等［11］為解決倉(cāng)庫(kù)揀選作業(yè)中因多揀貨員同時(shí)工作造成的堵塞問(wèn)題，設(shè)計(jì)了一種基于蟻群算法的揀選路線算法，以提高訂單揀選效率。藺一帥等［12］提出了貨位和AGV路徑協(xié)同優(yōu)化數(shù)學(xué)模型，將貨架優(yōu)化和路徑規(guī)劃歸為一個(gè)整體，并使用改進(jìn)遺傳算法對(duì)模型求解。余娜娜等［13］為實(shí)現(xiàn)AGV的無(wú)沖突路徑規(guī)劃，以最小化最大搬運(yùn)完成時(shí)間為目標(biāo)建立數(shù)學(xué)模型，并提出一種改進(jìn)差分進(jìn)化算法求解該問(wèn)題。李浩霖等［14］考慮“一車(chē)雙箱”存取模式，構(gòu)建了穿梭車(chē)立體倉(cāng)庫(kù)中的訂單分批決策與存取選擇決策的集成優(yōu)化數(shù)學(xué)模型，并應(yīng)用變鄰域算法解決該問(wèn)題。

為了在有限的空間內(nèi)高效地完成包裹的分揀任務(wù)，部分倉(cāng)庫(kù)設(shè)計(jì)了基于智能移載搬運(yùn)機(jī)器人的自動(dòng)化倉(cāng)庫(kù)系統(tǒng)（以下簡(jiǎn)稱(chēng)智能移載搬運(yùn)系統(tǒng)）。如圖1所示，智能移載搬運(yùn)系統(tǒng)主要由傳送帶分揀機(jī)、分揀格口、籠車(chē)以及與AGV具有相似功能特征的智能移載搬運(yùn)機(jī)器人（以下簡(jiǎn)稱(chēng)機(jī)器人）組成［15］。因此，此類(lèi)系統(tǒng)的運(yùn)作流程中將涉及兩類(lèi)設(shè)備（傳送帶分揀機(jī)和機(jī)器人）的決策問(wèn)題。通過(guò)對(duì)現(xiàn)有文獻(xiàn)進(jìn)行歸納分析，現(xiàn)有研究主要集中在單一分揀設(shè)備（傳送帶分揀機(jī)或AGV）的調(diào)度上，以均衡傳送帶分揀機(jī)的訂單量或最小化AGV的行駛路程為目標(biāo)進(jìn)行優(yōu)化決策；較少有將傳送帶分揀機(jī)中分揀格口的分配以及AGV的運(yùn)輸路線綜合考慮并進(jìn)行調(diào)度優(yōu)化的。因此，本文以智能移載搬運(yùn)系統(tǒng)為研究對(duì)象，考慮該系統(tǒng)運(yùn)作過(guò)程中傳送帶分揀機(jī)與機(jī)器人的聯(lián)系，以最小化完成包裹分揀的時(shí)間為目標(biāo)，構(gòu)建了一個(gè)混合整數(shù)規(guī)劃模型，同時(shí)對(duì)兩種設(shè)備的運(yùn)作進(jìn)行決策優(yōu)化。此外，不同于現(xiàn)有文獻(xiàn)中常用的啟發(fā)式求解算法，本文設(shè)計(jì)了一種精確式求解算法——基于路線模板法的分支定界算法高效求解本研究問(wèn)題，并通過(guò)大量數(shù)值實(shí)驗(yàn)驗(yàn)證該算法的有效性與高效性。最后，通過(guò)敏感性分析實(shí)驗(yàn)，為智能移載搬運(yùn)系統(tǒng)的運(yùn)作提供一些決策建議。

圖1 智能移載搬運(yùn)機(jī)器人及作業(yè)場(chǎng)景

2 問(wèn)題描述

本文的研究對(duì)象為基于智能移載搬運(yùn)機(jī)器人的自動(dòng)化倉(cāng)庫(kù)系統(tǒng)（如圖2所示），該系統(tǒng)主要由傳送帶分揀機(jī)、分揀格口、智能移載搬運(yùn)機(jī)器人以及籠車(chē)組成［15］。

圖2 基于智能移載搬運(yùn)機(jī)器人的自動(dòng)化倉(cāng)庫(kù)系統(tǒng)

在智能移載搬運(yùn)系統(tǒng)中，包裹根據(jù)其特征（如包裹的目的地信息等）經(jīng)傳送帶分揀機(jī)運(yùn)輸至不同的分揀格口；隨后，到達(dá)分揀格口的包裹將被搬運(yùn)至智能移載搬運(yùn)機(jī)器人上，智能移載搬運(yùn)機(jī)器人在籠車(chē)與分揀格口之間的巷道中穿行，將搬運(yùn)的包裹投遞到不同的籠車(chē)中，完成包裹的分揀任務(wù)。在該過(guò)程中，不同設(shè)備之間彼此聯(lián)系，以準(zhǔn)確高效地完成每一件包裹的分揀任務(wù)。在上述分揀過(guò)程中，存在兩個(gè)決策問(wèn)題：（1）根據(jù)包裹的目的地信息，決策包裹與分揀格口的對(duì)應(yīng)關(guān)系。（2）根據(jù)包裹對(duì)應(yīng)的分揀格口信息以及對(duì)應(yīng)的籠車(chē)信息，為機(jī)器人分配包裹并規(guī)劃行駛路線。此外，為順利完成分揀任務(wù)，本文提出如下假設(shè)：（1）預(yù)先知道包裹的目的地、對(duì)應(yīng)的籠車(chē)等信息。該假設(shè)可通過(guò)掃描包裹上電子面單實(shí)現(xiàn)。（2）每個(gè)分揀格口僅處理同一目的地的包裹。該假設(shè)可將同一批次包裹根據(jù)目的地信息分配給不同的分揀格口，對(duì)包裹進(jìn)行簡(jiǎn)單分類(lèi)。（3）有足夠的分揀格口能夠滿足所有目的地的需求。

3 模型構(gòu)建

為了解決上述問(wèn)題，本節(jié)提出一個(gè)混合整數(shù)規(guī)劃模型。模型中使用的集合、參數(shù)以及決策變量定義如下。

集合與下標(biāo)。S為包裹編號(hào)的集合，下標(biāo)為s；為包裹編號(hào)集合S的子集為分揀格口標(biāo)號(hào)的集合，下標(biāo)為n；R為機(jī)器人編號(hào)的集合，下標(biāo)為r；D為不同目的地的包裹編號(hào)的集合，下標(biāo)為d；e，＾e為機(jī)器人分揀路線的虛擬起始結(jié)點(diǎn)與虛擬終止結(jié)點(diǎn)。

參數(shù)。as，s′表示若包裹s與包裹s′的類(lèi)型相同，并且包裹s′緊接包裹s進(jìn)入傳送帶則為1，否則為0；bs為包裹s的目的地編號(hào)；gs為包裹s送入傳送帶的時(shí)間為從分揀格口n行駛至包裹s對(duì)應(yīng)的籠車(chē)所需的時(shí)間；為包裹通過(guò)傳送帶送至分揀格口n所需的時(shí)間；t為分揀格口處搬運(yùn)一件包裹所需的時(shí)間；M為一個(gè)極大的數(shù)。

決策變量。αn，d為0-1決策變量，若目的地d的包裹送往分揀格口n則為1，否則為0；βs，s′，r為0-1決策變量，若機(jī)器人r在運(yùn)輸包裹s后再運(yùn)送包裹s′則為1，否則為0；γs，r為機(jī)器人r到達(dá)負(fù)責(zé)分揀包裹s的分揀格口的時(shí)間；δs，r為機(jī)器人r開(kāi)始運(yùn)輸包裹s的時(shí)間；εs，r為0-1決策變量，若機(jī)器人r運(yùn)輸包裹s則為1，否則為0；ωr為機(jī)器人r完成本批次所有分揀任務(wù)的時(shí)間。

數(shù)學(xué)模型（F1）

目標(biāo)函數(shù)（1）表示最小化處理完最后一件包裹的時(shí)間。約束（2）確保相同目的地的包裹只能送往同一個(gè)分揀格口。約束（3）確保一個(gè)分揀格口僅處理來(lái)自一個(gè)目的地的包裹。約束（4）確保任意一件包裹只被一輛機(jī)器人運(yùn)輸。約束（5）至（9）為機(jī)器人的運(yùn)輸路線約束。約束（10）和約束（11）表示若機(jī)器人r先后連續(xù)運(yùn)輸包裹s，s′，則機(jī)器人到達(dá)包裹s′對(duì)應(yīng)分揀格口的時(shí)間應(yīng)晚于機(jī)器人r完成包裹s運(yùn)輸后返回包裹s′對(duì)應(yīng)的分揀格口的時(shí)間。約束（12）表示若包裹s，s′先后接連到達(dá)同一分揀格口，則機(jī)器人r′開(kāi)始運(yùn)輸包裹s′的時(shí)間晚于機(jī)器人r開(kāi)始運(yùn)輸包裹s的時(shí)間加上搬運(yùn)每件包裹所需的時(shí)間。約束（13）和（14）表示包裹s到達(dá)分揀格口后，立刻被機(jī)器人運(yùn)輸。約束（15）和（16）表示決策變量γs，r，δs，r，εs，r之間的關(guān)系。約束（17）確保ωr為機(jī)器人r運(yùn)送最后一件包裹的時(shí)間。約束（18）和（19）定義了決策變量的范圍。

4 算法設(shè)計(jì)

本文所研究的智能移載搬運(yùn)系統(tǒng)的資源調(diào)度問(wèn)題，是一個(gè)由目的地指派問(wèn)題與機(jī)器人路徑規(guī)劃問(wèn)題構(gòu)成的集成問(wèn)題。在本文的數(shù)學(xué)模型中，約束（2）和（3）為目的地指派問(wèn)題的相關(guān)約束，約束（4）至（16）為機(jī)器人路徑規(guī)劃問(wèn)題的相關(guān)約束。

為了求解該問(wèn)題，本節(jié)設(shè)計(jì)了一種基于路線模板法的分支定界算法，其中分支定界算法用于求解目的地指派問(wèn)題，路線模板法通過(guò)求解機(jī)器人的所有可行運(yùn)輸路線作為路線模板，然后從路線模板中選擇最優(yōu)運(yùn)輸路線，從而求解機(jī)器人路徑規(guī)劃問(wèn)題。在使用分支定界算法得到可行的目的地指派策略后，應(yīng)用4.2節(jié)中生成路線模板的方法生成機(jī)器人的運(yùn)輸路線，并計(jì)算目標(biāo)值，對(duì)指派策略的效果進(jìn)行評(píng)價(jià)和更新。

4.1 分支定界

4.1.1 搜索樹(shù)和分支策略

結(jié)合指派問(wèn)題的特性，采取添加目的地的思想構(gòu)造關(guān)于指派策略的搜索樹(shù)。首先，根節(jié)點(diǎn)代表所有目的地的包裹均不被分揀的情況，每一層代表不同的目的地（其中i表示層數(shù)，di表示i層對(duì)應(yīng)目的地）；隨后，從根節(jié)點(diǎn)開(kāi)始逐層進(jìn)行分支，當(dāng)搜索到第i層的某個(gè)結(jié)點(diǎn)時(shí)，考慮下一目的地的｜D｜-i種指派策略，以此分支得到｜D｜-i個(gè)新的子節(jié)點(diǎn)。重復(fù)上述步驟，直至所有目的地均被分配為止，即層數(shù)i＝｜D｜時(shí)結(jié)束分支。

假設(shè)｜N｜＝｜D｜＝3，完整的搜索樹(shù)結(jié)構(gòu)如圖3所示。其中搜索樹(shù)第i層的每一個(gè)節(jié)點(diǎn)均代表該層目的地di的指派策略，例如第1層的三個(gè)節(jié)點(diǎn)，分別表示目的地d1對(duì)應(yīng)的分揀格口為n1、n2和n3。搜索樹(shù)的構(gòu)建方法如下：首先，設(shè)置根節(jié)點(diǎn)為空，即無(wú)目的地被指派，隨后，在搜索樹(shù)的第1層中，對(duì)d1分別考慮n1，n2，n3三種情況，并將根節(jié)點(diǎn)分為三個(gè)子節(jié)點(diǎn)d1-n1，d1-n2，d1-n3。同理，在第2層中，繼續(xù)針對(duì)該層目的地考慮不同的分揀格口指派策略，并得到第2層的各節(jié)點(diǎn)d2-n2，d2-n3；d2-n1，d2-n3；d2-n1，d2-n2；以此類(lèi)推，直至得到所有指派策略。

4.1.2 上界與下界

每個(gè)節(jié)點(diǎn)都存在一個(gè)下界LB，其值表示當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)的指派策略下的目標(biāo)值，即最小完成分揀時(shí)間。以圖3中搜索樹(shù)第1層結(jié)點(diǎn)d1-n1為例，該節(jié)點(diǎn)的下界表示僅將目的地d1指派給分揀格口n1時(shí)的目標(biāo)值。結(jié)點(diǎn)d1-n1的子節(jié)點(diǎn)d2-n2的下界表示將目的地d1，d2分別指派給分揀格口n1，n2時(shí)的目標(biāo)值。

定義UB為全局上界，表示已搜索過(guò)的可行指派策略中的最小完成分揀時(shí)間。通常，初始上界設(shè)為無(wú)窮大，為了加快求解速率，本文將對(duì)應(yīng)包裹數(shù)較多的目的地優(yōu)先分配給靠近傳送帶入口處的分揀格口作為初始指派策略，以生成初始UB。

4.1.3 算法框架

步驟1定義αn，d，Z（αn，d）分別表示當(dāng)前節(jié)點(diǎn)的指派策略及其目標(biāo)值分別表示最優(yōu)可行指派策略及其目標(biāo)值。根據(jù)4.1.2中的初始指派策略可以得到初始可行解初始化根節(jié)點(diǎn)為空節(jié)點(diǎn)，且其LB為0。定義節(jié)點(diǎn)集合為Ω←?。

步驟2 從根節(jié)點(diǎn)開(kāi)始分支，得到子節(jié)點(diǎn)，并將所有子節(jié)點(diǎn)加入節(jié)點(diǎn)集合Ω。從節(jié)點(diǎn)集合Ω中選擇一個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn)，并將該節(jié)點(diǎn)從Ω中移除。根據(jù)當(dāng)前根節(jié)點(diǎn)的分配指派策略αn，d，求解機(jī)器人的最優(yōu)運(yùn)輸路線，得到目標(biāo)值Z（αn，d）。

步驟3（1）若Z（αn，d）＜UB且約束（2）未滿足時(shí)，跳轉(zhuǎn)至步驟2；（2）若Z（αn，d）＜UB且約束（2）被滿足時(shí)，更新跳轉(zhuǎn)至步驟4；（3）若Z（αn，d）≥UB，剪去該節(jié)點(diǎn)，跳轉(zhuǎn)至步驟4。

步驟4若當(dāng)前節(jié)點(diǎn)集合Ω為空，則算法結(jié)束；否則，從當(dāng)前節(jié)點(diǎn)集合Ω中選擇一個(gè)節(jié)點(diǎn)設(shè)置為當(dāng)前父節(jié)點(diǎn)，并從Ω中刪除該節(jié)點(diǎn)。跳轉(zhuǎn)到步驟2。

4.2 路線模板法

本節(jié)在給定目的地指派策略的基礎(chǔ)上，進(jìn)一步求解機(jī)器人路徑規(guī)劃問(wèn)題，即已知αn，d的值，求解模型中εs，r與βs，s′，r值。在某個(gè)確定的目的地指派策略下，可根據(jù)最后一件包裹到達(dá)分揀格口的時(shí)間求得目標(biāo)函數(shù)值。為了求解機(jī)器人運(yùn)輸包裹的路線，本節(jié)提出兩種路線模板生成方法及其對(duì)應(yīng)的兩個(gè)數(shù)學(xué)模型。

4.2.1 生成完整路線模板求解

在本節(jié)中，首先通過(guò)生成機(jī)器人運(yùn)輸包裹的所有完整可行路線作為路線模板；隨后建立模型，令機(jī)器人在路線模板中選擇可行路線，從而獲得機(jī)器人的最優(yōu)行駛路線。

1）完整路線模板的生成

為了求解所有可行的運(yùn)輸路線，定義以下新的參數(shù)與集合：us為包裹s到達(dá)對(duì)應(yīng)分揀格口的時(shí)間，F(xiàn)s為包裹s的可行后接包裹集合，即s1∈S｝。Ps為包裹s的可行前接包裹集合，即

生成可行路線L的步驟如下：

步驟1選擇S中us值最大的包裹s作為路線的當(dāng)前節(jié)點(diǎn)，并添加到路線中。

步驟2 選擇Ps中us值最大的包裹s′，更新路線終點(diǎn)s←s′，并添加到路線中。

步驟3重復(fù)步驟2直至Ps＝?，得到一條完整可行路線。

使用上述方法可求得所有可行的運(yùn)輸路線，但會(huì)造成生成的路線數(shù)量過(guò)多，求解效率低下的問(wèn)題。因此，在生成路線時(shí)，僅生成最長(zhǎng)完整路線。最長(zhǎng)完整路線是指滿足如下條件的路線：①路線的起始包裹的Ps＝?；②路線的終止包裹的Fs＝?；例如路線k：s1→s2→s3→s4→s5，且Ps1＝?，F(xiàn)s5＝?，而訪問(wèn)路線k中部分包裹的路線，如路線s1→s2→s3，s2→s3→s4將不再生成。

生成最長(zhǎng)完整路線的算法框架如算法1所示。

算法1 完整路線模板生成

2）基于完整路線模板的模型（F2）

由于路線模板中的路線均為最長(zhǎng)完整路線，若從完整路線模板中選擇路線，則易出現(xiàn)同一包裹在多條路線中同時(shí)出現(xiàn)的情形。為解決此問(wèn)題，本節(jié)首先將原模型的約束（4）松弛為約束∑r∈Rεs，r≥1，s∈S，根據(jù)得到的路線模板，構(gòu)建路線決策模型，從路線模板中選擇路線作為機(jī)器人的行駛路線。為構(gòu)建基于路線的模型（F2），定義相關(guān)集合、參數(shù)、決策變量如下。

集合。K為路線編號(hào)的集合，下標(biāo)為k。

參數(shù)。ck為路線k的費(fèi)用，即該路線中處理完最后一件包裹的時(shí)間。xs，k，若路線k中訪問(wèn)包裹s，則為1，否則為0。

決策變量。θk為0-1決策變量，若路線k被選擇為1，否則為0。

數(shù)學(xué)模型（F2）

目標(biāo)函數(shù)（20）表示最小化處理完該批次中最后一件包裹的時(shí)間。約束（21）確保任意一件包裹均被運(yùn)輸。約束（22）確保被選擇的路線數(shù)量不超過(guò)機(jī)器人數(shù)量。約束（23）確保ω為處理完最后一件包裹的時(shí)間。約束（24）設(shè)置了決策變量的范圍。

定義集合K′為該模型的解，K′＝｛k│θk＝1，k∈K｝；路線k中包裹的集合為Sk；在該模型中，包裹允許被運(yùn)輸多次，因此需要對(duì)集合K′中的路線進(jìn)行去重操作，以確保每件包裹僅被運(yùn)輸一次，從而獲得原問(wèn)題最優(yōu)解。去重操作的步驟如下：

步驟1定義未運(yùn)輸?shù)陌蠟镾0；未去重的路線集合為K0；初始化S0←S，K0←K′。從K0中選擇一條路線k，S0←S0＼Sk，K0←K0＼k。

步驟2從K0中選出一條路線k，K0←K0＼k；對(duì)Sk中的所有包裹s，進(jìn)行下述操作：若s?S0，則Sk←Sk＼s；否則S0←S0＼s。

步驟3若K0≠?，跳轉(zhuǎn)至步驟2；否則，更新路線集K′中的路線，即對(duì)于路線k∈K′，路線k中僅保留集合Sk中包含的包裹。

需要指出的是，生成所有可行最長(zhǎng)完整路線并運(yùn)用F2求解，可確保求解結(jié)果為原問(wèn)題的最優(yōu)解。假設(shè)存在最長(zhǎng)完整路線為k，定義所有訪問(wèn)路線k中部分包裹的路線集合為∈K｝。由于路線k′∈中各包裹完成分揀的時(shí)間與路線k中相應(yīng)的包裹完成分揀的時(shí)間相同，從路線k中刪除部分包裹，即可得到任意路線k′∈，因此，生成最長(zhǎng)完整路線作為路線模板，仍可確保求解結(jié)果為最優(yōu)解。

4.2.2 生成子路線模板求解

應(yīng)用4.2.1節(jié)方法，可選擇｜R｜條路線得到路線可行解。隨著包裹數(shù)量的增多，完整路線數(shù)量急劇增加，并且將導(dǎo)致模型F2的規(guī)模增大，難以在有效時(shí)間內(nèi)求得可行路徑解。因此，本節(jié)提出生成子路線模版的方式求解該問(wèn)題。

1）子路線模板的生成

本節(jié)在生成路線時(shí)，用數(shù)條子路線代替最長(zhǎng)完整路線；由于不同的子路線之間可以相互組合，形成不同的完整路線，因此相較于4.2.1節(jié)完整路線模板，運(yùn)用子路線模板可以減少路線的數(shù)量，從而提高求解效率。例如，5條子路線：s1→s2→s3，s1→s6→s7，s4→s5，s8→s10，s9→s11可組合成如下6條最長(zhǎng)完整路線：s1→s2→s3→s4→s5，s1→s2→s3→s8→s10，s1→s2→s3→s9→s11，s1→s6→s7→s4→s5，s1→s6→s7→s8→s10，s1→s6→s7→s9→s11。當(dāng)包裹數(shù)量增多時(shí)，利用子路線方法，可以顯著減少路線數(shù)量。此外，本節(jié)定義參數(shù)B表示子路線的最大長(zhǎng)度。

子路線生成的算法框架如算法2所示。

算法2 子路線模板生成

2）基于子路線模板的模型（F3）

與構(gòu)建模型F2時(shí)類(lèi)似，本節(jié)仍先將約束（4）松弛，隨后構(gòu)建路線決策模型，從子路線模板中為每輛機(jī)器人選擇若干條子路線，使其組合成一條完整路線，作為機(jī)器人的行駛路線。在運(yùn)行算法2求得所有子路線后，為了優(yōu)化子路線的組合方式，設(shè)置下述新集合，并提出基于子路線模板的模型（F3）：

集合與下標(biāo)。ok為路線k的起點(diǎn)，即ok＝｛s｜min｛us，s∈Sk｝｝；ek為路線k的終點(diǎn)，即ek＝｛s｜max｛us，s∈Sk｝｝；Ω+k為路線k的緊后路線集合，即行駛路線k后可行駛的路線集合，Ω+k＝｛k′｜ok′∈Fek，k′∈K｝；Ω-k為路線k的緊前路線集合，即行駛路線k前可行駛的路線集合，Ω-k＝｛k′｜ek′∈Pok，k′∈K｝。

參數(shù)。ck為路線k的費(fèi)用；xs，k，路線k運(yùn)輸包裹s時(shí)為1，否則為0。

決策變量。θk，r為0-1決策變量，若機(jī)器人r行駛路線k為1，否則為0；λk，k′，r為0-1決策變量，若機(jī)器人r行駛路線k后再行駛路線k′則為1，否則為0。

數(shù)學(xué)模型（F3）

目標(biāo)函數(shù)（25）表示最小化處理完該批次中最后一件包裹的時(shí)間。約束（26）確保任意一件包裹均被運(yùn)輸。約束（27）確保機(jī)器人從虛擬起始路線出發(fā)，并回到虛擬終止路線。約束（28）表示對(duì)于某輛機(jī)器人而言，其行駛的子路線一定存在緊前緊后路線，且其緊前或緊后路線具有唯一性。約束（29）確保ω為處理完最后一件包裹的時(shí)間。約束（30）設(shè)置了決策變量的范圍。

5 數(shù)值實(shí)驗(yàn)

為了驗(yàn)證第4節(jié)中所設(shè)計(jì)的算法的有效性以及高效性，本節(jié)進(jìn)行了大量的數(shù)值實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果展示在表1和表2中。本文所用實(shí)驗(yàn)平臺(tái)的CPU為Intel Xeon E5-2680 v4 CPU＠2.40GHz，內(nèi)存為256GB，采用Windows7 64位處理系統(tǒng)。代碼在C＃中實(shí)現(xiàn)，C＃版本為Visual Studio 2019，CPLEX版本為12.6.1。

表1 小規(guī)模算例結(jié)果

表2 大規(guī)模算例結(jié)果

5.1 算法測(cè)試

本節(jié)設(shè)計(jì)了大量實(shí)驗(yàn)對(duì)以下四種求解方法的效率進(jìn)行對(duì)比：（1）使用CPLEX求解器求解F1。（2）使用分支定界算法求解目的地指派策略，將指派策略作為已知參數(shù)帶入F1，使用CPLEX求解機(jī)器人的最優(yōu)運(yùn)輸路線；可稱(chēng)作基于CPLEX的分支定界算法，以下簡(jiǎn)稱(chēng)為BB+CPLEX。（3）使用分支定界算法求解目的地指派策略，使用4.2.1節(jié)生成完整路線模板的方法求解機(jī)器人的運(yùn)輸路線；可稱(chēng)作基于完整路線模板法的分支定界算法，以下簡(jiǎn)稱(chēng)為BB+Route。（4）使用分支定界算法求解目的地指派策略，使用4.2.2節(jié)生成子路線模板的方法求解機(jī)器人的運(yùn)輸路線；可稱(chēng)作基于子路線模板法的分支定界算法，以下簡(jiǎn)稱(chēng)為BB+SubRoute。每種求解方式取得的目標(biāo)值以及求解時(shí)間均被記錄在表1中，并且為了避免偶然性，在每組算例規(guī)模下，本文進(jìn)行了5次實(shí)驗(yàn)。此外，為保證算法可在適當(dāng)時(shí)間內(nèi)求得解，本文設(shè)定所有算法與CPLEX求解器的求解時(shí)間上限為7200秒。

從表1可以看出，在小規(guī)模算例中，BB+CPLEX、BB+Route、BB+SubRoute算法的求解結(jié)果與CPLEX的Gap均為0，且求解速度明顯更快，這說(shuō)明三種算法的求解效果均優(yōu)于CPLEX求解器。此外，相較于其他算法，BB+Route算法表現(xiàn)最優(yōu)，可在最短時(shí)間內(nèi)求得與CPLEX相同的解，這說(shuō)明求解小規(guī)模問(wèn)題時(shí)，可運(yùn)用BB+Route算法快速求解。而B(niǎo)B+SubRoute的求解時(shí)間略長(zhǎng)于BB+Route，這是因?yàn)樵谛∫?guī)模問(wèn)題中，子路線模板中的路線數(shù)量并未明顯少于完整路線模板中的數(shù)量，尚未發(fā)揮其優(yōu)勢(shì)。

為了進(jìn)一步驗(yàn)證BB+SubRoute算法的有效性，本節(jié)設(shè)計(jì)了大規(guī)模實(shí)驗(yàn)并展示了求解效果，如表2所示。由于在大規(guī)模算例中，CPLEX 以及BB+CPLEX均無(wú)法在有效時(shí)間（7200秒）內(nèi)求得解，因此未在表格中展示。表2對(duì)比了BB+Route與BB+SubRoute兩種算法的求解結(jié)果。在較小的規(guī)模算例下（如算例規(guī)模4-19-50），BB+Route算法求解時(shí)間明顯優(yōu)于BB+SubRoute算法；隨著算例規(guī)模的增大，BB+Route算法已無(wú)法在7200秒內(nèi)求得最優(yōu)解，而B(niǎo)B+SubRoute算法可在500秒內(nèi)求得最優(yōu)解，說(shuō)明了BB+SubRoute算法在求解大規(guī)模算例時(shí)，比BB+Route算法更具優(yōu)勢(shì)。因此，在求解小規(guī)模問(wèn)題時(shí)，可運(yùn)用BB+Route算法進(jìn)行求解；在求解大規(guī)模問(wèn)題時(shí)，可運(yùn)用BB+SubRoute算法進(jìn)行求解。

5.2 敏感性分析

本文研究的基于智能移載搬運(yùn)機(jī)器人的自動(dòng)化倉(cāng)庫(kù)系統(tǒng)，由傳送帶分揀機(jī)、機(jī)器人和籠車(chē)組成。在前文中，構(gòu)建了混合整數(shù)規(guī)劃模型以決策系統(tǒng)中包裹的目的地分配以及機(jī)器人的運(yùn)輸路線，隨后設(shè)計(jì)了算法以高效求解模型。事實(shí)上，系統(tǒng)中的其他資源，如傳送帶的運(yùn)行速度、籠車(chē)的布局也會(huì)影響系統(tǒng)的性能。本節(jié)通過(guò)對(duì)傳送帶速度與籠車(chē)布局方式進(jìn)行分析，進(jìn)而為倉(cāng)庫(kù)經(jīng)營(yíng)者提供決策建議。

正常情況下，該分揀設(shè)備的傳送帶運(yùn)行速度一般為2.7米／秒，并且該設(shè)備可根據(jù)具體情況對(duì)運(yùn)行速度進(jìn)行調(diào)整。對(duì)籠車(chē)來(lái)說(shuō)，不當(dāng)?shù)牟季謱?dǎo)致機(jī)器人在運(yùn)輸過(guò)程中的無(wú)用行程增加。本節(jié)將對(duì)比以下四種籠車(chē)的布局方式，研究籠車(chē)不同布局對(duì)分揀效率的影響。

①隨機(jī)布局。不同目的地的包裹對(duì)應(yīng)的籠車(chē)隨機(jī)分布在籠車(chē)暫存區(qū)的各個(gè)位置，如圖4（a）所示。

圖4 籠車(chē)排列方式示意圖（籠車(chē)上數(shù)字代表包裹數(shù)量）

②最短平均距離布局?；\車(chē)的位置由要分配的包裹數(shù)決定。將要裝載更多包裹的籠車(chē)分配到與分揀格口平均距離較小的位置，如圖4（b）所示。

③列式布局。將裝載同一目的地包裹的一組籠車(chē)安排在同一列，如圖4（c）所示。

④組合布局?；诹惺脚帕胁季?，將裝載更多包裹的籠車(chē)列分配到與揀選站較近的位置，對(duì)于同一列的籠車(chē)，將要裝載更多包裹的籠車(chē)分配到離分揀格口較近的位置，如圖4（d）所示。

為了對(duì)比不同傳送帶速度下、不同籠車(chē)布局下的總分揀時(shí)間的差異，本節(jié)對(duì)傳送帶速度與籠車(chē)布局的不同的組合方式，均進(jìn)行5次實(shí)驗(yàn)，取總分揀時(shí)間的平均值作為縱坐標(biāo)，其結(jié)果如圖5所示。可以看出，傳送帶速度對(duì)包裹的總分揀時(shí)間的影響比較微弱，恰當(dāng)?shù)牟季址绞綍?huì)明顯縮短包裹的總分揀時(shí)間；在四種不同的布局中，隨機(jī)布局的總分揀時(shí)間最長(zhǎng)，性能最差，這是因?yàn)樵陔S機(jī)布局中往往會(huì)存在一些不當(dāng)布局；相較于隨機(jī)布局，其他三種布局方式均可縮短總分揀時(shí)間，其中列式布局與組合布局兩者的總分揀時(shí)間相差不大，均明顯短于隨機(jī)布局和最短平均距離布局。

圖5 傳送帶速度對(duì)總分揀時(shí)間的影響

在分揀過(guò)程中，總分揀時(shí)間可分為機(jī)器人總行駛時(shí)間以及機(jī)器人等待時(shí)間，機(jī)器人行駛時(shí)會(huì)產(chǎn)生行駛成本。為了對(duì)比不同包裹數(shù)量下、不同籠車(chē)布局方式對(duì)機(jī)器人總行駛時(shí)間的影響，對(duì)于每組情形，同樣進(jìn)行5次實(shí)驗(yàn)，取總分揀時(shí)間的平均值作為縱坐標(biāo)值，結(jié)果如圖6所示?？梢钥闯霎?dāng)包裹數(shù)量一定時(shí)，組合布局中，機(jī)器人的總行駛時(shí)間小于其他布局方式，且隨著包裹數(shù)量的增大，組合布局的優(yōu)勢(shì)也愈發(fā)明顯。從上述結(jié)果可以看出，倉(cāng)庫(kù)經(jīng)營(yíng)者在部署倉(cāng)庫(kù)的籠車(chē)資源時(shí)，可選擇組合布局提高倉(cāng)庫(kù)運(yùn)作效率。

圖6 包裹數(shù)量對(duì)總行駛時(shí)間的影響

6 結(jié)論與啟示

本文以基于智能移載搬運(yùn)機(jī)器人的自動(dòng)化倉(cāng)庫(kù)系統(tǒng)為背景，研究了該系統(tǒng)中包裹目的地指派與機(jī)器人路徑規(guī)劃的集成優(yōu)化調(diào)度問(wèn)題。為解決此問(wèn)題，本文建立了一個(gè)以最小化完成分揀時(shí)間為目標(biāo)的混合整數(shù)規(guī)劃模型，并設(shè)計(jì)精確式求解算法求解該模型。大量實(shí)驗(yàn)驗(yàn)證了本文提出的模型與算法的有效性與高效性。此外，本文還對(duì)智能移載搬運(yùn)系統(tǒng)中的相關(guān)資源進(jìn)行了敏感度分析。本文的貢獻(xiàn)總結(jié)如下：

（1）智能移載搬運(yùn)系統(tǒng)主要由傳送帶分揀機(jī)與智能移載搬運(yùn)機(jī)器人組成，為實(shí)現(xiàn)系統(tǒng)中這兩種分揀設(shè)備的協(xié)同運(yùn)作，本文提出了一個(gè)混合整數(shù)線性規(guī)劃模型，以實(shí)現(xiàn)目的地指派與智能移載搬運(yùn)機(jī)器人路徑規(guī)劃問(wèn)題的集成優(yōu)化。

（2）為了高效求解上述建立的模型，本文設(shè)計(jì)了精確式求解算法——基于路線模板法的分支定界算法，并且大量的數(shù)值實(shí)驗(yàn)驗(yàn)證了算法的高效性，并得到如下結(jié)論：在小規(guī)模情況下，兩種基于路線模板的分支定界算法可在極短時(shí)間內(nèi)求得問(wèn)題的最優(yōu)。在大規(guī)模情況下，基于子路線模板法的分支定界算法的求解效率更高。

（3）為了探究智能移載搬運(yùn)系統(tǒng)中其他資源對(duì)系統(tǒng)性能的影響，本文對(duì)倉(cāng)庫(kù)中籠車(chē)的布局方式以及傳送帶的運(yùn)行速度進(jìn)行了敏感度分析實(shí)驗(yàn)，并給出管理啟示，為倉(cāng)庫(kù)的布局方式以及傳送帶的運(yùn)行提供了決策依據(jù)，有助于提升倉(cāng)庫(kù)的運(yùn)作效率。