考慮充電需求和時間窗的多AGV調(diào)度優(yōu)化建模

陳香玲 郭鵬 溫昆 裴霞

摘 要：為了提高自動引導(dǎo)小車 （automatic guided vehicle，AGV）在物流分揀中心的分揀效率，考慮采用純電力驅(qū)動的AGV分揀過程存在電量消耗和充電需求的特性，提出了一種優(yōu)化模型。在考慮AGV剩余電量和包裹時間窗等約束條件的基礎(chǔ)上，建立了以最小化分揀作業(yè)周期為目標(biāo)的混合整數(shù)規(guī)劃（MIP）模型并提出了相應(yīng)的約束規(guī)劃（CP）模型，模型中使用區(qū)間變量表示任務(wù)的執(zhí)行情況，借助累積函數(shù)記錄電量的變化情況。計算結(jié)果表明，與MIP模型相比，CP模型擁有更好的求解性能。采用混合整數(shù)規(guī)劃與約束規(guī)劃構(gòu)建AGV調(diào)度模型，可以有效提高分揀效率，降低企業(yè)運營成本，并為考慮更多約束的AGV調(diào)度研究提供求解途徑。

關(guān)鍵詞：物流系統(tǒng)管理;多AGV調(diào)度;充電需求;時間窗;約束規(guī)劃

中圖分類號：F252.1; TP23 文獻標(biāo)識碼：A

doi：10.7535/hbkd.2021yx02001

收稿日期：2020-12-28;修回日期：2021-03-01;責(zé)任編輯：馮 民

基金項目：國家自然科學(xué)基金（51405403）;國家重點研發(fā)計劃項目（2020YFB1712200）

第一作者簡介：陳香玲（1996-），女，四川達州人，碩士研究生，主要從事運籌優(yōu)化方面的研究。

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

陳香玲，郭鵬，溫昆，等.考慮充電需求和時間窗的多AGV調(diào)度優(yōu)化建模.河北科技大學(xué)學(xué)報，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.Journal of Hebei University of Science and Technology，2021，42（2）：91-100.

Optimized mathematical models for multi-AGV scheduling problem with charging requirements and time windows

CHEN Xiangling1，2，GUO Peng1，2，WEN Kun1，2，PEI Xia1，2

（1.School of Mechanical Engineering， Southwest Jiaotong University， Chengdu，Sichuan 610031， China; 2.Technology and Equipment of Rail Transit Operation and Maintenance Key Laboratory of Sichuan Province， Chengdu， Sichuan 610031， China）

Abstract：In order to improve the sorting efficiency of automatic guided vehicle （AGV） in the logistics sorting center， an optimized model was proposed considering the characteristics of power consumption and charging demand in the sorting process of electric-driven AGVs. On the basis of considering of the AGVs remaining power and package delivery time window， a mixed integer programming （MIP） model with the minimization of the sorting operation cycle and a corresponding constrained programming （CP） model were formulated. In CP model， the interval variables were used to describe the performance of tasks and the change of electric quantity was recorded by using cumulative function. The computational results show that the CP model has better performance compared with the MIP model.Adopting mixed integer programming and constrained programming to formulate the AGV scheduling model can effectively improve the sorting efficiency，reduce the operating cost of enterprises， and provide an alternative solution for the AGV scheduling problem with more constraints.

Keywords：

logistics system management; multi-AGV scheduling; charging demand; time window; constrained programming

近年來，隨著各大電商的高速發(fā)展，包裹數(shù)量逐年增多，物流分揀中心對分揀解決方案的高效率和高柔性提出了更高要求。目前，電商物流分揀中心主要采用大型交叉帶分揀機和人機結(jié)合的模式[1]，雖具有較高的物流分揀效率，但是交叉帶分揀設(shè)備的大型化決定了分揀中心場地的大型化，極大制約了中小型物流分揀中心建設(shè)的推廣。小包裹、小型化的物流分揀應(yīng)用場景越來越廣，傳統(tǒng)的大型分揀設(shè)備難以適應(yīng)當(dāng)前物流公司小型化分揀的需求。在此背景下，AGV作為自動化現(xiàn)代物流設(shè)備兼具柔性、效率和成本優(yōu)勢，在物流分揀中心得到了越來越廣泛的應(yīng)用[2]。因此，如何提高多AGV調(diào)度的效率也逐漸成為研究熱點[3]。

雖然目前已有許多關(guān)于AGV調(diào)度的研究，但大多集中在制造[4]領(lǐng)域，特別是在柔性制造系統(tǒng)中的車間調(diào)度領(lǐng)域[5-7]。在物流分揀行業(yè)，多AGV調(diào)度問題的研究仍是一個新的趨勢。BOYSEN等[8]研究了一種特殊的基于零件到取料機倉庫的揀選訂單處理系統(tǒng)。為了提高自動化分揀倉庫中的分揀效率，袁瑞萍等[9]設(shè)計了改進共同進化遺傳算法;賀學(xué)成等[10]針對高密集度的AGV分揀場景，提出了可避免擁堵的CAA*算法;XING等[11]提出了一種新的禁忌搜索算法，該算法可以解決多輛AGV同時工作時可能產(chǎn)生的沖突問題;余娜娜等[12]綜合考慮了AGV調(diào)度和路徑規(guī)劃問題，設(shè)計了一種改進差分進化算法。

