（北京機(jī)械工業(yè)自動(dòng)化研究所有限公司，北京 100120）

1 問(wèn)題的提出

根據(jù)有關(guān)部門(mén)的數(shù)據(jù)，我國(guó)2015年社會(huì)物流總費(fèi)用為10.8萬(wàn)億，占GDP總量的16.0%。顯然，從商業(yè)的角度出發(fā)，發(fā)展物流行業(yè)，提高效率，減少支出比單純地提高制造效率有著更重要的價(jià)值。倉(cāng)儲(chǔ)作為物流行業(yè)的一個(gè)重要環(huán)節(jié)很早就引起了重視。電子技術(shù)、電器技術(shù)、信息技術(shù)和機(jī)械設(shè)計(jì)制造的飛速發(fā)展使得一種新型的倉(cāng)儲(chǔ)方式——自動(dòng)化立體倉(cāng)庫(kù)（Automated Storage/Retrieval System，AV/RS）的出現(xiàn)變得理所應(yīng)當(dāng)。美國(guó)的Malmborg教授領(lǐng)導(dǎo)團(tuán)隊(duì)于2003年首先開(kāi)始了一種新型的自動(dòng)化立體倉(cāng)庫(kù)——自動(dòng)小車(chē)存取系統(tǒng)（Autonomous Vehicle Storage and Retrieval Systems，AVS/RS）（如圖1所示[1]）的研究。自動(dòng)小車(chē)存取系統(tǒng)可以極大地提高存取效率、滿足多種復(fù)雜的存取需求，自動(dòng)小車(chē)結(jié)構(gòu)示意圖如圖2所示。它還可以避免傳統(tǒng)堆垛機(jī)式自動(dòng)化立體倉(cāng)庫(kù)高耦合的缺點(diǎn)，極大地提高存取系統(tǒng)的柔性。因此，對(duì)AVS/RS的研究有著非常重要的意義。

圖1 自動(dòng)小車(chē)存取系統(tǒng)的立體示意圖

圖2 自動(dòng)小車(chē)結(jié)構(gòu)示意圖

當(dāng)前，國(guó)內(nèi)外關(guān)于AVS/RS的研究還處在起步階段。已有的研究主要集中如何建立AVS/RS的性能評(píng)估模型、減少阻塞或死鎖和AVS/RS的調(diào)度優(yōu)化。Heragu等[2]先用開(kāi)環(huán)排隊(duì)網(wǎng)絡(luò)（Open Queueing Network，OQN）對(duì)自動(dòng)小車(chē)存取系統(tǒng)進(jìn)行建模，然后用制造系統(tǒng)表現(xiàn)分析器（Manufacturing System Performance Analyzer，MPA）對(duì)一種AVS/RS配置進(jìn)行了出入庫(kù)效率分析。接著，他對(duì)多種配置的AVS/RS進(jìn)行了類(lèi)似的仿真研究。結(jié)果表明，當(dāng)自動(dòng)小車(chē)的利用率在60%到85%之間時(shí)，開(kāi)環(huán)排隊(duì)網(wǎng)絡(luò)可以有效地對(duì)自動(dòng)小車(chē)存取系統(tǒng)進(jìn)行出入庫(kù)效率分析。

Marchet等[3]同樣用開(kāi)環(huán)排隊(duì)網(wǎng)絡(luò)構(gòu)建了基于平均完成指令時(shí)間和等待時(shí)間等指標(biāo)的自動(dòng)小車(chē)存取系統(tǒng)評(píng)估模型。他們綜合了自動(dòng)小車(chē)和升降機(jī)（Lift）的速度與加速度以及各種類(lèi)型的貨格參數(shù)等情況，通過(guò)仿真證實(shí)了該模型的有效性。羅建[4]和吳長(zhǎng)慶[5]指出環(huán)路死鎖是AVS/RS中死鎖出現(xiàn)的主要類(lèi)型。該團(tuán)隊(duì)運(yùn)用著色賦時(shí)Petri網(wǎng)（Coloured Timed Petri Nets，CTPN）構(gòu)建了自動(dòng)小車(chē)存取系統(tǒng)的動(dòng)態(tài)模型。他們基于CTPN模型，使用有向工具構(gòu)建了防止環(huán)路死鎖的路線圖，給出了死鎖釋放的充分必要條件。文獻(xiàn)[6]和文獻(xiàn)[7]從儲(chǔ)位分配優(yōu)化的角度來(lái)提高自動(dòng)小車(chē)存取系統(tǒng)的出入庫(kù)效率。他們分別用離散粒子群算法、離散粒子群與模擬退火融合的算法建立了自動(dòng)小車(chē)存取系統(tǒng)的貨位優(yōu)化模型，并用仿真的方法驗(yàn)證了該方法的有效性。程志江等[8,9]基于模糊控制理論，對(duì)智能小車(chē)的控制系統(tǒng)進(jìn)行了研究。馮鋒等[10]為了讓自動(dòng)小車(chē)適應(yīng)不同場(chǎng)景的應(yīng)用，設(shè)計(jì)了自組織模糊控制器來(lái)優(yōu)化自動(dòng)小車(chē)的控制。

