基于通用變鄰域搜索的多AGV分揀調(diào)度優(yōu)化

郭超 陳香玲 郭鵬 王強(qiáng)

摘 要：為了解決物流倉儲(chǔ)分揀中心多臺(tái)AGV處理大量包裹調(diào)度優(yōu)化困難的問題，在考慮分揀作業(yè)時(shí)間窗和充電需求的基礎(chǔ)上，研究了大規(guī)模AGV調(diào)度問題。以最小化分揀作業(yè)周期為目標(biāo)，提出了一種通用變鄰域搜索（general variable neighborhood search，GVNS）算法，為各臺(tái)AGV指定轉(zhuǎn)運(yùn)任務(wù)和作業(yè)排序，采用遍歷插入啟發(fā)式策略生成滿足時(shí)間窗約束的初始解，設(shè)計(jì)了10種鄰域算子對初始解迭代尋優(yōu)，并對比不同規(guī)模算例的算法性能，分析AGV充電速率和數(shù)量配置對分揀效率的影響。結(jié)果表明，GVNS算法具有計(jì)算時(shí)間和求解性能方面的優(yōu)勢，能在較短時(shí)間內(nèi)求得近似最優(yōu)解，平均計(jì)算時(shí)間僅為532.78 s，明顯優(yōu)于混合整數(shù)規(guī)劃模型和約束規(guī)劃模型;當(dāng)包裹數(shù)為100時(shí)，最合適的AGV配置為14輛。因此，GVNS可以有效解決分揀中心考慮充電需求和硬時(shí)間窗的大規(guī)模多AGV調(diào)度問題，提高物流分揀效率，幫助企業(yè)找到科學(xué)、合理的AGV配置方案。

關(guān)鍵詞：物流系統(tǒng)管理;分揀作業(yè);自動(dòng)導(dǎo)引小車;調(diào)度;充電需求;變鄰域搜索

中圖分類號：F252.1;TP301?? 文獻(xiàn)標(biāo)識(shí)碼：A

doi：10.7535/hbkd.2021yx05011

收稿日期：2021-08-20;修回日期：2021-09-19;責(zé)任編輯：張士瑩

基金項(xiàng)目：國家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目（2020YFB1712200）;宜賓職業(yè)技術(shù)學(xué)院科研平臺(tái)建設(shè)計(jì)劃資助項(xiàng)目（YBZY21KYPT-03）;軌道交通運(yùn)維技術(shù)與裝備四川省重點(diǎn)實(shí)驗(yàn)室開放課題（2020YW004）

第一作者簡介：郭 超（1984—），男，四川宜賓人，講師，主要從事智能制造方面的研究。

通訊作者：郭 鵬副教授。E-mail：pengguo318@swjtu.edu.cn

General variable neighborhood search for the multi-AGV scheduling problem with sorting operations

GUO Chao1，2，CHEN Xiangling3，GUO Peng1，3，WANG Qiang2

（1.Technology and Equipment of Rail Transit Operation and Maintenance Key Laboratory of Sichuan Province，Chengdu，Sichuan 610031，China;2.School of Intelligent Manufacturing，Yibin Vocational and Technical College，Yibin，Sichuan 644003，China;3.School of Mechanical Engineering，Southwest Jiaotong University，Chengdu，Sichuan 610031，China）

Abstract：To solve the intractable multiple automatic guided vehicles （AGVs） scheduling problem encountered in the sorting processes of the logistics sorting centers，a large-scale AGV scheduling problem was studied on the basis of considering the sorting time windows and charging requirements.A general variable neighborhood search （GVNS） algorithm was proposed to minimize the makespan of the sorting operations，in which the assignment of transferring packages to AGVs and the sequence of sorting tasks for each AGV were determined.The traversal insertion heuristic was developed to generate the initial solution of the developed algorithm to ensure the constraint of time windows.Ten neighborhood operators were designed to optimize the initial solution for the iteration of the algorithm.Different sized test instances were compared，and the impacts of AGV charging rate and quantity configuration on sorting efficiency were analyzed.The results show that the GVNS algorithm is superior in computing time and solution performance.It can obtain the approximate optimal solution in a short time.The average computing time of GVNS is only 532.78 s，which is obviously better than the mixed integer and constraint programming models;when the number of packages is 100，the most suitable number of AGVs is 14.Therefore，GVNS can effectively solve the large-scale and multi-AGV scheduling problem with charging demand and hard time window，improve the efficiency of logistics sorting，and help enterprises find the scientific and reasonable AGV configuration scheme.

Keywords：

logistics system management;sorting operation;automatic guided vehicle;scheduling;charging demand;vari-able neighborhood search

