考慮充電需求和時間窗的多AGV調度優化建模

陳香玲 郭鵬 溫昆 裴霞

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

關鍵詞：物流系統管理;多AGV調度;充電需求;時間窗;約束規劃

中圖分類號：F252.1; TP23 文獻標識碼：A

doi：10.7535/hbkd.2021yx02001

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

基金項目：國家自然科學基金（51405403）;國家重點研發計劃項目（2020YFB1712200）

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

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

陳香玲，郭鵬，溫昆，等.考慮充電需求和時間窗的多AGV調度優化建模.河北科技大學學報，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

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

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

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

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

1 問題描述

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

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

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

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

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

2）每輛AGV從充電區出發時都為滿電量狀態;

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

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

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

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

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

2 數學模型

2.1 MIP模型

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

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

建立的混合整數規劃模型如下：

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）

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

2.2 CP模型

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

1）intervaLVar（s，e，l，）：區間變量，表示執行某個任務的時間間隔，其中s，e，l分別表示任務的開始時間、結束時間和持續時間，參數表示該任務是否存在是可選的。

2）sequenceVar（{α1，α2，…，αn}）：序列變量，由一組區間變量α組成，表示一組待執行的任務序列。

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

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

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

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

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

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

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

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

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

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

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

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

建立的約束規劃模型如下所示：

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）

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

由于函數stepAtStart（α，h）中的高度h必須是一個整數或2個整數組成的區間，而每個任務對AGV電量的影響值tPrevSk（i），i和length（Cki）是變量，所以CP Optimizer暫不支持此類型參數。為了解決這一問題，可以通過使用函數heightAtStart（α，f）給定區間變量α對累積函數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 數值算例分析

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

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

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

3.1 算例設計

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

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

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

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

3.2 計算結果與分析

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

表1給出了小規模算例的計算結果。從表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模型未能在規定時間內找到最優解，而CP模型卻在極短時間內找到了最優解。由以上3點可以看出，相較于MIP模型，同為精確算法的CP模型在各方面的求解性能更優。

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

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

3.3 AGV配置分析

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

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

3.4 拓展分析

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

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

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

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

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

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

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

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

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

4 結 語

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

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

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

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

參考文獻/References：

[1] 李明，吳耀華，吳穎穎，等.人工與自動化雙分揀區系統品項分配優化[J].機械工程學報，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的“貨到人”訂單揀選系統任務調度研究[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]賀學成，呂淑靜，呂岳.高密集度AGV快遞包裹分揀系統的路徑規劃[J].計算機系統應用，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調度與路徑規劃算法[J].計算機集成制造系統，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調度[J].上海海事大學學報，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充電與作業的集成調度研究[J].計算機工程與應用，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]孟磊磊，張超勇，邵新宇，等.基于約束規劃的焊接車間多資源約束調度研究[J].華中科技大學學報（自然科學版），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.