2 問(wèn)題的描述與建模

2.1 問(wèn)題的描述

根據(jù)自動(dòng)小車(chē)能否在升降機(jī)的協(xié)助下實(shí)現(xiàn)跨層作業(yè)，可將自動(dòng)小車(chē)存取系統(tǒng)分為單層作業(yè)的自動(dòng)小車(chē)存取系統(tǒng)和跨層作業(yè)的自動(dòng)小車(chē)存取系統(tǒng)。為了更加體現(xiàn)問(wèn)題的普遍性，本文選擇自動(dòng)小車(chē)可跨層且可在平面內(nèi)做二維運(yùn)動(dòng)的的自動(dòng)小車(chē)存取系統(tǒng)作為研究對(duì)象（在不作特殊說(shuō)明的情況下，下文所述自動(dòng)小車(chē)存取系統(tǒng)指的都是這種形式）。圖3為自動(dòng)小車(chē)存取系統(tǒng)水平剖面示意圖。如圖所示，網(wǎng)格線填充的矩形塊表示的是標(biāo)準(zhǔn)貨位，黑色填充矩形塊表示的是可運(yùn)輸自動(dòng)小車(chē)實(shí)現(xiàn)垂直運(yùn)動(dòng)的升降機(jī)，黑色填充的圓形塊則表示該層的I/O點(diǎn)（輸入或輸出點(diǎn)）。自動(dòng)小車(chē)可在空白的巷道自由運(yùn)行，并可在升降機(jī)的協(xié)助下完成跨層運(yùn)動(dòng)。

圖3 自動(dòng)小車(chē)存取系統(tǒng)水平剖面示意圖

自動(dòng)小車(chē)存取系統(tǒng)共有3種作業(yè)方式，分別為：?jiǎn)沃噶畛鰩?kù)方式，單指令入庫(kù)方式和雙指令出入庫(kù)復(fù)合作業(yè)方式。單指令出庫(kù)方式指的是AVS/RS在一段過(guò)程內(nèi)只完成出庫(kù)任務(wù)。單指令入庫(kù)方式指的是AVS/RS在一段過(guò)程內(nèi)只完成入庫(kù)任務(wù)。而，復(fù)合作業(yè)方式下，一個(gè)作業(yè)過(guò)程要完成出庫(kù)和入庫(kù)兩個(gè)任務(wù)，而每個(gè)任務(wù)都可能是跨層作業(yè)的。如圖4所示，復(fù)合作業(yè)方式下出庫(kù)貨位和入庫(kù)貨位是逐一交替進(jìn)行的。

圖4 復(fù)合方式下的作業(yè)流程

復(fù)合作業(yè)方式可以有效地縮短自動(dòng)小車(chē)和升降機(jī)的空載運(yùn)行時(shí)間，因此可以大大提高整個(gè)系統(tǒng)的出入庫(kù)效率[11]。本文接下來(lái)主要研究復(fù)合作業(yè)方式。

另外，自動(dòng)小車(chē)在水平面選擇不同的運(yùn)動(dòng)路徑也會(huì)造成任務(wù)完成時(shí)間的不同。假設(shè)平面上有兩個(gè)不重合的點(diǎn)，分別為點(diǎn)A和點(diǎn)B。理論上，A到B之間的路徑有無(wú)數(shù)條。實(shí)際上有兩類(lèi)路徑比較有代表性。如圖5所示，一類(lèi)是A到B之間的路徑與經(jīng)過(guò)A、B兩點(diǎn)的直線重合，即路徑2。路徑2的經(jīng)過(guò)的路程叫做點(diǎn)A與點(diǎn)B的歐氏距離。另一類(lèi)，路徑1和路徑3則代表著躲避規(guī)則分布障礙的路徑。容易證明，這類(lèi)路徑的路程都是相等的。這類(lèi)路徑所產(chǎn)生的距離可稱(chēng)為曼哈頓距離或出租車(chē)距離。在倉(cāng)庫(kù)的某一層內(nèi)，自動(dòng)小車(chē)需要在貨位、升降機(jī)電梯和I/O間運(yùn)動(dòng)。而這三者往往不是沿水平或垂直分布的，即將他們之間的距離簡(jiǎn)單地認(rèn)為是歐式距離是不合理的。即使只能沿水平和垂直分布的巷道運(yùn)行，在確定的兩點(diǎn)間，自動(dòng)小車(chē)的運(yùn)行路徑也存在無(wú)數(shù)條。其中，曼哈頓距離是最短的。因此，本文在計(jì)算自動(dòng)小車(chē)在水平運(yùn)行的最短路程時(shí)都采用曼哈頓距離。

