占翔南，徐立云+，凌旭峰，陳 晨

(1.同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院，上海 201804;2.上海師范大學(xué)天華學(xué)院 人工智能學(xué)院，上海 201815)

0 引言

多深度四向穿梭車倉儲(chǔ)系統(tǒng)是一種集倉儲(chǔ)、配送、管理等功能于一體的新型智能倉儲(chǔ)系統(tǒng)，具有空間利用率高，魯棒性強(qiáng)，響應(yīng)速度快等優(yōu)點(diǎn)，受到企業(yè)的廣泛關(guān)注。四向穿梭車作為該系統(tǒng)的作業(yè)搬運(yùn)設(shè)備，可以在多深度儲(chǔ)貨區(qū)的主干道及儲(chǔ)貨巷道中移動(dòng)，其運(yùn)行效率對出入庫訂單交付具有直接影響。多臺四向穿梭車同時(shí)作業(yè)，一方面容易引起四向穿梭車沖突死鎖問題，另一方面會(huì)加大整個(gè)倉儲(chǔ)調(diào)度的復(fù)雜性，因此，如何制定合理的任務(wù)調(diào)度策略以提高系統(tǒng)運(yùn)行效率是亟待解決的關(guān)鍵問題。

目前，為適應(yīng)自動(dòng)化立體倉儲(chǔ)系統(tǒng)的發(fā)展與應(yīng)用，國內(nèi)外學(xué)者對倉儲(chǔ)系統(tǒng)作業(yè)調(diào)度開展了相關(guān)研究。方彥軍等[1]研究了自動(dòng)小車存取系統(tǒng)的復(fù)合作業(yè)問題，將自動(dòng)小車存取系統(tǒng)中的三維路徑進(jìn)行拓?fù)浣?，采用改進(jìn)的人工狼群算法求解，驗(yàn)證了算法的有效性；楊瑋等[2-3]針對子母式穿梭車及雙載式多車穿梭車倉儲(chǔ)系統(tǒng)作業(yè)調(diào)度問題進(jìn)行了研究，分別采用混合粒子群和混合植物繁殖算法對相應(yīng)的數(shù)學(xué)模型進(jìn)行求解；WU等[4]則以任務(wù)完成時(shí)間及資源利用率為目標(biāo)建立多目標(biāo)作業(yè)調(diào)度模型，采用改進(jìn)遺傳算法進(jìn)行求解，并通過Java語言構(gòu)建任務(wù)調(diào)度仿真平臺對調(diào)度實(shí)例進(jìn)行仿真分析；ZHAN等[5]對雙深度多層穿梭車倉儲(chǔ)系統(tǒng)作業(yè)調(diào)度問題進(jìn)行了研究，以出庫時(shí)間、等待時(shí)間和系統(tǒng)碳排放最小為目標(biāo)建立了多目標(biāo)作業(yè)任務(wù)調(diào)度模型，并采用帶精英策略的非支配排序遺傳算法對其進(jìn)行求解，通過實(shí)例驗(yàn)證了模型及算法的有效性；YANG等[6]研究了雙貨位堆垛式自動(dòng)化立體庫中堆垛機(jī)執(zhí)行出入庫任務(wù)過程中的作業(yè)調(diào)度問題，建立了以作業(yè)時(shí)間最小為目標(biāo)的整數(shù)規(guī)劃模型，并通過仿真分析發(fā)現(xiàn)出入庫任務(wù)次數(shù)對求解效率有較大的影響；魯建廈等[7]對跨層穿梭車倉儲(chǔ)系統(tǒng)復(fù)合作業(yè)問題展開研究，通過分析提升機(jī)與穿梭車的實(shí)際作業(yè)流程，建立出入庫復(fù)合作業(yè)模型，并采用改進(jìn)人工魚群算法進(jìn)行求解。然而，上述倉儲(chǔ)系統(tǒng)作業(yè)調(diào)度問題的文獻(xiàn)均以單臺搬運(yùn)設(shè)備為研究基礎(chǔ)，缺乏對多臺搬運(yùn)設(shè)備同時(shí)作業(yè)的研究和優(yōu)化。

沈博聞等[8]針對倉儲(chǔ)系統(tǒng)中車輛集群調(diào)度進(jìn)行了研究，首先將倉儲(chǔ)系統(tǒng)中的車輛運(yùn)行環(huán)境進(jìn)行網(wǎng)格劃分，在考慮車輛運(yùn)行時(shí)序的基礎(chǔ)上使用A*算法解決了車輛尋路及多車避碰的問題；劉二輝等[9]則采用改進(jìn)的灰狼優(yōu)化算法解決了多AGV(automated guided vehicle)作業(yè)路徑問題，并使用MATLAB開發(fā)工具搭建了仿真平臺，驗(yàn)證了模型和算法的有效性；LI等[10]針對倉儲(chǔ)系統(tǒng)中的多車任務(wù)調(diào)度問題，考慮任務(wù)的執(zhí)行時(shí)間窗及任務(wù)執(zhí)行距離進(jìn)行建模，并采用改進(jìn)蟻群算法進(jìn)行求解；GHASSEMI等[11]針對分布式的多車調(diào)度系統(tǒng)進(jìn)行了研究，提出一種三階段的分布式多車調(diào)度算法，旨在解決隨著問題規(guī)模(車輛/任務(wù)數(shù)量)的增加而導(dǎo)致的計(jì)算成本激增的問題，算法將模糊聚類、二分圖及最大權(quán)重匹配3種方法進(jìn)行組合，最后使用不同的案例驗(yàn)證了算法的有效性。

