電商RMFS系統(tǒng)訂單分配與路徑規(guī)劃聯(lián)合優(yōu)化方法

秦進(jìn)，楊淑鈞，戴博

(1. 中南大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長(zhǎng)沙 410075；2. 湖南工商大學(xué) 工商管理學(xué)院，湖南 長(zhǎng)沙 410205；3. 特魯瓦技術(shù)大學(xué) 工業(yè)系統(tǒng)優(yōu)化實(shí)驗(yàn)室，法國(guó) 特魯瓦 10004)

隨著經(jīng)濟(jì)社會(huì)快速發(fā)展和互聯(lián)網(wǎng)技術(shù)的日益更新，電商行業(yè)發(fā)展迅猛。在面對(duì)海量客戶需求的環(huán)境下，電商訂單還呈現(xiàn)出高頻率、多品種、小批量等特性，這都使訂單處理變得極為復(fù)雜，也對(duì)電商物流的運(yùn)營(yíng)水平等提出更高要求[1]。在電商物流中心日常運(yùn)營(yíng)中，特別是在雙十一、雙十二等大促時(shí)期，如何準(zhǔn)確快速處理海量訂單、縮短商品交付時(shí)間，已成為電商企業(yè)核心競(jìng)爭(zhēng)力的關(guān)鍵所在。訂單揀選是電商物流倉(cāng)儲(chǔ)的關(guān)鍵環(huán)節(jié)，是指按訂單從存儲(chǔ)位置取出商品的全過(guò)程。在傳統(tǒng)的“人到貨”揀選系統(tǒng)中，人員行走時(shí)間占揀貨總時(shí)間的50%+，導(dǎo)致揀選效率低下[1-2]，難以滿足電商時(shí)代對(duì)訂單處理的需求。為節(jié)省人工并提高揀選速度，在智能化趨勢(shì)下，越來(lái)越多電商企業(yè)開始使用移動(dòng)機(jī)器人揀貨系統(tǒng)(Robotic Mobile Fulfillment System, RMFS)完成訂單揀選[3]。以亞馬遜Kiva系統(tǒng)為代表，RMFS采用機(jī)器人進(jìn)行貨物存儲(chǔ)、搜索、選擇和運(yùn)送工作，實(shí)現(xiàn)“貨到人”揀選模式的轉(zhuǎn)變。然而RMFS系統(tǒng)也帶來(lái)一系列新的挑戰(zhàn)。一方面，如何根據(jù)訂單信息快速匹配貨架和揀選站，合理規(guī)劃?rùn)C(jī)器人行走路徑，對(duì)系統(tǒng)協(xié)同調(diào)度能力提出了考驗(yàn)；另一方面，目前常用的“先到先揀選”(First-Come-First-Service, FCFS)策略往往會(huì)造成貨架重復(fù)進(jìn)出和機(jī)器人行走路線迂回，一定程度上會(huì)影響揀選設(shè)備性能的充分發(fā)揮和揀選作業(yè)效率。近年來(lái)，RMFS優(yōu)化研究受到越來(lái)越多關(guān)注。TOMPKINS 等[2]指出Kiva系統(tǒng)中AGV取回貨架的時(shí)間占比較大。WEIDINGER等[4]以貨架往返總距離最小化為目標(biāo)優(yōu)化返回貨架的位置分配。訂單分配是按一定規(guī)則對(duì)訂單進(jìn)行分批或排序，以盡可能地滿足多個(gè)訂單的需求，減少人工或設(shè)備的重復(fù)作業(yè)，縮短揀選作業(yè)時(shí)間。對(duì)于人工揀選系統(tǒng)，王轉(zhuǎn)等[5]指出里程節(jié)約的訂單分批方法效果優(yōu)于相似度分批法和傳統(tǒng)先到先分批規(guī)則。MENéNDEZ等[6]運(yùn)用常規(guī)變鄰域搜索算法解決訂單分批和排序問(wèn)題。相比于人工揀選系統(tǒng)，RMFS系統(tǒng)訂單分配相關(guān)研究較少。YANG等[3]將訂單排序與貨架調(diào)度問(wèn)題結(jié)合起來(lái)。BOYSEN等[7]研究了貨架移動(dòng)機(jī)器人系統(tǒng)中的訂單分批、訂單排序和貨架順序問(wèn)題，但只關(guān)注單個(gè)揀選站處理過(guò)程，現(xiàn)實(shí)情況中往往是多個(gè)揀選站并行處理訂單。揀選路徑規(guī)劃，目的是找出一條從起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)路線，縮短揀選員或設(shè)備的移動(dòng)距離。在人工揀選系統(tǒng)中，TOMPKINS等[2]總結(jié)了穿越法、最大間隙法、通道接通道法、返回法和中點(diǎn)回轉(zhuǎn)法等常用的揀貨路徑策略。王宏等[8]考慮了傳統(tǒng)雙區(qū)型倉(cāng)庫(kù)下的揀選員行走路徑問(wèn)題。而RMFS系統(tǒng)下的路徑規(guī)劃問(wèn)題，需要在人工揀貨路徑規(guī)劃經(jīng)驗(yàn)的基礎(chǔ)上充分考慮機(jī)器人移動(dòng)特性。夏揚(yáng)坤等[9]將多種類AGV物料配送規(guī)劃問(wèn)題歸結(jié)為帶軟時(shí)間窗的需求依訂單拆分車輛路徑問(wèn)題。張喜妹[10]針對(duì)Kiva系統(tǒng)的路徑規(guī)劃問(wèn)題提出了改進(jìn)的A*算法。綜上所述，在RMFS訂單分配決策的既有研究中，較少考慮多訂單、多貨架、多揀選站之間的分配關(guān)系和機(jī)器人運(yùn)輸距離。同時(shí)，研究多集中于訂單分配或路徑規(guī)劃的單獨(dú)決策，針對(duì)兩者的聯(lián)合優(yōu)化問(wèn)題目前才開始得到重視。因此，本文立足電商企業(yè)場(chǎng)景下的RMFS系統(tǒng)特性，考慮多個(gè)揀選站和距離因素，以機(jī)器人負(fù)載距離最小化為目標(biāo)，構(gòu)建訂單分配和路徑規(guī)劃聯(lián)合優(yōu)化模型，并設(shè)計(jì)A*和自適應(yīng)大領(lǐng)域搜索(Adaptive Large Neighborhood Search, ALNS)算法進(jìn)行求解和分析。