圖5 兩節(jié)點(diǎn)間的多種路徑

此外，選擇不同的任務(wù)完成順序和在需要跨層作業(yè)時(shí)選擇不同的升降機(jī)都會(huì)影響訂單的完成總時(shí)間。本文調(diào)度優(yōu)化的目標(biāo)就是在復(fù)合作業(yè)方式下、自動(dòng)小車(chē)水平運(yùn)動(dòng)按照曼哈頓距離運(yùn)動(dòng)的前提下，選擇合適的任務(wù)完成順序和在需要跨層作業(yè)時(shí)選擇合適的升降機(jī)以使任務(wù)訂單的完成時(shí)間最短。

2.2 系統(tǒng)建模

現(xiàn)對(duì)自動(dòng)小車(chē)存取系統(tǒng)做如下假定：

1）自動(dòng)小車(chē)可以逆向行駛，即自動(dòng)小車(chē)的運(yùn)行是雙向的。

2）不考慮自動(dòng)小車(chē)、升降機(jī)和貨架等硬件設(shè)備的故障等不利因素，且不考慮貨物的存取時(shí)間。

3）不考慮自動(dòng)小車(chē)和升降機(jī)的加速和減速過(guò)程，即認(rèn)為自動(dòng)小車(chē)在水平方向上的運(yùn)動(dòng)和升降機(jī)在垂直方向上的運(yùn)動(dòng)都是勻速的。

4）系統(tǒng)中各層的I/O點(diǎn)（本文假設(shè)每層的I/O點(diǎn)有且只有一個(gè)）是等價(jià)的，即認(rèn)為系統(tǒng)可借助任何一層的I/O點(diǎn)實(shí)現(xiàn)貨物離開(kāi)系統(tǒng)或進(jìn)入系統(tǒng)的操作，且不考慮各層I/O點(diǎn)到系統(tǒng)底層的距離。

5）自動(dòng)小車(chē)和升降機(jī)都是單負(fù)載的，即認(rèn)為自動(dòng)小車(chē)在一段時(shí)間內(nèi)只能攜帶一個(gè)貨物，升降機(jī)在一段時(shí)間只能攜帶一個(gè)自動(dòng)小車(chē)。

6）系統(tǒng)中自動(dòng)小車(chē)和升降機(jī)采取“上次完成位置處停靠” 的?？坎呗裕醋詣?dòng)小車(chē)和升降機(jī)完成任務(wù)后會(huì)停留在原地，不會(huì)主動(dòng)去做空行程運(yùn)動(dòng)。

將單個(gè)復(fù)合作業(yè)過(guò)程（即，完成一次相鄰出庫(kù)操作和入庫(kù)操作）分解為3個(gè)過(guò)程。

1）過(guò)程1：自動(dòng)小車(chē)從當(dāng)前位置（第一個(gè)復(fù)合作業(yè)過(guò)程時(shí)，自動(dòng)小車(chē)的出發(fā)位置為I/O點(diǎn)。之后的復(fù)合作業(yè)過(guò)程中，自動(dòng)小車(chē)的出發(fā)位置是上一個(gè)入庫(kù)貨位處。本文統(tǒng)一稱(chēng)之為上一個(gè)入庫(kù)貨位點(diǎn)）運(yùn)行到出庫(kù)貨位處的過(guò)程。當(dāng)上一次入庫(kù)貨位與當(dāng)前復(fù)合作業(yè)過(guò)程中的出庫(kù)貨位在不同層時(shí)，系統(tǒng)的運(yùn)行必須要用到升降機(jī)。否則，不需要升降機(jī)。

2）過(guò)程2：自動(dòng)小車(chē)從出庫(kù)貨位運(yùn)行到I/O點(diǎn)的過(guò)程。該過(guò)程不會(huì)涉及到升降機(jī)的調(diào)用。