為解決多臺穿梭車同時(shí)作業(yè)導(dǎo)致的沖突死鎖問題，LI等[12]和ROY等[13]均采用了區(qū)域控制法，將倉儲(chǔ)系統(tǒng)劃分為互不重疊的區(qū)域，且每個(gè)區(qū)域只允許一臺四向穿梭車執(zhí)行任務(wù)；LEE等[14]構(gòu)建了基于Cyber-Physical系統(tǒng)，用于檢測倉儲(chǔ)系統(tǒng)狀態(tài)并獲取實(shí)時(shí)數(shù)據(jù)，采用最短路徑算法為每臺穿梭車提前規(guī)劃好路徑，并使用時(shí)間窗方法檢測穿梭車的沖突，通過一定的規(guī)則調(diào)整穿梭車的運(yùn)行速度和路徑，最終得到無沖突的調(diào)度方案；劉元[15]在時(shí)間窗的基礎(chǔ)上，針對多AGV倉儲(chǔ)系統(tǒng)中的沖突死鎖問題提出了等待算法、路徑重規(guī)劃算法和綜合調(diào)度算法3種解決方案，其中綜合調(diào)度算法能夠根據(jù)實(shí)際情況靈活選擇路徑解決方案，魯棒性更強(qiáng)。

綜合以上研究，已經(jīng)有學(xué)者從自動(dòng)化立體倉儲(chǔ)系統(tǒng)及其相關(guān)問題出發(fā)，對作業(yè)任務(wù)調(diào)度進(jìn)行研究，并應(yīng)用于工程實(shí)踐，但仍存在以下不足：①目前研究的倉儲(chǔ)系統(tǒng)儲(chǔ)貨區(qū)均為單深度或雙深度，沒有考慮多深度儲(chǔ)貨區(qū)對作業(yè)調(diào)度的影響，當(dāng)多個(gè)出入庫任務(wù)出現(xiàn)在同一儲(chǔ)貨巷道，則系統(tǒng)會(huì)發(fā)生堵塞，影響作業(yè)效率；②沖突死鎖問題中，區(qū)域控制法和預(yù)測控制法會(huì)增加作業(yè)任務(wù)的中間環(huán)節(jié)，限制穿梭車作業(yè)范圍，從而降低倉儲(chǔ)系統(tǒng)作業(yè)效率；③實(shí)時(shí)調(diào)度對倉儲(chǔ)設(shè)備要求響應(yīng)速度要求極高，且會(huì)加大調(diào)度系統(tǒng)的瞬時(shí)工作量，從而影響系統(tǒng)的穩(wěn)定性。

本文以多深度四向穿梭車倉儲(chǔ)系統(tǒng)為研究對象，對多臺四向穿梭車同時(shí)作業(yè)的調(diào)度問題進(jìn)行研究。針對上述問題，首先采用圖論方法解決多臺穿梭車同時(shí)作業(yè)導(dǎo)致死鎖問題，根據(jù)Hopcroft-Tarjan算法深度優(yōu)先搜索特性，依次訪問系統(tǒng)中每個(gè)儲(chǔ)貨點(diǎn)獲取路徑方向，生成四向穿梭車在多深度儲(chǔ)貨區(qū)的定向作業(yè)路徑，用于解決多車路口沖突和相向沖突，從而避免四向車穿梭車任務(wù)死鎖問題。然后，在此基礎(chǔ)上建立出入庫復(fù)合作業(yè)調(diào)度優(yōu)化模型，設(shè)計(jì)了一種改進(jìn)混合遺傳算法進(jìn)行求解，對編碼方式的調(diào)整和變異修復(fù)機(jī)制進(jìn)行改進(jìn)，并提出基于任務(wù)順序的多位置鄰域交換法，能夠克服迭代過程中易出現(xiàn)非法解的問題，增加解空間的多樣性，從而有效提升收斂速度和全局搜索能力。

1 布局與假設(shè)

1.1 布局描述

多深度四向穿梭車倉儲(chǔ)系統(tǒng)由多深度高密度存儲(chǔ)貨架、四向穿梭車、輸送系統(tǒng)及控制系統(tǒng)組成。多深度存儲(chǔ)貨架用于貨物存儲(chǔ)，每個(gè)儲(chǔ)貨巷道有多個(gè)空格代表多個(gè)存儲(chǔ)貨位，同一儲(chǔ)貨巷道只能存放同一類貨物；四向穿梭車用于實(shí)現(xiàn)貨物的水平運(yùn)轉(zhuǎn)；輸送系統(tǒng)位于該倉儲(chǔ)系統(tǒng)的入庫口和出庫口，用于實(shí)現(xiàn)貨物的進(jìn)出轉(zhuǎn)運(yùn)；控制管理系統(tǒng)負(fù)責(zé)整個(gè)倉儲(chǔ)系統(tǒng)的設(shè)備監(jiān)控和作業(yè)任務(wù)調(diào)度。

如圖1所示為多深度四向穿梭車倉儲(chǔ)系統(tǒng)的布局圖，位于中間主干道上方的稱為上儲(chǔ)貨區(qū)，位于中間主干道下方的稱為下儲(chǔ)貨區(qū)。在該倉儲(chǔ)系統(tǒng)中，每層的布局均相同，出入庫提升機(jī)分別位于出庫口和入庫口。四向穿梭車可以沿著儲(chǔ)貨巷道及貨架橫向和縱向行駛。當(dāng)四向穿梭車處于空載狀態(tài)時(shí)，可以在存有貨物的多深度巷道中自由穿梭，到達(dá)倉儲(chǔ)系統(tǒng)的任意存儲(chǔ)貨位；當(dāng)四向穿梭車處于載貨狀態(tài)時(shí)，只能在空閑的多深度巷道及主干道上行駛。同一層中放置多臺四向穿梭車同時(shí)進(jìn)行出入庫作業(yè)，以提高系統(tǒng)的靈活性。