在以上多AGV調(diào)度研究中，AGV的電量消耗和充電需求始終是一個被忽略的問題，且現(xiàn)有的國內(nèi)外研究大多集中在傳統(tǒng)的調(diào)度問題，很少考慮充電需求。為了驗證考慮充電需求的必要性，MCHANEY[13]通過數(shù)值實驗驗證了各種電池使用方案對AGV的數(shù)量規(guī)劃、作業(yè)時間和調(diào)度優(yōu)化等方面的影響，提出若AGV為純電力驅(qū)動，則需要在實際作業(yè)中考慮其充電需求。隨后，一些研究開始增加AGV電量作為調(diào)度考慮的約束，但沒有考慮為AGV安排充電任務(wù)，部分研究中雖然存在電量限制，但只是使系統(tǒng)中的AGV在電量不足時無法參與后續(xù)任務(wù)[14-16]。近年來，周小凡等[17]研究了考慮AGV充電任務(wù)和充電等待時間的集裝箱碼頭多AGV調(diào)度問題，并建立了數(shù)學(xué)模型。張亞琦等[18]考慮了垂岸式集裝箱堆場布局和AGV 充電過程對實際作業(yè)的影響，并設(shè)計了遺傳算法。LIU等[19]將AGV的充電任務(wù)納入到任務(wù)調(diào)度優(yōu)化中，提出了無人倉庫中多AGV調(diào)度的多目標(biāo)數(shù)學(xué)模型，開發(fā)并集成了2種自適應(yīng)遺傳算法（AGA）和多自適應(yīng)遺傳算法（MAGA）。

基于以上分析發(fā)現(xiàn)，現(xiàn)有的研究大多忽略了AGV電量消耗這一現(xiàn)實因素，少數(shù)文獻考慮了電量消耗問題，但沒有考慮執(zhí)行充電任務(wù)對實際工作的影響。本文結(jié)合實際情況，不僅考慮了AGV的充電需求，還進一步加入了包裹的硬時間窗約束，以最小化分揀作業(yè)周期為優(yōu)化目標(biāo)，分別建立了混合整數(shù)規(guī)劃（mixed integer programming，MIP）模型和約束規(guī)劃（constraint programming，CP）模型。通過算例試驗結(jié)果，驗證了CP模型的有效性，通過對CP模型的可拓展性進行分析，表明了CP模型的靈活性。此外，還分析了不同AGV數(shù)量和充電率對優(yōu)化目標(biāo)的影響。

1 問題描述

物流分揀中心通常由入庫區(qū)、出庫區(qū)、分揀區(qū)等組成，而分揀區(qū)又由分揀臺、投放口、AGV充電區(qū)（停放區(qū)）等組成。本文借鑒文獻[19]中的分揀區(qū)布局方式，如圖1所示。在分揀區(qū)內(nèi)，來自不同地區(qū)的包裹入庫后隨著傳送帶到達各個分揀臺，AGV接收到搬運任務(wù)后前往包裹所在的分揀臺。AGV到達分揀臺后需要根據(jù)包裹上的運單信息，將其運送至對應(yīng)的投放口，每個投放口代表不同的配送地區(qū)。在投放口下方是漏斗和傳送帶，它們會收集包裹并將其運送至出庫區(qū)，在出庫區(qū)會有車輛進行下一階段的配送。

基于以上應(yīng)用場景，給定包裹集合N={1，2，…，n}，其中n為包裹總數(shù)。給定AGV集合K={1，2，…，m}，其中m為AGV數(shù)量。AGV在不工作時都停靠在充電區(qū)，當(dāng)接收到任務(wù)時，AGV從充電區(qū)出發(fā)前去搬運包裹。每個包裹i（i∈N）都有相應(yīng)的最早到達時間ei、搬運時間ti和最晚完工時間di。最晚完工時間di用于保證包裹分揀出庫后派送車輛的時間安排，因此每個包裹到達投放口的時間不能晚于該時間，否則將影響后續(xù)的車輛配送。

AGV搬運一個包裹通常需要經(jīng)歷3個階段：第1個階段是從當(dāng)前位置前往包裹所在的分揀臺，此時AGV處于空載階段;第2個階段是若AGV在ei之前到達分揀臺，存在等待階段，反之則不存在此階段;第3階段是AGV在分揀臺裝載包裹，運到對應(yīng)的投放口，此時是負載階段。每運送完一個包裹，AGV會檢查當(dāng)前電量是否低于安全電量g。當(dāng)電量充足時，AGV直接前往下一包裹所在分揀臺;當(dāng)電量不足時，AGV需要前往充電區(qū)充電，充電完成后再到下一包裹所在的分揀臺。如此反復(fù)，直至所有運輸任務(wù)執(zhí)行完畢，最后返回充電區(qū)。

本文模型存在的約束條件及假設(shè)如下：

1）當(dāng)AGV運送一個包裹時，會選擇最短路徑，最短路徑距離由AGV的起點和終點用曼哈頓距離唯一確定;

2）每輛AGV從充電區(qū)出發(fā)時都為滿電量狀態(tài);

3）AGV可以停留在裝卸位置（分揀臺/投放口）;

4）每輛AGV一次只能裝載一個包裹，即每輛AGV只能同時執(zhí)行一個包裹的運輸工作;

5）AGV的安全電量大于從任意投放口返回充電區(qū)所需的電量，以滿足AGV在執(zhí)行完搬運任務(wù)后有足夠的電量返回充電區(qū)充電;

6）每輛AGV的運輸效率相同，空載和負載的運行速度及耗電量不變;