1 問(wèn)題描述與分析

RMFS系統(tǒng)由可移動(dòng)貨架、移動(dòng)機(jī)器人、揀選站臺(tái)等部分組成，采用網(wǎng)格排列的模式?？梢苿?dòng)貨架是RMFS系統(tǒng)中的存儲(chǔ)設(shè)備，貨架上的料箱用于存放商品，底部一層中空留出機(jī)器人運(yùn)輸空間。當(dāng)系統(tǒng)下達(dá)訂單任務(wù)時(shí)，機(jī)器人沿著指定路線到達(dá)待揀選貨架位置，將貨架頂起離開地面后搬運(yùn)貨架前往目標(biāo)揀選站，等待人工揀出商品再運(yùn)送貨架回到存儲(chǔ)位置。揀選作業(yè)區(qū)域并行排列多個(gè)揀選站，每個(gè)揀選站可同時(shí)處理的訂單數(shù)量有限。在揀選站臺(tái)內(nèi)，揀選員借助激光指示器、條碼掃描儀等設(shè)備，從貨架上取出商品放入貨箱中[4]，揀選完畢后訂單對(duì)應(yīng)貨箱經(jīng)傳送帶輸送到出庫(kù)區(qū)打包，重復(fù)上述過(guò)程直到完成所有訂單。

在此場(chǎng)景下，RMFS系統(tǒng)訂單分配的決策問(wèn)題包括：1) 如何劃分訂單批次；2) 尋找能夠滿足每個(gè)批次訂單商品需求的待揀選貨架；3) 為每個(gè)批次訂單和待揀選貨架指定一個(gè)揀選站。由于待揀選貨架需要借助機(jī)器人搬運(yùn)至揀選站，完成揀貨作業(yè)后機(jī)器人再運(yùn)送其返回貨架存儲(chǔ)區(qū)域，因此機(jī)器人行走距離是影響訂單分配的重要因素。

圖1 RMFS系統(tǒng)倉(cāng)庫(kù)布局示意Fig. 1 Schematic layout of a warehouse section in RMFS