1.2 作業(yè)流程

在多深度四向穿梭車倉儲(chǔ)系統(tǒng)中，四向穿梭車入庫作業(yè)流程如下：

(1)當(dāng)入庫任務(wù)產(chǎn)生時(shí)，任務(wù)對應(yīng)的貨位狀態(tài)發(fā)生改變，表示該貨位將有貨物入庫，不再產(chǎn)生其他的入庫任務(wù)；

(2)接收到該入庫任務(wù)的四向穿梭車從當(dāng)前位置運(yùn)行至入庫口，從入庫口處取得貨物，此時(shí)四向穿梭車從空車狀態(tài)變?yōu)檩d貨狀態(tài)；

(3)以目標(biāo)貨位所在的儲(chǔ)貨巷道入口為目的地，根據(jù)路徑定向策略，為四向穿梭車規(guī)劃行駛路徑；

(4)四向穿梭車進(jìn)入目標(biāo)貨位所在儲(chǔ)貨巷道，到達(dá)目標(biāo)貨位放置貨物，并更新該貨位的貨位狀態(tài)，入庫任務(wù)結(jié)束。

四向穿梭車出庫作業(yè)流程如下：

(1)當(dāng)出庫任務(wù)產(chǎn)生時(shí)，任務(wù)對應(yīng)的貨位狀態(tài)發(fā)生改變，表示該貨位將由貨物出庫，不再產(chǎn)生其他出庫任務(wù)；

(2)接收到該入庫任務(wù)的四向穿梭車從當(dāng)前位置運(yùn)行至目標(biāo)貨位，從目標(biāo)貨位處取得貨物，此時(shí)四向穿梭車從空車狀態(tài)變?yōu)檩d貨狀態(tài)；

(3)以出庫口為目的地，根據(jù)路徑定向策略，為四向穿梭車規(guī)劃行駛路徑；

(4)四向穿梭車運(yùn)行至出庫口，放置貨物，并更新該貨位的貨位狀態(tài)，出庫任務(wù)結(jié)束。

當(dāng)系統(tǒng)完成任務(wù)分配，如何使多臺四向穿梭車合理配合，高效完成作業(yè)任務(wù)是多深度四向穿梭車系統(tǒng)調(diào)度優(yōu)化的目的。因此，需要對多臺穿梭車的作業(yè)路徑進(jìn)行規(guī)劃，而建立合理正確的復(fù)合作業(yè)模型是調(diào)度優(yōu)化的關(guān)鍵。

1.3 假設(shè)與符號

為建立合理正確的調(diào)度優(yōu)化模型，需對模型的主要假設(shè)條件和參數(shù)符號進(jìn)行說明。同時(shí)為了研究方便且不失一般性，進(jìn)行如下假設(shè)：

(1)四向穿梭車服從終點(diǎn)?？坎呗?Point-of-Service-Completion，POSC)，即四向穿梭車會(huì)?？吭诋?dāng)前任務(wù)結(jié)束的位置；

(2)貨物先進(jìn)先出原則，為保證倉儲(chǔ)系統(tǒng)貨物先進(jìn)先出，儲(chǔ)貨巷道內(nèi)的貨物采用先進(jìn)先出的操作方式，即只從儲(chǔ)貨巷道一端入貨，從另一端出貨；

(3)該系統(tǒng)內(nèi)同時(shí)存在入庫任務(wù)和出庫任務(wù)，四向穿梭車服從單一作業(yè)模式；

(4)四向穿梭車為勻速行駛，不考慮加速度；

(5)四向穿梭車執(zhí)行任務(wù)是狀態(tài)穩(wěn)定，保證有充足電量完成任務(wù)。

本文用到的主要參數(shù)如表1所示。

表1 主要參數(shù)說明

2 系統(tǒng)建模

2.1 多深度儲(chǔ)貨區(qū)路徑策略

在多深度四向穿梭車倉儲(chǔ)系統(tǒng)中，當(dāng)多臺四向穿梭車同時(shí)作業(yè)時(shí)，主干道交叉口及多深度儲(chǔ)貨巷道內(nèi)可能出現(xiàn)四向穿梭車沖突與死鎖現(xiàn)象，將導(dǎo)致儲(chǔ)貨區(qū)堵塞，使出入庫任務(wù)無法正常執(zhí)行。因此，如何避免四向穿梭車沖突與死鎖問題是解決作業(yè)調(diào)度的關(guān)鍵內(nèi)容之一。本文針對該問題，采用Hopcroft-Tarjan算法對多深度儲(chǔ)貨區(qū)制定路徑定向策略，在運(yùn)行規(guī)則上避免四向穿梭車沖突死鎖問題，從而可以實(shí)現(xiàn)全區(qū)域作業(yè)，減少作業(yè)任務(wù)中間環(huán)節(jié)，提升作業(yè)效率；另一方面，采用該方法可以降低調(diào)度系統(tǒng)的實(shí)時(shí)調(diào)度壓力和設(shè)備實(shí)時(shí)響應(yīng)的要求，增強(qiáng)倉儲(chǔ)系統(tǒng)的穩(wěn)定性。

對多深度儲(chǔ)貨區(qū)的交通網(wǎng)絡(luò)進(jìn)行建模，將其建模為圖G={V(G),E(G)}，將主干道和儲(chǔ)貨巷道抽象成圖G的邊，將交叉路口抽象成圖G的頂點(diǎn)。對多深度儲(chǔ)貨區(qū)中的交通網(wǎng)絡(luò)進(jìn)行路徑定向，實(shí)際是設(shè)定圖中每條單向邊的方向，使其成為具有強(qiáng)連通性的有向圖。對于不含割邊的連通圖G，采用Hopcroft-Tarjan算法求得G的強(qiáng)連通定向圖的步驟如下：