7）不考慮AGV在運行過程中可能產(chǎn)生的沖突和每次裝卸包裹的時間。

2 數(shù)學(xué)模型

2.1 MIP模型

假設(shè)物流分揀中心共有n個包裹需要分揀，由m輛AGV共同工作來完成所有作業(yè)任務(wù)。本文以最小化分揀作業(yè)周期為目標(biāo)建立混合整數(shù)規(guī)劃模型，相關(guān)符號的定義如下所示。

N為任務(wù)集合，N={1，2…，n};N+：N+=N∪{0，n+1}，0和n+1分別表示虛擬開始任務(wù)和虛擬結(jié)束任務(wù);K為AGV集合，K={1，2，…，m};Q為AGV的最大電池電量;g為AGV的安全電量;μ為AGV充電率;κ為AGV電量消耗率;M為一個足夠大的數(shù);tij 為從任務(wù)i的投放口到任務(wù)j的分揀臺所需的時間，若i=0或n+1，則對應(yīng)的點為充電區(qū)，因此t0，j表示從充電區(qū)到任務(wù)j的分揀臺所需的時間，ti，n+1表示從任務(wù)i的投放口到充電區(qū)所需的時間;hi為從任務(wù)i的分揀臺到任務(wù)i的投放口所需的時間，當(dāng)任務(wù)i為虛擬開始（結(jié)束）任務(wù)時，hi則為零;Cmax為分揀作業(yè)周期，即最大完工時間;ei為任務(wù)i到達分揀臺的時間;di為任務(wù)i的最晚完工時間;ski為任務(wù)i開始被AGVk執(zhí)行的時間;rki為AGVk完成任務(wù)i后的剩余電量;bki為AGVk完成任務(wù)i后去充電區(qū)并充滿電所需的時間;xkij為0或1，若AGVk在完成任務(wù)i后執(zhí)行任務(wù)j則為1，否則為0;zki為0或1，若AGVk執(zhí)行完任務(wù)j后需要去充電則為1，否則為0。

建立的混合整數(shù)規(guī)劃模型如下：

Obj：

min Cmax。（1）

s.t.

∑k∈K∑j∈N+xkij=1， i∈N，（2）

∑k∈K∑i∈N+xkij=1， j∈N，（3）

∑i∈N+xkij-∑i∈N+xkji=0， j∈N， i≠j， k∈K，（4）

∑i∈N+xk0，i≤1， k∈K，（5）

∑i∈N+xki，n+1≤1， k∈K，（6）

Cmax≥ski+hi， i∈N， k∈K，（7）

skj+M（1-xkij）+M·zki≥ski+hi+tij， i，j∈N+， i≠j， k∈K，（8）

skj+M（1-xkij）+M（1-zki）≥ski+hi+bki+t0，j， i，j∈N+， i≠j， k∈K，（9）

ski≥ei， i∈N+， k∈K，（10）

ski+ti≤di， i∈N+， k∈K，（11）

g≤rki≤Q， i∈N+， k∈K，（12）

bki+M（1-zki）≥ti，n+1+μ（Q-rki+κ·ti，n+1）， i∈N+， k∈K，（13）

rkj≤Q-κ（t0，j+hj）+M（1-zki）+M（1-xkij）， i，j∈N+， i≠j， k∈K，（14）

rkj≤rki-κ（tij+hj）+M·zki+M（1-xkij）， i，j∈N+， i≠j， k∈K。（15）

目標(biāo)函數(shù)（1）表示最小化最大完工時間，約束（2）和（3）表示每個任務(wù)都必須被執(zhí)行且只能被1輛AGV執(zhí)行1次;約束（4）表示對任意AGV和非虛擬任務(wù)，應(yīng)滿足任務(wù)網(wǎng)絡(luò)流約束;約束（5）和約束（6）分別表示每輛AGV都要從虛擬起點出發(fā)，最后返回虛擬終點;約束（7）使最大完工時間大于或等于任何一次搬運任務(wù)的完成時間;約束（8）表示如果AGVk執(zhí)行完任務(wù)i后執(zhí)行任務(wù)j，且在執(zhí)行完任務(wù)i時電量充足（即：xkij=1且zki=0），則任務(wù)i，j的開始執(zhí)行時間滿足skj≥ski+hi+tij;約束（9）表示如果AGVk執(zhí)行完任務(wù)i后執(zhí)行任務(wù)j，且在執(zhí)行完任務(wù)i時電量不足（即：xkij=1且zki=1），則任務(wù)i，j的開始執(zhí)行時間滿足skj≥ski+hi+bki+t0，j;約束（10）表示每個任務(wù)的開始執(zhí)行時間要晚于其最早可被執(zhí)行的時間;約束（11）表示每個任務(wù)的完工時間不能晚于其最晚完工時間;約束（12）為AGV電量約束;約束（13）表示AGVk在完成任務(wù)i后若需要充電，則去到充電區(qū)并充滿電所需的時間;約束（14）表示如果AGVk執(zhí)行完任務(wù)i后執(zhí)行任務(wù)j，且在執(zhí)行完任務(wù)i后需要充電（即：xkij=1且zki=1），則執(zhí)行完任務(wù)j后的電量;約束（15）表示如果AGVk執(zhí)行完任務(wù)i后執(zhí)行任務(wù)j，且在執(zhí)行完任務(wù)i后無需充電（即：xkij=1且zki=0），則執(zhí)行完任務(wù)j后的電量。

2.2 CP模型