3）過(guò)程3：自動(dòng)小車(chē)從I/O點(diǎn)運(yùn)行到入庫(kù)貨位處的過(guò)程。當(dāng)自動(dòng)小車(chē)當(dāng)前所在的I/O點(diǎn)與入庫(kù)貨位不在同一層時(shí)，系統(tǒng)的運(yùn)行必須要用到升降機(jī)。否則，不需要升降機(jī)。

假設(shè)當(dāng)前有N個(gè)出庫(kù)任務(wù)和N個(gè)入庫(kù)任務(wù)，系統(tǒng)中有M個(gè)升降機(jī)。本文的研究側(cè)重于調(diào)度的空間路徑優(yōu)化。因此，本文關(guān)于自動(dòng)小車(chē)的數(shù)量設(shè)定與文獻(xiàn)[12]相同，即認(rèn)為系統(tǒng)中有且僅有一個(gè)自動(dòng)小車(chē)。不同的任務(wù)完成順序和在每一復(fù)合作業(yè)過(guò)程中選擇不同的升降機(jī)，會(huì)產(chǎn)生不同的調(diào)度方案P，而這些調(diào)度方案所產(chǎn)生的時(shí)間效率往往是不同的。本文優(yōu)化的目標(biāo)是找到一個(gè)使訂單完成總時(shí)間最短的作業(yè)方案。則，建立系統(tǒng)的數(shù)學(xué)模型如下：

其中，T(In→Out)n為第n個(gè)復(fù)合作業(yè)過(guò)程中過(guò)程1的自動(dòng)小車(chē)耗時(shí)，T(Out→I/O)n為過(guò)程2的自動(dòng)小車(chē)通過(guò)曼哈頓距離的耗時(shí)，T(Out→In)n為過(guò)程3的自動(dòng)小車(chē)耗時(shí)。

當(dāng)過(guò)程1中自動(dòng)小車(chē)的運(yùn)行需要借助于升降機(jī)時(shí)，自動(dòng)小車(chē)的耗時(shí)如式(2)所示。

其中，TIn→Lift為過(guò)程1中，自動(dòng)小車(chē)從上一次入庫(kù)貨位處運(yùn)行到升降機(jī)電梯的耗時(shí)，TLiftwait,m為自動(dòng)小車(chē)等待第m個(gè)升降機(jī)（m=1,2,3…M）的耗時(shí)，TLiftrun,m為自動(dòng)小車(chē)乘坐該升降機(jī)的耗時(shí)。

當(dāng)過(guò)程3中自動(dòng)小車(chē)的運(yùn)行需要借助于升降機(jī)時(shí)，自動(dòng)小車(chē)的耗時(shí)如式(3)所示。

其中，TI/O→Lift為過(guò)程3中，自動(dòng)小車(chē)從I/O點(diǎn)運(yùn)行到升降機(jī)電梯的耗時(shí)，TLiftwait,s為自動(dòng)小車(chē)等待第s個(gè)升降機(jī)（s=1,2,3…m）的耗時(shí)，TLiftrun,s為自動(dòng)小車(chē)乘坐該升降機(jī)的耗時(shí)。

3 基于改進(jìn)遺傳算法的自動(dòng)小車(chē)存取系統(tǒng)的調(diào)度優(yōu)化

AVS/RS的調(diào)度優(yōu)化問(wèn)題可以用智能搜索算法求解。由于，遺傳算法具有可并發(fā)處理和應(yīng)用范圍廣泛等優(yōu)點(diǎn)而被廣泛應(yīng)用于求解此類(lèi)問(wèn)題。而簡(jiǎn)單遺傳算法又存在著收斂速度低和收斂精度差等缺點(diǎn)。因此，本文將使用改進(jìn)的遺傳算法來(lái)求解AVS/RS的調(diào)度優(yōu)化問(wèn)題。

3.1 編碼與解碼

符號(hào)編碼是滿足本文需求的最理想的編碼方式。為了方便編程操作，編碼的符號(hào)選用正整數(shù)。例如，第2個(gè)出庫(kù)任務(wù)表示為2，第5個(gè)入庫(kù)任務(wù)表示為5，升降機(jī)3表示3。將出庫(kù)任務(wù)、入庫(kù)任務(wù)和升降機(jī)的編碼依次排列，則可得到染色體個(gè)體的基因型。將出庫(kù)任務(wù)記為向量O，入庫(kù)任務(wù)記為向量I，升降機(jī)組記為向量E，則染色體個(gè)體可表示為D=（O，I，E）。例如，某任務(wù)訂單的完成順序?yàn)锳2→B2→A5→B4→A3→B1→A1→B3→A4→B5，且在5個(gè)復(fù)合作業(yè)過(guò)程中使用的電梯分別為（1，3）、（2，4）、（3，4）、（3，1）和（3，2），那么染色體個(gè)體可表示為：