步驟1任取G中的一個(gè)頂點(diǎn)v，令l(v)=1，L={v}，U=V-{v}，R=?；

步驟2在L中取頂點(diǎn)u，使得l(u)最大且滿足在U中存在與u相鄰的頂點(diǎn)，然后從U中取一個(gè)與u相鄰的頂點(diǎn)w，使得邊uw成為有向邊u→w，同時(shí)令l(w)=l(u)+1，L=L∪{w}，U=U-{w}，A=A∪{u→w}；

步驟3若L≠V，轉(zhuǎn)步驟2，否則執(zhí)行步驟4；

步驟4對當(dāng)前還未定向的邊ab，按照以下方法進(jìn)行定向：若l(a)>l(b)，則指定方向后的邊為a→b，否則邊為b→a。

上述步驟中，R為已經(jīng)確定方向的邊的集合，L為已經(jīng)給出標(biāo)號的頂點(diǎn)集合，U為還未給出標(biāo)號的頂點(diǎn)集合。

根據(jù)羅賓斯定理，圖G會(huì)出現(xiàn)多種強(qiáng)連通定向圖，需要結(jié)合倉儲(chǔ)布局及出入庫原則，確定最終路徑定向策略。為保證最終定向結(jié)果有利于倉儲(chǔ)系統(tǒng)的高效運(yùn)轉(zhuǎn)，應(yīng)優(yōu)先滿足如下條件：

(1)由于入庫口位于左上角，應(yīng)將X方向上靠近入庫口位置的1#主干道的方向設(shè)定為從左至右的方向；

(2)由于入庫口位于圖的上方，應(yīng)將儲(chǔ)貨巷道的入口處放置在1#及2#主干道上，以便實(shí)現(xiàn)儲(chǔ)貨巷道中貨物的先進(jìn)先出，因此儲(chǔ)貨巷道的方向應(yīng)由上至下。

根據(jù)上述優(yōu)先滿足條件，采用Hopcroft-Tarjan算法，將多深度儲(chǔ)貨區(qū)交通網(wǎng)絡(luò)定向圖與出入庫口路段結(jié)合后，最終得到的路徑定向圖如圖2所示。

2.2 作業(yè)調(diào)度模型

在多深度四向穿梭車倉儲(chǔ)系統(tǒng)中，通過對四向穿梭車作業(yè)過程分析，可將多深度四向穿梭車倉儲(chǔ)系統(tǒng)調(diào)度問題轉(zhuǎn)化成柔性車間作業(yè)調(diào)度問題。柔性車間作業(yè)調(diào)度問題可以描述為：多個(gè)工件需要在多臺機(jī)器上進(jìn)行加工，每個(gè)工件均有多個(gè)加工工序，每個(gè)工序的加工時(shí)間在不同工況的機(jī)器上不同，且同一個(gè)工件的工序之間具有先后約束，需要合理分配每臺機(jī)器上的加工工序，并確定工序的先后執(zhí)行順序，最終得到一個(gè)使得加工時(shí)間最短的分配方案。對于多深度儲(chǔ)貨區(qū)四向穿梭車調(diào)度問題來說，不同出入庫任務(wù)可視為待加工工件的不同工序，同時(shí)作業(yè)的四向穿梭車可以視為并行運(yùn)行的加工機(jī)器，不同出入庫任務(wù)可由不同穿梭車執(zhí)行，以完成所有作業(yè)任務(wù)的最短時(shí)間為目標(biāo)進(jìn)行求解，最終得到四向穿梭車的多車任務(wù)分配及任務(wù)執(zhí)行順序方案。

ki>0,i∈[1,m]；

(1)

(2)

(3)

(4)

Aq∩Aw=?,?q,w∈[1,m]。

(5)

其中：(1)表示每輛四向穿梭車至少分配一個(gè)任務(wù)；式(2)表示四向穿梭車在空載階段運(yùn)行時(shí)間不能為負(fù)值；式(3)表示四向穿梭車在裝載階段運(yùn)行時(shí)間必須為正值；式(4)表示四向穿梭車將執(zhí)行所有任務(wù)；式(5)表示一個(gè)任務(wù)只能由一輛四向穿梭車執(zhí)行。

根據(jù)以上約束模型，構(gòu)建如下目標(biāo)函數(shù)：

funC=min(max(Ti))。

(6)

最小化多臺四向穿梭車完成出入庫任務(wù)時(shí)間最大值，即完成所有作業(yè)任務(wù)的總時(shí)間最短。編號為i的四向穿梭車完成ki個(gè)任務(wù)的作業(yè)時(shí)間如下：

(7)

四向穿梭車的作業(yè)時(shí)間由具體任務(wù)決定，且車輛的起始點(diǎn)及貨物位置有關(guān)，根據(jù)上述路徑定向策略規(guī)劃車輛路徑，進(jìn)行相應(yīng)作業(yè)時(shí)間計(jì)算。對于入庫作業(yè)任務(wù)，四向穿梭車首先從起始點(diǎn)運(yùn)行至入庫口裝載貨物，然后根據(jù)多深度儲(chǔ)貨區(qū)路徑定向策略，制定相應(yīng)的路徑，從入庫口運(yùn)行至目標(biāo)貨位，入庫任務(wù)作業(yè)示意圖如圖3所示，其空載階段運(yùn)行時(shí)間為：

(8)

滿載過程運(yùn)行時(shí)間為：

(1)當(dāng)目標(biāo)貨位位于上儲(chǔ)貨區(qū)時(shí)，

(9)

(2)當(dāng)目標(biāo)貨位位于下儲(chǔ)貨區(qū)時(shí)，

(10)