近年來，起源于人工智能研究領(lǐng)域的約束規(guī)劃技術(shù)在車輛路徑優(yōu)化[20-21]、車間作業(yè)調(diào)度[22-23]、任務(wù)計劃[24]等多種組合優(yōu)化問題中獲得了越來越多的關(guān)注和應(yīng)用。目前還沒有將CP應(yīng)用于分揀中心多AGV調(diào)度這一復(fù)雜問題，因此本文提出并建立CP模型，與傳統(tǒng)的混合整數(shù)規(guī)劃作對比。與混合整數(shù)規(guī)劃相比，CP關(guān)注的是約束條件和可行性，而不是目標(biāo)函數(shù)和最優(yōu)性。由于CP模型在不同的CP求解器中表示方法和建模方法均不一致，本文所建CP模型基于IBM ILOG CPLEX Optimization 12.10.0中的OPL 12.10.0語言實現(xiàn)，因此使用該語言的語法構(gòu)造，涉及的變量和約束的語法如下。

1）intervaLVar（s，e，l，）：區(qū)間變量，表示執(zhí)行某個任務(wù)的時間間隔，其中s，e，l分別表示任務(wù)的開始時間、結(jié)束時間和持續(xù)時間，參數(shù)表示該任務(wù)是否存在是可選的。

2）sequenceVar（{α1，α2，…，αn}）：序列變量，由一組區(qū)間變量α組成，表示一組待執(zhí)行的任務(wù)序列。

3）alternative（α，B）：若區(qū)間變量α存在，則集合B={α1，α2，...，αn}中有且僅有一個區(qū)間變量存在，且2個區(qū)間變量的開始時間和結(jié)束時間一致。

4）prev（seq，α1，α2）：若區(qū)間變量α1和α2均存在于序列變量seq中，則在seq中α1位于α2之前。

5）if_then（e1，e2）：若布爾表達式e1為真，則布爾表達式e2也為真。

6）presence_of（α）：若區(qū)間變量α存在，則返回1，否則返回0。

7）noOverlap（seq，T）：序列變量seq中的所有區(qū)間變量之間的時間間隔必須滿足轉(zhuǎn)移時間矩陣T，從而使得所有區(qū)間變量在時間上不會發(fā)生干擾。

8）stepAtStart（α，h）：基本累積函數(shù)，用來表示活動對資源的累積使用情況，α表示對資源量有影響的區(qū)間變量，h表示區(qū)間變量α在執(zhí)行過程中對資源量的影響值。

9）heightAtStart（α，f）：區(qū)間變量α在其開始時間點對基本累積函數(shù)f的影響。

10）alwaysln（f，α，min，max）：累積函數(shù)f在區(qū)間變量α的時間間隔內(nèi)時，其可能值始終限制在特定的范圍內(nèi)。此外，α也可以是一個時間區(qū)間。

11）first（seq，α）：若區(qū)間變量α存在于序列變量seq中，則它必須位于序列的首位。

12）last（seq，α）：若區(qū)間變量α存在于序列變量seq中，則它必須位于序列的末位。

在CP模型中，將所有的任務(wù)定義為具有開始時間、持續(xù)時間和結(jié)束時間的區(qū)間變量。表示搬運任務(wù)的區(qū)間變量Xi的持續(xù)時間l=hi，表示充電任務(wù)的區(qū)間變量Cki的持續(xù)時間l為最大電量與當(dāng)前電量的差值。由于AGV在每完成一個搬運任務(wù)后都需要檢查當(dāng)前電量是否低于安全電量，若當(dāng)前電量低于安全電量，則Cki存在，反之則不存在。任務(wù)序列中的每個區(qū)間變量之間存在時間間隔，從而確保了任意區(qū)間變量在時間上不會發(fā)生重疊，該時間間隔實際上是指tij。CP模型中部分參數(shù)與MIP模型中的定義相同，其他參數(shù)和變量的定義如下所示。

T為各個任務(wù)點之間的轉(zhuǎn)移時間矩陣，T=;H為一個足夠大的整數(shù)，表示計劃期長度，也是完工時間的上界;Xi為區(qū)間變量，表示搬運任務(wù)i;Xki為可選區(qū)間變量，表示任務(wù)i分配給AGVk來完成;Cki為可選區(qū)間變量，表示AGVk完成任務(wù)i后的充電任務(wù);Xk0為區(qū)間變量，表示AGVk的虛擬開始任務(wù);Xkn+1為區(qū)間變量，表示AGVk的虛擬結(jié)束任務(wù);Sk為序列變量，表示分配給AGVk的待執(zhí)行任務(wù)序列;Qk為匯總累積函數(shù)，表示AGVk在工作過程中的電量;Pki為累積函數(shù)，表示AGVk執(zhí)行任務(wù)i時消耗的電量;Rki為累積函數(shù)，表示AGVk執(zhí)行任務(wù)i后的充電任務(wù)時消耗的電量。

建立的約束規(guī)劃模型如下所示：

Obj：

min（max（endOf（Xi））），i∈N，（16）

s.t.

alternative（Xi，{X1i，X2i，...Xmi}），i∈N，（17）

prev（Sk，Xki，Cki），i∈N，k∈K，（18）

if_then（presence_of（Cki），presence_of（Xki）），i∈N，k∈K，（19）

noOverlap（Sk，T），k∈K，（20）

Qk=stepAtStart（Xk0，Q）-

∑i∈NstepAtStart（Xki，κ·（tPrevSk（i），i+hi））+