假設(shè)，某任務(wù)訂單中出庫(kù)任務(wù)和入庫(kù)任務(wù)的數(shù)量都為N，那么染色體的長(zhǎng)度為4N。

可按照相同的原理進(jìn)行解碼操作。解碼操作是編碼操作的逆過(guò)程。例如，現(xiàn)有某染色體個(gè)體為：

則它表示的意義為：訂單按照順序A3→B1→A4→B2→A5→B3→A1→B5→A2→B4依次完成。在5個(gè)復(fù)合作業(yè)過(guò)程中使用的電梯分別為（3，1）、（4，1）、（2，3）、（2，1）和（2，4）。

3.1 編碼與解碼

這里采用傳統(tǒng)的種群初始化方法。將染色體個(gè)體的第一部分（出庫(kù)任務(wù)）、第二部分（入庫(kù)任務(wù)）和第三部分（升降機(jī)組）記為Part1、Part2和Part3，并設(shè)種群規(guī)模為Popsize，且D為某個(gè)可行解的基因型，即染色體個(gè)體。

在接受康復(fù)護(hù)理前，2組患者的ADL評(píng)分、FMA評(píng)分均較低且對(duì)比差異無(wú)統(tǒng)計(jì)學(xué)意義（P＞0.05）；在康復(fù)護(hù)理后，觀察組患者ADL評(píng)分、FMA評(píng)分結(jié)果均高于對(duì)照組，差異有統(tǒng)計(jì)學(xué)意義（P＜0.05）。 見(jiàn)表 1。

按照隨機(jī)的方式分別產(chǎn)生基因片段Part1、Part2和Part3。拼接這三個(gè)部分，即可得一個(gè)染色體個(gè)體。如此重復(fù)Popsize次，即可得到規(guī)模為Popsize的初始化種群。

3.2 線性調(diào)整適應(yīng)度值

這里的目標(biāo)函數(shù)可根據(jù)上文的分析通過(guò)編寫(xiě)計(jì)算機(jī)程序求得，記為f(x)。為了使適應(yīng)度值與任務(wù)完成時(shí)間成負(fù)相關(guān)，本文按照式(4)求適應(yīng)度函數(shù)。

在遺傳算法的前期，個(gè)體的適應(yīng)度值往往相差較大。種群中評(píng)價(jià)特別優(yōu)異的個(gè)體會(huì)得到過(guò)量的繁殖機(jī)會(huì)，容易造成早熟，即過(guò)早收斂。而，在遺傳算法的后期，個(gè)體的適應(yīng)度值則往往相差無(wú)幾，算法的選擇、交叉和變異過(guò)程幾乎變成了隨機(jī)過(guò)程。

為了避免以上兩種情況的發(fā)生，本文采用動(dòng)態(tài)的方法對(duì)適應(yīng)度函數(shù)進(jìn)行線性調(diào)整。將原適應(yīng)度函數(shù)簡(jiǎn)記為f，調(diào)整后的適應(yīng)度函數(shù)簡(jiǎn)記為f '。線性調(diào)整的表達(dá)式為：

其中，a和b為待確定的調(diào)整系數(shù)。

將種群的最大和最小適應(yīng)度值分別記為fmax和fmin，平均適應(yīng)度值記為favg。另外，引入復(fù)制期望參數(shù)c。一般情況下，c的取值在1.3到1.9之間。

則，調(diào)整后的適應(yīng)度函數(shù)為：

則，調(diào)整后的適應(yīng)度函數(shù)為：

3.3 基于混合方法的選擇策略

本文采用輪盤(pán)賭法選擇方式和精英個(gè)體保留法相結(jié)合的方式進(jìn)行選擇。該方式既可以提高優(yōu)秀個(gè)體參與繁殖的機(jī)會(huì)，又可以保護(hù)優(yōu)秀個(gè)體，使其不受破壞。則，遺傳算法可以有效率地提高收斂速度。

具體操作過(guò)程如下：

Step1：計(jì)算個(gè)體被選中的概率。

種群中個(gè)體i被選中的概率可用式(12)表示。

其中，POPsize為種群的規(guī)模，f '(i)為個(gè)體的經(jīng)過(guò)線性?xún)?yōu)化后的適應(yīng)度函數(shù)。

Step2：生成一個(gè)零到適應(yīng)度總和之間的隨機(jī)數(shù)。

先隨機(jī)生成一個(gè)0到1之間的實(shí)數(shù)w0，則待求的隨機(jī)數(shù)w可表示如下：

Step3：找出滿足條件的單個(gè)個(gè)體進(jìn)入交叉和變異操作。