對于出庫作業(yè)任務(wù)，四向穿梭車首先從起始點(diǎn)運(yùn)行至目標(biāo)，然后根據(jù)道路定向策略，制定相應(yīng)的路徑，從目標(biāo)貨位運(yùn)行至出庫口，出庫作業(yè)示意圖如圖4所示，其空載階段運(yùn)行時(shí)間為：

(11)

滿載過程運(yùn)行時(shí)間為：

(1)當(dāng)目標(biāo)貨位位于上儲(chǔ)貨區(qū)時(shí)，

(12)

(2)當(dāng)目標(biāo)貨位位于下儲(chǔ)貨區(qū)時(shí)，

(13)

3 算法設(shè)計(jì)

遺傳算法(Genetic Algorithm,GA)是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法，非常適用于處理傳統(tǒng)搜索算法難以解決的復(fù)雜優(yōu)化問題。遺傳算法具有較強(qiáng)的全局搜索能力，但局部搜索能力較弱。為解決多深度四向穿梭車倉儲(chǔ)系統(tǒng)作業(yè)調(diào)度問題，本文將模擬退火算法(Simulated Annealing algorithm,SA)較強(qiáng)的局部搜索能力引入到遺傳算法的搜索過程中，構(gòu)建一種改進(jìn)混合遺傳算法(Improved Hybrid GA,IHGA)，該算法兼具遺傳算法的全局搜索能力和模擬退火算法高效的局部搜索能力。為進(jìn)一步優(yōu)化改進(jìn)混合遺傳算法的性能，通過編碼方式的調(diào)整和變異修復(fù)機(jī)制的改進(jìn)有效避免迭代過程中易出現(xiàn)非法解的問題，避免算法過早收斂和局部早熟，并提出一種基于任務(wù)排序的多位置鄰域交換法，有效增加解空間的多樣性，進(jìn)而提高算法搜索性能。

3.1 算法流程

IHGA的工作原理為：首先利用GA對初始種群進(jìn)行遺傳操作，以達(dá)到進(jìn)化種群的目的，再通過模擬點(diǎn)火算法的Metropolis抽樣過程對遺傳算法進(jìn)化得到的結(jié)果進(jìn)行抽樣判定，而抽樣得到的結(jié)果又會(huì)成為遺傳算法進(jìn)行下一代進(jìn)化操作的初始種群，算法流程如圖5所示。

IHGA算法基本流程如下：

步驟1設(shè)置相關(guān)參數(shù)，主要包括：種群規(guī)模N，交叉概率Pc、變異概率Pm、最大迭代次數(shù)G、退溫控制值d、退溫速率λ；

步驟2根據(jù)約束條件，生成規(guī)模為N的初始種群P；

步驟3計(jì)算每個(gè)個(gè)體適應(yīng)度并排序，根據(jù)精英保留策略，選擇一定比例的最優(yōu)個(gè)體進(jìn)行保留；

步驟4通過錦標(biāo)賽選擇法選擇種群中適應(yīng)度高的個(gè)體進(jìn)入下一步操作；

步驟5采用自適應(yīng)交叉和變異算子，對種群進(jìn)行交叉和變異操作；

步驟6根據(jù)任務(wù)排序的多位置鄰域交換方法產(chǎn)生新解，若符合Metropolis準(zhǔn)則，則接受新解，否則保留原始解，由此產(chǎn)生模擬退火后的新種群P′；

步驟7判斷當(dāng)前是否滿足算法終止條件，若滿足，則結(jié)束算法流程并輸出最優(yōu)方案，否則轉(zhuǎn)步驟3。

3.2 算法實(shí)現(xiàn)

(1)構(gòu)造個(gè)體

為同時(shí)描述出入庫任務(wù)分配及四向穿梭車作業(yè)順序，采用如圖6所示的雙段染色體編碼方式，其中：第一段代表作業(yè)任務(wù)的編碼，稱為任務(wù)碼；第二段代表四向穿梭車執(zhí)行任務(wù)數(shù)的編碼，稱為車輛碼，每條染色體對應(yīng)一個(gè)調(diào)度方案，用于描述每輛四向穿梭車分得任務(wù)及任務(wù)執(zhí)行順序。

如圖6所示，當(dāng)任務(wù)碼為[6,3,7,8,5,1,2,4,9,10]，車輛碼為[2,1,3,4]時(shí)，經(jīng)過解碼可知，1號四向穿梭車任務(wù)數(shù)為2，執(zhí)行順序?yàn)閇6,3]；2號四向穿梭車任務(wù)數(shù)為1個(gè)，為7；3號四向穿梭車任務(wù)數(shù)為3，執(zhí)行順序?yàn)閇8,5,1]；4號四向穿梭車任務(wù)數(shù)為4，執(zhí)行順序?yàn)閇2,4,9,10]。

(2)適應(yīng)度函數(shù)

由于目標(biāo)函數(shù)值均大于1，選擇目標(biāo)函數(shù)值的倒數(shù)作為個(gè)體的適應(yīng)度值，當(dāng)完成所有任務(wù)的時(shí)間越大時(shí)，適應(yīng)度函數(shù)值越小。適應(yīng)度函數(shù)如式(14)表示：

(14)

式中Tmax表示四向穿梭車執(zhí)行任務(wù)的最大完成時(shí)間。

(3)選擇算子

本文采用錦標(biāo)賽方法進(jìn)行個(gè)體的選擇操作，每次從種群中選取2個(gè)個(gè)體進(jìn)行適應(yīng)度比較，將適應(yīng)度值高的個(gè)體放入交叉池，循環(huán)操作得到數(shù)量為N的種群。同時(shí)，使用精英保留策略將優(yōu)秀個(gè)體進(jìn)行保留，提高算法的全局收斂性。