隨著電子商務(wù)產(chǎn)業(yè)的不斷發(fā)展壯大，中國快遞包裹經(jīng)歷了連續(xù)十多年的爆炸式增長，從2010年的不足24億件迅速攀升到2020年的833.6億件，目前快遞總量已超過美國、日本及歐洲發(fā)達(dá)國家的快遞量總和，成為名副其實(shí)的“快遞大國”。逐年增長的快遞業(yè)務(wù)量對高效配送提出了更高要求?？爝f包裹從賣家手中到達(dá)買家手中需要經(jīng)歷一系列步驟，包括訂單確認(rèn)，快遞攬件、轉(zhuǎn)運(yùn)、分揀、運(yùn)輸，再分揀、轉(zhuǎn)運(yùn)與送達(dá)等。在完整的快遞配送流程中，至少要經(jīng)歷2次分揀，且每次分揀均會(huì)耗費(fèi)大量時(shí)間。因此，提高物流中心的分揀效率，可以在一定程度上縮短快遞整體配送時(shí)間，讓買家在更短時(shí)間內(nèi)收到包裹。為了應(yīng)對暴增的業(yè)務(wù)量，原有的人工分揀或傳送帶式倉儲(chǔ)物流相繼被自動(dòng)導(dǎo)引車（automatic guided vehicle，AGV）或自主移動(dòng)機(jī)器人（autonomous mobile robot，AMR）揀選作業(yè)系統(tǒng)替代。各大快遞公司（包括菜鳥、申通、順豐等）相繼引入了類似于亞馬遜Kiva機(jī)器人（見圖1）的作業(yè)系統(tǒng)[1-2]。采用上述分揀系統(tǒng)能夠?qū)崿F(xiàn)無人化、自動(dòng)化與智能化，但面臨的管理決策也更加復(fù)雜。因此，對多臺(tái)機(jī)器人開展調(diào)度優(yōu)化成為物流機(jī)器人領(lǐng)域研究的熱點(diǎn)問題之一。早期AGV在單個(gè)項(xiàng)目或者場景中應(yīng)用尚可，但其依賴于磁條等固定導(dǎo)航方式，只能在作業(yè)區(qū)域內(nèi)按照固定的路徑循環(huán)運(yùn)行，應(yīng)用相對簡單，且不需要系統(tǒng)具備較高的調(diào)度能力。類Kiva機(jī)器人的出現(xiàn)，使得對多AMR集群調(diào)度的需求越來越大[3]。多AMR調(diào)度除了要為每個(gè)AMR合理分配任務(wù)從而達(dá)到預(yù)期目標(biāo)，還要考慮到任務(wù)時(shí)間窗、優(yōu)先級、充電需求等各種限制因素。在倉儲(chǔ)物流中，AMR或者AGV調(diào)度主要依賴于最短隊(duì)列或最短走行距離等啟發(fā)式規(guī)則進(jìn)行決策[4]。為了實(shí)現(xiàn)對AGV集群調(diào)度的優(yōu)化，人們提出了多種元啟發(fā)式算法，包括粒子群-遺傳混合算法[5]、差分進(jìn)化算法[6]、Memetic算法[7]、大規(guī)模鄰域搜索[8]、自適應(yīng)大規(guī)模鄰域搜索[9]等。但這些研究對于實(shí)際場景中的柵格地圖和充電約束等考慮尚不充分，缺乏有效的求解手段。為了分析AGV調(diào)度規(guī)則，仿真手段也被用于調(diào)度分析和對比中[10]。

變鄰域搜索（variable neighborhood search，VNS）算法具有良好的通用性和尋優(yōu)能力，已在調(diào)度、設(shè)施布局、設(shè)施選址、車輛路徑等問題中取得了良好效果[11-17]。然而目前還鮮有文獻(xiàn)報(bào)道使用VNS解決考慮充電需求和時(shí)間窗的多AGV調(diào)度問題。為實(shí)現(xiàn)對大規(guī)模問題實(shí)例的求解，筆者基于文獻(xiàn)[18]的研究工作，在多AGV調(diào)度優(yōu)化建?；A(chǔ)上提出采用通用變鄰域搜索（general variable neighborhood search，GVNS）算法，針對多AGV作業(yè)場景下的分揀調(diào)度優(yōu)化問題，設(shè)計(jì)了一種啟發(fā)式規(guī)則，為通用變鄰域搜索算法提供初始解，采用10個(gè)不同的鄰域結(jié)構(gòu)用于局部搜索和擾動(dòng)階段，分析AGV充電速率和數(shù)量配置對優(yōu)化目標(biāo)的影響，通過算例測試，驗(yàn)證了算法的求解性能。

1 物流分揀流程

圍繞分揀作業(yè)流程，物流分揀中心分為入庫區(qū)、出庫區(qū)和分揀區(qū)3部分。分揀區(qū)由分揀臺(tái)、投放口和設(shè)備充電/停放區(qū)組成，如圖2所示，其中a和b分別代表柵格的行數(shù)和列數(shù)。在分揀區(qū)內(nèi)，來自不同地區(qū)的包裹入庫后隨著傳送帶到達(dá)各個(gè)分揀臺(tái)，AGV接收到搬運(yùn)任務(wù)后前往包裹所在分揀臺(tái)。AGV到達(dá)分揀臺(tái)后需要根據(jù)包裹上的運(yùn)單信息，將包裹運(yùn)送至相應(yīng)的投放口，每個(gè)投放口代表不同的城市或地區(qū)。在投放口的下方是漏斗和傳送帶，它們會(huì)收集包裹并將其運(yùn)送至出庫區(qū)，在出庫區(qū)會(huì)有車輛進(jìn)行下一階段的配送。