找出唯一同時(shí)滿足式(14)和式(15)的個(gè)體j。

Step4：選擇M個(gè)個(gè)體進(jìn)入交叉和變異操作。

這里的M也是一個(gè)由概率產(chǎn)生的正整數(shù)。設(shè)定種群中參與到交叉和變異的概率為p，p一般為0.8到1之間的實(shí)數(shù)。M可以按照式(16)確定。

即，POPsize與p的乘積取整，可得M。

重復(fù)M次Step2到Step3的操作，則可得到M個(gè)參與交叉和變異的個(gè)體。

Step5：保留（POPsize-M）個(gè)個(gè)體。

先記錄下（POPsize-M）個(gè)適應(yīng)度值較高的個(gè)體。然后，將該（POPsize-M）個(gè)個(gè)體的適應(yīng)度值逐一與經(jīng)過(guò)交叉和變異操作的個(gè)體的適應(yīng)度進(jìn)行比較。如果，該（POPsize-M）個(gè)個(gè)體中的某個(gè)個(gè)體的適應(yīng)度值高于M個(gè)經(jīng)過(guò)交叉和變異的個(gè)體的適應(yīng)度值，則用該個(gè)體替換種群中適應(yīng)度最低的個(gè)體。被替換的個(gè)體數(shù)在0到（POPsize-M）之間。

3.4 交叉算子和變異算子的設(shè)計(jì)

1）交叉算子

本文將個(gè)體的編碼分為三個(gè)部分，分別為出庫(kù)貨位排列Part1，入庫(kù)貨位排序Part2和升降機(jī)組Part3。其中，交叉算子必須使Part1和Part2在交叉操作后保持不重復(fù)、不遺漏。也就說(shuō)，Part1和Part2在交叉以后，仍然是一個(gè)嚴(yán)格的新的排列。則本文針對(duì)Part1和Part2部分分別使用位置基礎(chǔ)交叉法。而Part3的各基因片段之間并沒(méi)有絕對(duì)的邏輯關(guān)系。因此，可以選擇簡(jiǎn)單交叉法。

例如，D1和D2為兩個(gè)未經(jīng)交叉操作的染色體個(gè)體，如下：

Step1：在染色體個(gè)體D1的Part1部分隨機(jī)抽取若干個(gè)基因位，將這些位置上的基因作為新個(gè)體D1'中Part1部分對(duì)應(yīng)位置的基因。去掉染色體個(gè)體D2中Part1部分對(duì)應(yīng)位置的基因，并將D2中Part1部分剩下的基因依次填到D1'的Part1部分剩下的基因位。

Step2：隨機(jī)抽取個(gè)體D1中Part2部分的若干個(gè)基因位，將這些基因逐一復(fù)制到新個(gè)體D1'中Part2部分的對(duì)應(yīng)位置。去掉染色體個(gè)體D2中Part2部分與個(gè)體D1中Part2被抽取到的相同基因，將D2中Part2部分剩下的基因依次填到D1'的Part2部分剩下的基因位。

Setp3：隨機(jī)抽取個(gè)體D1中Part3部分的若干個(gè)基因位。在個(gè)體D2中Part3部分選取相同的基因位。將個(gè)體D1中Part3部分被抽取到的若干個(gè)基因位替換為個(gè)體D2中Part3部分所選取的對(duì)應(yīng)位置的相同基因，則可得到新個(gè)體D1'中Part3部分。

算法經(jīng)過(guò)Step1到Step3的操作，可以得到新的個(gè)體D1'。進(jìn)行類(lèi)似的操作以后可以得到新的個(gè)體D2'，新的個(gè)體D1'和D2'如下：

2） 變異算子

同樣地，變異操作也要按照三個(gè)部分分別進(jìn)行變異操作。這三個(gè)部分都可以使用移位變異法進(jìn)行變異操作。

以原染色體個(gè)體D為例。其中D為：

則，對(duì)原染色體個(gè)體D中的三個(gè)部分分別使用移位變異法，可得到新的染色體D'為：

3.5 基于改進(jìn)遺傳算法的AVS/RS調(diào)度優(yōu)化的執(zhí)行步驟

基于AVS/RS自身的特點(diǎn)，結(jié)合本文提出的改進(jìn)遺傳算法，可將算法過(guò)程描述如下：

步驟1：符號(hào)式編碼 本文選擇符號(hào)式編碼的方式編碼；

步驟2：種群初始化；

