陳香玲 郭鵬 溫昆 裴霞

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

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

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

doi：10.7535/hbkd.2021yx02001

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

基金項(xiàng)目：國(guó)家自然科學(xué)基金（51405403）;國(guó)家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目（2020YFB1712200）

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

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

陳香玲，郭鵬，溫昆，等.考慮充電需求和時(shí)間窗的多AGV調(diào)度優(yōu)化建模.河北科技大學(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.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

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

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

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

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

1 問(wèn)題描述

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

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

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

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

1）當(dāng)AGV運(yùn)送一個(gè)包裹時(shí)，會(huì)選擇最短路徑，最短路徑距離由AGV的起點(diǎn)和終點(diǎn)用曼哈頓距離唯一確定;

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

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

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

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

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

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

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

2.1 MIP模型

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

N為任務(wù)集合，N={1，2…，n};N+：N+=N∪{0，n+1}，0和n+1分別表示虛擬開(kāi)始任務(wù)和虛擬結(jié)束任務(wù);K為AGV集合，K={1，2，…，m};Q為AGV的最大電池電量;g為AGV的安全電量;μ為AGV充電率;κ為AGV電量消耗率;M為一個(gè)足夠大的數(shù);tij 為從任務(wù)i的投放口到任務(wù)j的分揀臺(tái)所需的時(shí)間，若i=0或n+1，則對(duì)應(yīng)的點(diǎn)為充電區(qū)，因此t0，j表示從充電區(qū)到任務(wù)j的分揀臺(tái)所需的時(shí)間，ti，n+1表示從任務(wù)i的投放口到充電區(qū)所需的時(shí)間;hi為從任務(wù)i的分揀臺(tái)到任務(wù)i的投放口所需的時(shí)間，當(dāng)任務(wù)i為虛擬開(kāi)始（結(jié)束）任務(wù)時(shí)，hi則為零;Cmax為分揀作業(yè)周期，即最大完工時(shí)間;ei為任務(wù)i到達(dá)分揀臺(tái)的時(shí)間;di為任務(wù)i的最晚完工時(shí)間;ski為任務(wù)i開(kāi)始被AGVk執(zhí)行的時(shí)間;rki為AGVk完成任務(wù)i后的剩余電量;bki為AGVk完成任務(wù)i后去充電區(qū)并充滿電所需的時(shí)間;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）表示最小化最大完工時(shí)間，約束（2）和（3）表示每個(gè)任務(wù)都必須被執(zhí)行且只能被1輛AGV執(zhí)行1次;約束（4）表示對(duì)任意AGV和非虛擬任務(wù)，應(yīng)滿足任務(wù)網(wǎng)絡(luò)流約束;約束（5）和約束（6）分別表示每輛AGV都要從虛擬起點(diǎn)出發(fā)，最后返回虛擬終點(diǎn);約束（7）使最大完工時(shí)間大于或等于任何一次搬運(yùn)任務(wù)的完成時(shí)間;約束（8）表示如果AGVk執(zhí)行完任務(wù)i后執(zhí)行任務(wù)j，且在執(zhí)行完任務(wù)i時(shí)電量充足（即：xkij=1且zki=0），則任務(wù)i，j的開(kāi)始執(zhí)行時(shí)間滿足skj≥ski+hi+tij;約束（9）表示如果AGVk執(zhí)行完任務(wù)i后執(zhí)行任務(wù)j，且在執(zhí)行完任務(wù)i時(shí)電量不足（即：xkij=1且zki=1），則任務(wù)i，j的開(kāi)始執(zhí)行時(shí)間滿足skj≥ski+hi+bki+t0，j;約束（10）表示每個(gè)任務(wù)的開(kāi)始執(zhí)行時(shí)間要晚于其最早可被執(zhí)行的時(shí)間;約束（11）表示每個(gè)任務(wù)的完工時(shí)間不能晚于其最晚完工時(shí)間;約束（12）為AGV電量約束;約束（13）表示AGVk在完成任務(wù)i后若需要充電，則去到充電區(qū)并充滿電所需的時(shí)間;約束（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后無(wú)需充電（即：xkij=1且zki=0），則執(zhí)行完任務(wù)j后的電量。

2.2 CP模型

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

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

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

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

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

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

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

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

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

9）heightAtStart（α，f）：區(qū)間變量α在其開(kāi)始時(shí)間點(diǎn)對(duì)基本累積函數(shù)f的影響。

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

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

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

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

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

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

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

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ù)值算例分析

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 AGV配置分析

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

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

3.4 拓展分析

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

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

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

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

2）該文獻(xiàn)中在目標(biāo)函數(shù)中額外考慮了最小化車輛數(shù)和耗電量。在實(shí)際應(yīng)用場(chǎng)景中，分揀中心的主要目標(biāo)是在盡可能短的時(shí)間內(nèi)分揀完所有的包裹，并且保證所有的包裹能夠在其最晚分揀完成時(shí)間之前送達(dá)對(duì)應(yīng)的投放口。因此本文未在目標(biāo)函數(shù)中考慮這2個(gè)因素，但本文提出的CP模型具有良好的可拓展性，若需要加入最小化車輛數(shù)和耗電量，僅需對(duì)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充電時(shí)增加的電量;Qkn+1表示AGVk完成所有任務(wù)后回到充電區(qū)的剩余電量，每輛車消耗的電量由初始電量、最終剩余電量和充電所得電量求得。因此，∑k∈K（Q-Qkn+1+∑i∈Nlength_of（Cki））表示所有車輛的總耗電量。

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

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

4 結(jié) 語(yǔ)

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

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

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

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

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

[1] 李明，吳耀華，吳穎穎，等.人工與自動(dòng)化雙分揀區(qū)系統(tǒng)品項(xiàng)分配優(yōu)化[J].機(jī)械工程學(xué)報(bào)，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].運(yùn)籌與管理，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].計(jì)算機(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]余娜娜，李鐵克，王柏琳，等.自動(dòng)化分揀倉(cāng)庫(kù)中多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].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]周小凡，萇道方，余芳，等.考慮充電和等待時(shí)間的集裝箱碼頭AGV調(diào)度[J].上海海事大學(xué)學(xué)報(bào)，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]張亞琦，楊斌，胡志華，等.自動(dòng)化碼頭AGV充電與作業(yè)的集成調(diào)度研究[J].計(jì)算機(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é)報(bào)（自然科學(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.