基于以上應(yīng)用場景，給定任務(wù)集合J={1，2，…，n}，其中J為包含所有任務(wù)的集合，n為任務(wù)總數(shù)。給定AGV集合K={1，2，…，m}，其中K為所有AGV集合，m為其數(shù)量（m=|K|）。AGV不工作時(shí)均?？吭诔潆妳^(qū)，當(dāng)接收到分揀作業(yè)指令時(shí)，其從充電區(qū)出發(fā)執(zhí)行分揀任務(wù)。每個(gè)包裹i（i∈J）都有相應(yīng)的最早到達(dá)時(shí)間ei、搬運(yùn)時(shí)間ti和最晚完工時(shí)間di，最晚完工時(shí)間用于保證包裹分揀出庫后的準(zhǔn)時(shí)派送。

AGV在運(yùn)送包裹時(shí)需經(jīng)歷3個(gè)階段：1）從當(dāng)前位置前往包裹所在的分揀臺(tái);2）若AGV在ei之前到達(dá)分揀臺(tái)，則需等待，否則直接裝載包裹;3）AGV運(yùn)送包裹到對應(yīng)的投放口。每運(yùn)送完一個(gè)包裹，AGV會(huì)檢查當(dāng)前電量是否低于安全電量g。當(dāng)電量充足時(shí)，AGV直接前往下一包裹所在分揀臺(tái);當(dāng)電量不足時(shí)，其需前往充電區(qū)充電，充電完成后再去到下一個(gè)包裹所在分揀臺(tái)。如此反復(fù)，直至所有運(yùn)輸任務(wù)執(zhí)行完畢，最后返回充電區(qū)。具體描述與數(shù)學(xué)規(guī)劃模型詳見文獻(xiàn)[18]。

2 GVNS算法的主要步驟及鄰域結(jié)構(gòu)

變鄰域搜索算法在應(yīng)用過程中衍生處理諸多拓展算法，包括變鄰域深度搜索算法、變鄰域分解搜索算法和偏態(tài)變鄰域搜索算法等[19-20]。本文所提出的通用變鄰域搜索（GVNS）是在局部搜索階段采用VND的變鄰域搜索算法，相比其他的VNS拓展算法擁有非常優(yōu)秀的求解性能，目前已被用于求解單分配集線器定位[21]、帶時(shí)間窗約束的多目標(biāo)車輛路徑與裝載[22]和取送貨一體的旅行商[23]等復(fù)雜組合優(yōu)化問題。GVNS算法的基本思想是在搜索過程中通過變換不同的操作算子盡可能多地探索解空間，尋找局部最優(yōu)解，然后通過擾動(dòng)跳出局部最優(yōu)，經(jīng)過多次迭代，不斷更新最優(yōu)解直至達(dá)到終止條件。

2.1 編碼方式

采用由整數(shù)構(gòu)成的編碼列表來表示每輛AGV待執(zhí)行的任務(wù)序列，其中每個(gè)整數(shù)表示AGV需要搬運(yùn)的包裹編號。每個(gè)AGV必須從充電區(qū)出發(fā)，在執(zhí)行完所有的任務(wù)后返回充電區(qū)。

因此每個(gè)AGV的編碼列表首尾位置都設(shè)置為0，分別表示虛擬開始任務(wù)和虛擬結(jié)束任務(wù)。所有AGV的編碼列表即為問題的一個(gè)解。如圖3所示，以10個(gè)包裹3輛AGV為例，其中包裹[1，3，10]由第1輛AGV負(fù)責(zé)搬運(yùn)，包裹[5，2，8，4]由第2輛AGV搬運(yùn)，同理，包裹[6，9，7]由第3輛AGV負(fù)責(zé)搬運(yùn)，共計(jì)3條路徑列表構(gòu)成了一個(gè)完整的解。

由圖3可以看出，在編碼階段并沒有將充電任務(wù)加入到任務(wù)列表中，這是為了便于后續(xù)的鄰域操作。對于是否需要執(zhí)行充電任務(wù)，會(huì)在遍歷AGV的每條路徑時(shí)加以判斷，進(jìn)而獲得目標(biāo)函數(shù)值。

2.2 初始解

初始解的質(zhì)量會(huì)影響整個(gè)算法的求解效率。為了找到較好的初始可行解，設(shè)計(jì)了一種啟發(fā)式方法，其偽代碼算法如表1所示。

首先生成m個(gè)僅包含虛擬開始任務(wù)和虛擬結(jié)束任務(wù)的空路徑[0，0];然后遍歷所有任務(wù)，計(jì)算每個(gè)任務(wù)在每條路徑的每個(gè)位置的適應(yīng)度值，同時(shí)記錄下每個(gè)任務(wù)的適應(yīng)度值和對應(yīng)的插入位置;找到擁有最小適應(yīng)度值的任務(wù)后，將該任務(wù)插入此位置，然后從任務(wù)列表中刪除該任務(wù);遍歷完所有的任務(wù)并全部插入到路徑列表后，輸出初始解。表1中步驟8的適應(yīng)度值計(jì)算公式為