(4)自適應(yīng)交叉和變異

標(biāo)準(zhǔn)遺傳算法使用固定的交叉率和變異率來確定染色體是否進(jìn)行交叉和變異操作，會(huì)存在兩個(gè)問題：①概率取值過小時(shí)會(huì)導(dǎo)致搜索效率較低，不利于尋找到全局最優(yōu)解；②概率取值過大時(shí)則有可能破壞較優(yōu)個(gè)體，導(dǎo)致較優(yōu)方案的丟失。因此，本文采用自適應(yīng)交叉與變異方法進(jìn)行操作，避免算法出現(xiàn)早熟和局部收斂問題。

(5)交叉算子

考慮到編碼方式的特殊性，個(gè)體如按照標(biāo)準(zhǔn)遺傳算法的交叉會(huì)產(chǎn)生非法解，因此僅對任務(wù)碼進(jìn)行交叉，對車輛碼進(jìn)行保留。本文采用兩點(diǎn)交叉方式對任務(wù)碼進(jìn)行交叉，如圖7所示。對于第二段車輛碼部分，如果使用兩點(diǎn)交叉法進(jìn)行交叉操作會(huì)使得四向穿梭車執(zhí)行分得任務(wù)數(shù)量變化較大，不利于進(jìn)一步產(chǎn)生更優(yōu)方案，因此在該階段第二段車輛碼直接保留到子代。

(6)變異修復(fù)

對于第一段任務(wù)碼進(jìn)行變異操作。采用交換變異的方法，如圖8所示，隨機(jī)選擇兩個(gè)變異點(diǎn)，交換父代選定的變異點(diǎn)得到新的子代。

對于第二段車輛碼進(jìn)行變異操作時(shí)，隨機(jī)選取數(shù)個(gè)車輛，采用鄰值變異法對車輛對應(yīng)的任務(wù)數(shù)量進(jìn)行變異操作。在變異操作過后，檢查當(dāng)前得到的染色體是否符合約束條件，對不符合約束條件的染色體進(jìn)行修正。修正方法如下：如圖9所示，當(dāng)父代為[2,1,3,4]，選中[1,3,4]進(jìn)行鄰值變異操作，變異結(jié)果為[0,4,3]，此時(shí)2號車分得的任務(wù)數(shù)量為0。為了修復(fù)0值基因，從當(dāng)前基因最大值上減1，給0值基因加1，得到經(jīng)過0值基因修復(fù)后的子代[2,1,3,3]，此時(shí)任務(wù)數(shù)量總和為9，小于變異前的任務(wù)數(shù)量總和10，將該差值加到基因最小值上，得到經(jīng)過修復(fù)總和操作的子代[2,2,3,3]，該子代滿足所有約束條件。經(jīng)過改進(jìn)的變異方式不會(huì)產(chǎn)生非法解，有利于可行解的搜索效率。

(7)控制參數(shù)的初值設(shè)置

控制參數(shù)t的初值設(shè)置直接影響算法的局部搜索能力和搜索速度。初值越高，算法最終獲得高質(zhì)量解的概率越大，但搜索時(shí)間越長；初值越低，搜索速度越快，但局部搜索能力越低。本文中控制參數(shù)的初值按照式(15)確定：

(15)

式中：fmax和fmin為當(dāng)前群體中最佳個(gè)體和最差個(gè)體的適應(yīng)度；Pr為控制參數(shù)t的初始接受概率。

(8)鄰域交換

本文提出了一種基于任務(wù)排序的多位置鄰域交換法，能夠有效增加解空間的多樣性。其交換過程可以描述為：對于要交換的個(gè)體i，隨機(jī)產(chǎn)生[1,40]區(qū)間內(nèi)的k(k≤40)個(gè)不同的整數(shù)：x1,x2,…xk。 依次對個(gè)體i第xi(1≤i≤40)位置的部分染色體進(jìn)行多位置鄰域交換。首先，算法隨機(jī)產(chǎn)生一個(gè)[1,max]區(qū)間的整數(shù)len，len是進(jìn)行交換的長度，max為設(shè)置的最大值，本文中取值為10。然后，從當(dāng)前的部分染色體中隨機(jī)選擇兩端長度為len的染色體段，進(jìn)行標(biāo)準(zhǔn)鄰域交換。最后，檢驗(yàn)交換后的個(gè)體i′是否滿足約束條件，若不滿足約束條件，則取消交換。重復(fù)上述過程，直到k個(gè)部分染色體交換完畢后，輸出交換后的個(gè)體i′，其流程圖如圖10所示。

(9)退溫函數(shù)

在改進(jìn)混合遺傳算法的模擬退火理論部分，要求控制參數(shù)t的值能夠以一個(gè)適中的速度下降，否則會(huì)影響算法的局部搜索能力和解的質(zhì)量。在算法搜索過程中，若產(chǎn)生的可行解數(shù)量較多，那么t的下降速度較快，本文按照式(16)對控制參數(shù)進(jìn)行降溫操作。

t(k+1)=λtk。

(16)

式中:λ為常量，λ∈[0,1]，λ的值越小，t的下降速度越快。

(10)新解的接受機(jī)制

新解的接受機(jī)制是改進(jìn)混合遺傳算法實(shí)現(xiàn)全局搜索的關(guān)鍵，本文采用Metropolis接受準(zhǔn)則作為新解的接受機(jī)制。

4 案例研究