RMFS系統(tǒng)路徑規(guī)劃的決策問(wèn)題是確定機(jī)器人行走路線及距離。機(jī)器人的行走路徑包含3個(gè)部分：1) 從當(dāng)前位置到目標(biāo)貨架；2) 運(yùn)送待揀選貨架至目標(biāo)揀選站；3) 從揀選站運(yùn)送貨架返回存儲(chǔ)位置。其中，1) 為空載距離，機(jī)器人可以無(wú)負(fù)荷穿梭于貨架底部；2)和3)為負(fù)載距離，機(jī)器人只能在通道內(nèi)運(yùn)輸貨架。由于機(jī)器人在貨架和揀選站之間來(lái)回的負(fù)載距離占據(jù)總距離的主要部分，對(duì)負(fù)載距離進(jìn)行優(yōu)化可以替代機(jī)器人行走總距離實(shí)現(xiàn)縮短訂單揀選時(shí)間、降低機(jī)器人能耗的目標(biāo)[4]。因此，本文以機(jī)器人負(fù)載距離最小化為目標(biāo)，將訂單分配與路徑規(guī)劃問(wèn)題聯(lián)合起來(lái)，并劃分為2個(gè)階段：第1階段路徑規(guī)劃，找出貨架到不同揀選站之間的最短路徑，即機(jī)器人負(fù)載距離，標(biāo)記路線和長(zhǎng)度；第2階段訂單分配，根據(jù)第1階段所得到的最短距離，以最小化機(jī)器人負(fù)載距離為目標(biāo)，生成訂單分批計(jì)劃，確定合適的批次出庫(kù)貨架及任務(wù)揀選站，從而建立起訂單、批次、貨架、揀選站之間的順序關(guān)系。

為了便于開展研究且不失一般性，本文做出下列假設(shè)：1) 訂單需求信息、貨架存儲(chǔ)信息已知，倉(cāng)庫(kù)采取隨機(jī)存儲(chǔ)策略，商品可以存儲(chǔ)在任何可用貨位；2) 無(wú)缺貨現(xiàn)象，所有貨架上的商品庫(kù)存數(shù)量總和大于所有訂單的需求數(shù)量；3) 訂單交付時(shí)間相同，批次內(nèi)訂單順序、待揀選貨架到達(dá)揀選站順序任意；4) 一個(gè)批次訂單只能由同一個(gè)揀選站完成揀選，不能拆分到其他揀選站；5) 待揀選貨架不在揀選站之間移動(dòng)，在一個(gè)揀選站完成揀選任務(wù)后隨即返回存儲(chǔ)區(qū)域；6) 每個(gè)貨架規(guī)格屬性相同，存儲(chǔ)位置不變，貨架出庫(kù)完成揀選任務(wù)后回到初始存儲(chǔ)位置；7) 靜態(tài)路徑規(guī)劃，不考慮機(jī)器人行進(jìn)過(guò)程中的擁堵或避碰情況。

2 模型構(gòu)建

在建立模型前，對(duì)參數(shù)和變量進(jìn)行定義，具體如表1所示。

表1 符號(hào)定義Table 1 Notation definitions

由此，以機(jī)器人負(fù)載總距離最小為目標(biāo)，建立RMFS系統(tǒng)訂單分配與路徑規(guī)劃混合整數(shù)規(guī)劃模型如下：

目標(biāo)函數(shù)(1)表示所有批次出庫(kù)貨架往返于存儲(chǔ)位置和揀選站之間的距離，即機(jī)器人負(fù)載總距離最小，drs為機(jī)器人運(yùn)送貨架r到揀選站s的最短距離。式(2)～(10)表示約束條件。式(2)和(3)確定訂單與批次的對(duì)應(yīng)關(guān)系，式(2)表示一個(gè)訂單只能被分配到一個(gè)批次，式(3)表示批次容量，每一批次中最多包含C個(gè)訂單。式(4)～(6)確定批次訂單與貨架的對(duì)應(yīng)關(guān)系，式(4)表示從待揀選貨架上揀出的商品數(shù)量必須滿足每一批次訂單需求，式(5)表示初始庫(kù)存限制，式(6)建立揀選商品數(shù)量與貨架是否被選擇之間的關(guān)系，使約束線性化。式(7)和(8)確定批次訂單與揀選站、批次貨架集與揀選站之間的對(duì)應(yīng)關(guān)系，式(7)表示一個(gè)批次訂單只能在同一個(gè)揀選站中進(jìn)行揀選作業(yè)，式(8)表示每一批次出庫(kù)貨架集前往該批次指定的揀選站。式(9)和(10)表示變量的取值范圍。