∑i∈NstepAtStart（Cki，（μ·length（Cki）-κ·ti，n+1）），k∈K，（21）

alwaysIn（Qk，，），k∈K，（22）

alwaysIn（Qk，Cki，），k∈K，（23）

first（Sk，Xk0）k∈K，（24）

last（Sk，Xkn+1），k∈K，（25）

Sk：sequenceVar（{Xk0，Xk1，...，Xkn+1}），k∈K，（26）

Xi：intervalVar（hi，，），i∈N，（27）

Xki：optlntervalVar（hi，，），i∈N，k∈K，（28）

Cki：optlntervalVar（，），i∈N，k∈K，（29）

Xk0：intervalVar（0，），k∈K，（30）

Xkn+1：intervalVar（0，），k∈K。（31）

上述模型中，目標(biāo)函數(shù)（16）表示最小化最大完工時間;約束（17）表示將每個搬運任務(wù)分配給一輛AGV;約束（18）確保對于給定的AGV在執(zhí)行完該搬運任務(wù)后若電量不足要去執(zhí)行充電任務(wù)，則該搬運任務(wù)和充電任務(wù)之間不能安排其他任務(wù);約束（19）表示若存在該充電任務(wù)，則在充電任務(wù)前的搬運任務(wù)也一定存在;約束（20）表示每輛AGV的任務(wù)序列在時間上無重疊，T為轉(zhuǎn)移時間矩陣，定義了序列中必須分隔2個連續(xù)區(qū)間的最小時間;約束（21）和（22）保證了每輛AGV的電量始終保持在可允許的范圍內(nèi)，其中κ·（tPrevSk（i），i+hi）表示AGV搬運任務(wù)對電量的負面影響，κ·ti，n+1表示AGV前往充電區(qū)對電量的負面影響，μ·length（Cki）表示AGV充電對電量的正面影響，三者都以累積函數(shù)表達式來表示;約束（23）表示AGV充電時會充到滿電量再出發(fā);約束（24）表示所有AGV都是從充電區(qū)出發(fā);約束（25）表示所有AGV最后都要回到充電區(qū);約束（26）—（31）定義了各個區(qū)間變量和序列變量。

由于函數(shù)stepAtStart（α，h）中的高度h必須是一個整數(shù)或2個整數(shù)組成的區(qū)間，而每個任務(wù)對AGV電量的影響值tPrevSk（i），i和length（Cki）是變量，所以CP Optimizer暫不支持此類型參數(shù)。為了解決這一問題，可以通過使用函數(shù)heightAtStart（α，f）給定區(qū)間變量α對累積函數(shù)f的電量影響值，因此需要將約束（21）等價替換為約束（32）—（36）便可解決該類問題。

Qk=stepAtStart（Xk0，Q）-∑i∈NPki+∑i∈NRki，k∈K，（32）

Pki=stepAtStart（Xki，（0，Q）），i∈N，k∈K，（33）

heightAtStart（Xki，Pki）=κ·（tPrevSk（i），i+hi），i∈N，k∈K，（34）

Rki=stepAtSate（Cki，（0，Q）），i∈N，k∈K，（35）

heightAtStart（Cki，Rki）=μ·length（Cki）-κ·ti，n+1，i∈N，k∈K。（36）

3 數(shù)值算例分析

針對混合整數(shù)規(guī)劃模型，使用8.1.1版本的Gurobi優(yōu)化求解器進行計算，對于約束規(guī)劃模型，使用IBM ILOG CPLEX Optimization Studio 12.10.0版本的CP Optimizer求解。2個模型均由Python語言實現(xiàn)，所有的算例運算在配置為AMD Ryzen 5-4600U with Radeon Graphics CPU @ 2.10 GHz，16.0 GB的個人電腦上運行。

為了便于分析算法的性能，本文引入相對百分比偏差（relative percentage difference，RPD）能更加直觀地對比試驗結(jié)果，其計算公式為RPD=Ccurent-CbestCbest×100%。（37）

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

3.1 算例設(shè)計

為驗證約束規(guī)劃模型的有效性，以圖2所示的分揀區(qū)規(guī)模為仿真實例，圖中分揀臺用白色長方塊表示，投放口用黑色小方塊表示，x和y軸上每單位表示2 m。任意位置都有其對應(yīng)的坐標(biāo)，例如：充電區(qū)的坐標(biāo)為（5，1），投放口6的坐標(biāo)為（7，2），分揀臺6的坐標(biāo)為（9，7），投放口42的坐標(biāo)為（8，12）。AGV每行駛一單位長度需要一單位時間，由此可以獲得任意點間的時間矩陣。

結(jié)合以上應(yīng)用場景數(shù)據(jù)，設(shè)計物流分揀中心多AGV調(diào)度問題的測試算例。首先，每個包裹的分揀點和投放點分別從整數(shù)均勻分布[1，8]和[1，56]中隨機選擇，由此可以獲得每個包裹的搬運時間ti。假設(shè)第k輛AGV的最早可用時間ak=0，AGV從當(dāng)前位置前往包裹i的分揀點所需時間的bi從整數(shù)均勻分布[2，20]中隨機選擇。然后，將任務(wù)先后分配給可用的AGV，保存每個包裹在初始調(diào)度中的開始搬運時間si=mink∈K{ak}+bi，并在每次分配后更新AGV的最早可用時間aargmink∈K{ak}=mink∈K{ak}+bi+ti。以上步驟生成了一個初始調(diào)度方案，以保證每個算例的可行性。