f=α×Cmax+（1-α）（s′i-si），i∈N。

式中：Cmax為分揀完成時(shí)間;點(diǎn)i為路徑中插入點(diǎn)后面的點(diǎn);si為點(diǎn)i在插入前的路徑中的開始時(shí)間;s0為點(diǎn)i在插入后路徑中的開始時(shí)間。對權(quán)重α進(jìn)行取值，使初始可行解盡可能地實(shí)現(xiàn)最小化分揀完成時(shí)間和時(shí)間窗更緊湊，得到不錯(cuò)的初始解。

2.3 鄰域結(jié)構(gòu)

GVNS算法涉及10個(gè)不同的操作算子。為了便于后續(xù)操作，為每個(gè)操作算子進(jìn)行標(biāo)號處理。需要特別說明的是，每種操作算子在選擇任務(wù)節(jié)點(diǎn)時(shí)都不會(huì)選擇位于路徑首尾位置的虛擬開始任務(wù)點(diǎn)和虛擬結(jié)束任務(wù)點(diǎn)。常用的操作算子包括Cross，2-opt，Relocate，Exchang和ICross，各自操作方式如下。

1）Cross算子（N1） 選擇任意2條路徑，分別從2條路徑任選1個(gè)點(diǎn)作為路徑的斷點(diǎn)，然后交換2條路徑的后半段，形成2條新的路徑，操作示例見圖4。

2）2-opt算子（N2） 選擇任意1條路徑，在該路徑中選擇2個(gè)不同的點(diǎn)作為斷點(diǎn)，使得路徑形成3個(gè)片段，然后對中間片段進(jìn)行逆序操作，形成1條新的路徑，操作示例見圖5。

3）Relocate算子（N3） 重新定位結(jié)構(gòu)，是指任意選擇2條路徑，從1條路徑中任意選擇1個(gè)點(diǎn)插入到另1條路徑的任意位置，形成2條新的路徑，操作示例見圖6。

4）Exchange算子（N4） 選擇任意2條路徑，分別從2條路徑中選擇1個(gè)點(diǎn)進(jìn)行交換，操作示例見圖7。

5）ICross算子（N5） 選擇任意2條路徑，分別取2條路徑任意長度的中間片段，將2條路徑的中間片段進(jìn)行逆序操作然后交換，形成2條新的路徑，操作示例見圖8。

此外，為了擴(kuò)大鄰域解的解空間，還使用了Or-opt算子、GENI算子、λ-Interchange算子3種擴(kuò)展鄰域結(jié)構(gòu)[24]，通過多次迭代保證對最優(yōu)解的搜索能力。

Or-opt算子（N6， N7，N8）：從任意1條路徑中隨機(jī)選擇1個(gè)點(diǎn)i，然后選擇1個(gè)距離i點(diǎn)給定長度x的點(diǎn)j（j=i+x），再從路徑中隨機(jī)選擇1個(gè)點(diǎn)k。路徑被i，j，k 3個(gè)點(diǎn)截成4個(gè)片段，如果k<i或k>j，則交換路徑的2個(gè)中間片段的位置，從而形成1條新路徑。通過為該算子設(shè)置3個(gè)不同長度參數(shù)x（x=1，2，3），形成了3個(gè)不同的鄰域結(jié)構(gòu)。當(dāng)x=2且k>j時(shí)，操作過程如圖9所示。

GENI算子（N9）：選擇任意2條路徑，從第1條路徑中選擇1個(gè)點(diǎn)i插入第2條路徑中的任一位置，然后從第2條路徑中選擇1個(gè)點(diǎn)k插入i點(diǎn)后面，形成2條新路徑，操作示例見圖10。

λ-Interchange算子（N10）：選擇任意2條路徑，分別從2條路徑中選擇任意一點(diǎn)隨機(jī)長度為λ1和λ2的片段進(jìn)行交換，形成2條新的路徑。若路徑1的長度為l1，選定點(diǎn)的位置為a，路徑2的長度為l2，選定點(diǎn)的位置為b，則λ1和λ2分別從整數(shù)均勻分布[1，l1-a-1]和[1，l2-b-1]中隨機(jī)選擇。當(dāng)λ1=λ2=2時(shí)，操作示例如圖11所示。

2.4 局部搜索階段

令Nl（l=1，2，…，lmax）為一組用于局部搜索階段的鄰域結(jié)構(gòu)集合，令Nl（s）為當(dāng)前解s在第l個(gè)鄰域結(jié)構(gòu)中的解集合。采用上述10個(gè)鄰域結(jié)構(gòu)（lmax=10）構(gòu)成VND獲得鄰域解集?；谖墨I(xiàn)[19]的算法機(jī)制，局部搜索階段從鄰域N1開始，到鄰域N10結(jié)束。將當(dāng)前解s傳入一個(gè)鄰域結(jié)構(gòu)后會(huì)產(chǎn)生一組鄰域解Nl（s），其中必然存在一個(gè)局部最優(yōu)解s′。若該局部最優(yōu)解s′優(yōu)于當(dāng)前解s，則將s替換為s′，并且返回到第一個(gè)鄰域結(jié)構(gòu)進(jìn)行搜索;否則，進(jìn)入下一個(gè)鄰域結(jié)構(gòu)進(jìn)行搜索，直到搜索完最后一個(gè)鄰域，若仍未能找到更優(yōu)解，則結(jié)束局部搜索階段。VND算法流程偽代碼如表2所示。