3 求解算法設(shè)計(jì)

RMFS系統(tǒng)訂單分配與路徑規(guī)劃聯(lián)合問(wèn)題在訂單分批問(wèn)題的基礎(chǔ)上增加了貨架和揀選站的任務(wù)指派及機(jī)器人路徑規(guī)劃，是NP難問(wèn)題。精確算法求解此類問(wèn)題需要耗費(fèi)較長(zhǎng)時(shí)間，本文設(shè)計(jì)了兩階段的啟發(fā)式算法對(duì)訂單分配和路徑規(guī)劃聯(lián)合問(wèn)題進(jìn)行求解。

由于A*算法是靜態(tài)路網(wǎng)中求解最短路徑的有效方法，被廣泛應(yīng)用于機(jī)器人路徑規(guī)劃[11-12]，第1階段首先使用A*算法求解路徑規(guī)劃問(wèn)題。自適應(yīng)大領(lǐng)域搜索算法(Adaptive Large Neighborhood Search, ALNS)最初由ROPKE等[13]提出用于解決帶時(shí)間窗的取送貨車輛問(wèn)題，算法通過(guò)動(dòng)態(tài)選擇移除算子和修復(fù)算子不斷對(duì)解進(jìn)行破壞和重構(gòu)，具有快速收斂的特性，容易跳出局部最優(yōu)，已適應(yīng)越來(lái)越多的優(yōu)化場(chǎng)景。?ULJ等[14]構(gòu)建了ALNS和TS禁忌搜索的組合方法解決大規(guī)模訂單分批問(wèn)題。王新等[15]根據(jù)車輛與無(wú)人機(jī)聯(lián)合配送路徑問(wèn)題特性設(shè)計(jì)了相應(yīng)的ALNS算法。李婷玉[16]指出在多商戶多車程同城物流配送車輛路徑問(wèn)題中，ALNS算法能夠以較低成本獲得最優(yōu)解，效果優(yōu)于TS算法。因此，第2階段使用ALNS算法對(duì)訂單分配問(wèn)題進(jìn)行求解。

3.1 A＊算法

A*算法結(jié)合了Dijkstra算法和最佳優(yōu)先搜索的思想，通過(guò)選擇合適的估價(jià)函數(shù)計(jì)算當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)代價(jià)最小的距離，啟發(fā)式選擇路徑的搜索方向，最終確定整條路徑。A*算法的估價(jià)函數(shù)可表示為：f(n)=g(n) +h(n)。其中，f(n)表示從起點(diǎn)到終點(diǎn)的估價(jià)函數(shù)，g(n)表示從起點(diǎn)到當(dāng)前節(jié)點(diǎn)n的實(shí)際代價(jià)，h(n)表示當(dāng)前節(jié)點(diǎn)n到終點(diǎn)的估計(jì)代價(jià)。

由于RMFS系統(tǒng)通常設(shè)置在網(wǎng)格上，而且機(jī)器人只能朝正北、正南、正東、正西4個(gè)方向直線移動(dòng)，選擇柵格法對(duì)倉(cāng)庫(kù)環(huán)境進(jìn)行建模，對(duì)機(jī)器人運(yùn)動(dòng)的二維平面區(qū)域建立直角坐標(biāo)系，以1為單位建立一個(gè)柵格，采用曼哈頓距離對(duì)距離進(jìn)行度量，兩點(diǎn)之間的曼哈頓距離為南北方向距離加上東西方向距離，即：d=|x1-x2|+|y1-y2|，其中，(x1， y1)和(x2， y2)分別表示2點(diǎn)坐標(biāo)。

3.2 自適應(yīng)大領(lǐng)域搜索算法(ALNS)

在傳統(tǒng)ALNS算法的基礎(chǔ)上，根據(jù)RMFS訂單分配問(wèn)題特性，設(shè)計(jì)改進(jìn)ALNS算法進(jìn)行模型求解。

3.2.1 初始解生成

