基于PLC立體倉庫畢業(yè)設(shè)計(jì)外文翻譯

河南理工大學(xué)2013中英文對照翻譯本科畢業(yè)設(shè)計(jì)（論文）中英文對照翻譯院（系部）機(jī)械與動力工程學(xué)院專業(yè)名稱測控技術(shù)與儀器年級班級1203班學(xué)生姓名張賀指導(dǎo)老師王耿20由一個單一的存儲/檢索機(jī)服務(wù)的多巷道自動化立體倉庫存在的揀選分揀問題YaghoubKhojastehJae-DongSon加馬里筑波大學(xué)崇實(shí)大學(xué)日本韓國摘要隨著現(xiàn)代化科技的發(fā)展，倉庫式存儲系統(tǒng)在設(shè)計(jì)與運(yùn)行方面出現(xiàn)了巨大的改革。自動化立體倉庫（AS/RS）嵌入計(jì)算機(jī)驅(qū)動正變得越來越普遍。由于AS/RS使用的增加對計(jì)算機(jī)控制的需要與支持也在提高。這項(xiàng)研究解決了在多巷道立體倉庫的揀選問題，在這種存儲/檢索（S/R）操作中，每種貨物可以在多個存儲位置被尋址到。提出運(yùn)算方法的目標(biāo)是，通過S/R系統(tǒng)揀選貨物來最大限度的減少行程時間。我們開發(fā)的遺傳式和啟發(fā)式算法，以及通過比較從大量的問題中得到一個最佳的解決方案。關(guān)鍵詞：自動化立體倉庫，AS/RS系統(tǒng)，揀選，遺傳算法。1.言在現(xiàn)今的生產(chǎn)環(huán)境中，庫存等級保持低于過去。那是因?yàn)檫@種較小的存儲系統(tǒng)不僅降低庫存量還增加了揀選貨物的速度。自動化立體倉庫（AS/RS），一方面通過提供快速響應(yīng)，來達(dá)到高操作效率；另一方面它還有助于運(yùn)作方面的系統(tǒng)響應(yīng)時間，減少的揀選完成的總行程時間。因此，它常被用于制造業(yè)、儲存?zhèn)}庫和分配設(shè)備等行業(yè)中。揀選是倉庫檢索功能的基本組成部分。它的主要目的是，在預(yù)先指定的地點(diǎn)中選擇適當(dāng)數(shù)量的貨物以滿足客戶揀選要求。雖然揀選操作僅僅是物體在倉儲中裝卸操作之一，但它卻是“最耗時間和花費(fèi)最大的倉儲功能。許多情形下，倉儲盈利的高低就在于是否能將揀選操作運(yùn)行處理好”。（Bozer和White）Ratliff和Rosenthal，他們關(guān)于自動化立體倉庫系統(tǒng)（AS/RS）的揀選問題進(jìn)行的研究，發(fā)明了基圖算法，在階梯式布局中選取最短的訪問路徑。Roodbergen和deKoster拓展了Ratliff和Rosenthal算法。他們認(rèn)為，在平行巷道揀選問題上，應(yīng)該穿越巷道末端和中間端進(jìn)行揀選，就此他們發(fā)明了一種動態(tài)的規(guī)劃算法解決這問題。就此VandenBerg和Gademann發(fā)明了一種運(yùn)輸模型(TP)，它是對于指定的存儲和卸載進(jìn)行測算的儀器。他們表示，最好的解決運(yùn)輸問題的方法是以機(jī)械的最佳布局來盡量減少運(yùn)行時間。Elsayed對階梯結(jié)構(gòu)的立體倉庫問題的研究表明，要在多巷道中揀選貨物并擬定最佳方案，是非常困難和并且耗時的。Elsayed和Stern提出了啟發(fā)式算法，但據(jù)說，他們并沒有在實(shí)際生產(chǎn)過程中得到滿意的結(jié)果。黃禹錫等人，研究了立體倉庫系統(tǒng)中的單巷道選道的問題，并提出決定了每個S/R系統(tǒng)揀選效率的啟發(fā)式算法。Thealgorithms在聚集前人分析的基礎(chǔ)上，采取了一些相似的措施。在1983年，通過仿真，把計(jì)算得到的參數(shù)與Elsayed和Sterns的結(jié)論進(jìn)行了比較。Bozer、White、Han、Lee和Schaefer等人提出了一個程序，在檢索測序的基礎(chǔ)上進(jìn)行優(yōu)化，解決了線性分配的問題。Lee和Schaefer介紹了一些優(yōu)化和啟發(fā)式的測序方法，其中包括存儲指令如何被分配到預(yù)先確定的存儲位置。Mahajan通過對小件貨物的貯存系統(tǒng)進(jìn)行了改善，得到了一種新的檢索測序方案，提出最近檢索原則并開發(fā)了一個驗(yàn)證模型來預(yù)測效果。黃禹錫制作了非線性數(shù)學(xué)模型，開發(fā)出以一種啟發(fā)式程序設(shè)計(jì)的自動化立體倉，與此同時還可以確定單位負(fù)載的大小。VandenBerg和Rouwenhorst調(diào)查了倉庫規(guī)劃和控制的文獻(xiàn)，規(guī)劃文件包括存儲位置的分配問題，倉庫儲存系統(tǒng)的控制問題包括路由、排序、調(diào)度、停留點(diǎn)的選擇和秩序配料。Goetschalckx和Wei提交1985年至1992年揀選系統(tǒng)的參考文獻(xiàn)。Koh提出了一些關(guān)于在存儲倉庫中，帶有塔式起重機(jī)的自動化立體倉庫的模式。他們推論出的這個模式是建立在隨機(jī)存儲分配規(guī)則的基礎(chǔ)上的一個單、雙指令周期。他們還根據(jù)營業(yè)額的存儲分配規(guī)則計(jì)算出相應(yīng)行程時間。Koh提出了優(yōu)化模式，在揀選系統(tǒng)的巷道最末端尋找到了一個最佳緩沖的區(qū)域，在那里S/R系統(tǒng)可提供多若干個通行巷道。Amato以coloredtimedPetrinets網(wǎng)站的資料為基礎(chǔ)提出了對順序檢索的揀選優(yōu)化算法。他們還提出了兩項(xiàng)對于起重機(jī)和航天飛機(jī)的運(yùn)作的優(yōu)化控制算法。Hsu審議多巷道的倉庫的順序配料問題，提出了遺傳算法來減少總旅行距離。Hwang和Cho提出了采摘的供應(yīng)中心倉庫秩序的績效評估模式。他們研究的目的是通過減少運(yùn)輸數(shù)量、計(jì)算性能和設(shè)備利用率來減少盡量減少成本。在近期的研究中，DeKoster對設(shè)計(jì)與控制手冊中揀選工程的典型決定問題進(jìn)行了文獻(xiàn)回顧。他們主要關(guān)注于存儲分配方法、路徑的選擇、配料和分區(qū)。然而，我們沒有這么多的文獻(xiàn)上的知識，在處理自動化立體倉庫的揀選問題上，每個物品都能夠被儲存在多個儲存點(diǎn)里。事實(shí)上，許多廠家的產(chǎn)品有許多類型、種類和形狀，這也是他們成品倉庫面臨的問題。例如一個瓷磚制造商，他的產(chǎn)品有兩個類型（墻磚和地磚）,分別有7中不同的尺寸，4種不同耐久性（磨損差餉)和100多種不同的顏色、圖案、顏色和形狀，總共有5600多種不同的產(chǎn)品類型。作為存儲策略，要一件剛進(jìn)來的貨物存放在最近的空倉位位置上。當(dāng)一個來自倉庫中物品，由于產(chǎn)品種類繁多，有很大的可能性從一個地方存入到另一個地方。因此，一件物品需要有幾個在倉庫中存儲位置。換句話說，由于分類和分區(qū)，每個單獨(dú)類型的產(chǎn)品在倉庫中需要一個更大的空間，一個物品在幾個地方存儲時不可避免的。2.問題描述在本研究中，我們考慮到了小件物品的自動存儲和檢索系統(tǒng)，那有一個或多個巷道。每個巷道包含了關(guān)于巷道兩旁倉儲貨架。每個巷道結(jié)束的地方都有一個輸入/輸出口（I/O）。在那里還有一個單獨(dú)的存儲/檢索（S/R）的儀器來為所有巷道的系統(tǒng)服務(wù)，它可以同時在垂直和水平方向移動。因此，在兩點(diǎn)之間的行程等于最小的水平和垂直行程。在收到命令之前S/R儀器已經(jīng)定位了輸入/輸出口中的位置。儀器的起始位置取決于最后一件貨物的最后一個命令的存儲位置。S/R計(jì)算行程中以恒定的速度水平和垂直移動。一個命令可以由多個貨物請求組成的。同樣每個貨物也可以在倉庫中多個位置存儲。當(dāng)檢索請求包括多個貨物，并且這些貨物在多個不同的倉庫位置時，S/R儀器必須到多個不同的存儲地點(diǎn)完成各個命令。本次研究的目的就是提出計(jì)算方法來減少S/R走過的總時間來完成命令程序。3.運(yùn)算方法我們現(xiàn)在有兩種運(yùn)算方法來解決這個問題：一種是探索式算法，還有一種是遺傳式算法。為了顯示所提出算法的優(yōu)越性，我們把它與其他方法進(jìn)行了比較。由于我們的解決問題方法是新提出的，沒有前人在這個領(lǐng)域進(jìn)行過研究，那么我們最先提出的一種運(yùn)算法，用它來獲取的最佳的解決方案，這種方法我們稱它為例證算法。其結(jié)果作為對于兩種擬議算法比較的基準(zhǔn)解決方案。在例證法中，我們確定所有可行的解決方法并將他們互相比較找出最好的解決方法來。為此，這個方案首先要找所有可行的方法來選擇一個命令。然后，S/R系統(tǒng)的計(jì)算獲得每個方法行程的總時間，最后，選取的解決方案要求在最短時間內(nèi)完成要求。這個解決方案被認(rèn)為是該問題的最佳解決方案?？紤]到一個命令的由k種不同類型的貨物組成，其中在ni(i=1,2,...,k)項(xiàng)貨物中第i項(xiàng)貨物被提出請求。在可行的解決辦法總數(shù)挑選順序可以給出：其中，mi是在第i項(xiàng)貨物在倉庫中的總庫存，得出：通過例證法已經(jīng)解決了各種類型的問題，并且確定了這種低金額低行程的最佳方案。我們發(fā)現(xiàn)，在當(dāng)前巷道上存在貨物（如：該巷道的S/R系統(tǒng)是在檢索過程的起始端）是解決這個問題的關(guān)鍵技術(shù)。我們基于先前提到的運(yùn)算結(jié)果發(fā)現(xiàn)了一種計(jì)算方法，稱它為現(xiàn)有巷道探索式（CAH)算法。在現(xiàn)有巷道探索式算法中，在當(dāng)前巷道中現(xiàn)存的貨物是首先被檢索的對象。其后，對該命令的其余部分（如果有的話）選中并運(yùn)用各種檢索方式進(jìn)行研究計(jì)算。我們可以簡單的對其進(jìn)行表達(dá)，如果設(shè)r表示在現(xiàn)有巷道中指令貨物的數(shù)目，那么如果r=0時，該運(yùn)算方法就類似于原來的例證法。如果r=1時，該運(yùn)算方法首先要通過S/R系統(tǒng)對行程時間進(jìn)行計(jì)算，設(shè)t1表示在當(dāng)前巷道中，現(xiàn)存貨物為了避免與揀選中的貨物沖突，對于其余的貨物(如果有的話)進(jìn)行同等于例證法的計(jì)算，以此來得到最小的計(jì)算行程時間。設(shè)t2表示在S/R系統(tǒng)中總的行程時間。最后將t1和t2之和作為最終的解決方案。如果r>1時，則該方法首先分配揀選順序，揀選所有的r貨物，既巷道中的現(xiàn)存貨物。在計(jì)算好行程時間之后，進(jìn)入t1階段開始移除列表中指令的貨物。在這之后，其余貨物(如果有的話)進(jìn)行類似于例證法的運(yùn)算,就如同，通過對每一個可行的方法計(jì)算出行程時間，最終選取其中最小的那個值，即t2階段。最后，在S/R系統(tǒng)中將t1和t2的和設(shè)為最終的解決方案。Khojasteh-Ghamari詳細(xì)的對在現(xiàn)有巷道中的貨物的揀選順序的分配方法進(jìn)行了討論。如果任何待命的貨物存在于現(xiàn)有巷道中，那么就將倉庫中現(xiàn)存貨物的數(shù)目除以解決方案的數(shù)目。因此，這項(xiàng)任務(wù)目的就是降低總方案的數(shù)目，以此來減少CPU時間（程序的處理時間）。3.1.遺傳算法遺傳算法是一種優(yōu)化過程，它將問題域比作基因類（個體或染色體），基因類是有多個基因體組成，其中基因體成符號形式串行。每一個基因類都有一個可能的解，通過對問題域中的染色體進(jìn)行評估來尋求可能的解決方案。在每一代中，我們對每個染色體進(jìn)行評估，選擇一個分布優(yōu)秀的區(qū)域，在其中對染色體進(jìn)行變異和交叉操作，重新組合，得到新的染色體。這樣幾代之后，在進(jìn)一步觀察后沒有得到新進(jìn)展的情況下，那么就將所得到最具適應(yīng)度的染色體視為（所有可能的）最佳解決方案。運(yùn)算常常會在出現(xiàn)大量的迭代速度和資料后終止（Michalewicz）。表示法每一個染色體表示待求解問題的一個可能解，將其中每一個等位基因被歸為一個貨物序列中。如此類推，在染色體中的每個基因序列表示貨物的種類和相對等位基因的存儲位置。因此，每個解決方案包括一個染色體，其中基因的數(shù)量等于所收到命令的貨物數(shù)目。如給出一個例子，圖1如圖1可見，一個可行方案中的貨物設(shè)為A,B,C和D代碼，他們被檢索位置為：貨物C在5號位置，貨物B在7號位置，貨物A在4號位置，貨物D在3好位置。圖1.代表一個可行的解決方案其表格表示為，貨物被揀選的順尋也顯示在其中。在這個例子中，在5號位置中貨物C將被首先檢索，其次是貨物B，再是貨物A，最后是貨物D。初始化初始域是隨機(jī)產(chǎn)生的。擁有隨機(jī)序列的指令貨物組成了染色體。在染色體中，每個貨物被賦予一個隨機(jī)代號。由此可見，每個可行方案所給予的條件是相同的。然而，在每一次重新運(yùn)算過程中，都會有一套適合的程序來解決方案。因此，染色體中的指令貨物將會無重復(fù)的隨機(jī)分布，貨物的地址代碼也會隨機(jī)選取，所分配的代號范圍會在1到該貨物的總倉庫庫存數(shù)之間。假設(shè)在倉庫內(nèi)現(xiàn)有總共A、B、C和D4件貨物，它們分別對應(yīng)代碼是6、9、7和4。為了形成如圖1所示的解決方案，首先，指令貨物死隨機(jī)選取的（C,B,A和D），然后，貨物C選取[1,7]的隨機(jī)整數(shù)，貨物B在[1，9]中選取，A在[1,6]之間選取，最后D在[1，4]中間隨機(jī)選取一個。交叉操作在置換問題的操作描述里，部分匹配交叉（簡稱PMX）常被用于揀選問題上，部分匹配交叉被視為一種交叉的排列，它確保所有的貨物能迅速的被后裔所發(fā)現(xiàn)。也就是說，兩個后裔全面的接受了父輩基因，接著再填充到其父輩的等位基因上。在圖2中，兩個父輩用p1和p2來表示，交叉點(diǎn)是1和3。根據(jù)在相應(yīng)的[M,R]和[E,A]之間，重復(fù)做貨物的取代，這就是說，在第一個父輩中的A和E由R和M所取代，而在第二個父輩中的R和M就由A和E來取代。生成的后代是O1和O2(圖2)。同時，根據(jù)PMX中的揀選問題得知，交叉操作的關(guān)鍵是只交換在染色體中的貨物區(qū)域并且不交換相關(guān)的等位基因。圖2.PMX操作變異操作我們現(xiàn)在用二進(jìn)制位(0和1)來表示基因。在揀選的問題上，相關(guān)聯(lián)的等位基因通過變異操作，將庫存中一個基因替代另外一個等位基因。換而言之，這個操作并沒有對貨物的序列起到任何作用，僅僅只是貨物選擇了另外一個序列代碼。假設(shè)在O1中，第三個基因被選為變異基因。由于貨物A在各儲存位置上的總數(shù)有6個，通過變異操作在[1,6]范圍里產(chǎn)生隨機(jī)整數(shù)來代替原來的第三個基因(圖3)，當(dāng)然，產(chǎn)生的代碼等于現(xiàn)有代碼時(如2)，則操作重復(fù)進(jìn)行，直到取得一個新代碼(除了2)。在這個范例中，4就是最后產(chǎn)生的代碼。評估與選擇在每代中，對于染色體的評估使用了一些有效的方法。圖3.變異操作在大量的優(yōu)化應(yīng)用中，適應(yīng)度是對目標(biāo)客觀本質(zhì)的計(jì)算。在揀選問題中，目標(biāo)函數(shù)的作用是將S/R系統(tǒng)的行程時間降低到最小。通過S/R系統(tǒng)對總行程時間做標(biāo)準(zhǔn)化的計(jì)算來得到下一代。Khojasteh-Ghamari對S/R系統(tǒng)計(jì)算的行程時間進(jìn)行做了一下說明。由于這個問題是最小化的問題，所以我們可以將每個染色體的目標(biāo)函數(shù)值改變成適應(yīng)值，適應(yīng)值大的染色體就更具適應(yīng)能力，這樣就能更清晰的表達(dá)他們的價值程度(cheng等人提出)：其中，eval(vk)是第K個染色體的適應(yīng)函數(shù)，f(vk)是第k個染色體在S/R系統(tǒng)下總行程時間。問題域的大小(簡稱popsize)決定了每個染色體應(yīng)被給的時間。現(xiàn)在來做個比喻，我們對下一代染色體的選擇比作為(賭臺上的)輪盤，適應(yīng)度大的染色體在下一代遺傳中被選的概率更高。在此方案中，行程時間短的更容易被選中作下一代的遺傳。賭盤的執(zhí)行如下：1.計(jì)算對于每個染色體的vk(k=1,2,...,最大范圍值)在S/R系統(tǒng)的總行程時間。2.計(jì)算每個染色體的適應(yīng)度eval(vk)(k=1,2,...,最大范圍值)。3.求得所有適應(yīng)的總數(shù)量4.計(jì)算對于每個染色體Vk的選擇概率pk(k=1,2,...,范圍最大值)。5.計(jì)算每個染色體vk的累積概率qk(k=1,2,...,范圍最大值)。每次選擇是在旋轉(zhuǎn)的賭盤中進(jìn)行的，其結(jié)果是動態(tài)的，被選中的染色體作為下一代的范圍域。-生成的一個隨機(jī)實(shí)數(shù)r在[0，1]范圍內(nèi)；-如果r≤1，那么選擇的第一個染色體v1，否則選擇第k個染色體vk(2≤k≤popsize)，這樣就有qk?1<r≤qk。在上一代中的染色體被新一代的染色體所替代。4.仿真結(jié)果我們制作了一個擁有36種不同貨物的立體倉庫，在其中還有5種不同類型的指令，對此比較3種運(yùn)算法的性能。每個貨物首先先用例證法來解決。以獲取最佳的行程時間和CPU占用率。接著用另外兩種解法來解決。研究結(jié)果如下2表。4.1.仿真模型我們創(chuàng)建了一個在36種不同物理規(guī)格情況下的倉庫，通過對于每一個倉庫施加5種不同的指令來對這3種算法的性能進(jìn)行比較。每種情況首先按例證法來得到最佳的行程時間和CPU占用率，然后再通過另外兩種計(jì)算方法來解決問題。研究結(jié)果顯示在下面兩個表格中。利用倉庫的主要3個參數(shù)（倉儲容量、密度和形狀）來設(shè)計(jì)36種不同存儲的情況。由于倉儲容量與倉庫中的巷道成比例關(guān)系，我們將倉儲容量劃分為4種情況，分別是1、2、3和4種巷道的形式。每個倉儲貨架有780個存儲位置。因?yàn)槊總€巷道有兩個貨架，則一個巷道就擁有1560個存儲位置。由于一個系統(tǒng)對倉庫中大量巷道進(jìn)行服務(wù)的話，將會大大降低其系統(tǒng)實(shí)際效率。所以在不考慮5個或更多巷道的情況下，就由一個S/R系統(tǒng)對所有巷道進(jìn)行服務(wù)。對于倉儲密度，我們假定倉庫中的使用率為60%、75%和95%。Bozer和White對倉儲形狀的配置進(jìn)行了相關(guān)描述為，倉儲形狀，它是一種對于貨架高度與長度的空間比例，假設(shè)倉儲容量與S/R系統(tǒng)的水平和垂直速度都是常數(shù)。那么我們將這3個值設(shè)定為（0.6,0.73和1）。此外還要補(bǔ)充的是，對上述每種情況的描述中，5種不同的指令為別是1，2，3，4和5，5種所要求的貨物編碼分別是一，二，三，四和五。4.2.結(jié)果在個人電腦配置是：“奔騰III,1000MHz的處理器,512MB內(nèi)存和2GB虛擬內(nèi)存”的情況下進(jìn)行了試驗(yàn)。結(jié)果列于表1和表2中。表1表示在3種運(yùn)算法下，4種類型“S/R系統(tǒng)平均行程時間”和“S/R系統(tǒng)平均CPU占用率”。兩種倉儲參數(shù)（倉儲密度和形狀）的組合形成了每個倉庫(倉庫分別有1、2、3和4個巷道)的9種情況，每種情況下的值表示了5種命令下的平均值。表2表示在倉儲形狀為0.6和1，4種巷道情況下的平均行程時間和平均CPU占用率。在表格中，例證法、現(xiàn)有巷道探索式算法和遺傳算法分別用“Enumeration”，“CAH”，“GA”所表示。5.分析結(jié)果通過對表1分析可知，在所有情況下的各類倉庫(1，2，3和4個巷道)，CAH算法是能獲得最大行程時間和最小CPU占用率的解決方案。換而言之，它是占用較小CPU使用率的方法。然而，它對S/R系統(tǒng)的行程時間超過了其他兩個。在倉庫中只有一個巷道的情況下，通過遺傳算法解決獲得的方案中89%為最佳的方案。其余的方案里次優(yōu)和最優(yōu)的解決方案平均只相差0.09％（但需要更大的CPU時間）。在擁有2個3個和4個巷道的倉庫中，遺傳法提供的11%的解決方案為最佳方案，其余方案里，獲得方案與最佳方案差別不大，分別是2巷道相差3.86%，3巷道相差4.83%和4巷道相差4.69%。倉庫中巷道的層架數(shù)目會影響到運(yùn)算效率。由于增加的總數(shù)是實(shí)際問題中出現(xiàn)的，例證法中要增加較大的CPU占用率才能獲得最佳解決方案。然而在大多數(shù)情況下，遺傳法則需要相比于例證法較少的CPU占用率就能完成S/R系統(tǒng)的最佳方案。表格1.3種算法的性能表格2.3中算法在倉儲形狀上的比較此外，運(yùn)算方法的性能是受貨架配置所影響的。表2顯示了通過對S/R系統(tǒng)的平均行程時間和平均CPU占用率在多巷道中的兩種倉儲形狀（0.6和1）的比較。在此表中顯示了當(dāng)倉儲容量增加時，兩個貨架配置的算法比較。在一個倉庫只有一個巷道時，例證法提供了最佳的方案，并且它的CPU占用率低于遺傳法。然而，如果倉庫有多個巷道時，遺傳算法需要的CPU占用率低于例證法。由于各種倉儲形狀B的結(jié)果相似，我們將倉儲形狀B設(shè)為0.73。因?yàn)閷的3種算法性能大致相同，所以在倉庫里的貨架配置對算法性能沒有影響。6.總結(jié)在本次研究中，我們討論了多巷道自動化立體倉庫系統(tǒng)，并得到了結(jié)果。就同類貨物在不同存儲位置被尋找的情況下，我們發(fā)明了兩種算法來解決這個問題，我們將第一種探索式算法命名為現(xiàn)有巷道探索式算法（簡稱CAH），第二種命名為可接受遺傳算法。為顯示每種算法的實(shí)際效率，我們將他們與例證法做了對比，例證法在獲得最佳方案的同時需要大量的CPU占用率，因此它并不是最理想的解決方案。CAH算法需要較小的CPU占用率，但獲得的方案大多數(shù)是需要較長的S/R系統(tǒng)行程時間的次佳的方案。而遺傳算法提供的方案大多是最佳和準(zhǔn)佳(平均占3.37%)的方案。因此，模擬的遺傳算法顯示，它的效率高于其他兩種算法。不久的將來，在功效和雙命令（DC）的自動化倉庫系統(tǒng)領(lǐng)域中，將對元啟發(fā)式方法和分支定界算法進(jìn)行評估，以便能在自動化倉庫揀選問題上創(chuàng)造最佳的解決方案。7.鳴謝我們感謝來自TarbiatModarres大學(xué)M.M.Sepehri教授的寶貴建議。我們也同樣的感謝為我們提出建議的匿名審稿人。參考文獻(xiàn)[1]Amato,F.,Basile,F.,Carbone,C.andChiacchio,P.,Anapproachtocontrolautomatedwarehousesystems,ControlEngineeringPractice,Vol.13,pp.1223-1241,2005.[2]Bozer,Y.A.andWhite,J.A.,Travel-timemodelsforautomatedstorage/retrievalsystems,IIETransactions,Vol.16,No.4,pp.329-338,1984.[3]Bozer,Y.A.andWhite,J.A.,Designandperformancemodelsforend-of-aisleorderpickingsystems,ManagementScience,Vol.36,No.7,pp.852-866,1990.[4]Cheng,R.,Gen,M.andSasaki,M.,Film-copydelivererproblemusinggeneticalgorithms,Computers&IndustrialEngineering,Vol.29,pp.549-553,1995.[5]Elsayed,E.A.,Algorithmsforoptimalmaterialhandlinginautomaticwarehousingsystems,InternationalJournalofProductionResearch,Vol.19,pp.525-535,1981.[6]Elsayed,E.A.andStern,R.G.,Computerizedalgorithmsfororderprocessinginautomatedwarehousingsystems,InternationalJournalofProductionResearch,Vol.21,pp.579-586,1983.[7]Goetschalckx,M.andWei,R.,Bibliographyonorderpickingsystems,Vol.1,pp.1985-1992,1994,availableat/people/faculty/MarcGoetschalckx/research.html.[8]Han,M.-H.,McGinnis,L.F.,Shieh,J.S.andWhite,J.A.,Onsequencingretrievalsinanautomatedstorage/retrievalsystem,IIETransactions,Vol.19,pp.56-66,1987.[9]Hwang,H.,Baek,W.andLee,M.-K.,Clusteringalgorithmsfororderpickinginanautomatedstorageandretrievalsystem,InternationalJournalofProductionResearch,Vol.26,pp.189-201,1988.[10]Hwang,H.,Moon,S.andGen,M.,Anintegratedmodelforthedesignofend-of-aisleorderpickingsystemandthedeterminationofunitloadsizesofAGVs,Computers&IndustrialEngineering,Vol.42,pp.249-258,2002.[11]Khojasteh-Ghamari,Y.,OrderpickingprobleminanAS/RSwithmultiplestocklocations.M.Sc.thesis,Tarbiat[12]Koh,S.G.,Kim,B.S.andKim,B.N.,TraveltimemodelforthewarehousingsystemwithatowercraneS/Rmachine,Computers&IndustrialEngineering,Vol.43,pp.495-507,2002.[13]Koh,S.G.,Kwon,H.M.andKim,Y.J.,Ananalysisoftheend-of-aisleorderpickingsystem:Multi-aisleservedbyasingleorderpicker,InternationalJournalofProductionEconomics,Vol.98,pp.162-171,2005.[14]Lee,H.F.andSchaefer,S.K.,Retrievalsequencingforunit-loadautomatedstorageandretrievalsystemswithmultipleopenings,InternationalJournalofProductionResearch,Vol.34,pp.2943-2962,1996.[15]Lee,H.F.andSchaefer,S.K.,Sequencingmethodsforautomatedstorageandretrievalsystemswithdedicatedstorage,Computers&IndustrialEngineering,Vol.32,pp.351-362,1997.[16]Mahajan,S.,Rao,B.V.andPeters,B.A.,Aretrievalsequencingheuristicforminiloadend-ofaisleautomatedstorage/retrievalsystems,InternationalJournalofProductionResearch,Vol.36,pp.1715-1731,1998.[17]Michalewicz,Z.,GeneticAlgorithms+DataStructures=EvolutionPrograms,1992(SpringerVerlag:Berlin)[18]Ratliff,H.D.andRosenthal,A.S.,Order-pickinginarectangularwarehouse:asolvablecaseofthetravelingsalesmanproblem,OperationsResearch,Vol.31,pp.507-521,1983.[19]Roodbergen,K.J.anddeKoster,R.,Routingorderpickersinawarehousewithamiddleaisle,EuropeanJournalofOperationalResearch,Vol.133,pp.32-43,2001.[20]Rouwenhorst,B.,Reuter,B.,Stockeahm,V.,vanHoutum,G.J.,Mantel,R.J.andZijm,W.H.M.,Warehousedesignandcontrol:frameworkandliteraturereview,EuropeanJournalofOperationalResearch,Vol.122,pp.515-533,2000.[21]VandenBerg,J.P.,Aliteraturesurveyonplanningandcontrolofwarehousingsystems,IIETransactions,Vol.31,pp.751-762,1999.[22]VandenBerg,J.P.andGademann,A.J.R.M.,Optimalroutinginanautomatedstorage/retrievalsystemwithdedicatedstorage,IIETransactions,Vol.31,pp.407-415,1999.[23]Hsu,C.M.,Chen,K.Y.andChen,M.C.,Batchingordersinwarehousesbyminimizingtraveldistancewithgeneticalgorithms,ComputersinIndustry,Vol.56,pp.169-178,2005.[24]Hwang,H.S.andCho,G.S.,Aperformanceevaluationmodelfororderpickingwarehousedesign,Computers&IndustrialEngineering,Vol.51,pp.335-342,2006.[25]DeKoster,R.,Le-Duc,T.andRoodbergenK.J.,Designandcontrolofwarehouseorderpicking:Aliteraturereview,EuropeanJournalofOperationalResearch,Vol.182,pp.481-501,2007.