步驟3：求適應(yīng)度值并做線性調(diào)整 本文通過(guò)取目標(biāo)函數(shù)的倒數(shù)的方法獲得適應(yīng)度函數(shù)，進(jìn)而求得適應(yīng)度值，并根據(jù)適應(yīng)度值分布情況做線性調(diào)整；

步驟4：判斷是否滿足終止條件 如果滿足終止條件，則輸出可能的最優(yōu)解或次優(yōu)解，并對(duì)應(yīng)于符號(hào)式編碼進(jìn)行解碼得到表現(xiàn)型。如果不滿足終止條件，則重復(fù)步驟5到步驟6；

步驟5：基于混合方式的選擇操作 本文設(shè)計(jì)并采用輪盤(pán)賭法和精英個(gè)體保留法相結(jié)合的選擇策略進(jìn)行選擇操作；

步驟6：交叉操作和變異操作。

4 實(shí)驗(yàn)及結(jié)果分析

4.1 實(shí)驗(yàn)參數(shù)

本文已經(jīng)建立了自動(dòng)小車(chē)存取系統(tǒng)的數(shù)學(xué)模型、分析了自動(dòng)小車(chē)存取系統(tǒng)的調(diào)度內(nèi)容并提出了一種改進(jìn)的遺傳算法以實(shí)現(xiàn)調(diào)度優(yōu)化。為了研究?jī)?yōu)化方案的可行性，需要設(shè)計(jì)合理實(shí)驗(yàn)以進(jìn)行仿真比較。

現(xiàn)對(duì)AVS/RS的各項(xiàng)參數(shù)做如下設(shè)定。系統(tǒng)包含升降機(jī)個(gè)數(shù)M=4；貨架的層數(shù)T=20；巷道單側(cè)的貨位數(shù)C=11；倉(cāng)儲(chǔ)水平方向上的巷道數(shù)A=2；貨位的寬度μw=1m；貨位的高度μh=0.6m；貨位深度為μd=0.5m；μA=0.5m；自動(dòng)小車(chē)在水平X方向上的運(yùn)動(dòng)速度vx=1.8m/s，在水平Y(jié)方向上的運(yùn)動(dòng)速度vy=1.8m/s；升降機(jī)在垂直方向上的速度為2m/s。

隨機(jī)生成10個(gè)出入庫(kù)任務(wù)。其中，5個(gè)出庫(kù)貨位分別為（4，7，20）、（6，11，5）、（7，9，17）、（2，5，11）和（3，7，5），5個(gè)入庫(kù)貨位分別為（3，9，11）、（8，7，17）、（3，7，19）、（5，11，13）和（9，6，17）。結(jié)合系統(tǒng)的各項(xiàng)參數(shù)，可得5個(gè)出庫(kù)貨位和5個(gè)入庫(kù)貨位的自動(dòng)小車(chē)映射位置的水平坐標(biāo)分別如表1和表2所示。

表1 出庫(kù)貨位映射坐標(biāo)

表2 入庫(kù)貨位映射坐標(biāo)

4.2 實(shí)驗(yàn)結(jié)果分析

為了驗(yàn)證本文提出的改進(jìn)遺傳算法IGA在解決自動(dòng)小車(chē)存取系統(tǒng)調(diào)度優(yōu)化方面的優(yōu)越性，本文將改進(jìn)遺傳算法IGA與基本遺傳算法GA和離散粒子群算法PSO進(jìn)行對(duì)比分析。設(shè)置這三個(gè)算法的種群規(guī)模Popsize同為30，最大迭代次數(shù)MAX_GEN為1000。IGA對(duì)適應(yīng)度值做線性調(diào)整，采用混合選擇策略，并采用線性下降的交叉和變異概率。GA采用簡(jiǎn)單輪盤(pán)賭選擇策略，并保持交叉率和變異不變，其中Pc=0.9，Pm=0.2。PSO的學(xué)習(xí)因子設(shè)置為C1=1，C2=1，慣性權(quán)重設(shè)置為從0.8曲線下降到0.3。這三種算法分別獨(dú)立運(yùn)行20次，取最短訂單完成時(shí)間，即目標(biāo)函數(shù)的最優(yōu)結(jié)果為最終的優(yōu)化結(jié)果。三種算法最終優(yōu)化結(jié)果的迭代趨勢(shì)如圖6所示。

圖6 三種算法收斂過(guò)程對(duì)比圖