采用隨機(jī)方法生成初始解。首先在不違反批次容量約束的前提下，依次將訂單隨機(jī)放入候選批次，生成訂單分批方案。接著根據(jù)商品庫(kù)存信息，尋找滿足每個(gè)批次訂單需求的貨架，為批次隨機(jī)分配任務(wù)揀選站，得到初始解決方案。為了更好地表示訂單分批以及貨架揀選站分配的過(guò)程，設(shè)計(jì)了對(duì)應(yīng)解的編碼。

訂單分批時(shí)按訂單編號(hào)順序排列，每一訂單i位置上的數(shù)字對(duì)應(yīng)著批次b。例如編碼[1, 3, 2, 1]表示訂單1和4劃分到批次1中，訂單2劃分到批次3中，訂單3劃分到批次2中。分配貨架和揀選站時(shí)，建立如圖2所示的二維數(shù)組，縱軸為批次，橫軸為貨架。貨架出庫(kù)狀態(tài)用0和正整數(shù)表示，0表示在批次訂單b中貨架r不出庫(kù)；正整數(shù)表示揀選站編號(hào)，即貨架r出庫(kù)執(zhí)行批次訂單b的揀選任務(wù)，去往批次指定的揀選站s。示例中批次1的出庫(kù)貨架為2，3和5，前往揀選站3進(jìn)行揀選。

圖2 貨架和揀選站分配編碼Fig. 2 Rack and picking station assignment code

3.2.2 移除算子和修復(fù)算子

在生成初始解后，ALNS算法采用移除算子將一定比例ξ的節(jié)點(diǎn)從解中刪除，再利用修復(fù)算子將移除列表里的節(jié)點(diǎn)重新插入到不完整的解中，形成新解。

對(duì)于訂單分批問(wèn)題，設(shè)計(jì)了2種移除算子和2種修復(fù)算子。1) 隨機(jī)移除訂單。在當(dāng)前解中隨機(jī)選擇一定數(shù)量的訂單，將它們移出原來(lái)所在的批次。該操作可增加解的多樣性，使其不易陷入局部最優(yōu)解。2) 最差距離訂單移除。計(jì)算每一訂單對(duì)應(yīng)的批次負(fù)載距離，移除距離較長(zhǎng)的訂單。3)隨機(jī)修復(fù)訂單。隨機(jī)生成批次編號(hào)，插入到被破壞的解中。4) 貪婪插入批次。將移除的訂單插入到距離最短的批次中。

對(duì)于貨架和揀選站的分配，同樣設(shè)計(jì)2種移除算子和2種修復(fù)算子。1) 隨機(jī)移除貨架和揀選站。選擇一定數(shù)量的批次，移除批次中對(duì)應(yīng)的任務(wù)貨架和揀選站。2) 移除最差批次貨架和揀選站。計(jì)算負(fù)載距離較長(zhǎng)的批次，移除貨架和揀選站。3) 隨機(jī)修復(fù)貨架和揀選站。隨機(jī)分配貨架和揀選站給被破壞的批次解。4) 貪婪修復(fù)貨架和揀選站。比較貨架和揀選站的不同分配情況，選擇使批次負(fù)載距離增加最少的分配結(jié)果。

3.2.3 自適應(yīng)機(jī)制

自適應(yīng)機(jī)制是ALNS算法的核心部分，其基本思想是根據(jù)產(chǎn)生的新解情況為移除算子和修復(fù)算子賦予相應(yīng)的分?jǐn)?shù)。當(dāng)?shù)玫叫碌娜肿顑?yōu)解時(shí)，算子加分σ1；當(dāng)?shù)玫揭粋€(gè)尚未接受過(guò)但比當(dāng)前解更好的解時(shí)，算子加分σ2；當(dāng)?shù)玫揭粋€(gè)尚未接受過(guò)且比當(dāng)前解差，但滿足接受準(zhǔn)則的解時(shí)，算子加分σ3。將ALNS算法分為若干階段，算法根據(jù)前一個(gè)階段的表現(xiàn)更新算子的權(quán)重，權(quán)重更新公式如下：

其中：wi表示算子第i階段的權(quán)重；βi表示算子評(píng)分；αi表示算子累計(jì)的調(diào)用次數(shù)；ρ為權(quán)重更新系數(shù)，控制權(quán)重變化速度。算子的表現(xiàn)越好，得分和權(quán)重越高，下一階段被輪盤賭選擇的概率越大。