OrderPickingProbleminaMulti-AisleAutomatedWarehouseServedbyaSingleStorage/RetrievalMachineYaghoubKhojasteh-Ghamari Jae-DongSonUniversityofTsukubaSoongsilJapanKoreaAbstractRecenttechnologicaldevelopmentshaverevolutionizedthedesignandoperationofware-housingsystems.Automatedstorageandretrievalsystems(AS/RS)drivenbyembeddedcomputersarebecomingincreasinglymoreprevalent.TheincreaseduseofAS/RSiscreatingtheneedforcomputerizedcontrolalgorithmstosupporttheschedulingandpickingdecisions.Thisresearchaddressesanorderpickingprobleminamulti-aisleautomatedwarehouse,inwhichasinglestorage/retrieval(S/R)machineperformsstorageandretrievaloperations,andeachitemcanbefoundinseveralstoragelocations.OurobjectiveistoproposealgorithmsthatminimizethetotaltimetraveledbytheS/Rmachinetocompletetheretrievalprocessoforders.Wedevelopageneticalgorithmandanordinaryheuristic,andprovideaperformancecomparisonofthemwithoptimalsolution.Numericalresultsfromalargesetofproblemsarereported.Keywords:AutomatedWarehouse,AS/RS,OrderPicking,GeneticAlgorithms.1.IntroductionIntoday’smanufacturingenvironments,inventoriesaremaintainedatlowerlevelsthaninthepast.Thesereducedinventorieshaveledtosmallerstoragesystems,whichinturnhavecreatedtheneedforquickaccesstothematerialbeingheldinwarehouse.Hence,automatedstorageandretrievalsystems(AS/RS)usedinmanufacturing,ware-housing,anddistributionapplicationsmustbedesignedtoprovidequickresponsetimestoservicerequestsinordertokeepthesystemoperatingefficiently.OneimportantoperationalaspectoftheAS/RS,whichcontributestothesystemresponsetime,istominimizethetotaltimetraveledbytheS/Rmachinetocompletetheretrievalprocessoforders.Orderpickingisafundamentalcomponentoftheretrievalfunctionperformedinwarehouses.Themainpurposeofanorderpickingsystemistofillcustomerordersbyselectingtheappropriateamountofmaterialfromapre-designatedstoragemediumknownasthepickingorforwardarea.Orderpickingrepresentsonlyasubsetofthematerialhandlingoperationsperformedinwarehousing.However,itis‘oneofthemostcostlyandtime-consumingfunctionsofwarehousing.Inmanywarehouses,thedifferencebetweenprofitandlossdependsonhowwelltheorderpickingoperationisrun’(BozerandWhite).TherearemanystudiesonorderpickingproblemsinAS/RSandautomatedware-housingsystems.RatliffandRosenthaldevelopedagraph-basedalgorithmtofindtheshortestpathtovisitasetofpicklocationsinaladderlayout.RoodbergenanddeKosterextendedtheworkofRatliffandRosenthal.Theyconsideredtheorderpickingprobleminaparallelaislewarehouseinwhichorderpickerscancrossovertheaislesattheendsofaislesaswellasatamiddlecrossaisle.Theydevelopedadynamicprogrammingalgorithmtosolvetheproblem.VandenBergandGademanndevelopedatransportationproblem(TP)modelforablocksequencinginanAS/RSwithdedicatedstorageandasingle-loadmachine.TheyprovedthattheoptimalsolutionoftheTPproblemistheoptimalsequenceofthemachinetominimizethetravellingtime.Elsayedmadeachainofstudiesontheproblemofoptimallybatchingseveralordersinatwo-dimensionalwarehousewithladderstructure.Recognizingthattheexactsolutionsoftheproblemareverydifficultandtimeconsumingtoobtain,ElsayedandSternpresentedsomeheuristicalgorithms,butreportedthatnoneofthemproducesconsistentlysuperiorresultsthroughexperimentations.Hwangetal.studiedasimilarorderpickingprobleminasingle-aisleAS/RSandpresentedheuristicalgorithms,whichdetermineanefficientbatchingofordersforeachtouroftheS/Rmachine.Thealgorithmswerebasedonclusteranalysiswithsomesimilaritymeasures.Throughsimulation,theycomparedperformancesoftheproposedalgorithmswithElsayedandSterns’resultsin1983.BozerandWhite,Hanetal.,andLeeandSchaeferproposedaproceduretooptimizethesequencingofretrievalrequestsbasedonthesolutionofalinearassignmentproblem.LeeandSchaeferalsopresentedseveraloptimumandheuristicsequencingmethods,whereastoragerequestisassignedtoapredeterminedstoragelocation.Mahajanetal.developedaretrievalsequencingschemeaimedatimprovingthethroughputofminiloadAS/RS.Theyproposedanearest-neighborretrievalsequencingheuristicanddevelopedananalyticalmodeltopredictitsperformance.Hwangetal.formulatedanonlinearmathematicalmodelanddevelopedanefficientheuristicsolutionproceduretodesigntheAS/RSanddeterminetheunitloadsizeofthevehiclesimultaneously.VandenBergandRouwenhorstetal.surveyedliteratureonwarehouseplanningandcontrol.Planningincludesthestoragelocationassignmentproblem,andthecontrolofawarehousingsystemincludesrouting,sequencing,scheduling,dwell-pointselection,andorderbatching.GoetschalckxandWeipresentedabibliographyonorderpickingsystemsfor1985throughto1992.KposedsomemodelsfortraveltimesoftheS/Rmachineinawarehousewithatowercrane.Theyderivedthemodelsforbothsingleanddualcommandcyclesbasedontherandomizedstorageassignmentrule.Theyalsocalculatedthetraveltimeundertheturnover-basedstorageassignmentrulethroughanumericalapproach.Kposedanoptimizationmodeltofindanoptimalbuffersizeinend-of-aisleorderpickingsystem,whereasingleS/Rmachineservesseveralaisles.AposedanalgorithmtooptimallysequencetheretrievalordersbasedoncoloredtimedPetrinetsframework.Theyalsoproposedtwocontrolalgorithmstooptimizetheoperationsofthecranesandshuttle.Hsuetal.consideredtheorderbatchingprobleminamulti-aislewarehouseandproposedageneticalgorithmtominimizethetotaltraveldistance.HwangandChopresentedaperformanceevaluationmodelfortheorderpickingwarehouseinasupplycenter.Theobjectiveoftheirstudywastominimizethecostbyminimizingthenumberoftransportersandtocalculatetheperformanceandfacilityutilizationrate.Inarecentstudy,DeKosteretal.carriedoutaliteraturereviewontypicaldecisionproblemsindesignandcontrolofmanualorderpickingprocesses.Theyfocusedonoptimallayoutdesign,storageassignmentmethods,routingmethods,orderbatchingandzoning.However,wehavenoknowledgeofpapersintheliteraturethataddresstheorderpickingprobleminautomatedstorageandretrievalsystems,whereeachitemcanbestockedatseveralstoragelocations.Infact,somemanufacturerswhoseproductshavealargevarietyoftypes,shapes,andsizesarefacedwiththisproblemintheirfinishedgoodswarehouses.Atilemanufacturer,forexample,whoseproductsareintwotypes(wallandfloor),eachofwhichin7differentsizes,4groupsofdurability(P.E.I.WearRating),and100differentcolors,designsandshadeshastotally5600differentproducttypes.Asastoragepolicy,acomingpackofaproductintothewarehouseisplacedinthenearestemptystoragelocation.Whenanitemisretrievedfromthewarehouse,becauseofthelargevarietyoftheproducts,thereisastrongprobabilitythattheplacebefilledwithanothertype.Therefore,anitemcanbefoundinseveralstoragelocationsinthewarehouse.Inotherwords,sinceclassifyingandzoningeachindividualtypeofproductinthewarehouseneedsawarehousewithalargespace,thestorageofaniteminseveralplacesisunavoidable.2.ProblemDescriptionInthisresearch,weconsideraminiloadautomatedstorageandretrievalsystem,wherethereareoneormoreaisles.Eachaislecontainsastoragerackonbothsidesoftheaisle.Thereisaninput/output(I/O)stationattheendofeachaisle.Thereisalsoasinglestorage/retrieval(S/R)machinededicatedtoallaislesofthesystem,whichcansimultaneouslymoveinverticalandhorizontaldirections.Hence,thetraveltimebetweentwopointsisequaltothemaximumofthehorizontalandverticaltravels.TheS/RmachineispositionedatoneoftheI/Ostationsbeforethereceiptofanorder.Thestartingplaceofthemachinedependsonthestoragelocation(aisle)ofthelastitemofthelastorder.IncalculatingthetraveltimeoftheS/Rmachine,constantvelocitiesareusedforhorizontalandverticaltravels.Anordercanbearequestformorethanoneitem.Alsoeachitemcanbeinseveralstoragelocationsinthewarehouse.Whenretrievalrequestsconsistofmultipleitemsandtheitemsareinmultiplestocklocations,theS/Rmachinemusttraveltonumerousstoragelocationstocompleteeachorder.TheaimofthisresearchistoproposealgorithmstominimizethetotaltimetraveledbytheS/Rmachinetocompletetheretrievalprocessofanorder.3.TheAlgorithmsWepresenttwoalgorithmstosolvetheproblem:anordinaryheuristic,andasuitablegeneticalgorithm.Toshowthesuperiorityofthepresentedalgorithms,itisnecessarytocomparethemwithothermethodsaswellastheoptimalsolution.Sinceourproblemisnew,noresearchhasbeenconductedinthisfield,wefirstpresentanalgorithmtoobtainthebestsolutionfortheproblem,socalledtheenumerationalgorithm.Itsresultsareusedasbenchmarksolutionsforperformancecomparisonofthetwoproposedalgorithms.Intheenumerationalgorithm,weidentifyallfeasiblesolutionsandcomparethemwitheachothertofindthebestsolution.Todothis,themethodfirstfindsallfeasiblewaystopickanorder.Then,itcalculatesthetotaltimetraveledbytheS/Rmachineforeachone,andfinallyselectsthesolutionrequiringtheleastamountoftimetoaccomplishtheorder.Thissolutionisconsideredastheoptimumsolutionfortheproblem.Consideranorderconsistsofkdistincttypesofitems,inwhichni(i=1,2,...,k)itemsoftheithtypearerequested.Thetotalnumberoffeasiblesolutionstopicktheordercanbegivenby：where,miisthetotalinventoryoftheithtypeinthewarehouse,and.Havingsolvedvariousproblemsbytheenumerationalgorithmandidentifyingthebestsolutionthathadtheminimumamountoftraveltime,wefoundthattheexistingitemsinthecurrentaisle(i.e.theaisleinwhichtheS/Rmachineisinatthebeginningoftheretrievingprocess)arethekeytothefinalsolution.Wedevelopanalgorithmonthebasisofthementionedresults,andcallitthecurrent-aisleheuristic(CAH)algorithm.IntheCAHalgorithm,theexistingitemsinthecurrentaisleareselectedfirstforretrieval.Afterwards,theremainderoftheorder(ifany)isselectedandallthevariousretrievalmethodsarestudied.Wecansimplifythepreviousstatementsbystatingthatifrdenotesthenumberoftheordereditemsexistinginthecurrentaisle,andifr=0,themethodthenbecomessimilartotheenumerationalgorithm.Ifr=1,thenthemethodfirstcalculatesthetimetraveledbytheS/Rmachine,t1,foronlyoneexistingiteminthecurrentaisle,andremovesthatitemfromthelistofordereditems,andthenfortheremainingitems(ifany),itproceedsassameastheenumerationalgorithmtoobtaintheminimumtraveltime,t2.ThetotaltraveltimeoftheS/Rmachinewillbesumoft1andt2asthefinalsolution.Ifr>1,thenthemethodfirstassignsthepickingsequencetopickupallritemswhichexistinthecurrentaisle.Aftercalculatingthetraveltime,t1,itremovestheitemsfromthelistofordereditems.Then,fortheremainingitems(ifany),itproceedsliketheenumerationalgorithm,i.e.findingallfeasiblewaysfollowedbycalculatingthetraveltimeforeachoneandfinallyselectingtheminimumvalueamongthem,t2.ThetotaltraveledtimeoftheS/Rmachinewillbesumoft1andt2asthefinalsolution.Khojasteh-Ghamaridiscussedindetailthemethodofassigningapickingsequenceoftheordereditemsexistinginthecurrentaisle.Ifanyordereditemsexistinthecurrentaisle,thenthenumberofwaysstudiedwillbedividedbythenumberoftheitemsexistinginthewarehouse.Therefore,thistaskcausesthetotalnumberofpotentialsolutionstodecreasedramatically,andhence,theCPUtime(processtimeoftheprogram)wouldbedecreasedaswell.3.1.GeneticalgorithmAgeneticalgorithmisanoptimizationprocessthatemploysgenotypes(individualsorchromosomes)inapopulation,andthegenotypesaremadeofunitscalledgenesarrangedinlinearsuccession.Eachgenotypewouldrepresentapotentialsolutiontoaproblem;anevaluationprocessrunonapopulationofchromosomescorrespondstoasearchthroughaspaceofpotentialsolutions.Ineachgeneration,weevaluateeachchromosome,selectanewpopulationwithrespecttotheprobabilitydistributionbasedonfitnessvalues,andrecombinethechromosomesinthenewpopulationbymutationandcrossoveroperators.Afteranumberofgenerations,whennofurtherimprovementisobserved,thebestchromosomerepresentsanoptimal(possiblytheglobal)solution.Thealgorithmisoftenterminatedafterafixednumberofiterationsdependingonspeedandresourcecriteria(Michalewicz).RepresentationAchromosomerepresentsapotentialsolution,whereeachoneisviewedasasequenceofitemseachwithitsownassociatedallele.Byanalogy,eachgeneinachromosomerepresentstheitemtype,anditsassociatedallelerepresentsthestoragelocation.Therefore,eachpotentialsolutionconsistsofachromosome,inwhichthenumberofgenesisequaltothenumberofitemsinthereceivedorder.AnexampleisgiveninFigure1.Figure1showsapotentialsolutioninwhichtheitemswithcodesA,B,CandDhavebeenordered.ItemCwithlocationnumber5,itemBwithlocationnumber7,itemAwithlocationnumber4,anditemDwithlocationnumber3havebeenselectedforretrieval.Figure1.Representationofapotentialsolution.Itshouldbenotedthatthesequenceofpickingitemshasalsobeenconsideredintherepresentation.Inthisexample,itemCwithlocationnumber5willberetrievedfirst,