電商倉儲(chǔ)系統(tǒng)具有時(shí)效性強(qiáng)，訂單波動(dòng)大等特點(diǎn)，高峰期日均訂單量是平時(shí)的幾十倍，甚至幾百倍，因此對倉儲(chǔ)系統(tǒng)的柔性要求非常高。本文以某電商單層多深度四向穿梭車倉儲(chǔ)系統(tǒng)為例，對出入庫任務(wù)分配及四向穿梭車作業(yè)順序進(jìn)行優(yōu)化。該倉儲(chǔ)系統(tǒng)分為上、下兩個(gè)儲(chǔ)貨區(qū)，其中每個(gè)儲(chǔ)貨區(qū)貨位深度為6，巷道數(shù)量為32。該層有5輛四向穿梭車，在某一時(shí)間窗口內(nèi)有40個(gè)出入庫任務(wù)需要被執(zhí)行，各車空閑時(shí)的坐標(biāo)位置點(diǎn)如表2所示，出入庫任務(wù)如表3所示，其中任務(wù)起點(diǎn)為(0,0)點(diǎn)的任務(wù)表示入庫任務(wù)，任務(wù)終點(diǎn)為(0,14)點(diǎn)的任務(wù)表示出庫任務(wù)。

表2 四向穿梭車起始位置坐標(biāo)點(diǎn)

表3 40個(gè)出入庫任務(wù)坐標(biāo)點(diǎn)

首先，需要對該單層多深度四向穿梭車倉儲(chǔ)系統(tǒng)制定路徑定向策略，將該倉儲(chǔ)系統(tǒng)建模為圖G={V(G),E(G)}，將主干道和儲(chǔ)貨巷道抽象成圖G的邊，將交叉路口抽象成圖G的頂點(diǎn)，得到圖G共有67條邊，102個(gè)頂點(diǎn)。采用Hopcroft-Tarjan算法求解該倉儲(chǔ)系統(tǒng)路徑定向策略的步驟如下：

步驟1將圖G的邊依次從1到67開始編號，將圖G的頂點(diǎn)依次從1到102開始編號；

步驟2取圖G中編號為1的交叉路口v，令l(v)=1，L={v}，U=V-{v}，R=?；

步驟3在L中取交叉路口u，使l(u)最大并且滿足在U中存在與u相鄰的交叉路口，然后從U中取一個(gè)與u相鄰的交叉路口w，使得路徑uw成為有向邊u→w，同時(shí)令l(w)=l(u)+1，L=L∪{w}，U=U-{w}，A=A∪{u→w}；

步驟4若L≠V，轉(zhuǎn)步驟3，否則執(zhí)行步驟5；

步驟5對當(dāng)前還未定向的路徑ab，按照以下方法進(jìn)行路徑定向：若l(a)>l(b)，則路徑ab的方向?yàn)閍→b，否則為b→a。

根據(jù)上述求解步驟，得到多種強(qiáng)連通路徑定向圖，因此需要結(jié)合倉儲(chǔ)布局及出入庫原則，確定最終路徑定向策略。由于入庫口位于圖G左上角，將靠近入庫口的水平主干道的路徑方向設(shè)定為從左至右，將儲(chǔ)貨巷道的入口放置在儲(chǔ)貨巷道的上方，以便實(shí)現(xiàn)儲(chǔ)貨巷道中貨物的先進(jìn)先出原則，因此儲(chǔ)貨巷道的路徑方向?yàn)閺纳现料隆?/p>

根據(jù)Hopcroft-Tarjan算法的求解結(jié)果，并結(jié)合該倉儲(chǔ)系統(tǒng)布局特點(diǎn)，最終得到該單層多深度四向穿梭車倉儲(chǔ)系統(tǒng)的路徑定向策略。

本文通過與區(qū)域控制策略對比來驗(yàn)證路徑定向策略的有效性。區(qū)域控制策略的思路是根據(jù)出入庫任務(wù)分布，將該倉儲(chǔ)系統(tǒng)劃分為5個(gè)區(qū)域，每臺穿梭車負(fù)責(zé)一個(gè)區(qū)域內(nèi)的出入庫任務(wù)。計(jì)算程序在MATLAB 2016b平臺上運(yùn)行，計(jì)算機(jī)配置為Intel(R) Core(TM) i7-7 700HQ CPU @2.80 GHz, 8.00 GB RAM。

根據(jù)程序運(yùn)行得到兩種策略下的四向穿梭車任務(wù)執(zhí)行順序的結(jié)果，如表4所示。在區(qū)域控制策略下，5臺穿梭車的作業(yè)時(shí)間分別為364.36s、460.87 s、516.45 s、551.29 s和597.42 s，由于5臺穿梭車同時(shí)作業(yè)，任務(wù)完成總時(shí)間為597.42 s。在路徑定向策略下，5臺穿梭車的作業(yè)時(shí)間分別為512.34 s、497.21 s、522.87 s、501.46 s和516.27 s，作業(yè)任務(wù)完成總時(shí)間為522.87 s，如圖11所示。由此可知，路徑定向策略的優(yōu)化效率為14.3%。

表4 2種策略下穿梭車分配的作業(yè)任務(wù)及執(zhí)行順序

由圖11結(jié)果可知，在區(qū)域控制策略下，5臺穿梭車任務(wù)完成時(shí)間差距較大，最短任務(wù)完成時(shí)間為364.36 s，最長任務(wù)完成時(shí)間為597.42 s，任務(wù)完成總時(shí)間為597.42 s；由于區(qū)域控制策略是根據(jù)出入庫任務(wù)分布，按照區(qū)域劃分確定穿梭車執(zhí)行任務(wù)范圍，導(dǎo)致離出入庫口近的任務(wù)完成時(shí)間短，離出入庫口遠(yuǎn)的任務(wù)完成時(shí)間長，因此1號穿梭車任務(wù)完成時(shí)間最短，5號穿梭車任務(wù)完成時(shí)間最長。在路徑定向策略下，5臺穿梭車任務(wù)完成時(shí)間差距較小，最短任務(wù)完成時(shí)間為497.21 s，最長任務(wù)完成時(shí)間為522.87 s，任務(wù)完成總時(shí)間為522.87 s；采用路徑定向策略可使得穿梭車在整個(gè)倉儲(chǔ)系統(tǒng)內(nèi)執(zhí)行任意作業(yè)任務(wù)，不受區(qū)域限制，從而提高穿梭車?yán)寐?，提升作業(yè)效率。