3.2.4 接受準(zhǔn)則和終止條件

為了避免陷入局部最優(yōu)，根據(jù)模擬退火算法的Metropolis準(zhǔn)則以一定概率P=e-[f(xnew)-f(xcurrent)/T]接受劣解。其中，T為當(dāng)前溫度，每次迭代T=T0·θ，T0為模擬退火初始溫度，θ∈[0， 1]為降溫速率；f(xnew)為新解的目標(biāo)函數(shù)值；f(xcurrent)為當(dāng)前解的目標(biāo)函數(shù)值。每次迭代中內(nèi)層模擬退火過(guò)程的終止溫度為Tend，算法達(dá)到最大迭代次數(shù)后停止搜索。

4 算例分析

4.1 算例構(gòu)造

如圖3所示，生成小規(guī)模(10×8)、中等規(guī)模(10×15)、大規(guī)模(10×30)3種不同大小的倉(cāng)庫(kù)柵格地圖進(jìn)行仿真實(shí)驗(yàn)。貨架、揀選站、機(jī)器人大小相同且占用一個(gè)柵格，機(jī)器人行走步長(zhǎng)為1。小、中、大3種規(guī)模算例的參數(shù)設(shè)置分別如下：貨架個(gè)數(shù)為25，50和100，揀選站個(gè)數(shù)為2、3和4，訂單分批容量為5，10和15，SKU商品總數(shù)為50、100和200，每張訂單上SKU種類范圍為[1, 3]，[1, 5]和[1, 7]。另外，倉(cāng)庫(kù)內(nèi)每個(gè)貨架隨機(jī)存儲(chǔ)1～6種SKU，每種SKU的庫(kù)存量范圍為[10, 50]，訂單需求量范圍為[1, 5]。仿真實(shí)驗(yàn)測(cè)試的最大訂單數(shù)量為500。

圖3 小規(guī)模、中等規(guī)模、大規(guī)模仿真?zhèn)}庫(kù)柵格地圖Fig. 3 Small scale， medium scale， large scale simulation warehouse grid map

根據(jù)ROPKE等[13]的分析，通過(guò)多次實(shí)驗(yàn)確定ALNS算法參數(shù)：自適應(yīng)機(jī)制中算子分?jǐn)?shù)設(shè)置為σ1=33，σ2=9，σ3=13，權(quán)重更新系數(shù)ρ=0.1；根據(jù)文獻(xiàn)[16]，破壞解的長(zhǎng)度比例ξ=0.2；在接受準(zhǔn)則中，每次迭代內(nèi)層模擬退火過(guò)程的初始溫度T0=100，終止溫度Tend=10，降溫速率θ=0.99，外層最大迭代次數(shù)為100。

4.2 結(jié)果分析

所有實(shí)驗(yàn)均在Python 3.6中編程實(shí)現(xiàn)，運(yùn)行環(huán)境Intel(R) Core(TM) i5-1135G7 @ 2.40 GHz ，16 GB內(nèi)存，調(diào)用IBM ILOG CPLEX12.8，最大運(yùn)行時(shí)間設(shè)為5 h(18 000 s)，每組實(shí)驗(yàn)重復(fù)10次取均值。

在A*算法得到貨架至揀選站最短距離及機(jī)器人搬運(yùn)路線的基礎(chǔ)上，使用FCFS、CPLEX和ALNS算法分別求解小、中、大3種規(guī)模算例的結(jié)果如表2～4所示，并將實(shí)際運(yùn)營(yíng)中常采用的先到先揀選結(jié)果(FCFS)作為對(duì)比基準(zhǔn)。其中Obj表示目標(biāo)函數(shù)即機(jī)器人負(fù)載總距離，Imp表示CPLEX或ALNS求解結(jié)果對(duì)比FCFS基準(zhǔn)數(shù)值的改進(jìn)程度，Gap表示ALNS與CPLEX求解結(jié)果之間的差異程度。

表2 小規(guī)模算例求解結(jié)果Table 2 Results of small-scale experiments