由改進(jìn)遺傳算法求得的最優(yōu)個(gè)體為[4 1 2 5 3丨1 4 2 5 3丨3 4 4 2 2 2 1 1 2 4]。解碼得，最優(yōu)完成順序?yàn)椋?，5，11）→（3，9，11）→（4，7，20）→（5，11，13）→（6，11，5）→（8，7，17）→（3，7，5）→（9，6，17）→（7，9，17）→（3，7，19）。其中第1個(gè)復(fù)合作業(yè)組使用升降機(jī)3和升降機(jī)4，第2個(gè)復(fù)合作業(yè)組使用升降機(jī)4和升降機(jī)2，第3個(gè)復(fù)合作業(yè)組使用兩次升降機(jī)2，第4個(gè)復(fù)合作業(yè)組使用兩次升降機(jī)1，第5個(gè)復(fù)合作業(yè)過(guò)程使用升降機(jī)3和升降機(jī)4。

由圖5可知，相比于簡(jiǎn)單遺傳算法和離散粒子群算法，本文提出的改進(jìn)遺傳算法具有更快的收斂速度和較好的收斂精度。證明了IGA是快速和較精確解決自動(dòng)小車(chē)存取系統(tǒng)調(diào)度優(yōu)化的方法。

5 結(jié)束語(yǔ)

本文以自動(dòng)小車(chē)可跨層作業(yè)的AVS/RS的調(diào)度優(yōu)化作為研究目標(biāo)。分析了AVS/RS在復(fù)合作業(yè)方式下的出入庫(kù)工作流程，建立了AVS/RS調(diào)度優(yōu)化的數(shù)學(xué)模型。提出了一種根據(jù)現(xiàn)有分布線性調(diào)整適應(yīng)度值，和以輪盤(pán)賭法和精英個(gè)體保留法相結(jié)合的混合選擇策略的改進(jìn)遺傳算法。最后，通過(guò)一組實(shí)驗(yàn)證明了該算法在解決AVS/RS的調(diào)度優(yōu)化求解時(shí)是有效的。未來(lái)可以將神經(jīng)網(wǎng)絡(luò)等人工智能算法引入到AVS/RS的調(diào)度優(yōu)化求解中。

[1]Fukunari M,Malmborg C J. A network queuing approach for evaluation of performance measures in autonomous vehicle storage and retrieval systems[J].European Journal of Operational Research,2009,193(1):152-167.

[2]Heragu S S,Cai X, Krishnamurthy A,et al.Analysis of autonomous vehicle storage and retrieval system by open queueing network[A].IEEE International Conference on Automation Science and Engineering. IEEE[C],2009:455-459.

[3]Gino Marchet, Marco Melacini, Sara Perotti, et al. Analytical model to estimate performances of autonomous vehicle storage and retrieval systems for product totes[J].International Journal of Production Research,2012,50(24):7134-7148.

[4]Luo J. Deadlock control of autonomous vehicle storage and retrieval systems via coloured timed Petri nets and digraph tools[J].International Journal of Production Research,2009,47(12):3253-3263.

[5]Chang-Qing W U, Shan-Jun H E, Luo J.Cycle-deadlock control of RGVs in autonomous vehicle storage and retrieval systems[J].Computer Integrated Manufacturing Systems,2008,14(9):1766-1773.

[6]羅鍵,鐘壽桂,吳長(zhǎng)慶.基于離散粒子群算法的AVS/RS貨位優(yōu)化[J].廈門(mén)大學(xué)學(xué)報(bào)(自然版),2009,48(2):212-215.

[7]鐘壽桂.基于離散粒子群與模擬退火融合算法的自動(dòng)小車(chē)存取系統(tǒng)貨位優(yōu)化[D].廈門(mén)大學(xué),2009.

[8]程志江,李劍波.基于模糊控制的智能小車(chē)控制系統(tǒng)開(kāi)發(fā)[J].計(jì)算機(jī)應(yīng)用,2008,28(s2):350-353.

[9]程志江,李劍波.基于遺傳算法的智能小車(chē)模糊控制系統(tǒng)的研發(fā)[J].自動(dòng)化儀表,2009,30(8):4-7.

[10]馮鋒,鄧志良,趙旭.AGV自動(dòng)導(dǎo)航小車(chē)自組織模糊控制器研究[J].微計(jì)算機(jī)信息,2008,24(10):84-86.

[11]喬巖,錢(qián)曉明,樓佩煌.基于改進(jìn)時(shí)間窗的AGVs避碰路徑規(guī)劃[J].計(jì)算機(jī)集成制造系統(tǒng),2012,18(12):2683-2688.

[12]羅鍵,蘇海墩,何善君,等.基于改進(jìn)遺傳算法的自動(dòng)小車(chē)存取系統(tǒng)升降機(jī)調(diào)度建模與優(yōu)化控制[J].廈門(mén)大學(xué)學(xué)報(bào)(自然版),2010,49(3):328-332.