接下來，生成每個包裹的時間窗。對于每個包裹的時間窗大小αi從區(qū)間[2，3]中隨機選擇，從區(qū)間[0，1]中選擇一個隨機數(shù)βi，用于確定包裹i在時間窗內(nèi)的初始位置?？紤]到充電需求這一因素，為保證算例的可行性，需要在時間窗中考慮充電時間ci，該時間從整數(shù)均勻分布[100，120]中隨機選擇。最后，基于以上數(shù)據(jù)，生成每個包裹的時間窗上界ei=si-ti·（αi-1）·βi和時間窗下界di=si+ti·+ci。

將AGV電容量用單位電量表示，1個單位電量為1 AH。設(shè)置AGV的參數(shù)配置為最大電容量Q=100;安全電量g=20;充電率μ=1 AH/s，表示一單位時間可以充一個單位的電量;電量消耗率κ=1 AH/m，表示行駛一單位長度需要消耗一個單位的電量。算例分為小規(guī)模算例和大規(guī)模算例，針對小規(guī)模算例，設(shè)置為包裹數(shù)n={8，10，14}，AGV數(shù)m={2，3，4};針對大規(guī)模算例，設(shè)置包裹數(shù)n=50，AGV數(shù)m={10，15，20}?？梢缘玫讲煌?guī)模的算例12組，為每組隨機生成4個，共計48個算例。

3.2 計算結(jié)果與分析

在計算中，將Gurobi和CP Optimizer的最大求解時間均設(shè)置為1 800 s，若在給定時間內(nèi)未找到最優(yōu)解，則停止計算并返回當(dāng)前已知最優(yōu)可行解。表1和表2中J表示待搬運包裹數(shù)量，V表示AGV數(shù)量，No.表示該組算例的序號，MIN表示該算例求得的最小目標(biāo)函數(shù)值。每個方法均列出了目標(biāo)值、計算時間和RPD，對比了小規(guī)模算例和大規(guī)模算例分別在MIP模型和CP模型中的計算結(jié)果。

表1給出了小規(guī)模算例的計算結(jié)果。從表1中可以看到，2個模型在大部分算例中都能求得相同的解，這證明了MIP模型和CP模型的正確性。從計算時間上來看，CP模型在25個算例中的計算時間均小于MIP模型，且CP模型的平均計算時間為300.76 s，遠小于MIP模型的平均計算時間。從求解精度上來看，MIP模型的平均RPD值為2.78，而CP模型的平均RPD值為0.00。在算例10-2-4和14-2-1中，MIP模型未能在規(guī)定時間內(nèi)找到最優(yōu)解，而CP模型卻在極短時間內(nèi)找到了最優(yōu)解。由以上3點可以看出，相較于MIP模型，同為精確算法的CP模型在各方面的求解性能更優(yōu)。

大規(guī)模算例的計算結(jié)果如表2所示。由于本問題為NP-hard問題，當(dāng)包裹數(shù)為50時，MIP模型僅有4個算例能找到近似解，其余8個算例耗費了1 800 s仍不能找到可行解。而CP模型有9個算例能在短時間

內(nèi)找到最優(yōu)解，僅有2個算例在規(guī)定時間內(nèi)未能找到可行解。從計算時間上來看，CP模型的平均計算時間為495.75 s，遠小于MIP模型的平均計算時間，且在AGV數(shù)為15和20的所有算例中，CP模型的平均計算時間僅為23.87 s。由此可見，CP模型在解決分揀中心考慮充電需求和硬時間窗的大規(guī)模多AGV調(diào)度問題上更有優(yōu)勢。

3.3 AGV配置分析

充電率配置的不同將導(dǎo)致AGV充電速率不一樣，參數(shù)配置越高充電率越大，即充電速度越快。不同的AGV充電率會導(dǎo)致AGV充電所需時間不同，從而影響分揀的總完工時間。此外在一定的分揀作業(yè)量下，不同的AGV數(shù)量配置同樣會影響分揀完工時間。對于運營方而言，AGV的配置越高，其采購成本也就越高，但如果AGV的配置過低，又會導(dǎo)致分揀任務(wù)無法按時完成或分揀效率過低，因此找到合適的AGV充電率配置和數(shù)量配置對于物流收益有非常大的影響。本文以包裹數(shù)n=14，AGV數(shù)m=2的算例來分析不同AGV充電率對總完工時間的影響。以包裹數(shù)n=14，AGV數(shù)m={2，3，4，5，6，7}的算例來分析AGV數(shù)量對總完工時間的影響。

圖3為不同的AGV充電率與最大完工時間關(guān)系對比，橫坐標(biāo)為AGV充電率，縱坐標(biāo)為最大完工時間。從圖3可以看出，當(dāng)充電率大于1.6 C/s時，最大完工時間降幅明顯放緩，因此，最合適的AGV充電率為1.6 C/s。圖4是不同AGV數(shù)量配置與最大完工時間關(guān)系對比，橫坐標(biāo)為AGV數(shù)量，縱坐標(biāo)為最大完工時間。由圖4可見，當(dāng)AGV數(shù)量大于4時，最大完工時間不再發(fā)生變化?？梢缘贸?，當(dāng)包裹數(shù)為14時，最多只需配置4輛AGV。

3.4 拓展分析