2.5 擾動(dòng)階段

局部搜索階段容易使算法陷入局部最優(yōu)。當(dāng)多次迭代仍然無法對解進(jìn)行改善時(shí)，通常可對當(dāng)前解進(jìn)行適當(dāng)?shù)臄_動(dòng)操作，生成下一次進(jìn)入局部搜索階段的起始解。若當(dāng)前解在經(jīng)過連續(xù)η次迭代后仍未能找到更優(yōu)，則說明算法陷入了局部最優(yōu)，沒有必要繼續(xù)進(jìn)行局部搜索，需要對當(dāng)前解進(jìn)行擾動(dòng)操作。令Nk（k=1，2，…，kmax）為一組用于擾動(dòng)階段的鄰域結(jié)構(gòu)集合，令Nk（s）為當(dāng)前解s在第k個(gè)鄰域結(jié)構(gòu)中的解集合，該階段同樣是上述的10個(gè)鄰域結(jié)構(gòu)（kmax=10）。為了使解空間得到有效擴(kuò)展，選擇隨機(jī)生成10個(gè)鄰域結(jié)構(gòu)的搜索順序。每次擾動(dòng)操作時(shí)，只需選擇一個(gè)操作算子，與局部搜索階段不同的是，操作算子隨機(jī)選擇路徑和節(jié)點(diǎn)進(jìn)行操作，而不是遍歷，當(dāng)找到一個(gè)可行解時(shí)即可結(jié)束擾動(dòng)階段。

2.6 算法框架

GVNS算法流程如表3所示，GVNS在定義了鄰域結(jié)構(gòu)Nk和Nl后（第1行），利用啟發(fā)式規(guī)則生成初始解s0，并將其傳遞給當(dāng)前解s（第2行），然后進(jìn)行初始化操作（第3行）。隨后開始迭代搜索，在擾動(dòng)階段找到一個(gè)可行解s′后（第5行），帶著該可行解s′進(jìn)入局部搜索階段（第6行）。在局部搜索階段，通過目標(biāo)函數(shù)值的大小評價(jià)解的質(zhì)量。目標(biāo)函數(shù)值越小，表示解的質(zhì)量越好。如果找到的局部最優(yōu)解s″優(yōu)于可行解s′，則將s′替換為s″。結(jié)束局部搜索階段后，需要判斷找到的局部最優(yōu)解s′是否優(yōu)于當(dāng)前解s （第7行）。如果是，則將s替換為s′，并且依然使用擾動(dòng)階段定義的第一個(gè)鄰域結(jié)構(gòu)進(jìn)行擾動(dòng)操作（第8行），否則進(jìn)一步判斷是否繼續(xù)進(jìn)行迭代搜索。如果達(dá)到算法終止條件，則返回當(dāng)前最優(yōu)解s （第10—17行）。算法的終止條件為當(dāng)前解連續(xù)Inip次迭代仍未能得到改善（第11行），若滿足該條件，則立即終止算法并輸出當(dāng)前最優(yōu)解。在GVNS算法中，設(shè)置Inip=10。需要特別說明的是，達(dá)到最大未優(yōu)化迭代次數(shù)Inip是指連續(xù)擾動(dòng)了Inip次，且每次擾動(dòng)后都會(huì)經(jīng)歷局部搜索階段，但當(dāng)前解都未得到改善。

3 算例分析

通過一系列的算例數(shù)值實(shí)驗(yàn)驗(yàn)證所提出的GVNS算法的性能，算法由Python語言實(shí)現(xiàn)，在配置為AMD Ryzen 5-4600U with Radeon Graphics CPU @ 2.10 GHz，16.0 GB的個(gè)人電腦上運(yùn)行。為了對比所提出GVNS算法的性能，文獻(xiàn)[11]中提到的混合整數(shù)規(guī)劃（mixed integer programming，MIP）模型和約束規(guī)劃（constraint programming，CP）模型也被用于求解算例。在算例分析中，MIP采用Gurobi求解器求解，CP采用CPLEX Optimization Studio 12.10.0中的CP Optimizer求解。引入相對百分比偏差（relative percentage difference，RPD）分析算法的性能，RPD計(jì)算公式如下：

RPD=Ccurrent-CbestCbest×100%。（2）

式中：Ccurrent表示當(dāng)前方法求得的目標(biāo)值，Cbest為該算例在所有方法中取得的最優(yōu)目標(biāo)值。RPD值越小，表示該方法求解效果越好。

3.1 算例設(shè)計(jì)

算例生成采用文獻(xiàn)[11]所述方法，分為小規(guī)模算例和大規(guī)模算例。針對小規(guī)模算例，設(shè)置包裹數(shù)n={8，10，14};針對大規(guī)模算例，設(shè)置包裹數(shù)n={50，100，200}。表4為算例中包裹數(shù)與AGV數(shù)的關(guān)系，可以得到18組不同規(guī)模的算例，每組隨機(jī)生成4個(gè)算例，共計(jì)72個(gè)。