為進(jìn)一步驗(yàn)證算法的有效性，將GA算法、SA算法和IHGA算法分別對作業(yè)任務(wù)規(guī)模為40,80,120的情況各重復(fù)進(jìn)行100次實(shí)驗(yàn)，每個(gè)作業(yè)任務(wù)規(guī)模下的貨位都是隨機(jī)產(chǎn)生的，在控制參數(shù)的選擇上，參考文獻(xiàn)[4，16-17]，算法參數(shù)如表5所示。

表5 GA,SA和IHGA算法參數(shù)設(shè)置

經(jīng)過MATLAB仿真計(jì)算，得到3種算法實(shí)驗(yàn)結(jié)果如表6所示，IHGA相對于GA和SA而言，算法的精度和穩(wěn)定性都有較大的提升，且減少了求解時(shí)間，表明IHGA算法是一種有效的求解算法。隨著任務(wù)規(guī)模的不斷增大，出入庫任務(wù)分配和四向穿梭車執(zhí)行順序更復(fù)雜，相比于GA和SA算法，IHGA算法的求解精度和穩(wěn)定性的優(yōu)勢不斷擴(kuò)大，優(yōu)化效果更為明顯，出入庫任務(wù)分配和四向穿梭車執(zhí)行順序更合理，任務(wù)完成時(shí)間提升更大，系統(tǒng)作業(yè)效率更高，從而表明該算法更適用于求解大規(guī)模的調(diào)度優(yōu)化問題。

表6 3種算法實(shí)驗(yàn)結(jié)果對比

如圖12所示為GA、SA和IHGA三種算法在不同任務(wù)規(guī)模下的算法收斂圖。GA算法前期全局搜索能力較強(qiáng)，算法收斂速度快，但局部搜索能力弱，從而導(dǎo)致求解的精度不高；SA算法搜索能力強(qiáng)，具有較好的搜索能力，但是算法需要較長的搜索時(shí)間，收斂速度慢；IHGA算法結(jié)合GA算法和SA算法的優(yōu)點(diǎn)，充分利用GA算法的全局搜索能力，使得算法前期快速收斂，又結(jié)合了SA的局部搜索能力，提高了求解精度，使得改進(jìn)后的算法具有更好的全局搜索能力及更快的收斂速度。相對于其他兩種算法，IHGA算法在求解精度和收斂速度上都有一定的提高，更適合本模型的尋優(yōu)。

當(dāng)任務(wù)規(guī)模為40時(shí)，經(jīng)過IHGA算法優(yōu)化后得到5臺四向穿梭車作業(yè)任務(wù)執(zhí)行順序，如表7所示，5臺四向穿梭車的作業(yè)時(shí)間分別為425.74 s、424.59 s、431.63 s、437.06 s和429.48 s，作業(yè)任務(wù)完成總時(shí)間為437.06 s。優(yōu)化后得到第4臺穿梭車作業(yè)路徑圖如圖13所示，第4臺穿梭車作業(yè)路徑順序?yàn)?2,12)→(0,0)→(7,3)→(0,0)→(9,1)→(31,1)→(0,14)→(0,0)→(5,11)→(0,0)→(7,5)→(0,0)→(15,11)→(16,3)→(0,14)→(16,2)→(0,14)。

表7 優(yōu)化后四向穿梭車分配的作業(yè)任務(wù)及執(zhí)行順序

由上述結(jié)果可知，采用Hopcroft-Tarjan算法可以有效制定路徑定向策略，從運(yùn)行規(guī)則上避免了多臺穿梭車同時(shí)作業(yè)交叉路口沖突和相向沖突，能夠有效解決多臺穿梭車全區(qū)域作業(yè)死鎖問題，從而提升作業(yè)效率。通過對混合遺傳算法編碼方式和變異修復(fù)機(jī)制的改進(jìn)，能夠克服迭代過程中易出現(xiàn)非法解的問題，增加解空間的多樣性，提升算法的收斂速度和全局搜索能力。

5 結(jié)束語

本文針對多深度四向穿梭車倉儲(chǔ)系統(tǒng)調(diào)度優(yōu)化問題開展研究。根據(jù)Hopcroft-Tarjan算法提出一種多深度儲(chǔ)貨區(qū)的路徑定向策略，在此基礎(chǔ)上建立以最小作業(yè)時(shí)間為目標(biāo)的調(diào)度優(yōu)化模型，并設(shè)計(jì)了改進(jìn)混合遺傳算法來優(yōu)化該倉儲(chǔ)布局下的任務(wù)調(diào)度。實(shí)驗(yàn)結(jié)果說明，本文提出的路徑定向策略可以有效解決四向穿梭車沖突與死鎖，提升系統(tǒng)作業(yè)效率。為了說明所設(shè)計(jì)算法的性能，在不同任務(wù)規(guī)模下，將IHGA算法與GA算法、SA算法的計(jì)算結(jié)果進(jìn)行了比較，實(shí)例結(jié)果表明IHGA算法具有更好的尋優(yōu)能力和更快的收斂速度，且能較大幅度地提高系統(tǒng)作業(yè)效率。下一步，將在此基礎(chǔ)上對多層多深度四向穿梭車倉儲(chǔ)系統(tǒng)調(diào)度優(yōu)化問題進(jìn)行研究。