從小規(guī)模算例求解結(jié)果中可以看出，相比簡(jiǎn)單的FCFS規(guī)則，進(jìn)行訂單分配后優(yōu)化效果明顯。其中CPLEX求解平均減少49.3%的機(jī)器人負(fù)載距離，在訂單數(shù)量I=20時(shí)效果最佳，減少52.5%負(fù)載距離。ALNS算法的求解質(zhì)量也較高，平均減少31.1%的機(jī)器人負(fù)載距離，在I=10時(shí)最大可減少47.6%的負(fù)載距離，與CPLEX求解差距均值15.2%，最少為5.8%，得到與CPLEX質(zhì)量相近的解。

求解時(shí)間方面，當(dāng)訂單數(shù)量較少時(shí)(I≤20)，CPLEX可以在1 s內(nèi)求得最優(yōu)解。但隨著訂單數(shù)量的增加，CPLEX求解時(shí)間呈指數(shù)級(jí)增長(zhǎng)，在I=40時(shí)，計(jì)算時(shí)間已高達(dá)7 027.4 s，當(dāng)訂單數(shù)量為50時(shí)已無(wú)法在可接受的時(shí)間(5 h)內(nèi)獲得可行解。

對(duì)于倉(cāng)庫(kù)規(guī)模大、訂單數(shù)量多、時(shí)間要求高的場(chǎng)景來(lái)說(shuō)，使用CPLEX對(duì)訂單進(jìn)行優(yōu)化分配實(shí)用性差。而ALNS算法受訂單數(shù)量增加變化的影響較小，在訂單數(shù)量達(dá)到100時(shí)仍可在較短時(shí)間內(nèi)(588.1 s)獲得21.1%的優(yōu)化效果，時(shí)間優(yōu)勢(shì)明顯，相比CPLEX求解器更適合求解規(guī)模較大的訂單分配問(wèn)題。

由于CPLEX在訂單數(shù)量較大的小規(guī)模算例中已難生成可行解，中等規(guī)模算例中僅對(duì)比FCFS和ALNS算法的求解結(jié)果。ALNS算法在中等規(guī)模算例中仍保持著平均20.1%的優(yōu)化效果，時(shí)間成本低，可在較短時(shí)間內(nèi)獲得高質(zhì)量的解。

表3 中等規(guī)模算例求解結(jié)果Table 3 Results of medium-scale experiments

表4 大規(guī)模算例求解結(jié)果Table 4 Results of large-scale experiments

在大規(guī)模算例中，ALNS算法平均可減少10.7%的機(jī)器人負(fù)載距離，最大可減少15.8%的負(fù)載距離(I=360)。當(dāng)訂單增加到500時(shí)，ALNS算法的運(yùn)行時(shí)間也仍保持在合理范圍內(nèi)(3 967.9 s)。

圖4記錄了ALNS算法在不同規(guī)模算例下的計(jì)算迭代過(guò)程。可以看出ALNS算法基本不依賴初始解的狀態(tài)，能顯著減少機(jī)器人負(fù)載距離，算法收斂較快，性能穩(wěn)定。

圖4 ALNS算法迭代過(guò)程Fig. 4 Iterative process of ALNS algorithm

5 結(jié)論

1) 研究電商物流中心RMFS揀選系統(tǒng)多訂單、多貨架、多揀選站場(chǎng)景下的訂單分配和路徑規(guī)劃聯(lián)合優(yōu)化問(wèn)題，構(gòu)建了以機(jī)器人負(fù)載距離最小為目標(biāo)的混合整數(shù)規(guī)劃模型，并使用A*算法和自適應(yīng)大鄰域搜索算法(ALNS)進(jìn)行求解。

2) 仿真結(jié)果表明，提出的優(yōu)化模型和算法最大可縮短47.6%的機(jī)器人負(fù)載距離，ALNS算法可在較短時(shí)間內(nèi)獲得高質(zhì)量的解，優(yōu)化效果良好，能夠有效縮短機(jī)器人行走距離，提高訂單揀選效率，降低倉(cāng)儲(chǔ)成本，研究結(jié)論可為電商企業(yè)提供運(yùn)營(yíng)指導(dǎo)。

3) 未來(lái)的研究可以引入更多決策因素，如訂單順序、到達(dá)時(shí)窗、動(dòng)態(tài)貨位、機(jī)器人任務(wù)分配等，細(xì)化訂單分配與路徑規(guī)劃聯(lián)合問(wèn)題特征，使問(wèn)題更符合RMFS系統(tǒng)實(shí)際運(yùn)營(yíng)場(chǎng)景。