3.2 參數(shù)調(diào)試

參數(shù)設(shè)置會(huì)直接影響算法效果，不同權(quán)重α取值的Rinit均值圖見圖12。在本文所提的GVNS算法中，權(quán)重α作為唯一變量需要進(jìn)行參數(shù)調(diào)試。在此，考慮不同的取值水平：0，0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9，1。選擇包裹數(shù)n=50，AGV數(shù)m取值{5，6，7，8，9，10，11，12，13，14，15}的11個(gè)大規(guī)模算例來調(diào)試權(quán)重α的取值。

權(quán)重α只會(huì)影響初始解，因此需觀察初始解目標(biāo)函數(shù)值的大小。為了簡化數(shù)據(jù)量，取所有算例在某一α值下初始解目標(biāo)函數(shù)值的平均值Rinit，Rinit值越小，表示初始解的質(zhì)量越好。由圖12可知，每個(gè)α的取值點(diǎn)均對應(yīng)參數(shù)測試算例集的平均值;從圖12中還可以看出，當(dāng)α為0.9時(shí)，Rinit值最小，因此設(shè)置權(quán)重α值為0.9。

3.3 計(jì)算結(jié)果與分析

將Gurobi和CP Optimizer的最大求解時(shí)間設(shè)置為1 800 s，若在給定時(shí)間內(nèi)未找到最優(yōu)解，則停止計(jì)算并返回當(dāng)前的最好可行解。GVNS算法的求解性能用RPD值進(jìn)行評價(jià)，此外，計(jì)算時(shí)間也作為求解性能評價(jià)指標(biāo)。為了消除啟發(fā)式算法可能存在的隨機(jī)性影響，GVNS算法對每個(gè)算例計(jì)算10次，然后取平均計(jì)算時(shí)間和平均RPD值。表5給出了小規(guī)模算例的計(jì)算結(jié)果，大規(guī)模算例的計(jì)算結(jié)果如表6所示，其中“J”表示包裹數(shù)量，“V”表示AGV數(shù)量，“No.”表示該組算例序號，“MIN”表示該算例求得的最小目標(biāo)函數(shù)值，“—”表示未在規(guī)定時(shí)間內(nèi)找到可行解。每個(gè)方法均列出了計(jì)算時(shí)間和RPD，對比小規(guī)模算例和大規(guī)模算例分別在MIP模型、CP模型和GVNS算法中的計(jì)算結(jié)果。

從表5可以看出，與啟發(fā)式方法相比，精確算法仍存在明顯的差距。MIP模型有8個(gè)算例未能找到最優(yōu)解，CP模型有9個(gè)算例未能找到最優(yōu)解，而GVNS僅有1個(gè)算例未能找到最優(yōu)解。從計(jì)算時(shí)間上來看，GVNS平均計(jì)算時(shí)間僅為0.42 s，遠(yuǎn)小于MIP和CP的計(jì)算時(shí)間。從求解質(zhì)量上來看，GVNS的平均RPD值僅為0.09，也遠(yuǎn)小于另外2個(gè)模型的RPD值。由小規(guī)模算例計(jì)算結(jié)果可知，GVNS在計(jì)算時(shí)間和求解質(zhì)量上都具有明顯優(yōu)勢。

由表6可知，由于本問題的NP-hard特性，當(dāng)包裹數(shù)為50時(shí)，MIP模型和CP模型還有部分算例能找到最優(yōu)解或近似解，但當(dāng)包裹數(shù)達(dá)到100及以上時(shí)，MIP模型和CP模型在所有算例中均無法在1 800 s內(nèi)找到可行解，可見優(yōu)化求解器無法求解大規(guī)模問題。而GVNS在所有大規(guī)模算例中均能在較短時(shí)間內(nèi)求得近似最優(yōu)解，平均計(jì)算時(shí)間僅為532.78 s，明顯優(yōu)于MIP模型和CP模型。由此可知，GVNS可以有效解決分揀中心考慮充電需求和硬時(shí)間窗的大規(guī)模多AGV調(diào)度問題。

3.4 AGV配置分析

不同配置的AGV會(huì)有不同的充電速率，配置越高充電率越大，即充電速度越快。不同的AGV充電率會(huì)導(dǎo)致AGV充電所需時(shí)間不同，從而影響分揀完成時(shí)間。此外，在一定分揀作業(yè)量下，不同AGV數(shù)量配置同樣會(huì)影響分揀完成時(shí)間。對于企業(yè)而言，AGV的配置越高，采購成本就越高，但如果AGV的配置過低，又會(huì)導(dǎo)致分揀任務(wù)無法按時(shí)完成或分揀效率過低。因此，找到合適的AGV充電率配置和數(shù)量配置對于物流中心來說是非常有必要的。本文以包裹數(shù)n=100，AGV數(shù)m=10的算例來分析不同的AGV充電率對分揀完成時(shí)間的影響。以包裹數(shù)n=100，AGV數(shù)m={10，12，14，16，18，20}的算例來分析AGV數(shù)量對分揀完成時(shí)間的影響。由于算例規(guī)模較大，因此使用GVNS算法進(jìn)行求解。為了簡化數(shù)據(jù)量，同時(shí)消除算法隨機(jī)性帶來的影響，每個(gè)算例都要計(jì)算10次，然后取分揀完成時(shí)間的平均值。