本文參考了文獻[19]中的分揀區(qū)布局方式，該文獻考慮了搬運不同包裹時AGV采用不同的速度，AGV的電量消耗率也隨速度的變化而變化。在實際的分揀場景中，AGV的行駛速度會因為搬運包裹的重量不同而存在一定的差異，由于本文的應(yīng)用場景是分揀小型包裹，因此對微小的速度差異忽略不計，假定AGV速度不變。由于該文獻未說明AGV的行駛速度和電量消耗率的取值方式，因而本文無法使用其提供的數(shù)據(jù)進行計算后作對比分析。但本文提出的約束同樣可以適用于求解該文獻中的問題，考慮到部分因素的差異，需要做出如下拓展。

1）本文考慮了每個包裹的最晚分揀完成時間，而該文獻中未考慮這一重要因素，因此可以將最晚完工時間設(shè)為一個極大的數(shù)M，只需將CP模型中的約束（27）和（28）改為

Xi：intervalVar（hi，，），i∈N，

Xki：optlntervalVar（hi，，），i∈N，k∈K。

2）該文獻中在目標(biāo)函數(shù)中額外考慮了最小化車輛數(shù)和耗電量。在實際應(yīng)用場景中，分揀中心的主要目標(biāo)是在盡可能短的時間內(nèi)分揀完所有的包裹，并且保證所有的包裹能夠在其最晚分揀完成時間之前送達對應(yīng)的投放口。因此本文未在目標(biāo)函數(shù)中考慮這2個因素，但本文提出的CP模型具有良好的可拓展性，若需要加入最小化車輛數(shù)和耗電量，僅需對CP模型中的式（16）做如下調(diào)整：

min（∑k∈Kpresence_of（Xk0）+max（endOf（Xi））+∑k∈K（Q-Qkn+1+length_of（Cki））），i∈N。

調(diào)整后的目標(biāo)函數(shù)中的∑k∈Kpresence_of（Xk0）表示從充電區(qū)出發(fā)的AGV數(shù)量，即參與到分揀作業(yè)中的AGV數(shù)量;∑i∈Nlength_of（Cki）表示AGVk充電時增加的電量;Qkn+1表示AGVk完成所有任務(wù)后回到充電區(qū)的剩余電量，每輛車消耗的電量由初始電量、最終剩余電量和充電所得電量求得。因此，∑k∈K（Q-Qkn+1+∑i∈Nlength_of（Cki））表示所有車輛的總耗電量。

3）若需要考慮AGV搬運不同包裹時設(shè)置不同的行駛速度和電量消耗率，則只需將給定的行駛速度和電量消耗率設(shè)置為一定范圍內(nèi)的變量即可。

通過以上對CP模型的拓展操作，可以將其他約束集成到本文的調(diào)度問題中。由此說明提出的多AGV調(diào)度問題和解決方案模型具有高度的靈活性，可適用于考慮不同因素的多種場景。

4 結(jié) 語

1）為進一步縮短包裹的分揀時間并提高AGV的分揀效率，針對物流分揀中心包裹分揀過程，從AGV采用純電力驅(qū)動和包裹分揀完成后需進行下一步配送這2個實際情況出發(fā)，研究了帶有充電需求和硬時間窗約束的多AGV調(diào)度問題。

2）建立了考慮AGV搬運作業(yè)和充電需求的混合整數(shù)規(guī)劃模型，并提出將約束規(guī)劃技術(shù)應(yīng)用于解決這一復(fù)雜調(diào)度問題，使用區(qū)間變量表示任務(wù)執(zhí)行情況，借助累積函數(shù)更加直觀地表述電量的變化情況。

3）通過使用OPL高級建模語言建立，并利用CP Optimizer進行了求解。不同規(guī)模的算例結(jié)果表明，CP模型比MIP模型擁有更優(yōu)的求解性能。

4）本文基于混合整數(shù)規(guī)劃與約束規(guī)劃技術(shù)實現(xiàn)了物流分揀中心AGV調(diào)度優(yōu)化，但所構(gòu)建的模型在處理大規(guī)模算例時存在求解時間過長的問題，在未來的研究中有必要針對問題特性設(shè)計基于變鄰域搜索或群集智能優(yōu)化算法的啟發(fā)式調(diào)度策略。此外，關(guān)于AGV工作過程中自動處理路徑?jīng)_突的問題也值得思考，以保證調(diào)度系統(tǒng)能夠處理分揀過程中的實時信息，更貼近實際作業(yè)過程。

參考文獻/References：

[1] 李明，吳耀華，吳穎穎，等.人工與自動化雙分揀區(qū)系統(tǒng)品項分配優(yōu)化[J].機械工程學(xué)報，2015，51（10）：197-204.

LI Ming，WU Yaohua，WU Yingying，et al.Items assignment optimization for double picking zones with manual picking system and automated picking system [J].Journal of Mechanical Engineering，2015，51（10）：197-204.

[2] ZHAN M，YU K.Wireless communication technologies in automated guided vehicles：Survey and analysis[C]//IECON 2018-44th Annual Conference of the IEEE Industrial Electronics Society.Washington：IEEE，2018：4155-4161.

[3] BOYSEN N，DE KOSTER R，WEIDINGER F.Warehousing in the e-commerce era：A survey[J].European Journal of Operational Research，2019，277（2）：396-411.

[4] OYEKANLU E A，SMITH A C，THOMAS W P，et al.A review of recent advances in automated guided vehicle technologies：Integration challenges and research areas for 5G-based smart manufacturing applications[J].IEEE Access，2020，8：202312-202353.