圖13為不同的AGV充電率與分揀完成時(shí)間關(guān)系折線圖。從圖13可以看出，當(dāng)充電率大于1.6時(shí)，分揀完成時(shí)間不再明顯減少，因此當(dāng)包裹數(shù)為100，AGV數(shù)為10時(shí)，最合適的AGV充電率為1.6。圖14是不同AGV數(shù)量配置與分揀完成時(shí)間關(guān)系折線圖。由圖14可知，當(dāng)AGV數(shù)量大于22時(shí)，分揀完成時(shí)間不再發(fā)生變化。因此，當(dāng)包裹數(shù)為100時(shí)，最多只需配置22輛AGV。當(dāng)AGV數(shù)量大于14時(shí)，分揀完成時(shí)間不再明顯減少，因此，當(dāng)包裹數(shù)為100時(shí)，最合適的AGV數(shù)量配置為14輛。

4 結(jié) 語

1）為了提高物流分揀中心的作業(yè)效率，在考慮充電需求和時(shí)間窗約束的基礎(chǔ)上，研究了大規(guī)模作業(yè)場景下的多AGV調(diào)度優(yōu)化問題。

2）基于所研究問題的復(fù)雜性，提出利用GVNS實(shí)現(xiàn)對大規(guī)模算例的有效求解。在GVNS算法的基本框架下，結(jié)合問題特性，設(shè)計(jì)了滿足時(shí)間窗約束的啟發(fā)式方法生成初始解，并為算法設(shè)計(jì)了10個(gè)鄰域操作算子，生成局部最優(yōu)解。

3）使用不同規(guī)模的算例進(jìn)行數(shù)值實(shí)驗(yàn)，并與混合整數(shù)規(guī)劃模型和約束規(guī)劃模型進(jìn)行對比，計(jì)算結(jié)果驗(yàn)證了所提出的GVNS算法求解大規(guī)模問題的可行性和高效性?？紤]到不同的AGV充電率和數(shù)量配置會(huì)影響多AGV的調(diào)度方案，采用控制變量法分別分析了不同的AGV充電率和數(shù)量配置下的分揀完成時(shí)間，并給出了合理的配置方案。

本文僅考慮分揀中心有一個(gè)充電區(qū)的情況，在實(shí)際應(yīng)用場景中，當(dāng)分揀場地很大且AGV數(shù)量很多時(shí)，AGV需要頻繁地返回充電區(qū)充電，合理的充電區(qū)布局方案是一個(gè)值得深入研究的問題。實(shí)際AGV分揀過程中還有很多問題需要考慮，例如AGV充電和放電的規(guī)律、AGV速度變化和AGV故障停機(jī)等。目前有關(guān)此方面的研究數(shù)據(jù)尚未見公開報(bào)道，筆者也在嘗試通過實(shí)驗(yàn)獲得真實(shí)的運(yùn)行數(shù)據(jù)，以使所討論的算法更具實(shí)際應(yīng)用價(jià)值。此外，在未來的研究中，還可通過仿真分析探討更多的不確定情況，譬如單個(gè)AGV的意外故障或包裹的緊急分揀作業(yè)等;同時(shí)還需對諸如遺傳算法、自適應(yīng)大規(guī)模鄰域搜索等算法之間的性能進(jìn)行對比分析的相關(guān)工作。

參考文獻(xiàn)/References：

[1] WEIDINGER F，BOYSEN N，BRISKORN D.Storage assignment with rack-moving mobile robots in KIVA warehouses[J].Transportation Science，2018，52（6）：1297-1588.

[2] 沈博聞，于寧波，劉景泰.倉儲(chǔ)物流機(jī)器人集群的智能調(diào)度和路徑規(guī)劃[J].智能系統(tǒng)學(xué)報(bào)，2014，9（6）：659-664.

SHEN Bowen，YU Ningbo，LIU Jingtai.Intelligent scheduling and path planning of warehouse mobile robots[J].CAAI Transactions on Intelligent Systems，2014，9（6）：659-664.

[3] FRAGAPANE G，de KOSTER R，SGARBOSSA F，et al.Planning and control of autonomous mobile robots for intralogistics：Literature review and research agenda[J].European Journal of Operational Research，2021，294（2）：405-426.

[4] da COSTABARROS? R，NASCIMENTO T P.Robotic mobile fulfillment systems：A survey on recent developments and research opportunities[J].Robotics and Autonomous Systems，2021，137：103729.

[5] 岳笑含，許曉健，王溪波.面向FMS基于改進(jìn)的混合PSO-GA的多AGV調(diào)度算法研究[J].計(jì)算機(jī)科學(xué)，2018，45（Z2）：167-171.

YUE Xiaohan，XU Xiaojian，WANG Xibo.Research on muti-AGV sechduling algorithm based on improved hybrid PSO-GA for FMS[J].Computer Science，2018，45（Z2）：167-171.