[5] ZACHARIA P T，XIDIAS E K.AGV routing and motion planning in a flexible manufacturing system using a fuzzy-based genetic algorithm[J].The International Journal of Advanced Manufacturing Technology，2020，109（7/8）：1801-1813.

[6] MOHAMMADI E K，SHIRAZI B.Toward high degree flexible routing in collision-free FMSs through automated guided vehicles dynamic strategy：A simulation metamodel[J].ISA Transactions，2020，96：228-244.

[7] CHAWLA V K，CHANDA A K，ANGRA S，et al.Effect of nature-inspired algorithms and hybrid dispatching rules on the performance of automatic guided vehicles in the flexible manufacturing system [J].Journal of the Brazilian Society of Mechanical Sciences and Engineering，2019，41（10）：1-17.

[8] BOYSEN N，BRISKORN D，EMDE S.Parts-to-picker based order processing in a rack-moving mobile robots environment[J].European Journal of Operational Research，2017，262（2）：550-562.

[9] 袁瑞萍，王慧玲，孫利瑞，等.基于物流AGV的“貨到人”訂單揀選系統(tǒng)任務(wù)調(diào)度研究[J].運籌與管理，2018，27（10）：133-138.

YUAN Ruiping，WANG Huiling，SUN Lirui，et al.Research on the task scheduling of “goods to picker” order picking system based on logistics AGV[J].Operations Research and Management Science，2018，27（10）：133-138.

[10]賀學(xué)成，呂淑靜，呂岳.高密集度AGV快遞包裹分揀系統(tǒng)的路徑規(guī)劃[J].計算機系統(tǒng)應(yīng)用，2019，28（4）：39-44.

HE Xuecheng，LYU Shujing，LYU Yue.Path planning of high density AGV parcel sorting system[J].Computer Systems & Applications，2019，28（4）：39-44.

[11]XING L N，LIU Y Y，LI H Y，et al.A novel tabu search algorithm for multi-AGV routing problem[J].Mathematics，2020，8（2）：279.

[12]余娜娜，李鐵克，王柏琳，等.自動化分揀倉庫中多AGV調(diào)度與路徑規(guī)劃算法[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].Computer Integrated Manufacturing Systems，2020，26（1）：171-180.

[13]MCHANEY R.Modelling battery constraints in discrete event automated guided vehicle simulations[J].International Journal of Production Research，1995，33（11）：3023-3040.

[14]KARIMI B，NIAKI S T A，HALEH H，et al.Bi-objective optimization of a job shop with two types of failures for the operating machines that use automated guided vehicles[J].Reliability Engineering and System Safety，2018，175：92-104.

[15]AIZED T.Modelling and performance maximization of an integrated automated guided vehicle system using coloured Petri net and response surface methods[J].Computers & Industrial Engineering，2009，57（3）：822-831.

[16]MOUSAVI M，YAP H J，MUSA S N，et al.Multi-objective AGV scheduling in an FMS using a hybrid of genetic algorithm and particle swarm optimization[J].PLoS One，2017，12（3）：e0169817.

[17]周小凡，萇道方，余芳，等.考慮充電和等待時間的集裝箱碼頭AGV調(diào)度[J].上海海事大學(xué)學(xué)報，2019，40（3）：1-5.

ZHOU Xiaofan，CHANG Daofang，YU Fang，et al.Scheduling of AGV in container terminals considering charging and waiting time[J].Journal of Shanghai Maritime University，2019，40（3）：1-5.

[18]張亞琦，楊斌，胡志華，等.自動化碼頭AGV充電與作業(yè)的集成調(diào)度研究[J].計算機工程與應(yīng)用，2017，53（18）：257-262.

ZHANG Yaqi，YANG Bin，HU Zhihua，et al.Research of AGV charging and job integrated scheduling at automated container terminal[J].Computer Engineering and Applications，2017，53（18）：257-262.

[19]LIU Y，JI S，SU Z，et al.Multi-objective AGV scheduling in an automatic sorting system of an unmanned （intelligent） warehouse by using two adaptive genetic algorithms and a multi-adaptive genetic algorithm[J].PLoS One，2019，14（12）：e0226161.

[20]HAM A M.Integrated scheduling of m-truck，m-drone，and m-depot constrained by time-window，drop-pickup，and m-visit using constraint programming[J].Transportation Research Part C：Emerging Technologies，2018，91：1-14.

[21]SCHUIJBROEK J，HAMPSHIRE R C，van HOEVE W J.Inventory rebalancing and vehicle routing in bike sharing systems [J].European Journal of Operational Research，2017，257（3）：992-1004.

[22]HAM A.Transfer-robot task scheduling in flexible job shop [J].Journal of Intelligent Manufacturing，2020，31（7）：1783-1793.

[23]孟磊磊，張超勇，邵新宇，等.基于約束規(guī)劃的焊接車間多資源約束調(diào)度研究[J].華中科技大學(xué)學(xué)報（自然科學(xué)版），2018，46（6）：1-7.

MENG Leilei，ZHANG Chaoyong，SHAO Xinyu，et al.Constraint programming for multi-resource constrained welding shop scheduling[J].Journal of Huazhong University of Science and Technology （Natural Science Edition），2018，46（6）：1-7.

[24]BOOTH K E C，TRAN T T，NEJAT G，et al.Mixed-integer and constraint programming techniques for mobile robot task planning[J].IEEE Robotics and Automation Letters，2016，1（1）：500-507.