[6] 余娜娜，李鐵克，王柏琳，等.自動(dòng)化分揀倉庫中多AGV調(diào)度與路徑規(guī)劃算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2020，26（1）：171-180.

YU Nana，LI Tieke，WANG Bailin，et al.Multi-AGVs scheduling and path planning algorithm in automated sorting warehouse[J].Com-puter Integrated Manufacturing Systems，2020，26（1）：171-180.

[7] JUN S，LEE S，YIH Y.Pickup and delivery problem with recharging for material handling systems utilising autonomous mobile robots[J].European Journal of Operational Research，2021，289（3）：1153-1168.

[8] POLTEN L，EMDE S.Scheduling automated guided vehicles in very narrow aisle warehouses[J].Omega，2021，99：102204.

[9] ULJ I，SALEWSKI H，GOEKE D，et al.Order batching and batch sequencing in an AMR-assisted picker-to-parts system[J].European Journal of Operational Research，2021.doi：10.1016/j.ejor.2021.05.033.

[10]陳敏，黎展滔，陳慶新，等.考慮有限物流運(yùn)輸能力的智能車間AGV調(diào)度算法研究[J].工業(yè)工程，2019，22（4）：49-57.

CHEN Min，LI Zhantao，CHEN Qingxin，et al.AGV scheduling algorithm of intelligent workshop considering limited logistics transportation capacity[J].Industrial Engineering Journal，2019，22（4）：49-57.

[11]陳香玲，郭鵬，溫昆，等.考慮充電需求和時(shí)間窗的多AGV調(diào)度優(yōu)化建模[J].河北科技大學(xué)學(xué)報(bào)，2021，42（2）：91-100.

CHEN Xiangling，GUO Peng，WEN Kun，et al.Optimized mathematical models for multi-AGV scheduling problem with charging requirements and time windows[J].Journal of Hebei University of Science and Technology，2021，42（2）：91-100.

[12]范厚明，劉鵬程，吳嘉鑫，等.集貨需求隨機(jī)的同時(shí)配集貨VRP及混合變鄰域搜索算法[J].系統(tǒng)工程理論與實(shí)踐，2019，39（10）：2646-2659.

FAN Houming，LIU Pengcheng，WU Jiaxin，et al.Hybrid genetic algorithm with variable neighborhood descent for the vehicle routing problem with simultaneous stochastic pickup and deterministic delivery[J].Systems Engineering：Theory & Practice，2019，39（10）：2646-2659.

[13]WU X Q，CHE A.Energy-efficient no-wait permutation flow shop scheduling by adaptive multi-objective variable neighborhood search[J].Omega，2020，94：102117.

[14]徐立云，程贊，宓宏，等.基于改進(jìn)變鄰域搜索算法的成型機(jī)分批重調(diào)度優(yōu)化[J].同濟(jì)大學(xué)學(xué)報(bào)（自然科學(xué)版），2020，48（10）：1460-1469.

XU Liyun，CHENG Zan，MI Hong，et al.Molding machines batch rescheduling optimization based on improved variable neighborhood search[J].Journal of Tongji University（Natural Science），2020，48（10）：1460-1469.

[15]CUI L Q，LIU X B，LU S J，et al.A variable neighborhood search approach for the resource-constrained multi-project collaborative scheduling problem[J].Applied Soft Computing，2021，107：107480.

[16]HERRN A，MANUEL C J，DUARTE A.An efficient variable neighborhood search for the space-free multi-row facility layout problem[J].European Journal of Operational Research，2021，295（3）：893-907.

[17]HOOGERVORST R，DOLLEVOET T，MARTI G，et al.A variable neighborhood search heuristic for rolling stock rescheduling[J].EURO Journal on Transportation and Logistics，2021，10：100032.

[18]SADATI M E H，ATAY B.A hybrid variable neighborhood search approach for the multi-depot green vehicle routing problem[J].Transportation Research Part E：Logistics and Transportation Review，2021，149：102293.

[19]MLADENOVI N，HANSEN P.Variable neighborhood search[J].Computers & Operations Research，1997，24（11）：1097-1100.

[20]董紅宇，黃敏，王興偉，等.變鄰域搜索算法綜述[J].控制工程，2009，16（sup2）：1-5.

DONG Hongyu，HUANG Min，WANG Xingwei，et al.Review of variable neighborhood search algorithm[J].Control Engineering of China，2009，16（sup2）：1-5.

[21]MIKI M，TODOSIJEVI R，UROEVI D.Less is more：General variable neighborhood search for the capacitated modular hub location problem[J].Computers & Operations Research，2019，110：101-115.

[22]SONG X，JONES D，ASGARI N，et al.Multi-objective vehicle routing and loading with time window constraints： A real-life application[J].Annals of Operations Research，2020，291（1）：799-825.

[23]MLADENOVI N，UROEVI D，HANAFI S，et al.A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem[J].European Journal of Operational Research，2012，220（1）：270-285.

[24]de ARMAS J，MELIN-BATISTA B，MORENO-PREZ J A，et al.GVNS for a real-world rich vehicle routing problem with time windows[J].Engineering Applications of Artificial Intelligence，2015，42：45-56.